數(shù)據(jù)結(jié)構(gòu)-C語言-線性表

線表第二章數(shù)據(jù)結(jié)構(gòu)（C語言）第二章線表第三章棧與隊(duì)列第四章串,數(shù)組與廣義表 若結(jié)構(gòu)是非空有限集,則有且僅有一個(gè)開始結(jié)點(diǎn)與一個(gè)終端結(jié)點(diǎn),并且所有結(jié)點(diǎn)都最多只有一個(gè)直接前趨與一個(gè)直接后繼。可表示為:（a一,a二,……,an）線結(jié)構(gòu)地定義:近三周上課內(nèi)容線結(jié)構(gòu)（邏輯,存儲(chǔ)與運(yùn)算）線結(jié)構(gòu)地特點(diǎn):①只有一個(gè)首結(jié)點(diǎn)與尾結(jié)點(diǎn);②除首尾結(jié)點(diǎn)外,其它結(jié)點(diǎn)只有一個(gè)直接前驅(qū)與一個(gè)直接后繼。線結(jié)構(gòu)表達(dá)式:（a一,a二,……,an）線結(jié)構(gòu)包括線表,堆棧,隊(duì)列,字符串,數(shù)組等等,其,最典型,最常用地是線表簡言之,線結(jié)構(gòu)反映結(jié)點(diǎn)間地邏輯關(guān)系是一對一地近三周上課內(nèi)容了解線結(jié)構(gòu)地特點(diǎn)掌握順序表地定義,查找,插入與刪除掌握鏈表地定義,創(chuàng)建,查找,插入與刪除能夠從時(shí)間與空間復(fù)雜度地角度比較兩種存儲(chǔ)結(jié)構(gòu)地不同特點(diǎn)及其適用場合零一OPTION零二OPTION零三OPTION零四OPTIONtarget目地目錄導(dǎo)航二.一二.二二.三二.四二.五二.六二.七二.八線表地定義與特點(diǎn)案例引入線地類型定義線表地順序表示與實(shí)現(xiàn)線表地鏈?zhǔn)奖硎九c實(shí)現(xiàn)順序表與鏈表地比較線表地應(yīng)用案例分析與實(shí)現(xiàn)Contents（a一,a二,…ai-一,ai,ai＋一,…,an）線表地定義:用數(shù)據(jù)元素地有限序列表示n=零時(shí)稱為數(shù)據(jù)元素線起點(diǎn)ai地直接前趨ai地直接后繼空表線終點(diǎn)線表地定義與特點(diǎn)下標(biāo),是元素地序號,表示元素在表地位置n為元素總個(gè)數(shù),即表長分析二六個(gè)英文字母組成地英文表（A,B,C,D,……,Z）例二分析學(xué)生情況登記表數(shù)據(jù)元素都是記錄;元素間關(guān)系是線數(shù)據(jù)元素都是字母;元素間關(guān)系是線同一線表地元素必定具有相同特學(xué)號姓名別年齡班級零四一八一零二零五于春梅女一八零四級計(jì)算機(jī)一班零四一八一零二六零何仕鵬男二零零四級計(jì)算機(jī)二班零四一八一零二八四王爽女一九零四級計(jì)算機(jī)三班零四一八一零三六零王亞武男一八零四級計(jì)算機(jī)四班:::::目錄導(dǎo)航二.一二.二二.三二.四二.五二.六二.七二.八線表地定義與特點(diǎn)案例引入線地類型定義線表地順序表示與實(shí)現(xiàn)線表地鏈?zhǔn)奖硎九c實(shí)現(xiàn)順序表與鏈表地比較線表地應(yīng)用案例分析與實(shí)現(xiàn)Contents二.二案例引入案例二.一:一元多項(xiàng)式地運(yùn)算案例二.二:稀疏多項(xiàng)式地運(yùn)算案例二.三:表達(dá)式求值案例二.四:舞伴問題指數(shù)（下標(biāo)i）零一二三四系數(shù)p[i]一零五-四三二案例二.一:一元多項(xiàng)式地運(yùn)算Pn(x)

=

p零

+

p一x

+

p二x二

+

…

+

pnxn線表P

=

(p零,p一,p二,…,pn)P(x)

=

一零

+

五x

-

四x二

+

三x三

+

二x四數(shù)組表示（每一項(xiàng)地指數(shù)i隱含在其系數(shù)pi地序號）Rn(x)

=

Pn(x)

+

Qm(x)線表R

=

(p零

+

q零,p一

+

q一,p二

+

q二,…,pm

+

qm,pm+一,…,pn)稀疏多項(xiàng)式S(x)

=

一

+

三x一零零零零

+

二x二零零零零案例二.一:一元多項(xiàng)式地運(yùn)算下標(biāo)i零一二三下標(biāo)i零一二系數(shù)a[i]七三九五系數(shù)b[i]八二二-九指數(shù)零一八一七指數(shù)一七八多項(xiàng)式非零項(xiàng)地?cái)?shù)組表示線表P

=((p一,e一),(p二,e二),…,(pm,em))案例二.二:稀疏多項(xiàng)式地運(yùn)算（a）A(x)

=

七

+

三x

+

九x八

+

五x一七（b）(x)

=

八x

+

二二x七

?

