第3章线性表及其存储结构.ppt

《第3章线性表及其存储结构.ppt》由会员分享，可在线阅读，更多相关《第3章线性表及其存储结构.ppt（70页珍藏版）》请在课桌文档上搜索。

1、第3章 线性表及其存储结构,3.1线性表的基本概念3.2线性表的顺序存储及运算3.3线性表的链式存储及运算,3.1 线性表的基本概念,线性表是由 n(n0)个数据元素 a1,a2,an 组成的一个有限序列。表中的每一个数据元素，除了第一个外，有且只有一个前件；除了最后一个外，有且只有一个后件。即线性表或是一个空表或可以表示为：（a1,a2,ai,an）其中 ai（i=1,2,n)是属于数据对象的元素，通常也称其为线性表中的一个结点。,数据元素在线性表中的位置，只取决于它们自己的序号。非空线性表的结构特征为：有且只有一个根结点a1,它无前件；有且只有一个终端结点an,它无后件；除根结点与终端结点

2、外，其他所有结点有且只有一个前件，也有且只有一个后件。线性表中结点的个数n称为线性表的长度。当 n=0时，称为空表。,在稍微复杂的线性表中，一个数据元素还可以由若干个数据项组成。例如，某班的学生情况登记表是一个复杂的线性表，表中每一个学生的情况就组成了线性表中的每一个元素，每一个数据元素包括学号、姓名、性别、入学成绩4个数据项。,3.2线性表的顺序存储及其运算,3.2.1 线性表的顺序存储 线性表的顺序存储结构称为顺序表。,线性表的顺序存储结构具有两个基本特点：线性表中所有元素所占的存储空间是连续的；线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。,假设线性表中的第一个数据元素的存储地址

3、（即首地址）为 ADR(a1)，每一个数据元素占k个字节，则线性表中第i个元素ai在计算机存储空间中的存储地址为：ADR(ai)=ADR(a1)+(i-1)k,长度为n的线性表在计算机中的顺序存储结构如图3-1所示。,在程序设计语言中，通常定义一个一维数组来表示线性表的顺序存储空间。应注意数组的基本类型要与线性表中数据元素的类型相同。,数组需要根据情况预设足够的大小，同时还需要一个变量指出线性表在数组中的当前状况，如元素个数或最后一个元素在数组中的位置等。这两方面的信息共同描述一个顺序表，可将它们封装在一起。对C语言，顺序表可定义如下：,对C语言，顺序表可定义如下：#define MaxLen

4、gth 50 typedef int ElemType;typedef struct ElemType listMaxLength;int length;SeqList;今后使用此定义时，MaxLength及ElemType要根据实际问题的需要可重新选定。,3.2.2顺序表的基本运算,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，其

5、余类推，an+1为原表中an。,一般情况下，要在第i(1in)个元素之前插入一个新元素时，首先要从最后一个元素开始，直到第i个元素之间共 n-i+1 个元素依次向后移动一个位置。移动结束时，第i个位置就被空出，然后将新元素插入，插入结束线性表的长度增1。在平均情况下，插入一个新元素，需要移动表中一半的元素。,注意：若最后一个元素之后没有多余的自由空间（即表的大小n=MaxLength）时，那么插入一个元素，将会发生上溢。在顺序表L中的第i个元素之前插入一个新元素x的算法InsertList描述如下：,void InsertList(SeqList*L,int i,ElemType x)int

6、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-1的线性表(a1,a2,ai-1,ai+1,an)。,即(a1,a2,ai-1,ai,ai+1,an-1)，其中ai 为原表中的ai+1

7、，其余类推，an-1为原表中an。,一般情况下，要删除第i(1in)个元素，需要从第i+1 个元素开始，直到第n 个元素之间，共有n-i 个元素依次向前移动了一个位置。删除结束后，顺序表的长度就缩小了。在平均情况下，要在顺序表中删除一个元素，需要移动表中一半的元素。在顺序表L中删除第i个元素并用x 返回其值的算法DeleteList描述如下：,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=

8、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.取顺序表的第i个元素 从顺序表中取第i（1in）个数据元素的算法如下:(用于在表中随机的访问任意一个结点)ElemT

