大学数据结构课件线性表.ppt

1、主要知识点主要知识点线性表抽象数据类型线性表抽象数据类型顺序表顺序表单链表单链表循环链表与双向链表循环链表与双向链表1.1.线性表的定义线性表的定义 线性表是线性表是n(n0)个数据元素的有限序列。由相同类型个数据元素的有限序列。由相同类型数据元素（数据元素（a1, a2, an）组成的线性结构。数据元素之间组成的线性结构。数据元素之间存在着线性的逻辑关系：存在着线性的逻辑关系：（1）表中有且仅有一个开始结点；）表中有且仅有一个开始结点；（2）表中有且仅有一个终端结点；）表中有且仅有一个终端结点；（3）除开始结点外，表中每个结点均只有一个前趋）除开始结点外，表中每个结点均只有一个前趋结点（结点

2、（Predecessor）;（4）除终端结点外，表中每个结点只均只有一个后）除终端结点外，表中每个结点只均只有一个后继结点（继结点（Successor）2.2.线性表抽象数据类型线性表抽象数据类型数据对象数据对象: a1, a2, , an, ai的数据类型为的数据类型为ElemType操作集合操作集合:(1) Initiate(L) 初始化线性表初始化线性表(2) Length(L) 求当前数据元素个数求当前数据元素个数(3) Insert(L, i, x) 插入数据元素插入数据元素*(4) Delete(L, i) 删除数据元素删除数据元素*(5) Get(L, i) 取数据元素取数据元素

3、逻辑关系逻辑关系: , 对对ai，当，当1in时，它有一个直时，它有一个直接前趋接前趋ai-1；当；当1in时，它有一个直接后继时，它有一个直接后继ai+1。(6) Locate(L, x) 确定确定x在表中的位置在表中的位置1.顺序表的存储结构顺序表的存储结构 实现顺序存储结构的方法是实现顺序存储结构的方法是使用数组使用数组。数组把线性表。数组把线性表的数据元素存储在一块的数据元素存储在一块连续地址空间连续地址空间的内存单元中，这样的内存单元中，这样线性表中逻辑上相邻的数据元素在物理存储地址上也相邻。线性表中逻辑上相邻的数据元素在物理存储地址上也相邻。数据元素间的逻辑上的前驱、后继逻辑关系就

4、表现在数据数据元素间的逻辑上的前驱、后继逻辑关系就表现在数据元素的存储单元的物理前后位置上。元素的存储单元的物理前后位置上。 向量是内存中一批地址连续的存储单元。所以，线性向量是内存中一批地址连续的存储单元。所以，线性表的顺序存储也称为向量存储。表的顺序存储也称为向量存储。顺序表的存储结构如图所示顺序表的存储结构如图所示顺序存储结构的顺序存储结构的线性表称作顺序表线性表称作顺序表a0a1a2a3a4a5elemlength=6MaxSize-1 1 2 3 4 5 6 第第i个元素的地址：个元素的地址： LOC(ai)=LOC(a1)+L*(i-1)typedef struct ElemTyp

