1、1第1章 緒論本章學(xué)習(xí)內(nèi)容:1.1 什么是數(shù)據(jù)結(jié)構(gòu) 1.2 算法描述 1.3 算法分析21.1 什么是數(shù)據(jù)結(jié)構(gòu)1.1.1 數(shù)據(jù)結(jié)構(gòu)示例學(xué)號(hào)姓名性別籍貫電話通訊地址01張三男長(zhǎng)沙8639000麓山南路327號(hào)02李四男北京23456789學(xué)院路435號(hào)03王五女廣州30472589天河路478號(hào)04趙六男上海41237568南京路1563號(hào)05錢七女南京5013472南京大學(xué)06劉八女武漢61543726武漢大學(xué)07朱九男昆明4089651云南大學(xué)08孫十女杭州6154372西湖路635號(hào)【例1-1】給出一張學(xué)生數(shù)據(jù)表 如下:3在學(xué)生表中，一行為一個(gè)學(xué)生信息，代表一個(gè)學(xué)生數(shù)據(jù)，一列為一個(gè)屬性，整

2、個(gè)二維表格形成學(xué)生數(shù)據(jù)的一個(gè)線性序列，每個(gè)學(xué)生排列的位置有先后次序，它們之間形成一種線性關(guān)系，是一種典型的數(shù)據(jù)結(jié)構(gòu)（線性結(jié)構(gòu)），我們將它稱為線性表?！纠?-2】描述一個(gè)磁盤的目錄及文件結(jié)構(gòu)，包含一個(gè)根目錄，若干個(gè)一級(jí)子目錄（文件夾），每個(gè)一級(jí)子目錄中又包含若干個(gè)二級(jí)子目錄（子文件夾），如下所示: 在此種結(jié)構(gòu)中，數(shù)據(jù)之間呈現(xiàn)一對(duì)多的非線性關(guān)系，也是我們常用的一種數(shù)據(jù)結(jié)構(gòu)（非線性結(jié)構(gòu)），我們將它稱為樹形結(jié)構(gòu)。4【例1-3】描述一個(gè)大學(xué)的校園網(wǎng)，（圓圈代表站點(diǎn)，邊表示網(wǎng)線）如下所示。在此種結(jié)構(gòu)中，數(shù)據(jù)之間呈現(xiàn)多對(duì)多的非線性關(guān)系，這也是我們常用的一種數(shù)據(jù)結(jié)構(gòu)（非線性結(jié)構(gòu)），我們將它稱為圖形結(jié)構(gòu)。51.

3、1.2 基本術(shù)語(yǔ)1數(shù)據(jù)（data）數(shù)據(jù)是指能夠輸入到計(jì)算機(jī)中，并被計(jì)算機(jī)識(shí)別和處理的符號(hào)的集合。例如：數(shù)字、字母、漢字、圖形、圖像、聲音都稱為數(shù)據(jù)。2數(shù)據(jù)元素（data element）數(shù)據(jù)元素是組成數(shù)據(jù)的基本單位。數(shù)據(jù)元素是一個(gè)數(shù)據(jù)整體中相對(duì)獨(dú)立的單位，但它還可以分割成若干個(gè)具有不同屬性的項(xiàng)（字段），故不是組成數(shù)據(jù)的最小單位。3數(shù)據(jù)對(duì)象（data object）數(shù)據(jù)對(duì)象是性質(zhì)相同的數(shù)據(jù)元素組成的集合，是數(shù)據(jù)的一個(gè)子集。例如，整數(shù)數(shù)據(jù)對(duì)象的集合可表示為N=0,1,2.，大寫字母字符數(shù)據(jù)對(duì)象的集合可表示為C=A, B,Z。64數(shù)據(jù)類型（data type）數(shù)據(jù)是一組性質(zhì)相同的值的集合以及定義于這

4、個(gè)值集合上的一組操作的總稱。例如，高級(jí)語(yǔ)言中用到的整數(shù)數(shù)據(jù)類型，是指由-3276832767中的整數(shù)數(shù)值構(gòu)成的集合及一組操作（加、減、乘、除、乘方等）的總稱。5抽象數(shù)據(jù)類型（Abstract Data Types）抽象數(shù)據(jù)類型通常是指由用戶定義，用以表示應(yīng)用問(wèn)題的數(shù)據(jù)模型，抽象數(shù)據(jù)類型由基本數(shù)據(jù)類型組成，并包括一組相關(guān)的操作。抽象數(shù)據(jù)類型有些類似于C語(yǔ)言中的struct類型和pascal語(yǔ)言中的record類型，但它增加了相關(guān)的操作。在本書中，描述一種抽象數(shù)據(jù)類型將采用如下書寫格式：ADT is Data: Operation:END7【例1-4】 給出自然數(shù)（Natural Number）的

5、抽象數(shù)據(jù)類型定義。ADT Natural Number isData:一個(gè)整數(shù)的有序子集合，它開(kāi)始于0，終止于機(jī)器能表示的最大整數(shù)（MAXINT）。Operation:對(duì)于所有x,y Natural Number，定義如下操作：add(x,y)求XYsub(x,y)求XYmul(x,y)求XYdiv(x,y)求XYequal(x,y)判斷X，Y是否相等end81.1.3 數(shù)據(jù)結(jié)構(gòu)1數(shù)據(jù)結(jié)構(gòu)（data structure）數(shù)據(jù)結(jié)構(gòu)是指相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素所組成的集合。具體來(lái)說(shuō)，數(shù)據(jù)結(jié)構(gòu)包含三個(gè)方面的內(nèi)容，即數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)和對(duì)數(shù)據(jù)所施加的運(yùn)算。這三個(gè)方面的關(guān)系為

6、：（1）數(shù)據(jù)的邏輯結(jié)構(gòu)獨(dú)立于計(jì)算機(jī)，是數(shù)據(jù)本身所固有的。（2）存儲(chǔ)結(jié)構(gòu)是邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)器中的映像，必須依賴于計(jì)算機(jī)。（3）運(yùn)算是指所施加的一組操作總稱。運(yùn)算的定義直接依賴于邏輯結(jié)構(gòu)，但運(yùn)算的實(shí)現(xiàn)必依賴于存儲(chǔ)結(jié)構(gòu)。比如，例1-1提到的學(xué)生數(shù)據(jù)表，除了有8個(gè)學(xué)生的數(shù)據(jù)外，還存在著一對(duì)一的線性關(guān)系，例1-2提到的磁盤目錄及文件結(jié)構(gòu)，除包含文件數(shù)據(jù)外，還存在著目錄之間一對(duì)多的非線性關(guān)系，例1-3提到的大學(xué)校園網(wǎng)，除包含站點(diǎn)數(shù)據(jù)外，還存在著站點(diǎn)間的多對(duì)多的非線性關(guān)系。92從邏輯結(jié)構(gòu)劃分?jǐn)?shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)從邏輯結(jié)構(gòu)劃分為：（1）線性結(jié)構(gòu)元素之間為一對(duì)一的線性關(guān)系，第一個(gè)元素?zé)o直接前驅(qū)，最后一個(gè)元素?zé)o直

