250頁(yè)的精品清華大學(xué)嚴(yán)蔚敏數(shù)據(jù)結(jié)構(gòu)-課件

1、數(shù) 據(jù) 結(jié) 構(gòu)計(jì)算機(jī)系第一章 緒 論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ǔ)空間的需求 第一章 緒 論計(jì)算機(jī)是一門(mén)研究用計(jì)算機(jī)進(jìn)行信息表示和處理的科學(xué)。這里面涉及到兩個(gè)問(wèn)題： 信息的表示 信息的處理 而信息的表示和組又直接關(guān)系到處理信息的程序的效率。隨著計(jì)算機(jī)的普及，信息量的增加，信息范圍的拓寬，使許多系統(tǒng)程序和應(yīng)用程序的規(guī)模很大，結(jié)構(gòu)又相當(dāng)復(fù)雜。因此，為了編寫(xiě)出一個(gè)“好”的程序，必須分析待處理的對(duì)象的特征及各對(duì)象之間存在的關(guān)系，這就是數(shù)據(jù)

2、結(jié)構(gòu)這門(mén)課所要研究的問(wè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，2n) 分別表示某人的名字和對(duì)應(yīng)的電話號(hào)碼要求設(shè)計(jì)一個(gè)算法，當(dāng)給定任何一個(gè)人的名字時(shí)，該算法能夠打印出此人的電話號(hào)碼，如果該電話簿中根本就沒(méi)有這個(gè)人，則該算法也能夠報(bào)告沒(méi)有這個(gè)人的標(biāo)志。

3、算法的設(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)， 1in 數(shù)據(jù)結(jié)構(gòu)還要提供每種結(jié)構(gòu)類型所定義的各種運(yùn)算的算法。例2、圖書(shū)館的書(shū)目檢索系統(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)算，而且確保

4、經(jīng)過(guò)這些運(yùn)算后所得到的新結(jié)構(gòu)仍然是原來(lái)的結(jié)構(gòu)類型。 1.2 基本概念和術(shù)語(yǔ)數(shù)據(jù)(Data):是對(duì)信息的一種符號(hào)表示。在計(jì)算機(jī)科學(xué)中是指所有能輸入到計(jì)算機(jī)中并被計(jì)算機(jī)程序處理的符號(hào)的總稱。數(shù)據(jù)元素(Data Element):是數(shù)據(jù)的基本單位，在計(jì)算機(jī)程序中通常作為一個(gè)整體進(jìn)行考慮和處理。 一個(gè)數(shù)據(jù)元素可由若干個(gè)數(shù)據(jù)項(xiàng)組成。數(shù)據(jù)項(xiàng)是數(shù)據(jù)的不可分割的最小單位。數(shù)據(jù)對(duì)象(Data Object)：是性質(zhì)相同的數(shù)據(jù)元素的集合。是數(shù)據(jù)的一個(gè)子集。數(shù)據(jù)結(jié)構(gòu)(Data Structure)：是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。數(shù)據(jù)結(jié)構(gòu)主要指邏輯結(jié)構(gòu)和物理結(jié)構(gòu) 數(shù)據(jù)之間的相互關(guān)系稱為邏輯結(jié)構(gòu)。通

5、常分為四類基本結(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)系。 數(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)，又稱

6、為存儲(chǔ)結(jié)構(gòu)。 數(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)上的一組算法。用三元組描述如下：（，）數(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è)存放地址的指針域（ ），用

7、此指針來(lái)表示數(shù)據(jù)元素之間的邏輯關(guā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)， 1.3 抽象數(shù)據(jù)類型的表示和實(shí)現(xiàn)P11 1.4 算法和算法分析算法：是對(duì)特定問(wèn)題求解步驟的一種描述 算法是指令的有限序列，其中每一條指令表示一個(gè)或多個(gè)操作。 算法具有以下五個(gè)特性

8、：（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)的。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)該好讀。以