5、e elem MAXSIZE; int length; Sqlist;事先定义的事先定义的常量常量结构体类型名，之后可用结构体类型名，之后可用于说明结构体变量于说明结构体变量在结构体中还可以使用动态一维数组。如下定义：在结构体中还可以使用动态一维数组。如下定义：typedef struct ElemType *elem ; int length ; Sqlist1 ;使用指针表示使用指针表示数组域数组域表长域表长域SqlistSqlist a ; a ;a.Elema.Elem=(Sqlist1=(Sqlist1* *) )malloc(MAXSIZEmalloc(MAXSIZE* *size

6、of(ElemTypesizeof(ElemType););free (free (a.elema.elem) )#define MAXSIZE 1002.顺序表操作的实现（顺序表操作的实现（线性表在向量中基本运算的实现线性表在向量中基本运算的实现）#define MAXSIZE 100Typedef int ElemType ; typedef struct ElemType elem MAXSIZE; /*数组域数组域*/ int length; /*表长域表长域*/ Sqlist; /*结构体类型名结构体类型名*/int Insert (Sqlist *L, int i, ElemTyp

7、e x)int j;for(j = L-length; j i; j-) L-elemj = L-elemj-1; /*依次后移依次后移*/ L-elemi = x; /*插入插入x*/L-length +; /*元素个数加元素个数加1*/return 1;typedef struct ElemType elem MAXSIZE; int length; Sqlist; （2 2）删除数据元素删除数据元素ListDelete(LListDelete(L, i, x), i, x)（2 2）删除数据元素操作的算法实现删除数据元素操作的算法实现 int Delete ( Sqlist *L, in

8、t i) int j; for(j = i +1; j lengh-1; j+) L-elemj-1 = L - elemj; /*依次前移依次前移*/ L - lengh-;/*数据元素个数减数据元素个数减1*/ return 1; 3.顺序表操作的效率分析顺序表操作的效率分析时间效率分析时间效率分析:算法时间主要耗费在移动元素的操作上，因此计算时间复算法时间主要耗费在移动元素的操作上，因此计算时间复杂度的基本操作杂度的基本操作(最深层语句频度最深层语句频度) 而移动元素的个数取决于插入或删除元素的位置而移动元素的个数取决于插入或删除元素的位置i若若i =lengh，则根本无需移动（特别快）

9、；则根本无需移动（特别快）；若若i =0，则表中元素全部要后移（特别慢）；则表中元素全部要后移（特别慢）；应当考虑在各种位置插入（共应当考虑在各种位置插入（共n+1种可能）的平均移动次种可能）的平均移动次数才合理。数才合理。设设 Pi 是在第是在第 i 个存储位置插入一个数据元素的概个存储位置插入一个数据元素的概率，顺序表中的数据元素个数为率，顺序表中的数据元素个数为n, 当在顺序表的当在顺序表的任何位置上插入数据元素的概率相等时，有任何位置上插入数据元素的概率相等时，有Pi=1/(n+1),则则 同理可证同理可证: :顺序表删除一元素的时间效率为顺序表删除一元素的时间效率为: :T（n)=(

10、n-1)/2 顺序表中的其余操作都和数据元素个数顺序表中的其余操作都和数据元素个数n n无关，因此，无关，因此，在顺序表中插入和删除一个数据元素的时间复杂度为在顺序表中插入和删除一个数据元素的时间复杂度为O O( (n n), ), 其余操作的时间复杂度都为其余操作的时间复杂度都为O O(1)(1)插入插入效率：效率：删除删除效率：效率：4. 顺序表应用举例顺序表应用举例 例：编程实现如下任务例：编程实现如下任务: :建立一个线性表，首先依次建立一个线性表，首先依次输入数据元素输入数据元素1 1，2 2，3 3，1010，然后删除数据元素，然后删除数据元素5 5，最后依次显示当前线性表中的数据

11、元素。要求采用顺序最后依次显示当前线性表中的数据元素。要求采用顺序表实现，假设该顺序表的数据元素个数在最坏情况下不表实现，假设该顺序表的数据元素个数在最坏情况下不会超过会超过100100个。个。实现方法：实现方法：1 1、采用直接编写一个主函数实现。、采用直接编写一个主函数实现。2 2、利用已设计实现的抽象数据类型模块。（存放在头文、利用已设计实现的抽象数据类型模块。（存放在头文件名为件名为SqList.hSqList.h中，通过中，通过 # #include “include “SqList.hSqList.h” ” ）程序设计如下：程序设计如下：void main(void)Sqlist

12、myList;int i , x;Initiate(&myList);for(i = 0; i 10; i+) Insert(&myList, i, i+1);Delete(&myList, 4);for(i = 0; i Length(myList); i+) Get(myList, i, &x);程序运行结果：程序运行结果：1 2 3 4 6 7 8 9 10 elem 100 length=0#include #include Sqlist.h#define MAXSIZE 100typedef int ElemType;elem 0=1Elem1=2Elem4=5Elem9=10 le

13、ngth=10typedef struct ElemType elem MAXSIZE; int length; Sqlist;elem 0=1Elem1=2Elem4=6Elem8=10 length=9主要优点主要优点: 算法简单，空间单元利用率高；算法简单，空间单元利用率高；主要缺点主要缺点: 1. 插入和删除时需要移动较多的数据元素，所以在频插入和删除时需要移动较多的数据元素，所以在频繁时行插入、删除操作时效率较低。繁时行插入、删除操作时效率较低。 2.需要预先确定数据元素的最大个数。并预先占用一需要预先确定数据元素的最大个数。并预先占用一片地址连续的存储空间。片地址连续的存储空间。

