《教案數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏第2章線性表課件》由會員分享，可在線閱讀，更多相關(guān)《教案數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏第2章線性表課件（172頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、徐海霞徐海霞 第第2章章 線性表線性表近近近近3 3 3 3周周周周上課上課上課上課內(nèi)容內(nèi)容內(nèi)容內(nèi)容第第2 2章章 線性表線性表第第3 3章章 棧和隊列棧和隊列第第4 4章章 串、數(shù)組和廣義串、數(shù)組和廣義表表 線性結(jié)構(gòu)線性結(jié)構(gòu)若若結(jié)結(jié)構(gòu)構(gòu)是是非非空空有有限限集集，則則有有且且僅僅有有一一個個開開始始結(jié)結(jié)點點和和一一個個終終端端結(jié)結(jié)點點，并并且且所所有有結(jié)結(jié)點點都都最最多多只只有有一一個個直接前趨和一個直接后繼。直接前趨和一個直接后繼?？杀硎緸榭杀硎緸椋海ǎ海╝ a1 1,a,a2 2 ,a,an n）線性結(jié)構(gòu)的定義：線性結(jié)構(gòu)的定義：線性結(jié)構(gòu)的定義：線性結(jié)構(gòu)的定義：（邏輯、存儲（邏輯、存儲和運算

2、）和運算）線性結(jié)構(gòu)的特點：線性結(jié)構(gòu)的特點：只有一個首結(jié)點和尾結(jié)點；只有一個首結(jié)點和尾結(jié)點；除除首首尾尾結(jié)結(jié)點點外外，其其他他結(jié)結(jié)點點只只有有一一個個直直接接前前驅(qū)驅(qū)和和一一個直接后繼。個直接后繼。線性結(jié)構(gòu)表達(dá)式：（線性結(jié)構(gòu)表達(dá)式：（a a1 1,a,a2 2 ,a,an n）線性結(jié)構(gòu)包括線性表、堆棧、隊列、字符串、數(shù)線性結(jié)構(gòu)包括線性表、堆棧、隊列、字符串、數(shù)組等等，其中，最典型、最常用的是組等等，其中，最典型、最常用的是線性表線性表簡言之，線性結(jié)構(gòu)反映結(jié)點間的邏輯關(guān)系是簡言之，線性結(jié)構(gòu)反映結(jié)點間的邏輯關(guān)系是 一對一一對一 的的第第2 2章線性表章線性表1.1.了解線性結(jié)構(gòu)的特點了解線性結(jié)構(gòu)的特

3、點2.2.掌握順序表的定義、查找、插入和刪除掌握順序表的定義、查找、插入和刪除 3.3.掌握鏈表的定義、創(chuàng)建、查找、插入和刪除掌握鏈表的定義、創(chuàng)建、查找、插入和刪除 4.4.能夠從時間和空間復(fù)雜度的角度比較兩種存儲結(jié)能夠從時間和空間復(fù)雜度的角度比較兩種存儲結(jié)構(gòu)的不同特點及其適用場合構(gòu)的不同特點及其適用場合 教學(xué)目標(biāo)教學(xué)目標(biāo)2.1 2.1 線性表的定義和特點線性表的定義和特點2.2 2.2 案例引入案例引入2.3 2.3 線性的類型定義線性的類型定義2.4 2.4 線性表的順序表示和實現(xiàn)線性表的順序表示和實現(xiàn)2.5 2.5 線性表的鏈?zhǔn)奖硎竞蛯崿F(xiàn)線性表的鏈?zhǔn)奖硎竞蛯崿F(xiàn)2.6 2.6 順序表和鏈表

4、的比較順序表和鏈表的比較2.7 2.7 線性表的應(yīng)用線性表的應(yīng)用2.8 2.8 案例分析與實現(xiàn)案例分析與實現(xiàn)教學(xué)內(nèi)容教學(xué)內(nèi)容（a1,a2,ai-1，ai,ai1，,an）線性表的定性表的定義：用數(shù)據(jù)元素的有限序列表示用數(shù)據(jù)元素的有限序列表示n=0時稱稱為數(shù)據(jù)元素數(shù)據(jù)元素線性起點性起點ai的直接前的直接前趨ai的直接后的直接后繼下下標(biāo)，是元素的是元素的序號，表示元素序號，表示元素在表中的位置在表中的位置n為元素元素總個個數(shù)，即表數(shù)，即表長空表空表線性性終點點2.1 2.1 線性表的定義和特點線性表的定義和特點例例例例11分析分析分析分析2626個英文字母個英文字母個英文字母個英文字母組組成的英文

5、表成的英文表成的英文表成的英文表 （A,B,C,D,Z）學(xué)號學(xué)號姓名姓名性性別年年齡班班級041810205041810205于春梅于春梅女女 18 180404級計算機算機1 1班班041810260041810260何仕何仕鵬男男 20 200404級計算機算機2 2班班041810284041810284王王 爽爽女女 19 190404級計算機算機3 3班班041810360041810360王王亞武武男男 18 180404級計算機算機4 4班班：例例例例22分析學(xué)生情況登分析學(xué)生情況登分析學(xué)生情況登分析學(xué)生情況登記記表表表表數(shù)據(jù)元素都是數(shù)據(jù)元素都是記錄;元素元素間關(guān)系是關(guān)系是線性性

6、數(shù)據(jù)元素都是字母數(shù)據(jù)元素都是字母;元素元素間關(guān)系是關(guān)系是線性性同一同一線性表中的元素必定具有相同特性性表中的元素必定具有相同特性2.2 2.2 案例引入案例引入案例案例案例案例2.1 2.1 2.1 2.1：一元多項式的運算：一元多項式的運算：一元多項式的運算：一元多項式的運算Pn(x)=p0+p1x+p2x2+pnxn線性表線性表P=(p0,p1,p2,pn)指數(shù)（下標(biāo)i）01234系數(shù)pi105-432P(x)=10+5x-4x2+3x3+2x4數(shù)組表示數(shù)組表示（每一（每一項的指數(shù)的指數(shù)i隱含含在其系數(shù)在其系數(shù)pi的序號中）的序號中）Rn(x)=Pn(x)+Qm(x)線性表線性表R=(p0

7、+q0,p1+q1,p2+q2,pm+qm,pm+1,pn)稀疏多項式稀疏多項式S(x)=1+3x10000+2x20000北京林業(yè)大學(xué)信息學(xué)院下標(biāo)i0123下標(biāo)i012系數(shù)ai7395系數(shù)bi822-9指數(shù)01817指數(shù)178多項式非零項非零項的數(shù)組表示（a）A(x)=7+3x+9x8+5x17 （b）B(x)=8x+22x79x8線性表線性表P=(p1,e1),(p2,e2),(pm,em)l創(chuàng)建一個創(chuàng)建一個新數(shù)組新數(shù)組c cl分別從頭遍歷比較分別從頭遍歷比較a a和和b b的每一項的每一項指數(shù)相同指數(shù)相同，對應(yīng)系數(shù)相加，若其和不為零，則在，對應(yīng)系數(shù)相加，若其和不為零，則在c c中增加一個

