清華大學(xué)考研真題-sjjg

數(shù)據(jù)結(jié)構(gòu)計(jì)算機(jī)系第一頁(yè)，編輯于星期五：十三點(diǎn)四十四分。第一章緒論1.1什么是數(shù)據(jù)結(jié)構(gòu)1.2基本概念和術(shù)語(yǔ)1.3抽象數(shù)據(jù)類型的表示與實(shí)現(xiàn)1.4算法和算法分1.4.1算法1.4.2算法設(shè)計(jì)的要求1.4.3算法效率的度量1.4.4算法的存儲(chǔ)空間的需求第二頁(yè)，編輯于星期五：十三點(diǎn)四十四分。第一章緒論計(jì)算機(jī)是一門研究用計(jì)算機(jī)進(jìn)行信息表示和處理的科學(xué)。這里面涉及到兩個(gè)問(wèn)題：信息的表示信息的處理而信息的表示和組又直接關(guān)系到處理信息的程序的效率。隨著計(jì)算機(jī)的普及，信息量的增加，信息范圍的拓寬，使許多系統(tǒng)程序和應(yīng)用程序的規(guī)模很大，結(jié)構(gòu)又相當(dāng)復(fù)雜。因此，為了編寫出一個(gè)“好”的程序，必須分析待處理的對(duì)象的特征及各對(duì)象之間存在的關(guān)系，這就是數(shù)據(jù)結(jié)構(gòu)這門課所要研究的問(wèn)題。第三頁(yè)，編輯于星期五：十三點(diǎn)四十四分。

1.1什么是數(shù)據(jù)結(jié)構(gòu)

眾所周知，計(jì)算機(jī)的程序是對(duì)信息進(jìn)行加工處理。在大多數(shù)情況下，這些信息并不是沒(méi)有組織，信息（數(shù)據(jù)）之間往往具有重要的結(jié)構(gòu)關(guān)系，這就是數(shù)據(jù)結(jié)構(gòu)的內(nèi)容。那么，什么是數(shù)據(jù)結(jié)構(gòu)呢？先看以下幾個(gè)例子。例1、電話號(hào)碼查詢系統(tǒng)設(shè)有一個(gè)電話號(hào)碼薄，它記錄了N個(gè)人的名字和其相應(yīng)的電話號(hào)碼，假定按如下形式安排：(a1，b1)(a2，b2)…(an，bn)其中ai，bi(i=1，2…n)分別表示某人的名字和對(duì)應(yīng)的電話號(hào)碼要求設(shè)計(jì)一個(gè)算法，當(dāng)給定任何一個(gè)人的名字時(shí)，該算法能夠打印出此人的電話號(hào)碼，如果該電話簿中根本就沒(méi)有這個(gè)人，則該算法也能夠報(bào)告沒(méi)有這個(gè)人的標(biāo)志。第四頁(yè)，編輯于星期五：十三點(diǎn)四十四分。算法的設(shè)計(jì)，依賴于計(jì)算機(jī)如何存儲(chǔ)人的名字和對(duì)應(yīng)的電話號(hào)碼，或者說(shuō)依賴于名字和其電話號(hào)碼的結(jié)構(gòu)。數(shù)據(jù)的結(jié)構(gòu)，直接影響算法的選擇和效率。上述的問(wèn)題是一種數(shù)據(jù)結(jié)構(gòu)問(wèn)題。可將名字和對(duì)應(yīng)的電話號(hào)碼設(shè)計(jì)成：二維數(shù)組、表結(jié)構(gòu)、向量。假定名字和其電話號(hào)碼邏輯上已安排成N元向量的形式，它的每個(gè)元素是一個(gè)數(shù)對(duì)(ai，bi)，1≤i≤n數(shù)據(jù)結(jié)構(gòu)還要提供每種結(jié)構(gòu)類型所定義的各種運(yùn)算的算法。第五頁(yè)，編輯于星期五：十三點(diǎn)四十四分。例2、圖書館的書目檢索系統(tǒng)自動(dòng)化問(wèn)題例3、教師資料檔案管理系統(tǒng)例4、多叉路口交通燈的管理問(wèn)題P3通過(guò)以上幾例可以直接地認(rèn)為：數(shù)據(jù)結(jié)構(gòu)就是研究數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)以及它們之間相互關(guān)系，并對(duì)這種結(jié)構(gòu)定義相應(yīng)的運(yùn)算，而且確保經(jīng)過(guò)這些運(yùn)算后所得到的新結(jié)構(gòu)仍然是原來(lái)的結(jié)構(gòu)類型。第六頁(yè)，編輯于星期五：十三點(diǎn)四十四分。1.2基本概念和術(shù)語(yǔ)數(shù)據(jù)(Data):是對(duì)信息的一種符號(hào)表示。在計(jì)算機(jī)科學(xué)中是指所有能輸入到計(jì)算機(jī)中并被計(jì)算機(jī)程序處理的符號(hào)的總稱。數(shù)據(jù)元素(DataElement):是數(shù)據(jù)的基本單位，在計(jì)算機(jī)程序中通常作為一個(gè)整體進(jìn)行考慮和處理。一個(gè)數(shù)據(jù)元素可由若干個(gè)數(shù)據(jù)項(xiàng)組成。數(shù)據(jù)項(xiàng)是數(shù)據(jù)的不可分割的最小單位。數(shù)據(jù)對(duì)象(DataObject)：是性質(zhì)相同的數(shù)據(jù)元素的集合。是數(shù)據(jù)的一個(gè)子集。數(shù)據(jù)結(jié)構(gòu)(DataStructure)：是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。第七頁(yè)，編輯于星期五：十三點(diǎn)四十四分。數(shù)據(jù)結(jié)構(gòu)主要指邏輯結(jié)構(gòu)和物理結(jié)構(gòu)數(shù)據(jù)之間的相互關(guān)系稱為邏輯結(jié)構(gòu)。通常分為四類基本結(jié)構(gòu)：一、集合結(jié)構(gòu)中的數(shù)據(jù)元素除了同屬于一種類型外，別無(wú)其它關(guān)系。二、線性結(jié)構(gòu)結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一對(duì)一的關(guān)系。三、樹(shù)型結(jié)構(gòu)結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一對(duì)多的關(guān)系。四、圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)結(jié)構(gòu)中的數(shù)據(jù)元素之間存在多對(duì)多的關(guān)系。

第八頁(yè)，編輯于星期五：十三點(diǎn)四十四分。數(shù)據(jù)結(jié)構(gòu)的形式定義為：數(shù)據(jù)結(jié)構(gòu)是一個(gè)二元組：Data-Structure=(D，S)其中：D是數(shù)據(jù)元素的有限集，S是D上關(guān)系的有限集。例復(fù)數(shù)的數(shù)據(jù)結(jié)構(gòu)定義如下：Complex=(C，R)其中：C是含兩個(gè)實(shí)數(shù)的集合﹛C1，C2﹜，分別表示復(fù)數(shù)的實(shí)部和虛部。R={P}，P是定義在集合上的一種關(guān)系{〈C1，C2〉}。數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的表示稱為數(shù)據(jù)的物理結(jié)構(gòu)，又稱為存儲(chǔ)結(jié)構(gòu)。第九頁(yè)，編輯于星期五：十三點(diǎn)四十四分。

