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