数据结构与程序设计(王丽苹)15linkedl.ppt
5/27/2023,数据结构与程序设计,1,数据结构与程序设计(15),王丽苹,5/27/2023,数据结构与程序设计,2,Linked List Implementation,本章主要讨论链表的实现。即用链接存储形式来实现列表。,5/27/2023,数据结构与程序设计,3,Linked List Implementation,链表中节点的类型定义：template struct Node/data membersNode_entry entry;Node*next;/constructorsNode();Node(Node_entry item,Node*link=NULL);,5/27/2023,数据结构与程序设计,4,Actions on a Linked List,Book P222 Figure 6.1,5/27/2023,数据结构与程序设计,5,Actions on a Linked List,5/27/2023,数据结构与程序设计,6,Implementation of Linked List,列表的链接实现方式，请参考：目录LinkList下例程,5/27/2023,数据结构与程序设计,7,Implementation of Linked List,/结构体类型Node的定义。template struct Node/data membersNode_entry entry;Node*next;/constructorsNode();Node(Node_entry item,Node*add_on=NULL);,5/27/2023,数据结构与程序设计,8,Implementation of Linked List,/构造函数的实现templateNode:Node()next=NULL;templateNode:Node(Node_entry item,Node*add_on)entry=item;next=add_on;,5/27/2023,数据结构与程序设计,9,Implementation of Linked List,enum Error_codeunderflow,overflow,range_error,success;template class List public:List();List();List(const List,5/27/2023,数据结构与程序设计,10,Implementation of Linked List,template List:List()count=0;head=NULL;,5/27/2023,数据结构与程序设计,11,Implementation of Linked List,template Node*List:set_position(int position)const/*Pre:position is a valid position in the List;0*q=head;/引入临时的指针q/通过q来周游链表for(int i=0;i next;return q;,5/27/2023,数据结构与程序设计,12,Implementation of Linked List,Insert操作,5/27/2023,数据结构与程序设计,13,Implementation of Linked List,template Error_code List:insert(int position,const List_entry,5/27/2023,数据结构与程序设计,14,Implementation of Linked List,/产生新的节点空间。new_node=new Node(x,following);if(new_node=NULL)return overflow;/将新产生的节点加入到链表中。if(position=0)head=new_node;elseprevious-next=new_node;count+;return success;,5/27/2023,数据结构与程序设计,15,Implementation of Linked Insert的两种情况：,position-1 position,previous,following,Position0,Position=0,following,head,new_node,new_node,5/27/2023,数据结构与程序设计,16,Implementation of Linked List,template Error_code List:remove(int position,List_entry,5/27/2023,数据结构与程序设计,17,Implementation of Linked Listremove的两种情况：,position-1 position,previous,following,Position0,Position=0,Position=0,following,head,5/27/2023,数据结构与程序设计,18,Implementation of Linked List,template int List:size()constreturn count;,5/27/2023,数据结构与程序设计,19,Implementation of Linked List,template bool List:full()constNode*new_node;new_node=new Node;if(new_node=NULL)return true;else delete new_node;return false;,5/27/2023,数据结构与程序设计,20,Implementation of Linked List,template bool List:empty()constreturn count=0;,5/27/2023,数据结构与程序设计,21,Implementation of Linked List,template void List:clear()List_entry x;while(!empty()remove(0,x);,5/27/2023,数据结构与程序设计,22,Implementation of Linked List,template void List:traverse(void(*visit)(List_entry,5/27/2023,数据结构与程序设计,23,Implementation of Linked List,template Error_code List:retrieve(int position,List_entry,5/27/2023,数据结构与程序设计,24,Implementation of Linked List,template Error_code List:replace(int position,const List_entry,5/27/2023,数据结构与程序设计,25,Implementation of Linked List,template List:List(const List,5/27/2023,数据结构与程序设计,26,Implementation of Linked List,template/Another methodList:List(const List,5/27/2023,数据结构与程序设计,27,Copy Constructor,p_copy head new_copy,copy,5/27/2023,数据结构与程序设计,28,Implementation of Linked List,template void List:operator=(const List/?Is it OK,这里存在一点小问题：当 List x，y;x=y/okx=x/将出现问题。,5/27/2023,数据结构与程序设计,29,Implementation of Linked List,template void List:operator=(const List,5/27/2023,数据结构与程序设计,30,Implementation of Linked List,template List:List()List_entry x;while(!empty()remove(0,x);,5/27/2023,数据结构与程序设计,31,Implementation of Linked List,template void update(List_entry,5/27/2023,数据结构与程序设计,32,Implementation of Linked List,void main()List mylist;for(int i=0;i5;i+)mylist.insert(i,i);coutYour list have mylist.size()elements:endl;mylist.traverse(print);mylist.remove(1,i);coutAfter remove(1):endl;mylist.traverse(print);mylist.remove(0,i);coutAfter remove(0):endl;mylist.traverse(print);,5/27/2023,数据结构与程序设计,33,Result,Your list have 5 elements:01234After remove(1):0234After remove(0):234,5/27/2023,数据结构与程序设计,34,Implementation of Linked List,List mylist2(mylist);cout mylist3;mylist3=mylist;coutAfter mylist3=mylist:endl;mylist3.traverse(print);,5/27/2023,数据结构与程序设计,35,Result,After mylist2(mylist):234After update:468After mylist3=mylist:468,5/27/2023,数据结构与程序设计,36,实现效率分析,在处理n个元素的链表时：Clear,insert,remove,retrieve和replace的时间与n近似。List，empty，full和size在常量时间内操作。这种实现还有没有改进的余地呢？,
