《数据结构与程序设计(16)-linkedList》由会员分享，可在线阅读，更多相关《数据结构与程序设计(16)-linkedList（30页珍藏版）》请在金锄头文库上搜索。
1、7/22/2024数据结构与程序设计 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 operat
2、ion refers to the same or a later position, start tracing through the list from this last-used position.7/22/2024数据结构与程序设计 2Implementation of Linked List2ntemplate nclass List npublic:nList( );nList( );nList(const List ©);nvoid operator = (const List ©);nint size( ) const;nbool full( ) const
3、;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, const List_entry &x);7/22/20
4、24数据结构与程序设计 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 set_position(int position) const
5、;n;7/22/2024数据结构与程序设计 4C+中的关键字：mutablen关键字mutable的含义：n类的mutable成员能够被任何成员函数修改，即使是const修饰的常量成员函数也能够对它进行修改。7/22/2024数据结构与程序设计 5Implementation of Linked List2nList : List()nncount = 0;nhead = NULL;ncurrent_position = 0;ncurrent = NULL;n7/22/2024数据结构与程序设计 6Implementation of Linked List2ntemplate nvoid Li
6、st : 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;n7/22/2024数据结构与程序设计 7Implementation of Linked List2ntemplate nError_code List : insert(int position, co
7、nst 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_node = NULL)nreturn overflow;7/22/2024数据结构
8、与程序设计 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;n7/22/2024数据结构与程序设计 9Implementation of Linked List2 position-1 positionprev
9、iousfollowingPosition0Position=0followingheadnew_nodenew_node7/22/2024数据结构与程序设计 10Implementation of Linked List2ntemplate nError_code List : remove(int position, List_entry &x)nnif (position = count)nreturn range_error;nNode *previous, *following;nif (position 0) nset_position(position - 1);npreviou
10、s = current;nfollowing = previous-next;nprevious-next=following-next;n7/22/2024数据结构与程序设计 11Implementation of Linked List2nelsenfollowing = head;nhead = head-next;n/should be addedncurrent_position = 0;ncurrent = head;nn x=following-entry;ndelete following;n count-;nreturn success;n7/22/2024数据结构与程序设计
11、 12Implementation of Linked List2 position-1 positionpreviousfollowingPosition0Position=0Position=0followinghead7/22/2024数据结构与程序设计 13Implementation of Linked List2ntemplate nError_code List : retrieve(int position, List_entry &x) constnnif (position = count)nreturn range_error;nNode *p_node;nset_pos
12、ition(position);nx=current-entry;nreturn success;n7/22/2024数据结构与程序设计 14Implementation of Linked List2目录目录LinkList2下例程下例程上机完成上机完成LinkList27/22/2024数据结构与程序设计 15进一步的改进nKeeping the last-used Positionn当插入的位置在最后一次使用的位置当插入的位置在最后一次使用的位置之后时，效率较高。之后时，效率较高。n当插入的位置在最后一次使用的位置当插入的位置在最后一次使用的位置之前时，需要从链表头部重新计数。之前时，需
13、要从链表头部重新计数。n改进方法：改进方法：将单链表变为双链表将单链表变为双链表7/22/2024数据结构与程序设计 16Doubly Linked ListsBOOK P227 figure 6.37/22/2024数据结构与程序设计 17Doubly Linked Listsn/定义双链表节点类型定义双链表节点类型ntemplate nstruct Node n/ data membersnNode_entry entry;nNode *next;nNode *back;n/ constructorsnNode( );nNode(Node_entry item, Node *link_ba
14、ck = NULL, Node *link_next = NULL);n;7/22/2024数据结构与程序设计 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 references the Node at position . */nnif (current_position next;
15、nelsenfor ( ; current_position != position; current_position-)ncurrent = current-back;n7/22/2024数据结构与程序设计 19Doubly Linked Lists7/22/2024数据结构与程序设计 20Doubly Linked Lists (BOOK P229 figure 6.4)nError_code List : insert(int position, const List_entry &x)nnNode *new_node, *following, *preceding;nif (posi
16、tion 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 - 1);npreceding = current;nfollowing = preceding-next;n/给给followi
17、ng和和preceding指针赋初始值。指针赋初始值。7/22/2024数据结构与程序设计 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_node;nif (following != NULL) following-back = new_node;n/调整调整current和
18、和current_position指针指针n current = new_node;ncurrent_position = position;n /Should be added.nif (position = 0)head = new_node;n count+;nreturn success;n7/22/2024数据结构与程序设计 22Doubly Linked Lists position-1 positionprecedingfollowingPosition0Position=0Count！=0followingheadnew_nodenew_nodenew_nodePosition
19、=0Count = 07/22/2024数据结构与程序设计 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);nprevious = current;nfollowing = previous-next;nprevious-next=following-next;ni
20、f(following-next)following-next-back=previous;n7/22/2024数据结构与程序设计 24Doubly Linked Listsnelsenfollowing = head;nhead = head-next;nif(head)head-back=NULL;n/should be addedncurrent_position = 0;ncurrent = head;nn x=following-entry;ndelete following;n count-;nreturn success;n7/22/2024数据结构与程序设计 25Doubly
21、Linked Lists position-1 positionpreviousfollowingPosition0Position=0Position=0followinghead7/22/2024数据结构与程序设计 26Doubly Linked Listsntemplate nclass List npublic:nList( );nList( );nList(const List ©);nvoid operator = (const List ©);nint size( ) const;nbool full( ) const;nbool empty( ) const;n
22、void 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, const List_entry &x);7/22/2024数据结构与程序设计 27Doubly Li
23、nked 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;7/22/2024数据结构与程序设计 28Implementat
24、ion of Doubly Linked List目录目录DoubleLinkList下例程下例程上机完成上机完成DoubleLinkList7/22/2024数据结构与程序设计 29Comparison of ImplementationsBOOK P230链表的优势：链表的优势：Dynamic storage. Overflow is no problem.Insert and remove operation is more quickly.链表的不足：链表的不足：每一个节点需要额外的空间存放下一个节点的每一个节点需要额外的空间存放下一个节点的地址。地址。不支持随机访问，即不能够通过下标
25、直接访问不支持随机访问，即不能够通过下标直接访问内容。内容。7/22/2024数据结构与程序设计 30Comparison of ImplementationsnP231nContiguous storage is generally preferablenwhen the entries are individually very small;nwhen the size of the list is known when the program is written;nfew insertions or deletions need to be made except at the end of the list; nwhen random access is important.nLinked storage proves superiornwhen the entries are large;nwhen the size of the list is not known in advance; andnwhen flexibility is needed in inserting, deleting, and rearranging the entries.