8、新項中增加一個新項指數(shù)不相同指數(shù)不相同，則將指數(shù)較小的項復(fù)制到，則將指數(shù)較小的項復(fù)制到c c中中l(wèi)一個多項式已遍歷一個多項式已遍歷完畢完畢時，將另一個剩余項依次復(fù)制到時，將另一個剩余項依次復(fù)制到c c中即可中即可案例案例案例案例2.2 2.2 2.2 2.2：稀疏多項式的運算：稀疏多項式的運算：稀疏多項式的運算：稀疏多項式的運算A17(x)=7+3x+9x8+5x17B8(x)=8x+22x7-9x8-1703198517-181227-98ABpapbl順序存儲結(jié)構(gòu)存在問題順序存儲結(jié)構(gòu)存在問題存儲空間分配不靈活存儲空間分配不靈活運算的空間復(fù)雜度高運算的空間復(fù)雜度高鏈?zhǔn)酱鎯Y(jié)構(gòu)鏈?zhǔn)酱鎯Y(jié)構(gòu)多項

9、式相加多項式相加A17(x)=7+3x+9x8+5x17B8(x)=8x+22x7-9x8-1703198517-181227-98ABpapb多項式相加多項式相加A17(x)=7+3x+9x8+5x17B8(x)=8x+22x7-9x8-17011198517-181227-98ABpapb多項式相加多項式相加A17(x)=7+3x+9x8+5x17B8(x)=8x+22x7-9x8-17011198517-181227-98ABpapb多項式相加多項式相加A17(x)=7+3x+9x8+5x17B8(x)=8x+22x7-9x8-17011198517-181227-98ABpapb（1

10、1）查找）查找（2 2）插入）插入（3 3）刪除）刪除（4 4）修改）修改（5 5）排序）排序（6 6）計數(shù)）計數(shù)案例案例案例案例2.3 2.3 2.3 2.3：圖書信息管理系統(tǒng)：圖書信息管理系統(tǒng)：圖書信息管理系統(tǒng)：圖書信息管理系統(tǒng)圖書順序表圖書順序表圖書鏈表圖書鏈表l線性表中數(shù)據(jù)元素的類型可以為簡單類型，也可以為復(fù)雜類型。線性表中數(shù)據(jù)元素的類型可以為簡單類型，也可以為復(fù)雜類型。l許多實際應(yīng)用問題所涉的基本操作有很大相似性，不應(yīng)為每個具許多實際應(yīng)用問題所涉的基本操作有很大相似性，不應(yīng)為每個具體應(yīng)用單獨編寫一個程序。體應(yīng)用單獨編寫一個程序。l從具體應(yīng)用中從具體應(yīng)用中抽象出共性的邏輯結(jié)構(gòu)和基本操作

11、抽象出共性的邏輯結(jié)構(gòu)和基本操作（抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型），然后實現(xiàn)其存儲結(jié)構(gòu)和基本操作。，然后實現(xiàn)其存儲結(jié)構(gòu)和基本操作。線性表的重要基本操作線性表的重要基本操作1.1.初始化初始化2.2.取值取值3.3.查找查找4.4.插入插入5.5.刪除刪除2.3 2.3 線性表的類型定義線性表的類型定義2.4 2.4 線性表的順序表示和實現(xiàn)線性表的順序表示和實現(xiàn)線性表的順序表示又稱為線性表的順序表示又稱為順序存儲結(jié)構(gòu)順序存儲結(jié)構(gòu)或或順序映像順序映像。簡言之，邏輯上相鄰，物理上也相鄰簡言之，邏輯上相鄰，物理上也相鄰順序存儲方法：順序存儲方法：用用一組地址連續(xù)一組地址連續(xù)的存儲單元依次存儲的存儲單元依次存儲

12、線性表的元素，可通過線性表的元素，可通過數(shù)組數(shù)組VnVn來實現(xiàn)。來實現(xiàn)。順序存儲定義：順序存儲定義：把邏輯上相鄰的數(shù)據(jù)元素存儲在物理把邏輯上相鄰的數(shù)據(jù)元素存儲在物理上相鄰的存儲單元中的存儲結(jié)構(gòu)。上相鄰的存儲單元中的存儲結(jié)構(gòu)。元素元素n.元素元素i.元素元素2元素元素1LoLo+mLo+(i-1)*mLo+（n-1)*m存存儲地址地址存存儲內(nèi)容內(nèi)容Loc(元素元素i)=Lo+（i-1)*m順序存序存儲#define MAXSIZE 100 /最大最大長度度typedef struct ElemType *elem;/指向數(shù)據(jù)元素的基地址指向數(shù)據(jù)元素的基地址int length;/線性表的當(dāng)前性表

13、的當(dāng)前長度度 SqList；順序表的序表的類型定型定義#defineMAXSIZE10000/圖書表可能達(dá)到的最大長度圖書表可能達(dá)到的最大長度typedefstruct/圖書信息定義圖書信息定義charno20;/圖書圖書ISBNcharname50;/圖書名字圖書名字floatprice;/圖書價格圖書價格Book;typedefstructBook*elem;/存儲空間的基地址存儲空間的基地址intlength;/圖書表中當(dāng)前圖書個數(shù)圖書表中當(dāng)前圖書個數(shù)SqList;/圖書表的順序存儲結(jié)構(gòu)類型為圖書表的順序存儲結(jié)構(gòu)類型為SqList圖書表的表的順序存序存儲結(jié)構(gòu)構(gòu)類型定型定義malloc(m

14、)：開辟：開辟m字字節(jié)長度的地址空度的地址空間，并返回并返回這段空段空間的首地址的首地址sizeof(x)：計算算變量量x的的長度度free(p)：釋放指放指針p所指所指變量的存量的存儲空空間，即即徹底底刪除一個除一個變量量補充：充：C語言的言的動態(tài)分配函數(shù)（分配函數(shù)（）new 類型名型名T（初（初值列表）列表）功能：功能：申申請用于存放用于存放T類型型對象的內(nèi)存空象的內(nèi)存空間，并依初，并依初值列表列表賦以初以初值結(jié)果果值：成功：成功：T類型的指型的指針，指向新分配的內(nèi)存，指向新分配的內(nèi)存失失?。? 0（NULL）int*p1=newint;或或int*p1=newint(10);delete