數(shù)據(jù)對(duì)象可以是有限的，也可以是無(wú)限的。數(shù)據(jù)結(jié)構(gòu)不同于數(shù)據(jù)類型，也不同于數(shù)據(jù)對(duì)象，它不僅要描述數(shù)據(jù)類型的數(shù)據(jù)對(duì)象，而且要描述數(shù)據(jù)對(duì)象各元素之間的相互關(guān)系。抽象數(shù)據(jù)類型：一個(gè)數(shù)學(xué)模型以及定義在該模型上的一組操作。抽象數(shù)據(jù)類型實(shí)際上就是對(duì)該數(shù)據(jù)結(jié)構(gòu)的定義。因?yàn)樗x了一個(gè)數(shù)據(jù)的邏輯結(jié)構(gòu)以及在此結(jié)構(gòu)上的一組算法。用三元組描述如下：（Ｄ，Ｓ，Ｐ）第十頁(yè)，編輯于星期五：十三點(diǎn)四十四分。數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中有兩種不同的表示方法：順序表示和非順序表示由此得出兩種不同的存儲(chǔ)結(jié)構(gòu)：順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu):用數(shù)據(jù)元素在存儲(chǔ)器中的相對(duì)位置來(lái)表示數(shù)據(jù)元素之間的邏輯關(guān)系。鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：在每一個(gè)數(shù)據(jù)元素中增加一個(gè)存放地址的指針（），用此指針來(lái)表示數(shù)據(jù)元素之間的邏輯關(guān)系。第十一頁(yè)，編輯于星期五：十三點(diǎn)四十四分。數(shù)據(jù)類型：在一種程序設(shè)計(jì)語(yǔ)言中，變量所具有的數(shù)據(jù)種類。例1、在FORTRAN語(yǔ)言中，變量的數(shù)據(jù)類型有整型、實(shí)型、和復(fù)數(shù)型例2、在C語(yǔ)言中數(shù)據(jù)類型：基本類型和構(gòu)造類型基本類型：整型、浮點(diǎn)型、字符型構(gòu)造類型：數(shù)組、結(jié)構(gòu)、聯(lián)合、指針、枚舉型、自定義數(shù)據(jù)對(duì)象：某種數(shù)據(jù)類型元素的集合。例3、整數(shù)的數(shù)據(jù)對(duì)象是{…-3，-2，-1，0，1，2，3，…}英文字符類型的數(shù)據(jù)對(duì)象是{A，B，C，D，E，F(xiàn)，…}第十二頁(yè)，編輯于星期五：十三點(diǎn)四十四分。1.3抽象數(shù)據(jù)類型的表示和實(shí)現(xiàn)P11第十三頁(yè)，編輯于星期五：十三點(diǎn)四十四分。

1.4算法和算法分析算法：是對(duì)特定問(wèn)題求解步驟的一種描述算法是指令的有限序列，其中每一條指令表示一個(gè)或多個(gè)操作。算法具有以下五個(gè)特性：（1）有窮性一個(gè)算法必須總是在執(zhí)行有窮步之后結(jié)束，且每一步都在有窮時(shí)間內(nèi)完成。（2）確定性算法中每一條指令必須有確切的含義。不存在二義性。且算法只有一個(gè)入口和一個(gè)出口。（3）可行性一個(gè)算法是可行的。即算法描述的操作都是可以通過(guò)已經(jīng)實(shí)現(xiàn)的基本運(yùn)算執(zhí)行有限次來(lái)實(shí)現(xiàn)的。第十四頁(yè)，編輯于星期五：十三點(diǎn)四十四分。4）輸入一個(gè)算法有零個(gè)或多個(gè)輸入，這些輸入取自于某個(gè)特定的對(duì)象集合。5）輸出一個(gè)算法有一個(gè)或多個(gè)輸出，這些輸出是同輸入有著某些特定關(guān)系的量。1.4.2算法設(shè)計(jì)的要求評(píng)價(jià)一個(gè)好的算法有以下幾個(gè)標(biāo)準(zhǔn):(1)正確性(Correctness)算法應(yīng)滿足具體問(wèn)題的需求。(2)可讀性(Readability)算法應(yīng)該好讀。以有利于閱讀者對(duì)程序的理解。(3)健狀性(Robustness)算法應(yīng)具有容錯(cuò)處理。當(dāng)輸入非法數(shù)據(jù)時(shí)，算法應(yīng)對(duì)其作出反應(yīng)，而不是產(chǎn)年莫名其妙的輸出結(jié)果。第十五頁(yè)，編輯于星期五：十三點(diǎn)四十四分。(4)效率與存儲(chǔ)量需求效率指的是算法執(zhí)行的時(shí)間；存儲(chǔ)量需求指算法執(zhí)行過(guò)程中所需要的最大存儲(chǔ)空間。一般，這兩者與問(wèn)題的規(guī)模有關(guān)。1.4.3算法效率的度量

對(duì)一個(gè)算法要作出全面的分析可分成兩用人才個(gè)階段進(jìn)行，即事先分析和事后測(cè)試事先分析求出該算法的一個(gè)時(shí)間界限函數(shù)事后測(cè)試收集此算法的執(zhí)行時(shí)間和實(shí)際占用空間的統(tǒng)計(jì)資料。定義：如果存在兩個(gè)正常數(shù)c和n0，對(duì)于所有的n≧n0，有︱f(n)︳≦c｜g(n)︳則記作f(n)=O(g(n))第十六頁(yè)，編輯于星期五：十三點(diǎn)四十四分。一般情況下，算法中基本操作重復(fù)執(zhí)行的次數(shù)是問(wèn)題規(guī)模n的某個(gè)函數(shù)，算法的時(shí)間量度記作T(n)=O(f(n))稱作算法的漸近時(shí)間復(fù)雜度。例１、for(I=1，I<=n;++I)for(j=1;j<=n;++j){c[I][j]=0;for(k=1;k<=n;++k)c[I][j]+=a[I][k]*b[k][j];}第十七頁(yè)，編輯于星期五：十三點(diǎn)四十四分。由于是一個(gè)三重循環(huán)，每個(gè)循環(huán)從1到n，則總次數(shù)為:n×n×n=n3時(shí)間復(fù)雜度為T(n)=O(n3)頻度：是指該語(yǔ)句重復(fù)執(zhí)行的次數(shù)例２{++x;s=0;}將x自增看成是基本操作，則語(yǔ)句頻度為１，即時(shí)間復(fù)雜度為Ｏ(1)如果將s=0也看成是基本操作，則語(yǔ)句頻度為２，其時(shí)間復(fù)雜度仍為Ｏ(1)，即常量階。例３、for(I=1;I<=n;++I){++x;s+=x;}語(yǔ)句頻度為：2n其時(shí)間復(fù)雜度為：O(n)即時(shí)間復(fù)雜度為線性階。第十八頁(yè)，編輯于星期五：十三點(diǎn)四十四分。例４、for(I=1;I<=n;++I)for(j=1;j<=n;++j){++x;s+=x;}語(yǔ)句頻度為：2n2其時(shí)間復(fù)雜度為：O(n2)即時(shí)間復(fù)雜度為平方階。定理：若A(n)=amnm+am-1nm-1+…+a1n+a0是一個(gè)m次多項(xiàng)式，則A(n)=O(nm)證略。例５for(i=2;i<=n;++I)for(j=2;j<=i-1;++j){++x;a[i，j]=x;}第十九頁(yè)，編輯于星期五：十三點(diǎn)四十四分。語(yǔ)句頻度為：1+2+3+…+n-2=(1+n-2)×(n-2)/2=(n-1)(n-2)/2=n2-3n+2∴時(shí)間復(fù)雜度為O(n2)即此算法的時(shí)間復(fù)雜度為平方階.一個(gè)算法時(shí)間為O(1)的算法，它的基本運(yùn)算執(zhí)行的次數(shù)是固定的。因此，總的時(shí)間由一個(gè)常數(shù)（即零次多項(xiàng)式）來(lái)限界。而一個(gè)時(shí)間為O(n2)的算法則由一個(gè)二次多項(xiàng)式來(lái)限界。

第二十頁(yè)，編輯于星期五：十三點(diǎn)四十四分。以下六種計(jì)算算法時(shí)間的多項(xiàng)式是最常用的。其關(guān)系為：O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n3)指數(shù)時(shí)間的關(guān)系為：O(2n)<O(n!)<O(nn)當(dāng)n取得很大時(shí)，指數(shù)時(shí)間算法和多項(xiàng)式時(shí)間算法在所需時(shí)間上非常懸殊。因此，只要有人能將現(xiàn)有指數(shù)時(shí)間算法中的任何一個(gè)算法化簡(jiǎn)為多項(xiàng)式時(shí)間算法，那就取得了一個(gè)偉大的成就。第二十一頁(yè)，編輯于星期五：十三點(diǎn)四十四分。有的情況下，算法中基本操作重復(fù)執(zhí)行的次數(shù)還隨問(wèn)題的輸入數(shù)據(jù)集不同而不同。例如：Voidbubble-sort(inta[]，intn)for(I=n-1;change=TURE;I>1&&change;--I){change=false;for(j=0;j<I;++j)if(a[j]>a[j+1]){a[j]←→a[j+1];change=TURE}}最好情況：0次