九x八創(chuàng)建一個(gè)新數(shù)組c案例二.二:稀疏多項(xiàng)式地運(yùn)算分別從頭遍歷比較a與b地每一項(xiàng)指數(shù)相同,對應(yīng)系數(shù)相加,若其與不為零,則在c增加一個(gè)新項(xiàng)。指數(shù)不相同,則將指數(shù)較小地項(xiàng)復(fù)制到c。一個(gè)多項(xiàng)式已遍歷完畢時(shí),將另一個(gè)剩余項(xiàng)依次復(fù)制到c即可A一七(x)=七+三x+九x八+五x一七B八(x)=八x+二二x七-九x八-一七零三一九八五一七-一八一二二七-九八ABpapb順序存儲(chǔ)結(jié)構(gòu)存在問題存儲(chǔ)空間分配不靈活運(yùn)算地空間復(fù)雜度高鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)案例二.二:稀疏多項(xiàng)式地運(yùn)算多項(xiàng)式相加A一七(x)=七+三x+九x八+五x一七B八(x)=八x+二二x七-九x八-一七零三一九八五一七-一八一二二七-九八ABpapbA一七(x)=七+三x+九x八+五x一七B八(x)=八x+二二x七-九x八-一七零一一一九八五一七-一八一二二七-九八ABpapb多項(xiàng)式相加A一七(x)=七+三x+九x八+五x一七B八(x)=八x+二二x七-九x八-一七零一一一九八五一七-一八一二二七-九八ABpapb多項(xiàng)式相加A一七(x)=七+三x+九x八+五x一七B八(x)=八x+二二x七-九x八-一七零一一一九八五一七-一八一二二七-九八ABpapb多項(xiàng)式相加（一）查找（二）插入（三）刪除（四）修改（五）排序（六）計(jì)數(shù)案例二.三:圖書信息管理系統(tǒng)圖書順序表圖書鏈表案例二.三:圖書信息管理系統(tǒng)線表數(shù)據(jù)元素地類型可以為簡單類型,也可以為復(fù)雜類型。許多實(shí)際應(yīng)用問題所涉地基本操作有很大相似,不應(yīng)為每個(gè)具體應(yīng)用單獨(dú)編寫一個(gè)程序。從具體應(yīng)用抽象出地邏輯結(jié)構(gòu)與基本操作（抽象數(shù)據(jù)類型）,然后實(shí)現(xiàn)其存儲(chǔ)結(jié)構(gòu)與基本操作?？偨Y(jié)零三零一零二目錄導(dǎo)航二.一二.二二.三二.四二.五二.六二.七二.八線表地定義與特點(diǎn)案例引入線地類型定義線表地順序表示與實(shí)現(xiàn)線表地鏈?zhǔn)奖硎九c實(shí)現(xiàn)順序表與鏈表地比較線表地應(yīng)用案例分析與實(shí)現(xiàn)Contents線表地重要基本操作線表地類型定義基本操作初始化查找插入取值刪除一五四三二目錄導(dǎo)航二.一二.二二.三二.四二.五二.六二.七二.八線表地定義與特點(diǎn)案例引入線地類型定義線表地順序表示與實(shí)現(xiàn)線表地鏈?zhǔn)奖硎九c實(shí)現(xiàn)順序表與鏈表地比較線表地應(yīng)用案例分析與實(shí)現(xiàn)Contents線表地順序表示又稱為順序存儲(chǔ)結(jié)構(gòu)或順序映像。線表地順序表示與實(shí)現(xiàn)零一零二順序存儲(chǔ)定義把邏輯上相鄰地?cái)?shù)據(jù)元素存儲(chǔ)在物理上相鄰地存儲(chǔ)單元地存儲(chǔ)結(jié)構(gòu)。簡言之,邏輯上相鄰,物理上也相鄰順序存儲(chǔ)方法用一組地址連續(xù)地存儲(chǔ)單元依次存儲(chǔ)線表地元素,可通過數(shù)組V[n]來實(shí)現(xiàn)。元素n……..元素i……..元素二元素一LoLo+mLo+(i-一)*mLo+（n-一)*m存儲(chǔ)地址存儲(chǔ)內(nèi)容Loc(元素i)=Lo+（i-一)*m線表地順序表示與實(shí)現(xiàn)順序存儲(chǔ)#defineMAXSIZE一零零//最大長度typedefstruct{ ElemType*elem;//指向數(shù)據(jù)元素地基地址 intlength;//線表地當(dāng)前長度}SqList;順序表地類型定義#defineMAXSIZE一零零零零 //圖書表可能達(dá)到地最大長度typedefstruct //圖書信息定義{charno[二零]; //圖書ISBNcharname[五零]; //圖書名字floatprice; //圖書價(jià)格}Book;typedefstruct{Book*elem; //存儲(chǔ)空間地基地址intlength; //圖書表當(dāng)前圖書個(gè)數(shù)}SqList; //圖書表地順序存儲(chǔ)結(jié)構(gòu)類型為SqList圖書表地順序存儲(chǔ)結(jié)構(gòu)類型定義補(bǔ)充:C語言地動(dòng)態(tài)分配函數(shù)（<stdlib.h>）malloc(m)開辟m字節(jié)長度地地址空間,并返回這段空間地首地址sizeof(x)計(jì)算變量x地長度。free(p)釋放指針p所指變量地存儲(chǔ)空間,即徹底刪除一個(gè)變量new類型名T（初值列表）功能:申請用于存放T類型對象地內(nèi)存空間,并依初值列表賦以初值結(jié)果值:成功:T類型地指針,指向新分配地內(nèi)存失敗:零（NULL）int*p一=newint;

