攻克C语言链表.ppt

《攻克C语言链表.ppt》由会员分享，可在线阅读，更多相关《攻克C语言链表.ppt（51页珍藏版）》请在三一办公上搜索。

1、Data Structure Using C,信息管理学院尹晓yx_,Chapter 5Linked Lists,在本章中，我们将学到：认识链表的特性链表的三种类型单链表双链表循环链表稀疏矩阵利用链表对多项表达式进行加法计算,假设有一个单链表中存储了100000个数字，这些数字从第一个节点开始依次按升序排序。如果我们想以升序的方式显示这些数字，该怎么办呢？答案是：从第一个节点开始遍历列表。,假如我们又需要以降序的方式显示这些数字，如何解决此问题呢？单链表中每一个节点链接到序列中的下一个节点。这意味着我们只能以单向遍历列表。要以降序的方式显示数字，我们需要反转(reverse)这个链表。,链接列

2、表,1,100000,2,Header,3,.,反转单链表ptr1=Header-linkptr2=ptr1-linkptr3=ptr2-linkptr1-link=NULLwhile ptr3不为空ptr2-link=ptr1ptr1=ptr2ptr2=ptr3ptr3=ptr3-linkptr2-link=ptr1Header-link=ptr2,5,7,10,22,Header,10,10,15,反转结束,上述算法的存在什么问题？无论你什么时候访问下一节点，你都需要调整三个变量的所有链接。此方法的缺点：对长链表来说效率低且耗时。如何解决此问题？如果列表中每一个节点不仅包含序列中其下一个节

3、点的地址，而且还包含其前一节点的地址，那么此问题就可以解决。,链接列表,考虑下面的单链表。我们可以在单链表的每个节点中引入一个额外的字段，它存储前一个节点的地址。这种类型的链表就是双链表(doubly linked list)。,链接列表,Header,15,19,21,23,25,32,Header,15,19,21,23,25,32,Doubly linked lists are also called two-way list or two-way chain)。在双链表中，每个节点需要存储：数据下一个节点的地址前一个节点的地址定义双链表中节点的结构体类型struct nodeint d

4、ata;struct node*Llink;struct node*Rlink;,链接列表（续）,5.5 Doubly Linked List,A doubly linked list is a linear data structure in which each node can have any number of data fields and two link fields which are used to point to the previous node and the next node.(page 184),链接列表（续）,5.5.1 Definition,The ope

5、rations that can be performed on the doubly linked list are：a)insertionb)deletionc)searchd)copye)merge f)traverseThe only difference between a singly linked list and doubly linked list is that two pointer nodes have to be modified.(page 184),链接列表（续）,5.5.2 Opertations on a Doubly Linked List,25,10,15

6、,create a new node,the address is New.ptr=Header-Rlinkif New is not NULLNew-Llink=HeaderHeader-Rlink=NewNew-Rlink=ptrptr-Llink=NewNew-data=X,Header,在前端插入元素75,插入完成,75,a)Insertion operationi)at the frontii)at the endiii)at any postion,75,25,10,15,在双链表的末尾插入一个节点ptr=Header-Rlinkwhile ptr-Rlink is not NUL

7、L ptr=ptr-Rlinkcreate a new node,the address is Newif New is not NULLNew-Llink=ptrptr-Rlink=NewNew-Rlink=NULLNew-data=Xelse print“create fail”,Header,在末尾插入元素75,插入完成,a)Insertion operationi)at the frontii)at the endiii)at any postion,75,25,10,15,ptr=Header-Rlinkwhile ptr-data!=X and ptr is not NULL pt

8、r=ptr-Rlinkcreate a new node,the address is Newif ptr is NULLprint“cant find X”returnif ptr-data=Xptr1=ptr-RlinkNew-Llink=ptrNew-Rlink=ptr1ptr-Rlink=Newptr1-Llink=NewNew-data=X,Header,在元素10后插入元素75,插入完成,a)Insertion operationi)at the frontii)at the endiii)at any postion,25,10,ptr=Header-Rlinkif ptr is