第二十二頁(yè)，編輯于星期五：十三點(diǎn)四十四分。最壞情況：1+2+3+…+n-1=n(n-1)/2平均時(shí)間復(fù)雜度為:O(n2)算法的存儲(chǔ)空間需求空間復(fù)雜度:算法所需存儲(chǔ)空間的度量，記作:S(n)=O(f(n))其中n為問(wèn)題的規(guī)模(或大小)第二十三頁(yè)，編輯于星期五：十三點(diǎn)四十四分。

第二章線性表2.1線性表的類型定義2.2線性表的順序表示和實(shí)現(xiàn)2.3線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)2.3.1線性鏈表2.3.2循環(huán)鏈表2.3.3雙向鏈表2.4一元多項(xiàng)式的表示及相加第二十四頁(yè)，編輯于星期五：十三點(diǎn)四十四分。2.1線性表的邏輯結(jié)構(gòu)線性表(LinearList)：由n(n≧)個(gè)數(shù)據(jù)元素(結(jié)點(diǎn))a1，a2，…an組成的有限序列。其中數(shù)據(jù)元素的個(gè)數(shù)n定義為表的長(zhǎng)度。當(dāng)n=0時(shí)稱為空表，常常將非空的線性表(n>0)記作：(a1，a2，…an)這里的數(shù)據(jù)元素ai(1≦i≦n)只是一個(gè)抽象的符號(hào)，其具體含義在不同的情況下可以不同。例1、26個(gè)英文字母組成的字母表（A，B，C、…、Z）例2、某校從1978年到1983年各種型號(hào)的計(jì)算機(jī)擁有量的變化情況。（6，17，28，50，92，188）第二十五頁(yè)，編輯于星期五：十三點(diǎn)四十四分。例3、學(xué)生健康情況登記表如下：姓名學(xué)號(hào)性別年齡健康情況王小林790631男18健康陳紅790632女20一般劉建平790633男21健康張立立790634男17神經(jīng)衰弱……..……..…….…….…….第二十六頁(yè)，編輯于星期五：十三點(diǎn)四十四分。例4、一副撲克的點(diǎn)數(shù)（2，3，4，…，J，Q，K，A）從以上例子可看出線性表的邏輯特征是：在非空的線性表，有且僅有一個(gè)開(kāi)始結(jié)點(diǎn)a1，它沒(méi)有直接前趨，而僅有一個(gè)直接后繼a2；有且僅有一個(gè)終端結(jié)點(diǎn)an，它沒(méi)有直接后繼，而僅有一個(gè)直接前趨an-1；其余的內(nèi)部結(jié)點(diǎn)ai(2≦i≦n-1)都有且僅有一個(gè)直接前趨ai-1和一個(gè)直接后繼ai+1。線性表是一種典型的線性結(jié)構(gòu)。數(shù)據(jù)的運(yùn)算是定義在邏輯結(jié)構(gòu)上的，而運(yùn)算的具體實(shí)現(xiàn)則是在存儲(chǔ)結(jié)構(gòu)上進(jìn)行的。抽象數(shù)據(jù)類型的定義為：P19第二十七頁(yè)，編輯于星期五：十三點(diǎn)四十四分。

算法2.1例2-1利用兩個(gè)線性表LA和LB分別表示兩個(gè)集合A和B，現(xiàn)要求一個(gè)新的集合A=A∪B。voidunion(List&La，ListLb){La-len=listlength(La);Lb-len=listlength(Lb);for(I=1;I<=lb-len;I++){getelem(lb，I，e);if(!locateelem(la，e，equal))listinsert(la，++la-en，e)}}

第二十八頁(yè)，編輯于星期五：十三點(diǎn)四十四分。算法2.2例2-2巳知線性表LA和線性表LB中的數(shù)據(jù)元素按值非遞減有序排列，現(xiàn)要求將LA和LB歸并為一個(gè)新的線性表LC，且LC中的元素仍按值非遞減有序排列。此問(wèn)題的算法如下：

第二十九頁(yè)，編輯于星期五：十三點(diǎn)四十四分。voidmergelist(listla，listlb，list&lc)initlist(lc);I=j=1;k=0;la-len=listlength(la);lb-len=listlength(lb);while((I<=la-len)&&(j<=lb-len)){第三十頁(yè)，編輯于星期五：十三點(diǎn)四十四分。getelem(la，I，ai);getelem(lb，j，bj);if(ai<=bj){listinsert(lc，++k，ai);++I;}else{listinsert(lc，++k，bj);++j;}}while(I<=la-len){getelem((la，I++，ai);listinsert(lc，++k，ai);}while(j<=lb-len){getelem((lb，j++，bj);listinsert(lc，++k，bi);}}第三十一頁(yè)，編輯于星期五：十三點(diǎn)四十四分。2.2線性表的順序存儲(chǔ)結(jié)構(gòu)2.2.1線性表把線性表的結(jié)點(diǎn)按邏輯順序依次存放在一組地址連續(xù)的存儲(chǔ)單元里。用這種方法存儲(chǔ)的線性表簡(jiǎn)稱順序表。假設(shè)線性表的每個(gè)元素需占用l個(gè)存儲(chǔ)單元，并以所占的第一個(gè)單元的存儲(chǔ)地址作為數(shù)據(jù)元素的存儲(chǔ)位置。則線性表中第I+1個(gè)數(shù)據(jù)元素的存儲(chǔ)位置LOC(ai+1)和第i個(gè)數(shù)據(jù)元素的存儲(chǔ)位置LOC(aI)之間滿足下列關(guān)系：LOC(ai+1)=LOC(ai)+l線性表的第i個(gè)數(shù)據(jù)元素ai的存儲(chǔ)位置為：LOC(ai)=LOC(a1)+(I-1)*l

第三十二頁(yè)，編輯于星期五：十三點(diǎn)四十四分。由于C語(yǔ)言中的一維數(shù)組也是采用順序存儲(chǔ)表示，故可以用數(shù)組類型來(lái)描述順序表。又因?yàn)槌擞脭?shù)組來(lái)存儲(chǔ)線性表的元素之外，順序表還應(yīng)該用一個(gè)變量來(lái)表示線性表的長(zhǎng)度屬性，所以我們用結(jié)構(gòu)類型來(lái)定義順序表類型。#defineListSize100typedefintDataType;typedefstruc{DataTypedata[ListSize];intlength;}Sqlist;第三十三頁(yè)，編輯于星期五：十三點(diǎn)四十四分。2.2.2順序表上實(shí)現(xiàn)的基本操作在順序表存儲(chǔ)結(jié)構(gòu)中，很容易實(shí)現(xiàn)線性表的一些操作，如線性表的構(gòu)造、第i個(gè)元素的訪問(wèn)。注意：C語(yǔ)言中的數(shù)組下標(biāo)從“0”開(kāi)始，因此，若L是Sqlist類型的順序表，則表中第i個(gè)元素是l.data[I-1]。以下主要討論線性表的插入和刪除兩種運(yùn)算。1、插入線性表的插入運(yùn)算是指在表的第I(1≦i≦n+1個(gè)位置上，插入一個(gè)新結(jié)點(diǎn)x，第三十四頁(yè)，編輯于星期五：十三點(diǎn)四十四分。使長(zhǎng)度為n的線性表(a1，…ai-1，ai，…，an)變成長(zhǎng)度為n+1的線性表(a1，…ai-1，x，ai，…，an)