或int*p一=newint(一零);delete指針P功能:釋放指針P所指向地內(nèi)存。P需要是new操作地返回值deletep一;補(bǔ)充:C++地動(dòng)態(tài)存儲(chǔ)分配函數(shù)調(diào)用時(shí)傳送給形參表地實(shí)參需要與形參在類型,個(gè)數(shù),順序上保持一致補(bǔ)充:C++地參數(shù)傳遞參數(shù)傳遞有兩種方式傳值方式（參數(shù)為整型,實(shí)型,字符型等）傳地址參數(shù)為指針變量參數(shù)為引用類型參數(shù)為數(shù)組名voidmain(){ floata,b; cin>>a>>b; swap(a,b); cout<<a<<endl<<b<<endl;}#include<iostream.h>voidswap(floatm,floatn){ floattemp; temp=m; m=n; n=temp;}傳值方式把實(shí)參地值傳送給函數(shù)局部工作區(qū)相應(yīng)地副本,函數(shù)使用這個(gè)副本執(zhí)行必要地功能。函數(shù)修改地是副本地值,實(shí)參地值不變傳地址方式－－指針變量作參數(shù)voidmain(){ floata,b,*p一,*p二; cin>>a>>b; p一=&a;p二=&b; swap(p一,p二); cout<<a<<endl<<b<<endl;}#include<iostream.h>voidswap(float*m,float*n){ floatt; t=*m; *m=*n; *n=t;}形參變化影響實(shí)參傳地址方式－－指針變量作參數(shù)voidmain(){ floata,b,*p一,*p二; cin>>a>>b; p一=&a;p二=&b; swap(p一,p二); cout<<a<<endl<<b<<endl;}#include<iostream.h>voidswap(float*m,float*n){ float*t; t=m; m=n; n=t;}形參變化不影響實(shí)參？？傳地址方式－－引用類型作參數(shù)引用:它用來給一個(gè)對象提供一個(gè)替代地名字。#include<iostream.h>voidmain(){ inti=五; int&j=i; i=七; cout<<"i="<<i<<"j="<<j;}什么是引用？？？j是一個(gè)引用類型,代表i地一個(gè)替代名。i值改變時(shí),j值也跟著改變,所以會(huì)輸出。i=七j=七#include<iostream.h>voidswap(float＆m,float＆n){ floattemp; temp=m; m=n; n=temp;}傳地址方式－－引用類型作參數(shù)voidmain(){floata,b;cin>>a>>b;swap(a,b);cout<<a<<endl<<b<<endl;}傳遞引用給函數(shù)與傳遞指針地效果是一樣地,形參變化實(shí)參也發(fā)生變化。引用類型作形參,在內(nèi)存并沒有產(chǎn)生實(shí)參地副本,它直接對實(shí)參操作;而一般變量作參數(shù),形參與實(shí)參就占用不同地存儲(chǔ)單元,所以形參變量地值是實(shí)參變量地副本。因此,當(dāng)參數(shù)傳遞地?cái)?shù)據(jù)量較大時(shí),用引用比用一般變量傳遞參數(shù)地時(shí)間與空間效率都好。引用類型作形參地三點(diǎn)說明指針參數(shù)雖然也能達(dá)到與使用引用地效果,但在被調(diào)函數(shù)需要重復(fù)使用"*指針變量名"地形式行運(yùn)算,這很容易產(chǎn)生錯(cuò)誤且程序地閱讀較差;另一方面,在主調(diào)函數(shù)地調(diào)用點(diǎn)處,需要用變量地地址作為實(shí)參。一二三傳地址方式－－數(shù)組名作參數(shù)#include<iostream.h>voidsub(char);voidmain（void）{chara[一零]="hello";sub(a);cout<<a<<endl;}voidsub(charb[]){b[]="world";}傳遞地是數(shù)組地首地址對形參數(shù)組所做地任何改變都將反映到實(shí)參數(shù)組#include<iostream.h>#defineN一零intmax(inta[]);voidmain(){ inta[一零]; inti,m; for(i=零;i<N;i++) cin>>a[i]; m=max(a); cout<<"themaxnumberis:"<<m;}用數(shù)組作函數(shù)地參數(shù),求一零個(gè)整數(shù)地最大數(shù)intmax(intb[]){inti,n;n=b[零];for(i=一;i<N;i++) if(n<b[i])n=b[i];returnn;}練#include<iostream.h>#defineN一零voidsub(intb[]){ inti,j,temp,m; m=N/二; for(i=零;i<m;i++){j=N-一-i;temp=b[i]; b[i]=b[j];b[j]=temp; } return;}voidmain(){ inta[一零],i; for(i=零;i<N;i++) cin>>a[i]; sub(a); for(i=零;i<N;i++) cout<<a[i];}用數(shù)組作為函數(shù)地參數(shù),將數(shù)組n個(gè)整數(shù)按相反地順序存放,要求輸入與輸出在主函數(shù)完成線表地重要基本操作基本操作初始化查找插入取值刪除一五四三二初始化線表L（參數(shù)用引用）StatusInitList_Sq(SqList&L)//構(gòu)造一個(gè)空地順序表L{L.elem=newElemType[MAXSIZE];//為順序表分配空間if(!L.elem)exit(OVERFLOW);//存儲(chǔ)分配失敗L.length=零; //空表長度為零returnOK;}StatusInitList_Sq(SqList*L)//構(gòu)造一個(gè)空地順序表L{ L->elem=newElemType[MAXSIZE];//為順序表分配空間if(!L->elem)exit(OVERFLOW);//存儲(chǔ)分配失敗L->length=零; //空表長度為零returnOK;}初始化線表L（參數(shù)用指針）voidDestroyList(SqList&L){if(L.elem)delete[]L.elem;//釋放存儲(chǔ)空間}voidClearList(SqList&L){L.length=零;//將線表地長度置為零}補(bǔ)充:幾個(gè)簡單基本操作地算法實(shí)現(xiàn)銷毀線表L清空線表L補(bǔ)充:幾個(gè)簡單基本操作地算法實(shí)現(xiàn)intGetLength(SqListL){return(L.length);}intIsEmpty(SqListL){if(L.length==零)return一;elsereturn零;}求線表L地長度判斷線表L是否為空線表地重要基本操作基本操作初始化查找插入取值刪除一五四三二intGetElem(SqListL,inti,ElemType&e){if(i<一||i>L.length)returnERROR;//判斷i值是否合理,若不合理,返回ERRORe=L.elem[i-一];//第i-一地單元存儲(chǔ)著第i個(gè)數(shù)據(jù)returnOK;}取值（根據(jù)位置i獲取相應(yīng)位置數(shù)據(jù)元素地內(nèi)容）隨機(jī)存取獲取線表L地某個(gè)數(shù)據(jù)元素地內(nèi)容查找（根據(jù)指定數(shù)據(jù)獲取數(shù)據(jù)所在地位置）順序查找圖示二五三四五七一六四八零九零一二三四五data查找一六i二五三四五七一六四八零九i二五三四五七一六四八零九i二五三四五七一六四八零九i查找成功二五三四五七一六四八零一二三四data查找五零i二五三四五七一六四八i二五三四五七一六四八i二五三四五七一六四八i二五三四五七一六四八i查找失敗查找（根據(jù)指定數(shù)據(jù)獲取數(shù)據(jù)所在地位置）查找算法時(shí)間效率分析？？？在線表L查找值為e地?cái)?shù)據(jù)元素intLocateELem(SqListL,ElemTypee){ for(i=零;i<L.length;i++) if(L.elem[i]==e)returni+一; return零;}查找（根據(jù)指定數(shù)據(jù)獲取數(shù)據(jù)所在地位置）二五一二四七八九三六一四一二三四五六七八九二五一二四七九九八九三六一四九九插入二五一二四七八九三六一四二五一二四七八九三六一四二五一二四七八九三六一四插第四個(gè)結(jié)點(diǎn)之前,移動(dòng)六－四+一次插在第i個(gè)結(jié)點(diǎn)之前,移動(dòng)n-i+一次插入（插在第i個(gè)結(jié)點(diǎn)之前）判斷插入位置i是否合法。算法步驟零一零二零三零四零五判斷順序表地存儲(chǔ)空間是否已滿。將第n至第i位地元素依次向后移動(dòng)一個(gè)位置,空出第i個(gè)位置。將要插入地新元素e放入第i個(gè)位置。表長加一,插入成功返回OK。StatusListInsert_Sq(SqList&L,inti,ElemTypee){if(i<一||i>L.length+一)returnERROR; //i值不合法if(L.length==MAXSIZE)returnERROR;//當(dāng)前存儲(chǔ)空間已滿for(j=L.length-一;j>=i-一;j--)L.elem[j+一]=L.elem[j];//插入位置及之后地元素后移L.elem[i-一]=e;//將新元素e放入第i個(gè)位置++L.length; //表長增一returnOK;}算法描述在線表L第i個(gè)數(shù)據(jù)元素之前插入數(shù)據(jù)元素e若插入在尾結(jié)點(diǎn)之后,則根本無需移動(dòng)（特別快）;若元素全部后移（特別慢）;若要考慮在各種位置插入（n+一種可能）地均移動(dòng)次數(shù),該如何計(jì)算？算法時(shí)間主要耗費(fèi)在移動(dòng)元素地操作上算法分析二五一二四七八九三六一四一二三四五六七八九二五一二四七三六一四二五一二四七三六一四二五一二四七三六一四刪除刪除（刪除第i個(gè)結(jié)點(diǎn)）刪除第四個(gè)結(jié)點(diǎn),移動(dòng)六－四次刪除第i個(gè)結(jié)點(diǎn),移動(dòng)n-i次算法步驟（一）判斷刪除位置i是否合法（合法值為一≤i≤n）。（二）將欲刪除地元素保留在e。（三）將第i+一至第n位地元素依次向前移動(dòng)一個(gè)位置。（四）表長減一,刪除成功返回OK。StatusListDelete_Sq(SqList&L,inti){if((i<一)||(i>L.length))returnERROR; //i值不合法for(j=i;j<=L.length-一;j++)L.elem[j-一]=L.elem[j];//被刪除元素之后地元素前移--L.length; //表長減一returnOK;}算法描述將線表L第i個(gè)數(shù)據(jù)元素刪除若刪除尾結(jié)點(diǎn),則根本無需移動(dòng)（特別快）;若刪除首結(jié)點(diǎn),則表n-一個(gè)元素全部前移（特別慢）;若要考慮在各種位置刪除（n種可能）地均移動(dòng)次數(shù),該如何計(jì)算？算法時(shí)間主要耗費(fèi)在移動(dòng)元素地操作上算法分析一二三顯然,順序表地空間復(fù)雜度S(n)=O(一)（沒有占用輔助空間）查找,插入,刪除算法地均時(shí)間復(fù)雜度為:O(n)順序表（順序存儲(chǔ)結(jié)構(gòu)）地特點(diǎn)這種存取元素地方法被稱為隨機(jī)存取法利用數(shù)據(jù)元素地存儲(chǔ)位置表示線表相鄰數(shù)據(jù)元素之間地前后關(guān)系,即線表地邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)一致在訪問線表時(shí),可以快速地計(jì)算出任何一個(gè)數(shù)據(jù)元素地存儲(chǔ)地址。因此可以粗略地認(rèn)為,訪問每個(gè)元素所花時(shí)間相等（一）（二）順序表地優(yōu)缺點(diǎn)鏈表為克服這一缺點(diǎn)存儲(chǔ)密度大（結(jié)點(diǎn)本身所占存儲(chǔ)量/結(jié)點(diǎn)結(jié)構(gòu)所占存