9、 NULLprint“list empty”returnelseptr1=ptr-RlinkHeader-Rlink=ptr1ptr1-Llink=Headerfree(ptr),Header,在前端删除元素,删除完成,b)Deletion operation：i)at the frontii)at the endiii)at any postion,10,ptr=Header-Rlinkif ptr is NULLprint“list empty”returnwhile ptr-Rlink is not NULL ptr=ptr-Rlinkhere,ptr points to the las

10、t nodeptr1=ptr-Llinkptr1-Rlink=NULLfree(ptr),Header,在末尾删除元素,删除完成,b)Deletion operation：i)at the frontii)at the endiii)at any postion,ptr=Header-Rlinkif ptr is NULLprint“list empty”returnwhile ptr-data!=X and ptr is not NULL ptr=ptr-Rlinkif ptr is NULLprint“cant find X”returnif ptr-data=Xptr1=ptr-Llin

11、kptr2=ptr-Rlinkptr1-Rlink=ptr2ptr2-Llink=ptr1free(ptr),Header,删除元素10,删除完成,15,25,b)Deletion operation：i)at the frontii)at the endiii)at any postion,c)search operation in a doubly linked list,ptr=Header-Rlinkwhile ptr-data!=X and ptr is not NULLptr=ptr-Rlinkif ptr is NULLprint“cant find X”returnif ptr

12、-data=Xreturn ptr,return ptr,查找成功,查找元素10,15,25,Header,d)copy operation,ptr1=Header-Rlinkcreate a new node,the address is Header1ptr2=Header1ptr2-data=NULLptr2-Llink=NULLwhile ptr1 is not NULLcreate a new node，the address is NewNew-data=ptr1-dataptr2-Rlink=NewNew-Llink=ptr2ptr1=ptr1-Rlinkptr2=Newptr2

13、-Rlink=NULL,复制结束,15,25,10,Header,New,15,New,10,New,25,e)merge operation in a doubly linked list,ptr=Header1-Rlinkwhile ptr-Rlink is not NULLptr=ptr-Rlinkptr1=Header2-Rlinkptr1-Llink=ptrptr-Rlink=ptr1free(Header2),合并结束,15,25,10,Header1,27,35,18,f)traversing the doubly linked list,ptr=Header1-Rlinkwhi

14、le ptr is not NULLprint ptr-dataptr=ptr-Rlink,15,25,10,Header1,15,10,25,遍历结束,假定你正在开发一款动作游戏，其中会给每个游戏者一套武器。在屏幕上依次显示每种武器。一旦显示第n个武器后，就会再次显示第一次出现的武器，并且这种顺序会跟前面一样继续。你将使用哪种数据结构来存储武器的列表？,我们可以使用单链表。但是，武器需要以循环重复的次序显示。因此，一旦显示了所有武器，指针必须从列表中第一个武器重新开始。这需要在每次到达列表结尾时重新初始化指针。在此情况下，如果遍历最后一个武器对应的节点后指针能够自动移到列表中的第一个武器，那

15、将会更加简单。使用循环链表(circular linked list)可以实现这一点。,A circular linked list is a linked list where the last node points to the header node.(page 198)In circlular linked list,there are no NULL links.Circular linked lists can be either of the two types:singly linked circular listdoubly linked circular list,链接列

16、表（续）,5.6 Circular Linked List,15,9,11,23,5,12,15,9,11,23,5,12,5.6.2 singly linked circular list,5.6.3 doubly linked circular list,There is a disadvantage that if there is no care in processing the data elements in the nodes,an infinite loop can occur.(page 199),To avoid this problem,a special node c

17、alled a header node can be maintained without the data element.,The operations that can be performed on circular linked list are：a)insertionb)deletionc)traversingd)searchinge)mergingf)splittingg)copying,链接列表（续）,5.6.4 Opertations on a Circular Linked List,traversing the circular linked list,ptr=Heade

18、r-linkwhile ptr!=Headerprint ptr-dataptr=ptr-link,15,10,25,10,Header,15,10,25,遍历结束,insert a node in a circular linked list at the end,Create a new node,the address is Newptr=Header-linkwhile ptr-link!=Headerptr=ptr-linkif New is not NULLptr-link=NewNew-link=HeaderNew-data=X,15,10,25,10,Header,在末尾插入元