7、接后繼，其余元素都有一個(gè)直接前驅(qū)和直接后繼。（2）非線性結(jié)構(gòu)元素之間為一對(duì)多或多對(duì)多的非線性關(guān)系，每個(gè)元素有多個(gè)直接前驅(qū)或多個(gè)直接后繼。（3）集合結(jié)構(gòu)元素之間無(wú)任何關(guān)系，元素的排列無(wú)任何順序。3從存儲(chǔ)結(jié)構(gòu)劃分?jǐn)?shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)從存儲(chǔ)結(jié)構(gòu)劃分為：（1）順序存儲(chǔ)（向量存儲(chǔ)）所有元素存放在一片連續(xù)的存儲(chǔ)單元中，邏輯上相鄰的元素存放到計(jì)算機(jī)內(nèi)存中仍然相鄰。10（2）鏈?zhǔn)酱鎯?chǔ)所有元素存放在可以不連續(xù)的存儲(chǔ)單元中，但元素之間的關(guān)系可以通過(guò)地址確定，邏輯上相鄰的元素存放到計(jì)算機(jī)內(nèi)存后不一定是相鄰的。4數(shù)據(jù)結(jié)構(gòu)的抽象描述數(shù)據(jù)結(jié)構(gòu)可用二元組D=(K,R)的形式來(lái)描述。其中，K=a1,a2,an為元素集合，R=r1

8、,r2,rm為關(guān)系的集合?！纠?-5】設(shè)有一個(gè)線性表（a1,a2,a3,a4,a5），它的抽象描述可表示為D=(K,R)，其中K=a1,a2,a3,a4,a5，R=,，則它的邏輯結(jié)構(gòu)的圖形描述如下。（3）索引存儲(chǔ)使用該方法存放元素的同時(shí)，還建立附加的索引表，索引表中的每一項(xiàng)稱為索引項(xiàng)，索引項(xiàng)的一般形式是：（關(guān)鍵字，地址），其中的關(guān)鍵字是能惟一標(biāo)識(shí)一個(gè)結(jié)點(diǎn)的那些數(shù)據(jù)項(xiàng)。（4）散列存儲(chǔ)通過(guò)構(gòu)造散列函數(shù)，用函數(shù)的值來(lái)確定元素存放的地址11【例1-6】設(shè)一個(gè)數(shù)據(jù)結(jié)構(gòu)的抽象描述為D=(K,R)，其中K=a,b,c,d,e,f,g,h，r=, ,，則它的邏輯結(jié)構(gòu)的圖形描述如下?！纠?-7】設(shè)一個(gè)數(shù)據(jù)結(jié)構(gòu)的

9、抽象描述為D=(K,R)，其中K=1,2,3,4，而R=(1,2),(1,3), (1,4),(2,3),(2,4),(3,4)，則它的邏輯結(jié)構(gòu)的圖形描述如下。121.2 算法描述1.2.1 基本概念1算法（algorithm）通俗地講，算法就是一種解題的方法。更嚴(yán)格地說(shuō)，算法是由若干條指令組成的有窮序列，它必須滿足下述條件（也稱為算法的五大特性）：（1）輸入：具有0個(gè)或多個(gè)輸入的外界量（算法開(kāi)始前的初始量）。（2）輸出：至少產(chǎn)生一個(gè)輸出，它們是算法執(zhí)行完后的結(jié)果。（3）有窮性：每條指令的執(zhí)行次數(shù)必須是有限的。（4）確定性：每條指令的含義都必須明確，無(wú)二義性。（5）可行性：每條指令的執(zhí)行時(shí)間都

10、是有限的。132算法和程序的關(guān)系算法的含義與程序十分相似，但二者是有區(qū)別的。一個(gè)程序不一定滿足有窮性（死循環(huán)），另外，程序中的指令必須是機(jī)器可執(zhí)行的，而算法中的指令則無(wú)此限制。一個(gè)算法若用計(jì)算機(jī)語(yǔ)言來(lái)書寫，則它就可以是一個(gè)程序。1.2.2 算法描述1用流程圖描述算法一個(gè)算法可以用流程圖的方式來(lái)描述，輸入輸出、判斷、處理分別用不同的框圖表示，用箭頭表示流程的流向。這是一種描述算法的較好方法，目前在一些高級(jí)語(yǔ)言程序設(shè)計(jì)中仍然采用。2用自然語(yǔ)言描述算法用我們?nèi)粘Ｉ钪械淖匀徽Z(yǔ)言（可以是中文形式，也可以是英文形式）也可以描述算法。143用其他方式描述算法我們還可以用數(shù)學(xué)語(yǔ)言或約定的符號(hào)語(yǔ)言來(lái)描述算法。

11、4用C語(yǔ)言描述算法在本教材中，我們將采用C語(yǔ)言或類C語(yǔ)言來(lái)描述算法。用C語(yǔ)言描述算法遵循如下規(guī)則：（1）所有算法的描述都用C語(yǔ)言中的函數(shù)形式函數(shù)類型 函數(shù)名(形參及類型說(shuō)明) 函數(shù)語(yǔ)句部分return(表達(dá)式值)； （2）函數(shù)中的形式參數(shù)有兩種傳值方式若為一般變量名，則為單向傳值參數(shù)，若在變量前面增加“&”符號(hào)，則為雙向傳地址參數(shù)。例如有一個(gè)函數(shù)為void swap(&i, &j,k)，則i，j為雙向傳地址參數(shù)，k為單向傳值參數(shù)。15（3）輸入函數(shù)C語(yǔ)言中的輸入函數(shù)調(diào)用為: scanf(“格式控制”,地址列表)。（4）輸出函數(shù)C語(yǔ)言中的輸出函數(shù)調(diào)用為:printf(“格式控制”,變量列表)。（

12、5）C的作用域在C中，每個(gè)變量都有一個(gè)作用域。在函數(shù)內(nèi)聲明的變量，僅能在該函數(shù)內(nèi)部有效，在類中聲明的變量，可以在該類內(nèi)部有效。在整個(gè)程序中都能使用的變量，為全局變量，否則稱為局部變量。若一個(gè)全局變量與一個(gè)局部變量同名，則該范圍內(nèi)全局變量不起作用。161.3 算法分析求解同一個(gè)問(wèn)題，可以有許多不同的算法，那么怎樣來(lái)衡量這些算法的優(yōu)劣呢？首要的條件是選用的算法必須是正確的，其次，考慮如下三點(diǎn)：（1）執(zhí)行算法所耗費(fèi)的時(shí)間。（2）執(zhí)行算法所占用的內(nèi)存開(kāi)銷（主要考慮占用的輔助存儲(chǔ)空間）。（3）算法應(yīng)易于理解，易于編碼，易于調(diào)試等。171.3.1 時(shí)間復(fù)雜度1時(shí)間頻度一個(gè)算法執(zhí)行所耗費(fèi)的時(shí)間，從理論上是不

