軟件技術基礎線性結構——鏈表制作主講段景山鏈表的典型形態(tài)請用5分鐘快速閱讀教材第9頁至第12頁。回答以下問題：什么是頭結點？教材中的單鏈表插入算法與教案中的插入算法有什么大的區(qū)別——即頭結點有什么用？鏈表的典型形態(tài)1.2.5鏈表的典型形態(tài)1、單鏈表如前所述2、帶頭節(jié)點的單鏈表頭節(jié)點：是一個特殊的鏈點，數據內容無效鏈點指針指向鏈表頭/////a1...頭節(jié)點aian...a1an......ai頭指針鏈表的典型形態(tài)帶頭節(jié)點的單鏈表幾個容易混淆的概念第一個元素節(jié)點、頭指針、頭節(jié)點、鏈表頭a1ai+1anheadtailai-1......ai/////a1...aian...第一個元素節(jié)點頭指針頭節(jié)點head第一個元素節(jié)點、鏈表頭鏈表的典型形態(tài)帶頭節(jié)點單鏈表的操作特點插入和刪除算法不必考慮在表首進行時，需要更改頭指針的特殊處理——把第一元素鏈點地址記錄在某個鏈點的next域內/////a1...aian...headp＝head；p->next=p->next->next;while(location>1&&p!=NULL){…}如果location為1,表首節(jié)點將被刪除p為什么教材中使用**而教案中沒有使用？鏈表的定義不同教材中僅定義了鏈點，沒有定義鏈表結構，一個鏈表僅由一個頭指針開始教案中還定義了鏈表結構在結構中除了有鏈表頭指針，還有……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為什么教材中使用**而教案中沒有使用？本質是一樣的：要在調用的子函數中改變頭指針的指向改變指針的指向，即改變指針變量的內容要改變指針的內容，必須將指針變量的地址傳入教材中是將指針的地址傳入－－指針的指針教案中將地址所在的結構的地址傳入其它常用的鏈表形式請用1分鐘的時間快速閱讀教材第12頁至15頁，回答問題：鏈表還有哪些形式，有什么特點？雙向鏈表1.3雙向鏈表特點：每一個鏈點包含兩個指針，前趨指針后繼指針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;鏈點的定義鏈表的定義雙向鏈表插入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;法三：在操作雙向鏈表時同樣要注意操作順序雙向鏈表插入算法實現（略）找到ai執(zhí)行插入操作體會插入操作有多種方式實現，步驟比較復雜雙向鏈表的使用靈活，可進可退練習：前面的四個步驟的組合順序里，哪些是正確的，哪些是錯誤的？通過這個練習，加強鏈表指針操作的訓練雙向鏈表刪除1.3.3雙向鏈表的刪除操作問題描述：刪除第i個元素ai-1aiai＋1ppp（1）（2）（3）（1）當p在ai－1處時p->next->next->prior=p;p->next=p->next->next雙向鏈表刪除1.3.3雙向鏈表的刪除操作問題描述：刪除第i個元素ai-1aiai＋1ppp（1）（2）（3）（2）當p在ai處時課堂作業(yè)請完成算法（3）當p在ai+1處時循環(huán)鏈表1.4循環(huán)鏈表a1ai+1anheadtailai-1......ai將鏈表頭尾相接headerai+1antaila1...ai…對循環(huán)鏈表的遍歷可以從任何一個節(jié)點開始循環(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;擴展：靜態(tài)鏈表“在數組內”的鏈表指針域不是真正的指針，而是記錄后繼元素在數組內的下標和我們的“小紙條”很相近liduanyangmaliu2340-101234作業(yè)作業(yè)：5、在一個從小到大按序排列的雙向鏈表中，將新元