9、有利于閱讀者對(duì)程序的理解。 (3)健狀性(Robustness) 算法應(yīng)具有容錯(cuò)處理。當(dāng)輸入非法數(shù)據(jù)時(shí)，算法應(yīng)對(duì)其作出反應(yīng)，而不是產(chǎn)年莫名其妙的輸出結(jié)果。(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ì)于所有的nn0，有f(n) cg(n) 則記作 f(n)=O(g(n)一般情況下，算法中

10、基本操作重復(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) cIj=0; for(k=1;k=n;+k) cIj+=aIk*bkj; 由于是一個(gè)三重循環(huán)，每個(gè)循環(huán)從1到n，則總次數(shù)為: nnn=n3時(shí)間復(fù)雜度為T(mén)(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ǔ)句頻度為

11、：2n其時(shí)間復(fù)雜度為：O(n) 即時(shí)間復(fù)雜度為線性階。例、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)=a m n m +a m-1 n m-1 +a1n+a0是一個(gè)m次多項(xiàng)式，則A(n)=O(n m)證略。例for(i=2;i=n;+I) for(j=2;j=i-1;+j) +x;ai，j=x;語(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í)間為

12、O(1)的算法，它的基本運(yùn)算執(zhí)行的次數(shù)是固定的。因此，總的時(shí)間由一個(gè)常數(shù)（即零次多項(xiàng)式）來(lái)限界。而一個(gè)時(shí)間為O(n2)的算法則由一個(gè)二次多項(xiàng)式來(lái)限界。 以下六種計(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!)1 & change;-I) change=false; for(j=0;jaj+1) aj aj+1; change=TURE 最好情況：0次 最壞情況：1+2+3+n-1 =n(n-1)/2 平均時(shí)間復(fù)雜度為:O(n2)1.4.4算法的存儲(chǔ)空間需求空間復(fù)雜度:算法所需存儲(chǔ)空間的度量，

13、記作: S(n)=O(f(n) 其中n為問(wèn)題的規(guī)模(或大小) 第二章 線性表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)式的表示及相加2.1 線性表的邏輯結(jié)構(gòu)線性表(Linear List) ：由n(n)個(gè)數(shù)據(jù)元素(結(jié)點(diǎn))a1，a2， an組成的有限序列。其中數(shù)據(jù)元素的個(gè)數(shù)n定義為表的長(zhǎng)度。當(dāng)n=0時(shí)稱為空表，常常將非空的線性表(n0)記作： (a1，a2，an) 這里的數(shù)據(jù)元素ai(1in)只是一個(gè)抽象的符號(hào)，其具體含義在不同的情況下可以不同。例1、26個(gè)英文字母組成的

14、字母表 （A，B，C、Z）例2、某校從1978年到1983年各種型號(hào)的計(jì)算機(jī)擁有量的變化情況。 （6，17，28，50，92，188）例3、學(xué)生健康情況登記表如下：姓 名學(xué) 號(hào)性 別年齡 健康情況王小林790631 男 18 健康陳 紅790632 女 20 一般劉建平790633 男 21 健康張立立790634 男 17 神經(jīng)衰弱 . . .例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è)直接前趨a n-1；其余的內(nèi)

15、部結(jié)點(diǎn)ai(2in-1)都有且僅有一個(gè)直接前趨a i-1和一個(gè)直接后繼a i+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 算法2.1例2-1 利用兩個(gè)線性表LA和LB分別表示兩個(gè)集合A和B，現(xiàn)要求一個(gè)新的集合A=AB。 void union(List &La，List Lb) La-len=listlength(La); Lb-len=listlength(Lb); for(I=1;I=lb-len;I+) getelem(lb，I，e); if(!locateelem(la，e，equal)listi

16、nsert(la，+la-en，e) 算法2.2例2-2 巳知線性表LA和線性表LB中的數(shù)據(jù)元素按值非遞減有序排列，現(xiàn)要求將LA和LB歸并為一個(gè)新的線性表LC，且LC中的元素仍按值非遞減有序排列。 此問(wèn)題的算法如下： void mergelist(list la，list lb，list &lc) initlist(lc); I=j=1;k=0; la-len=listlength(la); lb-len=listlength(lb); while(I=la-len)&(j=lb-len) getelem(la，I，ai);getelem(lb，j，bj); if(ai=bj)listinse

17、rt(lc，+k，ai);+I; elselistinsert(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); 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(

18、 a i+1)和第i個(gè)數(shù)據(jù)元素的存儲(chǔ)位置LOC(a I )之間滿足下列關(guān)系： LOC(a i+1)=LOC(a i)+l 線性表的第i個(gè)數(shù)據(jù)元素ai的存儲(chǔ)位置為： LOC(ai)=LOC(a1)+(I-1)*l 由于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)定義順序表類型。 # define ListSize 100 typedef int DataType; typedef struc DataType dataListSize; int length; Sq

