《攻克C语言链表》PPT课件.ppt

Data Structure Using C,信息管理学院 尹晓 yx_018126.com,Chapter 5 Linked Lists,在本章中，我们将学到： 认识链表的特性 链表的三种类型 单链表 双链表 循环链表 稀疏矩阵 利用链表对多项表达式进行加法计算,假设有一个单链表中存储了100000个数字，这些数字从第一个节点开始依次按升序排序。 如果我们想以升序的方式显示这些数字，该怎么办呢？ 答案是：从第一个节点开始遍历列表。,假如我们又需要以降序的方式显示这些数字，如何解决此问题呢？ 单链表中每一个节点链接到序列中的下一个节点。这意味着我们只能以单向遍历列表。 要以降序的方式显示数字，我们需要反转(reverse)这个链表。,链接列表,1,100000,2,Header,3,.,反转单链表 ptr1=Header-link ptr2=ptr1-link ptr3=ptr2-link ptr1-link=NULL while ptr3不为空 ptr2-link=ptr1 ptr1=ptr2 ptr2=ptr3 ptr3=ptr3-link ptr2-link=ptr1 Header-link=ptr2,5,7,10,22,Header,10,10,15,反转结束,上述算法的存在什么问题？ 无论你什么时候访问下一节点，你都需要调整三个变量的所有链接。 此方法的缺点：对长链表来说效率低且耗时。 如何解决此问题？ 如果列表中每一个节点不仅包含序列中其下一个节点的地址，而且还包含其前一节点的地址，那么此问题就可以解决。,链接列表,考虑下面的单链表。 我们可以在单链表的每个节点中引入一个额外的字段，它存储前一个节点的地址。这种类型的链表就是双链表 (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 node int data; 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 operations that can be performed on the doubly linked list are： a) insertion b) deletion c) search d) copy e) merge f) traverse The 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,create a new node, the address is New. ptr=Header-Rlink if New is not NULL New-Llink=Header Header-Rlink=New New-Rlink=ptr ptr-Llink=New New-data=X,Header,在前端插入元素75,插入完成,75,a) Insertion operation i) at the front ii) at the end iii) at any postion,75,25,10,15,在双链表的末尾插入一个节点 ptr=Header-Rlink while ptr-Rlink is not NULL ptr=ptr-Rlink create a new node, the address is New if New is not NULL New-Llink=ptr ptr-Rlink=New New-Rlink=NULL New-data=X else print “create fail”,Header,在末尾插入元素75,插入完成,a) Insertion operation i) at the front ii) at the end iii) at any postion,75,25,10,15,ptr=Header-Rlink while ptr-data !=X and ptr is not NULL ptr=ptr-Rlink create a new node, the address is New if ptr is NULL print “cant find X” return if ptr-data = X ptr1=ptr-Rlink New-Llink=ptr New-Rlink=ptr1 ptr-Rlink=New ptr1-Llink=New New-data=X,Header,在元素10后插入元素75,插入完成,a) Insertion operation i) at the front ii) at the end iii) at any postion,25,10,ptr=Header-Rlink if ptr is NULL print “list empty” return else ptr1=ptr-Rlink Header-Rlink=ptr1 ptr1-Llink=Header free(ptr),Header,在前端删除元素,删除完成,b) Deletion operation： i) at the front ii) at the end iii) at any postion,10,ptr=Header-Rlink if ptr is NULL print “list empty” return while ptr-Rlink is not NULL ptr=ptr-Rlink here, ptr points to the last node ptr1=ptr-Llink ptr1-Rlink=NULL free(ptr),Header,在末尾删除元素,删除完成,b) Deletion operation： i) at the front ii) at the end iii) at any postion,ptr=Header-Rlink if ptr is NULL print “list empty” return while ptr-data!=X and ptr is not NULL ptr=ptr-Rlink if ptr is NULL print“cant find X” return if ptr-data=X ptr1=ptr-Llink ptr2=ptr-Rlink ptr1-Rlink=ptr2 ptr2-Llink=ptr1 free(ptr),Header,删除元素10,删除完成,15,25,b) Deletion operation： i) at the front ii) at the end iii) at any postion,c) search operation in a doubly linked list,ptr=Header-Rlink while ptr-data!=X and ptr is not NULL ptr=ptr-Rlink if ptr is NULL print “cant find X” return if ptr-data=X return ptr,return ptr,查找成功,查找元素10,15,25,Header,d) copy operation,ptr1=Header-Rlink create a new node, the address is Header1 ptr2=Header1 ptr2-data=NULL ptr2-Llink=NULL while ptr1 is not NULL create a new node，the address is New New-data=ptr1-data ptr2-Rlink=New New-Llink=ptr2 ptr1=ptr1-Rlink ptr2=New ptr2-Rlink=NULL,复制结束,15,25,10,Header,New,15,New,10,New,25,e) merge operation in a doubly linked list,ptr=Header1-Rlink while ptr-Rlink is not NULL ptr=ptr-Rlink ptr1=Header2-Rlink ptr1-Llink=ptr ptr-Rlink=ptr1 free(Header2),合并结束,15,25,10,Header1,27,35,18,f) traversing the doubly linked list,ptr=Header1-Rlink while ptr is not NULL print ptr-data ptr=ptr-Rlink,15,25,10,Header1,15,10,25,遍历结束,假定你正在开发一款动作游戏，其中会给每个游戏者一套武器。 在屏幕上依次显示每种武器。一旦显示第n个武器后，就会再次显示第一次出现的武器，并且这种顺序会跟前面一样继续。 你将使用哪种数据结构来存储武器的列表？,我们可以使用单链表。 但是，武器需要以循环重复的次序显示。 因此，一旦显示了所有武器，指针必须从列表中第一个武器重新开始。 这需要在每次到达列表结尾时重新初始化指针。 在此情况下，如果遍历最后一个武器对应的节点后指针能够自动移到列表中的第一个武器，那将会更加简单。 使用循环链表(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 list doubly linked circular list,链接列表（续）,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 called a header node can be maintained without the data element.,The operations that can be performed on circular linked list are： a) insertion b) deletion c) traversing d) searching e) merging f) splitting g) copying,链接列表（续）,5.6.4 Opertations on a Circular Linked List,traversing the circular linked list,ptr=Header-link while ptr != Header print ptr-data ptr=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 New ptr=Header-link while ptr-link!=Header ptr=ptr-link if New is not NULL ptr-link=New New-link=Header New-data=X,15,10,25,10,Header,在末尾插入元素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 representation Linked-list representation,链接列表（续）,5.7 Sparse 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 represented 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,-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行,Exercise：,0 1 0 0 0 0 -3 0 0 8 0 5 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 在一个多项表达式中，每一项都伴有两个值：系数和指数 因此，若要用链表来表示一个多项表达式，每个节点应该包括以下信息： 系数（coefficient） 指数（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,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.exp The coefficients of two nodes have to be added R.coeff = P.coeff + Q.coeff R.exp = P.exp case 2: P.exp Q.exp Copy the coefficient term of P to the coefficient term of R. R.coeff = P.Coeff R.exp = P.exp Case 3: P.exp Q.exp Copy the coefficient term of Q to the coefficient term of R. R.coeff = Q. Coeff R.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 读取的节点的指数值较大(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,从Polynomial 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 的当前节点的指数值。 从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。 将两个节点的系数相加。结果节点现在的系数值为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剩下的节点添加到结果列表 。,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-link create a new node Rheader Rheader-coeff=NULL Rheader-exp=NULL Rheader-link=NULL Rptr=Rheader while (Pptr is not NULL) and (Qptr is not NULL) if Pptr-exp=Qptr-exp . else if Pptr-expQptr-exp . else .,1) assume that the two polynomials P and Q have already been crea