算法2.3VoidInsertList(Sqlist*L，DataTypex，intI){intj;if(I<1||I>l.length+1)printf(“Positionerror”);returnERROR

第三十五頁(yè)，編輯于星期五：十三點(diǎn)四十四分。if(l.length>=ListSize)printf(“overflow”);exit(overflow);for(j=l.length-1;j>=I-1;j--)l.data[j+1]=l.data[j];l.data[I-1]=x;l.length++;}第三十六頁(yè)，編輯于星期五：十三點(diǎn)四十四分?，F(xiàn)在分析算法的復(fù)雜度。這里的問(wèn)題規(guī)模是表的長(zhǎng)度，設(shè)它的值為。該算法的時(shí)間主要化費(fèi)在循環(huán)的結(jié)點(diǎn)后移語(yǔ)句上，該語(yǔ)句的執(zhí)行次數(shù)（即移動(dòng)結(jié)點(diǎn)的次數(shù)）是。由此可看出，所需移動(dòng)結(jié)點(diǎn)的次數(shù)不僅依賴于表的長(zhǎng)度，而且還與插入位置有關(guān)。當(dāng)時(shí)，由于循環(huán)變量的終值大于初值，結(jié)點(diǎn)后移語(yǔ)句將不進(jìn)行；這是最好情況，其時(shí)間復(fù)雜度O（1）；當(dāng)=1時(shí)，結(jié)點(diǎn)后移語(yǔ)句將循環(huán)執(zhí)行n次，需移動(dòng)表中所有結(jié)點(diǎn)，這是最壞情況，第三十七頁(yè)，編輯于星期五：十三點(diǎn)四十四分。其時(shí)間復(fù)雜度為O（n）。由于插入可能在表中任何位置上進(jìn)行，因此需分析算法的平均復(fù)雜度在長(zhǎng)度為n的線性表中第i個(gè)位置上插入一個(gè)結(jié)點(diǎn)，令Eis(n)表示移動(dòng)結(jié)點(diǎn)的期望值（即移動(dòng)的平均次數(shù)），則在第i個(gè)位置上插入一個(gè)結(jié)點(diǎn)的移動(dòng)次數(shù)為n-I+1。故Eis(n)=pi(n-I+1)不失一般性，假設(shè)在表中任何位置(1≦i≦n+1)上插入結(jié)點(diǎn)的機(jī)會(huì)是均等的，則p1=p2=p3=…=pn+1=1/(n+1)因此，在等概率插入的情況下，Eis(n)=(n-I+1)/(n+1)=n/2

第三十八頁(yè)，編輯于星期五：十三點(diǎn)四十四分。也就是說(shuō)，在順序表上做插入運(yùn)算，平均要移動(dòng)表上一半結(jié)點(diǎn)。當(dāng)表長(zhǎng)n較大時(shí)，算法的效率相當(dāng)?shù)?。雖然Eis(n)中n的的系數(shù)較小，但就數(shù)量級(jí)而言，它仍然是線性階的。因此算法的平均時(shí)間復(fù)雜度為O(n)。2、刪除線性表的刪除運(yùn)算是指將表的第i(1≦i≦n)結(jié)點(diǎn)刪除，使長(zhǎng)度為n的線性表：(a1，…ai-1，ai，ai+1…，an)變成長(zhǎng)度為n-1的線性表(a1，…ai-1，ai+1，…，an)第三十九頁(yè)，編輯于星期五：十三點(diǎn)四十四分。VoiddeleteList(Sqlist*L，intI){intj;if(I<1||I>l.length)printf(“Positionerror”);returnERRORfor(j=i;j<=l.length-1;j++)l.data[j-1]=l.data[j];l.length--;}

第四十頁(yè)，編輯于星期五：十三點(diǎn)四十四分。該算法的時(shí)間分析與插入算法相似，結(jié)點(diǎn)的移動(dòng)次數(shù)也是由表長(zhǎng)n和位置i決定。若I=n，則由于循環(huán)變量的初值大于終值，前移語(yǔ)句將不執(zhí)行，無(wú)需移動(dòng)結(jié)點(diǎn)；若I=1，則前移語(yǔ)句將循環(huán)執(zhí)行n-1次，需移動(dòng)表中除開(kāi)始結(jié)點(diǎn)外的所有結(jié)點(diǎn)。這兩種情況下算法的時(shí)間復(fù)雜度分別為O(1)和O(n)。刪除算法的平均性能分析與插入算法相似。在長(zhǎng)度為n的線性表中刪除一個(gè)結(jié)點(diǎn)，令Ede(n)表示所需移動(dòng)結(jié)點(diǎn)的平均次數(shù)，刪除表中第i個(gè)結(jié)點(diǎn)的移動(dòng)次數(shù)為n-i，故Ede(n)=pi(n-I)式中，pi表示刪除表中第i個(gè)結(jié)點(diǎn)的概率。在等第四十一頁(yè)，編輯于星期五：十三點(diǎn)四十四分。概率的假設(shè)下，p1=p2=p3=…=pn=1/n由此可得：Ede(n)=(n-I)/n=(n-1)/2即在順序表上做刪除運(yùn)算，平均要移動(dòng)表中約一半的結(jié)點(diǎn)，平均時(shí)間復(fù)雜度也是O(n)。

2.3線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)線性表的順序表示的特點(diǎn)是用物理位置上的鄰接關(guān)系來(lái)表示結(jié)點(diǎn)間的邏輯關(guān)系，這一特點(diǎn)使我們可以隨機(jī)存取表中的任一結(jié)點(diǎn)，但它也使得第四十二頁(yè)，編輯于星期五：十三點(diǎn)四十四分。插入和刪除操作會(huì)移動(dòng)大量的結(jié)點(diǎn).為避免大量結(jié)點(diǎn)的移動(dòng)，我們介紹線性表的另一種存儲(chǔ)方式，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，簡(jiǎn)稱為鏈表(LinkedList)。2.3.1線性鏈表鏈表是指用一組任意的存儲(chǔ)單元來(lái)依次存放線性表的結(jié)點(diǎn)，這組存儲(chǔ)單元即可以是連續(xù)的，也可以是不連續(xù)的，甚至是零散分布在內(nèi)存中的任意位置上的。因此，鏈表中結(jié)點(diǎn)的邏輯次序和物理次序不一定相同。為了能正確表示結(jié)點(diǎn)間的邏輯關(guān)系，在存儲(chǔ)每個(gè)結(jié)點(diǎn)值的同時(shí)，還必須存儲(chǔ)指示其后繼結(jié)點(diǎn)的地址（或位置）信息，這個(gè)信息稱為指針(pointer)或鏈(link)。這兩部分組成了鏈表中的結(jié)點(diǎn)結(jié)構(gòu)：第四十三頁(yè)，編輯于星期五：十三點(diǎn)四十四分。

其中：data域是數(shù)據(jù)域，用來(lái)存放結(jié)點(diǎn)的值。next是指針域（亦稱鏈域），用來(lái)存放結(jié)點(diǎn)的直接后繼的地址（或位置）。鏈表正是通過(guò)每個(gè)結(jié)點(diǎn)的鏈域?qū)⒕€性表的n個(gè)結(jié)點(diǎn)按其邏輯次序鏈接在一起的。由于上述鏈表的每一個(gè)結(jié)只有一個(gè)鏈域，故將這種鏈表稱為單鏈表（SingleLinked)。顯然，單鏈表中每個(gè)結(jié)點(diǎn)的存儲(chǔ)地址是存放在其前趨結(jié)點(diǎn)next域中，而開(kāi)始結(jié)點(diǎn)無(wú)前趨，故應(yīng)設(shè)頭指針head指向開(kāi)始結(jié)點(diǎn)。同時(shí)，由于終端結(jié)點(diǎn)無(wú)后繼，故終端結(jié)點(diǎn)的指針域?yàn)榭?，即null（圖示中也可用^表示)。例1、線性表:(bat，cat，eat，fat，hat，jat，lat，mat)datalink第四十四頁(yè)，編輯于星期五：十三點(diǎn)四十四分。的單鏈表示意圖如下：……110……130135……160頭指針head165170……200205…………………h(huán)at200…….……cat135eat170….……matNullbat130fat110…………jat205lat160…………165第四十五頁(yè)，編輯于星期五：十三點(diǎn)四十四分。headbatcateatmat^…單鏈表是由表頭唯一確定，因此單鏈表可以用頭指針的名字來(lái)命名。例如：若頭指針名是head，則把鏈表稱為表head。用C語(yǔ)言描述的單鏈表如下：Typedefchardatatype;