14、3. 如果插入数据元素量超过预先分配的存储空间时，如果插入数据元素量超过预先分配的存储空间时，要临时扩大有很大困难。要临时扩大有很大困难。线性表顺序存储结构的主要优缺点线性表顺序存储结构的主要优缺点线性表的链表存储结构的特点：是构成链表的结点（即分线性表的链表存储结构的特点：是构成链表的结点（即分配给每一个数据元素的存储单元）可分为两个域（数据域配给每一个数据元素的存储单元）可分为两个域（数据域和指针域）。数据域保存数据元素本身的数据信息，指针和指针域）。数据域保存数据元素本身的数据信息，指针域保存其直接后继结点的地址（称为指针）。数据元素间域保存其直接后继结点的地址（称为指针）。数据元素间的

15、逻辑关系由每个结点的指针体现。所以，逻辑上相邻的的逻辑关系由每个结点的指针体现。所以，逻辑上相邻的数据元素在物理上不要求相邻。因此它不需要一片地址连数据元素在物理上不要求相邻。因此它不需要一片地址连续的存储空间，可以避免了顺序表所具有的缺点。续的存储空间，可以避免了顺序表所具有的缺点。指针域指针域nextnext或或指针域指针域nextnext或或存储数据元素信息（简单类型或结存储数据元素信息（简单类型或结构类型）的子域构类型）的子域存储直接后继结点的地址（即存储位置存储直接后继结点的地址（即存储位置) )的子域（的子域（存储地址的变量称为指针变量存储地址的变量称为指针变量）2.3.1 结点结

16、构与指针变量结点结构与指针变量结点的存储结构定义为结点的存储结构定义为：typedef int ElemType ;Typedef struct node ElemType data; /* 数据域数据域 */ struct node *next; /* 指针域指针域 */ Lnode1. 结点结构结点结构假设假设h, p, q为指针变量，可说明如下：为指针变量，可说明如下：Lnode *h, *p, *q; /* 4 bytes 未赋值未赋值 */h=NULL; /* set NULL to h */h=(Lnode*)malloc(sizeof(Lnode); /* point to a

17、new node */p=h; /* p 和和 h 中存放的是同一结点的首地址中存放的是同一结点的首地址 */p-data = 12; p-next =NULL;free(h) /* or free(p) ,release the nodes space to the system*/hp?h?q?12hp?hp?hNext: 4bytesData: Sizeof(ElemType)2. 指针变量及其基本操作指针变量及其基本操作p=q;qqpp=q-next;qqpp-next = q; pqpqp-next=q-next;ppqq指针变量的主要操作：指针变量的主要操作：语句语句 执行前执行前

18、 执行后执行后2.3.2 单链表及其结构单链表及其结构 n个结点链接在一起可以构成一个链表。由于其每个个结点链接在一起可以构成一个链表。由于其每个结点中只包含一个指针域，故称为单链表。结点中只包含一个指针域，故称为单链表。非空线性单链表非空线性单链表,包括一个头结点和包括一个头结点和n个数据元个数据元素的结点。头指针素的结点。头指针h指向链表的头结点或首元指向链表的头结点或首元结点。头指针结点。头指针h 可以作为链表的唯一已知条件。可以作为链表的唯一已知条件。对链表的各种操作一般须从头指针开始。对链表的各种操作一般须从头指针开始。h空链表空链表h-next =NULLh ha1a2an附加头结

19、点，简称头结点，附加头结点，简称头结点，h结点，数据域可放结点，数据域可放表长信息，它不计入表长度。表长信息，它不计入表长度。头指针头指针首元结点首元结点存储线性表第存储线性表第一个数据元素一个数据元素2.3.3 线性链表基本运算的实现线性链表基本运算的实现pa1a2anhdata nextxs(a) 插入前插入前1) 在带头结点单链表第一个数据元素前插入结点在带头结点单链表第一个数据元素前插入结点pa1a2anhdata nextxs(b) 插入后插入后第一步:s-next = p -next第二步:p -next = spa1a2anhdata nextxs第一步:s-next = p -