13、能算出來(lái)的，必須上機(jī)運(yùn)行測(cè)試才能知道。但我們不可能也沒(méi)有必要對(duì)每個(gè)算法都上機(jī)測(cè)試（因?yàn)?，?jì)算機(jī)的運(yùn)行速度與CPU等因素有關(guān)。同一算法在不同的計(jì)算機(jī)上運(yùn)行的時(shí)間是不同的），只需知道在相同的條件下，哪個(gè)算法花費(fèi)的時(shí)間多，哪個(gè)算法花費(fèi)的時(shí)間少就可以了。并且一個(gè)算法花費(fèi)的時(shí)間與算法中語(yǔ)句的執(zhí)行次數(shù)成正比，哪個(gè)算法中語(yǔ)句執(zhí)行次數(shù)多，它花費(fèi)的時(shí)間就多。一個(gè)算法中的語(yǔ)句執(zhí)行次數(shù)稱為語(yǔ)句頻度或時(shí)間頻度，記為T(n)?！纠?-8】求下列算法段的語(yǔ)句頻度。for(i=1; i=n; i+)for(j =1; j=i ; j+)x=x+1;分析：該算法為一個(gè)二重循環(huán)，執(zhí)行次數(shù)為內(nèi)、外循環(huán)次數(shù)相乘，但內(nèi)循環(huán)次數(shù)不固定

14、，與外循環(huán)有關(guān)，因此，時(shí)間頻度T(n)=1+2+3+n= 。182時(shí)間復(fù)雜度在剛才提到的時(shí)間頻度中，n稱為問(wèn)題的規(guī)模，當(dāng)n不斷變化時(shí)，時(shí)間頻度T(n)也會(huì)不斷變化。但有時(shí)我們想知道它變化時(shí)呈現(xiàn)什么規(guī)律，為此，引入時(shí)間復(fù)雜度概念。設(shè)T(n)的一個(gè)輔助函數(shù)為g(n)，定義為當(dāng)n大于等于某一足夠大的正整數(shù)n0時(shí)，存在兩個(gè)正的常數(shù)A和B（其中AB），使得A B均成立，或有 = A，（其中A為常數(shù)），則稱g(n)是T(n)的同數(shù)量級(jí)函數(shù)。把T(n)表示成數(shù)量級(jí)的形式為：T(n)=(g(n),其中大寫字母為英文Order（即數(shù)量級(jí)）一詞的第一個(gè)字母。例如，若T(n)= ，則有 = ，故它的時(shí)間復(fù)雜度為(n

15、2)，即(n)與n2數(shù)量級(jí)相同。19【例1-9】分析下列算法段的時(shí)間頻度及時(shí)間復(fù)雜度。for （i=1;i=n;i+） for (j=1;j=i;j+) for ( k=1;k0時(shí)稱為非空表。通常將非空的線性表記為（a1，a2，an），其中的數(shù)據(jù)元素ai（1in）是一個(gè)抽象的符號(hào)，其具體含義在不同情況下是不同的，即它的數(shù)據(jù)類型可以根據(jù)具體情況而定，本書中，我們將它的類型設(shè)定為elemtype，表示某一種具體的已知數(shù)據(jù)類型。242線性表的特征從線性表的定義可以看出線性表的特征：（1）有且僅有一個(gè)開(kāi)始結(jié)點(diǎn)（表頭結(jié)點(diǎn)）a1，它沒(méi)有直接前驅(qū)，只有一個(gè)直接后繼；（2）有且僅有一個(gè)終端結(jié)點(diǎn)（表尾結(jié)點(diǎn)）an

16、，它沒(méi)有直接后繼，只有一個(gè)直接前驅(qū)；（3）其他結(jié)點(diǎn)都有一個(gè)直接前驅(qū)和直接后繼；（ 4）元素之間為一對(duì)一的線性關(guān)系。因此，線性表是一種典型的線性結(jié)構(gòu)，用二元組表示為：linear_list=(A,R)其中A=ai 1in,n0,aielemtypeR=rr= 1in-1對(duì)應(yīng)的邏輯結(jié)構(gòu)圖如下所示。252.1.2 線性表的運(yùn)算給出了線性表的邏輯結(jié)構(gòu)后，就可以直接定義它的一些基本運(yùn)算，但這些運(yùn)算要實(shí)現(xiàn)，還必須依賴于具體的存儲(chǔ)結(jié)構(gòu)。常見(jiàn)線性表的運(yùn)算有：（1）置空表 setnull(&L)：將線性表L置成空表。（2）求長(zhǎng)度 Length(L)：求給定線性表L的長(zhǎng)度。（3）取元素 Get（L,i）：若1il

17、ength(L)，則取第i個(gè)位置上的元素，否則取得的元素為NULL。 （4）求直接前驅(qū) Prior(L,x)：求線性表L中元素值為x的直接前驅(qū)，若x為第一個(gè)元素，前驅(qū)為NULL。（5）求直接后繼 Next（L,x）：求線性表L中元素值為x的直接后繼，若x為最后一個(gè)元素，后繼為NULL。（6）定位函數(shù) Locate(L,x)：在線性表L中查找值為x的元素位置，若有多個(gè)值為x，則以第一個(gè)為準(zhǔn)，若沒(méi)有，位置為0。（7）插入 Insert(&L,x,i)：在線性表L中第i個(gè)位置上插入值為x的元素。（8）刪除 Dele（&L,i）：刪除線性表L中第i個(gè)位置上的元素。262.1.3 線性表的抽象數(shù)據(jù)類型描

18、述上述這些操作可用抽象數(shù)據(jù)類型描述為：ADT Linearlist isData:一個(gè)線性表L定義為L(zhǎng)=(a1,a2,an)，當(dāng)L=()時(shí)定義為一個(gè)空表。Operation:void setnull(&L)/將線性表L置成空表int Length(L)/求給定線性表L的長(zhǎng)度elemtype Get(L,i)/取線性表L第i個(gè)位置上的元素elemtype Prior(L,x)/求線性表L中元素值為x的直接前驅(qū)elemtype Next(L,x)/求線性表L中元素值為x的直接后繼int Locate(L,x)/在線性表L中查找值為x的元素位置void Insert(&L,x,i)/在線性表L中第i

19、個(gè)位置上插入值為x的元素void Dele(&L,i)/刪除線性表L中第i個(gè)位置上的元素END Linearlist27【例2-1】假設(shè)線性表L=(23,56,89,76,18)，i=3，x=56，y=88，則對(duì)L的一組操作及結(jié)果如下：Length(L) /所得結(jié)果為5Get(L,i) /所得結(jié)果為89Prior(L,x) /所得結(jié)果為23Next(L,x) /所得結(jié)果為89Locate(L,x) /所得結(jié)果為2Insert(&L,y,i) /所得結(jié)果為(23,56,88,89,76,18)Dele(&L,i+1) /所得結(jié)果為(23,56,88,76,18)282.2 線性表的順序存儲(chǔ)結(jié)構(gòu)2

20、.2.1 順序表結(jié)構(gòu)線性表的順序存儲(chǔ)結(jié)構(gòu)，也稱為順序表。其存儲(chǔ)方式為：在內(nèi)存中開(kāi)辟一片連續(xù)存儲(chǔ)空間，但該連續(xù)存儲(chǔ)空間的大小要大于或等于順序表的長(zhǎng)度，然后讓線性表中第一個(gè)元素存放在連續(xù)存儲(chǔ)空間的第一個(gè)位置，第二個(gè)元素緊跟在第一個(gè)之后，其余依此類推。顯然，利用順序表來(lái)存儲(chǔ)線性表，表中相鄰的元素存儲(chǔ)在計(jì)算機(jī)內(nèi)的位置也相鄰，故可以借助數(shù)據(jù)元素在計(jì)算機(jī)內(nèi)的物理位置相鄰來(lái)表示線性表中數(shù)據(jù)元素之間線性邏輯關(guān)系。假設(shè)線性表中元素為(a1,a2,.,an)，設(shè)第一個(gè)元素a1的內(nèi)存地址為L(zhǎng)OC(a1)，而每個(gè)元素在計(jì)算機(jī)內(nèi)占d個(gè)存儲(chǔ)單元，則第i個(gè)元素ai的地址為L(zhǎng)OC(ai)=LOC(a1)+(i-1)d （其中

21、1in）。29從上面的公式可知，該存儲(chǔ)結(jié)構(gòu)類似于高級(jí)語(yǔ)言中的一維數(shù)組存儲(chǔ)結(jié)構(gòu)（即向量結(jié)構(gòu)），適合于隨機(jī)訪問(wèn)，于是可用C語(yǔ)言描述為：#define maxsize Maxlen /Maxlen表示線性表允許的最大長(zhǎng)度struct sequenlist elemtype amaxsize; /表示線性表(a1,a2,an,aMaxlen), elemtype表示某種具體數(shù)據(jù)類型 int len; /len表示線性表的實(shí)際長(zhǎng)度 ;所定義的運(yùn)算函數(shù)如下: int length(struct sequenlist L ); /求順序表L的長(zhǎng)度 void Insert(struct sequenlist

22、&L , elemtype x , int i); /將元素x插入順序表L第i個(gè)位置 void Dele(struct sequenlist &L , int i) ; /刪除順序表L第i個(gè)位置的元素 void setnull(struct sequenlist &L ); /順序表L置空表 int Locate(struct sequenlist L , elemtype x) ; /定位，順序表L中查找元素x的位置 elemtype Get(struct sequenlist L , int i); /取順序表L中第i個(gè)位置的元素 elemtype prior(struct sequenl

23、ist L , elemtype x );/順序表L中求元素x的前驅(qū) elemtype next(struct sequenlist L , elemtype x ); /順序表L中求元素x的后繼 30在上述描述中，a為一個(gè)數(shù)組類型，第一個(gè)元素為a0而非a1，因?yàn)镃中數(shù)組的下標(biāo)是從0開(kāi)始而非1開(kāi)始。存儲(chǔ)空間從a0amaxsize-1，而不是從a1amaxsize，不能使用amaxsize。為了與我們的a1對(duì)應(yīng)，建議從a1開(kāi)始使用元素，將a0存儲(chǔ)單元浪費(fèi)掉，這樣給我們的操作帶來(lái)較大方便（以后使用不再聲明），當(dāng)然，一般情形下，不應(yīng)該浪費(fèi)a0存儲(chǔ)單元，這可根據(jù)具體情形來(lái)定。2.2.2 順序表運(yùn)算實(shí)現(xiàn)