9、ype GetElem(SeqList*L,int i)/*取表中第i个数据元素*/if(iL-length)printf(n i值非法!);exit(1);return(L-listi-1);,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);/*若

10、空表，则返回*/while(ilisti-1!=x)i+;if(in)return(i+1);/*找到返回其位置*/else return(-1);/*查找失败返回-1*/,从上面的讨论可知，在顺序表中插入或删除一个数据元素的时间要消耗在移动元素上，而移动元素的个数取决于表长n及插入或删除元素的位置i。假设在长度为n的顺序表的任意位置i（1in）插入一个元素的概率为pi=1/(n+1)，所需移动元素的次数为n-i+1，那么每插入一个元素，所需移动元素的次数的平均值为：Ais=n/2,在表中插入一个元素，平均要移动一半的元素，平均时间复杂度为O(n)。最好的情况是在表尾插入时，不需要移动元素；最

11、坏的情况是在表头插入时，需要移动表中n个元素。,假设，在长度为n的顺序表的任意位置i（1in）删除该位置元素的概率为qi=1/n，所需移动元素的次数为n-i，那么，每删除一个元素，所需移动元素的次数的平均值为：Ade=(n-1)/2,在顺序表中删除一个元素，平均约移动表中一半的元素。平均时间复杂度为O(n)。最好的情况是当i=n，即在表尾删除时，不需要移动元素；最坏的情况是当i=1，即在表头删除时，需要移动表中n-1个元素。,3.3线性表的链式存储及其运算,线性表的顺序存储结构存在缺点 是：插入与删除操作，需大量移动数据元素；再者，在顺序存储结构下，线性表的长度估计困难，并且当有多个顺序表同时

12、共享计算机的存储空间时，不便于对存储空间进行动态分配。,由于线性表的顺序存储结构存在以上缺点，因此，对于大的线性表，特别是元素变动频繁的大线性表，不宜采用顺序存储结构，而是采用下面介绍的链式存储结构。,3.3.1线性表的链式存储,假设数据结构中的每一个数据结点对应于一个存储单元，这种存储单元称为存储结点，简称结点。若每个结点由两部分组成：一部分用于存放数据元素值，称为数据域；另一部分用于存放指针，称为指针域。其中指针用于指向该结点的前一个或后一个结点。通过每个结点的指针域将n个结点按其逻辑顺序连接在一起而构成的数据存储结构，称为链式存储结构。,链式存储结构，既可用来表示线性结构，也可用来表示非

13、线性结构。线性表的链式存储结构，称为线性链表。对线性链表而言，它不要求逻辑上相邻的元素在物理位置上也相邻。其存储单元既可以是连续的，也可以是不连续的，甚至可以零散分布在内存中的任何位置上。,通常，为了适应线性链表的存储，计算机的存储空间被划分成一个一个的小块，每一小块占若干字节，这些小块就是存储结点。存储结点的结构，如图 3-2 所示。,在图中，data域就是数据域（或称值域），next域就是指针域（或称链域）,在线性链表中，用一个专门的头指针 head指向线性链表中第一个数据元素的结点（即存放线性链表中第一个数据元素的存储序号）。线性链表中最后一个元素没有后件，因此，线性链表中最后一个结点的

14、指针域为空（用NULL 或0表示），表示链表终止。,用下面例子，来说明线性链表的存储结构。设线性表为(a1，a2，a3，a4),存储空间具有9个存储结点，该线性表在存储空间中的物理存储状态如图3-3(下页)所示。该线性链表的逻辑状态如图3-4所示。,图3-3 线性链表的物理存储状态举例,3.3.2线性链表的基本运算,1.单链表的基本运算单链表结构类型定义如下：typedef struct node ElemType data;/*数值域*/struct node*next;/*指针域*/ListNode,*LinkList;,为了便于实现插入、删除结点的操作，通常在单链表的第一个结点之前增设一

15、个表头结点。该结点的结构与表中其他结点的结构相同，其数据域可以不存储任何信息，也可以存储如线性表的表名、长度等附加信息；其指针域用来存放线性表中的第一个结点的地址。若线性表为空表，则表头结点的指针域为空，设H为单链表的头指针，指向头结点；存储单链表的第一个元素的结点称为开始结点（或称首结点），其指针域存放第二个结点的地址；称存储最后一个元素的结点称终端结点（或称尾结点），其指针域为空，如图3-5所示。,1）建立单链表,依据新结点插入位置的不同，将生成的单链表分为先进先出、后进先出及有序三种。先进先出单链表：在建立单链表时，将每次生成的新结点，总是插入到当前链表的表尾作为尾结点。,若用换行符n作