20、next第二步:p -next = spai-1a1aiandata nextxss-next = p-next(x.next =ai -1.next)p-next = s(ai -1.next = s)h* 分别在带头结点单链表的首元结点和其它结点前插入结点的操作比较分别在带头结点单链表的首元结点和其它结点前插入结点的操作比较2) 删除带头结点单链表第一个数据元素结点删除带头结点单链表第一个数据元素结点pa1a2anhdata next删除前删除前pa1a2anhdata next删除后删除后p-next = p-next-next(a1.next)* 删除带头结点单链表首元结点和其它结点操

21、作的比较删除带头结点单链表首元结点和其它结点操作的比较pa1a2anhdata next删除后删除后p-next = p-next-next(a1.next)pai-1a1aiandata nextai+1p-next = p-next -next( ai-1 .next = ai.next )h3) 在不带头结点单链表第一个数据元素前插入结点在不带头结点单链表第一个数据元素前插入结点a1a2anhxs(a) 插入前插入前a1a2anhxs(b) 插入后插入后第一步: s-next = h第二步: h = s4).在不带头结点单链表其他数据元素前插入结点在不带头结点单链表其他数据元素前插入结点

22、pai-1a1aianhdata nextxs插入前插入前pai-1a1aianhdata nextxss-next = p-next(x.next =ai -1.next)p-next = s(ai -1.next = s)插入后插入后* 在不带头结点单链表首元结点和其他结点前插入结点之比在不带头结点单链表首元结点和其他结点前插入结点之比较较pai-1a1aianhdata nextxss-next = p-next(x.next =ai -1.next)p-next = s(ai -1.next = s)a1a2anhxs第一步: s-next = h第二步: h = s5) 删除不带头结

23、点单链表第一个数据元素结点删除不带头结点单链表第一个数据元素结点6) 删除不带头结点单链表其他数据元素结点删除不带头结点单链表其他数据元素结点a1a2anhdata nexth=h-nextpai-1a1aianhdata nextai+1p-next = p-next -next( ai-1 .next = ai.next )（1）带头结点单链表无论在第一个数据元素结点前插入，带头结点单链表无论在第一个数据元素结点前插入，还是在其他结点前插入，操作方法一样；而不带头结点单还是在其他结点前插入，操作方法一样；而不带头结点单链表在第一个数据元素结点前插入，和在其他结点前插入，链表在第一个数据元素

