攻克C语言链表.ppt
《攻克C语言链表.ppt》由会员分享,可在线阅读,更多相关《攻克C语言链表.ppt(51页珍藏版)》请在三一文库上搜索。
1、Data Structure Using C,信息管理学院 尹晓 yx_,Chapter 5 Linked Lists,在本章中,我们将学到: 认识链表的特性 链表的三种类型 单链表 双链表 循环链表 稀疏矩阵 利用链表对多项表达式进行加法计算,假设有一个单链表中存储了100000个数字,这些数字从第一个节点开始依次按升序排序。 如果我们想以升序的方式显示这些数字,该怎么办呢? 答案是:从第一个节点开始遍历列表。,假如我们又需要以降序的方式显示这些数字,如何解决此问题呢? 单链表中每一个节点链接到序列中的下一个节点。这意味着我们只能以单向遍历列表。 要以降序的方式显示数字,我们需要反转(rev
2、erse)这个链表。,链接列表,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,反转结束,上述算法的存在什么问题? 无论你什么时候访问下一节点,你都需要调整三个变量的所有链接。 此方法的缺点:对长链表来说效率低且耗时。 如何
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)。 在双链表中,每个节点需要存储: 数据 下一个节点的地址 前一个
4、节点的地址 定义双链表中节点的结构体类型 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.
5、 (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),链
6、接列表(续),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 pos
7、tion,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 en
8、d 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后插入元
9、素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 p
10、ostion,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 p
11、tr 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)
12、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
13、 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-
14、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,遍历结束,假定你正在开发一款动作游戏,其中会给每个游
15、戏者一套武器。 在屏幕上依次显示每种武器。一旦显示第n个武器后,就会再次显示第一次出现的武器,并且这种顺序会跟前面一样继续。 你将使用哪种数据结构来存储武器的列表?,我们可以使用单链表。 但是,武器需要以循环重复的次序显示。 因此,一旦显示了所有武器,指针必须从列表中第一个武器重新开始。 这需要在每次到达列表结尾时重新初始化指针。 在此情况下,如果遍历最后一个武器对应的节点后指针能够自动移到列表中的第一个武器,那将会更加简单。 使用循环链表(circular linked list)可以实现这一点。,A circular linked list is a linked list where t
16、he 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 cir
17、cular 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
18、 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,He
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 攻克 语言
链接地址:https://www.31doc.com/p-2462415.html