軟件技術(shù)基礎(chǔ)07-多種鏈表

軟件技術(shù)基礎(chǔ)線性結(jié)構(gòu)——鏈表制作主講段景山鏈表的典型形態(tài)請用5分鐘快速閱讀教材第9頁至第12頁?；卮鹨韵聠栴}：什么是頭結(jié)點(diǎn)？教材中的單鏈表插入算法與教案中的插入算法有什么大的區(qū)別——即頭結(jié)點(diǎn)有什么用？鏈表的典型形態(tài)1.2.5鏈表的典型形態(tài)1、單鏈表如前所述2、帶頭節(jié)點(diǎn)的單鏈表頭節(jié)點(diǎn)：是一個特殊的鏈點(diǎn)，數(shù)據(jù)內(nèi)容無效鏈點(diǎn)指針指向鏈表頭/////a1...頭節(jié)點(diǎn)aian...a1an......ai頭指針鏈表的典型形態(tài)帶頭節(jié)點(diǎn)的單鏈表幾個容易混淆的概念第一個元素節(jié)點(diǎn)、頭指針、頭節(jié)點(diǎn)、鏈表頭a1ai+1anheadtailai-1......ai/////a1...aian...第一個元素節(jié)點(diǎn)頭指針頭節(jié)點(diǎn)head第一個元素節(jié)點(diǎn)、鏈表頭鏈表的典型形態(tài)帶頭節(jié)點(diǎn)單鏈表的操作特點(diǎn)插入和刪除算法不必考慮在表首進(jìn)行時，需要更改頭指針的特殊處理——把第一元素鏈點(diǎn)地址記錄在某個鏈點(diǎn)的next域內(nèi)/////a1...aian...headp＝head；p->next=p->next->next;while(location>1&&p!=NULL){…}如果location為1,表首節(jié)點(diǎn)將被刪除p為什么教材中使用**而教案中沒有使用？鏈表的定義不同教材中僅定義了鏈點(diǎn)，沒有定義鏈表結(jié)構(gòu)，一個鏈表僅由一個頭指針開始教案中還定義了鏈表結(jié)構(gòu)在結(jié)構(gòu)中除了有鏈表頭指針，還有……typedefstructlist_type{ node_type*head; node_type*tail; intlength;}list_type;headtaillengtha1a2為什么教材中使用**而教案中沒有使用？教材voidmain（）{node*head;createsl(&head);……}voidcreatesl(node**h){*h=firstnode;……}教案voidmain（）{list_typelist;create_l(&list);……}voidcreate_l(list_type*l){l->head=firstnode;……}headheadheadtaillengthheadtaillengtha1為什么教材中使用**而教案中沒有使用？本質(zhì)是一樣的：要在調(diào)用的子函數(shù)中改變頭指針的指向改變指針的指向，即改變指針變量的內(nèi)容要改變指針的內(nèi)容，必須將指針變量的地址傳入教材中是將指針的地址傳入－－指針的指針教案中將地址所在的結(jié)構(gòu)的地址傳入其它常用的鏈表形式請用1分鐘的時間快速閱讀教材第12頁至15頁，回答問題：鏈表還有哪些形式，有什么特點(diǎn)？雙向鏈表1.3雙向鏈表特點(diǎn)：每一個鏈點(diǎn)包含兩個指針，前趨指針后繼指針a1……h(huán)eadtailNa2NPanPa1NPP：priorN：next雙向鏈表1.3.1雙向鏈表的定義typedefstructdouble_link_node_type{ structdouble_link_node_type*prior; structdouble_link_node_type*next; elemtypedata;}dl_node_type;typedefstructdouble_link_list_type{ dl_node_type*head; dl_node_type*tail; intlength;}dl_list_type;鏈點(diǎn)的定義鏈表的定義雙向鏈表插入1.3.2雙向鏈表的插入操作問題描述：在第i個元素前插入新元素試試小紙片的方法能不能幫助思考ai-1NPaiNPanewNP50li55duan61yang66ma70liu61667050NULL44anewNULL66NULL505561head=55雙向鏈表插入1.3.2雙向鏈表的插入操作ai-1NPaiNP問題描述：在第i個元素前插入新元素anewNP1、anew->next=ai2、ai-1->next=anew3、anew->prior=ai-14、ai->prior=anewpanew->next=p;p->prior->next=anew;anew->prior=p->prior;p->prior=anew;僅使用p指針法一：雙向鏈表插入1.3.2雙向鏈表的插入操作ai-1ai問題描述：在第i個元素前插入新元素anewp2、anew->next=p;1、p->prior->next=anew;3、anew->prior=p->prior;4、p->prior=anew;法二：雙向鏈表插入1.3.2雙向鏈表的插入操作ai-1ai問題描述：在第i個元素前插入新元素anewp2、anew->next=p;3、anew->prior=p->prior;1、p->prior=anew;法三：在操作雙向鏈表時同樣要注意操作順序雙向鏈表插入算法實(shí)現(xiàn)（略）找到ai執(zhí)行插入操作體會插入操作有多種方式實(shí)現(xiàn)，步驟比較復(fù)雜雙向鏈表的使用靈活，可進(jìn)可退練習(xí)：前面的四個步驟的組合順序里，哪些是正確的，哪些是錯誤的？通過這個練習(xí)，加強(qiáng)鏈表指針操作的訓(xùn)練雙向鏈表刪除1.3.3雙向鏈表的刪除操作問題描述：刪除第i個元素ai-1aiai＋1ppp（1）（2）（3）（1）當(dāng)p在ai－1處時p->next->next->prior=p;p->next=p->next->next雙向鏈表刪除1.3.3雙向鏈表的刪除操作問題描述：刪除第i個元素ai-1aiai＋1ppp（1）（2）（3）（2）當(dāng)p在ai處時課堂作業(yè)請完成算法（3）當(dāng)p在ai+1處時循環(huán)鏈表1.4循環(huán)鏈表a1ai+1anheadtailai-1......ai將鏈表頭尾相接headerai+1antaila1...ai…對循環(huán)鏈表的遍歷可以從任何一個節(jié)點(diǎn)開始循環(huán)鏈表例，將兩個循環(huán)鏈表連接起來a1ai+1antail1ai-1......aib1tail2......node_type*merge_list(tail1,tail2){}tail1->next=tail2->next;tail2->next=tail1->next;???returntail2;temp=tail1->next;tail1->next=tail2->next;tail2->next=temp;擴(kuò)展：靜態(tài)鏈表“在數(shù)組內(nèi)”的鏈表指針域不是真正的指針，而是記錄后繼元素在數(shù)組內(nèi)的下標(biāo)和我們的“小紙條”很相近liduanyangmaliu2340-101234作業(yè)作業(yè)：5、在一個從小到大按序排列的雙向鏈表中，將新元