七 链表(ying)

1、2021-7-1 1页 2.3 2.3 linked listslinked lists The drawback of the static date structure 1.1.Once memory space is allocated for the array, it cannot be extended. 2.If some data item has to be inserted or if some data has to be removed from the array in the middle,bconsiderable amount of date of data m

2、ovement occurs. this data movement consumes computer time and decreases program efficiency. To overcome this problem of static data structure,，a linked list data structure is used. 2021-7-1 2页 Linked-listsLinked-lists nIn the linked-list data structure, the elements need not be stored in consecutive

3、 memory locations. nThe memory space allocated for the elements of the list can be extended at any time. nEach element will have two types of fields, namely, data fields and pointer fields. data fields have the actual data, the pointer fields has the address of the next element. 2021-7-1 3页 Definiti

4、on A linked list is an order collection of finite homogeneous data elements called nodes where the linear order is maintained by means of links or pointers. The number of pointers are maintained depending on the requirements and usage.based on this ,linked lists are classified into three categories:

5、 nSingly linked list nDoubly linked list nCircularly linked list 2021-7-1 4页 Singly linked list H a4 120 a5 NULL a1 240 a3 110 a2 210 110 120 130 160 200 210 240 160 a1a2an H1 data next Node structure data fields pointer fields H2 2021-7-1 5页 链式存储结构特点链式存储结构特点： 1.1.使用任意的存储单元存储线性表，不需要空间连续；使用任意的存储单元存储线

6、性表，不需要空间连续； 2.2.通过前一个结点得到后一个结点的地址，使它们前后之间建通过前一个结点得到后一个结点的地址，使它们前后之间建 立一一对应的关系（即：前趋和后继的关系）。立一一对应的关系（即：前趋和后继的关系）。 结点定义如下：结点定义如下： typedef struct node ElemType data; /* data fields */ struct node *next; /* pointer fields*/ LNode，*LinkList； data next 【说明】【说明】 ELEMTP为通用数据类型；为通用数据类型； next next 为指向结构体类型的指针，