24、順序表上的基本運(yùn)算，我們都將以函數(shù)的形式描述。下面僅討論插入、刪除、求長(zhǎng)度、置空表、定位算法、取元素等，其他算法讀者自己可類似分析。1求順序表的長(zhǎng)度length(L)算法的語(yǔ)句如下：int length(struct sequenlist L ) return L.len;該算法的語(yǔ)句頻度為1，時(shí)間復(fù)雜度為O(1)。312插入運(yùn)算Insert(&L,x,i)要將x插入到順序表L的第i個(gè)位置，可分三種情形考慮：（1）i位置超過(guò)表長(zhǎng)，發(fā)生溢出，不能插入；（2）i值非法，不能插入；（3）i值合法，進(jìn)行插入。算法描述為：void Insert(struct sequenlist &L,elemtype

25、 x,int i) int j;if(L.len=maxsize-1) printf(overflown);else if (iL.len+1) printf(position is not correct!n);elsefor(j=L.len;j=i;j-)L.aj+1=L.aj; /元素后移L.ai=x; /插入元素L.len+; /表長(zhǎng)度增加132分析該算法的執(zhí)行效率：該算法花費(fèi)的時(shí)間，主要在于循環(huán)中元素的后移（其他語(yǔ)句花費(fèi)的時(shí)間可以忽略），即從插入位置到最后位置的所有元素都要后移一位，使空出的位置插入元素值x。但是，插入的位置是不固定的，當(dāng)插入位置i=1時(shí)，全部元素都得移動(dòng)，需n次移動(dòng)

26、，當(dāng)i=n+1時(shí)，不需移動(dòng)元素，故在i位置插入時(shí)移動(dòng)次數(shù)為n-i+1。假設(shè)在每個(gè)位置插入的概率相等，為 ，則平均移動(dòng)元素的次數(shù)為 ，故時(shí)間復(fù)雜度為O(n)。從上面的分析可知，順序表上的插入算法平均要移動(dòng)一半元素，故當(dāng)n較大時(shí)，算法的效率相當(dāng)?shù)汀?刪除運(yùn)算Dele(&L,i)刪除算法描述為：void Dele(struct sequenlist &L , int i) int j; if(iL.len) printf( position is not correct!n); else for(j=i+1;j=L.len;j+) L.aj-1=L.aj; /元素前移 L.len-; /表長(zhǎng)度減1

27、33該算法的運(yùn)行時(shí)間主要花費(fèi)在元素前移上，和剛才的插入算法類似，平均移動(dòng)次數(shù)為 ，故時(shí)間復(fù)雜度為(n)。順序表上的刪除運(yùn)算平均移動(dòng)元素次數(shù)也將近為表長(zhǎng)的一半，當(dāng)n較大時(shí)，算法的效率相當(dāng)?shù)汀捻樞虮聿迦?、刪除運(yùn)算可知，當(dāng)n較大時(shí)，算法效率都相當(dāng)?shù)汀Ｈ粲写罅窟\(yùn)算為插入、刪除運(yùn)算，則不宜選用順序表，必須選用另外的存儲(chǔ)結(jié)構(gòu)。從順序表插入、刪除運(yùn)算可知，當(dāng)n較大時(shí)，算法效率都相當(dāng)?shù)汀Ｈ粲写罅窟\(yùn)算為插入、刪除運(yùn)算，則不宜選用順序表，必須選用另外的存儲(chǔ)結(jié)構(gòu)。4置空表setnull( &L )算法如下：void setnull(struct sequenlist &L ) L.len=0;該算法的時(shí)間復(fù)雜度為

28、O(1)。345定位算法Locate(L,x)算法如下：int Locate(struct sequenlist L , elemtype x) int j=0; while(jL.len)&(L.aj!=x) j+; if(jL.len) return j; else return -1;該算法的時(shí)間復(fù)雜度為O(n)。6取元素Get(L,i)算法如下：elemtype Get(struct sequenlist L,int i) if(i=L.len) return NULL; else return L.ai;該算法的時(shí)間復(fù)雜度為O(1)。352.2.3 順序表存儲(chǔ)空間的動(dòng)態(tài)分配上面介紹的

