軟件技術(shù)與基礎(chǔ)課件6

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

structlist_type{ node_type*head; node_type*tail;

intlength;}list_type;headtaillengtha1a2為什么教材中使用**而教案中沒(méi)有使用？教材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為什么教材中使用**而教案中沒(méi)有使用？本質(zhì)是一樣的：要在函數(shù)調(diào)用中改變頭指針的指向改變指針的指向，即改變指針變量的內(nèi)容要改變指針的內(nèi)容，必須將指針變量的地址傳入教材中是將指針的地址傳入－－指針的指針教案中將地址所在的結(jié)構(gòu)的地址傳入雙向鏈表1.3雙向鏈表特點(diǎn)：每一個(gè)鏈點(diǎn)包含兩個(gè)指針，前趨指針后繼指針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;鏈點(diǎn)的定義鏈表的定義雙向鏈表插入1.3.2雙向鏈表的插入操作ai-1NPaiNP問(wèn)題描述：在第i個(gè)元素前插入新元素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指針?lè)ㄒ唬弘p向鏈表插入1.3.2雙向鏈表的插入操作ai-1ai問(wèn)題描述：在第i個(gè)元素前插入新元素anewp2、anew->next=p;1、p->prior->next=anew;3、anew->prior=p->prior;4、p->prior=anew;法二：雙向鏈表插入1.3.2雙向鏈表的插入操作ai-1ai問(wèn)題描述：在第i個(gè)元素前插入新元素anewpp2、anew->next=p;3、anew->prior=p->prior;1、p->prior=anew;法三：在操作雙向鏈表時(shí)同樣要注意操作順序雙向鏈表插入算法實(shí)現(xiàn)（略）找到ai執(zhí)行插入操作體會(huì)插入操作有多種方式實(shí)現(xiàn)，步驟比較復(fù)雜雙向鏈表的使用靈活，可進(jìn)可退思考：前面的四個(gè)步驟的組合順序里，哪些是正確的，哪些是錯(cuò)誤的？雙向鏈表刪除1.3.3雙向鏈表的刪除操作問(wèn)題描述：刪除第i個(gè)元素ai-1aiai＋1ppp（1）（2）（3）（1）當(dāng)p在ai－1處時(shí)p->next->next->prior=p;p->next=p->next->next雙向鏈表刪除1.3.3雙向鏈表的刪除操作問(wèn)題描述：刪除第i個(gè)元素ai-1aiai＋1ppp（1）（2）（3）（2）當(dāng)p在ai處時(shí)課堂作業(yè)請(qǐng)完成算法（3）當(dāng)p在ai+1處時(shí)循環(huán)鏈表1.4循環(huán)鏈表a1ai+1anheadtailai-1......ai將鏈表頭尾相接headerai+1antaila1...ai…對(duì)循環(huán)鏈表的遍歷可以從任何一個(gè)節(jié)點(diǎn)開(kāi)始上機(jī)練習(xí)題例１、讀入一組數(shù)建立鏈表，以負(fù)數(shù)作為輸入結(jié)束算法實(shí)現(xiàn)分析（１）如何讀入一組數(shù)并以負(fù)數(shù)為結(jié)束建立框架：main(){ x＝0;初始化

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

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

scanf(“data%d:“，x);}上機(jī)練習(xí)題（２）如何建立鏈表——新的元素以怎樣的方式插入鏈表？每次插在表頭或者每次插在表尾？決定每次插在表尾！new_node->next=list.tail->next;list.tail->next=new_node;（3）邊界問(wèn)題：第一個(gè)節(jié)點(diǎn)插入時(shí)list.header=new_node;list.tail=new_node;上機(jī)練習(xí)題list_type*create_list(){}初始化；while(x>=0){}read(&x);生成新元素插入新元素returnlist;上機(jī)練習(xí)題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;生成新鏈點(diǎn)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;}上機(jī)練習(xí)題例2、檢查一個(gè)（單向）鏈表，刪除其中數(shù)據(jù)大于100的元素算法實(shí)現(xiàn)分析（1）逐個(gè)檢查鏈表的算法框架while(current!=NULL){ ...... current=current->next;}ai+1ai-1......aicurrent上機(jī)練習(xí)題(2)刪除大于100的鏈點(diǎn)if(current->data>100){

刪除該鏈點(diǎn)}必須找到current的前趨鏈點(diǎn)才能刪除ai+1ai-1......aicurrentlastlast->next=current->next;free(current);current=last->next;刪除不刪除last=current;current=current->next;上機(jī)練習(xí)題(3)邊界：第一個(gè)元素需要?jiǎng)h除時(shí)if(last=

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

刪除current; } else{

走向下一個(gè)鏈點(diǎn)；

}}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é)束}體會(huì)last指針的作用思考 如果是雙向鏈表還是否需要last指針？上機(jī)練習(xí)題例3、將一個(gè)單向鏈表反向連接算法分析（1）逐個(gè)進(jìn)行的基本框架（2）反向操作方法一：header1header2目標(biāo)上機(jī)練習(xí)題a1方法二、直接在原鏈表的基礎(chǔ)上操作a2a3a4a1a2a3a4ai-2ai-1aiai+1ai+2currentcontinuelastcurrent->next=lastlast=currentcurrent＝continuecontinue＝continue->next考慮首部的初始化以及尾部的處