攻克C语言链表ppt课件

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

2、reverse)这个链表。链接列表链接列表11000002Header3.11000002Header3.反转单链表反转单链表ptr1=Header-linkptr2=ptr1-linkptr3=ptr2-linkptr1-link=NULLwhile ptr3不为空不为空ptr2-link=ptr1ptr1=ptr2ptr2=ptr3ptr3=ptr3-linkptr2-link=ptr1Header-link=ptr25710 22Headerptr2ptr110ptr31015ptr1ptr2 ptr3ptr1ptr2ptr3ptr1ptr2ptr3NULL反转终了上述算法的存在什么问题

3、？无论他什么时候访问下一节点，他都需求调整三个变量的一切链接。此方法的缺陷：对长链表来说效率低且耗时。如何处理此问题？假设列表中每一个节点不仅包含序列中其下一个节点的地址，而且还包含其前一节点的地址，那么此问题就可以处理。链接列表链接列表思索下面的单链表。我们可以在单链表的每个节点中引入一个额外的字段，它存储前一个节点的地址。这种类型的链表就是双链表 (doubly linked list)。链接列表链接列表Header151921232532Header151921232532Doubly linked lists are also called two-way list or two-wa

4、y chain)。在双链表中，每个节点需求存储：数据下一个节点的地址前一个节点的地址定义双链表中节点的构造体类型struct nodeint 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 use

5、d to point to the previous node and the next node. (page 184)链接列表续链接列表续5.5.1 DefinitionThe operations 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 poi

6、nter nodes have to be modified. (page 184)链接列表续链接列表续5.5.2 Opertations on a Doubly Linked List251015create a new node, the address is New.ptr=Header-Rlinkif New is not NULLNew-Llink=HeaderHeader-Rlink=NewNew-Rlink=ptrptr-Llink=NewNew-data=XHeader在前端插入元素75插入完成Newptr75a) Insertion operationi) at the fr

7、ontii) at the endiii) at any postionNew75251015在双链表的末尾插入一个节点在双链表的末尾插入一个节点ptr=Header-Rlinkwhile ptr-Rlink is not NULL ptr=ptr-Rlinkcreate a new node, the address is Newif New is not NULLNew-Llink=ptrptr-Rlink=NewNew-Rlink=NULLNew-data=Xelse print “create failHeader在末尾插入元素75插入完成ptrptra) Insertion oper

8、ationi) at the frontii) at the endiii) at any postionNew75251015ptr=Header-Rlinkwhile ptr-data !=X and ptr is not NULL ptr=ptr-Rlinkcreate a new node, the address is Newif ptr is NULLprint “cant find Xreturnif ptr-data = Xptr1=ptr-RlinkNew-Llink=ptrNew-Rlink=ptr1ptr-Rlink=Newptr1-Llink=NewNew-data=X

9、Header在元素10后插入元素75插入完成ptrptrptr1a) Insertion operationi) at the frontii) at the endiii) at any postion2510ptr=Header-Rlinkif ptr is NULLprint “list emptyreturnelseptr1=ptr-RlinkHeader-Rlink=ptr1ptr1-Llink=Headerfree(ptr)Header在前端删除元素删除完成15ptrptr1b) Deletion operation：i) at the frontii) at the endiii

10、) at any postion10ptr=Header-Rlinkif ptr is NULLprint “list emptyreturnwhile ptr-Rlink is not NULL ptr=ptr-Rlinkhere, ptr points to the last nodeptr1=ptr-Llinkptr1-Rlink=NULLfree(ptr)Header在末尾删除元素删除完成15ptr25ptr1ptrb) Deletion operation：i) at the frontii) at the endiii) at any postionptr=Header-Rlink

11、if ptr is NULLprint “list emptyreturnwhile ptr-data!=X and ptr is not NULL ptr=ptr-Rlinkif ptr is NULLprint“cant find Xreturnif ptr-data=Xptr1=ptr-Llinkptr2=ptr-Rlinkptr1-Rlink=ptr2ptr2-Llink=ptr1free(ptr)Header删除元素10删除完成15ptr25ptr1ptr10ptr2b) Deletion operation：i) at the frontii) at the endiii) at

