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

Data Structure Using CData Structure Using C信息管理学院信息管理学院尹晓尹晓yx_018@yx_018@Chapter 5Linked Lists•在本章中，我们将学到：–认识链表的特性–链表的三种类型•单链表•双链表•循环链表–稀疏矩阵–利用链表对多项表达式进行加法计算假设有一个单链表中存储了100000个数字，这些数字从第一个节点开始依次按升序排序如果我们想以升序的方式显示这些数字，该怎么办呢？答案是：从第一个节点开始遍历列表11000002Header3...假如我们又需要以降序的方式显示这些数字，如何解决此问题呢？单链表中每一个节点链接到序列中的下一个节点这意味着我们只能以单向遍历列表要以降序的方式显示数字，我们需要反反转(reverse)这个链表链接列表链接列表11000002Header3...11000002Header3...反转单链表反转单链表1.ptr1=Header->link2.ptr2=ptr1->link3.ptr3=ptr2->link4.ptr1->link=NULL5.while ptr3不为空a.ptr2->link=ptr1b.ptr1=ptr2c.ptr2=ptr3d.ptr3=ptr3->link6.ptr2->link=ptr17.Header->link=ptr25710 22Headerptr2ptr110ptr31015ptr1ptr2 ptr3ptr1ptr2ptr3ptr1ptr2ptr3NULL反转结束上述算法的存在什么问题？无论你什么时候访问下一节点，你都需要调整三个变量的所有链接。

此方法的缺点：对长链表来说效率低且耗时如何解决此问题？如果列表中每一个节点不仅包含序列中其下一个节点的地址，而且还包含其前一节点的地址，那么此问题就可以解决链接列表链接列表考虑下面的单链表我们可以在单链表的每个节点中引入一个额外的字段，它存储前一个节点的地址这种类型的链表就是双双链表表 (doubly linked list)链接列表链接列表Header151921232532Header151921232532•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 ListDataRlinkNodeLlink•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2510151.create a new node, the address is New.2.ptr=Header->Rlink3.if New is not NULLa.New->Llink=Headerb.Header->Rlink=Newc.New->Rlink=ptrd.ptr->Llink=Newe.New->data=XHeader在前端插入元素75插入完成Newptr75a) Insertion operation–i) at the front–ii) at the end–iii) at any postionNew75251015在双链表的末尾插入一个节点在双链表的末尾插入一个节点1.ptr=Header->Rlink2.while ptr->Rlink is not NULL ptr=ptr->Rlink3.create a new node, the address is New4.if New is not NULLa.New->Llink=ptrb.ptr->Rlink=Newc.New->Rlink=NULLd.New->data=X5.else a.print “create fail”Header在末尾插入元素75插入完成ptrptr•a) Insertion operation–i) at the front–ii) at the end–iii) at any postionNew752510151.ptr=Header->Rlink2.while ptr->data !=X and ptr is not NULL1. ptr=ptr->Rlink3.create a new node, the address is New4.if ptr is NULLa.print “can’t find X”b.return5.if ptr->data == Xa.ptr1=ptr->Rlinkb.New->Llink=ptrc.New->Rlink=ptr1d.ptr->Rlink=Newe.ptr1->Llink=Newf.New->data=XHeader在元素10后插入元素75插入完成ptrptrptr1•a) Insertion operation–i) at the front–ii) at the end–iii) at any postion25101.ptr=Header->Rlink2.if ptr is NULLa.print “list empty”b.return3.elsea.ptr1=ptr->Rlinkb.Header->Rlink=ptr1c.ptr1->Llink=Headerd.free(ptr)Header在前端删除元素删除完成15ptrptr1•b) Deletion operation：：–i) at the front–ii) at the end–iii) at any postion101.ptr=Header->Rlink2.if ptr is NULLa.print “list empty”b.return3.while ptr->Rlink is not NULL1. ptr=ptr->Rlink4.here, ptr points to the last nodea.ptr1=ptr->Llinkb.ptr1->Rlink=NULLc.free(ptr)Header在末尾删除元素删除完成15ptr25ptr1ptr•b) Deletion operation：：–i) at the front–ii) at the end–iii) at any postion1.ptr=Header->Rlink2.if ptr is NULLa.print “list empty”b.return3.while ptr->data!=X and ptr is not NULL1. ptr=ptr->Rlink4.if ptr is NULLa.print“can’t find X”b.return5.if ptr->data==Xa.ptr1=ptr->Llinkb.ptr2=ptr->Rlinkc.ptr1->Rlink=ptr2d.ptr2->Llink=ptr1e.free(ptr)Header删除元素10删除完成15ptr25ptr1ptr10ptr2•b) Deletion operation：：–i) at the front–ii) at the end–iii) at any postionc) search operation in a doubly linked list1.ptr=Header->Rlink2.while ptr->data!=X and ptr is not NULLa.ptr=ptr->Rlink3.if ptr is NULLa.print “can’t find X”b.return4.if ptr->data==Xa.return ptrptrptrreturn ptr查找成功查找元素10152510HeaderHeader1d) copy operation1.ptr1=Header->Rlink2.create a new node, the address is Header13.ptr2=Header14.ptr2->data=NULL5.ptr2->Llink=NULL6.while ptr1 is not NULLa.create a new node，the address is Newb.New->data=ptr1->datac.ptr2->Rlink=Newd.New->Llink=ptr2e.ptr1=ptr1->Rlinkf.ptr2=New7.ptr2->Rlink=NULLptr1复制结束152510Headerptr2New15ptr1ptr2New10ptr1ptr2New25ptr1NULLptr2Header2e) merge operation in a doubly linked list1.ptr=Header1->Rlink2.while ptr->Rlink is not NULLa.ptr=ptr->Rlink3.ptr1=Header2->Rlink4.ptr1->Llink=ptr5.ptr->Rlink=ptr16.free(Header2)ptr合并结束152510Header12735ptr18ptr1f) traversing the doubly linked list1.ptr=Header1->Rlink2.while ptr is not NULLa.print ptr->datab.ptr=ptr->Rlinkptr152510Header1ptr1510ptr25ptrNULL遍历结束假定你正在开发一款动作游戏，其中会给每个游戏者一套武器。