19、素75,75,插入完成,Sparse Matrices（稀疏矩阵）is a matrices contianing very few non-zero elements.(page 210)Representing large sparse matrices wastes huge amounts of memory spaces for storing zeros.There are two ways of representing sparse matrices:Array representationLinked-list representation,链接列表（续）,5.7 Spars

20、e Matrices,5.7.1 Array representation,Each non-zero element in the sparse matrix is represented the following form:(Row,Column,Value),0 1 2 3,0,1,2,3,4,5.7.2 Linked-List representation for Sparse Matrices,Each column is represented by a circularly linked list with a head node.Each row is also repres

21、ented by a circularly linked list with a head node.Each node in the structure other than a head node is a non-zero term of a matrix and is made up of 5 fields:(Row,Col,Down,Right,Value),链接列表（续）,link to the next non-zero elements in the same column,link to the next non-zero elements in the same row,-

22、8,6,7,-5,4,orthogonal list(十字链表),orthogonal list(十字链表),第0行,第1行,第2行,第3行,第4行,第0列,第1列,第2列,第3列,orthogonal list(十字链表),-8,6,7,-5,4,第0列,第1列,第2列,第3列,第0行,第1行,第2行,第3行,第4行,orthogonal list(十字链表),-8,6,7,-5,4,第0列,第1列,第2列,第3列,第0行,第1行,第2行,第3行,第4行,orthogonal list(十字链表),-8,6,7,-5,4,第0列,第1列,第2列,第3列,第0行,第1行,第2行,第3行,第4行

23、,Exercise：,0 1 0 0 0 0-30 0 8 05 0 0 0,Polynomial manipulation（计算多项式表达式）Dynamic storage management（动态存储管理）Garbage Collection（垃圾回收）Buddy Systems（伙伴系统）,链接列表（续）,5.8 Application,The general form of polynomial is:P(x)=anxn+an-1xn-1+a1x+a0在一个多项表达式中，每一项都伴有两个值：系数和指数因此，若要用链表来表示一个多项表达式，每个节点应该包括以下信息：系数（coeffic

24、ient）指数（exponent）链接到下一个节点的指针（the pointer to point the next node）,链接列表（续）,5.8.1 Polynomial manipulation,10,Coeff,Exp,coefficient,exponent,pointer to point the next node,Link,用单链表表示多项表达式:P(x)=3x8-7x6+14x3+12x 5注意：系数为 0的项不需要存储到节点中。下面我们考虑加法操作：加法（Addition of two polynomials）,链接列表（续）,i)Polynomial addition

25、,Polynomial 1:4x5+5x4+2x3+3x2+7x,Polynomial 2:9x6+6x4+3x2,To add two polynomial,say P and Q.There are may be 3 cases:case 1:P.exp=Q.expThe coefficients of two nodes have to be added R.coeff=P.coeff+Q.coeff R.exp=P.expcase 2:P.exp Q.expCopy the coefficient term of P to the coefficient term of R.R.coe

26、ff=P.CoeffR.exp=P.expCase 3:P.exp Q.expCopy the coefficient term of Q to the coefficient term of R.R.coeff=Q.CoeffR.exp=Q.exp,10,a,n1,Link,10,b,n2,Link,P=axn1,Q=bxn2,Polynomial 1:4x5+5x4+2x3+3x2+7x,Polynomial 2:9x6+6x4+3x2,读取 Polynomial 1 的第一个节点和 Polynomial 2 的第一个节点。比较两个节点的指数值。从Polynomial 2 读取的节点的指数

27、值较大(6 5)。将指数值为6的节点添加到 Polynomial 3 的列表。,10,9,6,Polynomial 3:9x6,Polynomial 1:4x5+5x4+2x3+3x2+7x,Polynomial 2:9x6+6x4+3x2,从Polynomial 2读取下一个节点。比较Polynomial 1的当前节点的指数和Polynomial 2的指数值。从Polynomial 1读取的节点的指数值较大(5 4)。因此，将指数值为5的节点添加到 Polynomial 3 的列表。,10,4,5,Polynomial 3:9x6+4x5,10,9,6,Polynomial 3:9x6,从P

