数据结构与程序设计(16)-linkedList_第1页
数据结构与程序设计(16)-linkedList_第2页
数据结构与程序设计(16)-linkedList_第3页
数据结构与程序设计(16)-linkedList_第4页
数据结构与程序设计(16)-linkedList_第5页
已阅读5页,还剩25页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

1、11/23/2021数据结构与程序设计 1Implementation of Linked List2nBook P225 改进的思路改进的思路nKeeping Suppose an application processes list entries in order or refers to the same entry several times before processing another entry.nthe last-used PositionnRemember the last-used position in the list and, if the next opera

2、tion refers to the same or a later position, start tracing through the list from this last-used position.11/23/2021数据结构与程序设计 2Implementation of Linked List2ntemplate nclass List npublic:nList( );nList( );nList(const List &copy);nvoid operator = (const List &copy);nint size( ) const;nbool ful

3、l( ) const;nbool empty( ) const;nvoid clear( );nvoid traverse(void (*visit)(List_entry &);nError_code retrieve(int position, List_entry &x) const;nError_code replace(int position, const List_entry &x);nError_code remove(int position, List_entry &x);nError_code insert(int position, co

4、nst List_entry &x);11/23/2021数据结构与程序设计 3Implementation of Linked List2nprotected:n/ Data members for the linked list /implementation now follow.nint count;nmutable int current_position;nmutable Node *current;nNode *head;n/ The following auxiliary function is used to /locate list positionsnvoid s

5、et_position(int position) const;n;11/23/2021数据结构与程序设计 4C+中的关键字:mutablen关键字mutable的含义:n类的mutable成员能够被任何成员函数修改,即使是const修饰的常量成员函数也能够对它进行修改。11/23/2021数据结构与程序设计 5Implementation of Linked List2nList : List()nncount = 0;nhead = NULL;ncurrent_position = 0;ncurrent = NULL;n11/23/2021数据结构与程序设计 6Implementation

6、 of Linked List2ntemplate nvoid List : set_position(int position) constn/* Pre: position is a valid position in the List : 0 = position count .nPost: The current Node pointer references the Node at position . */nnif (position next;n11/23/2021数据结构与程序设计 7Implementation of Linked List2ntemplate nError_

7、code List : insert(int position, const List_entry &x)nnif (position count)nreturn range_error;nNode *new_node, *previous, *following;nif (position 0) nset_position(position - 1);nprevious = current;nfollowing = previous-next;nnelse following = head;nnew_node = new Node(x, following);nif (new_nod

8、e = NULL)nreturn overflow;11/23/2021数据结构与程序设计 8Implementation of Linked List2nif (position = 0)nhead = new_node;n/should be addedncurrent_position = 0;ncurrent = head;nnelsenprevious-next = new_node;n/should be addednset_position(position);nncount+;nreturn success;n11/23/2021数据结构与程序设计 9Implementatio

9、n of Linked List2 position-1 positionpreviousfollowingPosition0Position=0followingheadnew_nodenew_node11/23/2021数据结构与程序设计 10Implementation of Linked List2ntemplate nError_code List : remove(int position, List_entry &x)nnif (position = count)nreturn range_error;nNode *previous, *following;nif (po

10、sition 0) nset_position(position - 1);nprevious = current;nfollowing = previous-next;nprevious-next=following-next;n11/23/2021数据结构与程序设计 11Implementation of Linked List2nelsenfollowing = head;nhead = head-next;n/should be addedncurrent_position = 0;ncurrent = head;nn x=following-entry;ndelete followi

11、ng;n count-;nreturn success;n11/23/2021数据结构与程序设计 12Implementation of Linked List2 position-1 positionpreviousfollowingPosition0Position=0Position=0followinghead11/23/2021数据结构与程序设计 13Implementation of Linked List2ntemplate nError_code List : retrieve(int position, List_entry &x) constnnif (positi

12、on = count)nreturn range_error;nNode *p_node;nset_position(position);nx=current-entry;nreturn success;n11/23/2021数据结构与程序设计 14Implementation of Linked List2 目录目录LinkList2下例程下例程 上机完成上机完成LinkList211/23/2021数据结构与程序设计 15进一步的改进nKeeping the last-used Positionn当插入的位置在最后一次使用的位置当插入的位置在最后一次使用的位置之后时,效率较高。之后时,效率

13、较高。n当插入的位置在最后一次使用的位置当插入的位置在最后一次使用的位置之前时,需要从链表头部重新计数。之前时,需要从链表头部重新计数。n改进方法:改进方法:将单链表变为双链表将单链表变为双链表11/23/2021数据结构与程序设计 16Doubly Linked ListsBOOK P227 figure 6.311/23/2021数据结构与程序设计 17Doubly Linked Listsn/定义双链表节点类型定义双链表节点类型ntemplate nstruct Node n/ data membersnNode_entry entry;nNode *next;nNode *back;n

14、/ constructorsnNode( );nNode(Node_entry item, Node *link_back = NULL, Node *link_next = NULL);n;11/23/2021数据结构与程序设计 18Doubly Linked Listsntemplate nvoid List : set_position(int position) constn/* Pre: position is a valid position in the List : 0 = position count .nPost: The current Node pointer refe

15、rences the Node at position . */nnif (current_position next;nelsenfor ( ; current_position != position; current_position-)ncurrent = current-back;n11/23/2021数据结构与程序设计 19Doubly Linked Lists11/23/2021数据结构与程序设计 20Doubly Linked Lists (BOOK P229 figure 6.4)nError_code List : insert(int position, const Li

16、st_entry &x)nnNode *new_node, *following, *preceding;nif (position count) return range_error;nif (position = 0) /在第在第0号位置插入的特殊情况号位置插入的特殊情况nif (count = 0) following = NULL;nelse nset_position(0);nfollowing = current;nnpreceding = NULL;nnelse /一般情况,在链表中间或者末尾插入一般情况,在链表中间或者末尾插入nset_position(position

17、 - 1);npreceding = current;nfollowing = preceding-next;n/给给following和和preceding指针赋初始值。指针赋初始值。11/23/2021数据结构与程序设计 21Doubly Linked Lists (BOOK P229 figure 6.4)n new_node = new Node(x, preceding, following);/产生新节点产生新节点nif (new_node = NULL) return overflow;nif (preceding != NULL) preceding-next = new_no

18、de;nif (following != NULL) following-back = new_node;n/调整调整current和和current_position指针指针n current = new_node;ncurrent_position = position;n /Should be added.nif (position = 0)head = new_node;n count+;nreturn success;n11/23/2021数据结构与程序设计 22Doubly Linked Lists position-1 positionprecedingfollowingPosi

19、tion0Position=0Count!=0followingheadnew_nodenew_nodenew_nodePosition=0Count = 011/23/2021数据结构与程序设计 23Doubly Linked ListsnError_code List : remove(int position, List_entry &x)nnif (position = count)nreturn range_error;nNode *previous, *following;nif (position 0) nset_position(position - 1);nprevi

20、ous = current;nfollowing = previous-next;nprevious-next=following-next;nif(following-next)following-next-back=previous;n11/23/2021数据结构与程序设计 24Doubly Linked Listsnelsenfollowing = head;nhead = head-next;nif(head)head-back=NULL;n/should be addedncurrent_position = 0;ncurrent = head;nn x=following-entr

21、y;ndelete following;n count-;nreturn success;n11/23/2021数据结构与程序设计 25Doubly Linked Lists position-1 positionpreviousfollowingPosition0Position=0Position=0followinghead11/23/2021数据结构与程序设计 26Doubly Linked Listsntemplate nclass List npublic:nList( );nList( );nList(const List &copy);nvoid operator =

22、(const List &copy);nint size( ) const;nbool full( ) const;nbool empty( ) const;nvoid clear( );nvoid traverse(void (*visit)(List_entry &);nError_code retrieve(int position, List_entry &x) const;nError_code replace(int position, const List_entry &x);nError_code remove(int position, Lis

23、t_entry &x);nError_code insert(int position, const List_entry &x);11/23/2021数据结构与程序设计 27Doubly Linked Listsnprotected:n/ Data members for the linked list implementation now follow.nint count;nmutable int current_position;nmutable Node *current;nNode *head;n/ The following auxiliary function is used to locate list positionsnvoid set_position(int position) const;n;11/23/2021数据结构与程序设计 28Implementation of Doubly Linked List 目录目录DoubleLinkList下例程下例程 上机完成上机完成DoubleLi

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论