儲(chǔ)量）可以隨機(jī)存取表任一元素優(yōu)點(diǎn):在插入,刪除某一元素時(shí),需要移動(dòng)大量元素浪費(fèi)存儲(chǔ)空間屬于靜態(tài)存儲(chǔ)形式,數(shù)據(jù)元素地個(gè)數(shù)不能自由擴(kuò)充缺點(diǎn):目錄導(dǎo)航二.一二.二二.三二.四二.五二.六二.七二.八線表地定義與特點(diǎn)案例引入線地類型定義線表地順序表示與實(shí)現(xiàn)線表地鏈?zhǔn)奖硎九c實(shí)現(xiàn)順序表與鏈表地比較線表地應(yīng)用案例分析與實(shí)現(xiàn)Contents線表地鏈?zhǔn)奖硎九c實(shí)現(xiàn)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)結(jié)點(diǎn)在存儲(chǔ)器地位置是任意地,即邏輯上相鄰地?cái)?shù)據(jù)元素在物理上不一定相鄰線表地鏈?zhǔn)奖硎居址Q為非順序映像或鏈?zhǔn)接诚瘛Ｈ绾螌?shí)現(xiàn)？通過指針來實(shí)現(xiàn)單鏈表地存儲(chǔ)映像free(a)可利用存儲(chǔ)空間a零a二a一a三

freefirst(b)經(jīng)過一段運(yùn)行后地單鏈表結(jié)構(gòu)線表地鏈?zhǔn)奖硎九c實(shí)現(xiàn)例畫出二六個(gè)英文字母表地鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu):邏輯結(jié)構(gòu):（a,b,…,y,z）aheadb/\z……各結(jié)點(diǎn)由兩個(gè)域組成:數(shù)據(jù)域:存儲(chǔ)元素?cái)?shù)值數(shù)據(jù)指針域:存儲(chǔ)直接后繼結(jié)點(diǎn)地存儲(chǔ)位置指針數(shù)據(jù)例畫出二六個(gè)英文字母表地鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)與鏈?zhǔn)酱鎯?chǔ)有關(guān)地術(shù)語一,結(jié)點(diǎn):數(shù)據(jù)元素地存儲(chǔ)映像。由數(shù)據(jù)域與指針域兩部分組成二,鏈表:n個(gè)結(jié)點(diǎn)由指針鏈組成一個(gè)鏈表。它是線表地鏈?zhǔn)酱鎯?chǔ)映像,稱為線表地鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)四三二一六七八五a一heada二an……h(huán)ead循環(huán)鏈表示意圖:三,單鏈表,雙鏈表,循環(huán)鏈表:結(jié)點(diǎn)只有一個(gè)指針域地鏈表,稱為單鏈表或線鏈表有兩個(gè)指針域地鏈表,稱為雙鏈表首尾相接地鏈表稱為循環(huán)鏈表與鏈?zhǔn)酱鎯?chǔ)有關(guān)地術(shù)語四,頭指針,頭結(jié)點(diǎn)與首元結(jié)點(diǎn)頭指針是指向鏈表第一個(gè)結(jié)點(diǎn)地指針首元結(jié)點(diǎn)是指鏈表存儲(chǔ)第一個(gè)數(shù)據(jù)元素a一地結(jié)點(diǎn)頭結(jié)點(diǎn)是在鏈表地首元結(jié)點(diǎn)之前附設(shè)地一個(gè)結(jié)點(diǎn);數(shù)據(jù)域內(nèi)只放空表標(biāo)志與表長等信息與鏈?zhǔn)酱鎯?chǔ)有關(guān)地術(shù)語頭指針頭結(jié)點(diǎn)首元結(jié)點(diǎn)a一heada二…infoan^上例鏈表地邏輯結(jié)構(gòu)示意圖有以下兩種形式:①ZHAOQIANLISUNZHOUWUZHENG/\WANGH②ZHAOQIANLISUNZHOUWUZHENG/\WANGH區(qū)別:①無頭結(jié)點(diǎn)②有頭結(jié)點(diǎn)與鏈?zhǔn)酱鎯?chǔ)有關(guān)地術(shù)語討論一.如何表示空表？有頭結(jié)點(diǎn)時(shí),當(dāng)頭結(jié)點(diǎn)地指針域?yàn)榭諘r(shí)表示空表非空表 空表零ana零headhead^表頭結(jié)點(diǎn)第一個(gè)結(jié)點(diǎn)與鏈?zhǔn)酱鎯?chǔ)有關(guān)地術(shù)語討論二.在鏈表設(shè)置頭結(jié)點(diǎn)有什么好處？⒈便于首元結(jié)點(diǎn)地處理首元結(jié)點(diǎn)地地址保存在頭結(jié)點(diǎn)地指針域,所以在鏈表地第一個(gè)位置上地操作與其它位置一致,無須行特殊處理;⒉便于空表與非空表地統(tǒng)一處理無論鏈表是否為空,頭指針都是指向頭結(jié)點(diǎn)地非空指針,因此空表與非空表地處理也就統(tǒng)一了。與鏈?zhǔn)酱鎯?chǔ)有關(guān)地術(shù)語討論三.頭結(jié)點(diǎn)地?cái)?shù)據(jù)域內(nèi)裝地是什么？頭結(jié)點(diǎn)地?cái)?shù)據(jù)域可以為空,也可存放線表長度等附加信息,但此結(jié)點(diǎn)不能計(jì)入鏈表長度值。頭結(jié)點(diǎn)地?cái)?shù)據(jù)域H與鏈?zhǔn)酱鎯?chǔ)有關(guān)地術(shù)語結(jié)點(diǎn)在存儲(chǔ)器地位置是任意地,即邏輯上相鄰地?cái)?shù)據(jù)元素在物理上不一定相鄰鏈表（鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)）地特點(diǎn)訪問時(shí)只能通過頭指針入鏈表,并通過每個(gè)結(jié)點(diǎn)地指針域向后掃描其余結(jié)點(diǎn),所以尋找第一個(gè)結(jié)點(diǎn)與最后一個(gè)結(jié)點(diǎn)所花費(fèi)地時(shí)間不等這種存取元素地方法被稱為順序存取法零一OPTION零二OPTION鏈表地優(yōu)缺點(diǎn)優(yōu)點(diǎn)數(shù)據(jù)元素地個(gè)數(shù)可以自由擴(kuò)充插入,刪除等操作不必移動(dòng)數(shù)據(jù),只需修改鏈接指針,修改效率較高缺點(diǎn)存儲(chǔ)密度小存取效率不高,需要采用順序存取,即存取數(shù)據(jù)元素時(shí),只能按鏈表地順序行訪問（順藤摸瓜）鏈表地優(yōu)缺點(diǎn)練一.鏈表地每個(gè)結(jié)點(diǎn)都恰好包含一個(gè)指針。二.順序表結(jié)構(gòu)適宜于行順序存取,而鏈表適宜于行隨機(jī)存取。三.順序存儲(chǔ)方式地優(yōu)點(diǎn)是存儲(chǔ)密度大,且插入,刪除運(yùn)算效率高。四.線表若采用鏈?zhǔn)酱鎯?chǔ)時(shí),結(jié)點(diǎn)之間與結(jié)點(diǎn)內(nèi)部地存儲(chǔ)空間都是可以不連續(xù)地。五.線表地每個(gè)結(jié)點(diǎn)只能是一個(gè)簡單類型,而鏈表地每個(gè)結(jié)點(diǎn)可以是一個(gè)復(fù)雜類型×單鏈表地定義與實(shí)現(xiàn)非空表空表單鏈表是由表頭唯一確定,因此單鏈表可以用頭指針地

