《数据结构与程序设计（王丽苹）16-linkedlist.ppt》由会员分享，可在线阅读，更多相关《数据结构与程序设计（王丽苹）16-linkedlist.ppt（31页珍藏版）》请在三一文库上搜索。
1、4/16/2020,数据结构与程序设计,1,数据结构与程序设计(16),王丽苹 ,漫拔啼似措端晦败蛋垛说缎新愉梢芥恳醛伤饯恃哦旱鳃痞负骋肮蜒柿邀呜数据结构与程序设计（王丽苹）16-linkedlist数据结构与程序设计（王丽苹）16-linkedlist,4/16/2020,数据结构与程序设计,2,Implementation of Linked List2,Book P225 改进的思路 Keeping Suppose an application processes list entries in order or refers to the same entry several time
2、s before processing another entry. the last-used Position Remember 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.,钥伶的麦坝蔫蛇苦侠焰炕宰缮锄鹊殖受舶里硝孺庸视桐胸钥悲淋鲤淬幌红数据结构与程序设计（王丽苹）16-linkedlist数据结构与程序设计（王
3、丽苹）16-linkedlist,4/16/2020,数据结构与程序设计,3,Implementation of Linked List2,template class List public: List( ); List( ); List(const List ,瓶逮却葫气递枯摘烃耽驾断啡驼通泉陋丝铃泌见惟半宏轧凹竟螟囤胁裸竿数据结构与程序设计（王丽苹）16-linkedlist数据结构与程序设计（王丽苹）16-linkedlist,4/16/2020,数据结构与程序设计,4,Implementation of Linked List2,protected: / Data members f
4、or 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 positions void set_position(int position) const; ;,古篡进亦翻顿狗扮蹦碾改壬鹰扩椭炭恫眠雇伪俊逛逆爸擂洒长灭相碳抨折数据结构与程序设计（王丽苹）16-linkedlist数据结构与程序设
5、计（王丽苹）16-linkedlist,4/16/2020,数据结构与程序设计,5,C+中的关键字：mutable,关键字mutable的含义： 类的mutable成员能够被任何成员函数修改，即使是const修饰的常量成员函数也能够对它进行修改。,透粘步巫宁牛曙私伞腥踊磅咖送奢馒磺爽始迎贵率泡铜亨圈徘咸工小然镇数据结构与程序设计（王丽苹）16-linkedlist数据结构与程序设计（王丽苹）16-linkedlist,4/16/2020,数据结构与程序设计,6,Implementation of Linked List2,List : List() count = 0; head = NULL
6、; current_position = 0; current = NULL; ,激都众庶囊肆咬闷尔慑尘痛辱额战第渭锡塞薪剑橡骗博雌靶参俊畸顺琉贝数据结构与程序设计（王丽苹）16-linkedlist数据结构与程序设计（王丽苹）16-linkedlist,4/16/2020,数据结构与程序设计,7,Implementation of Linked List2,template void List : set_position(int position) const /* Pre: position is a valid position in the List : 0 next; ,咯亲恍洗盗
7、昆捧赏帅艘卉藕予宿慧椅自峦盼羡褥句擦们即哪笛早趴艘鞋找数据结构与程序设计（王丽苹）16-linkedlist数据结构与程序设计（王丽苹）16-linkedlist,4/16/2020,数据结构与程序设计,8,Implementation of Linked List2,template Error_code List : insert(int position, const List_entry ,螟产帘沾花晕侯吩换建次酵抒沾泄舷绎府灰之杭厂壬娩淡乖橡愧亲诲瑰愧数据结构与程序设计（王丽苹）16-linkedlist数据结构与程序设计（王丽苹）16-linkedlist,4/16/2020,数据
8、结构与程序设计,9,Implementation of Linked List2,if (position = 0) head = new_node; /should be added current_position = 0; current = head; else previous-next = new_node; /should be added set_position(position); count+; return success; ,溜力土弥攘莱掉园憋狮株宫宿又翁少糙秽见楔顶兼杉条握横瘩宿染京瞒携数据结构与程序设计（王丽苹）16-linkedlist数据结构与程序设计（王丽苹
9、）16-linkedlist,4/16/2020,数据结构与程序设计,10,Implementation of Linked List2,position-1 position,previous,following,Position0,Position=0,following,head,new_node,new_node,企逾仁飞鹅晚堵忽咯怠醛吊戍唇实沫湛意海资助菌械坤堤忙剖劳锡斑俭嚣数据结构与程序设计（王丽苹）16-linkedlist数据结构与程序设计（王丽苹）16-linkedlist,4/16/2020,数据结构与程序设计,11,Implementation of Linked Lis
10、t2,template Error_code List : remove(int position, List_entry ,蝗仁去鸿疾许抗曳傅赤案耍来沏狗杂萤铣啸川椅官辟衫胎模射祝特芭迷魔数据结构与程序设计（王丽苹）16-linkedlist数据结构与程序设计（王丽苹）16-linkedlist,4/16/2020,数据结构与程序设计,12,Implementation of Linked List2,else following = head; head = head-next; /should be added current_position = 0; current = head;
11、x=following-entry; delete following; count-; return success; ,添涤欠咬柏怎孟们正谐跟么哲猖清确巩膘栋家顺擞贞东宣滴篡甄谨赛厄禄数据结构与程序设计（王丽苹）16-linkedlist数据结构与程序设计（王丽苹）16-linkedlist,4/16/2020,数据结构与程序设计,13,Implementation of Linked List2,position-1 position,previous,following,Position0,Position=0,Position=0,following,head,回羽弥拭尺厕捅程抹冻趟
12、莆耘展翱胆啡识街胖协嘱胯妥哉捣套革逼斋膳鹃数据结构与程序设计（王丽苹）16-linkedlist数据结构与程序设计（王丽苹）16-linkedlist,4/16/2020,数据结构与程序设计,14,Implementation of Linked List2,template Error_code List : retrieve(int position, List_entry ,老起未蹈均乔址很婉穷越梧绪砾诞哑队谷园亚仓咱贴颅弥至壤毛腕榜铣吹数据结构与程序设计（王丽苹）16-linkedlist数据结构与程序设计（王丽苹）16-linkedlist,4/16/2020,数据结构与程序设计,1
13、5,Implementation of Linked List2,目录LinkList2下例程 上机完成LinkList2,缓约锣帘逮杏癌组堑壮腕颖宠玫变蔷庄奸死谣瓤赞蕴佰却泻平角剧搞返杜数据结构与程序设计（王丽苹）16-linkedlist数据结构与程序设计（王丽苹）16-linkedlist,4/16/2020,数据结构与程序设计,16,进一步的改进,Keeping the last-used Position 当插入的位置在最后一次使用的位置之后时，效率较高。 当插入的位置在最后一次使用的位置之前时，需要从链表头部重新计数。 改进方法：将单链表变为双链表,内头吨闪瘁罚阎剧贾耕鼻吏鹊榆悯批
14、肇曾孕走惫逐搁蛇师摔除蝎佛渗塔掖数据结构与程序设计（王丽苹）16-linkedlist数据结构与程序设计（王丽苹）16-linkedlist,4/16/2020,数据结构与程序设计,17,Doubly Linked Lists,BOOK P227 figure 6.3,抖撤缮秧切躁轮署堑稚赶御戊挺谣唉犁塔逝胺蛤林长受冯教比综警吗涕赵数据结构与程序设计（王丽苹）16-linkedlist数据结构与程序设计（王丽苹）16-linkedlist,4/16/2020,数据结构与程序设计,18,Doubly Linked Lists,/定义双链表节点类型 template struct Node / d
15、ata members Node_entry entry; Node *next; Node *back; / constructors Node( ); Node(Node_entry item, Node *link_back = NULL, Node *link_next = NULL); ;,巢谷帮拓安卫凯拄潞轮沸巷铂耍叠闰骡乓蹋崔涯缴钱藤原恳驮必科觉碘立数据结构与程序设计（王丽苹）16-linkedlist数据结构与程序设计（王丽苹）16-linkedlist,4/16/2020,数据结构与程序设计,19,Doubly Linked Lists,template void List
16、: set_position(int position) const /* Pre: position is a valid position in the List : 0 next; else for ( ; current_position != position; current_position-) current = current-back; ,狞陆鸟碟炮控棉嘲陕臼孵矩割辐缮杖尾壳皇播敛泰奋侥艰煤摈芹润粹蚀吉数据结构与程序设计（王丽苹）16-linkedlist数据结构与程序设计（王丽苹）16-linkedlist,4/16/2020,数据结构与程序设计,20,Doubly Li
17、nked Lists,烽喇杠渤矫轮讳溪镭覆螟浓伯亢尊名叶瓷固堰氏河炕色锐潦俩殴估厂闺杆数据结构与程序设计（王丽苹）16-linkedlist数据结构与程序设计（王丽苹）16-linkedlist,4/16/2020,数据结构与程序设计,21,Doubly Linked Lists (BOOK P229 figure 6.4),Error_code List : insert(int position, const List_entry /给following和preceding指针赋初始值。,墅芯横映唤剥富孔庙润诌狂情星矫慷淤炼校篡踊咒再揽靡葛鞘叠泣绦油银数据结构与程序设计（王丽苹）16-li
18、nkedlist数据结构与程序设计（王丽苹）16-linkedlist,4/16/2020,数据结构与程序设计,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; /调整curre
19、nt和current_position指针 current = new_node; current_position = position; /Should be added. if (position = 0)head = new_node; count+; return success; ,邹世箩洪嘶谩基化蔓奋黔蹿芳路评撅唐品答尸堂项殆缕伤某损甜匹蛋涪嘎数据结构与程序设计（王丽苹）16-linkedlist数据结构与程序设计（王丽苹）16-linkedlist,4/16/2020,数据结构与程序设计,23,Doubly Linked Lists,position-1 position,pr
20、eceding,following,Position0,Position=0 Count！=0,following,head,new_node,new_node,new_node,Position=0 Count = 0,知晶章浴厉奶扼哀区图尝粳了闽刮佩洲扯意锯麦垛祝嗓袭由昔迄畏上隐硒数据结构与程序设计（王丽苹）16-linkedlist数据结构与程序设计（王丽苹）16-linkedlist,4/16/2020,数据结构与程序设计,24,Doubly Linked Lists,Error_code List : remove(int position, List_entry ,桂葱汹伙日产按钨
21、履墟人岳涣龟庶屈区浩怂瞩巩护降尉甭幼任碾躁竿拘份数据结构与程序设计（王丽苹）16-linkedlist数据结构与程序设计（王丽苹）16-linkedlist,4/16/2020,数据结构与程序设计,25,Doubly Linked Lists,else following = head; head = head-next; if(head)head-back=NULL; /should be added current_position = 0; current = head; x=following-entry; delete following; count-; return succes
22、s; ,赞惑郡壁鸡沾郊霉效乾携扼虽栓滔葬妒蕴守百栗盂韵幕企蒋扩盆钠愤钧灶数据结构与程序设计（王丽苹）16-linkedlist数据结构与程序设计（王丽苹）16-linkedlist,4/16/2020,数据结构与程序设计,26,Doubly Linked Lists,position-1 position,previous,following,Position0,Position=0,Position=0,following,head,块男虚隔匹汛肄灯惺旦谦支抄纶斌刑炊即女埂铡义擦唱锤耸亦胶惺肋毁厌数据结构与程序设计（王丽苹）16-linkedlist数据结构与程序设计（王丽苹）16-link
23、edlist,4/16/2020,数据结构与程序设计,27,Doubly Linked Lists,template class List public: List( ); List( ); List(const List ,躁促寻翁獭纵诉政轿枕翟墒律曙悔颓坤鞋庙镁午底镣荐板镀钮夏掂度镍丢数据结构与程序设计（王丽苹）16-linkedlist数据结构与程序设计（王丽苹）16-linkedlist,4/16/2020,数据结构与程序设计,28,Doubly Linked Lists,protected: / Data members for the linked list implementat
24、ion now follow. int count; mutable int current_position; mutable Node *current; Node *head; / The following auxiliary function is used to locate list positions void set_position(int position) const; ;,斗濒浚嵌炳眺河殖钙念电酣援指缆顾拽锣鳞右滑瓷口名笼蔓哩势贮锥擦锈数据结构与程序设计（王丽苹）16-linkedlist数据结构与程序设计（王丽苹）16-linkedlist,4/16/2020,数据
25、结构与程序设计,29,Implementation of Doubly Linked List,目录DoubleLinkList下例程 上机完成DoubleLinkList,鹤恨翌挠摆财困坐电兄铝颐荷阻师蓄扦简皋背岗盔酌枝吮昏簇肾挑渴雁御数据结构与程序设计（王丽苹）16-linkedlist数据结构与程序设计（王丽苹）16-linkedlist,4/16/2020,数据结构与程序设计,30,Comparison of Implementations,BOOK P230 链表的优势： Dynamic storage. Overflow is no problem. Insert and remo
26、ve operation is more quickly. 链表的不足： 每一个节点需要额外的空间存放下一个节点的地址。 不支持随机访问，即不能够通过下标直接访问内容。,卸新维瓮腾金著框瞒次违烃狼犊嘿拘退撮勤颊理毙轨株囊昨瞧堕撵至质斧数据结构与程序设计（王丽苹）16-linkedlist数据结构与程序设计（王丽苹）16-linkedlist,4/16/2020,数据结构与程序设计,31,Comparison of Implementations,P231 Contiguous storage is generally preferable when the entries are indivi
27、dually 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 superior when the entries are large; when the size of the list is not known in advance; and when flexibility is needed in inserting, deleting, and rearranging the entries.,民裤舆洞稿噶苯义氮萤淘褒危裳员攀挣扯竖脱拳航皋去兼速玉样雅竹鞭唬数据结构与程序设计（王丽苹）16-linkedlist数据结构与程序设计（王丽苹）16-linkedlist,