軟件技術(shù)基礎(chǔ)制作主講段景山段景山線性結(jié)構(gòu)鏈表的典型形態(tài)1.2.5鏈表的典型形態(tài)1、單鏈表如前所述2、帶頭節(jié)點的單鏈表頭節(jié)點：是一個特殊的鏈點，數(shù)據(jù)內(nèi)容無效鏈點指針指向鏈表頭/////a1...頭節(jié)點aian...a1an......ai頭指針鏈表的典型形態(tài)帶頭節(jié)點的單鏈表幾個容易混淆的概念第一個元素節(jié)點\頭指針、頭節(jié)點、鏈表頭第一個元素節(jié)點是線性表關(guān)系中第一個元素——a1鏈表頭是第一個鏈點，一般在鏈表的頭部。頭指針是指向第一個元素所在鏈點的指針頭節(jié)點：是一個特殊的鏈點，數(shù)據(jù)內(nèi)容無效，鏈點指針指向鏈表頭鏈表的典型形態(tài)帶頭節(jié)點的單鏈表幾個容易混淆的概念第一個元素節(jié)點、頭指針、頭節(jié)點、鏈表頭a1ai+1anheadtailai-1......ai/////a1...aian...第一個元素節(jié)點、鏈表頭第一個元素節(jié)點頭指針頭節(jié)點head鏈表的典型形態(tài)帶頭節(jié)點單鏈表的操作特點插入和刪除算法不必考慮在表首進行時，需要更改頭指針的特殊處理/////a1...aian...headp＝head；p->next=p->next->next;while(location>1&&p!=NULL){…}如果location為1,表首節(jié)點將被刪除p為什么教材中使用**而教案中沒有使用？教材中僅定義了鏈點，沒有定義鏈表結(jié)構(gòu)程序中調(diào)用的上下文不同typedef

structlist_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ì)是一樣的：要在函數(shù)調(diào)用中改變頭指針的指向改變指針的指向，即改變指針變量的內(nèi)容要改變指針的內(nèi)容，必須將指針變量的地址傳入教材中是將指針的地址傳入－－指針的指針教案中將地址所在的結(jié)構(gòu)的地址傳入雙向鏈表1.3雙向鏈表特點：每一個鏈點包含兩個指針，前趨指針后繼指針a1……h(huán)eadtailNa2NPanPa1NPP：priorN：next雙向鏈表1.3.1雙向鏈表的定義typedef

structdouble_link_node_type{

structdouble_link_node_type*prior;

structdouble_link_node_type*next;

elemtypedata;}dl_node_type;typedef

structdouble_link_list_type{ dl_node_type*head; dl_node_type*tail;

intlength;}dl_list_type;鏈點的定義鏈表的定義雙向鏈表插入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個元素前插入新元素anewpp2、anew->next=p;3、anew->prior=p->prior;1、p->prior=anew;法三：在操作雙向鏈表時同樣要注意操作順序雙向鏈表插入算法實現(xiàn)（略）找到ai執(zhí)行插入操作體會插入操作有多種方式實現(xiàn)，步驟比較復(fù)雜雙向鏈表的使用靈活，可進可退思考：前面的四個步驟的組合順序里，哪些是正確的，哪些是錯誤的？雙向鏈表刪除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é)點開始上機練習題例１、讀入一組數(shù)建立鏈表，以負數(shù)作為輸入結(jié)束算法實現(xiàn)分析（１）如何讀入一組數(shù)并以負數(shù)為結(jié)束建立框架：main(){ x＝0;初始化

while(x>=0){ read(&x)；

插入鏈表； }}read(int*x){

scanf(“data%d:“，x);}上機練習題（２）如何建立鏈表——新的元素以怎樣的方式插入鏈表？每次插在表頭或者每次插在表尾？決定每次插在表尾！new_node->next=list.tail->next;list.tail->next=new_node;（3）邊界問題：第一個節(jié)點插入時list.header=new_node;list.tail=new_node;上機練習題list_type*create_list(){}初始化；while(x>=0){}read(&x);生成新元素插入新元素returnlist;上機練習題list_type*create_list(){list_typelist;list->length=0;list->header=NULL;list->tail=NULL;node_type*new_node;intx;x=0;while(x>=0){new_node=(node_type*)malloc(size_of(structnode_type));new_node->data=x;假設(shè)elemtype

就是整數(shù)類型new_node->next=NULL;生成新鏈點if(list.length<=0){

list.header=new_node;

list.tail=new_node;}else{ new_node->next=list.tail->next;

list.tail->next=new_node;}list.legth++;read(x);}return&list;}上機練習題例2、檢查一個（單向）鏈表，刪除其中數(shù)據(jù)大于100的元素算法實現(xiàn)分析（1）逐個檢查鏈表的算法框架while(current!=NULL){ ...... current=current->next;}ai+1ai-1......aicurrent上機練習題(2)刪除大于100的鏈點if(current->data>100){

刪除該鏈點}必須找到current的前趨鏈點才能刪除ai+1ai-1......aicurrentlastlast->next=current->next;free(current);current=last->next;刪除不刪除last=current;current=current->next;上機練習題(3)邊界：第一個元素需要刪除時if(last=

=NULL){ list->header=current->next; free(current); current=list->header;}ai+1a1...aicurrentlast上機練習題del_over100(list_type*list){}初始化while(current!=NULL){ if(current->data>100){

刪除current; } else{

走向下一個鏈點；

}}voiddel_over100(list_type*list){last=NULL;current=list->header;if(last==NULL){ list->header=current->next; free(current); current=list->header;}else{ last->next=current->next; free(current); current=last->next;}else{ last=current; current=current->next;}while(current!=NULL){

if(current->data>100){}}//while結(jié)束}體會last指針的作用思考 如果是雙向鏈表還是否需要last指針？上機練習題例3、將一個單向鏈表反向連接算法分析（1）逐個進行的基本框架（2）反向操作方法一：header1header2目標上機練習題a1方法二、直接在原鏈表的基礎(chǔ)上操作a2a3a4a1a2a3a4ai-2ai-1aiai+1ai+2currentcontinuelastcurrent->next=lastlast=currentcurrent＝continuecontinue＝continue->next考慮首部的初始化以及尾部的處