Typedefstructnode{datatypedata;structnode*next;}listnode;第四十六頁(yè)，編輯于星期五：十三點(diǎn)四十四分。typedeflistnode*linklist;listnode*p;linklisthead;注意區(qū)分指針變量和結(jié)點(diǎn)變量這兩個(gè)不同的概念。P為動(dòng)態(tài)變量，它是通過(guò)標(biāo)準(zhǔn)函數(shù)生成的，即p=(listnode*)malloc(sizeof(listnode));函數(shù)malloc分配了一個(gè)類型為listnode的結(jié)點(diǎn)變量的空間，并將其首地址放入指針變量p中。一旦p所指的結(jié)點(diǎn)變量不再需要了，又可通過(guò)標(biāo)準(zhǔn)函數(shù)free(p)釋放所指的結(jié)點(diǎn)變量空間。第四十七頁(yè)，編輯于星期五：十三點(diǎn)四十四分。指針變量P和（其值為結(jié)點(diǎn)地址）和結(jié)點(diǎn)變量*P之間的關(guān)系。第四十八頁(yè)，編輯于星期五：十三點(diǎn)四十四分。一、建立單鏈表假設(shè)線性表中結(jié)點(diǎn)的數(shù)據(jù)類型是字符，我們逐個(gè)輸入這些字符型的結(jié)點(diǎn)，并以換行符‘\n’為輸入結(jié)束標(biāo)記。動(dòng)態(tài)地建立單鏈表的常用方法有如下兩種：1、頭插法建表該方法從一個(gè)空表開(kāi)始，重復(fù)讀入數(shù)據(jù)，生成新結(jié)點(diǎn)，將讀入數(shù)據(jù)存放到新結(jié)點(diǎn)的數(shù)據(jù)域中，然后將新結(jié)點(diǎn)插入到當(dāng)前鏈表的表頭上，直到讀入結(jié)束標(biāo)志為止。第四十九頁(yè)，編輯于星期五：十三點(diǎn)四十四分。linklistcreatelistf(void){charch;linklisthead;listnode*p;head=null;ch=getchar();while(ch!=‵\n′{p=(listnode*)malloc(sizeof(listnode));p–>data=ch;p–>next=head;第五十頁(yè)，編輯于星期五：十三點(diǎn)四十四分。head=p;ch=getchar();}return(head);}第五十一頁(yè)，編輯于星期五：十三點(diǎn)四十四分。listlinkcreatelist(intn){intdata;linklisthead;listnode*phead=null;for(i=n;i>0;--i){p=(listnode*)malloc(sizeof(listnode));scanf((〝%d〞，&p–>data);p–>next=head;head=p;}第五十二頁(yè)，編輯于星期五：十三點(diǎn)四十四分。return(head);}2、尾插法建表

頭插法建立鏈表雖然算法簡(jiǎn)單，但生成的鏈表中結(jié)點(diǎn)的次序和輸入的順序相反。若希望二者次序一致，可采用尾插法建表。該方法是將新結(jié)點(diǎn)插入到當(dāng)前鏈表的表尾上，為此必須增加一個(gè)尾指針r，使其始終指向當(dāng)前鏈表的尾結(jié)點(diǎn)。例：第五十三頁(yè)，編輯于星期五：十三點(diǎn)四十四分。linklistcreater(){charch;linklisthead;listnode*p，*r;//(，*head;)head=NULL;r=NULL;while((ch=getchar()!=‵\n′){p=(listnode*)malloc(sizeof(listnode));p–>data=ch;if(head=NULL)head=p;else

第五十四頁(yè)，編輯于星期五：十三點(diǎn)四十四分。r–>next=p;r=p;}if(r!=NULL)r–>next=NULL;return(head);}說(shuō)明：第一個(gè)生成的結(jié)點(diǎn)是開(kāi)始結(jié)點(diǎn)，將開(kāi)始結(jié)點(diǎn)插入到空表中，是在當(dāng)前鏈表的第一個(gè)位置上插入，該位置上的插入操作和鏈表中其它位置上的插入操作處理是不一樣的，原因是開(kāi)始結(jié)點(diǎn)的位置是存放在頭指針（指針變量）中，

第五十五頁(yè)，編輯于星期五：十三點(diǎn)四十四分。而其余結(jié)點(diǎn)的位置是在其前趨結(jié)點(diǎn)的指針域中。算法中的第一個(gè)if語(yǔ)句就是用來(lái)對(duì)第一個(gè)位置上的插入操作做特殊處理。算法中的第二個(gè)if語(yǔ)句的作用是為了分別處理空表和非空表兩種不同的情況，若讀入的第一個(gè)字符就是結(jié)束標(biāo)志符，則鏈表head是空表，尾指針r亦為空，結(jié)點(diǎn)*r不存在；否則鏈表head非空，最后一個(gè)尾結(jié)點(diǎn)*r是終端結(jié)點(diǎn)，應(yīng)將其指針域置空。如果我們?cè)阪湵淼拈_(kāi)始結(jié)點(diǎn)之前附加一個(gè)結(jié)點(diǎn)，并稱它為頭結(jié)點(diǎn)，那么會(huì)帶來(lái)以下兩個(gè)優(yōu)點(diǎn)：a、由于開(kāi)始結(jié)點(diǎn)的位置被存放在頭結(jié)點(diǎn)的指針域中，所以在鏈表的第一個(gè)位置上的操作就第五十六頁(yè)，編輯于星期五：十三點(diǎn)四十四分。和在表的其它位置上的操作一致，無(wú)需進(jìn)行特殊處理；b、無(wú)論鏈表是否為空，其頭指針是指向頭結(jié)點(diǎn)在的非空指針（空表中頭結(jié)點(diǎn)的指針域?yàn)榭眨虼丝毡砗头强毡淼奶幚硪簿徒y(tǒng)一了。其算法如下：linklistcreatelistr1(){charch;linklisthead=(linklist)malloc(sizeof(listnode));listnode*p，*r

第五十七頁(yè)，編輯于星期五：十三點(diǎn)四十四分。r=head;while((ch=getchar())!=‵\n′{p=(listnode*)malloc(sizeof(listnode));p–>data=ch;p–>next=p;r=p;}r–>next=NULL;return(head);}第五十八頁(yè)，編輯于星期五：十三點(diǎn)四十四分。上述算法里動(dòng)態(tài)申請(qǐng)新結(jié)點(diǎn)空間時(shí)未加錯(cuò)誤處理，可作下列處理：p=(listnode*)malloc(sizeof(listnode))if(p==NULL)error(〝Nospacefornodecanbeobtained〞);returnERROR;

以上算法的時(shí)間復(fù)雜度均為O(n)。第五十九頁(yè)，編輯于星期五：十三點(diǎn)四十四分。二、查找運(yùn)算

1、按序號(hào)查找在鏈表中，即使知道被訪問(wèn)結(jié)點(diǎn)的序號(hào)i，也不能象順序表中那樣直接按序號(hào)i訪問(wèn)結(jié)點(diǎn)，而只能從鏈表的頭指針出發(fā)，順鏈域next逐個(gè)結(jié)點(diǎn)往下搜索，直到搜索到第i個(gè)結(jié)點(diǎn)為止。因此，鏈表不是隨機(jī)存取結(jié)構(gòu)。設(shè)單鏈表的長(zhǎng)度為n，要查找表中第i個(gè)結(jié)點(diǎn)，僅當(dāng)1≦i≦n時(shí)，i的值是合法的。但有時(shí)需要找頭結(jié)點(diǎn)的位置，故我們將頭結(jié)點(diǎn)看做是第0個(gè)結(jié)點(diǎn)，其算法如下：第六十頁(yè)，編輯于星期五：十三點(diǎn)四十四分。Listnode*getnode(linklisthead，inti){intj;listnode*p;p=head;j=0;while(p–>next&&j<I){p=p–>next;j++;}if(i==j)returnp;第六十一頁(yè)，編輯于星期五：十三點(diǎn)四十四分。

elsereturnNULL;}

2、按值查找按值查找是在鏈表中，查找是否有結(jié)點(diǎn)值等于給定值key的結(jié)點(diǎn)，若有的話，則返回首次找到的其值為key的結(jié)點(diǎn)的存儲(chǔ)位置；否則返回NULL。查找過(guò)程從開(kāi)始結(jié)點(diǎn)出發(fā)，順著鏈表逐個(gè)將結(jié)點(diǎn)的值和給定值key作比較。其算法如下：第六十二頁(yè)，編輯于星期五：十三點(diǎn)四十四分。Listnode*locatenode(linklisthead，intkey){listnode*p=head–>next;while(p&&p–>data!=key)p=p–>next;returnp;}

該算法的執(zhí)行時(shí)間亦與輸入實(shí)例中的的取值key有關(guān)，其平均時(shí)間復(fù)雜度的分析類似于按序號(hào)查找，也為O(n)。第六十三頁(yè)，編輯于星期五：十三點(diǎn)四十四分。三、插入運(yùn)算插入運(yùn)算是將值為x的新結(jié)點(diǎn)插入到表的第i個(gè)結(jié)點(diǎn)的位置上，即插入到ai-1與ai之間。因此，我們必須首先找到ai-1的存儲(chǔ)位置p，然后生成一個(gè)數(shù)據(jù)域?yàn)閤的新結(jié)點(diǎn)*p，并令結(jié)點(diǎn)*p的指針域指向新結(jié)點(diǎn)，新結(jié)點(diǎn)的指針域指向結(jié)點(diǎn)ai。從而實(shí)現(xiàn)三個(gè)結(jié)點(diǎn)ai-1，x和ai之間的邏輯關(guān)系的變化，插入過(guò)程如：第六十四頁(yè)，編輯于星期五：十三點(diǎn)四十四分。具體算法如下：voidinsertnode(linklisthead，datetypex，inti){listnode*p，*q;p=getnode(head，i-1);if(p==NULL)error(〝positionerror〞);q=(listnode*)malloc(sizeof(listnode));q–>data=x;q–>next=p–next;p–>next=q;}第六十五頁(yè)，編輯于星期五：十三點(diǎn)四十四分。設(shè)鏈表的長(zhǎng)度為n，合法的插入位置是1≦i≦n+1。注意當(dāng)i=1時(shí)，getnode找到的是頭結(jié)點(diǎn)，當(dāng)i=n+1時(shí)，getnode找到的是結(jié)點(diǎn)an。因此，用i-1做實(shí)參調(diào)用getnode時(shí)可完成插入位置的合法性檢查。算法的時(shí)間主要耗費(fèi)在查找操作getnode上，故時(shí)間復(fù)雜度亦為O(n)。四、刪除運(yùn)算刪除運(yùn)算是將表的第i個(gè)結(jié)點(diǎn)刪去。因?yàn)樵趩捂湵碇薪Y(jié)點(diǎn)ai的存儲(chǔ)地址是在其直接前趨結(jié)點(diǎn)aai-1的指針域next中，所以我們必須首先找到