名字來命名若頭指針名是L,則把鏈表稱為表LtypedefstructLnode{ElemTypedata;//數(shù)據(jù)域structLNode*next;//指針域}LNode,*LinkList;//*LinkList為Lnode類型地指針單鏈表地存儲(chǔ)結(jié)構(gòu)定義LNode*pLinkListpLNode*p注意區(qū)分指針變量與結(jié)點(diǎn)變量兩個(gè)不同地概念若p->data=ai,則p->next->data=ai+一單鏈表地存儲(chǔ)結(jié)構(gòu)定義指針變量p:表示結(jié)點(diǎn)地址結(jié)點(diǎn)變量*p:表示一個(gè)結(jié)點(diǎn)單鏈表基本操作地實(shí)現(xiàn)初始化零一零二零三零四零五取值查找插入刪除基本操作地實(shí)現(xiàn)算法步驟算法描述初始化(構(gòu)造一個(gè)空表)StatusInitList_L(LinkList&L){L=newLNode; L->next=NULL;returnOK;}（一）生成新結(jié)點(diǎn)作頭結(jié)點(diǎn),用頭指針L指向頭結(jié)點(diǎn)。（二）頭結(jié)點(diǎn)地指針域置空。StatusDestroyList_L(LinkList&L){LinkListp;while(L){p=L;L=L->next;deletep;}returnOK;}補(bǔ)充:幾個(gè)簡單基本操作地算法實(shí)現(xiàn)銷毀StatusClearList(LinkList&L){//將L重置為空表LinkListp,q;p=L->next;//p指向第一個(gè)結(jié)點(diǎn)while(p)//沒到表尾{q=p->next;deletep;p=q;}L->next=NULL;//頭結(jié)點(diǎn)指針域?yàn)榭誶eturnOK;}補(bǔ)充:幾個(gè)簡單基本操作地算法實(shí)現(xiàn)清空pLa一a二…...^pi零一p二pn==NULLan求表長p=L->next;i=零;while(p){i++;p=p->next;}補(bǔ)充:幾個(gè)簡單基本操作地算法實(shí)現(xiàn)"數(shù)"結(jié)點(diǎn):指針p依次指向各個(gè)結(jié)點(diǎn)從第一個(gè)元素開始"數(shù)"一直"數(shù)"到最后一個(gè)結(jié)點(diǎn)求表長intListLength_L(LinkListL){//返回L數(shù)據(jù)元素個(gè)數(shù)LinkListp;p=L->next;//p指向第一個(gè)結(jié)點(diǎn)i=零;while(p){//遍歷單鏈表,統(tǒng)計(jì)結(jié)點(diǎn)數(shù)i++;p=p->next;}returni;}"數(shù)"結(jié)點(diǎn):指針p依次指向各個(gè)結(jié)點(diǎn)從第一個(gè)元素開始"數(shù)"一直"數(shù)"到最后一個(gè)結(jié)點(diǎn)補(bǔ)充:幾個(gè)簡單基本操作地算法實(shí)現(xiàn)判斷表是否為空intListEmpty(LinkListL){ //若L為空表,則返回一,否則返回零if(L->next)//非空return零;elsereturn一;}補(bǔ)充:幾個(gè)簡單基本操作地算法實(shí)現(xiàn)線表地重要基本操作初始化零一零二零三零四零五取值查找插入刪除基本操作地實(shí)現(xiàn)思考:順序表里如何找到第i個(gè)元素？鏈表地查找:要從鏈表地頭指針出發(fā),順著鏈域next逐個(gè)結(jié)點(diǎn)往下搜索,直至搜索到第i個(gè)結(jié)點(diǎn)為止。因此,鏈表不是隨機(jī)存取結(jié)構(gòu)取值（根據(jù)位置i獲取相應(yīng)位置數(shù)據(jù)元素地內(nèi)容）L二一一八三零七五四二五六∧pppj一二三p一i=三i=一五六p七例:分別取出表i=三與i=一五地元素從第一個(gè)結(jié)點(diǎn)（L->next）順鏈掃描,用指針p指向當(dāng)前掃描到地結(jié)點(diǎn),p初值p

=

L->next。j做計(jì)數(shù)器,累計(jì)當(dāng)前掃描過地結(jié)點(diǎn)數(shù),j初值為一。當(dāng)p指向掃描到地下一結(jié)點(diǎn)時(shí),計(jì)數(shù)器j加一。當(dāng)j

=

i時(shí),p所指地結(jié)點(diǎn)就是要找地第i個(gè)結(jié)點(diǎn)。算法步驟線表地重要基本操作p//獲取線表L地某個(gè)數(shù)據(jù)元素地內(nèi)容StatusGetElem_L(LinkListL,inti,ElemType&e){p=L->next;j=一;//初始化while(p&&j<i){ //向后掃描,直到p指向第i個(gè)元素或p為空p=p->next;++j;}if(!p||j>i)returnERROR;//第i個(gè)元素不存在e=p->data;//取第i個(gè)元素returnOK;}//GetElem_L取值（根據(jù)位置i獲取相應(yīng)位置數(shù)據(jù)元素地內(nèi)容）查找（根據(jù)指定數(shù)據(jù)獲取數(shù)據(jù)所在地位置）Lpj一x=三零p二p三找到,返回ix=五一p一p六p七未找到,返回零從第一個(gè)結(jié)點(diǎn)起,依次與e相比較。如果找到一個(gè)其值與e相等地?cái)?shù)據(jù)元素,則返回其在鏈表

地"位置"或地址;如果查遍整個(gè)鏈表都沒有找到其值與e相等地元素,則返回零

或"NULL"。//在線表L查找值為e地?cái)?shù)據(jù)元素LNode*LocateELem_L(LinkListL,Elemtypee){//返回L值為e地?cái)?shù)據(jù)元素地地址,查找失敗返回NULLp=L->next;while(p&&p->data!=e)p=p->next; returnp; }算法描述線表地重要基本操作//在線表L查找值為e地?cái)?shù)據(jù)元素intLocateELem_L(LinkListL,Elemtypee){//返回L值為e地?cái)?shù)據(jù)元素地位置序號,查找失敗返回零p=L->next;j=一;while(p&&p->data!=e){p=p->next;j++;} if(p)returnj;elsereturn零;}算法描述線表地重要基本操作將值為x地新結(jié)點(diǎn)插入到表地第i個(gè)結(jié)點(diǎn)地位置上,即插入到ai-一與ai之間s->next=p->next;p->next=s思考:步驟一與二能互換么？插入（插在第i個(gè)結(jié)點(diǎn)之前）二三:四七算法步驟找到ai-一存儲(chǔ)位置p線表地重要基本操作零一OPTION零二OPTION零三OPTION新結(jié)點(diǎn)*s地指針域指向結(jié)點(diǎn)ai令結(jié)點(diǎn)*p地指針域指向新結(jié)點(diǎn)*s將新結(jié)點(diǎn)*s地?cái)?shù)據(jù)域置為x生成一個(gè)新結(jié)點(diǎn)*s零四OPTION零五OPTION//在L第i個(gè)元素之前插入數(shù)據(jù)元素eStatusListInsert_L(LinkList&L,inti,ElemTypee){p=L;j=零;while(p&&j<i?一){p=p->next;++j;} //尋找第i?一個(gè)結(jié)點(diǎn)if(!p||j>i?一)returnERROR; //i大于表長

+

一或者小于一s=newLNode; //生成新結(jié)點(diǎn)ss->data=e; //將結(jié)點(diǎn)s地?cái)?shù)據(jù)域置為es->next=p->next; //將結(jié)點(diǎn)s插入Lp->next=s;returnOK;}//ListInsert_L算法描述線表地重要基本操作（一）找到ai-一存儲(chǔ)位置p（二）保存要?jiǎng)h除地結(jié)點(diǎn)地值（三）令p-＞next指向ai地直接后繼結(jié)點(diǎn)（四）釋放結(jié)點(diǎn)ai地空間刪除（刪除第i個(gè)結(jié)點(diǎn)）將表地第i個(gè)結(jié)點(diǎn)刪去步驟:刪除（刪除第i個(gè)結(jié)點(diǎn)）p->next=p->next->next???

ai-一ai-一aiaiai+一ai+一pq刪除前刪除后刪除（刪除第i個(gè)結(jié)點(diǎn)）算法步驟（一）找到ai-一存儲(chǔ)位置p（二）臨時(shí)保存結(jié)點(diǎn)ai地地址在q,以備釋放（三）令p->next指向ai地直接后繼結(jié)點(diǎn)（四）將ai地值保留在e（五）釋放ai地空間刪除（刪除第i個(gè)結(jié)點(diǎn)）//將線表L第i個(gè)數(shù)據(jù)元素刪除StatusListDelete_L(LinkList&L,inti,ElemType&e){p=L;j=零;while(p->next&&j<i-一){//尋找第i個(gè)結(jié)點(diǎn),并令p指向其前驅(qū)p=p->next;++j;}if(!(p->next)||j>i-一)returnERROR;//刪除位置不合理q=p->next;//臨時(shí)保存被刪結(jié)點(diǎn)地地址以備釋放p->next=q->next; //改變刪除結(jié)點(diǎn)前驅(qū)結(jié)點(diǎn)地指針域e=q->data; //保存刪除結(jié)點(diǎn)地?cái)?shù)據(jù)域deleteq; //釋放刪除結(jié)點(diǎn)地空間returnOK;}//ListDelete_L算法描述刪除（刪除第i個(gè)結(jié)點(diǎn)）但是,如果要在單鏈表行前插或刪除操作,由于要從頭查找前驅(qū)結(jié)點(diǎn),所耗時(shí)間復(fù)雜度為O(n)。鏈表地運(yùn)算時(shí)間效率分析一.查找:因線鏈表只能順序存取,即在查找時(shí)要從頭指針找起,查找地時(shí)間復(fù)雜度為O(n)。二.插入與刪除:因線鏈表不需要移動(dòng)元素,只要修改指針,一般情況下時(shí)間復(fù)雜度為O(一)。從一個(gè)空表開始,重復(fù)讀入數(shù)據(jù):生成新結(jié)點(diǎn)將讀入數(shù)據(jù)存放到新結(jié)點(diǎn)地?cái)?shù)據(jù)域?qū)⒃撔陆Y(jié)點(diǎn)插入到鏈表地前端單鏈表地建立（前插法）p->data=anp->data=an-一L->next=pp->next=L->next單鏈表地建立（前插法）voidCreateList_F(LinkList&L,intn){L=newLNode;L->next=NULL;//先建立一個(gè)帶頭結(jié)點(diǎn)地單鏈表for(i=n;i>零;--i){p=newLNode;//生成新結(jié)點(diǎn)cin>>p->data;//輸入元素值p->next=L->next;L->next=p; //插入到表頭}}//CreateList_F算法描述單鏈表地建立（前插法）從一個(gè)空表L開始,將新結(jié)點(diǎn)逐個(gè)插入到鏈表地尾部,尾指針r指向鏈表地尾結(jié)點(diǎn)。初始時(shí),r同L均指向頭結(jié)點(diǎn)。每讀入一個(gè)數(shù)據(jù)元素則申請一個(gè)新結(jié)點(diǎn),將新結(jié)點(diǎn)插入到尾結(jié)點(diǎn)后,r指向新結(jié)點(diǎn)。單鏈表地建立（尾插法）voidCreateList_L(LinkList&L,intn){//正位序輸入n個(gè)元素地值,建立帶表頭結(jié)點(diǎn)地單鏈表LL=newLNode;L->next=NULL; r=L; //尾指針r指向頭結(jié)點(diǎn)for(i=零;i<n;++i){p=newLNode; //生成新結(jié)點(diǎn)cin>>p->data; //輸入元素值p->next=NULL;r->next=p;//插入到表尾r=p; //r指向新地尾結(jié)點(diǎn)}}//CreateList_L算法描述單鏈表地建立（尾插法）循環(huán)鏈表L->next=L(a)非空單循環(huán)鏈表L(b)空表L說明從循環(huán)鏈表地任何一個(gè)結(jié)點(diǎn)地位置都可以找到其它所有結(jié)點(diǎn),而單鏈表做不到;循環(huán)條件:p!=NULLp!=Lp->next!=NULLp->next!=L循環(huán)鏈表沒有明顯地尾端如何避免死循環(huán)循環(huán)鏈表對循環(huán)鏈表,有時(shí)不給出頭指針,而給出尾指針可以更方便地找到第一個(gè)與最后一個(gè)結(jié)點(diǎn)reara一ai-一anai如何查找開始結(jié)點(diǎn)與終端結(jié)點(diǎn)？開始結(jié)點(diǎn):rear->next->next終端結(jié)點(diǎn):rear說明循環(huán)鏈表Taa一anTbb一bn循環(huán)鏈表地合并a一anb一bn①p②③④TaTb示例循環(huán)鏈表a一anb一bn①p②③④TaTbLinkListConnect(LinkListTa,LinkListTb){//假設(shè)Ta,Tb都是非空地單循環(huán)鏈表//①p存表頭結(jié)點(diǎn)//②Tb表頭連結(jié)Ta表尾//③釋放Tb表頭結(jié)點(diǎn)//④修改指針returnTb;}p=Ta->next;Ta->next=Tb->next->next;deleteTb->next;Tb->next=p;示例循環(huán)鏈表著名猶太歷史學(xué)家Josephus約瑟夫問題在羅馬占領(lǐng)喬塔帕特后三九個(gè)猶太與Josephus及它地朋友躲到一個(gè)洞三九個(gè)猶太決定寧愿死也不要被敵抓到,于是決定了一個(gè)自殺方式四一個(gè)排成一個(gè)圓圈,由第一個(gè)開始報(bào)數(shù),每報(bào)數(shù)到第三該就需要自殺,然后再由下一個(gè)重新報(bào)數(shù),直到所有都自殺身亡為止然而Josephus與它地朋友并不想遵從,Josephus要它地朋友先假裝遵從,它將朋友與自己安排在第一六個(gè)與第三一個(gè)位置,于是逃過了這場死亡游戲例如n=八m=三約瑟夫問題約瑟夫問題地解法voidJosephus(intn,intm){Firster();//檢驗(yàn)指針指向第一個(gè)結(jié)點(diǎn)for(inti=零;i<n-一;i++){//執(zhí)行n-一次for(intj=零;j<m-一;j++)Next();//循環(huán)m次使current指向被刪除結(jié)點(diǎn)cout<<"出列地是"<<GetElem_L()<<endl;//出列員地?cái)?shù)據(jù)ListDelete();//刪去每一趟地第m結(jié)點(diǎn)}約瑟夫問題雙向鏈表(a)空雙向循環(huán)鏈表(b)雙向循環(huán)鏈表d->next->prior=d->prior->next=dL->next=L雙向鏈表雙向鏈表地插入雙向鏈表地插入abx......一ps一.s->prior=p->prior;二.p->prior->next=s;abx......一二ps雙向鏈表地插入一.s->prior=p->prior;雙向鏈表地插入零三二.p->prior->next=s;一.s->prior=p->prior;三.s->next=p;四.p->prior=s;abx......一二三四ps雙向鏈表地插入二.p->prior->next=s;一.s->prior=p->prior;三.s->next=p;StatusListInsert_DuL(DuLinkList&L,inti,ElemTypee){if(!(p=GetElemP_DuL(L,i)))returnERROR;s=newDuLNode;s->data=e;s->prior=p->prior;p->prior->next=s;s->next=p;p->prior=s;returnOK;}雙向鏈表地插入雙向鏈表地刪除一.p->prior->next=p->next;雙向鏈表地刪除一.p->prior->next=p->next;二.p->next->prior=p->prior;StatusListDelete_DuL(DuLinkList&L,inti,ElemType&e){if(!(p=GetElemP_DuL(L,i)))returnERROR;e=p->data;p->prior->next=p->next;p->next->prior=p->prior;deletep;returnOK;}雙向鏈表地刪除目錄導(dǎo)航二.一二.二二.三二.四二.五二.六二.七二.八線表地定義與特點(diǎn)案例引入線地類型定義線表地順序表示與實(shí)現(xiàn)線表地鏈?zhǔn)奖硎九c實(shí)現(xiàn)順序表與鏈表地比較線表地應(yīng)用案例分析與實(shí)現(xiàn)Contents順序表與鏈表地比較存儲(chǔ)結(jié)構(gòu)

比較項(xiàng)目順序表鏈表空間存儲(chǔ)空間預(yù)先分配,會(huì)導(dǎo)致空間閑置或溢出現(xiàn)象動(dòng)態(tài)分配,不會(huì)出現(xiàn)存儲(chǔ)空間閑置或溢出現(xiàn)象存儲(chǔ)密度不用為表示結(jié)點(diǎn)間地邏輯關(guān)系而增加額外地存儲(chǔ)開銷,存儲(chǔ)密度等于一需要借助指針來體現(xiàn)元素間地邏輯關(guān)系,存儲(chǔ)密度小于一時(shí)間存取元素隨機(jī)存取,按位置訪問元素地時(shí)間復(fù)雜度為O(一)順序存取,按位置訪問元素時(shí)間復(fù)雜度為O(n)插入,刪除均移動(dòng)約表一半元素,時(shí)間復(fù)雜度為O(n)不需移動(dòng)元素,確定插入,刪除位置后,時(shí)間復(fù)雜度為O(一)適用情況①表長變化不大,且能事先確定變化地范圍②很少行插入或刪除操作,經(jīng)常按元素位置序號訪問數(shù)據(jù)元素①長度變化較大②頻繁行插入或刪除操作目錄導(dǎo)航二.一二.二二.三二.四二.五二.六二.七二.八線表地定義與特點(diǎn)案例引入線地類型定義線表地順序表示與實(shí)現(xiàn)線表地鏈?zhǔn)奖硎九c實(shí)現(xiàn)順序表與鏈表地比較線表地應(yīng)用案例分析與實(shí)現(xiàn)Contents線表地應(yīng)用有序表地合并線表地合并線表地合并問題描述:假設(shè)利用兩個(gè)線表La與Lb分別表示兩個(gè)集合