29、線性表順序存儲(chǔ)，是預(yù)先給定大小為maxsize的存儲(chǔ)空間，程序在編譯階段就會(huì)知道該類型變量的大小，在程序開(kāi)始運(yùn)行前，就會(huì)為它分配好存儲(chǔ)空間，故是一種存儲(chǔ)空間的靜態(tài)分配。而動(dòng)態(tài)分配是在定義線性表的存儲(chǔ)類型時(shí)，不是定義好一個(gè)數(shù)組空間，而是只定義一個(gè)指針，待程序運(yùn)行后再申請(qǐng)一個(gè)用于存儲(chǔ)線性表的空間，并把該空間的首地址賦給這個(gè)指針。訪問(wèn)動(dòng)態(tài)存儲(chǔ)分配的線性表中的元素和訪問(wèn)靜態(tài)存儲(chǔ)分配的線性表中的元素的情況完全相同，既可以采用指針?lè)绞剑部梢圆捎脭?shù)組下標(biāo)方式。若將前面線性表的順序存儲(chǔ)結(jié)構(gòu)類型中的數(shù)組形式改為指針形式，則得到動(dòng)態(tài)分配形式如下：struct sequenlist elemtype *a; in

30、t len; ;36在此時(shí)，只有線性表置空表算法需要修改，其他算法都與靜態(tài)分配相同。這時(shí)的置空表算法應(yīng)改為：void setnull(struct sequenlist &L ) L.a=malloc(sizeof(elemtype)*maxsize) ); /動(dòng)態(tài)申請(qǐng)存儲(chǔ)單元 if(L.a=NULL) exit(1); /申請(qǐng)不成功 L.len=0;372.3 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，也稱為鏈表。其存儲(chǔ)方式是：在內(nèi)存中利用存儲(chǔ)單元（可以不連續(xù)）來(lái)存放元素值及它在內(nèi)存中的地址，各個(gè)元素的存放順序及位置都可以以任意順序進(jìn)行，原來(lái)相鄰的元素存放到計(jì)算機(jī)內(nèi)存中后不一定相鄰，從一個(gè)元

31、素找下一個(gè)元素必須通過(guò)地址（指針）才能實(shí)現(xiàn)，故不能像順序表一樣可隨機(jī)訪問(wèn)，而只能按順序訪問(wèn)。常用的鏈表有單鏈表、循環(huán)鏈表和雙向鏈表、多重鏈表等。2.3.1 單鏈表結(jié)構(gòu)在定義的鏈表中，若只含有一個(gè)指針域來(lái)存放下一個(gè)元素地址，稱這樣的鏈表為單鏈表或線性鏈表。線性鏈表中的結(jié)點(diǎn)結(jié)構(gòu)可描述為 。其中data域用來(lái)存放結(jié)點(diǎn)本身的信息，類型由具體問(wèn)題而定，本書中，我們也將其設(shè)定為elemtype類型，表示某一種具體的已知類型，next域用來(lái)存放下一個(gè)元素地址。data next38【例2-2】設(shè)有一個(gè)線性表(a1,a2,a3,a4,a5,a6)，在內(nèi)存中的存放形式見(jiàn)下圖。首先用頭指針存放第一個(gè)元素的地址，然

32、后每個(gè)結(jié)點(diǎn)的指針域存放下一個(gè)元素地址，最后一個(gè)結(jié)點(diǎn)的指針域?yàn)榭?，表示沒(méi)有后繼元素，設(shè)為NULL或。我們用上圖來(lái)描述單鏈表，是內(nèi)存中的存放形式，但看起來(lái)不太直觀，如果我們用下圖來(lái)描述單鏈表，則看起來(lái)直觀得多。39單鏈表可用語(yǔ)言描述為：struct link elemtype data; /元素類型struct link *next; /指針類型，存放下一個(gè)元素的地址;所定義的函數(shù)運(yùn)算如下:int length( ); /求鏈表的長(zhǎng)度void Insert(elemtype x,int i); /將元素x插入到第i個(gè)位置void Dele(int i) ; /刪除第i個(gè)位置的元素void setn

33、ull( ); /置空表int Locate(elemtype x) ; /定位，查找元素x的位置elemtype Get(int i); /取第i個(gè)位置的元素elemtype prior(elemtype x ); /求元素x的前驅(qū)elemtype succ(elemtype x ); /求元素x的后繼struct link *hcreat( ) /頭插法建立單鏈表struct link *rcreat( ) /尾插法建立單鏈表 402.3.2 單鏈表運(yùn)算在此僅介紹單鏈表建立、查找、插入、刪除、輸出等運(yùn)算，其他算法可類似分析。1頭插法建立單鏈表（從左邊插入結(jié)點(diǎn)）建立不帶頭結(jié)點(diǎn)的鏈表，算法為：

34、struct link *hcreat(int n ) /n表示結(jié)點(diǎn)的個(gè)數(shù) struct link *s,*p; int i; p=NULL; for(i=1;idata); /輸入結(jié)點(diǎn)的數(shù)據(jù)值 s-next=p; p=s; return p;41但是，為了便于實(shí)現(xiàn)各種運(yùn)算，通常在單鏈表的第一個(gè)結(jié)點(diǎn)之前增設(shè)一個(gè)附加結(jié)點(diǎn)，稱為頭結(jié)點(diǎn)，其他結(jié)點(diǎn)稱為表結(jié)點(diǎn)。頭結(jié)點(diǎn)結(jié)構(gòu)與表結(jié)點(diǎn)結(jié)構(gòu)相同，其數(shù)據(jù)域?yàn)榭眨部梢源娣疟黹L(zhǎng)等附加信息。不帶頭結(jié)點(diǎn)的單鏈表和帶頭結(jié)點(diǎn)的單鏈表見(jiàn)下圖。不帶頭結(jié)點(diǎn)的單鏈表帶頭結(jié)點(diǎn)的單鏈表42建立帶頭結(jié)點(diǎn)的鏈表，算法為： struct link *hcreat(int n ) struc