16、为输入结束标志，用rear作为总是指向链表尾结点的尾指针，则建立带表头结点的先进先出单链表的算法如下：,LinkList CreateList_ff()LinkList H,p,rear;char ch;H=(LinkList)malloc(sizeof(ListNode);/*生成表头结点*/,if(!H)printf(n 存储分配失败);exit(1);H-next=NULL;/*表初值为空*/rear=H;/*尾指针指向表头结点*/while(ch=getchar()!=n)p=(LinkList)malloc(sizeof(ListNode);/*生成新结点*/,if(!p)print

17、f(n 存储分配失败);exit(1);p-data=ch;p-next=p;/*新结点插入表尾*/rear=p;/*尾指针指向新结点*/return(H);/*返回头指针*/,后进先出表：在建立单连表时，将每次生成的新结点，总是插入到当前链表的表头结点之后作为当前链表的首结点。若用换行符n作为输入结束标志，则建立带表头结点的后进先出单链表的算法如下：,LinkList CreateList_fr()LinkList H,p;char ch;H=(LinkList)malloc(sizeof(ListNode);/*生成表头结点*/,if(!H)printf(n 存储分配失败);exit(1)

18、;H-next=NULL;/*表初值为空*/while(ch=getchar()!=n)p=(LinkList)malloc(sizeof(ListNode);/*生成新结点*/,if(!p)printf(n 存储分配失败);exit(1);p-data=ch;p-next=H-next;H-next=p;/*插入表头结点之后*/return(H);/*返回头指针*/,有序单链表：是指原表中结点的数据值，按从小到大（或从大到小）的顺序排列。为了建立一个有序单链表，每次生成的新结点，总是插入到当前链表的合适位置。在带表头结点的单链表中，所有位置上的插入操作都是一致的，不需要做特殊处理。,若用换行

19、符n作为输入结束标志，pre为指向当前结点前件的指针、cur为指向当前结点的指针，则建立带表头结点的有序单链表的算法如下：,LinkList CreateList_or()LinkList H,pre,cur;/*pre将指向当前结点的前件，cur将指向当前结点*/char ch;H=(LinkList)malloc(sizeof(ListNode);/*生成表头结点*/if(!H)printf(n 存储分配失败);exit(1);,H-next=NULL;/*表初值为空*/while(ch=getchar()!=n)pre=H;/*pre指向当前结点的前件*/cur=H-next;/*cur

20、指当前结点*/while(cur,cur=(LinkList)malloc(sizeof(ListNode);/*生成新结点*/if(!cur)printf(n 存储分配失败);exit(1);cur-data=ch;cur-next=pre-next;/*新结点插在pre所指结点的后面*/,pre-next=cur;/*尾指针指向新结点*/return(H);/*返回头指针*/容易看出，以上3个算法的时间复杂度均为O(n)。,2）查找结点 在对单链表进行插入或删除运算时，总是首先要找到插入或删除的位置，这就需要对线性链表进行扫描查找。,通常，有查找第i个结点或查找具有给定元素值的结点，两种情

21、况。查找单链表中的第i个结点 在带表头结点的单链表中，查找第i个结点。不能像在顺序表中那样，只能从单链表的头指针出发，沿着结点的链域逐个向下，直到搜索到第i个结点为止。此时，p指向第i个结点。在带表头结点的单链表H中，查找第i个结点的算法如下：,LinkList GetElem(LinkList H,int i)int j=1;/*j累计当前扫描的结点数*/LinkList p;p=H-next;/*p指向第一个结点*/while(p,if(j=i/*第i个结点不存在，返回NULL*/在单链表中查找给定值的结点 依据给定的数据项的值x，在带表头结点的单链表中查找。若找到，则通过i返回首次找到的

22、结点的位置，同时，返回指向该结点的指针p。若查找失败，则返回NULL。,在带表头结点的单链表H中查找x的算法：LinkList LocateElem(LinkList H,ElemType x,int*i)LinkList p;/*p为指针*/p=H-next;/*p指向第一个结点*/*i=1;while(p,if(p-data=x)return(p);/*找到返回结点位置*/else return(NULL);/*没找到返回NULL*/以上两个，查找算法的时间复杂度均为O(n)。3）单链表的插入 单链表的插入，是指在单链表中插入一个新结点。有两种情况：在单链表的第i个位置插入一个新结点和在有

23、序单链表中插入一个新结点。,在单链表的第i个位置插入一个新结点 假设单链表中有n个结点，插入位置i的允许取值范围为1至n+1。在第i个位置插入一个新结点，首先，要找到第i-1个结点，然后将新结点插入到第i-1个结点之后。若指针pre指向第i-1个结点，cur指向新结点，插入就是让新结点的指针域指向原来的第 i个结点，即cur-next=pre-next，并且修改第i-1个结点的指针域，让其指向新结点。即pre-next=cur。插入过程如图3-6所示：,在第i个位置，插入一个值为x的新结点算法：InsertList(LinkList H,int i,ElemType x)LinkList pr

24、e,cur;pre=GetElem(H,i-1);/*调用查找函数使pre指向第i-1个结点*/,if(!pre)printf(n i值不合法);exit(1);cur=(LinkList)mallco(sizeof(ListNode);/*生成新结点*/if(!cur)printf(n 存储分配失败);exit(1);,cur-data=x;/*新结点的值为x*/cur-next=pre-next;/*新结点的指针域值指向原来的第i个结点*/pre-next=cur;/*第i-1个结点的指针域值指向新结点*/,在有序单链表中插入一个新结点 要在一个带表头结点的有序单链表H中插入一个值为x的新

25、结点。就必须对生成的新结点，依据值x的大小在表中找到合适的插入位置，然后将其插入到链表中。算法如下：,InsertOrder(LinkList H,ElemType x)LinkList cur,pre;pre=H;cur=H-next;while(cur/*cur指向当前结点*/,cur=(LinkList)malloc(sizeof(ListNode);/*生成新结点*/if(!cur)printf(n 存储分配失败);exit(1);cur-data=x;/*新结点值为x*/cur-next=pre-next;/*插入新结点*/pre-next=cur;/*pre指向新结点*/,从单链表

26、插入新结点的过程中，可以看出对线性链表进行插入操作时，没有发生数据元素的移动，只是改变了有关结点的指针域。在以上两个插入结点的算法中，时间复杂度的数量级均为O(n)。,4）单链表的删除操作 单链表的删除操作，是指在单链表中，删除包括指定元素的结点。有两种情况：一是删除单链表的第i个结点，二是删除单链表中，具有给定值x的结点。均不移动表中的数据元素，只需改变，被删除结点的前一个结点指针。,删除单链表的第i个结点 设单链表中有n个结点，删除第i个结点时，i的允许取值范围为1至n。与插入类似，首先要找到第i-1个结点。再用指针pre指向该结点，用指针cur指向第i个结点。然后使第i-1个结点的指针指

27、向第i+1个结点(pre-next=cur-next)。最后用函数free释放第i个结点所占空间。删除过程如图3-7所示。在带表头结点的单链表H中，删除第i个结点的算法如下：,DeleteList1(LinkList H,int i,ElemType*x)LinkList pre,cur;pre=GetElem(H,i-1);/*用GetElem函数找第i-1个结点并使pre指向它*/,if(pre=NULL|pre-next=NULL)/*判断i值是否合法*/printf(n i值不合法!);exit(1);cur=pre-next;/*cur指第i个结点*/pre-next=cur-nex

28、t;/*使第i-1个结点的指针指向第i+1个结点*/*x=cur-data;/*第i个结点的值由x返回*/free(cur);/*释放第i个结点所占的空间*/,删除单链表中具有给定值的结点 在带表头结点的单链表H中，搜索具有给定值x的结点，若找到，就删除该结点。这种删除情况的算法如下：,DeleteList2(LinkList H,ElemType x)LinkList p,pre;p=H-next;/*p指向链表的第1个结点*/pre=H;/*pre指向第1个结点的前件*/,while(p/*释放值为x的结点空间*/,else printf(n 链表中没有具有值为x的结点);此算法的时间复杂

29、度的数量级为O(n)。,2.循环链表及其基本运算 从单链表任一结点出发查找其前面的结点是很困难的。为了克服这一缺点，我们使带表头结点的单链表中的最后一个结点的指针指向头结点，使整个链表构成一个环形，这种链式存储结构被称为循环链表，如图3-8所示。特别地，只有头结点的循环链表称为空循环链表，如图3-9所示。,带头结点的循环链表中，可看出循环链表的结构与前面所讨论的单链表相比，具有以下两个特点：,1）头结点的数据域为任意或者根据需要来设置，头结点的指针域指向线性表的第一个元素的结点，头指针指向表头结点。2）最后一个结点的指针域不是NULL，而是指向表头结点。即在循环链表中没有空指针，所有结点的指针

30、构成了一个环状链。在循环链表中，只要指出表中任何一个结点的位置，就可以从它出发访问到表中其他所有的结点，而线性单链表做不到这一点。,循环链表的插入和删除的方法与线性单链表基本相同，不再赘述。只须注意一点：在单链表的结构中，空表的条件是H-next=NULL,而在循环链表结构中，空表的条件是H-next=H。,3.双向链表 从循环链表的结构特征可看出，若要找一个结点的直接前件结点需要兜一个圈子才行，这当然是很不方便的。就像乘单向环行的公交车一样，若坐过了站，就要多坐许多站,才能到达预定的地点。因此，任何城市的公交车，除单行道外，都是双向行驶的。为类似的目的，可以将单向链表改为双向链表。,双向链表

31、的每个结点含有两个指针域：一个指向其直接前件结点，称为prior；一个指向其直接后件结点，称为next。双向链表结点的结构如图3-10所示，双向链表的逻辑结构如图3-11所示。,有了两个方向的链指针之后，在链表上进行访问非常方便，但是在双向链表上进行插入和删除运算，要涉及两个指针的链接，故比单链表的插入与删除运算复杂些。,3.3.3线性链表应用举例,设多项式Pn(x)=a0+a1x+a2x2+anxn 其中ai(i=0,1,2,n)是x的i次幂的系数（即x的幂指数为i）。线性表（a0,a1,a2,an）可唯一确定多项式Pn(x)。两个多项式相加，如果采用顺序存储结构来存储此线性表，由于多项式中

32、可能有多项的系数为0，顺序存储就会浪费大量存储空间。故应采用单链表来存储该线性表。在单链表中，每个结点设3个域，分别为系数域coef，指数域exp和指针域next。结点结构如图3-12所示。,例如，多项式a(x)=4+3x+7x5+8x7与多项式b(x)=3-7x5+6x6 相加，所得的和，为多项式c(x)=a(x)+b(x)=7+3x+6x6+8x7的单链表形式，如图3-13所示：。,从图3-13可清楚地看出，多项式a(x)与b(x)相加的结果为多项式c(x)，变成由单链表Ha和Hb，求单链表Hc了。,假设单链表是以x的幂指数值的递增顺序排列。指针pa、pb分别指向Ha、Hb当前正被考察的两

33、个结点。,比较两个结点的指数域，有以下3种情况：,pa-expexp，将pa所指的结点插入到Hc链表中，移动指针pa指向下一结点。pa-exppb-exp，将pb所指的结点插入到Hc链表中，移动指针pb指向下一结点。pa-exp=pb-exp，将两个结点中的系数相加，若和不为0，则插入到Hc链表中，移动指针pa、pb，指向下一结点。重复上述过程，直至pa或pb的值为NULL。当其中一个为空时，说明该表的结点已经处理完，只要将另一表的剩余部分链接到Hc链表之后。,将两个多项式a(x)和b(x)相加生成c(x)的程序见教材 P24-27。,定义链表结点结构如下：typedef struct node float coef;/*coef为多项式项的系数*/int exp;/*exp为多项式项的x幂指数*/struct node*next;ListNode,*LinkList;/*说明ListNode为结构体变量,LinkList为结构体指针*/,运行该程序的例子如下：Pleas input n:4Input coef and exp:4 0 3 1 7 5 8 7Pleas input n:3Input coef and exp:3 0-7 5 6 6Output coef and exp of c(x):7 0 3 1 6 6 8 7,