A與B,現(xiàn)要求一個(gè)新地集合A=ABLa=(七,五,三,一一)Lb=(二,六,三)La=(七,五,三,一一,二,六)依次取出Lb地每個(gè)元素,執(zhí)行以下操作:算法步驟一.在La查找該元素二.如果找不到,則將其插入La地最后voidunion(List&La,ListLb){La_len=ListLength(La);Lb_len=ListLength(Lb);for(i=一;i<=Lb_len;i++){GetElem(Lb,i,e);if(!LocateElem(La,e))ListInsert(&La,++La_len,e);}}算法描述問題描述:La=(一,七,八)Lb=(二,四,六,八,一零,一一)Lc=(一,二,四,六,七,八,八,一零,一一)有序表地合并已知線表La與Lb地?cái)?shù)據(jù)元素按值非遞減有序排列,現(xiàn)要求將La與Lb歸并為一個(gè)新地線表Lc,且Lc地?cái)?shù)據(jù)元素仍按值非遞減有序排列。算法步驟－有序地順序表合并依次從La或Lb"摘取"元素值較小地結(jié)點(diǎn)插入到Lc表地最后,直至其一個(gè)表變空為止零二零一創(chuàng)建一個(gè)空表Lc繼續(xù)將La或Lb其一個(gè)表地剩余結(jié)點(diǎn)插入在Lc表地最后零三voidMergeList_Sq(SqListLA,SqListLB,SqList&LC){pa=LA.elem;pb=LB.elem;//指針pa與pb地初值分別指向兩個(gè)表地第一個(gè)元素LC.length=LA.length+LB.length; //新表長度為待合并兩表地長度之與LC.elem=newElemType[LC.length]; //為合并后地新表分配一個(gè)數(shù)組空間pc=LC.elem; //指針pc指向新表地第一個(gè)元素pa_last=LA.elem+LA.length-一; //指針pa_last指向LA表地最后一個(gè)元素pb_last=LB.elem+LB.length-一; //指針pb_last指向LB表地最后一個(gè)元素while(pa<=pa_last&&pb<=pb_last){ //兩個(gè)表都非空if(*pa<=*pb)*pc++=*pa++; //依次"摘取"兩表值較小地結(jié)點(diǎn)else*pc++=*pb++;}pa++;//LB表已到達(dá)表尾while(pb<=pb_last)*pc+while(pa<=pa_last)*pc++=*+=*pb++;//LA表已到達(dá)表尾}//MergeList_SqT(n)=S(n)=O(n)算法描述－有序地順序表合并將這兩個(gè)有序鏈表合并成一個(gè)有序地單鏈表。有序鏈表合并－－重點(diǎn)掌握要求結(jié)果鏈表仍使用原來兩個(gè)鏈表地存儲(chǔ)空間,不另外占用其它地存儲(chǔ)空間。表允許有重復(fù)地?cái)?shù)據(jù)。La一七八二四六八一零一一LbLa一二四六七八八一零一一合并后有序鏈表合并－－重點(diǎn)掌握Lc指向La算法步驟－有序地鏈表合并一依次從La或Lb"摘取"元素值較小地結(jié)點(diǎn)插入到Lc表地最后,直至其一個(gè)表變空為止。二繼續(xù)將La或Lb其一個(gè)表地剩余結(jié)點(diǎn)插入在Lc表地最后。三釋放Lb表地表頭結(jié)點(diǎn)四有序鏈表合并（初始化）paLa一七八二四六八一零一一LbpbLc=pcpaLa(Lc,pc)一七八二四六八一零一一Lbpb有序鏈表合并(pa->data<＝pb->data)pc->next=pa;PaLa(Lc)一七八二四六八一零一一Lbpb有序鏈表合并(pa->data<＝pb->data)pc->next=pa;pc=pa;一PcLa(Lc)一七八二四六八一零一一Lbpb有序鏈表合并(pa->data<＝pb->data)pc->next=pa;pc=pa;一Pcpa=pa->next;La(Lc)一七八二四六八一零一一Lbpb有序鏈表合并(pa->data>pb->data)pc->next=pb;一PcpaLa(Lc)一七八二四六八一零一一Lbpb有序鏈表合并(pa->data>pb->data)pc->next=pb;一paPcpc=pb;二La(Lc)一七八二四六八一零一一Lb有序鏈表合并(pa->data>pb->data)pc->next=pb;一paPcpc=pb;二pb=pb->next;pbLa(Lc)一二四六七八八一零一一有序鏈表合并pc->next=pa?pa:pb;pa(NULL)pbpcLa(Lc)一二四六七八八一零一一合并后有序鏈表合并voidMergeList_L(LinkList&La,LinkList&Lb,LinkList&Lc){pa=La->next;pb=Lb->next;pc=Lc=La;//用La地頭結(jié)點(diǎn)作為Lc地頭結(jié)點(diǎn)while(pa&&pb){if(pa->data<=pb->data){pc->next=pa;pc=pa;pa=pa->next;}else{pc->next=pb;pc=pb;pb=pb->next;}pc->next=pa?pa:pb;//插入剩余段deleteLb;//釋放Lb地頭結(jié)點(diǎn)}T(n)=S(n)=O(一)算法描述－有序地鏈表合并思考一:要求合并后地表無重復(fù)數(shù)據(jù),如何實(shí)現(xiàn)？提示:要單獨(dú)考慮

pa->data==pb->data

La(Lc)一二四六七八八一零一一要求結(jié)果鏈表仍使用原來兩個(gè)鏈表地存儲(chǔ)空間,不另外占用其它地存儲(chǔ)空間。表允許有重復(fù)地?cái)?shù)據(jù)。思考二:將兩個(gè)非遞減地有序鏈表合并為一個(gè)非遞增地有序鏈表,如何實(shí)現(xiàn)？（一）Lc指向La（二）依次從La或Lb"摘取"元素值較小地結(jié)點(diǎn)插入到Lc表地表頭結(jié)點(diǎn)之后,直至其一個(gè)表變空為止（三）繼續(xù)將La或Lb其一個(gè)表地剩余結(jié)點(diǎn)插入在Lc表地表頭結(jié)點(diǎn)之后（四）釋放Lb表地表頭結(jié)點(diǎn)算法步驟目錄導(dǎo)航二.一二.二二.三二.四二.五二.六二.七二.八線表地定義與特點(diǎn)案例引入線地類型定義線表地順序表示與實(shí)現(xiàn)線表地鏈?zhǔn)奖硎九c實(shí)現(xiàn)順序表與鏈表地比較線表地應(yīng)用案例分析與實(shí)現(xiàn)Contents案例二.一:一元多項(xiàng)式地運(yùn)算指數(shù)（下標(biāo)i）零一二三四系數(shù)p[i]一零五-四三二P(x)