第六十六頁(yè)，編輯于星期五：十三點(diǎn)四十四分。ai-1的存儲(chǔ)位置p。然后令p–>next指向ai的直接后繼結(jié)點(diǎn)，即把a(bǔ)i從鏈上摘下。最后釋放結(jié)點(diǎn)ai的空間，將其歸還給“存儲(chǔ)池”。此過(guò)程為：第六十七頁(yè)，編輯于星期五：十三點(diǎn)四十四分。具體算法如下：voiddeletelist(linklisthead，inti){listnode*p，*r;p=getnode(head，i-1);if(p==NULL||p–>next==NULL)returnERROR;r=p–>next;p–>next=r–>next;free(r);}第六十八頁(yè)，編輯于星期五：十三點(diǎn)四十四分。

設(shè)單鏈表的長(zhǎng)度為n，則刪去第i個(gè)結(jié)點(diǎn)僅當(dāng)1≦i≦n時(shí)是合法的。注意，當(dāng)i=n+1時(shí)，雖然被刪結(jié)點(diǎn)不存在，但其前趨結(jié)點(diǎn)卻存在，它是終端結(jié)點(diǎn)。因此被刪結(jié)點(diǎn)的直接前趨*p存在并不意味著被刪結(jié)點(diǎn)就一定存在，僅當(dāng)*p存在（即p!=NULL）且*p不是終端結(jié)點(diǎn)（即p–>next!=NULL）時(shí)，才能確定被刪結(jié)點(diǎn)存在。顯然此算法的時(shí)間復(fù)雜度也是O(n)。從上面的討論可以看出，鏈表上實(shí)現(xiàn)插入和刪除運(yùn)算，無(wú)須移動(dòng)結(jié)點(diǎn)，僅需修改指針。第六十九頁(yè)，編輯于星期五：十三點(diǎn)四十四分。2.3.2循環(huán)鏈表

循環(huán)鏈表時(shí)一種頭尾相接的鏈表。其特點(diǎn)是無(wú)須增加存儲(chǔ)量，僅對(duì)表的鏈接方式稍作改變，即可使得表處理更加方便靈活。單循環(huán)鏈表：在單鏈表中，將終端結(jié)點(diǎn)的指針域NULL改為指向表頭結(jié)點(diǎn)的或開(kāi)始結(jié)點(diǎn)，就得到了單鏈形式的循環(huán)鏈表，并簡(jiǎn)單稱為單循環(huán)鏈表。為了使空表和非空表的處理一致，循環(huán)鏈表中也可設(shè)置一個(gè)頭結(jié)點(diǎn)。這樣，空循環(huán)鏈表僅有一個(gè)自成循環(huán)的頭結(jié)點(diǎn)表示。如下圖所示：第七十頁(yè)，編輯于星期五：十三點(diǎn)四十四分。

a1an

….head⑴非空表⑵空表在用頭指針表示的單鏈表中，找開(kāi)始結(jié)點(diǎn)a1的時(shí)間是O(1)，然而要找到終端結(jié)點(diǎn)an，則需從頭指針開(kāi)始遍歷整個(gè)鏈表，其時(shí)間是O(n)第七十一頁(yè)，編輯于星期五：十三點(diǎn)四十四分。在很多實(shí)際問(wèn)題中，表的操作常常是在表的首尾位置上進(jìn)行，此時(shí)頭指針表示的單循環(huán)鏈表就顯得不夠方便.如果改用尾指針rear來(lái)表示單循環(huán)鏈表，則查找開(kāi)始結(jié)點(diǎn)a1和終端結(jié)點(diǎn)an都很方便，它們的存儲(chǔ)位置分別是(rear–>next)—>next和rear，顯然，查找時(shí)間都是O(1)。因此，實(shí)際中多采用尾指針表示單循環(huán)鏈表。由于循環(huán)鏈表中沒(méi)有NULL指針，故涉及遍歷操作時(shí)，其終止條件就不再像非循環(huán)鏈表那樣判斷p或p—>next是否為空，而是判斷它們是否等于某一指定指針，如頭指什或尾指針等。第七十二頁(yè)，編輯于星期五：十三點(diǎn)四十四分。例、在鏈表上實(shí)現(xiàn)將兩個(gè)線性表(a1，a2，a3，…an)和(b1，b2，b3，…bn)鏈接成一個(gè)線性表的運(yùn)算。linklistconnect(linklistheada，linklistheadb){linklistp=heada—>next;heada—>next=(headb—next)—>nextfree(headb—>next);headb—>next=p;return(headb);}第七十三頁(yè)，編輯于星期五：十三點(diǎn)四十四分。2.3.3雙鏈表雙向鏈表(Doublelinkedlist):在單鏈表的每個(gè)結(jié)點(diǎn)里再增加一個(gè)指向其直接前趨的指針域prior。這樣就形成的鏈表中有兩個(gè)方向不同的鏈，故稱為雙向鏈表。形式描述為：

typedefstructdlistnode{datatypedata;strucdlistnode*prior，*next;}dlistnode;typedefdlistnode*dlinklist;dlinklisthead;第七十四頁(yè)，編輯于星期五：十三點(diǎn)四十四分。和單鏈表類似，雙鏈表一般也是由頭指針唯一確定的，增加頭指針也能使雙鏈表上的某些運(yùn)算變得方便，將頭結(jié)點(diǎn)和尾結(jié)點(diǎn)鏈接起來(lái)也能構(gòu)成循環(huán)鏈表，并稱之為雙向鏈表。設(shè)指針p指向某一結(jié)點(diǎn)，則雙向鏈表結(jié)構(gòu)的對(duì)稱性可用下式描述：(p—>prior)—>next=p=(p—>next)—>prior即結(jié)點(diǎn)*p的存儲(chǔ)位置既存放在其前趨結(jié)點(diǎn)*(p—>prior)的直接后繼指針域中，也存放在它的后繼結(jié)點(diǎn)*(p—>next)的直接前趨指針域中。第七十五頁(yè)，編輯于星期五：十三點(diǎn)四十四分。雙向鏈表的前插操作算法如下：voiddinsertbefor(dlistnode*p，datatypex){dlistnode*q=malloc(sizeof(dlistnode));q—>data=x;q—>prior=p—>prior;q—>next=p;p—>prior—>next=q;p—>prior=q;}第七十六頁(yè)，編輯于星期五：十三點(diǎn)四十四分。voidddeletenode(dlistnode*p){p–>prior–>next=p–>next;p–>next–>prior=p–>prior;free(p);}