7、为指向结构体类型的指针， 指示下一结点（后继，除最后一个指示下一结点（后继，除最后一个 元素）所在的位置。元素）所在的位置。 2021-7-1 6页 头指针头指针(head)变量定义方法如下：变量定义方法如下： LinkList H; LNode *p； p=(LinkList)malloc(sizeof(LNode)； 声明后，系统会分配足够的空间来容纳声明后，系统会分配足够的空间来容纳Linklist结构，同时指结构，同时指 针针p p指向新的内存位置。指向新的内存位置。 p p p所指的结点为所指的结点为* *p p，* *p p的类型为的类型为LNodeLNode型，型， data f

8、ields :( (* *p).datap).data或或p-datap-data， pointer fields :( (* *p).next p).next 或或 p-nextp-next。 free(p) free(p) 则表示释放指针则表示释放指针p p所指向的结点空间。所指向的结点空间。 2021-7-1 7页 2.3.2 basic operations 1. Creating a linked list Insert a node at the front of the linked list. （16，20，65，12） 1265 H H 12 H 201265 H 16201

9、265 H 2021-7-1 8页 【2.62.6】InsertFirst LinkList Creat_LinkList1( ) LinkList H=(LinkList)malloc(sizeof(LNode); /* 生成头结点生成头结点 */ H -next=NULL； /* 空表空表 */ LNode *s; int x; /* 设数据元素的类型为设数据元素的类型为int */ scanf(%d, while (x!=-1) s=(LinkList)malloc(sizeof(LNode); s-data=x; s-next=H-next; H-next=s; scanf (%d,

10、return H ; 2021-7-1 9页 (2)(2)Inserts a node after the last node of the linked Inserts a node after the last node of the linked list list （16，20，65，12） H r H r 16 H r16 20 H r162065 rH 16206512 2021-7-1 10页 【2.72.7】InsertLastInsertLast LinkList Creat_LinkList2( ) LinkList H=(LinkList)malloc(sizeof(LN

11、ode); H -next=NULL； /* 空表空表 */ LNode *s,*r=H ; int x; /* 设数据元素的类型为设数据元素的类型为int */ scanf(%d, while (x!=-1) s= (LinkList)malloc(sizeof(LNode); s-data=x; s -next =r-next ; r-next=s; r=s; /*r 指向新的尾结点指向新的尾结点 */ scanf(%d, return H ; 2021-7-1 11页 The length of listThe length of list 算法思路：设一个指针和计数器，初始化使指向头结

12、点算法思路：设一个指针和计数器，初始化使指向头结点 H，=0。若所指结点还有后继结点，向后移动，计数。若所指结点还有后继结点，向后移动，计数 器加器加 1，重复上述过程，直到，重复上述过程，直到p-next=NULL为止。为止。 【算法【算法2.8】设】设H是带头结点的单链表，求带头结点单链表的表是带头结点的单链表，求带头结点单链表的表 长。长。 Status Length_LinkList (LinkList H) LNode * p= H ; int j=0; while(p-next) p=p-next; j+； return j; H 16206512 2021-7-1 12页 按序号

13、查找第按序号查找第 k 个数据元素个数据元素 LinkList Get_LinkList(LinkList H,int k); LNode *p=H; int j=0; while (p-next!=NULL j+; if (j=k) return p ; else return NULL; 60765590 85 p H 例如：例如： i =3: 当当p指向指向85时，时， j=1； p指向指向60时，时， j=2； p指向指向76时，时， j=3； 退出循环。退出循环。 例如：例如： k =6 。 当当p指向指向85时，时， j=1； 当当p指向指向90时，时， j=5； 再执行再执行p=

14、p-next时，时， p= NULL，退出循环。退出循环。 【时间复杂度均为【时间复杂度均为O(n) 2021-7-1 13页 链表中查找链表中查找 x 的算法实现的算法实现 LNode * Locate_LinkList( LinkList H, ElemType x) LNode * p=H-next; while(p!=NULL return p; 60765590 85 pL 例如：查找例如：查找76，p 指向指向76结点时，结点时， 退出退出while循环，循环， 返回返回p指向的结点。指向的结点。 【时间复杂度均为【时间复杂度均为O(n) 2021-7-1 14页 4 4Inser

15、tion of a nodeInsertion of a node 设设p指向单链表中某结点，指向单链表中某结点，s指向待插入的新结点，将指向待插入的新结点，将*s插入插入 到到*p的后面。的后面。 p xs x s p q s-next=p-next; p-next=s; 将新结点将新结点*s 插入到插入到*p 的前面，在插入操作前首先要找到的前面，在插入操作前首先要找到 *p 的前驱的前驱*q，然后再将然后再将*s 插入到插入到*q 之后。之后。 q=H; while (q-next!=p) q=q-next; s-next=q-next; q-next=s; 2021-7-1 15页 【

16、算法【算法2.11】将新结点】将新结点s插入到第插入到第i个结点的位置上，即插入到个结点的位置上，即插入到ai-1与与 ai 之间。之间。 算法思路：算法思路： (1) 查找第查找第 i-1个结点；若存在继续个结点；若存在继续(2)，否则结束；，否则结束； (2) 创建新结点；创建新结点； (3) 将新结点插入，结束。将新结点插入，结束。 Hai-1 x ai p s 2021-7-1 16页 int Insert_LinkList( LinkList H, int i, ElemType x) /* 在单链表在单链表H的第的第i个位置上插入值为个位置上插入值为x的元素的元素 */ LNode

17、 * p,*s; p=Get_LinkList(H,i-1); if (p=NULL) printf(插入位置插入位置i错错);return ERROR; else s=(LinkList)malloc(sizeof(LNode); s-data=x; s-next=p-next; p-next=s； return OK; /* Insert_LinkList */ 时间复杂度为时间复杂度为O(n) 2021-7-1 17页 5. 5. Deleting a nodeDeleting a node 【算法算法2.12】删除链表中第】删除链表中第 i 个结点。个结点。 算法思路：算法思路： (1

18、) 查找第查找第 i-1 个结点；若存在，则继续个结点；若存在，则继续(2)，否则结束；，否则结束； (2) 若存在第若存在第 i 个结点则继续个结点则继续(3)，否则结束；，否则结束； (3) 删除第删除第 i 个结点，结束。个结点，结束。 q-next=p-next; free(p); x p q Hai-1ai+1 p q ai 释放到 存储池 2021-7-1 18页 int Del_LinkList(LinkList H，int i) /* 删除删除 单链表单链表H上的第上的第i个数据结点个数据结点 */ LinkList p, q; p=Get_LinkList(H,i-1); i

19、f (p=NULL) printf(第第i-1个结点不存在个结点不存在) ;return ERROR ; else if(p-next=NULL) printf(第第i个结点不存在个结点不存在);return ERROR; else q=p-next; /* q指向第指向第i个结点个结点 */ p-next=q-next; free(q); return OK; /* Del_LinkList */ 时间复杂度为时间复杂度为O(n) 2021-7-1 19页 从上面的讨论可以看出从上面的讨论可以看出： (1)(1) 在单链表上插入、删除一个结点，必须知道其前驱结点。在单链表上插入、删除一个结点

20、，必须知道其前驱结点。 (2)(2) 单链表不具有按序号随机访问的特点，只能从头指针开单链表不具有按序号随机访问的特点，只能从头指针开 始依次进行访问。始依次进行访问。 (3)(3)链表上实现的插入和删除运算，不用移动结点，仅需修链表上实现的插入和删除运算，不用移动结点，仅需修 改指针。改指针。 考虑的几个问题：考虑的几个问题： (1)(1)如果在链表中第如果在链表中第i i个结点个结点后后插入一个值为插入一个值为y y的结点，如果的结点，如果i i不不 存在，则把结点插在表尾。如何实现？存在，则把结点插在表尾。如何实现？ (2)(2)如果在不带头结点的链表中第如果在不带头结点的链表中第i i

21、 （i=1i=1）个结点前插入一个结点前插入一 个值为个值为y y的结点（在链表中值为的结点（在链表中值为x x的结点前插入一个值为的结点前插入一个值为y y的结的结 点）点） ，如何实现？，如何实现？ 2021-7-1 20页 (2)删除所有值为x的结点，并返回1值为x的结点个数。 int Delete_Linkst2 (LNode *H, Elemtype x ) LNode *p, *q; q =H ; count=0; while( q -next ) p=q-next ; if(p -data = =x) q-next=p-next ; /*逐个判断结点值，为逐个判断结点值，为x则删

22、除则删除*/ free(p); +count; /* count +1*/ else q=p; /* while */ return count; /* Delete_Linkst2 */ 80768090 85 H pq 例如例如x =80的情况。的情况。 时间复杂度为时间复杂度为O(n). 考虑不带表头结点的情况，删考虑不带表头结点的情况，删 除算法相对考虑的因素要多些。除算法相对考虑的因素要多些。 2021-7-1 21页 2.3.3 Circularly linked listCircularly linked list a1a2anH a2a1a2anH a1a2anH *(rear

23、-next) 2021-7-1 22页 定义：循环链表是另一种形式的链表存储结构，实现方法是将 表中最后一个结点的指针域指向单链表的表头结点，这样就形 成了一个环。这种结构便于查找结点。 循环条件： 1. 单链表的循环条件是 p 或 p-next 是否为空。 2. P 或 p-next 是否等于头结点 通常在循环链表中只设尾结点而不设头结点，这样尾结 点就起到了既指头又指尾的功能。 a1a2anH 非空单向链表非空单向链表 H 空链表空链表 2021-7-1 23页 例如对两个单循环链表例如对两个单循环链表HA、HB的连接操作，：的连接操作，： p=RAnext; RA-next=RB-nex

24、t-next; free(RB-next); RB-next=p; 时间复杂度为时间复杂度为O(1) RB b1 bn a1 an RA p 存储池 2021-7-1 24页 2.3.4 Doubly linked listDoubly linked list In the case of a singly linked list, it is possible to traverse in only one direction, i.e., from the left to the right. In some applications it is desirable to traverse

25、 the linked lists in both directions, that is from the left to the right or from the right to the left. 双向循环链表 a2a1a2an H a2a1a2an H 2021-7-1 25页 Doubly linked listDoubly linked list Definition A doubly linked list is a linear data structure in which each node can have any number of data fields and

26、two link fields which are used to point to the previous node and the next node. 2021-7-1 26页 prior data next 结点结构 特点: (1)可从两个方向搜索某个结点。可从两个方向搜索某个结点。 (2)无论利用向前这一链还是向后这一链，都可以遍历这无论利用向前这一链还是向后这一链，都可以遍历这 个链表。特别是如果一根链失效了，还可以利用另一根个链表。特别是如果一根链失效了，还可以利用另一根 链修复整个链表链修复整个链表 。 双向链表结点的定义如下：双向链表结点的定义如下： typedef str

27、uct dlnode ElemType data; struct dlnode *prior, *next; DLNode, *DLinkList; H a2a1 an H 空表 2021-7-1 27页 当当p p指向双向循环链表中的某一结点时，则有以下等式：指向双向循环链表中的某一结点时，则有以下等式： p-prior-next=p； p=p-next-prior； 1 1双向链表中结点的插入操作双向链表中结点的插入操作 设设p p指向双向链表中某结点，指向双向链表中某结点，s s指指 向待插入的新结点，将向待插入的新结点，将 * *s s插入插入 到到 * *p p的前面，插入过程如图的

28、前面，插入过程如图2-2- 1717所示，尤其要注意操作顺序，所示，尤其要注意操作顺序， 操作过程如下：操作过程如下： s-prior=p- prior; p-prior-next=s; s-next=p; p-prior=s; p x s a2a1a2 p a2 2021-7-1 28页 2 2双向链表中结点的删除操作双向链表中结点的删除操作 设设p p指向双向链表中待删除的结点。指向双向链表中待删除的结点。 p-prior-next=p-next; p-next-prior=p-prior; free(p); p 2.3.5 静态链表静态链表 静态链表用数组实现静态链表用数组实现，每个数，

29、每个数 据元素除了存储数据信息外，据元素除了存储数据信息外， 还要存储逻辑相邻的下一个数还要存储逻辑相邻的下一个数 据元素在数组中的位置，可见，据元素在数组中的位置，可见， 静态链表虽然是用数组实现的，静态链表虽然是用数组实现的， 但是逻辑相邻的数据元素不一但是逻辑相邻的数据元素不一 定在物理位置上也相邻。定在物理位置上也相邻。 a1 a2 a3 a4 a5 4 5 3 1 2 4 0 1 2 3 4 5 6 data next SL=0 2021-7-1 29页 typedef struct ElemType data ; int next ; SNode ; /* 结点类型结点类型 */

30、SNode sdMAXSIZE; int SL; /* 头指针变量头指针变量 */ a1 a2 a3 a4 a5 4 5 3 1 2 4 0 1 2 3 4 5 6 data next SL=0 2.3.6 顺序表和链表的比较顺序表和链表的比较 顺序存储有三个顺序存储有三个优点优点： (1) 方法简单，各种高级语言中都有数组，容易实现。方法简单，各种高级语言中都有数组，容易实现。 (2) 不用为表示结点间的逻辑关系而增加额外的存储开销。不用为表示结点间的逻辑关系而增加额外的存储开销。 (3) 顺序表具有按元素序号随机访问的特点。顺序表具有按元素序号随机访问的特点。 但它也有两个但它也有两个缺点

31、缺点： (1) 插入、删除操作时，平均移动大约表中一半元素，效率低。插入、删除操作时，平均移动大约表中一半元素，效率低。 (2) 需要预先分配足够大的存储空间。需要预先分配足够大的存储空间。 2021-7-1 30页 在实际中怎样选取存储结构的几点考虑：在实际中怎样选取存储结构的几点考虑： (2) (2) 基于运算的考虑基于运算的考虑 如果对线性表的主要操作是查找，适宜采用顺序表结构。对如果对线性表的主要操作是查找，适宜采用顺序表结构。对 于频繁进行插入和删除操作的线性表，适宜采用链表结构。于频繁进行插入和删除操作的线性表，适宜采用链表结构。 (3)(3)基于环境的考虑基于环境的考虑 顺序表的

32、实现基于数组类型，链表的操作是基于指针。顺序表的实现基于数组类型，链表的操作是基于指针。 (1) (1) 基于存储的考虑基于存储的考虑 顺序表的存储空间是静态分配的，在程序执行之前必须明确顺序表的存储空间是静态分配的，在程序执行之前必须明确 规定规定“MAXSIZEMAXSIZE”大小，估计过大，造成浪费，过小造成溢出。大小，估计过大，造成浪费，过小造成溢出。 链表不用事先估计存储规模，但链表的存储密度较低。链表不用事先估计存储规模，但链表的存储密度较低。 存储密度存储密度是指一个结点中数据元素所占的存储单元数和整个是指一个结点中数据元素所占的存储单元数和整个 结点所占的存储单元之比。显然顺序

33、表的存储密度为结点所占的存储单元之比。显然顺序表的存储密度为1 1，链式，链式 存储结构的存储密度小于。存储结构的存储密度小于。 2021-7-1 31页 2.4 2.4 线性表的典型应用线性表的典型应用 在数学上，一个多项式可写成下列形式：在数学上，一个多项式可写成下列形式： P(x)=anxn+an-1xn-1+.+a1x1+a0 ，其中其中a ai i为为x xi i的非零的非零 系数系数。 可采用单链表来表示。多项式中的可采用单链表来表示。多项式中的 每一项为单链表中的一个结点，每每一项为单链表中的一个结点，每 个结点包含三个域：系数域、指数个结点包含三个域：系数域、指数 域和指针域。域和指针域。 现有多项式：现有多项式： (x) =5 x9+8 x7+3 x 2 可表示为：可表示为： pa 237895 expcoefnext 系数域系数域 指数域指数域 指针域指针域 2021-7-1 32页 现在设有两个多项式：做相加运算：现在设有两个多项式：做相加运算： A(x)=5 x9+8 x7+3 x 2 B(x)=6x12+10 x9-3 x 2-12 pb 0-12 2-3 910126 pa 23 7895 运算前运算前 p