15、 指指針P功能：功能：釋放指放指針P所指向的內(nèi)存。所指向的內(nèi)存。P必必須是是new操作的返回操作的返回值deletep1;補充：充：C+的的動態(tài)存存儲分配分配n函數(shù)函數(shù)調(diào)用用時傳送送給形參表的形參表的實參必參必須與形參在與形參在類型、型、個數(shù)、個數(shù)、順序上保持一致序上保持一致n參數(shù)參數(shù)傳遞有兩種方式有兩種方式n傳值方式方式（參數(shù)（參數(shù)為整型、整型、實型、字符型等）型、字符型等）n傳地址地址參數(shù)參數(shù)為指指針變量量參數(shù)參數(shù)為引用引用類型型參數(shù)參數(shù)為數(shù)數(shù)組名名補充：充：C+中的參數(shù)中的參數(shù)傳遞voidmain()floata,b;cinab;swap(a,b);coutaendlbendl;#inc

16、ludevoidswap(floatm,floatn)floattemp;temp=m;m=n;n=temp;傳值方式方式把把實參的參的值傳送送給函數(shù)局部工作區(qū)相函數(shù)局部工作區(qū)相應(yīng)的副的副本中本中，函數(shù)使用，函數(shù)使用這個副本個副本執(zhí)行必要的功能。行必要的功能。函數(shù)修改的是函數(shù)修改的是副本的副本的值，實參的參的值不不變傳地址地址方式方式指指針變量作參數(shù)量作參數(shù)voidmain()floata,b,*p1,*p2;cinab;p1=&a;p2=&b;swap(p1,p2);coutaendlbendl;#includevoidswap(float*m,float*n)floatt;t=*m;*m=

17、*n;*n=t;形參形參變化影響化影響實參參 *傳地址地址方式方式指指針變量作參數(shù)量作參數(shù)voidmain()floata,b,*p1,*p2;cinab;p1=&a;p2=&b;swap(p1,p2);coutaendlbendl;#includevoidswap(float*m,float*n)float*t;t=m;m=n;n=t;形參形參變化不影響化不影響實參？參？傳地址地址方式方式引用引用類型作參數(shù)型作參數(shù)引用：它用來引用：它用來給一個一個對象提供一個替代的名字。象提供一個替代的名字。#includevoidmain()inti=5;int&j=i;i=7;couti=ij=ab;s

18、wap(a,b);coutaendlbendl;#includevoidswap(floatm,floatn)floattemp;temp=m;m=n;n=temp;傳地址地址方式方式引用引用類型作參數(shù)型作參數(shù)（1）傳遞引用引用給函數(shù)與函數(shù)與傳遞指指針的效果是一的效果是一樣的，的，形參形參變化化實參也參也發(fā)生生變化化。（2）引用）引用類型作形參，在內(nèi)存中并沒有型作形參，在內(nèi)存中并沒有產(chǎn)生生實參的副本，它參的副本，它直接直接對實參操作參操作；而一般；而一般變量作參數(shù)，形參與量作參數(shù)，形參與實參就占用不同的存參就占用不同的存儲單元，所以形參元，所以形參變量的量的值是是實參參變量的副本。量的副本。因

19、此，當(dāng)因此，當(dāng)參數(shù)參數(shù)傳遞的數(shù)據(jù)量的數(shù)據(jù)量較大大時，用引用，用引用比用一般比用一般變量量傳遞參數(shù)的參數(shù)的時間和空和空間效率都效率都好。好。引用引用類型作形參的三點型作形參的三點說明明（3）指）指針參數(shù)參數(shù)雖然也能達(dá)到與使用引用的效然也能達(dá)到與使用引用的效果，但在被果，但在被調(diào)函數(shù)中需要重復(fù)使用函數(shù)中需要重復(fù)使用“*指指針變量名量名”的形式的形式進(jìn)行運算，行運算，這很容易很容易產(chǎn)生生錯誤且程序的且程序的閱讀性性較差；另一方面，在主差；另一方面，在主調(diào)函數(shù)的函數(shù)的調(diào)用點用點處，必，必須用用變量的地址作量的地址作為實參參。引用引用類型作形參的三點型作形參的三點說明明傳地址地址方式方式數(shù)數(shù)組名作參數(shù)名

20、作參數(shù)#includevoid sub(char);void main（void）char a10=“hello”;sub(a);coutaendl;void sub(char b)b=“world”;傳遞的是數(shù)的是數(shù)組的首地址的首地址對形參數(shù)形參數(shù)組所做的任何改所做的任何改變都將反映到都將反映到實參數(shù)參數(shù)組中中北京林業(yè)大學(xué)信息學(xué)院#include#defineN10intmax(inta);voidmain()inta10;inti,m;for(i=0;iai;m=max(a);coutthemaxnumberis:m;intmax(intb)inti,n;n=b0;for(i=1;iN;i

21、+)if(nbi)n=bi;returnn;用數(shù)用數(shù)組作函數(shù)的參數(shù)，求作函數(shù)的參數(shù)，求10個整數(shù)的最大數(shù)個整數(shù)的最大數(shù)練習(xí)：用數(shù)用數(shù)組作作為函數(shù)的參數(shù)，將數(shù)函數(shù)的參數(shù)，將數(shù)組中中n個整數(shù)按相反的個整數(shù)按相反的順序存序存放，要求放，要求輸入和入和輸出在主函數(shù)中完成出在主函數(shù)中完成#include#defineN10voidsub(intb)inti,j,temp,m;m=N/2;for(i=0;im;i+)j=N-1-i;temp=bi;bi=bj;bj=temp;return;voidmain()inta10,i;for(i=0;iai;sub(a);for(i=0;iN;i+)coutele

22、m=newElemTypeMAXSIZE;/為順序表分配空序表分配空間if(!L-elem)exit(OVERFLOW);/存存儲分配失分配失敗L-length=0;/空表空表長度度為0returnOK;銷毀線性表性表Lvoid DestroyList(SqList&L)if(L.elem)deleteL.elem;/釋放存放存儲空空間清空清空線性表性表LvoidClearList(SqList&L)L.length=0;/將將線性表的性表的長度置度置為0補充：幾個充：幾個簡單基本操作的算法基本操作的算法實現(xiàn)求求線性表性表L的的長度度intGetLength(SqListL)return(L.

23、length);判斷判斷線性表性表L是否是否為空空intIsEmpty(SqListL)if(L.length=0)return1;elsereturn0;補充：幾個充：幾個簡單基本操作的算法基本操作的算法實現(xiàn)1.1.初始化初始化2.2.取值取值3.3.查找查找4.4.插入插入5.5.刪除刪除線性表的重要基本操作性表的重要基本操作int GetElem(SqList L,int i,ElemType&e)if(iL.length)return ERROR;/判斷判斷i值是否合理，若不合理，返回是否合理，若不合理，返回ERROR e=L.elemi-1;/第第i-1的的單元存元存儲著第著第i個數(shù)