24、结点前插入，和在其他结点前插入，操作方法不一样操作方法不一样（2）删除操作和插入操作类似）删除操作和插入操作类似（3）设计带头结点单链表的算法时，头指针参数可设计）设计带头结点单链表的算法时，头指针参数可设计成输入型参数；设计不带头结点单链表的算法时，头指针成输入型参数；设计不带头结点单链表的算法时，头指针参数必须设计成输出型参数参数必须设计成输出型参数（4）因此，带头结点单链表的算法设计简单因此，带头结点单链表的算法设计简单2.3.4 单链表的操作实现举例单链表的操作实现举例xhqsp q=h; while(q-next!=p) q=q-next; s=(Lnode*)malloc(size

25、of(Lnode) s-data = x; s-next =p; q-next = s;Typedef struct node ElemType data; struct node *next; Lnode1、在、在p 指向的结点前插入数据元素指向的结点前插入数据元素x2、在线性表中值为、在线性表中值为x的元素前插入值为的元素前插入值为y的数据元素的数据元素aiyanhqxa1spvoid Insert(Lnode *h, ElemType x, ElemType y) s=(Lnode*)malloc(sizeof(Lnode) s-data = y; q=h; p=q-next; whil

26、e(p!=NULL)&(p-data!=x) q=p; p=p-next; s-next =p; q-next = s;Typedef struct node ElemType data; struct node *next; Lnode3、删除、删除p所指向的结点所指向的结点bqpca q=h; while( q-next !=p ) q=q-next; q-next = p-next; free( p );4、删除线性表中值为、删除线性表中值为x的数据元素的数据元素void Delete( Lnode *h, ElemType x ) q=h; p=q-next; while(p!=NUL

27、L)&(p-data!=x) q=p; p=p-next; if ( p=NULL) printf(“NO!”); else q-next = p-next; free(p); printf(“YES!”); Typedef struct node ElemType data; struct node *next; Lnodeaixanhqai+1a1p5、删除线性链表中第、删除线性链表中第i个元素结点，并返回该数据元素的值。个元素结点，并返回该数据元素的值。ElemType Deletei ( Lnode *h, int i ) int k=0; p=h; while( p -next !=

28、NULL)&( k next; k+; if ( p-next !=NULL)& k=i-1) /* 第第i个元素结点存在个元素结点存在 */ q = p-next; y=q-data; p-next = q-next; free(q); else printf(“n i error!”); y = -1; return y;ai-1aianhpai+1a1qp2.3.5 单链表操作的效率分析单链表操作的效率分析单链表的插入和删除操作不需移动数据元素，只需比较数据单链表的插入和删除操作不需移动数据元素，只需比较数据元素。因此，当在单链表的任何位置上插入数据元素的概率元素。因此，当在单链表的任何

29、位置上插入数据元素的概率相等时，在单链表中插入一个数据元素时比较数据元素的平相等时，在单链表中插入一个数据元素时比较数据元素的平均次数为：均次数为：删除一个数据元素时比较数据元素的平均次数为：删除一个数据元素时比较数据元素的平均次数为：所以，单链表进行数据元素插入删除操作的时间复杂度为所以，单链表进行数据元素插入删除操作的时间复杂度为O(n)。2.4 2.4 循环链表与双向链表循环链表与双向链表 循环单链表是单链表的另一种形式的存储结构，其结构特点是链表中循环单链表是单链表的另一种形式的存储结构，其结构特点是链表中最后一个结点的指针域指向整个链表的第一个结点，从而使链表形成一个最后一个结点的指

30、针域指向整个链表的第一个结点，从而使链表形成一个环。它的优点是从表中任一结点出发均可找到表中其它结点。环。它的优点是从表中任一结点出发均可找到表中其它结点。程序设计：程序设计：p!=NULL改为改为 p!=headP-!=NULL改为改为 p-!=headhead(a) 空链表空链表reara0a1an-1head(b) 非空链表非空链表r尾指针尾指针2.4.1 循环链表循环链表a0a1an-1harab0b1bm-1hbrba0a1an-1harab0b1bm-1hbrb rb-next = ra-next; ra-next = hb-next； free(hb); ra = rb 让让b

31、b链表尾结点的指链表尾结点的指针域保存针域保存a a链表的头链表的头结点地址结点地址让让a a链表尾结点链表尾结点的指针域保存的指针域保存b b链表的首元结点链表的首元结点地址地址消毁消毁b b链表的链表的头结点头结点让让a a链表的尾指针指向链表的尾指针指向b b链表的尾结点链表的尾结点将两个循环链将两个循环链表首尾相接表首尾相接 双向链表是每个结点除后继指针域外还有一个前驱指双向链表是每个结点除后继指针域外还有一个前驱指针域，它是解决查找前驱结点问题的有效途径。针域，它是解决查找前驱结点问题的有效途径。prior data nexta1a2anhead 非空链表非空链表2.4.2 双向链表

32、双向链表headprior next空链表空链表p-next-prior=p; p-prior-next=pabcheadp1、在双向链表中插入一个结点：、在双向链表中插入一个结点： s-next=p; s-prior=p-prior; p-prior-next = s; p-prior = s;axbps2、从双向链表中删除一个结点：、从双向链表中删除一个结点： p-prior-next = p-next; p-next-prior = p-prior; free(p);pabc2.4.3 顺序存储结构与链表存储结构的综合分析与比较顺序存储结构与链表存储结构的综合分析与比较顺序存储结构的优点

33、：顺序存储结构的优点：1、内存的存储密度高；、内存的存储密度高；2、在结点等长时，可随机存取结点；、在结点等长时，可随机存取结点；缺点：缺点：1、插入、删除需要大量移动数据，效率较低；、插入、删除需要大量移动数据，效率较低；2、要求占用连续的存储空间，存储分配需预先进行，且不易扩大。、要求占用连续的存储空间，存储分配需预先进行，且不易扩大。链表存储结构的优点：链表存储结构的优点：1、克服了顺序存储结构的缺点和不足；、克服了顺序存储结构的缺点和不足；2、插入和删除操作效率高；、插入和删除操作效率高；缺点：缺点：1、查找数据元素时需要从头结点开始逐个查找，不能随机存取；、查找数据元素时需要从头结点开始逐个查找，不能随机存取；2、结点包含指针域，空间单元利用率不高；、结点包含指针域，空间单元利用率不高；3、链表操作的算法也较复杂。、链表操作的算法也较复杂。