




版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
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 ©);nvoid operator = (const List ©);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 ©);nvoid operator =
22、(const List ©);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. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2025-2030中国挖掘机行业市场发展现状及竞争格局与投资发展前景研究报告
- 2025-2030中国手机挂件行业市场现状分析及竞争格局与投资发展研究报告
- 不良饮食健康教育
- 中班乘车安全课件
- 葡萄园转让空白合同范本
- 中医体质健康处方
- 荷兰木鞋买卖合同协议书
- 采购合同的付款调整协议
- 保姆合同范本2025
- 解除合伙种植合同协议书
- 2023年司法鉴定程序通则
- 2023届大连市瓦房店市数学四下期末质量检测试题含解析
- 保安员在岗培训法律
- 期货市场行情及技术分析课件
- 安徽宝镁轻合金有限公司年产30万吨高性能镁基轻合金项目环境影响报告书
- 高尔夫各品牌草坪机械性能对比
- 2023上海初中英语词性转换集合一
- 高考英语真题科技说明文阅读理解精选训练含答案
- 2016-2022年全国高考英语读后续写及概要写作试题真题及范文
- 2023年中工国际工程股份有限公司招聘笔试题库及答案解析
- YS/T 534.2-2007氢氧化铝化学分析方法第2部分:烧失量的测定重量法
评论
0/150
提交评论