在屏幕上依次显示每种武器一旦显示第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159112351215911235125.6.2 singly linked circular list5.6.3 doubly linked circular listThere 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 list1.ptr=Header->link2.while ptr != Headera.print ptr->datab.ptr=ptr->link15102510Headerptr15ptr10ptr25遍历结束ptrinsert a node in a circular linked list at the end1.Create a new node, the address is New2.ptr=Header->link3.while ptr->link!=Headera.ptr=ptr->link4.if New is not NULLa.ptr->link=Newb.New->link=Headerc.New->data=X15102510Headerptrptr在末尾插入元素75New75插入完成•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 30 1 23 4 RowColValue01-803610730-5324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)链接列表（续）链接列表（续）DownRowColRightValuelink to the next non-zero elements in the same columnlink to the next non-zero elements in the same row5 40 00 00 00 00 00 00 00 00 00 1-80 3 61 073 0-50 1 2 30 1 23 4 3 24orthogonal list (十字链表)5 40 00 00 00 00 00 00 00 00 00 1 2 30 1 23 4 orthogonal list (十字链表)第0行第1行第2行第3行第4行第0列第1列第2列第3列5 40 00 00 00 00 00 00 00 00 00 1 2 30 1 23 4 orthogonal list (十字链表)0 1-80 3 61 073 0-53 24第0列第1列第2列第3列第0行第1行第2行第3行第4行5 40 00 00 00 00 00 00 00 00 00 1 2 30 1 23 4 orthogonal list (十字链表)0 1-80 3 61 073 0-53 24第0列第1列第2列第3列第0行第1行第2行第3行第4行5 40 00 00 00 00 00 00 00 00 00 1 2 30 1 23 4 orthogonal list (十字链表)0 1-80 3 61 073 0-53 24第0列第1列第2列第3列第0行第1行第2行第3行第4行Exercise：：0 1 0 02 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•在一个多项表达式中，每一项都伴有两个值：系数和指数•因此，若要用链表来表示一个多项表达式，每个节点应该包括以下信息：–系数（coefficient）–指数（exponent）–链接到下一个节点的指针（the pointer to point the next node）链接列表（续）链接列表（续）5.8.1 Polynomial manipulation10CoeffExpcoefficientexponentpointer to point the next nodeLink•用单链表表示多项表达式: P(x) = 3x8 - 7x6 + 14x3 + 12x – 5•注意：系数为 0的项不需要存储到节点中。

•下面我们考虑加法操作：–加法（Addition of two polynomials）链接列表（续）链接列表（续） 3 8 -7 614 312 1-5 0 Headeri) Polynomial additionPolynomial 1: 4x5 + 5x4 + 2x3 + 3x2 + 7xPolynomial 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.exp10an1Link10bn2LinkP=axn1Q=bxn2Polynomial 1: 4x5 + 5x4 + 2x3 + 3x2 + 7xPolynomial 2: 9x6 + 6x4 + 3x2读取 Polynomial 1 的第一个节点和 Polynomial 2 的第一个节点。

