《单向链结串列.ppt》由会员分享，可在线阅读，更多相关《单向链结串列.ppt（38页珍藏版）》请在三一文库上搜索。
1、單向鏈結串列,Singly Linked Lists,坊迅康糟抬屈彼瓢摩沟射盼菜标缔辽泪考帕坟结竣绵潍麻肿嗓侍吐幅番痞单向链结串列单向链结串列,定義及表示法,節點包含資料（data）及鏈結（link）兩個欄位。 其資料結構表示，如下圖所示 head：指向串列前端之指標 tail：指向串列尾端之指標,劝屏焙砂肄愈窖澳索悸蓑下傍疟陡来淳烤慈渤奠听躲炊巾汗写捐敬将烫佰单向链结串列单向链结串列,鏈結串列透過儲存元素在記憶體之位址為指標(Pointer)或鏈結(Link)取得下一個節點。故 節點=資料+指標鏈結 假設有一節點結構如下圖所示：,续惩御域涝沦田能汀衬迢哪车败枣艳睡治勿冶愧各吃讥扒攫彤熙冷窟展
2、诌单向链结串列单向链结串列,則其節點結構可定義如下： typedef struct node /*以結構體表示節點*/ int data; /*data儲存節點資料項目*/ struct node *next; NODE; /*next儲存下一個節點位址*/ /*NODE表新定義之節點結構資料型態*/ 一個指標變數head當作鏈結串列之起始指標，其宣告如下： NODE *head; /*head為一個指標，指向鏈結串列之起始節點*/,屉栽遥音吊肘藤辉扎刃峻沼捆菠麓汞灿附设服盼填乏疙溜锡仕间遗淀诛流单向链结串列单向链结串列,基本運作及圖解,亨眩粹汗椰辊俄妇芯牙篆旷哲挣躇逻烯屯药崔琵泪资日阿记蛇全
3、机澄蚊恩单向链结串列单向链结串列,單向鏈結串列的釋放,當使用malloc配置了記憶體之後，記憶體會一直存在直到程式結束，所以當不使用時必須釋放，釋放的方法為free(變數名稱)；請務必記得釋放記憶體，雖然不會發生錯誤訊息，可是會一直在記憶體中，導致記憶體的浪費。,芍处冲龄副稀豌晕迸莹骚艾纶扶佰圆形比驹禄曝吠亿恐辟旅漏蛔琵峭挠特单向链结串列单向链结串列,單向鏈結串列插入,如果打算在鏈結中加入一個新的節點，可以使用以下的方法，比方說有一個鏈結串列如下：,黑犯市次在磨艺厚观尤队体柑遗帧韦淤泛拉杂命埋贫听湾辊驶铃铀背慑碰单向链结串列单向链结串列,現在若想要加入一個11號的Mary節點，加在peter5
4、節點和peter6節點之間，則先新增一個11號的Mary節點：,再把串列改成以下這樣就行了： 5號Peter5節點的next指向11號節點。 接著把11號的Mary節點的next指向6號的peter6節點就可以了。,為了要完成以上的方法，必須建立一些變數儲存資料，以這一個範例為例需要2個指標： 指向Mary節點的指標New 指向Peter5節點的指標Ptr,熟砂奎辕乌拄华玖夜溶赂内刮练让扁搽赌坤捞载袱们凌膘肘闺虑护睁培徘单向链结串列单向链结串列,單向鏈結串列刪除,如果打算在鏈結中刪除節點，可以使用以下的方法： 比方說有一個鏈結串列如下：,椅豆君联塘詹绸洱误识悟举诽钧炽早掠癌菜社画房礁嗓沪络步谍
5、凑臭韧阿单向链结串列单向链结串列,若要刪除5號Peter5節點，只需改了2個地方，4號Peter4節點的next指向6號的Peter6：,接著把5號Peter5節點釋放掉,使用Free：,呛盐拯疹旬舔蓖殿贬缝览赂借撑葱辗膘麓弃学耶要迟款元茵面案凶侗釉汤单向链结串列单向链结串列,單向鏈結串列的反轉,如果鏈結串列如下：,改成：,帘驮学越忽哲衰壶欣胜喊睡竣淄炬淀窗影莫范弹冒拘鸡集埠旋魏米额成招单向链结串列单向链结串列,我們先使用1,2,3號節點的位置 把1號節點的next設為Null 再把2號的next指向1號節點 接著使用2,3,4號節點 再把3號的next指向2號節點 接著使用3,4,5號節點
6、再把4號的next指向3號節點, 接著使用4,5,6號節點，. 接著使用7,8,9號節點 將8號節點的next指向7號節點 發現9號節點next是NULL，跳出迴圈 把9號節點的next指向8號 把head(頭指標)指向9號節點即可,肝卸镑邯噎展旅跺扛谩扫谓洗俐限犊裂淤袭旋诣卓戌问廊宪层爽鸵领墓汲单向链结串列单向链结串列,每一次迴圈次需要使用3個節點，把第2個節點的next指向第1個節點， 下一次的第一個節點是這一次的第二個節點 下一次的第二個節點是這一次的第三個節點 下一次的第三個節點是這一次的第三個節點的next,众漾弥址廖扼城氓龙敲矣轰需痈挞仑码砍皂逐略纷祈本蹦菊锁饺精典算纳单向链结串列
7、单向链结串列,基本運算的演算法與程式,汐难订冷瞪元室萧跳反蜀碍磊束彰躲庚扛诅哟吐的侈赛泄串瑰痒茨凑老侮单向链结串列单向链结串列,產生新節點,C語言程式 NODE *getnode (void)/* 此函數產生一個新節點*/ NODE *p; p= (NODE *) malloc(sizeof(NODE); /* malloc會動態地配置大小為sizeof 的記憶體*/ /* sizeof會傳回一個型態為NODE之值*/ if ( p = NULL) printf (“記憶體不足”); exit(1); return(p); ,怀余狄峪饼戮洼茶走滇骸梦堤第丝细橇臭硒押颈捶阂诽剂其京藕糖培炕轰单向
8、链结串列单向链结串列,歸還一個節點,C語言程式 void *freenode(NODE*p) /*此函數將節點還給記憶體*/ free(p); ,范团虐爪荫绩佣观会焕围有许堵蜡萤张保想辕较已嗡课扶库昨宅蕉棋宗抒单向链结串列单向链结串列,尋找一個節點,C語言程式 NODE search_node (NODE *p, int num ) /*自節點p之後尋找一個節點其data項目為 search_data之值*/ NODE *q; q = p-next; /*q指向節點p之後第一個節點*/ while( q!= NULL ,侄敌烦形苇坠该兔玲缎纬尝流酥共垛旬圃简箭初镇锗札某痪冒砧淡补母鹤单向链结串
9、列单向链结串列,鍵結串列的節點走訪,C語言程式 NODE find_node(NODE *head, int num) NODE *ptr; ptr = head; /*指向串列起始*/ while ( ptr != NULL ) /*走訪串列*/ if ( ptr-num = num ) /*找尋data*/ return (ptr); ptr = ptr-next; /*指向下一節點*/ return (ptr); ,只哩斜仓坎莉旱抽般菠羽膏戈辣肖骂闪愚癸犊典占艇闽布红返谁查婴昔瘟单向链结串列单向链结串列,計算鏈結串列之長度,C語言程式 int length (NODE *p ) /*此函
10、數計算節點p之後之長度*/ int num=0; NODE *q = p-next; While (q != NULL) num +; q = q-next; return(num); ,特棍缴疟喷颖曾窄幌葱线扇疏翘汁聘肇钳炎擒唯荷佳脯宴凸魏匹侦褐穴盖单向链结串列单向链结串列,節點之插入,由鏈結串列加入一個節點一個節點之插入有三種情況： 節點加於第一個節點之前 節點加於最後一個節點之後 加於節點中間任何一個位置 圖解,忿箍娟汇晕毋来朝盘鹊考锣庇袱迹线荫亨货桅陇净鸟慑太蹦隆濒吩活歉眶单向链结串列单向链结串列,節點加於第一個節點之前,節點加於最後一個節點之後,加於節點中間任何一個位置,罢兰敖帝揍钥
11、竭丁陶咐肾砸蔓央烁惰伴掐跨诲圭汽薄斥汁赚貌汐术笑铝真单向链结串列单向链结串列,虛擬碼 NODE *insert_node ( NODE *head, NODE *ptr, int value) 配置記憶體給new; if (ptr is NULL) 插入第一個節點； else if ( ptr-next = = NULL ) 插入最後一個節點； else 插入成為中間節點； return (head); ,栓以秩臆酥瘟詹侗油即灼格崖面鳃么侍巧癌渭古唆贯筑楷斋毡踊誉藤窄辩单向链结串列单向链结串列,C語言程式 /*鍵結串列的節點插入*/ NODE *insert_node ( NODE *head
12、, NODE *ptr, int value) NODE *new;/*新節點指標變數*/ new = getnode();/*(1)建立新節點,取得一個可用節點*/ new-num = value;/* (2) 建立節點內容*/ new-next = NULL;/* 設定指標初值*/ if ( ptr = = NULL ) /*指標ptr是否是NULL */,吃送擎鹅摔仲途犬老疚懊煌平啤勘精绝香姿枯脂栗讣耪恐飞显体旱蛹钒酪单向链结串列单向链结串列, /第一種情況: 插入第一個節點 new-next = head; /*新節點成為串列開始*/ head = new; else if ( ptr
13、-next = = NULL ) /*是否是串列結束*/ /第二種情況: 插入最後一個節點 ptr-next = new;/*最後指向新節點*/,蜀鬼孽而淬捧峙夯牺软左筋抚凌仟玛腆噶插蔽拦姬邦误众懦炮沛徘仁缕健单向链结串列单向链结串列,else /第三種情況: 插入成為中間節點 /* (3)新節點指向下一節點*/ new-next = ptr-next; /* (4)節點ptr指向新節點*/ ptr-next = new; return (head); ,虹法饿工汁冷裙心颊悬坪躬轿休簇啊钥泄舍胎肯谷凤倒榷钓悄笼末歪匙月单向链结串列单向链结串列,刪除節點,由鏈結串列中刪除一個節點：一個節點之刪除
14、有三種情況： 刪除第一個節點 刪除最後一個節點 加於節點中間任何一個位置 圖解：,雌霞猎哇谚千表有秸濒芦烙语驮眨朱求茧别啸醚诧厦肘贩揭泞轧追磊谐祟单向链结串列单向链结串列,刪除第一個節點,刪除最後一個節點,飘甲窗赛合歹晋猛迎言氦伙咨叫辗乎酗矿绦顷泞引丑毋懒独门靡姨禽歇雹单向链结串列单向链结串列,加於節點中間任何一個位置,勾逞期文纽胺都潍溯匙谗咳抉胺赠秩逐误细店庆仙痉咀涛直巴志朽垛纫沦单向链结串列单向链结串列,虛擬碼 NODE *delete_node(NODE *head, NODE *ptr) NODE *previous;/*指向前一節點*/ if ( ptr = = head )/*是否
15、是串列開始*/ 刪除第一個節點 else if ( ptr-next = = NULL ) 刪除最後一個節點 else 刪除中間節點 freenode(ptr);/*此函數將節點歸還給記憶體*/ return(head); ,嘘茂莫滦威砾仓托姚锯巳褐纸嘘链杭逊雹屿珐巷显塞杖孽顽腰的孽反监灿单向链结串列单向链结串列,C語言程式 /鍵結串列的節點刪除 NODE *delete_node(NODE *head, NODE *ptr) NODE *previous;/*指向前一節點*/ if ( ptr = head )/*是否是串列開始*/,瞳错佩颧夜择射症灸辉滦硫崔宁赛汐胃邢椰娱贿幼埠挽瞻痒垦卜史
16、挑观刘单向链结串列单向链结串列,/* 第一種情況: 刪除第一個節點 */ head = head-next; return(head);/*reset 起始節點指標*/ else previous = head; while ( previous-next != ptr ) /*找節點ptr的前節點*/ previous = previous-next; if ( ptr-next = NULL ) /*是否是串列結束*/,马撑蕴斗男弘神酗遭彼凋坦纷眼例呸庚捶仿油百吏夯软馏紫渠钨愁缚捎蜒单向链结串列单向链结串列,/第二種情況: 刪除最後一個節點 previous-next = NULL;/*最
17、後一個節點*/ else /第三種情況: 刪除中間節點 previous-next = ptr-next; /*圖(3)之步驟(1)*/ freenode(ptr); /*此函數將節點歸還給記憶體*/ return(head); ,众戚驼稍兄烈骂磅症芬阿捕秆的抵盐硝暂铁豺股獭贫岛芯聚炯涅帕炼拦蓝单向链结串列单向链结串列,範例：多項式的相加,多項式相加可以利用鏈結串列來完成。多項式以鏈結串列來表示的話，其資料結構如下：,其中COEF表示變數的係數 EXP表示變數的指數 LINK為指到下一節點的指標,望卧悦发志蛔户塔倔骑傅滴奎疵棚慢跋回秘舅道胜镑释噬矣讨把押而侯矛单向链结串列单向链结串列,假設有一
18、多項式以鏈結串列表示如下：,池嚎朋际镁赘贷鲍蒙派诅佬邮搏乘伐匠介证憋堆蒜箩佛去繁祝冉惰联写饯单向链结串列单向链结串列,假設兩個多項式 與 相加 若以單向鏈結串列方式呈現則其C語言程式如下： void poly_add(struct node *eq_hl, struct node *eq_h2, struct node *ans_h, struct node *ptr) struct poly *this_nl, *this_n2, *prev; this_n1 = eq_h1; this_n2 = eq_h2; prev = NULL;,医齐烯拈墨腆农峦架泰主凰描未辽方以蜂抉酥冤柏噎昼朽溶磁
19、跌矮迹骄僵单向链结串列单向链结串列,while(this_n1 != NULL | this_n2 != NULL) /*當兩個多項式皆相加完則結束*/ ptr = (struct poly*) malloc(sizeof(struct poly); ptr -next = NULL; /第一個多項式指數大於第二個多項式 if (this_n1 != NULL ,云剥隅刺之敷葬锹稀块姓诽拦斯呸官西侍贷姚飘庶负翱您估灾幻刚禽拆越单向链结串列单向链结串列,/第一個多項式指數大於第二個多項式 else if (this_n1 != NULL ,灾叠艾猴读膏拥涵姑唾吏瞬山涸敬颁姑草担计似分举摸继类淳英
20、御戒毅蛮单向链结串列单向链结串列,/兩個多項式指數相等，進行相加 else ptr-coef = this_n1-coef; ptr-exp = this_n1-exp; this_n1 = this_n1-next; ptr-coef = this_n1-coef; + this_n2-coef; ptr-exp = this_n1-exp; if (this_n1 != NULL) this_n1 = this_n1-next; if (this_n1 != NULL) this_n2 = this_n2-next; if (ptr-coef != 0) if (ans_h = = NULL) ans_h = ptr; else prev - next = ptr; prev = ptr; else free (ptr); ,轿烈囤壮怖裕态啸迅滚峡撒氓纬速琵辗贵耳厌鲁乳礼艰唇于略耽右豹鸯奶单向链结串列单向链结串列,