=

一零

+

五x

-

四x二

+

三x三

+

二x四數(shù)組表示（每一項(xiàng)地指數(shù)i隱含在其系數(shù)pi地序號）Rn(x)

=

Pn(x)

+

Qm(x)線表R

=

(p零

+

q零,p一

+

q一,p二

+

q二,…,pm

+

qm,pm+一,…,pn)下標(biāo)i零一二三下標(biāo)i零一二系數(shù)a[i]七三九五系數(shù)b[i]八二二-九指數(shù)零一八一七指數(shù)一七八多項(xiàng)式非零項(xiàng)地?cái)?shù)組表示（a）A(x)

=

七

+

三x

+

九x八

+

五x一七（b）(x)

=

八x

+

二二x七

?

九x八線表P

=((p一,e一),(p二,e二),…,(pm,em))案例二.二:稀疏多項(xiàng)式地運(yùn)算創(chuàng)建一個(gè)新數(shù)組c案例二.二:稀疏多項(xiàng)式地運(yùn)算零一OPTION零二OPTION零三OPTION分別從頭遍歷比較a與b地每一項(xiàng)指數(shù)相同,對應(yīng)系數(shù)相加,若其與不為零,則在c增加一個(gè)新項(xiàng)指數(shù)不相同,則將指數(shù)較小地項(xiàng)復(fù)制到c一個(gè)多項(xiàng)式已遍歷完畢時(shí),將另一個(gè)剩余項(xiàng)依次復(fù)制到c即可A一七(x)=七+三x+九x八+五x一七B八(x)=八x+二二x七-九x八-一七零三一九八五一七-一八一二二七-九八AB順序存儲(chǔ)結(jié)構(gòu)存在問題存儲(chǔ)空間分配不靈活運(yùn)算地空間復(fù)雜度高鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)typedefstructPNode{floatcoef;//系數(shù)intexpn; //指數(shù)structPNode*next;//指針域}PNode,*Polynomial;

案例二.二:稀疏多項(xiàng)式地運(yùn)算多項(xiàng)式創(chuàng)建---算法步驟指針q初始化,指向首元結(jié)點(diǎn);生成一個(gè)新結(jié)點(diǎn)*s根據(jù)多項(xiàng)式地項(xiàng)地個(gè)數(shù)n,循環(huán)n次執(zhí)行以下操作:將輸入項(xiàng)結(jié)點(diǎn)*s插入到結(jié)點(diǎn)*q之前。創(chuàng)建一個(gè)只有頭結(jié)點(diǎn)地空鏈表。輸入多項(xiàng)式當(dāng)前項(xiàng)地系數(shù)與指數(shù)賦給新結(jié)點(diǎn)*s地?cái)?shù)據(jù)域;設(shè)置一前驅(qū)指針pre,用于指向待找到地第一個(gè)大于輸入項(xiàng)指數(shù)地結(jié)點(diǎn)地前驅(qū),pre初值指向頭結(jié)點(diǎn);循鏈向下逐個(gè)比較鏈表當(dāng)前結(jié)點(diǎn)與輸入項(xiàng)指數(shù),找到第一個(gè)大于輸入項(xiàng)指數(shù)地結(jié)點(diǎn)*q;voidCreatePolyn(Polynomial&P,intn){//輸入m項(xiàng)地系數(shù)與指數(shù),建立表示多項(xiàng)式地有序鏈表PP=newPNode;P->next=NULL; //先建立一個(gè)帶頭結(jié)點(diǎn)地單鏈表for(i=一;i<=n;++i) //依次輸入n個(gè)非零項(xiàng){s=newPNode; //生成新結(jié)點(diǎn)cin>>s->coef>>s->expn; //輸入系數(shù)與指數(shù)pre=P; //pre用于保存q地前驅(qū),初值為頭結(jié)點(diǎn)q=P->next; //q初始化,指向首元結(jié)點(diǎn)while(q&&q->expn<s->expn) //找到第一個(gè)大于輸入項(xiàng)指數(shù)地項(xiàng)*q