注意：與單鏈表的插入和刪除操作不同的是，在雙鏈表中插入和刪除必須同時(shí)修改兩個(gè)方向上的指針。上述兩個(gè)算是法的時(shí)間復(fù)雜度均為O(1)。第七十七頁(yè)，編輯于星期五：十三點(diǎn)四十四分。

第三章棧和隊(duì)列3.1棧3.1.1抽象數(shù)據(jù)類型棧的定義3.1.2棧的表示和實(shí)現(xiàn)3.2棧的應(yīng)用舉例3.2.1數(shù)制轉(zhuǎn)換3.2.2括號(hào)匹配的檢驗(yàn)3.2.4行編輯程序3.2.5迷宮求解3.2.5表達(dá)式求值第七十八頁(yè)，編輯于星期五：十三點(diǎn)四十四分。

3.1.1棧3.1.1棧的定義及基本運(yùn)算棧(Stack)是限制在表的一端進(jìn)行插入和刪除運(yùn)算的線性表，通常稱插入、刪除的這一端為棧頂(Top)，另一端為棧底(Bottom)。當(dāng)表中沒(méi)有元素時(shí)稱為空棧。假設(shè)棧S=(a1，a2，a3，…an)，則a1稱為棧底元素，an為棧頂元素。棧中元素按a1，a2，a3，…an的次序進(jìn)棧，退棧的第一個(gè)元素應(yīng)為棧頂元素。換句話說(shuō)，棧的修改是按后進(jìn)先出的原則進(jìn)行的。因此，棧稱為后進(jìn)先出表（LIFO）。第七十九頁(yè)，編輯于星期五：十三點(diǎn)四十四分。3.1.2順序棧由于棧是運(yùn)算受限的線性表，因此線性表的存儲(chǔ)結(jié)構(gòu)對(duì)棧也適應(yīng)。棧的順序存儲(chǔ)結(jié)構(gòu)簡(jiǎn)稱為順序棧，它是運(yùn)算受限的線性表。因此，可用數(shù)組來(lái)實(shí)現(xiàn)順序棧。因?yàn)闂５孜恢檬枪潭ú蛔兊模钥梢詫５孜恢迷O(shè)置在數(shù)組的兩端的任何一個(gè)端點(diǎn)；棧頂位置是隨著進(jìn)棧和退棧操作而變化的，故需用一個(gè)整型變量top第八十頁(yè)，編輯于星期五：十三點(diǎn)四十四分。例、一疊書或一疊盤子。

棧的抽象數(shù)據(jù)類型的定義如下：P44

anan-1a2a1……棧頂棧底第八十一頁(yè)，編輯于星期五：十三點(diǎn)四十四分。top7654321-1第八十二頁(yè)，編輯于星期五：十三點(diǎn)四十四分。來(lái)指示當(dāng)前棧頂?shù)奈恢?，通常稱top為棧頂指針。因此，順序棧的類型定義只需將順序表的類型定義中的長(zhǎng)度屬性改為top即可。順序棧的類型定義如下：#defineStackSize100typedefchardatatype;typedefstruct{datatypedata[stacksize];inttop;}seqstack;第八十三頁(yè)，編輯于星期五：十三點(diǎn)四十四分。設(shè)S是SeqStack類型的指針變量。若棧底位置在向量的低端，即s–>data[0]是棧底元素，那么棧頂指針s–>top是正向增加的，即進(jìn)棧時(shí)需將s–>top加1，退棧時(shí)需將s–>top減1。因此，s–>top<0表示空棧，s–>top=stacksize-1表示棧滿。當(dāng)棧滿時(shí)再做進(jìn)棧運(yùn)算必定產(chǎn)生空間溢出，簡(jiǎn)稱“上溢”;當(dāng)棧空時(shí)再做退棧運(yùn)算也將產(chǎn)生溢出，簡(jiǎn)稱“下溢”。上溢是一種出錯(cuò)狀態(tài)，應(yīng)該設(shè)法避免之；下溢則可能是正?，F(xiàn)象，因?yàn)闂Ｔ诔绦蛑惺褂脮r(shí)，其初態(tài)或終態(tài)都是空棧，所以下溢常常用來(lái)作為程序控制轉(zhuǎn)移的條件。第八十四頁(yè)，編輯于星期五：十三點(diǎn)四十四分。3、判斷棧滿intstackfull(seqstack*s){return(s–>top==stacksize-1);}4、進(jìn)棧voidpush(seqstack*s，datatypex){if(stackfull(s))error(“stackoverflow”);s–>data[++s–>top]=x;}第八十五頁(yè)，編輯于星期五：十三點(diǎn)四十四分。1、置空棧voidinitstack(seqstack*s){s–>top=-1;}2、判斷?？読ntstackempty(seqstack*s){return(s–>top==-1);}第八十六頁(yè)，編輯于星期五：十三點(diǎn)四十四分。5、退棧datatypepop(seqstack*s){if(stackempty(s))error(“stackunderflow”);x=s–>data[top];s–>top--;return(x)//return(s–>data[s–>top--]);}

第八十七頁(yè)，編輯于星期五：十三點(diǎn)四十四分。6、取棧頂元素Datatypestacktop(seqstack*s){if(stackempty(s)error(“stackisenpty”);returns–>data[s–>top];}

第八十八頁(yè)，編輯于星期五：十三點(diǎn)四十四分。3.1.3鏈棧棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)稱為鏈棧，它是運(yùn)算是受限的單鏈表，克插入和刪除操作僅限制在表頭位置上進(jìn)行.由于只能在鏈表頭部進(jìn)行操作，故鏈表沒(méi)有必要像單鏈表那樣附加頭結(jié)點(diǎn)。棧頂指針就是鏈表的頭指針。鏈棧的類型說(shuō)明如下：typedefstructstacknode{datatypedatastructstacknode*next}stacknode;第八十九頁(yè)，編輯于星期五：十三點(diǎn)四十四分。Voidinitstack(seqstack*p){p–>top=null;}intstackempty(linkstack*p){returnp–>top==null;}

