第3章线性表及其存储结构.ppt
3.1线性表的基本线性表的基本概念概念3.2线性表的顺序线性表的顺序存储及运算存储及运算3.3线性表的链式线性表的链式存储及运算存储及运算3.1 线性表的基本概念线性表的基本概念 线性表是由线性表是由 n(n0)个数据元素个数据元素 a1,a2,an 组成的一个有限序列。表中的每一个数据元组成的一个有限序列。表中的每一个数据元素，除了第一个外，有且只有一个前件；除素，除了第一个外，有且只有一个前件；除了最后一个外，有且只有一个后件。即线性了最后一个外，有且只有一个后件。即线性表或是一个空表或可以表示为：表或是一个空表或可以表示为：（a1,a2,ai,an）其中其中 ai（i=1,2,n)是属于数据对象的元素，通常也称其为线性是属于数据对象的元素，通常也称其为线性表中的一个结点。表中的一个结点。数据元素在线性表中的位置，只取决于它们数据元素在线性表中的位置，只取决于它们自己的序号自己的序号。非空线性表的结构特征为：非空线性表的结构特征为：有且只有一个根结点有且只有一个根结点a a1 1,它无前件；它无前件；有且只有一个终端结点有且只有一个终端结点a an n,它无后件；它无后件；除根结点与终端结点外，其他所有结点除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。线有且只有一个前件，也有且只有一个后件。线性表中结点的个数性表中结点的个数n称为线性表的长度。当称为线性表的长度。当 n=0时，称为空表。时，称为空表。在稍微复杂的线性表中，一个数据元素还在稍微复杂的线性表中，一个数据元素还可以由若干个数据项组成。例如，某班的学可以由若干个数据项组成。例如，某班的学生情况登记表是一个复杂的线性表，表中每生情况登记表是一个复杂的线性表，表中每一个学生的情况就组成了线性表中的每一个一个学生的情况就组成了线性表中的每一个元素，每一个数据元素包括学号、姓名、性元素，每一个数据元素包括学号、姓名、性别、入学成绩别、入学成绩4个数据项。个数据项。3.2线性表的顺序存储及其运算线性表的顺序存储及其运算 3.2.1 线性表的顺序存储线性表的顺序存储 线性表的顺序存储结构称为顺序表。线性表的顺序存储结构称为顺序表。线性表的顺序存储结构具有两个基本特点：线性表的顺序存储结构具有两个基本特点：线性表中所有元素所占的存储空间是连线性表中所有元素所占的存储空间是连续的；续的；线性表中各数据元素在存储空间中是按线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。逻辑顺序依次存放的。假设线性表中的第一个数据元素的存储地假设线性表中的第一个数据元素的存储地址（即首地址）为址（即首地址）为 ADR(aADR(a1 1)，每一个数据元，每一个数据元素占素占k k个字节，则线性表中第个字节，则线性表中第i i个元素个元素a ai i在计在计算 机 存 储 空 间 中 的 存 储 地 址 为：算 机 存 储 空 间 中 的 存 储 地 址 为：ADR(aADR(ai i)=ADR(a)=ADR(a1 1)+(i-1)k)+(i-1)k长度为长度为n n的线的线性表在性表在计算机计算机中的顺中的顺序存储序存储结构如结构如图图3-13-1所示。所示。在程序设计语言中，通常定义一个一维数组在程序设计语言中，通常定义一个一维数组来表示线性表的顺序存储空间。来表示线性表的顺序存储空间。应注意数组的基本类型要与线性表中数据元应注意数组的基本类型要与线性表中数据元素的类型相同。素的类型相同。数组需要根据情况预设足够的大小，同时数组需要根据情况预设足够的大小，同时还需要一个变量指出线性表在数组中的当前还需要一个变量指出线性表在数组中的当前状况，如元素个数或最后一个元素在数组中状况，如元素个数或最后一个元素在数组中的位置等。这两方面的信息共同描述一个顺的位置等。这两方面的信息共同描述一个顺序表，可将它们封装在一起。对序表，可将它们封装在一起。对C语言，顺语言，顺序表可定义如下：序表可定义如下：对对C语言，顺序表可定义如下：语言，顺序表可定义如下：#define MaxLength 50 typedef int ElemType;typedef struct ElemType listMaxLength;int length;SeqList;今后使用此定义时，今后使用此定义时，MaxLength及及ElemType要根据实际问题的需要可重新要根据实际问题的需要可重新选定。选定。3.2.2顺序表的基本运算顺序表的基本运算 1.1.顺序表的插入顺序表的插入 设长度为设长度为 n 的顺序表为（的顺序表为（a1,a2,ai,an），），要在顺序表的第要在顺序表的第i(1in)个元素个元素ai之前插之前插入一个新入一个新 元素元素x，插入后得到长度为，插入后得到长度为 n+1的的线性表线性表(a1,a2,ai-1,x,ai,an)，即，即(a1,a2,ai-1,ai,ai+1,an+1)，其中，其中ai 为新插入的元素为新插入的元素x，ai+1 为原表中的为原表中的ai，其，其余类推，余类推，an+1为原表中为原表中an。一般情况下，要在第一般情况下，要在第i(1in)个元素之个元素之前插入一个新元素时，首先要从最后一个元前插入一个新元素时，首先要从最后一个元素开始，直到第素开始，直到第i个元素之间共个元素之间共 n-i+1 个元个元素依次向后移动一个位置。移动结束时，第素依次向后移动一个位置。移动结束时，第i个位置就被空出，然后将新元素插入，插入个位置就被空出，然后将新元素插入，插入结束线性表的长度增结束线性表的长度增1 1。在平均情况下，插入。在平均情况下，插入一个新元素，需要移动表中一半的元素。一个新元素，需要移动表中一半的元素。注意：注意：若最后一个元素之后没有多余的自由若最后一个元素之后没有多余的自由空间（即表的大小空间（即表的大小n=MaxLength）时，那么）时，那么插入一个元素，将会发生上溢。插入一个元素，将会发生上溢。在顺序表在顺序表L L中的第中的第i i个元素之前插入一个新元个元素之前插入一个新元素素x x的算法的算法InsertListInsertList描述如下：描述如下：void InsertList(SeqList*L,int i,ElemType x)int j,n=L-length;if(in+1)printf(n i值不合法值不合法);exit(1);if(n=MaxLength)printf(n 表空间上溢表空间上溢);exit(1);for(j=n-1;j=i-1;j-)L-listj+1=L-listj;/*数据元数据元素依次向后移动一个位置素依次向后移动一个位置*/L-listi-1=x;/*插入插入x*/L-length+;/*表长增加表长增加1*/2.顺序表的删除顺序表的删除 通常，在长度为通常，在长度为 n 的顺序表中，要删除线的顺序表中，要删除线性表的第性表的第i(1in)个元素个元素ai。得到长度为。得到长度为 n-1n-1的线性表的线性表(a(a1 1,a a2 2,a ai-1i-1,a ai+1i+1,a an n)。即即(a1,a2,ai-1,ai,ai+1,an-1)，其，其中中ai 为原表中的为原表中的ai+1，其余类推，其余类推，an-1为为原表中原表中an。一般情况下，要删除第一般情况下，要删除第i(1in)个个元素，需要从第元素，需要从第i+1 个元素开始，直到第个元素开始，直到第n 个元素之间，共有个元素之间，共有n-i 个元素依次向前移动个元素依次向前移动了一个位置。删除结束后，顺序表的长度就了一个位置。删除结束后，顺序表的长度就缩小了。在平均情况下，要在顺序表中删缩小了。在平均情况下，要在顺序表中删除一个元素，需要移动表中一半的元素。除一个元素，需要移动表中一半的元素。在顺序表在顺序表L L中删除第中删除第i i个元素并用个元素并用x x 返回其返回其值的算法值的算法DeleteListDeleteList描述如下：描述如下：void DeleteList(SeqList*L,int i,ElemType*x)int j,n=L-length;if(in)printf(n i值不合法值不合法!);exit(1);*x=L-listi-1;/*将被删元素的值，赋给将被删元素的值，赋给*x*/for(j=i;jlistj-1=L-listj;/*元素依次向前移动一个位置元素依次向前移动一个位置*/L-length-;/*表长减少表长减少1*/3.顺序表的初始化顺序表的初始化 构造一个空的顺序表构造一个空的顺序表L（即表的初始化）的（即表的初始化）的算法如下：算法如下：void InitList(SeqList*L)/*构造一个空的顺序表构造一个空的顺序表L*/L-length=0;/*线性表长度赋线性表长度赋0值值*/4.顺序表的长度顺序表的长度 确定顺序表确定顺序表L的长度算法如下：的长度算法如下：int ListLength(SeqList*L)/*求线性表求线性表L的长度的长度*/return(L-length);/*返回返回L的长度的长度*/5.5.取顺序表的第取顺序表的第i i个元素个元素 从顺序表中取第从顺序表中取第i（1in）个数据元素的算）个数据元素的算法如下法如下:(用于在表中用于在表中随机的访问任意一个结点随机的访问任意一个结点)ElemType GetElem(SeqList*L,int i)/*取表中第取表中第i个数据元素个数据元素*/if(iL-length)printf(n i值非法值非法!);exit(1);return(L-listi-1);6.6.顺序表的定位运算顺序表的定位运算 根据某个指定的元素值或数据项的值根据某个指定的元素值或数据项的值x，对对顺序表顺序表L进行查找，若进行查找，若L中有元素的值与中有元素的值与x相同，相同，则返回首次找到的元素在则返回首次找到的元素在L中的位置；若查找中的位置；若查找失败，则返回失败，则返回-1的算法如下：的算法如下：int LocateElem(SeqList*L,ElemType x)/*查找与查找与x相匹配的元素并返回相匹配的元素并返回其其位置位置*/int i=0,n=L-lenth;if(n=0)printf(n Empty List!);exit(1);/*若空表，则返回若空表，则返回*/while(ilisti-1!=x)i+;if(inext=NULL;/*表初值为空表初值为空*/rear=H;/*尾指针指向表头结点尾指针指向表头结点*/while(ch=getchar()!=n)p=(LinkList)malloc(sizeof(ListNode);/*生成新结点生成新结点*/if(!p)printf(n 存储分配失败存储分配失败);exit(1);p-data=ch;p-next=p;/*新结点插入表尾新结点插入表尾*/rear=p;/*尾指针指向新结点尾指针指向新结点*/return(H);/*返回头指针返回头指针*/后进先出表：后进先出表：在建立单连表时，将每次在建立单连表时，将每次生成的新结点，总是插入到当前链表的表头生成的新结点，总是插入到当前链表的表头结点之后作为当前链表的首结点。若用换行结点之后作为当前链表的首结点。若用换行符符nn作为输入结束标志，则建立带表头结作为输入结束标志，则建立带表头结点的后进先出单链表的算法如下：点的后进先出单链表的算法如下：LinkList CreateList_fr()LinkList H,p;char ch;H=(LinkList)malloc(sizeof(ListNode);/*生成表头结点生成表头结点*/if(!H)printf(n 存储分配失败存储分配失败);exit(1);H-next=NULL;/*表初值为空表初值为空*/while(ch=getchar()!=n)p=(LinkList)malloc(sizeof(ListNode);/*
