数据结构与程序设计(王丽苹)16-linkedl.ppt
5/27/2023,数据结构与程序设计,1,数据结构与程序设计(16),王丽苹,5/27/2023,数据结构与程序设计,2,Implementation of Linked List2,Book P225 改进的思路Keeping Suppose an application processes list entries in order or refers to the same entry several times before processing another entry.the last-used PositionRemember the last-used position in the list and,if the next operation refers to the same or a later position,start tracing through the list from this last-used position.,5/27/2023,数据结构与程序设计,3,Implementation of Linked List2,template class List public:List();List();List(const List,5/27/2023,数据结构与程序设计,4,Implementation of Linked List2,protected:/Data members for the linked list/implementation now follow.int count;mutable int current_position;mutable Node*current;Node*head;/The following auxiliary function is used to/locate list positionsvoid set_position(int position)const;,5/27/2023,数据结构与程序设计,5,C+中的关键字：mutable,关键字mutable的含义：类的mutable成员能够被任何成员函数修改，即使是const修饰的常量成员函数也能够对它进行修改。,5/27/2023,数据结构与程序设计,6,Implementation of Linked List2,List:List()count=0;head=NULL;current_position=0;current=NULL;,5/27/2023,数据结构与程序设计,7,Implementation of Linked List2,template void List:set_position(int position)const/*Pre:position is a valid position in the List:0 next;,5/27/2023,数据结构与程序设计,8,Implementation of Linked List2,template Error_code List:insert(int position,const List_entry,5/27/2023,数据结构与程序设计,9,Implementation of Linked List2,if(position=0)head=new_node;/should be addedcurrent_position=0;current=head;elseprevious-next=new_node;/should be addedset_position(position);count+;return success;,5/27/2023,数据结构与程序设计,10,Implementation of Linked List2,position-1 position,previous,following,Position0,Position=0,following,head,new_node,new_node,5/27/2023,数据结构与程序设计,11,Implementation of Linked List2,template Error_code List:remove(int position,List_entry,5/27/2023,数据结构与程序设计,12,Implementation of Linked List2,elsefollowing=head;head=head-next;/should be addedcurrent_position=0;current=head;x=following-entry;delete following;count-;return success;,5/27/2023,数据结构与程序设计,13,Implementation of Linked List2,position-1 position,previous,following,Position0,Position=0,Position=0,following,head,5/27/2023,数据结构与程序设计,14,Implementation of Linked List2,template Error_code List:retrieve(int position,List_entry,5/27/2023,数据结构与程序设计,15,Implementation of Linked List2,目录LinkList2下例程上机完成LinkList2,5/27/2023,数据结构与程序设计,16,进一步的改进,Keeping the last-used Position当插入的位置在最后一次使用的位置之后时，效率较高。当插入的位置在最后一次使用的位置之前时，需要从链表头部重新计数。改进方法：将单链表变为双链表,5/27/2023,数据结构与程序设计,17,Doubly Linked Lists,BOOK P227 figure 6.3,5/27/2023,数据结构与程序设计,18,Doubly Linked Lists,/定义双链表节点类型template struct Node/data membersNode_entry entry;Node*next;Node*back;/constructorsNode();Node(Node_entry item,Node*link_back=NULL,Node*link_next=NULL);,5/27/2023,数据结构与程序设计,19,Doubly Linked Lists,template void List:set_position(int position)const/*Pre:position is a valid position in the List:0 next;elsefor(;current_position!=position;current_position-)current=current-back;,5/27/2023,数据结构与程序设计,20,Doubly Linked Lists,5/27/2023,数据结构与程序设计,21,Doubly Linked Lists(BOOK P229 figure 6.4),Error_code List:insert(int position,const List_entry/给following和preceding指针赋初始值。,5/27/2023,数据结构与程序设计,22,Doubly Linked Lists(BOOK P229 figure 6.4),new_node=new Node(x,preceding,following);/产生新节点if(new_node=NULL)return overflow;if(preceding!=NULL)preceding-next=new_node;if(following!=NULL)following-back=new_node;/调整current和current_position指针 current=new_node;current_position=position;/Should be added.if(position=0)head=new_node;count+;return success;,5/27/2023,数据结构与程序设计,23,Doubly Linked Lists,position-1 position,preceding,following,Position0,Position=0Count！=0,following,head,new_node,new_node,new_node,Position=0Count=0,5/27/2023,数据结构与程序设计,24,Doubly Linked Lists,Error_code List:remove(int position,List_entry,5/27/2023,数据结构与程序设计,25,Doubly Linked Lists,elsefollowing=head;head=head-next;if(head)head-back=NULL;/should be addedcurrent_position=0;current=head;x=following-entry;delete following;count-;return success;,5/27/2023,数据结构与程序设计,26,Doubly Linked Lists,position-1 position,previous,following,Position0,Position=0,Position=0,following,head,5/27/2023,数据结构与程序设计,27,Doubly Linked Lists,template class List public:List();List();List(const List,5/27/2023,数据结构与程序设计,28,Doubly Linked Lists,protected:/Data members for the linked list implementation now follow.int count;mutable int current_position;mutable Node*current;Node*head;/The following auxiliary function is used to locate list positionsvoid set_position(int position)const;,5/27/2023,数据结构与程序设计,29,Implementation of Doubly Linked List,目录DoubleLinkList下例程上机完成DoubleLinkList,5/27/2023,数据结构与程序设计,30,Comparison of Implementations,BOOK P230链表的优势：Dynamic storage.Overflow is no problem.Insert and remove operation is more quickly.链表的不足：每一个节点需要额外的空间存放下一个节点的地址。不支持随机访问，即不能够通过下标直接访问内容。,5/27/2023,数据结构与程序设计,31,Comparison of Implementations,P231Contiguous storage is generally preferablewhen the entries are individually very small;when the size of the list is known when the program is written;few insertions or deletions need to be made except at the end of the list;when random access is important.Linked storage proves superiorwhen the entries are large;when the size of the list is not known in advance;andwhen flexibility is needed in inserting,deleting,and rearranging the entries.,