第九十頁(yè)，編輯于星期五：十三點(diǎn)四十四分。Voidpush(linkstack*p,datatypex){stacknode*qq=(stacknode*)malloc(sizeof(stacknode));q–>data=x;q–>next=p–>top;p–>top=p;}第九十一頁(yè)，編輯于星期五：十三點(diǎn)四十四分。Datatypepop(linkstack*p){datatypex;stacknode*q=p–>top;if(stackempty(p)error(“stackunderflow.”);x=q–>data;p–>top=q–>next;free(q);returnx;}第九十二頁(yè)，編輯于星期五：十三點(diǎn)四十四分。datatypestacktop(linkstack*p){if(stackempty(p))error(“stackisempty.”);returnp–>top–>data;}第九十三頁(yè)，編輯于星期五：十三點(diǎn)四十四分。

3.2棧的應(yīng)用舉例由于棧結(jié)構(gòu)具有的后進(jìn)先出的固有特性，致使棧成為程序設(shè)計(jì)中常用的工具。以下是幾個(gè)棧應(yīng)用的例子。

3.2.1數(shù)制轉(zhuǎn)換

十進(jìn)制N和其它進(jìn)制數(shù)的轉(zhuǎn)換是計(jì)算機(jī)實(shí)現(xiàn)計(jì)算的基本問(wèn)題,其解決方法很多,其中一個(gè)簡(jiǎn)單算法基于下列原理:N=(ndivd)*d+nmodd(其中:div為整除運(yùn)算,mod為求余運(yùn)算)例如(1348)10=(2504)8，其運(yùn)算過(guò)程如下：第九十四頁(yè)，編輯于星期五：十三點(diǎn)四十四分。nndiv8nmod8134816841682102125202第九十五頁(yè)，編輯于星期五：十三點(diǎn)四十四分。voidconversion(){initstack(s);scanf(“%”,n);while(n){push(s,n%8);n=n/8;}while(!Stackempty(s)){pop(s,e);printf(“%d”,e);}}第九十六頁(yè)，編輯于星期五：十三點(diǎn)四十四分。3.2.2括號(hào)匹配的檢驗(yàn)

假設(shè)表達(dá)式中充許括號(hào)嵌套,則檢驗(yàn)括號(hào)是否匹配的方法可用“期待的急迫程度”這個(gè)概念來(lái)描述。例：（（）（）（（）））3.2.3行編輯程序

在編輯程序中，設(shè)立一個(gè)輸入緩沖區(qū)，用于接受用戶輸入的一行字符，然后逐行存入用戶數(shù)據(jù)區(qū)。允許用戶輸入錯(cuò)誤，并在發(fā)現(xiàn)有誤時(shí)可以及時(shí)更正。

第九十七頁(yè)，編輯于星期五：十三點(diǎn)四十四分。行編輯程序算法如下:voidlineedit(){initstack(s);ch=gether();while(ch!=eof){while(ch!=eof&&ch!=‘\n’){

switch(ch){case‘#’:pop(s,c);case‘@’:clearstack(s);default:push(s,ch);}第九十八頁(yè)，編輯于星期五：十三點(diǎn)四十四分。ch=getchar();}clearstack(s);if(ch!=eof)ch=gethar();}destroystack(s);}第九十九頁(yè)，編輯于星期五：十三點(diǎn)四十四分。3.2.4迷宮求解

入口出口第一百頁(yè)，編輯于星期五：十三點(diǎn)四十四分。3.4隊(duì)列3.4.1抽象數(shù)據(jù)類型隊(duì)列的定義隊(duì)列(Queue)也是一種運(yùn)算受限的線性表。它只允許在表的一端進(jìn)行插入，而在另一端進(jìn)行刪除。允許刪除的一端稱為隊(duì)頭(front)，允許插入的一端稱為隊(duì)尾(rear)。例如：排隊(duì)購(gòu)物。操作系統(tǒng)中的作業(yè)排隊(duì)。先進(jìn)入隊(duì)列的成員總是先離開(kāi)隊(duì)列。因此隊(duì)列亦稱作先進(jìn)先出(FirstInFirstOut)的線性表，簡(jiǎn)稱FIFO表。當(dāng)隊(duì)列中沒(méi)有元素時(shí)稱為空隊(duì)列。在空隊(duì)列中依次加入元素a1,a2,…an之后，a1是隊(duì)頭元素，an是隊(duì)尾元素。顯然退出隊(duì)列的次序也只能是a1,a2,…an，也就是說(shuō)隊(duì)列的修改是依先進(jìn)先出的原則進(jìn)行的。第一百零一頁(yè)，編輯于星期五：十三點(diǎn)四十四分。下圖是隊(duì)列的示意圖：

a1a2…an

出隊(duì)入隊(duì)隊(duì)頭隊(duì)尾隊(duì)列的抽象數(shù)據(jù)定義見(jiàn)書Ｐ593.4.2循環(huán)隊(duì)列－隊(duì)列的順序表示和實(shí)現(xiàn)

隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)稱為順序隊(duì)列，順序隊(duì)列實(shí)際上是運(yùn)算受限的順序表，和順序表一樣，順序隊(duì)列也是必須用一個(gè)向量空間來(lái)存放當(dāng)前隊(duì)第一百零二頁(yè)，編輯于星期五：十三點(diǎn)四十四分。列中的元素。由于隊(duì)列的隊(duì)頭和隊(duì)尾的位置是變化的，因而要設(shè)兩個(gè)指針和分別指示隊(duì)頭和隊(duì)尾元素在隊(duì)列中的位置，它們的初始值地隊(duì)列初始化時(shí)均應(yīng)置為０。入隊(duì)時(shí)將新元素插入所指的位置，然后將加１。出隊(duì)時(shí)，刪去所指的元素，然后將加１并返回被刪元素。由此可見(jiàn)，當(dāng)頭尾指針相等時(shí)隊(duì)列為空。在非空隊(duì)列里，頭指針始終指向隊(duì)頭元素，而尾指針始終指向隊(duì)尾元素的下一位置。０１２３0123

FrontrearabcFrontrear

(a)隊(duì)列初始為空（b）A,B,C入隊(duì)第一百零三頁(yè)，編輯于星期五：十三點(diǎn)四十四分。０１２３０１２３bc

frontrearfrontrear（c)a出隊(duì)(d)b,c出隊(duì)，隊(duì)為空和棧類似，隊(duì)列中亦有上溢和下溢現(xiàn)象。此外，順序隊(duì)列中還存在“假上溢”現(xiàn)象。因?yàn)樵谌腙?duì)和出隊(duì)的操作中，頭尾指針只增加不減小，致使被刪除元素的空間永遠(yuǎn)無(wú)法重新利用。因此，盡管隊(duì)列中實(shí)際的元素個(gè)數(shù)遠(yuǎn)遠(yuǎn)小于向量空間的規(guī)模，但也可能由于尾指針?biāo)瘸鱿蛄靠臻g的上界而不能做入隊(duì)操作。該現(xiàn)象稱為假上溢。第一百零四頁(yè)，編輯于星期五：十三點(diǎn)四十四分。為充分利用向量空間?？朔鲜黾偕弦绗F(xiàn)象的方法是將向量空間想象為一個(gè)首尾相接的圓環(huán)，并稱這種向量為循環(huán)向量，存儲(chǔ)在其中的隊(duì)列稱為循環(huán)隊(duì)列（CircularQueue)。在循環(huán)隊(duì)列中進(jìn)行出隊(duì)、入隊(duì)操作時(shí)，頭尾指針仍要加1，朝前移動(dòng)。只不過(guò)當(dāng)頭尾指針指向向量上界（QueueSize-1）時(shí)，其加1操作的結(jié)果是指向向量的下界0。這種循環(huán)意義下的加1操作可以描述為：if(I+1==QueueSize)i=0;elsei++;

利用模運(yùn)算可簡(jiǎn)化為：i=(i+1)%QueueSize第一百零五頁(yè)，編輯于星期五：十三點(diǎn)四十四分。顯然，因?yàn)檠h(huán)隊(duì)列元素的空間可以被利用，除非向量空間真的被隊(duì)列元素全部占用，否則不會(huì)上溢。因此，除一些簡(jiǎn)單的應(yīng)用外，真正實(shí)用的順序隊(duì)列是循環(huán)隊(duì)列。如圖所示：由于入隊(duì)時(shí)尾指針向前追趕頭指針，出隊(duì)時(shí)頭指針向前追趕尾指針，故隊(duì)空和隊(duì)滿時(shí)頭尾指針均相等。因此，我們無(wú)法通過(guò)front=rear來(lái)判斷隊(duì)列“空”還是“滿”。解決此問(wèn)題的方法至少有三種：其一是另設(shè)一個(gè)布爾變量以匹別隊(duì)列的空和滿；其二是少用一個(gè)元素的空間，約定入隊(duì)前，測(cè)試尾指針在循環(huán)意義下加1后是否等于頭指針，若相等則認(rèn)為隊(duì)滿（注意：rear所指的單元始終為空）；第一百零六頁(yè)，編輯于星期五：十三點(diǎn)四十四分。其三是使用一個(gè)計(jì)數(shù)器記錄隊(duì)列中元素的總數(shù)（實(shí)際上是隊(duì)列長(zhǎng)度）。下面我們用第三種方法實(shí)現(xiàn)循環(huán)隊(duì)列上的六種基本操作，為此先給出循環(huán)隊(duì)列的類型定義。#defineQueueSize100typedefcharDataType;typedefStruct{intfront;intrear;intcount;datatypedata[queuesize]}cirqueue;第一百零七頁(yè)，編輯于星期五：十三點(diǎn)四十四分。（1）置空隊(duì)voidinitqueue(cirqueue*q){q–>front=q–>rear=0;q–>count=0;}（2）判斷隊(duì)空intqueueempty(cirqueue*q){returnq–>count==0;}（3）判斷隊(duì)滿intqueuefull(cirqueue*q){returnq–>count==queuesize;}第一百零八頁(yè)，編輯于星期五：十三點(diǎn)四十四分。（4）入隊(duì)voidenqueue(cirqueue*q,datatypex){if(queuefull(q))error(“queueoverflow”);q–>count++;q