28、olynomial 1读取下一个节点。比较 Polynomial 1 和 Polynomial 2 的当前节点的指数值。这两个指数值相等，都是4。相加两个节点的系数。结果节点具有的系数值是 11(6+5)。将结果节点添加到Polynomial 3的列表。,10,11,4,Polynomial 1:4x5+5x4+2x3+3x2+7x,Polynomial 2:9x6+6x4+3x2,10,4,5,Polynomial 3:9x6+4x5+11x4,10,9,6,Polynomial 3:9x6+4x5,从两个列表读取下一个节点。比较Polynomial 1和Polynomial 2 的当前节点

29、的指数值。从Polynomial 1 读取的节点指数值较大(3 2)。将指数值为3的节点添加到Polynomial 3的列表。,Polynomial 1:4x5+5x4+2x3+3x2+7x,Polynomial 2:9x6+6x4+3x2,10,11,4,10,4,5,Polynomial 3:9x6+4x5+11x4+2x3,10,9,6,10,2,3,Polynomial 3:9x6+4x5+11x4,从Polynomial 1读取下一个节点。比较 Polynomial 1 和Polynomial 2 的当前节点的指数值。两个指数值相等，都是2。将两个节点的系数相加。结果节点现在的系数值

30、为6(3+3)。将结果节点添加到Polynomial 3的列表。,10,6,2,Polynomial 1:4x5+5x4+2x3+3x2+7x,Polynomial 2:9x6+6x4+3x2,10,11,4,10,4,5,Polynomial 3:9x6+4x5+11x4+2x3+6x2,10,9,6,10,2,3,Polynomial 3:9x6+4x5+11x4+2x3,Polynomial 1:4x5+5x4+2x3+3x2+7x,Polynomial 2:9x6+6x4+3x2,现在，Polynomial 2中没有节点了。将第一个列表Polynomial 1剩下的节点添加到结果列表。

31、,10,7,1,10,6,2,10,11,4,10,4,5,Polynomial 3:9x6+4x5+11x4+2x3+6x2+7x,10,9,6,10,2,3,Polynomial 3:9x6+4x5+11x4+2x3+6x2,Pptr=PHeader-link Qptr=QHeader-linkcreate a new node RheaderRheader-coeff=NULL Rheader-exp=NULL Rheader-link=NULLRptr=Rheaderwhile(Pptr is not NULL)and(Qptr is not NULL)if Pptr-exp=Qptr

32、-exp.else if Pptr-expQptr-exp.else.,1)assume that the two polynomials P and Q have already been created.2)PHeader is the header of polynomial P3)Qheader is the header of polynomial Q,create a new node NewRptr-link=NewRptr=NewRptr-coeff=Pptr-coeff+Qptr-coeffRptr-exp=Pptr-expRptr-link=NULLPptr=Pptr-li

33、nkQptr=Qptr.link,create a new node NewRptr-link=NewRptr=NewRptr-coeff=Pptr-coeffRptr-exp=Pptr-expRptr-link=NULLPptr=Pptr-link,create a new node NewRptr-link=NewRptr=NewRptr-coeff=Qptr-coeffRptr-exp=Qptr-expRptr-link=NULLQptr=Qptr-link,6.while Pptr is not NULLcreate a new node NewRptr-link=newRptr=ne

34、wRptr-coeff=Pptr-coeffRptr-exp=Pptr-expRptr-link=NULLPptr=Pptr-link7.while Qptr is not NULLcreate a new node NewRptr-link=newRptr=newRptr-coeff=Qptr-coeffRptr-exp=Qptr-expRptr-link=NULLQptr=Qptr-link,continue,课后习题,write a program to convert a singly linked list into a circularly linked list,and then,count the nodes of the circularly linked list.,Example:,15,10,25,10,Header,20,The length of the circular linked list is:4,page 273(10 and 11),本章要掌握的内容,1.链表的特性。2.单链表的基本操作。3.双链表的基本操作。4.循环链表的基本操作。5.什么是稀疏矩阵？稀疏矩阵的两种压缩存储方法？三元组表示法十字链表表示法6.多项表达式加法操作的算法。,