19、list;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.dataI-1。 以下主要討論線性表的插入和刪除兩種運(yùn)算。 1、插入 線性表的插入運(yùn)算是指在表的第I(1in+1個(gè)位置上，插入一個(gè)新結(jié)點(diǎn)x，使長(zhǎng)度為n的線性表 (a1，a i-1，ai，an) 變成長(zhǎng)度為n+1的線性表 (a1，a i-1，x，ai，an) 算法2.3Void InsertList(Sqlist*L，DataType x，int I) int j; if

20、(Il.length+1) printf(“Position error”); return ERROR if(l.length=ListSize) printf(“overflow”); exit(overflow); for(j=l.length-1;j=I-1;j-) l.dataj+1=l.dataj; l.dataI-1=x; l.length+; 現(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)變量的

21、終值大于初值，結(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)，這是最壞情況，其時(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è)在表中任何位置(1in+1)上插入結(jié)點(diǎn)的機(jī)會(huì)是均等的，則 p1=p2=p3=p n+1=1/(n+1) 因此，在等概率插入的情況下， Eis(n)= (n-I

22、+1)/(n+1)=n/2 也就是說(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(1in)結(jié)點(diǎn)刪除，使長(zhǎng)度為n的線性表： (a1，a i-1，ai，a i+1，an) 變成長(zhǎng)度為n-1的線性表 (a1，a i-1，a i+1，an) Void deleteList(Sqlist*L，int I) int j; if(Il.length) printf(“Position error”); return ERRO

23、R for(j=i;jdata=ch; pnext=head; head=p; ch=getchar( ); return (head); listlink createlist(int n) int data; linklist head; listnode *p head=null; for(i=n;i0;-i) p=(listnode*)malloc(sizeof(listnode); scanf(%d，&pdata); pnext=head; head=p; return(head); 2、尾插法建表 頭插法建立鏈表雖然算法簡(jiǎn)單，但生成的鏈表中結(jié)點(diǎn)的次序和輸入的順序相反。若希望二者次序

24、一致，可采用尾插法建表。該方法是將新結(jié)點(diǎn)插入到當(dāng)前鏈表的表尾上，為此必須增加一個(gè)尾指針r，使其始終指向當(dāng)前鏈表的尾結(jié)點(diǎn)。例： linklist creater( ) char ch; linklist head; listnode *p，*r; /(， *head;) head=NULL;r=NULL; while(ch=getchar( )!=n) p=(listnode *)malloc(sizeof(listnode); pdata=ch; if(head=NULL) head=p; else rnext=p; r=p; if (r!=NULL) rnext=NULL; return(h

25、ead); 說(shuō)明：第一個(gè)生成的結(jié)點(diǎn)是開(kāi)始結(jié)點(diǎn)，將開(kāi)始結(jié)點(diǎn)插入到空表中，是在當(dāng)前鏈表的第一個(gè)位置上插入，該位置上的插入操作和鏈表中其它位置上的插入操作處理是不一樣的，原因是開(kāi)始結(jié)點(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)，并稱

26、它為頭結(jié)點(diǎn)，那么會(huì)帶來(lái)以下兩個(gè)優(yōu)點(diǎn)： a、由于開(kāi)始結(jié)點(diǎn)的位置被存放在頭結(jié)點(diǎn)的指針域中，所以在鏈表的第一個(gè)位置上的操作就 和在表的其它位置上的操作一致，無(wú)需進(jìn)行特殊處理；b、無(wú)論鏈表是否為空，其頭指針是指向頭結(jié)點(diǎn) 在的非空指針（空表中頭結(jié)點(diǎn)的指針域?yàn)榭眨虼丝毡砗头强毡淼奶幚硪簿徒y(tǒng)一了。 其算法如下：linklist createlistr1( ) char ch; linklist head=(linklist)malloc(sizeof(listnode); listnode *p，*r r=head; while(ch=getchar( )!=n p=(listnode*)malloc(

27、sizeof(listnode); pdata=ch; pnext=p; r=p; rnext=NULL; return(head); 上述算法里動(dòng)態(tài)申請(qǐng)新結(jié)點(diǎn)空間時(shí)未加錯(cuò)誤處理，可作下列處理： p=(listnode*)malloc(sizeof(listnode) if(p=NULL) error(No space for node can be obtained); return ERROR; 以上算法的時(shí)間復(fù)雜度均為O(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)往下

28、搜索，直到搜索到第i個(gè)結(jié)點(diǎn)為止。因此，鏈表不是隨機(jī)存取結(jié)構(gòu)。 設(shè)單鏈表的長(zhǎng)度為n，要查找表中第i個(gè)結(jié)點(diǎn)，僅當(dāng)1in時(shí)，i的值是合法的。但有時(shí)需要找頭結(jié)點(diǎn)的位置，故我們將頭結(jié)點(diǎn)看做是第0 個(gè)結(jié)點(diǎn)，其算法如下：Listnode * getnode(linklist head ， int i) int j; listnode * p; p=head;j=0; while(pnext & jnext; j+; if (i=j) return p; else return NULL; 2、按值查找 按值查找是在鏈表中，查找是否有結(jié)點(diǎn)值等于給定值key的結(jié)點(diǎn)，若有的話，則返回首次找到的其值為key的結(jié)點(diǎn)的

29、存儲(chǔ)位置；否則返回NULL。查找過(guò)程從開(kāi)始結(jié)點(diǎn)出發(fā)，順著鏈表逐個(gè)將結(jié)點(diǎn)的值和給定值key作比較。其算法如下：Listnode * locatenode(linklist head，int key) listnode * p=headnext; while( p & pdata!=key) p=pnext; return p; 該算法的執(zhí)行時(shí)間亦與輸入實(shí)例中的的取值key有關(guān)，其平均時(shí)間復(fù)雜度的分析類似于按序號(hào)查找，也為O(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)閤的新

30、結(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ò)程如：具體算法如下： void insertnode(linklist head，datetype x，int i) listnode * p，*q; p=getnode(head，i-1); if(p=NULL) error(position error); q=(listnode *)malloc(sizeof(listnode); qdata=x; qnext=pnext; pnext=q; 設(shè)鏈表的長(zhǎng)度為n，合法的插入位置是1in+1。注意當(dāng)i=1時(shí)，ge

31、tnode找到的是頭結(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)a a i-1的指針域next中，所以我們必須首先找到 a i-1的存儲(chǔ)位置p。然后令pnext指向ai的直接后繼結(jié)點(diǎn)，即把a(bǔ)i從鏈上摘下。最后釋放結(jié)點(diǎn)ai的空間，將其歸還給“存儲(chǔ)池”。此過(guò)程為：具體算法如下： void deletelist(linklist head， int i)

32、listnode * p， *r; p=getnode(head，i-1); if(p= =NULL | pnext= =NULL) return ERROR; r=pnext; pnext=rnext; free( r ) ; 設(shè)單鏈表的長(zhǎng)度為n，則刪去第i個(gè)結(jié)點(diǎn)僅當(dāng)1in時(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) （即pnext!=NULL）時(shí)，才能確定被刪結(jié)點(diǎn)存在。 顯然此算法的時(shí)間復(fù)雜度也是O(n)。 從上面的討論可以看出，鏈表上實(shí)

33、現(xiàn)插入和刪除運(yùn)算，無(wú)須移動(dòng)結(jié)點(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)表示。如下圖所示： a1 an .head 非空表 空表 在用頭指針表示的單鏈表中，找開(kāi)始結(jié)點(diǎn)a1的時(shí)間是O(1)，然而要找到終端結(jié)點(diǎn)an，則需從頭指針開(kāi)始遍歷整個(gè)鏈表，其時(shí)間是O(n) 在很

34、多實(shí)際問(wèn)題中，表的操作常常是在表的首尾位置上進(jìn)行，此時(shí)頭指針表示的單循環(huán)鏈表就顯得不夠方便.如果改用尾指針rear來(lái)表示單循環(huán)鏈表，則查找開(kāi)始結(jié)點(diǎn)a1和終端結(jié)點(diǎn)an都很方便，它們的存儲(chǔ)位置分別是(rearnext) next和rear，顯然，查找時(shí)間都是O(1)。因此，實(shí)際中多采用尾指針表示單循環(huán)鏈表。 由于循環(huán)鏈表中沒(méi)有NULL指針，故涉及遍歷操作時(shí)，其終止條件就不再像非循環(huán)鏈表那樣判斷p或pnext是否為空，而是判斷它們是否等于某一指定指針，如頭指什或尾指針等。例、在鏈表上實(shí)現(xiàn)將兩個(gè)線性表(a1，a2，a3，an)和(b1，b2，b3，bn)鏈接成一個(gè)線性表的運(yùn)算。 linklist co

35、nnect(linklist heada，linklist headb) linklist p=headanext; headanext=(headbnext)next free(headbnext); headbnext=p; return(headb); 2.3.3雙鏈表 雙向鏈表(Double linked list):在單鏈表的每個(gè)結(jié)點(diǎn)里再增加一個(gè)指向其直接前趨的指針域prior。這樣就形成的鏈表中有兩個(gè)方向不同的鏈，故稱為雙向鏈表。形式描述為： typedef struct dlistnode datatype data; struc dlistnode *prior，*next;

36、dlistnode; typedef dlistnode * dlinklist; dlinklist head; 和單鏈表類似，雙鏈表一般也是由頭指針唯一確定的，增加頭指針也能使雙鏈表上的某些運(yùn)算變得方便，將頭結(jié)點(diǎn)和尾結(jié)點(diǎn)鏈接起來(lái)也能構(gòu)成循環(huán)鏈表，并稱之為雙向鏈表。 設(shè)指針p指向某一結(jié)點(diǎn)，則雙向鏈表結(jié)構(gòu)的對(duì)稱性可用下式描述： (pprior)next=p=(pnext)prior 即結(jié)點(diǎn)*p的存儲(chǔ)位置既存放在其前趨結(jié)點(diǎn)*(pprior)的直接后繼指針域中，也存放 在它的后繼結(jié)點(diǎn)*(pnext)的直接前趨指針域中。雙向鏈表的前插操作算法如下： void dinsertbefor(dlistno

37、de *p，datatype x) dlistnode *q=malloc(sizeof(dlistnode); qdata=x; qprior=pprior; qnext=p; ppriornext=q; pprior=q; void ddeletenode(dlistnode *p) ppriornext=pnext; pnextprior=pprior; free(p); 注意：與單鏈表的插入和刪除操作不同的是，在雙鏈表中插入和刪除必須同時(shí)修改兩個(gè)方向上的指針。上述兩個(gè)算是法的時(shí)間復(fù)雜度均為O(1)。 第三章 棧和隊(duì)列3.1 棧 3.1.1 抽象數(shù)據(jù)類型棧的定義 3.1.2 棧的表示和實(shí)

38、現(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á)式求值 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）。3.1.2 順序棧 由

39、于棧是運(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)闂５孜恢檬枪潭ú蛔兊?，所以可以將棧底位置設(shè)置在數(shù)組的兩端的任何一個(gè)端點(diǎn)；棧頂位置是隨著進(jìn)棧和退棧操作而變化的，故需用一個(gè)整型變量top例、一疊書(shū)或一疊盤(pán)子。 棧的抽象數(shù)據(jù)類型的定義如下：P44 a n a n-1 a2 a1棧頂 棧底top7 6 5 4 3 2 1 -1來(lái)指示當(dāng)前棧頂?shù)奈恢?，通常稱top為棧頂指針。因此，順序棧的類型定義只需將順序表的類型定義中的長(zhǎng)度屬性改為top即可。順序棧的類型定義如下： # define StackSize 100

40、 typedef char datatype; typedef struct datatype datastacksize; int top; seqstack; 設(shè)S是SeqStack類型的指針變量。若棧底位置在向量的低端，即sdata0是棧底元素，那么棧頂指針stop是正向增加的，即進(jìn)棧時(shí)需將stop加1，退棧時(shí)需將stop 減1。因此，stoptop =stacksize-1表示棧滿。當(dāng)棧滿時(shí)再做進(jìn)棧運(yùn)算必定產(chǎn)生空間溢出，簡(jiǎn)稱“上溢”;當(dāng)?？諘r(shí)再做退棧運(yùn)算也將產(chǎn)生溢出，簡(jiǎn)稱“下溢”。上溢是一種出錯(cuò)狀態(tài)，應(yīng)該設(shè)法避免之；下溢則可能是正?，F(xiàn)象，因?yàn)闂Ｔ诔绦蛑惺褂脮r(shí)，其初態(tài)或終態(tài)都是空棧，所以

41、下溢常常用來(lái)作為程序控制轉(zhuǎn)移的條件。3、判斷棧滿 int stackfull(seqstack *s) return(stop=stacksize-1); 4、進(jìn)棧 void push(seqstack *s，datatype x) if (stackfull(s) error(“stack overflow”); sdata+stop=x; 1、置空棧 void initstack(seqstack *s) stop=-1; 2、判斷?？?int stackempty(seqstack *s) return(stop=-1); 5、退棧 datatype pop(seqstack *s) i

42、f(stackempty(s) error(“stack underflow”); x=sdatatop; stop-; return(x) /return(sdatastop-); 6、取棧頂元素 Datatype stacktop(seqstack *s) if(stackempty(s) error(“stack is enpty”); return sdatastop; 3.1.3 鏈棧 棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)稱為鏈棧，它是運(yùn)算是受限的單鏈表，克插入和刪除操作僅限制在表頭位置上進(jìn)行.由于只能在鏈表頭部進(jìn)行操作，故鏈表沒(méi)有必要像單鏈表那樣附加頭結(jié)點(diǎn)。棧頂指針就是鏈表的頭指針。 鏈棧的類型說(shuō)明如

43、下： typedef struct stacknode datatype data struct stacknode *next stacknode; Void initstack(seqstack *p) ptop=null; int stackempty(linkstack *p) return ptop=null; Void push(linkstack *p,datatype x) stacknode *q q=(stacknode*)malloc(sizeof(stacknode); qdata=x; qnext=ptop; ptop=p; Datatype pop(linkstac

44、k *p) datatype x; stacknode *q=ptop; if(stackempty(p) error(“stack underflow.”); x=qdata; ptop=qnext; free(q); return x; datatype stack top(linkstack *p) if(stackempty(p) error(“stack is empty.”); return ptopdata; 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ī)

45、實(shí)現(xiàn)計(jì)算的基本問(wèn)題,其解決方法很多,其中一個(gè)簡(jiǎn)單算法基于下列原理: N=(n div d)*d+n mod d ( 其中:div為整除運(yùn)算,mod為求余運(yùn)算) 例如 (1348)10=(2504)8，其運(yùn)算過(guò)程如下： n n div 8 n mod 8 1348 168 4 168 21 0 21 2 5 2 0 2 void conversion( ) initstack(s); scanf (“%”,n); while(n) push(s,n%8); n=n/8; while(! Stackempty(s) pop(s,e); printf(“%d”,e); 3.2.2 括號(hào)匹配的檢驗(yàn) 假

46、設(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í)更正。 行編輯程序算法如下: void lineedit( ) 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);

47、ch=getchar( ); clearstack(s); if(ch!=eof) ch=gethar( ); destroystack(s); 3.2.4 迷宮求解 入口出口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)先出(First In First Out)的線性表，簡(jiǎn)稱FIFO表。當(dāng)隊(duì)列中沒(méi)有元素時(shí)稱為空隊(duì)列。在空隊(duì)列中依次加入元素

48、a1,a2,an之后，a1是隊(duì)頭元素，an是隊(duì)尾元素。顯然退出隊(duì)列的次序也只能是a1,a2,an ，也就是說(shuō)隊(duì)列的修改是依先進(jìn)先出的原則進(jìn)行的。下圖是隊(duì)列的示意圖： a1a2an出隊(duì)入隊(duì)隊(duì)頭隊(duì)尾隊(duì)列的抽象數(shù)據(jù)定義見(jiàn)書(shū)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ì)列中的元素。由于隊(duì)列的隊(duì)頭和隊(duì)尾的位置是變化的，因而要設(shè)兩個(gè)指針和分別指示隊(duì)頭和隊(duì)尾元素在隊(duì)列中的位置，它們的初始值地隊(duì)列初始化時(shí)均應(yīng)置為。入隊(duì)時(shí)將新元素插入所指的位置，然后將加。出隊(duì)時(shí)，刪去所指的元素，然后將加并返回

49、被刪元素。由此可見(jiàn)，當(dāng)頭尾指針相等時(shí)隊(duì)列為空。在非空隊(duì)列里，頭指針始終指向隊(duì)頭元素，而尾指針始終指向隊(duì)尾元素的下一位置。 0 1 2 3FrontrearabcFront rear (a)隊(duì)列初始為空（b）A,B,C入隊(duì) b c front rear front rear （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)象稱為假上

50、溢。為充分利用向量空間?？朔鲜黾偕弦绗F(xiàn)象的方法是將向量空間想象為一個(gè)首尾相接的圓環(huán)，并稱這種向量為循環(huán)向量，存儲(chǔ)在其中的隊(duì)列稱為循環(huán)隊(duì)列（Circular Queue)。在循環(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; else i+; 利用模運(yùn)算可簡(jiǎn)化為： i=(i+1)%QueueSize 顯然，因?yàn)檠h(huán)隊(duì)列元素的空間可以被利用，除非向量空間真的被隊(duì)列元素全部占用，否則不會(huì)上溢。因此，除一些簡(jiǎn)單的應(yīng)用

51、外，真正實(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所指的單元始終為空）；其三是使用一個(gè)計(jì)數(shù)器記錄隊(duì)列中元素的總數(shù)（實(shí)際上是隊(duì)列長(zhǎng)度）。下面我們用第三種方法實(shí)現(xiàn)循環(huán)隊(duì)列上的六種基本操作，為此先給出循環(huán)隊(duì)列的類型定義。 #define QueueSize 100

52、typedef char DataType; typedef Struct int front; int rear; int count; datatype dataqueuesize cirqueue;（1）置空隊(duì) void initqueue(cirqueue *q) qfront=qrear=0; qcount=0; （2）判斷隊(duì)空 int queueempty(cirqueue *q) return qcount=0; （3）判斷隊(duì)滿 int queuefull(cirqueue *q) return qcount=queuesize; （4）入隊(duì) void enqueue(cirqu

53、eue *q,datatype x) if(queuefull(q) error(“queue overflow”); qcount+; qdataqrear=x; qrear=(qrear+1)%queuesize; （5）出隊(duì) datatype dequeue(cirqueue *q) datatype temp; if(queueempty(q) error(“queue underflow”); temp=qdataqfront; qcount-; qfront=(qfront+1)%queuesize; return temp; （6）取頭指針 datatype queuefront

54、(cirqueue *q) if(queueempty(q) error(“queue is empty.”); return qdataqfront; 3.4.3 鏈隊(duì)列 隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)簡(jiǎn)稱為鏈隊(duì)列，它是限制僅在表頭刪除和表尾插入的單鏈表。顯然僅有單鏈表的頭指針不便于在表尾做插入操作，為此再增加一個(gè)尾指針，指向鏈表的最后一個(gè)結(jié)點(diǎn)。于是，一個(gè)鏈隊(duì)列由一個(gè)頭指針唯一確定。和順序隊(duì)列類似，我們也是將這兩個(gè)指針?lè)庋b在一起，將鏈隊(duì)列的類型LinkQueue定義為一個(gè)結(jié)構(gòu)類型： typedef struct queuenode datatype data; struct queuenode *nex

55、t; queuenode; typedef struct queuenode *front; queuenode *rear; linkqueue;下面給出鏈隊(duì)列上實(shí)現(xiàn)的基本運(yùn)算： void initqueue(linkqueue *q) qfront=qrear=null; int queueempty(linkqueue *q) return qfront=null &qrear=null; void enqueue(linkqueue *q,datatype x) queuenode *p p=(queuenode * )malloc(sizeof(queuenode); pdata=x

56、; pnext=null; if(queueempty(q) qfront=qrear=p; else qrearnext=p; qrear=p; Datatype dequeue(linkqueue *q) datatype x; queuenode *p if(queueempty(q) error(“queue underflow”); p=qfront; x=pdata; qfront=pnext; if(qrear=p) qrear=null; free(p); return x; datatype queuefront(linkqueue *q) if(queueempty(q)

57、error(“queue is empty.”); return qfrontdata; 注意：在出隊(duì)算法中，一般只需修改隊(duì)頭指針。但當(dāng)原隊(duì)中只有一個(gè)結(jié)點(diǎn)時(shí)，該結(jié)點(diǎn)既是隊(duì)頭也是隊(duì)尾，故刪去此結(jié)點(diǎn)時(shí)亦需修改尾指針，且刪去此結(jié)點(diǎn)后隊(duì)列變空。 習(xí)題1、設(shè)將整數(shù)以萬(wàn)計(jì)、2、3、4依次進(jìn)棧，但只要出棧時(shí)棧非空，則可將出棧操作按任何次序夾入其中，請(qǐng)回答下有問(wèn)題：（1）若入棧次序?yàn)閜ush(1)，pop()，push(2，push(3)，pop()，pop( )，push(4)，pop( )，則出棧的數(shù)字序列為什么？（2）能否得到出棧序列車(chē)員423和平共處五項(xiàng)原則432？并說(shuō)明為什么不能得到或如何得到。（3

58、）請(qǐng)分析1、2、3、4的24種排列中，哪些序列可以通過(guò)相應(yīng)的入出棧得到。2、鏈棧中為何不設(shè)頭指針？3、循環(huán)隊(duì)列的優(yōu)點(diǎn)是什么？如何判斷它的空和滿？4、設(shè)長(zhǎng)度為n的鏈隊(duì)列用單循環(huán)鏈表表示，若只設(shè)頭指針，則怎樣進(jìn)行入隊(duì)和出隊(duì)操作；若只設(shè)尾指針呢？5、利用棧的基本操作，寫(xiě)一個(gè)返回棧s中結(jié)點(diǎn)個(gè)數(shù)的算法int stacksize(seqstack s)，并說(shuō)明s為何不用作為指針參數(shù)？6、利用棧的基本操作，寫(xiě)一個(gè)將棧中所有結(jié)點(diǎn)均刪除算法，并說(shuō)明S為何要作為指針參數(shù)？7、用第二種方法，即少用一個(gè)元素空間的方法來(lái)區(qū)別循環(huán)隊(duì)列的隊(duì)空和隊(duì)滿，試設(shè)計(jì)置空隊(duì)、判隊(duì)空、判隊(duì)滿、出隊(duì)、入隊(duì)及取隊(duì)頭元素等六個(gè)基本操作。8、假

59、設(shè)循環(huán)隊(duì)列只設(shè)rear和quelen來(lái)分別指示隊(duì)尾元素的位置和隊(duì)中元素的個(gè)數(shù)，試給出判斷此循環(huán)隊(duì)列的隊(duì)滿條件，并寫(xiě)出相應(yīng)的入隊(duì)和出隊(duì)算法，要求出隊(duì)時(shí)需返回隊(duì)頭指針。9、指出下列程序段的功能是什么？ (1) void demo1(seqstack *s) int I;arr64;n=0; while (!stackempty(s) arrn+=pos(s); for(I=0;n;I+) push(s,arrI); (2) void demo2(seqstack *s,int m) seqstack t; int i; initstack(t);while(! Stackempty(s) if(I

60、=pop(s)!=m) push(t,I);While(! Stackempty(t) i=pop(t); push(s,I); 第四章 串4.1 串類型的定義4.2 串的表示和實(shí)現(xiàn) 4.2.1 定長(zhǎng)順序存儲(chǔ)表示 4.2.2 堆分配存儲(chǔ)表示 4.2.3 串的塊鏈存儲(chǔ)表示 4.1 串類型的定義一、串和基本概念 串(String)是零個(gè)或多個(gè)字符組成的有限序列。一般記作S=“a1a2a3an”，其中S 是串名，雙引號(hào)括起來(lái)的字符序列是串值；ai(1in)可以是字母、數(shù)字或其它字符；串中所包含的字符個(gè)數(shù)稱為該串的長(zhǎng)度。長(zhǎng)度為零的串稱為空串(Empty String)，它不包含任何字符。 通常將僅由一