24、據(jù)個數(shù)據(jù)return OK;2.取取值（根據(jù)位置（根據(jù)位置i獲取相取相應(yīng)位置數(shù)據(jù)元素的內(nèi)容）位置數(shù)據(jù)元素的內(nèi)容）隨機存取獲取取線性表性表L中的某個數(shù)據(jù)元素的內(nèi)容中的某個數(shù)據(jù)元素的內(nèi)容3.查找找（根據(jù)指定數(shù)據(jù)（根據(jù)指定數(shù)據(jù)獲取數(shù)據(jù)所在的位置）取數(shù)據(jù)所在的位置）順序查找圖示順序查找圖示25 34 57 16 48 09012345data查找查找 16 i25 34 57 16 48 09i25 34 57 16 48 09i25 34 57 16 48 09i查找成功查找成功25 34 57 16 4801234data查找 50i25 34 57 16 48i25 34 57 16 48i25

25、 34 57 16 48i25 34 57 16 48i查找失敗查找失敗3.查找找（根據(jù)指定數(shù)據(jù)（根據(jù)指定數(shù)據(jù)獲取數(shù)據(jù)所在的位置）取數(shù)據(jù)所在的位置）查找算法找算法時間效率分析效率分析？在在線性表性表L中中查找找值為e的數(shù)據(jù)元素的數(shù)據(jù)元素int LocateELem(SqList L,ElemType e)for(i=0;i L.length;i+)if(L.elemi=e)return i+1;return 0;3.查找找（根據(jù)指定數(shù)據(jù)（根據(jù)指定數(shù)據(jù)獲取數(shù)據(jù)所在的位置）取數(shù)據(jù)所在的位置）2512478936141234567892512479989361499插入插入2512478936142

26、51247893614251247893614插第插第 4 個個結(jié)點之前，移點之前，移動 64+1 次次插在第插在第 i 個個結(jié)點之前，移點之前，移動 n-i+1 次次4.插入插入（插在第（插在第 i 個個結(jié)點之前）點之前）（1）判斷）判斷插入位置插入位置i 是否合法是否合法。（2）判斷）判斷順序表的序表的存存儲空空間是否已是否已滿。（3）將第）將第n至第至第i 位的元素依次位的元素依次向后移向后移動一個位置一個位置，空，空出第出第i個位置。個位置。（4）將要插入的新元素）將要插入的新元素e放入第放入第i個位置個位置。（5）表表長加加1，插入成功返回，插入成功返回OK?！舅惴ú剿惴ú襟E】4.在

27、在線性表性表L中第中第i個數(shù)據(jù)元素之前插入數(shù)據(jù)元素個數(shù)據(jù)元素之前插入數(shù)據(jù)元素e StatusListInsert_Sq(SqList&L,inti,ElemTypee)if(iL.length+1)returnERROR;/i值不合法不合法if(L.length=MAXSIZE)returnERROR;/當(dāng)前存當(dāng)前存儲空空間已已滿for(j=L.length-1;j=i-1;j-)L.elemj+1=L.elemj;/插入位置及之后的元素后移插入位置及之后的元素后移L.elemi-1=e;/將新元素將新元素e放入第放入第i個位置個位置+L.length;/表表長增增1returnOK;【算法描

28、述算法描述】若插入在尾若插入在尾結(jié)點之后，點之后，則根本無需移根本無需移動（特（特別快）；快）；若插入在首若插入在首結(jié)點之前，點之前，則表中元素全部后移（特表中元素全部后移（特別慢）；慢）；若要考若要考慮在各種位置插入（共在各種位置插入（共n+1種可能）的平均移種可能）的平均移動次次數(shù)，數(shù)，該如何如何計算？算？算法算法時間主要耗主要耗費在移在移動元素的操作上元素的操作上【算法分析算法分析】251247893614123456789251247361425124736142512473614刪除刪除5.刪除除（刪除第除第 i 個個結(jié)點）點）刪除第除第 4 個個結(jié)點，移點，移動 64 次次刪除第除