比较两个节点的指数值 从Polynomial 2 读取的节点的指数值较大(6 > 5)将指数值为6的节点添加到 Polynomial 3 的列表 1096Polynomial 3: 9x6Polynomial 1: 4x5 + 5x4 + 2x3 + 3x2 + 7xPolynomial 2: 9x6 + 6x4 + 3x2从Polynomial 2读取下一个节点 比较Polynomial 1的当前节点的指数和Polynomial 2的指数值 从Polynomial 1读取的节点的指数值较大 (5 > 4)因此，将指数值为5的节点添加到 Polynomial 3 的列表 1045Polynomial 3: 9x6 + 4x51096Polynomial 3: 9x6从Polynomial 1读取下一个节点 比较 Polynomial 1 和 Polynomial 2 的当前节点的指数值这两个指数值相等， 都是4 相加两个节点的系数结果节点具有的系数值是 11(6 + 5) 将结果节点添加到Polynomial 3的列表 10114Polynomial 1: 4x5 + 5x4 + 2x3 + 3x2 + 7xPolynomial 2: 9x6 + 6x4 + 3x21045Polynomial 3: 9x6 + 4x5 + 11x41096Polynomial 3: 9x6 + 4x5从两个列表读取下一个节点。

比较Polynomial 1和Polynomial 2 的当前节点的指数值 从Polynomial 1 读取的节点指数值较大 (3 > 2) 将指数值为3的节点添加到Polynomial 3的列表 Polynomial 1: 4x5 + 5x4 + 2x3 + 3x2 + 7xPolynomial 2: 9x6 + 6x4 + 3x2101141045Polynomial 3: 9x6 + 4x5 + 11x4 + 2x310961023Polynomial 3: 9x6 + 4x5 + 11x4从Polynomial 1读取下一个节点 比较 Polynomial 1 和Polynomial 2 的当前节点的指数值两个指数值相等，都是2 将两个节点的系数相加结果节点现在的系数值为6 (3 + 3) 将结果节点添加到Polynomial 3的列表 1062Polynomial 1: 4x5 + 5x4 + 2x3 + 3x2 + 7xPolynomial 2: 9x6 + 6x4 + 3x2101141045Polynomial 3: 9x6 + 4x5 + 11x4 + 2x3 + 6x2 10961023Polynomial 3: 9x6 + 4x5 + 11x4 + 2x3Polynomial 1: 4x5 + 5x4 + 2x3 + 3x2 + 7xPolynomial 2: 9x6 + 6x4 + 3x2现在，Polynomial 2中没有节点了。

将第一个列表Polynomial 1剩下的节点添加到结果列表 10711062101141045Polynomial 3: 9x6 + 4x5 + 11x4 + 2x3 + 6x2 + 7x10961023Polynomial 3: 9x6 + 4x5 + 11x4 + 2x3 + 6x2 1.Pptr=PHeader->link Qptr=QHeader->link2.create a new node Rheader3.Rheader->coeff=NULL Rheader->exp=NULL Rheader->link=NULL4.Rptr=Rheader5.while (Pptr is not NULL) and (Qptr is not NULL)a.if Pptr->exp==Qptr->exp….b.else if Pptr->exp>Qptr->exp….c.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 Qa)create a new node Newb)Rptr->link=Newc)Rptr=Newd)Rptr->coeff=Pptr->coeff+Qptr->coeffe)Rptr->exp=Pptr->expf)Rptr->link=NULLg)Pptr=Pptr->linkh)Qptr=Qptr.linka)create a new node Newb)Rptr->link=Newc)Rptr=Newd)Rptr->coeff=Pptr->coeffe)Rptr->exp=Pptr->expf)Rptr->link=NULLg)Pptr=Pptr->linka)create a new node Newb)Rptr->link=Newc)Rptr=Newd)Rptr->coeff=Qptr->coeffe)Rptr->exp=Qptr->expf)Rptr->link=NULLg)Qptr=Qptr->link6. while Pptr is not NULLa.create a new node Newb.Rptr->link=newc.Rptr=newd.Rptr->coeff=Pptr->coeffe.Rptr->exp=Pptr->expf.Rptr->link=NULLg.Pptr=Pptr->linka.7. while Qptr is not NULLa.create a new node Newb.Rptr->link=newc.Rptr=newd.Rptr->coeff=Qptr->coeffe.Rptr->exp=Qptr->expf.Rptr->link=NULLg.Qptr=Qptr->linkcontinue…课后习题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:15102510Header20The length of the circular linked list is: 4page 273 (10 and 11)本章要掌握的内容•1. 链表的特性。

•2. 单链表的基本操作•3. 双链表的基本操作•4. 循环链表的基本操作•5. 什么是稀疏矩阵？稀疏矩阵的两种压缩存储方法？–三元组表示法–十字链表表示法•6. 多项表达式加法操作的算法。