35、t link *s,*p; int i; p=(struct link *)malloc(sizeof(struct link); p-next=NULL; for(i=1;idata); s-next=p-next; p-next=s; return p;若假設(shè)鏈表中元素個(gè)數(shù)為n個(gè)，則兩種算法的時(shí)間復(fù)雜度都為(n)。432尾插法建立單鏈表（從右邊插入結(jié)點(diǎn)）（1）不帶頭結(jié)點(diǎn)的算法 struct link *rcreat(int n ) struct link *s,*r,*p; int i; p=NULL; for(i=1;idata);if(p=NULL) p=s;else r-next=s

36、;r=s;r-next=NULL;return p;44（2）帶頭結(jié)點(diǎn)的算法 struct link *rcreat(int n ) struct link *s,*r,*p; int i; p=(struct link *)malloc(sizeof(struct link);r=p; p-next=NULL; for(i=1;idata);r-next=s;r=s;r-next=NULL;return p;45比較上面兩種算法可以發(fā)現(xiàn)，建立不帶頭結(jié)點(diǎn)的單鏈表，必須進(jìn)行空表與非空表兩種情形的區(qū)分（循環(huán)中用if語(yǔ)句），而建立帶頭結(jié)點(diǎn)的單鏈表，則可省去這種判斷。所以，引入頭結(jié)點(diǎn)可以帶來(lái)以下好處：

37、第一，由于開(kāi)始結(jié)點(diǎn)的存儲(chǔ)地址存放在頭結(jié)點(diǎn)的指針域中，所以對(duì)鏈表的第一個(gè)結(jié)點(diǎn)和其他結(jié)點(diǎn)的處理一致，無(wú)須特殊處理。第二，不管鏈表是否為空，其頭指針都是指向頭結(jié)點(diǎn)的非空指針。因此，可不必區(qū)分空表與非空表，即可使空表與非空表的處理統(tǒng)一起來(lái)。第三，頭結(jié)點(diǎn)的信息域data一般沒(méi)有存放什么信息，故可以用來(lái)存放一些輔助信息，如鏈表長(zhǎng)度等。因此，若無(wú)特別聲明，以后建立的鏈表都為帶頭結(jié)點(diǎn)的鏈表。同樣上面兩種算法的時(shí)間復(fù)雜度都為(n)。463單鏈表上的查找運(yùn)算單鏈表上的查找與順序表不一樣，不能實(shí)現(xiàn)隨機(jī)查找，要找某一個(gè)元素，只能從頭開(kāi)始查找，故屬于順序查找。（1）按值查找Locate(head,x)在帶頭結(jié)點(diǎn)的單鏈表

38、head中，查找值為x的結(jié)點(diǎn)，若找到，則返回它的地址，否則返回NULL。 struct link *Locate(struct link *head , elemtype x) struct link *p; p=head-next; while(p!=NULL)&(p-data!=x) p=p-next; return p; 47（2）按序號(hào)查找get(head,i)在帶頭結(jié)點(diǎn)的單鏈表head中查找第i個(gè)位置上的元素，若找到，則返回它的地址，否則返回NULL。struct link *get(struct link *head , int i) int j; struct link *p;

39、j=1; p=head-next; while(jnext; return p; 上述兩種查找算法的時(shí)間復(fù)雜度都為(n)。4單鏈表上的插入運(yùn)算在順序表中，插入元素時(shí)，將會(huì)有大量元素向后移動(dòng)，而在單鏈表中，插入一個(gè)結(jié)點(diǎn)不需要移動(dòng)元素，只需修改指針指向即可。48算法描述為：void insert(struct link *head , elemtype x , elemtype y)/在頭指針head所指帶頭結(jié)點(diǎn)的單鏈表中，在值為y的結(jié)點(diǎn)之后插入值為x的結(jié)點(diǎn)struct link *p,*s; s=(struct link *)malloc(sizeof(struct link); s-data=

40、x; if(head-next=NULL) /鏈表為空 head-next=s; s-next=NULL; p=Locate(head,y) /調(diào)用查找算法 if(p=NULL) printf(插入位置非法n); else s-next=p-next; p-next=s; 該算法花費(fèi)的時(shí)間主要耗費(fèi)在查找上，故時(shí)間復(fù)雜為(n)，若調(diào)用另一種查找算法，程序需作適當(dāng)修改，可作類似分析。495單鏈表上的刪除運(yùn)算算法描述為： void dele(struct link *head , elemtype x)/在head為頭指針的帶頭結(jié)點(diǎn)的單鏈表中，刪除值為x的結(jié)點(diǎn) struct link *p,*q;

41、q=head; p=head-next; while(p!=NULL)&(p-data!=x) q=p; p=p-next; if(p=NULL) printf(要?jiǎng)h除的結(jié)點(diǎn)不存在n); else q-next=p-next; free(p); 該算法花費(fèi)的時(shí)間主要耗費(fèi)在查找上，故時(shí)間復(fù)雜度為(n)。若要?jiǎng)h除鏈表中第i個(gè)結(jié)點(diǎn)，將上述刪除算法做適當(dāng)修改即可。506輸出單鏈表若需將單鏈表按邏輯順序輸出，則必須從頭到尾訪問(wèn)單鏈表中的每一個(gè)結(jié)點(diǎn)，算法描述如下：void print(struct link *head) struct link *p; p=head-next; while(p-next!

42、=NULL) printf(“%d-”,p-data);/輸出表中非最后一個(gè)元素 p=p-next; printf(“%dn”,p-data); /輸出表中最后一個(gè)元素 該算法必須對(duì)鏈表從頭到尾訪問(wèn)一次，假設(shè)鏈表長(zhǎng)度為n，因此，該算法時(shí)間復(fù)雜度為(n)。512.3.3 循環(huán)鏈表結(jié)構(gòu)單鏈表上的訪問(wèn)是一種順序訪問(wèn)，從其中某一個(gè)結(jié)點(diǎn)出發(fā)，可以找到它的直接后繼，但無(wú)法找到它的直接前驅(qū)。因此，我們可以考慮建立這樣的鏈表具有單鏈表的特征，但又不需要增加額外的存儲(chǔ)空間，僅對(duì)表的鏈接方式稍做改變，使得對(duì)表的處理更加方便靈活。從單鏈表可知，最后一個(gè)結(jié)點(diǎn)的指針域?yàn)镹ULL表示單鏈表已經(jīng)結(jié)束。如果將單鏈表最后一個(gè)結(jié)

43、點(diǎn)的指針域改為存放鏈表中頭結(jié)點(diǎn)（或第一個(gè)結(jié)點(diǎn)）的地址，就使得整個(gè)鏈表構(gòu)成一個(gè)環(huán)，又沒(méi)有增加額外的存儲(chǔ)空間，稱這樣的鏈表為單循環(huán)鏈表，在不引起混淆時(shí)稱為循環(huán)表（后面還要提到雙向循環(huán)表），如下圖所示。（a）空循環(huán)表（b）非空循環(huán)表52循環(huán)鏈表上的運(yùn)算與單鏈表上的運(yùn)算基本一致，區(qū)別只在于最后一個(gè)結(jié)點(diǎn)的判斷（即循環(huán)的條件不同），但利用循環(huán)鏈表實(shí)現(xiàn)某些運(yùn)算較單鏈表方便（從某個(gè)結(jié)點(diǎn)出發(fā)能求出它的直接前驅(qū)，而單鏈表是不行的，只能從頭出發(fā)）。【例2-3】在如下圖所示的單循環(huán)鏈表中，求P的直接前驅(qū)（從P出發(fā)，而不從head出發(fā)），算法如下：struct link *prior(struct link *head

44、 ,struct link *p)struct link *q; q=p-next; while(q-next!=p) q=q-next; return q;顯然該算法的時(shí)間復(fù)雜度為(n)。53既然是循環(huán)鏈表， head指針就可以指向任意結(jié)點(diǎn)，若將head指向末尾，有時(shí)的操作會(huì)比head指向開(kāi)頭的操作更方便，下面將舉例說(shuō)明。【例2-4】將兩個(gè)鏈表合并成一個(gè)鏈表（第一個(gè)表的尾接第二個(gè)表的頭），要求用head指向頭和head指向尾兩種循環(huán)鏈表實(shí)現(xiàn)，分別如下圖一和圖二所示。圖一圖二54對(duì)第一種合并算法，可以分三步走：第一步，先找到head1中最后一個(gè)結(jié)點(diǎn)an ，語(yǔ)句描述為：p=head1-next;

45、while(p-next!=head1) p=p-next;第二步，找到head2中最后一個(gè)結(jié)點(diǎn)bm ，語(yǔ)句描述為：q=head2-next;while(q-next!=head2)q=q-next;第三步，合并，語(yǔ)句描述為：p-next=head2-next;q-next=head1;具體算法請(qǐng)讀者自己完成。對(duì)于第二種合并算法，僅用三條語(yǔ)句就能實(shí)現(xiàn)，具體為：t=head1-next;head1-next=head2-next-next;head2-next=t;顯然，第一種合并算法的時(shí)間復(fù)雜度為O(n+m)，第二種合并算法時(shí)間復(fù)雜度為O(1)。因此，用尾指針?biāo)狙h(huán)表較頭指針?biāo)狙h(huán)表操作更