29、第 i 個個結(jié)點，移點，移動 n-i 次次（1）判斷）判斷刪除位置除位置i 是否合法是否合法（合法（合法值為1in）。）。（2）將欲）將欲刪除的元素保留在除的元素保留在e中。中。（3）將第）將第i+1至第至第n 位的元素依次位的元素依次向前移向前移動一個位置一個位置。（4）表表長減減1，刪除成功返回除成功返回OK。【算法步算法步驟】5.將將線性表性表L中第中第i個數(shù)據(jù)元素個數(shù)據(jù)元素刪除除StatusListDelete_Sq(SqList&L,inti)if(iL.length)returnERROR;/i值不合法不合法for(j=i;jdata=ai,則則p-next-data=ai+1 *

30、2.5.2 單鏈表基本操作的表基本操作的實現(xiàn)1.1.初始化初始化2.2.取值取值3.3.查找查找4.4.插入插入5.5.刪除刪除 *1.初始化初始化(構(gòu)造一個空表構(gòu)造一個空表)【算法步算法步驟】（1）生成新）生成新結(jié)點作點作頭結(jié)點，用點，用頭指指針L指向指向頭結(jié)點。點。（2）頭結(jié)點的指點的指針域置空。域置空。【算法描述算法描述】StatusInitList_L(LinkList&L)L=newLNode;L-next=NULL;returnOK;*銷毀StatusDestroyList_L(LinkList&L)LinkListp;while(L)p=L;L=L-next;deletep;re

31、turnOK;補充：幾個充：幾個簡單基本操作的算法基本操作的算法實現(xiàn) *清空清空StatusClearList(LinkList&L)/將將L重置重置為空表空表 LinkListp,q;p=L-next;/p指向第一個指向第一個結(jié)點點while(p)/沒到表尾沒到表尾 q=p-next;deletep;p=q;L-next=NULL;/頭結(jié)點指點指針域域為空空 returnOK;補充：幾個充：幾個簡單基本操作的算法基本操作的算法實現(xiàn) *pLa1a2.pi01p2pn=NULLan求表求表長p=L-next;i=0;while(p)i+;p=p-next;補充：幾個充：幾個簡單基本操作的算法基本

32、操作的算法實現(xiàn)“數(shù)數(shù)”結(jié)點：點：指指針p依次指向各個依次指向各個結(jié)點點從第一個元素開始從第一個元素開始“數(shù)數(shù)”一直一直“數(shù)數(shù)”到最后一個到最后一個結(jié)點點 *求表求表長intListLength_L(LinkListL)/返回返回L中數(shù)據(jù)元素個數(shù)中數(shù)據(jù)元素個數(shù)LinkListp;p=L-next;/p指向第一個指向第一個結(jié)點點i=0;while(p)/遍遍歷單鏈表表,統(tǒng)計結(jié)點數(shù)點數(shù)i+;p=p-next;returni;“數(shù)數(shù)”結(jié)點：點：指指針p依次指向各個依次指向各個結(jié)點點從第一個元素開始從第一個元素開始“數(shù)數(shù)”一直一直“數(shù)數(shù)”到最后一個到最后一個結(jié)點點 *判斷表是否判斷表是否為空空intLi

33、stEmpty(LinkListL)/若若L為為空表，空表，則則返回返回1，否，否則則返回返回0 if(L-next)/非空非空 return0;elsereturn1;1.1.初始化初始化2.2.取值取值3.3.查找查找4.4.插入插入5.5.刪除刪除線性表的重要基本操作性表的重要基本操作 *思考：思考：順序表里如何找到第序表里如何找到第i個元素？個元素？鏈表的表的查找：要從找：要從鏈表的表的頭指指針出出發(fā)，順著著鏈域域next逐個逐個結(jié)點往下搜索，直至點往下搜索，直至搜索到第搜索到第i個個結(jié)點點為止。因此，止。因此，鏈表不是表不是隨機存取隨機存取結(jié)構(gòu)構(gòu)2.取取值（根據(jù)位置（根據(jù)位置i獲取相

34、取相應(yīng)位置數(shù)據(jù)元素的內(nèi)容）位置數(shù)據(jù)元素的內(nèi)容）*85L211830754256pppj1 2 3pp1i=3i=156p7例：分例：分別取出表中取出表中i=3和和i=15的元素的元素從第從第1個個結(jié)點（點（L-next）順鏈掃描，用指描，用指針p指向當(dāng)指向當(dāng)前前掃描到的描到的結(jié)點，點，p初初值p=L-next。j做做計數(shù)器，累數(shù)器，累計當(dāng)前當(dāng)前掃描描過的的結(jié)點數(shù)，點數(shù)，j初初值為1。當(dāng)當(dāng)p指向指向掃描到的下一描到的下一結(jié)點點時，計數(shù)器數(shù)器j加加1。當(dāng)當(dāng)j=i時，p所指的所指的結(jié)點就是要找的第點就是要找的第i個個結(jié)點。點?！舅惴ú剿惴ú襟E】*北京林業(yè)大學(xué)信息學(xué)院/獲取取線性表性表L中的某個數(shù)據(jù)元

35、素的內(nèi)容中的某個數(shù)據(jù)元素的內(nèi)容StatusGetElem_L(LinkListL,inti,ElemType&e)p=L-next;j=1;/初始化初始化while(p&jnext;+j;if(!p|ji)returnERROR;/第第i個元素不存在個元素不存在e=p-data;/取第取第i個元素個元素returnOK;/GetElem_L 2.取取值（根據(jù)位置（根據(jù)位置i獲取相取相應(yīng)位置數(shù)據(jù)元素的內(nèi)容）位置數(shù)據(jù)元素的內(nèi)容）*從第一個從第一個結(jié)點起，依次和點起，依次和e相比相比較。如如果果找找到到一一個個其其值與與e相相等等的的數(shù)數(shù)據(jù)據(jù)元元素素，則返返回回其其在在鏈表中的表中的“位置位置”或地

36、址或地址；如如果果查遍遍整整個個鏈表表都都沒沒有有找找到到其其值和和e相相等等的的元元素素，則返回返回0或或“NULL”。L211830753056pj1x=30p2p3找到，返回找到，返回i ix=51p1p6p7未找到，返回03.查找找（根據(jù)指定數(shù)據(jù)（根據(jù)指定數(shù)據(jù)獲取數(shù)據(jù)所在的位置）取數(shù)據(jù)所在的位置）*/在在線性表性表L中中查找找值為e的數(shù)據(jù)元素的數(shù)據(jù)元素LNode*LocateELem_L(LinkListL，Elemtypee)/返回返回L中中值為e的數(shù)據(jù)元素的的數(shù)據(jù)元素的地址地址，查找失找失敗返回返回NULLp=L-next;while(p&p-data!=e)p=p-next;re

37、turnp;【算法描述算法描述】*/在在線性表性表L中中查找找值為e的數(shù)據(jù)元素的數(shù)據(jù)元素intLocateELem_L(LinkListL，Elemtypee)/返回返回L中中值為e的數(shù)據(jù)元素的的數(shù)據(jù)元素的位置序號位置序號，查找失找失敗返回返回0p=L-next;j=1;while(p&p-data!=e)p=p-next;j+;if(p)returnj;elsereturn0;【算法描述算法描述】*將將值為x的新的新結(jié)點插入到表的第點插入到表的第i個個結(jié)點的位點的位置上，即插入到置上，即插入到ai-1與與ai之之間3.插入插入（插在第（插在第 i 個個結(jié)點之前）點之前）s-next=p-ne

38、xt;p-next=s思考：步思考：步驟1和和2能互能互換么？么？*【算法步算法步驟】（1）找到）找到ai-1存存儲位置位置p（2）生成一個新）生成一個新結(jié)點點*s（3）將新）將新結(jié)點點*s的數(shù)據(jù)域置的數(shù)據(jù)域置為x（4）新）新結(jié)點點*s的指的指針域指向域指向結(jié)點點ai（5）令）令結(jié)點點*p的指的指針域指向新域指向新結(jié)點點*s */在在L中第中第i個元素之前插入數(shù)據(jù)元素個元素之前插入數(shù)據(jù)元素e StatusListInsert_L(LinkList&L,inti,ElemTypee)p=L;j=0;while(p&jnext;+j;/尋找第找第i1個個結(jié)點點if(!p|ji1)returnERR

39、OR;/i大于表大于表長+1或者小于或者小于1s=newLNode;/生成新生成新結(jié)點點ss-data=e;/將將結(jié)點點s的數(shù)據(jù)域置的數(shù)據(jù)域置為es-next=p-next;/將將結(jié)點點s插入插入L中中p-next=s;returnOK;/ListInsert_L【算法描述算法描述】*將表的第將表的第i個個結(jié)點點刪去去步步驟：（1）找到）找到ai-1存存儲位置位置p（2）保存要）保存要刪除的除的結(jié)點的點的值（3）令）令p-next指向指向ai的直接后的直接后繼結(jié)點點（4）釋放放結(jié)點點ai的空的空間5.刪除除（刪除第除第 i 個個結(jié)點）點）*5.刪除除（刪除第除第 i 個個結(jié)點）點）*5.刪除除

40、（刪除第除第 i 個個結(jié)點）點）p-next=p-next-next?ai-1ai-1aiaiai+1ai+1pq刪除前刪除前刪除后刪除后 *【算法步算法步驟】（1）找到）找到ai-1存存儲位置位置p（2）臨時保存保存結(jié)點點ai的地址在的地址在q中，以中，以備釋放放（3）令）令p-next指向指向ai的直接后的直接后繼結(jié)點點（4）將）將ai的的值保留在保留在e中中（5）釋放放ai的空的空間 */將將線性表性表L中第中第i個數(shù)據(jù)元素個數(shù)據(jù)元素刪除除StatusListDelete_L(LinkList&L,inti,ElemType&e)p=L;j=0;while(p-next&jnext;+j

41、;if(!(p-next)|ji-1)returnERROR;/刪除位置不合理除位置不合理q=p-next;/臨時保存被保存被刪結(jié)點的地址以點的地址以備釋放放p-next=q-next;/改改變刪除除結(jié)點前點前驅(qū)結(jié)點的指點的指針域域e=q-data;/保存保存刪除除結(jié)點的數(shù)據(jù)域點的數(shù)據(jù)域deleteq;/釋放放刪除除結(jié)點的空點的空間 return OK;/ListDelete_L【算法描述算法描述】*1.查找找:因因線性性鏈表只能表只能順序存取，即在序存取，即在查找找時要要從從頭指指針找起，找起，查找的找的時間復(fù)復(fù)雜度度為O(n)。2.插入和插入和刪除除:因因線性性鏈表不需要移表不需要移動元素

42、，只要元素，只要修改指修改指針，一般情況下，一般情況下時間復(fù)復(fù)雜度度為O(1)。但是，如果要在但是，如果要在單鏈表中表中進(jìn)行前插或行前插或刪除操作，除操作，由于要從由于要從頭查找前找前驅(qū)結(jié)點，所耗點，所耗時間復(fù)復(fù)雜度度為O(n)。鏈表的運算表的運算時間效率分析效率分析 *n從一個空表開始，重復(fù)從一個空表開始，重復(fù)讀入數(shù)據(jù)：入數(shù)據(jù)：u生成新生成新結(jié)點點u將將讀入數(shù)據(jù)存放到新入數(shù)據(jù)存放到新結(jié)點的數(shù)據(jù)域中點的數(shù)據(jù)域中u將將該新新結(jié)點插入到點插入到鏈表的前端表的前端單鏈表的建立（前插法）表的建立（前插法）*p-data=anp-data=an-1L-next=pp-next=L-next單鏈表的建立（

43、前插法）表的建立（前插法）*voidCreateList_F(LinkList&L,intn)L=newLNode;L-next=NULL;/先建立一個先建立一個帶頭結(jié)點的點的單鏈表表for(i=n;i0;-i)p=newLNode;/生成新生成新結(jié)點點cinp-data;/輸入元素入元素值p-next=L-next;L-next=p;/插入到表插入到表頭/CreateList_F【算法描述算法描述】*n從一個空表從一個空表L開始，將新開始，將新結(jié)點逐個插入到點逐個插入到鏈表的尾部，尾指表的尾部，尾指針r指向指向鏈表的尾表的尾結(jié)點。點。n初始初始時，r同同L均指向均指向頭結(jié)點。每點。每讀入一個

44、數(shù)據(jù)元素入一個數(shù)據(jù)元素則申申請一一個新個新結(jié)點，將新點，將新結(jié)點插入到尾點插入到尾結(jié)點后，點后，r指向新指向新結(jié)點。點。單鏈表的建立（尾插法）表的建立（尾插法）*voidCreateList_L(LinkList&L,intn)/正位序正位序輸入入n個元素的個元素的值，建立，建立帶表表頭結(jié)點的點的單鏈表表LL=newLNode;L-next=NULL;r=L;/尾指尾指針r指向指向頭結(jié)點點for(i=0;ip-data;/輸入元素入元素值p-next=NULL;r-next=p;/插入到表尾插入到表尾r=p;/r指向新的尾指向新的尾結(jié)點點/CreateList_L【算法描述算法描述】*2.5.

45、3 循循環(huán)鏈表表L-next=L(a)非空非空單循循環(huán)鏈表表L(b)空表空表L說明明從循從循環(huán)鏈表中的任何一個表中的任何一個結(jié)點的位置都可點的位置都可以找到其他所有以找到其他所有結(jié)點，而點，而單鏈表做不到；表做不到；循環(huán)條件：循環(huán)條件：p!=NULLp!=Lp-next!=NULLp-next!=L循環(huán)鏈表中沒有明顯的尾端循環(huán)鏈表中沒有明顯的尾端 如何避免死循環(huán)如何避免死循環(huán) *對循循環(huán)鏈表，有表，有時不不給出出頭指指針，而，而給出出尾指尾指針可以更方便的找到可以更方便的找到第一個和最后一個第一個和最后一個結(jié)點點reara1ai-1anai如何查找開始結(jié)點和終端結(jié)點？如何查找開始結(jié)點和終端結(jié)點

46、？開始結(jié)點：開始結(jié)點：rear-next-next終端結(jié)點：終端結(jié)點：rear說明明TaTaa a1 1a an nTbTbb b1 1b bn n循循環(huán)鏈表的合并表的合并a a1 1a an nb b1 1b bn npTaTaTbTb示例示例 *a a1 1a an nb b1 1b bn npTaTaTbTbLinkListConnect(LinkListTa,LinkListTb)/假假設(shè)Ta、Tb都是非空的都是非空的單循循環(huán)鏈表表/p存表存表頭結(jié)點點/Tb表表頭連結(jié)Ta表尾表尾/釋放放Tb表表頭結(jié)點點/修改指修改指針returnTb;p=Ta-next;Ta-next=Tb-next

47、-next;deleteTb-next;Tb-next=p;示例示例 *著名猶太歷史學(xué)家著名猶太歷史學(xué)家Josephus在羅馬人占領(lǐng)喬塔帕特后在羅馬人占領(lǐng)喬塔帕特后39個猶太人與個猶太人與Josephus及他的朋友躲及他的朋友躲到一個洞中到一個洞中39個猶太人決定寧愿死也不要被敵人個猶太人決定寧愿死也不要被敵人抓到，于是決定了一個自殺方式抓到，于是決定了一個自殺方式41個人個人排成一個圓圈，由第排成一個圓圈，由第1個人開個人開始報數(shù)，每報數(shù)到第始報數(shù)，每報數(shù)到第3人該人就必須自人該人就必須自殺，然后再由下一個重新報數(shù)，直到殺，然后再由下一個重新報數(shù)，直到所有人都自殺身亡為止所有人都自殺身亡為止

48、然而然而Josephus和他的朋友并不想遵從，和他的朋友并不想遵從，Josephus要他的朋友先假裝遵從，他要他的朋友先假裝遵從，他將朋友與自己安排在第將朋友與自己安排在第16個與第個與第31個個位置，于是逃過了這場死亡游戲位置，于是逃過了這場死亡游戲約瑟夫瑟夫問題例如例如n=8m=3約瑟夫瑟夫問題約約瑟夫瑟夫瑟夫瑟夫問題問題的解法的解法的解法的解法voidJosephus(intn,intm)Firster();/檢驗指指針指向第一個指向第一個結(jié)點點for(inti=0;in-1;i+)/執(zhí)行行n-1次次for(intj=0;jm-1;j+)Next();/循循環(huán)m次使次使current指向

49、被指向被刪除除結(jié)點點cout“出列的人是出列的人是”GetElem_L()next-prior=d-prior-next=dL-next=L *雙向雙向鏈表的插入表的插入 *1.s-prior=p-prior;雙向雙向鏈表的插入表的插入a ab bx x.1 1p ps s *雙向雙向鏈表的插入表的插入1.s-prior=p-prior;2.p-prior-next=s;abx.12ps *雙向雙向鏈表的插入表的插入1.s-prior=p-prior;2.p-prior-next=s;3.s-next=p;*雙向雙向鏈表的插入表的插入4.p-prior=s;abx.1234ps1.s-prio

50、r=p-prior;2.p-prior-next=s;3.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;雙向雙向鏈表的插入表的插入 *雙向雙向鏈表的表的刪除除 *1.p-prior-next=p-next;雙向雙向鏈表的表的刪除除 *雙向雙向鏈表的表的刪除除1.p-prior-next=p-n

51、ext;2.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;雙向雙向鏈表的表的刪除除北京林業(yè)大學(xué)信息學(xué)院2.6 順序表和序表和鏈表的比表的比較存儲結(jié)構(gòu)比較項目順序表鏈表空間存儲空間預(yù)先分配，會導(dǎo)致空間閑置或溢出現(xiàn)象動態(tài)分配，不會出現(xiàn)存儲空間閑置或溢出現(xiàn)象存儲密度不用為表示結(jié)點間的邏輯關(guān)系而增加額外

52、的存儲開銷，存儲密度等于1需要借助指針來體現(xiàn)元素間的邏輯關(guān)系，存儲密度小于1時間存取元素隨機存取，按位置訪問元素的時間復(fù)雜度為O(1)順序存取，按位置訪問元素時間復(fù)雜度為O(n)插入、刪除平均移動約表中一半元素，時間復(fù)雜度為O(n)不需移動元素，確定插入、刪除位置后，時間復(fù)雜度為O(n)適用情況 表長變化不大，且能事先確定變化的范圍 很少進(jìn)行插入或刪除操作，經(jīng)常按元素位置序號訪問數(shù)據(jù)元素 長度變化較大 頻繁進(jìn)行插入或刪除操作 *2.7 線性表的性表的應(yīng)用用線線性表的合并性表的合并性表的合并性表的合并有序表的合并有序表的合并有序表的合并有序表的合并1 12 2 *2.7.1 線性表的合并性表的合

53、并問題描述：描述：假假設(shè)利用兩個利用兩個線性表性表La和和Lb分分別表示兩表示兩個集合個集合A和和B,現(xiàn)要求一個新的集合要求一個新的集合 A=ABLa=(7,5,3,11)Lb=(2,6,3)La=(7,5,3,11,2,6).*依次取出依次取出Lb 中的每個元素，中的每個元素，執(zhí)行以下操作：行以下操作：在在La中中查找找該元素元素如果找不到，如果找不到，則將其插入將其插入La的最后的最后【算法步算法步驟】*voidunion(List&La,ListLb)La_len=ListLength(La);Lb_len=ListLength(Lb);for(i=1;i=Lb_len;i+)GetEl

54、em(Lb,i,e);if(!LocateElem(La,e)ListInsert(&La,+La_len,e);【算法描述算法描述】*問題描述：描述：已已知知線性性表表La 和和Lb中中的的數(shù)數(shù)據(jù)據(jù)元元素素按按值非非遞減減有有序序排排列列,現(xiàn)要要求求將將La和和Lb歸并并為一一個個新新的的線性性表表Lc,且且Lc中的數(shù)據(jù)元素仍按中的數(shù)據(jù)元素仍按值非非遞減有序排列減有序排列.La=(1,7,8)Lb=(2,4,6,8,10,11)Lc=(1,2,4,6,7,8,8,10,11).2.7.2 有序表的合并有序表的合并 *(1)創(chuàng)建一個空表建一個空表Lc(2)依次從依次從 La 或或 Lb 中中“

55、摘取摘取”元素元素值較小小的的結(jié)點插入到點插入到 Lc 表的最后，直至其中一個表表的最后，直至其中一個表變空空為止止(3)繼續(xù)將將 La 或或 Lb 其中一個表的剩余其中一個表的剩余結(jié)點點插入在插入在 Lc 表的最后表的最后【算法步算法步驟】有序的有序的順序表合并序表合并 *voidMergeList_Sq(SqListLA,SqListLB,SqList&LC)pa=LA.elem;pb=LB.elem;/指指針pa和和pb的初的初值分分別指向兩個表的第一個元素指向兩個表的第一個元素LC.length=LA.length+LB.length;/新表新表長度度為待合并兩表的待合并兩表的長度之和

56、度之和LC.elem=newElemTypeLC.length;/為合并后的新表分配一個數(shù)合并后的新表分配一個數(shù)組空空間pc=LC.elem;/指指針pc指向新表的第一個元素指向新表的第一個元素pa_last=LA.elem+LA.length-1;/指指針pa_last指向指向LA表的最后一個元素表的最后一個元素pb_last=LB.elem+LB.length-1;/指指針pb_last指向指向LB表的最后一個元素表的最后一個元素while(pa=pa_last&pb=pb_last)/兩個表都非空兩個表都非空if(*pa=*pb)*pc+=*pa+;/依次依次“摘取摘取”兩表中兩表中值較

57、小的小的結(jié)點點else*pc+=*pb+;while(pa=pa_last)*pc+=*pa+;/LB表已到達(dá)表尾表已到達(dá)表尾while(pbdatadata)pc-next=pa;*PaLa(Lc)17824681011Lbpb有序有序鏈表合并表合并(pa-datadata)pc-next=pa;pc=pa;1Pc *La(Lc)17824681011Lbpb有序有序鏈表合并表合并(pa-datadata)pc-next=pa;pc=pa;1Pcpa=pa-next;Pa *La(Lc)17824681011Lbpb有序有序鏈表合并表合并(pa-datapb-data)pc-next=pb;

58、1Pcpa *La(Lc)17824681011Lbpb有序有序鏈表合并表合并(pa-datapb-data)pc-next=pb;1paPcpc=pb;2 *La(Lc)17824681011Lb有序有序鏈表合并表合并(pa-datapb-data)pc-next=pb;1paPcpc=pb;2pb=pb-next;pb *La(Lc)12467881011有序有序鏈表合并表合并pc-next=pa?pa:pb;pa(NULL)pbpc *La(Lc)12467881011合并后合并后delete Lb;有序有序鏈表合并表合并 *voidMergeList_L(LinkList&La,Lin

59、kList&Lb,LinkList&Lc)pa=La-next;pb=Lb-next;pc=Lc=La;/用用La的的頭結(jié)點作點作為Lc的的頭結(jié)點點while(pa&pb)if(pa-datadata)pc-next=pa;pc=pa;pa=pa-next;elsepc-next=pb;pc=pb;pb=pb-next;pc-next=pa?pa:pb;/插入剩余段插入剩余段deleteLb;/釋放放Lb的的頭結(jié)點點T(n)=S(n)=O(1)【算法描述算法描述】有序的有序的鏈表合并表合并 *思考思考1：要求合并后的表無重復(fù)數(shù)據(jù)，如何：要求合并后的表無重復(fù)數(shù)據(jù)，如何實現(xiàn)？提示：要提示：要單獨考

60、獨考慮pa-data=pb-dataLa(Lc)12467881011 *要求要求結(jié)果果鏈表仍使用原來兩個表仍使用原來兩個鏈表的存表的存儲空空間,不另外占用其它的存不另外占用其它的存儲空空間。表中允表中允許有重復(fù)的數(shù)據(jù)。有重復(fù)的數(shù)據(jù)。思考思考2：將兩個非：將兩個非遞減的有序減的有序鏈表合并表合并為一個非一個非遞增的有序增的有序鏈表，如何表，如何實現(xiàn)？*(1)Lc指向指向La(2)依次從依次從 La 或或 Lb 中中“摘取摘取”元素元素值較小小的的結(jié)點插入到點插入到 Lc 表的表的表表頭結(jié)點之后點之后，直至其，直至其中一個表中一個表變空空為止止(3)繼續(xù)將將 La 或或 Lb 其中一個表的剩余其

61、中一個表的剩余結(jié)點點插入在插入在 Lc 表的表的表表頭結(jié)點之后點之后(4)釋放放 Lb 表的表表的表頭結(jié)點點【算法步算法步驟】2.8 2.8 案例分析與實現(xiàn)案例分析與實現(xiàn)案例案例案例案例2.1 2.1 2.1 2.1：一元多項式的運算：一元多項式的運算：一元多項式的運算：一元多項式的運算指數(shù)（下標(biāo)i）01234系數(shù)pi105-432P(x)=10+5x-4x2+3x3+2x4數(shù)組表示數(shù)組表示（每一（每一項的指數(shù)的指數(shù)i隱含含在其系數(shù)在其系數(shù)pi的序號中）的序號中）Rn(x)=Pn(x)+Qm(x)線性表線性表R=(p0+q0,p1+q1,p2+q2,pm+qm,pm+1,pn)北京林業(yè)大學(xué)信息

62、學(xué)院下標(biāo)i0123下標(biāo)i012系數(shù)ai7395系數(shù)bi822-9指數(shù)01817指數(shù)178多項式非零項非零項的數(shù)組表示（a）A(x)=7+3x+9x8+5x17 （b）B(x)=8x+22x79x8線性表線性表P=(p1,e1),(p2,e2),(pm,em)l創(chuàng)建一個創(chuàng)建一個新數(shù)組新數(shù)組c cl分別從頭遍歷比較分別從頭遍歷比較a a和和b b的每一項的每一項指數(shù)相同指數(shù)相同，對應(yīng)系數(shù)相加，若其和不為零，則在，對應(yīng)系數(shù)相加，若其和不為零，則在c c中增加一個新項中增加一個新項指數(shù)不相同指數(shù)不相同，則將指數(shù)較小的項復(fù)制到，則將指數(shù)較小的項復(fù)制到c c中中l(wèi)一個多項式已遍歷一個多項式已遍歷完畢完畢時

63、，將另一個剩余項依次復(fù)制到時，將另一個剩余項依次復(fù)制到c c中即可中即可案例案例案例案例2.2 2.2 2.2 2.2：稀疏多項式的運算：稀疏多項式的運算：稀疏多項式的運算：稀疏多項式的運算A17(x)=7+3x+9x8+5x17B8(x)=8x+22x7-9x8-1703198517-181227-98ABl順序存儲結(jié)構(gòu)存在問題順序存儲結(jié)構(gòu)存在問題存儲空間分配不靈活存儲空間分配不靈活運算的空間復(fù)雜度高運算的空間復(fù)雜度高鏈?zhǔn)酱鎯Y(jié)構(gòu)鏈?zhǔn)酱鎯Y(jié)構(gòu)typedefstructPNodefloatcoef;/系數(shù)系數(shù)intexpn;/指數(shù)指數(shù)structPNode*next;/指指針域域PNode,*

64、Polynomial;創(chuàng)建一個只有頭結(jié)點的空鏈表。根據(jù)多項式的項的個數(shù)n，循環(huán)n次執(zhí)行以下操作：l生成一個新結(jié)點*s；l輸入多項式當(dāng)前項的系數(shù)和指數(shù)賦給新結(jié)點*s的數(shù)據(jù)域；l設(shè)置一前驅(qū)指針pre，用于指向待找到的第一個大于輸入項指數(shù)的結(jié)點的前驅(qū)，pre初值指向頭結(jié)點；l指針q初始化，指向首元結(jié)點；l循鏈向下逐個比較鏈表中當(dāng)前結(jié)點與輸入項指數(shù)，找到第一個大于輸入項指數(shù)的結(jié)點*q；l將輸入項結(jié)點*s插入到結(jié)點*q之前。多項式創(chuàng)建多項式創(chuàng)建-【算法步驟算法步驟】voidCreatePolyn(Polynomial&P,intn)/輸入入m項的系數(shù)和指數(shù)，建立表示多的系數(shù)和指數(shù)，建立表示多項式的有序式

65、的有序鏈表表PP=newPNode;P-next=NULL;/先建立一個先建立一個帶頭結(jié)點的點的單鏈表表for(i=1;is-coefs-expn;/輸入系數(shù)和指數(shù)入系數(shù)和指數(shù)pre=P;/pre用于保存用于保存q的前的前驅(qū)，初，初值為頭結(jié)點點q=P-next;/q初始化，指向首元初始化，指向首元結(jié)點點while(q&q-expnexpn)/找到第一個大于找到第一個大于輸入入項指數(shù)的指數(shù)的項*qpre=q;q=q-next;/whiles-next=q;/將將輸入入項s插入到插入到q和其前和其前驅(qū)結(jié)點點pre之之間pre-next=s;/for多項式創(chuàng)建多項式創(chuàng)建-【算法描述算法描述】A17(

66、x)=7+3x+9x8+5x17B8(x)=8x+22x7-9x8-1703198517-181227-98ABpapb多項式相加多項式相加A17(x)=7+3x+9x8+5x17B8(x)=8x+22x7-9x8-1703198517-181227-98ABpapb多項式相加多項式相加A17(x)=7+3x+9x8+5x17B8(x)=8x+22x7-9x8-17011198517-181227-98ABpapb多項式相加多項式相加A17(x)=7+3x+9x8+5x17B8(x)=8x+22x7-9x8-17011198517-181227-98ABpapbA17(x)=7+3x+9x8+5x17B8(x)=8x+22x79x8 指針p1和p2初始化，分別指向Pa和Pb的首元結(jié)點。p3指向和多項式的當(dāng)前結(jié)點，初值為Pa的頭結(jié)點。當(dāng)指針p1和p2均未到達(dá)相應(yīng)表尾時，則循環(huán)比較p1和p2所指結(jié)點對應(yīng)的指數(shù)值（p1-expn與p2-expn），有下列3種情況：當(dāng)p1-expn等于p2-expn時，則將兩個結(jié)點中的系數(shù)相加，若和不為零，則修改p1所指結(jié)點的系數(shù)值，同時刪除p2所指結(jié)點，若和