12、any postionc) search operation in a doubly linked listptr=Header-Rlinkwhile ptr-data!=X and ptr is not NULLptr=ptr-Rlinkif ptr is NULLprint “cant find Xreturnif ptr-data=Xreturn ptrptrptrreturn ptr查找胜利查找元素10152510HeaderHeader1d) copy operationptr1=Header-Rlinkcreate a new node, the address is Header

13、1ptr2=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-Rlink=NULLptr1复制终了152510Headerptr2New15ptr1ptr2New10ptr1ptr2New25ptr1NULLptr2Header2e) merge operation in a doubly linked list

14、ptr=Header1-Rlinkwhile ptr-Rlink is not NULLptr=ptr-Rlinkptr1=Header2-Rlinkptr1-Llink=ptrptr-Rlink=ptr1free(Header2)ptr合并终了152510Header12735ptr18ptr1f) traversing the doubly linked listptr=Header1-Rlinkwhile ptr is not NULLprint ptr-dataptr=ptr-Rlinkptr152510Header1ptr1510ptr25ptrNULL遍历终了假定他正在开发一款动作

15、游戏，其中会给每个游戏者一套武器。在屏幕上依次显示每种武器。一旦显示第n个武器后，就会再次显示第一次出现的武器，并且这种顺序会跟前面一样继续。他将运用哪种数据构造来存储武器的列表？我们可以运用单链表。但是，武器需求以循环反复的次序显示。因此，一旦显示了一切武器，指针必需从列表中第一个武器重新开场。这需求在每次到达列表结尾时重新初始化指针。在此情况下，假设遍历最后一个武器对应的节点后指针可以自动移到列表中的第一个武器，那将会更加简单。运用循环链表(circular linked list)可以实现这一点。 A circular linked list is a linked list where

16、 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 List159112351215911235125.6.2 singly linked circular list

17、5.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 perfor

18、med on circular linked list are：a) insertionb) deletionc) traversingd) searchinge) mergingf) splittingg) copying链接列表续链接列表续5.6.4 Opertations on a Circular Linked Listtraversing the circular linked listptr=Header-linkwhile ptr != Headerprint ptr-dataptr=ptr-link15102510Headerptr15ptr10ptr25遍历终了ptrinse

19、rt a node in a circular linked list at the endCreate a new node, the address is Newptr=Header-linkwhile ptr-link!=Headerptr=ptr-linkif New is not NULLptr-link=NewNew-link=HeaderNew-data=X15102510Headerptrptr在末尾插入元素75New75插入完成Sparse Matrices稀疏矩阵 is a matrices contianing very few non-zero elements. (p

20、age 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 Sparse Matrices5.7.1 Array representation Each non-zero element in the sparse matrix is re

21、presented the following form: (Row, Column, Value)0 1 2 30 1 23 4 RowColValue01-803610730-53245.7.2 Linked-List representation for Sparse MatricesEach 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 nod

22、e 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 row5 40 00 00 00 00 00 00 00 00 00 1-80

23、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

24、 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 0 0 0 -30 0 8 05 0 0 0 Polynomial manipulation计算多项式表达式Dynamic storage management动态

25、存储管理Garbage Collection渣滓回收Buddy Systems同伴系统链接列表续链接列表续5.8 ApplicationThe 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 manipulation10Coe

26、ffExpcoefficientexponentpointer 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 Headeri) Polynomial additionPolynomial 1: 4x5 + 5x4 + 2x3 + 3x2 + 7xPolynomial 2: 9x6 + 6x4 + 3x2To ad

27、d 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.coeff = P.CoeffR.exp = P.expCase 3: P.exp 5)。将指数值为6的节点添加到

28、 Polynomial 3 的列表 。1096Polynomial 3: 9x6Polynomial 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读取

29、下一个节点。 比较 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 的当前

30、节点的指数值。 从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。 将两个节

31、点的系数相加。结果节点如今的系数值为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 + 2x3Polynomial 1: 4x5 + 5x4 + 2x3 + 3x2 + 7xPolynomial 2: 9x6 + 6x4 + 3x2如今，Polyn

32、omial 2中没有节点了。 将第一个列表Polynomial 1剩下的节点添加到结果列表 。10711062101141045Polynomial 3: 9x6 + 4x5 + 11x4 + 2x3 + 6x2 + 7x10961023Polynomial 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-exp.else if Pptr-expQptr-exp.else .1) assume that the two polynomials