46、方便。552.3.4 雙向鏈表結(jié)構(gòu)1雙向鏈表的基本概念在單鏈表中，從某個(gè)結(jié)點(diǎn)出發(fā)可以直接找到它的直接后繼，時(shí)間復(fù)雜度為O(1)，但無(wú)法直接找到它的直接前驅(qū)；在單循環(huán)鏈表中，從某個(gè)結(jié)點(diǎn)出發(fā)可以直接找到它的直接后繼，時(shí)間復(fù)雜度仍為O(1)，直接找到它的直接前驅(qū)，時(shí)間復(fù)雜度為O(n)。有時(shí)，希望能快速找到一個(gè)結(jié)點(diǎn)的直接前驅(qū)，這時(shí)，可以在單鏈表中的結(jié)點(diǎn)中增加一個(gè)指針域指向它的直接前驅(qū)，這樣的鏈表就稱為雙向鏈表（一個(gè)結(jié)點(diǎn)中含有兩個(gè)指針）。如果每條鏈構(gòu)成一個(gè)循環(huán)鏈表，則會(huì)得到雙向循環(huán)鏈表。雙向鏈表可用C語(yǔ)言描述如下： struct dblink elemtype data; /結(jié)點(diǎn)的數(shù)據(jù)域，類型設(shè)定為el

47、emtypestruct dblink *next , *prior; /定義指向直接后繼和直接前驅(qū)的指針;所定義的函數(shù)運(yùn)算如下: void dbinsert(struct dblink *head , elemtype x , elemtype y); /插入函數(shù) /其他成員函數(shù)定義及實(shí)現(xiàn)省略56在雙向鏈表中，若涉及的運(yùn)算僅用到一個(gè)方向的指針，則雙向鏈表中的運(yùn)算與單鏈表中算法一致。例如查找、輸出等運(yùn)算，與單鏈表中運(yùn)算一致。若運(yùn)算涉及兩個(gè)方向的指針，則與單鏈表中的算法不同，例如插入、刪除運(yùn)算。下面僅討論插入、刪除運(yùn)算。由于雙向鏈表是一種對(duì)稱的結(jié)構(gòu)，因此比起單鏈表來(lái)，求某個(gè)結(jié)點(diǎn)的直接前驅(qū)和直接后

48、繼都相當(dāng)方便，時(shí)間復(fù)雜度為O(1)，并且還有一個(gè)很重要的性質(zhì)：若P為指向某個(gè)結(jié)點(diǎn)的指針，則有：p-next-prior=p=p-prior-next雙向鏈表的形式見(jiàn)下圖一，雙向循環(huán)鏈表形式見(jiàn)下圖二。同樣，雙向鏈表和雙向循環(huán)鏈表與單鏈表一樣，都可以帶頭結(jié)點(diǎn)。圖一圖二572雙向鏈表插入運(yùn)算dbinsert (head,x,y)插入算法描述為：void dbinsert(struct dblink *head , elemtype x , elemtype y) struct dblink *p,*s; s=(struct dblink *)malloc(sizeof(struct dblink);

49、 /申請(qǐng)待插入的結(jié)點(diǎn) s-data=x; p=head; while(p!=NULL)&(p-data!=y) /用循環(huán)查找值為y的結(jié)點(diǎn) p=p-next; if (p!=NULL) /已找到插入位置 s-next=p-next; p-next-prior=s; s-prior=p; p-next=s; else printf(插入位置不存在n); 58因?yàn)殡p向鏈表有兩個(gè)方向的指針，故查找也可以從后往前進(jìn)行，請(qǐng)讀者自己修改算法中查找部分程序，使之從后往前查找。無(wú)論是哪種查找，時(shí)間復(fù)雜度都為O(n)，而該算法花費(fèi)的時(shí)間主要是在查找方面，故該算法的時(shí)間復(fù)雜度為O(n)。3雙向鏈表的刪除運(yùn)算dbde

50、lete(head ,x)刪除算法描述為:：void dbdelete(struct dblink *head , int x) struct dblink *p; p=head; while(p!=NULL)&(p-data!=x) /用循環(huán)查找值為x的結(jié)點(diǎn) p=p-next; if(p!=NULL) /已找到該結(jié)點(diǎn) p-prior-next=p-next; p-next-prior=p-prior; delete p; /刪除后的結(jié)點(diǎn)空間回收 else printf(沒(méi)找到，不能刪除n); 該算法花費(fèi)的時(shí)間主要是在查找結(jié)點(diǎn)上，故時(shí)間復(fù)雜度仍為O(n)。592.4 一元多項(xiàng)式的表示及相加2.

51、4.1 一元多項(xiàng)式的表示1順序表表示設(shè)有一個(gè)一元多項(xiàng)式fn(x)=a0+a1x+a2x2+anxn，若只存儲(chǔ)它的系數(shù)a0，a1，a2，an，則可以用一個(gè)一維數(shù)組表示，占用的存儲(chǔ)單元有n+1個(gè)。但若有很多系數(shù)為0時(shí)，將會(huì)浪費(fèi)很多存儲(chǔ)單元。例如對(duì)于一元多項(xiàng)式 f(x)=1+3x5+9x1000，用順序表來(lái)存儲(chǔ)系數(shù)時(shí)，需要1001個(gè)存儲(chǔ)單元，但實(shí)際只要存儲(chǔ)三項(xiàng)就可以了，浪費(fèi)的存儲(chǔ)單元有998個(gè)。若只存儲(chǔ)非0的系數(shù)，雖然可以節(jié)省存儲(chǔ)單元，但又不知道是對(duì)應(yīng)哪一項(xiàng)指數(shù)，操作起來(lái)不方便。因此，可以考慮使用另一種存儲(chǔ)結(jié)構(gòu)。2鏈表表示對(duì)于一元多項(xiàng)式fn(x)=a0+a1x+a2x2+anxn，若有很多系數(shù)為0時(shí)

52、，可以只存儲(chǔ)非0的系數(shù)及對(duì)應(yīng)的指數(shù)，這時(shí)，用單鏈表表示比較方便。例如，f(x)=2+5x7+11x25+8x30，用單鏈表表示見(jiàn)下圖 602.4.2 一元多項(xiàng)式的相加1基本思想對(duì)A(x)和B(x)兩個(gè)一元多項(xiàng)式相加時(shí)，需要對(duì)兩個(gè)單鏈表從頭向尾進(jìn)行掃描。具體實(shí)現(xiàn)方法為：取A或B表中任意一個(gè)表頭作相加后的鏈表表頭，不妨取A鏈表的表頭作相加后的鏈表表頭，新表指針pc=A，前驅(qū)指針pre=A，然后設(shè)置兩個(gè)搜索指針：p=A-next; q=B-next;當(dāng)pa和pb都不為空時(shí)，反復(fù)執(zhí)行下面的語(yǔ)句（循環(huán)）：（1）若p的指數(shù)q的指數(shù)將q插入新表中，q指針后移；（3）若p的指數(shù)=q的指數(shù)若相加的系數(shù)等于0，刪

53、除p、q兩個(gè)結(jié)點(diǎn)，然后p、q后移；若相加的系數(shù)不為0，則將結(jié)果放入p中，并將p插入新表中，p指針后移，刪除q結(jié)點(diǎn)，q后移。最后，當(dāng)循環(huán)結(jié)束后，若q非空，則pre-next=q;算法結(jié)束。 61兩個(gè)鏈表A(x)=7+3x+9x8+5x17和B(x)=8x+22x7-9x8相加的過(guò)程見(jiàn)下圖 622算法實(shí)現(xiàn)#includestruct poly int coef; /系數(shù)int exp ; /指數(shù) struct poly *next; /指針類型，存放下一個(gè)元素的地址;63/頭插法建立帶頭結(jié)點(diǎn)的單鏈表struct poly *hcreat( ) struct poly *s,*p; int i,j;

54、 printf(輸入結(jié)點(diǎn)數(shù)值，為0時(shí)算法結(jié)束); scanf(“%d %d”,&i,&j); p=(struct poly *)malloc(sizeof(struct poly); p-next=NULL; while(i!=0) s=(struct poly *)malloc(sizeof(struct poly); s-coef=i;s-exp=j; s-next=p-next; p-next=s; scanf(“%d %d”,&i,&j); return p;64 struct poly *add(struct poly *A,struct poly *B) /多項(xiàng)式相加 struct

55、 poly *p,*q,*pre,*C,*u; p=A-next;q=B-next; pre=A;C=A; while(p!=NULL&q!=NULL) if(p-expexp) pre=p;p=p-next; else if(p-exp=q-exp) int x=p-coef+q-coef; if(x!=0) p-coef=x;pre=p; else pre-next=p-next;delete p; p=pre-next;u=q; q=q-next;delete u; else u=q-next; q-next=p;pre-next=q;pre=q;q=u; if(q!=NULL) pre

56、-next=q; return C;65 void main() struct poly *A,*B,*C, a; A=a.hcreat(); /頭插法建立第一個(gè)多項(xiàng)式鏈表 B=a.hcreat(); /頭插法建立第二個(gè)多項(xiàng)式鏈表 C=a.add(A,B); /多項(xiàng)式相加2.5 順序表與鏈表的比較上面已經(jīng)討論了線性表的兩種存儲(chǔ)結(jié)構(gòu)：順序表和鏈表。在實(shí)際應(yīng)用中，兩種方法各有特色，我們究竟選用哪一種作為存儲(chǔ)結(jié)構(gòu)呢?這要根據(jù)具體問(wèn)題的要求和性質(zhì)來(lái)決定，一般可以從以下幾個(gè)方面考慮。661基于存儲(chǔ)空間的考慮順序表的存儲(chǔ)空間是靜態(tài)分配的，程序執(zhí)行之前必須預(yù)先分配。若線性表的長(zhǎng)度n變化較大，存儲(chǔ)空間難以事先

57、確定，估計(jì)過(guò)大，將造成大量存儲(chǔ)單元的浪費(fèi)，估計(jì)過(guò)小時(shí)又不能臨時(shí)擴(kuò)充存儲(chǔ)單元，將使空間溢出機(jī)會(huì)增多。鏈表的存儲(chǔ)空間是動(dòng)態(tài)分配的，只要內(nèi)存空間尚有空閑，就不會(huì)發(fā)生溢出。對(duì)于存儲(chǔ)空間的考慮，可以用存儲(chǔ)密度的大小來(lái)衡量。存儲(chǔ)密度為結(jié)點(diǎn)應(yīng)占用的存儲(chǔ)量除以結(jié)點(diǎn)實(shí)際占用的存儲(chǔ)量。存儲(chǔ)密度越大，存儲(chǔ)空間利用率越高，反之利用率越低。例如，順序表的存儲(chǔ)密度為100%，單鏈表為50%（假設(shè)指針?biāo)伎臻g與數(shù)據(jù)域所占空間相同），雙向鏈表的存儲(chǔ)密度為33%。由此可知，當(dāng)線性表的長(zhǎng)度變化不大，存儲(chǔ)空間可以事先估計(jì)時(shí)，采用順序表作存儲(chǔ)結(jié)構(gòu)比較方便；當(dāng)線性表長(zhǎng)度變化較大，存儲(chǔ)空間難以事先估計(jì)時(shí)，采用鏈表作存儲(chǔ)結(jié)構(gòu)比較方便。67

58、2基于時(shí)間的考慮順序表是一種隨機(jī)訪問(wèn)的表，而鏈表是一種順序訪問(wèn)的表，因此順序表的訪問(wèn)較鏈表方便。若線性表中運(yùn)算主要為存取、查找運(yùn)算，采用時(shí)間復(fù)雜度為O(1)的順序表比較方便；若線性表中的運(yùn)算大部分為插入、刪除運(yùn)算，采用時(shí)間復(fù)雜度為O(1)的鏈表比較方便；若鏈表中操作運(yùn)算都在表尾進(jìn)行，應(yīng)采用尾指針?biāo)镜膯窝h(huán)鏈表。3基于語(yǔ)言的考慮有的高級(jí)語(yǔ)言無(wú)指針數(shù)據(jù)類型，因此，若用鏈表作存儲(chǔ)結(jié)構(gòu)，則只能用整數(shù)代替指針，稱這樣的鏈表為靜態(tài)鏈表，而一般的鏈表則稱為動(dòng)態(tài)鏈表（我們所用的鏈表都為動(dòng)態(tài)鏈表）。 682.6 算法應(yīng)用舉例【例2-5】實(shí)現(xiàn)一個(gè)單鏈表的就地逆置（所謂就地逆置就是不另外增加多余的輔助空間）。分析

59、：要將一個(gè)單鏈表逆置，即將(a1,a2,an)變成(an,an-1,a2,a1)。但鏈表已存在，故不需要另外申請(qǐng)存儲(chǔ)空間，只需改變鏈表的鏈接關(guān)系即可?？梢越柚鷨捂湵淼念^插法來(lái)實(shí)現(xiàn)題目要求，改變單鏈表的鏈接關(guān)系。算法描述如下：void swaplink(struct link *head) struct link *p,*s; p=head-next; head-next=NULL; while(p!=NULL) s=p-next; p-next=head-next; head-next=p; p=s; 該算法的時(shí)間復(fù)雜度為O(n)。69【例2-6】用順序表解決約瑟夫（Josephus）問(wèn)題。約

60、瑟夫問(wèn)題為：n個(gè)人圍成一圈，從第S個(gè)人開(kāi)始報(bào)數(shù)1，2，m，數(shù)到m的人出圈，然后從出圈的下一個(gè)人開(kāi)始重復(fù)此過(guò)程，直到全部人出圈。要求在給出m，n，s后，能輸出出圈序列。分析：n個(gè)人可以用1，2，n進(jìn)行編號(hào)，然后存入一個(gè)一維數(shù)組中，若某個(gè)人出圈，則將后面的人往前移一個(gè)數(shù)組位置，最后面的位置被空出，可以存放出圈人的編號(hào)，再對(duì)前面n-1個(gè)人重復(fù)此過(guò)程，直到剩下一個(gè)人為止，則此時(shí)數(shù)組中存放的值為出圈人的反序。70算法描述如下：#define n 人數(shù)#define m 報(bào)數(shù)上界#define s 報(bào)數(shù)開(kāi)始位置void josephus(int an+1 , int m , int s) int i,j,