清華大學(xué)數(shù)據(jù)構(gòu)講義

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

2、據(jù)結(jié)構(gòu)這門課所要研究的問題。l 1.1什么是數(shù)據(jù)結(jié)構(gòu)l 眾所周知，計算機(jī)的程序是對信息進(jìn)行加工處理。在大多數(shù)情況下，這些信息并不是沒有組織，信息（數(shù)據(jù)）之間往往具有重要的結(jié)構(gòu)關(guān)系，這就是數(shù)據(jù)結(jié)構(gòu)的內(nèi)容。那么，什么是數(shù)據(jù)結(jié)構(gòu)呢？先看以下幾個例子。l 例1、電話號碼查詢系統(tǒng)l 設(shè)有一個電話號碼薄，它記錄了n個人的名字和其相應(yīng)的電話號碼，假定按如下形式安排：l (a1，b1)(a2，b2)(an，bn)l其中ai，bi(i=1，2n) 分別表示某人的名字和對應(yīng)的電話號碼要求設(shè)計一個算法，當(dāng)給定任何一個人的名字時，該算法能夠打印出此人的電話號碼，如果該電話簿中根本就沒有這個人，則該算法也能夠報告沒有這

3、個人的標(biāo)志。l 算法的設(shè)計，依賴于計算機(jī)如何存儲人的名字和對應(yīng)的電話號碼，或者說依賴于名字和其電話號碼的結(jié)構(gòu)。l 數(shù)據(jù)的結(jié)構(gòu)，直接影響算法的選擇和效率。l 上述的問題是一種數(shù)據(jù)結(jié)構(gòu)問題。可將名字和對應(yīng)的電話號碼設(shè)計成：二維數(shù)組、表結(jié)構(gòu)、向量。 假定名字和其電話號碼邏輯上已安排成n元向量的形式，它的每個元素是一個數(shù)對(ai，bi)， 1in 數(shù)據(jù)結(jié)構(gòu)還要提供每種結(jié)構(gòu)類型所定義的各種運(yùn)算的算法。例2、圖書館的書目檢索系統(tǒng)自動化問題例3、教師資料檔案管理系統(tǒng)例4、多叉路口交通燈的管理問題 p3 通過以上幾例可以直接地認(rèn)為：數(shù)據(jù)結(jié)構(gòu)就是研究數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)以及它們之間相互關(guān)系，并對這種結(jié)構(gòu)定義

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

5、 數(shù)據(jù)之間的相互關(guān)系稱為邏輯結(jié)構(gòu)。通常分為四類基本結(jié)構(gòu)：l一、集合 結(jié)構(gòu)中的數(shù)據(jù)元素除了同屬于一種類型外，別無其它關(guān)系。l二、線性結(jié)構(gòu) 結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一對一的關(guān)系。l三、樹型結(jié)構(gòu) 結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一對多的關(guān)系。l四、圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu) 結(jié)構(gòu)中的數(shù)據(jù)元素之間存在多對多的關(guān)系。l 數(shù)據(jù)結(jié)構(gòu)的形式定義為：數(shù)據(jù)結(jié)構(gòu)是一個二元組： data-structure=(d，s)其中：d是數(shù)據(jù)元素的有限集，s是d上關(guān)系的有限集。例 復(fù)數(shù)的數(shù)據(jù)結(jié)構(gòu)定義如下： complex=(c，r)其中：c是含兩個實數(shù)的集合c1，c2，分別表示復(fù)數(shù)的實部和虛部。r=p，p是定義在集合上的一種關(guān)系c1，c2。數(shù)

6、據(jù)結(jié)構(gòu)在計算機(jī)中的表示稱為數(shù)據(jù)的物理結(jié)構(gòu)，又稱為存儲結(jié)構(gòu)。l 數(shù)據(jù)對象可以是有限的，也可以是無限的。l數(shù)據(jù)結(jié)構(gòu)不同于數(shù)據(jù)類型，也不同于數(shù)據(jù)對象，它不僅要描述數(shù)據(jù)類型的數(shù)據(jù)對象，而且要描述數(shù)據(jù)對象各元素之間的相互關(guān)系。l抽象數(shù)據(jù)類型：一個數(shù)學(xué)模型以及定義在該模型上的一組操作。l抽象數(shù)據(jù)類型實際上就是對該數(shù)據(jù)結(jié)構(gòu)的定義。因為它定義了一個數(shù)據(jù)的邏輯結(jié)構(gòu)以及在此結(jié)構(gòu)上的一組算法。l用三元組描述如下：l（，）l數(shù)據(jù)結(jié)構(gòu)在計算機(jī)中有兩種不同的表示方法：l 順序表示和非順序表示l由此得出兩種不同的存儲結(jié)構(gòu)：順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)l順序存儲結(jié)構(gòu):用數(shù)據(jù)元素在存儲器中的相對位置來表示數(shù)據(jù)元素之間的邏輯關(guān)系。

7、l鏈?zhǔn)酱鎯Y(jié)構(gòu)：在每一個數(shù)據(jù)元素中增加一個存放地址的指針（ ），用此指針來表示數(shù)據(jù)元素之間的邏輯關(guān)系。l數(shù)據(jù)類型：在一種程序設(shè)計語言中，變量所具有的數(shù)據(jù)種類。l例1、 在fortran語言中，變量的數(shù)據(jù)類型有整型、實型、和復(fù)數(shù)型 l例2、在c語言中l(wèi)數(shù)據(jù)類型：基本類型和構(gòu)造類型l基本類型：整型、浮點型、字符型l構(gòu)造類型：數(shù)組、結(jié)構(gòu)、聯(lián)合、指針、枚舉型、自定義l數(shù)據(jù)對象：某種數(shù)據(jù)類型元素的集合。l例3、整數(shù)的數(shù)據(jù)對象是-3，-2，-1，0，1，2，3，l英文字符類型的數(shù)據(jù)對象是a，b，c，d，e，f，l 1.3 抽象數(shù)據(jù)類型的表示和實現(xiàn)lp11l 1.4 算法和算法分析l算法：是對特定問題求解步

8、驟的一種描述l 算法是指令的有限序列，其中每一條指令表示一個或多個操作。l 算法具有以下五個特性：l（1）有窮性 一個算法必須總是在執(zhí)行有窮步之后結(jié)束，且每一步都在有窮時間內(nèi)完成。l（2）確定性 算法中每一條指令必須有確切的含義。不存在二義性。且算法只有一個入口和一個出口。l（3）可行性 一個算法是可行的。即算法描述的操作都是可以通過已經(jīng)實現(xiàn)的基本運(yùn)算執(zhí)行有限次來實現(xiàn)的。l4）輸入 一個算法有零個或多個輸入，這些輸入取自于某個特定的對象集合。l5）輸出 一個算法有一個或多個輸出，這些輸出是同輸入有著某些特定關(guān)系的量。l1.4.2 算法設(shè)計的要求l評價一個好的算法有以下幾個標(biāo)準(zhǔn):l(1) 正確性

9、(correctness ) 算法應(yīng)滿足具體問題的需求。l(2)可讀性(readability) 算法應(yīng)該好讀。以有利于閱讀者對程序的理解。 (3)健狀性(robustness) 算法應(yīng)具有容錯處理。當(dāng)輸入非法數(shù)據(jù)時，算法應(yīng)對其作出反應(yīng)，而不是產(chǎn)年莫名其妙的輸出結(jié)果。l(4)效率與存儲量需求 效率指的是算法執(zhí)行的時間；存儲量需求指算法執(zhí)行過程中所需要的最大存儲空間。一般，這兩者與問題的規(guī)模有關(guān)。l1.4.3 算法效率的度量l 對一個算法要作出全面的分析可分成兩用人才個階段進(jìn)行，即事先分析和事后測試l事先分析 求出該算法的一個時間界限函數(shù)l事后測試 收集此算法的執(zhí)行時間和實際占用空間的統(tǒng)計資料。

10、l定義：如果存在兩個正常數(shù)c和n0，對于所有的nn0，有f(n) cg(n) l則記作 f(n)=o(g(n)一般情況下，算法中基本操作重復(fù)執(zhí)行的次數(shù)是問題規(guī)模n的某個函數(shù)，算法的時間量度記作 t(n)=o(f(n)稱作算法的漸近時間復(fù)雜度。例、for(i=1，i=n;+i) for(j=1;j=n;+j) cij=0; for(k=1;k=n;+k) cij+=aik*bkj; l由于是一個三重循環(huán)，每個循環(huán)從1到n，則總次數(shù)為: nnn=n3l時間復(fù)雜度為t(n)=o(n3)l頻度：是指該語句重復(fù)執(zhí)行的次數(shù)l例 +x;s=0;l將x自增看成是基本操作，則語句頻度為，即時間復(fù)雜度為(1)l如

11、果將s=0也看成是基本操作，則語句頻度為，其時間復(fù)雜度仍為(1)，即常量階。l例、for(i=1;i=n;+i)l +x;s+=x;l 語句頻度為：2n其時間復(fù)雜度為：o(n)l 即時間復(fù)雜度為線性階。l例、for(i=1;i=n;+i)lfor(j=1;j=n;+j)l +x;s+=x;l 語句頻度為：2n2l其時間復(fù)雜度為：o(n2)l 即時間復(fù)雜度為平方階。l定理：若a(n)=a m n m +a m-1 n m-1 +a1n+a0是一個m次多項式，則a(n)=o(n m)證略。例for(i=2;i=n;+i) for(j=2;j=i-1;+j) +x;ai，j=x;l語句頻度為：l 1

12、+2+3+n-2=(1+n-2) (n-2)/2l =(n-1)(n-2)/2l =n2-3n+2l 時間復(fù)雜度為o(n2)l 即此算法的時間復(fù)雜度為平方階.l 一個算法時間為o(1)的算法，它的基本運(yùn)算執(zhí)行的次數(shù)是固定的。因此，總的時間由一個常數(shù)（即零次多項式）來限界。而一個時間為o(n2)的算法則由一個二次多項式來限界。l l以下六種計算算法時間的多項式是最常用的。其關(guān)系為：l o(1)o(logn)o(n)o(nlogn)l o(n2)o(n3)l指數(shù)時間的關(guān)系為：l o(2n)o(n!)1 & change;-i)l l change=false;l for(j=0;jaj+1

13、) l aj aj+1;l change=turel l 最好情況：0次l l l最壞情況：1+2+3+n-1l =n(n-1)/2l 平均時間復(fù)雜度為:o(n2)l1.4.4算法的存儲空間需求l空間復(fù)雜度:算法所需存儲空間的度量，記作:l s(n)=o(f(n) l其中n為問題的規(guī)模(或大小) 第二章 線性表l2.1 線性表的類型定義l2.2 線性表的順序表示和實現(xiàn)l2.3 線性表的鏈?zhǔn)奖硎竞蛯崿F(xiàn)l 2.3.1 線性鏈表 2.3.2 循環(huán)鏈表 2.3.3 雙向鏈表 2.4 一元多項式的表示及相加l2.1 線性表的邏輯結(jié)構(gòu)l線性表(linear list) ：由n(n)個數(shù)據(jù)元素(結(jié)點)a1，

14、a2， an組成的有限序列。其中數(shù)據(jù)元素的個數(shù)n定義為表的長度。當(dāng)n=0時稱為空表，常常將非空的線性表(n0)記作：l (a1，a2，an) l這里的數(shù)據(jù)元素ai(1in)只是一個抽象的符號，其具體含義在不同的情況下可以不同。l例1、26個英文字母組成的字母表l （a，b，c、z）l例2、某校從1978年到1983年各種型號的計算機(jī)擁有量的變化情況。l （6，17，28，50，92，188）例3、學(xué)生健康情況登記表如下：姓 名學(xué) 號性 別年齡 健康情況王小林790631 男 18 健康陳 紅790632 女 20 一般劉建平790633 男 21 健康張立立790634 男 17 神經(jīng)衰弱 .

15、 . .l例4、一副撲克的點數(shù)l （2，3，4，j，q，k，a） 從以上例子可看出線性表的邏輯特征是：在非空的線性表，有且僅有一個開始結(jié)點a1，它沒有直接前趨，而僅有一個直接后繼a2；有且僅有一個終端結(jié)點an，它沒有直接后繼，而僅有一個直接前趨a n-1；其余的內(nèi)部結(jié)點ai(2in-1)都有且僅有一個直接前趨a i-1和一個直接后繼a i+1。 線性表是一種典型的線性結(jié)構(gòu)。l數(shù)據(jù)的運(yùn)算是定義在邏輯結(jié)構(gòu)上的，而運(yùn)算的具體實現(xiàn)則是在存儲結(jié)構(gòu)上進(jìn)行的。l抽象數(shù)據(jù)類型的定義為：p19 算法2.1l例2-1 利用兩個線性表la和lb分別表示兩個集合a和b，現(xiàn)要求一個新的集合a=ab。 void unio

16、n(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)listinsert(la，+la-en，e) l l 算法2.2l例2-2 巳知線性表la和線性表lb中的數(shù)據(jù)元素按值非遞減有序排列，現(xiàn)要求將la和lb歸并為一個新的線性表lc，且lc中的元素仍按值非遞減有序排列。l 此問題的算法如下： void mergelist(list la，list lb，list &lc) i

17、nitlist(lc); i=j=1;k=0; la-len=listlength(la); lb-len=listlength(lb); while(i=la-len)&(j=lb-len)l getelem(la，i，ai);getelem(lb，j，bj);l if(ai=bj)listinsert(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);listinser

18、t(lc，+k，bi); l 2.2 線性表的順序存儲結(jié)構(gòu)l2.2.1 線性表 把線性表的結(jié)點按邏輯順序依次存放在一組地址連續(xù)的存儲單元里。用這種方法存儲的線性表簡稱順序表。 假設(shè)線性表的每個元素需占用l個存儲單元，并以所占的第一個單元的存儲地址作為數(shù)據(jù)元素的存儲位置。則線性表中第i+1個數(shù)據(jù)元素的存儲位置loc( a i+1)和第i個數(shù)據(jù)元素的存儲位置loc(a i )之間滿足下列關(guān)系： loc(a i+1)=loc(a i)+l 線性表的第i個數(shù)據(jù)元素ai的存儲位置為： loc(ai)=loc(a1)+(i-1)*l l由于c語言中的一維數(shù)組也是采用順序存儲表示，故可以用數(shù)組類型來描述順序

19、表。又因為除了用數(shù)組來存儲線性表的元素之外，順序表還應(yīng)該用一個變量來表示線性表的長度屬性，所以我們用結(jié)構(gòu)類型來定義順序表類型。l # define listsize 100l typedef int datatype;l typedef strucl datatype datalistsize;l int length;l sqlist;l2.2.2 順序表上實現(xiàn)的基本操作 在順序表存儲結(jié)構(gòu)中，很容易實現(xiàn)線性表的一些操作，如線性表的構(gòu)造、第i個元素的訪問。 注意：c語言中的數(shù)組下標(biāo)從“0”開始，因此，若l是sqlist類型的順序表，則表中第i個元素是l.datai-1。 以下主要討論線性表的插

20、入和刪除兩種運(yùn)算。 1、插入 線性表的插入運(yùn)算是指在表的第i(1in+1個位置上，插入一個新結(jié)點x，使長度為n的線性表 (a1，a i-1，ai，an) 變成長度為n+1的線性表 (a1，a i-1，x，ai，an) 算法2.3lvoid insertlist(sqlist*l，datatype x，int i)l l int j;l if(il.length+1)l printf(“position error”);l return errorl l if(l.length=listsize)l printf(“overflow”);l exit(overflow);l for(j=l.le

21、ngth-1;j=i-1;j-)l l.dataj+1=l.dataj;l l.datai-1=x;l l.length+;ll 現(xiàn)在分析算法的復(fù)雜度。l 這里的問題規(guī)模是表的長度，設(shè)它的值為。該算法的時間主要化費(fèi)在循環(huán)的結(jié)點后移語句上，該語句的執(zhí)行次數(shù)（即移動結(jié)點的次數(shù)）是。由此可看出，所需移動結(jié)點的次數(shù)不僅依賴于表的長度，而且還與插入位置有關(guān)。l當(dāng)時，由于循環(huán)變量的終值大于初值，結(jié)點后移語句將不進(jìn)行；這是最好情況，其時間復(fù)雜度o（1）；l當(dāng)=1時，結(jié)點后移語句將循環(huán)執(zhí)行n次，需移動表中所有結(jié)點，這是最壞情況，l其時間復(fù)雜度為o（n）。l 由于插入可能在表中任何位置上進(jìn)行，因此需分析算法的平

22、均復(fù)雜度 在長度為n的線性表中第i個位置上插入一個結(jié)點，令eis(n)表示移動結(jié)點的期望值（即移動的平均次數(shù)），則在第i個位置上插入一個結(jié)點的移動次數(shù)為n-i+1。故 eis(n)= pi(n-i+1) 不失一般性，假設(shè)在表中任何位置(1in+1)上插入結(jié)點的機(jī)會是均等的，則 p1=p2=p3=p n+1=1/(n+1) 因此，在等概率插入的情況下， eis(n)= (n-i+1)/(n+1)=n/2 也就是說，在順序表上做插入運(yùn)算，平均要移動表上一半結(jié)點。當(dāng)表長 n較大時，算法的效率相當(dāng)?shù)汀ｋm然eis(n)中n的的系數(shù)較小，但就數(shù)量級而言，它仍然是線性階的。因此算法的平均時間復(fù)雜度為o(n)

23、。 2、刪除 線性表的刪除運(yùn)算是指將表的第i(1in)結(jié)點刪除，使長度為n的線性表： (a1，a i-1，ai，a i+1，an) 變成長度為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 error for(j=i;jdata=ch; pnext=head; head=p; ch=getchar( ); return (head); listlink createlist(int n) int data; link

24、list 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é)點的次序和輸入的順序相反。若希望二者次序一致，可采用尾插法建表。該方法是將新結(jié)點插入到當(dāng)前鏈表的表尾上，為此必須增加一個尾指針r，使其始終指向當(dāng)前鏈表的尾結(jié)點。例： linklist creater( ) char ch; linklist head;

25、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(head); 說明：第一個生成的結(jié)點是開始結(jié)點，將開始結(jié)點插入到空表中，是在當(dāng)前鏈表的第一個位置上插入，該位置上的插入操作和鏈表中其它位置上的插入操作處理是不一樣的，原因是開始結(jié)點的位置是存放在頭指針（指針變量）中

26、， 而其余結(jié)點的位置是在其前趨結(jié)點的指針域中。算法中的第一個if語句就是用來對第一個位置上的插入操作做特殊處理。算法中的第二個if語句的作用是為了分別處理空表和非空表兩種不同的情況，若讀入的第一個字符就是結(jié)束標(biāo)志符，則鏈表head是空表，尾指針r亦為空，結(jié)點*r不存在；否則鏈表head非空，最后一個尾結(jié)點*r是終端結(jié)點，應(yīng)將其指針域置空。 如果我們在鏈表的開始結(jié)點之前附加一個結(jié)點，并稱它為頭結(jié)點，那么會帶來以下兩個優(yōu)點： a、由于開始結(jié)點的位置被存放在頭結(jié)點的指針域中，所以在鏈表的第一個位置上的操作就 和在表的其它位置上的操作一致，無需進(jìn)行特殊處理；b、無論鏈表是否為空，其頭指針是指向頭結(jié)點

27、在的非空指針（空表中頭結(jié)點的指針域為空），因此空表和非空表的處理也就統(tǒng)一了。 其算法如下：linklist createlistr1( ) char ch; linklist head=(linklist)malloc(sizeof(listnode); listnode *p，*r r=head; while(ch=getchar( )!= n p=(listnode*)malloc(sizeof(listnode); pdata=ch; pnext=p; r=p; rnext=null; return(head); 上述算法里動態(tài)申請新結(jié)點空間時未加錯誤處理，可作下列處理： p=(list

28、node*)malloc(sizeof(listnode) if(p=null) error(no space for node can be obtained); return error; 以上算法的時間復(fù)雜度均為o(n)。二、查找運(yùn)算 1、按序號查找 在鏈表中，即使知道被訪問結(jié)點的序號i，也不能象順序表中那樣直接按序號i訪問結(jié)點，而只能從鏈表的頭指針出發(fā)，順鏈域next逐個結(jié)點往下搜索，直到搜索到第i個結(jié)點為止。因此，鏈表不是隨機(jī)存取結(jié)構(gòu)。 設(shè)單鏈表的長度為n，要查找表中第i個結(jié)點，僅當(dāng)1in時，i的值是合法的。但有時需要找頭結(jié)點的位置，故我們將頭結(jié)點看做是第0 個結(jié)點，其算法如下：li

29、stnode * 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é)點值等于給定值key的結(jié)點，若有的話，則返回首次找到的其值為key的結(jié)點的存儲位置；否則返回null。查找過程從開始結(jié)點出發(fā)，順著鏈表逐個將結(jié)點的值和給定值key作比較。其算法如下：listnode * locatenode(linklist head，int key) li

30、stnode * p=headnext; while( p & pdata!=key) p=pnext; return p; 該算法的執(zhí)行時間亦與輸入實例中的的取值key有關(guān)，其平均時間復(fù)雜度的分析類似于按序號查找，也為o(n)。三、插入運(yùn)算 插入運(yùn)算是將值為x的新結(jié)點插入到表的第i個結(jié)點的位置上，即插入到ai-1與ai之間。因此，我們必須首先找到ai-1的存儲位置p，然后生成一個數(shù)據(jù)域為x的新結(jié)點*p，并令結(jié)點*p的指針域指向新結(jié)點，新結(jié)點的指針域指向結(jié)點ai。從而實現(xiàn)三個結(jié)點ai-1，x和ai之間的邏輯關(guān)系的變化，插入過程如：具體算法如下： void insertnode(link

31、list 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è)鏈表的長度為n，合法的插入位置是1in+1。注意當(dāng)i=1時，getnode找到的是頭結(jié)點，當(dāng) i=n+1時，getnode找到的是結(jié)點an。因此，用i-1做實參調(diào)用getnode時可完成插入位置的合法性檢查。算法的時間主要耗費(fèi)在查找操作getnode上，故時

32、間復(fù)雜度亦為o(n)。四、刪除運(yùn)算 刪除運(yùn)算是將表的第i個結(jié)點刪去。因為在單鏈表中結(jié)點ai的存儲地址是在其直接前趨結(jié)點a a i-1的指針域next中，所以我們必須首先找到 a i-1的存儲位置p。然后令pnext指向ai的直接后繼結(jié)點，即把a(bǔ)i從鏈上摘下。最后釋放結(jié)點ai的空間，將其歸還給“存儲池”。此過程為：具體算法如下： void deletelist(linklist head， int i) listnode * p， *r; p=getnode(head，i-1); if(p= =null | pnext= =null) return error; r=pnext; pnext=r

33、next; free( r ) ; 設(shè)單鏈表的長度為n，則刪去第i個結(jié)點僅當(dāng)1in時是合法的。注意，當(dāng)i=n+1時，雖然被刪結(jié)點不存在，但其前趨結(jié)點卻存在，它是終端結(jié)點。因此被刪結(jié)點的直接前趨*p存在并不意味著被刪結(jié)點就一定存在，僅當(dāng)*p存在（即p!=null）且*p不是終端結(jié)點 （即pnext!=null）時，才能確定被刪結(jié)點存在。 顯然此算法的時間復(fù)雜度也是o(n)。 從上面的討論可以看出，鏈表上實現(xiàn)插入和刪除運(yùn)算，無須移動結(jié)點，僅需修改指針。2.3.2 循環(huán)鏈表 循環(huán)鏈表時一種頭尾相接的鏈表。其特點是無須增加存儲量，僅對表的鏈接方式稍作改變，即可使得表處理更加方便靈活。單循環(huán)鏈表：在單鏈

34、表中，將終端結(jié)點的指針域null改為指向表頭結(jié)點的或開始結(jié)點，就得到了單鏈形式的循環(huán)鏈表，并簡單稱為單循環(huán)鏈表。 為了使空表和非空表的處理一致，循環(huán)鏈表中也可設(shè)置一個頭結(jié)點。這樣，空循環(huán)鏈表僅有一個自成循環(huán)的頭結(jié)點表示。如下圖所示： a1 an .head 非空表 空表 在用頭指針表示的單鏈表中，找開始結(jié)點a1的時間是o(1)，然而要找到終端結(jié)點an，則需從頭指針開始遍歷整個鏈表，其時間是o(n) 在很多實際問題中，表的操作常常是在表的首尾位置上進(jìn)行，此時頭指針表示的單循環(huán)鏈表就顯得不夠方便.如果改用尾指針rear來表示單循環(huán)鏈表，則查找開始結(jié)點a1和終端結(jié)點an都很方便，它們的存儲位置分別是

35、(rearnext) next和rear，顯然，查找時間都是o(1)。因此，實際中多采用尾指針表示單循環(huán)鏈表。 由于循環(huán)鏈表中沒有null指針，故涉及遍歷操作時，其終止條件就不再像非循環(huán)鏈表那樣判斷p或pnext是否為空，而是判斷它們是否等于某一指定指針，如頭指什或尾指針等。例、在鏈表上實現(xiàn)將兩個線性表(a1，a2，a3，an)和(b1，b2，b3，bn)鏈接成一個線性表的運(yùn)算。 linklist connect(linklist heada，linklist headb) linklist p=headanext; headanext=(headbnext)next free(headbne

36、xt); headbnext=p; return(headb); 2.3.3雙鏈表 雙向鏈表(double linked list):在單鏈表的每個結(jié)點里再增加一個指向其直接前趨的指針域prior。這樣就形成的鏈表中有兩個方向不同的鏈，故稱為雙向鏈表。形式描述為： typedef struct dlistnode datatype data; struc dlistnode *prior，*next; dlistnode; typedef dlistnode * dlinklist; dlinklist head; 和單鏈表類似，雙鏈表一般也是由頭指針唯一確定的，增加頭指針也能使雙鏈表上的某些

37、運(yùn)算變得方便，將頭結(jié)點和尾結(jié)點鏈接起來也能構(gòu)成循環(huán)鏈表，并稱之為雙向鏈表。 設(shè)指針p指向某一結(jié)點，則雙向鏈表結(jié)構(gòu)的對稱性可用下式描述： (pprior)next=p=(pnext)prior 即結(jié)點*p的存儲位置既存放在其前趨結(jié)點*(pprior)的直接后繼指針域中，也存放 在它的后繼結(jié)點*(pnext)的直接前趨指針域中。雙向鏈表的前插操作算法如下： void dinsertbefor(dlistnode *p，datatype x) dlistnode *q=malloc(sizeof(dlistnode); qdata=x; qprior=pprior; qnext=p; ppriorn

38、ext=q; pprior=q; void ddeletenode(dlistnode *p) ppriornext=pnext; pnextprior=pprior; free(p); 注意：與單鏈表的插入和刪除操作不同的是，在雙鏈表中插入和刪除必須同時修改兩個方向上的指針。上述兩個算是法的時間復(fù)雜度均為o(1)。 第三章 棧和隊列3.1 棧 3.1.1 抽象數(shù)據(jù)類型棧的定義 3.1.2 棧的表示和實現(xiàn)3.2 棧的應(yīng)用舉例 3.2.1 數(shù)制轉(zhuǎn)換 3.2.2 括號匹配的檢驗 3.2.4 行編輯程序 3.2.5 迷宮求解 3.2.5 表達(dá)式求值 3.1.1 棧3.1.1 棧的定義及基本運(yùn)算 棧(

39、stack)是限制在表的一端進(jìn)行插入和刪除運(yùn)算的線性表，通常稱插入、刪除的這一端為棧頂(top)，另一端為棧底(bottom)。當(dāng)表中沒有元素時稱為空棧。 假設(shè)棧s=(a1，a2，a3，an)，則a1稱為棧底元素，an為棧頂元素。棧中元素按a1，a2，a3，an的次序進(jìn)棧，退棧的第一個元素應(yīng)為棧頂元素。換句話說，棧的修改是按后進(jìn)先出的原則進(jìn)行的。因此，棧稱為后進(jìn)先出表（lifo）。3.1.2 順序棧 由于棧是運(yùn)算受限的線性表，因此線性表的存儲結(jié)構(gòu)對棧也適應(yīng)。 棧的順序存儲結(jié)構(gòu)簡稱為順序棧，它是運(yùn)算受限的線性表。因此，可用數(shù)組來實現(xiàn)順序棧。因為棧底位置是固定不變的，所以可以將棧底位置設(shè)置在數(shù)組的

40、兩端的任何一個端點；棧頂位置是隨著進(jìn)棧和退棧操作而變化的，故需用一個整型變量top例、一疊書或一疊盤子。 棧的抽象數(shù)據(jù)類型的定義如下：p44 a n a n-1 a2 a1棧頂 棧底top7 6 5 4 3 2 1 -1來指示當(dāng)前棧頂?shù)奈恢?，通常稱top為棧頂指針。因此，順序棧的類型定義只需將順序表的類型定義中的長度屬性改為top即可。順序棧的類型定義如下： # define stacksize 100 typedef char datatype; typedef struct datatype datastacksize; int top; seqstack; 設(shè)s是seqstack類型的指

41、針變量。若棧底位置在向量的低端，即sdata0是棧底元素，那么棧頂指針stop是正向增加的，即進(jìn)棧時需將stop加1，退棧時需將stop 減1。因此，stoptop =stacksize-1表示棧滿。當(dāng)棧滿時再做進(jìn)棧運(yùn)算必定產(chǎn)生空間溢出，簡稱“上溢”;當(dāng)?？諘r再做退棧運(yùn)算也將產(chǎn)生溢出，簡稱“下溢”。上溢是一種出錯狀態(tài)，應(yīng)該設(shè)法避免之；下溢則可能是正常現(xiàn)象，因為棧在程序中使用時，其初態(tài)或終態(tài)都是空棧，所以下溢常常用來作為程序控制轉(zhuǎn)移的條件。3、判斷棧滿 int stackfull(seqstack *s) return(stop=stacksize-1); 4、進(jìn)棧 void push(seqs

42、tack *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) if(stackempty(s) error(“stack underflow”); x=sdatatop; stop-; return(x) /return(sdatastop-); 6、取棧頂

43、元素 datatype stacktop(seqstack *s) if(stackempty(s) error(“stack is enpty”); return sdatastop; 3.1.3 鏈棧 棧的鏈?zhǔn)酱鎯Y(jié)構(gòu)稱為鏈棧，它是運(yùn)算是受限的單鏈表，克插入和刪除操作僅限制在表頭位置上進(jìn)行.由于只能在鏈表頭部進(jìn)行操作，故鏈表沒有必要像單鏈表那樣附加頭結(jié)點。棧頂指針就是鏈表的頭指針。 鏈棧的類型說明如下： typedef struct stacknode datatype data struct stacknode *next stacknode; void initstack(seqsta

44、ck *p) ptop=null; int stackempty(linkstack *p) return ptop=null; lvoid push(linkstack *p,datatype x) stacknode *q q=(stacknode*)malloc(sizeof(stacknode); qdata=x; qnext=ptop; ptop=p; datatype pop(linkstack *p) datatype x; stacknode *q=ptop; if(stackempty(p) error(“stack underflow.”); x=qdata; ptop=q

45、next; 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è)計中常用的工具。以下是幾個棧應(yīng)用的例子。 3.2.1 數(shù)制轉(zhuǎn)換 十進(jìn)制n和其它進(jìn)制數(shù)的轉(zhuǎn)換是計算機(jī)實現(xiàn)計算的基本問題,其解決方法很多,其中一個簡單算法基于下列原理: n=(n div d)*d+n mod d ( 其中:div為整除運(yùn)算,mod為求余運(yùn)算) 例如 (1348)10=(250

46、4)8，其運(yùn)算過程如下： 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 括號匹配的檢驗 假設(shè)表達(dá)式中充許括號嵌套,則檢驗括號是否匹配的方法可用“期待的急迫程度”這個概念來描述。例： （）（） （）3.2.3 行編輯程序 在編輯程序中，設(shè)立一個輸入緩沖區(qū)，用于接受用戶輸入的一行字符，

47、然后逐行存入用戶數(shù)據(jù)區(qū)。允許用戶輸入錯誤，并在發(fā)現(xiàn)有誤時可以及時更正。 行編輯程序算法如下: 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); ch=getchar( ); clearstack(s); if(ch!=eof) ch=gethar( ); destroystack(s); 3.2.4 迷宮求解 入口出口3.4

48、隊列3.4.1 抽象數(shù)據(jù)類型隊列的定義 隊列(queue)也是一種運(yùn)算受限的線性表。它只允許在表的一端進(jìn)行插入，而在另一端進(jìn)行刪除。允許刪除的一端稱為隊頭(front)，允許插入的一端稱為隊尾(rear)。例如：排隊購物。操作系統(tǒng)中的作業(yè)排隊。先進(jìn)入隊列的成員總是先離開隊列。因此隊列亦稱作先進(jìn)先出(first in first out)的線性表，簡稱fifo表。當(dāng)隊列中沒有元素時稱為空隊列。在空隊列中依次加入元素a1,a2,an之后，a1是隊頭元素，an是隊尾元素。顯然退出隊列的次序也只能是a1,a2,an ，也就是說隊列的修改是依先進(jìn)先出的原則進(jìn)行的。下圖是隊列的示意圖： a1a2an出隊入

49、隊隊頭隊尾隊列的抽象數(shù)據(jù)定義見書593.4.2 循環(huán)隊列隊列的順序表示和實現(xiàn)隊列的順序存儲結(jié)構(gòu)稱為順序隊列，順序隊列實際上是運(yùn)算受限的順序表，和順序表一樣，順序隊列也是必須用一個向量空間來存放當(dāng)前隊列中的元素。由于隊列的隊頭和隊尾的位置是變化的，因而要設(shè)兩個指針和分別指示隊頭和隊尾元素在隊列中的位置，它們的初始值地隊列初始化時均應(yīng)置為。入隊時將新元素插入所指的位置，然后將加。出隊時，刪去所指的元素，然后將加并返回被刪元素。由此可見，當(dāng)頭尾指針相等時隊列為空。在非空隊列里，頭指針始終指向隊頭元素，而尾指針始終指向隊尾元素的下一位置。 0 1 2 3frontrearabcfront rear (

50、a)隊列初始為空（b）a,b,c入隊 b c front rear front rear （c) a出隊 (d) b,c出隊，隊為空和棧類似，隊列中亦有上溢和下溢現(xiàn)象。此外，順序隊列中還存在“假上溢”現(xiàn)象。因為在入隊和出隊的操作中，頭尾指針只增加不減小，致使被刪除元素的空間永遠(yuǎn)無法重新利用。因此，盡管隊列中實際的元素個數(shù)遠(yuǎn)遠(yuǎn)小于向量空間的規(guī)模，但也可能由于尾指針?biāo)瘸鱿蛄靠臻g的上界而不能做入隊操作。該現(xiàn)象稱為假上溢。為充分利用向量空間。克服上述假上溢現(xiàn)象的方法是將向量空間想象為一個首尾相接的圓環(huán)，并稱這種向量為循環(huán)向量，存儲在其中的隊列稱為循環(huán)隊列（circular queue)。在循環(huán)隊列中

51、進(jìn)行出隊、入隊操作時，頭尾指針仍要加1，朝前移動。只不過當(dāng)頭尾指針指向向量上界（queuesize-1）時，其加1操作的結(jié)果是指向向量的下界0。這種循環(huán)意義下的加1操作可以描述為： if(i+1=queuesize) i=0; else i+; 利用模運(yùn)算可簡化為： i=(i+1)%queuesize 顯然，因為循環(huán)隊列元素的空間可以被利用，除非向量空間真的被隊列元素全部占用，否則不會上溢。因此，除一些簡單的應(yīng)用外，真正實用的順序隊列是循環(huán)隊列。 如圖所示：由于入隊時尾指針向前追趕頭指針，出隊時頭指針向前追趕尾指針，故隊空和隊滿時頭尾指針均相等。因此，我們無法通過front=rear來判斷隊列

52、“空”還是“滿”。 解決此問題的方法至少有三種： 其一是另設(shè)一個布爾變量以匹別隊列的空和滿；其二是少用一個元素的空間，約定入隊前，測試尾指針在循環(huán)意義下加1后是否等于頭指針，若相等則認(rèn)為隊滿（注意：rear所指的單元始終為空）；其三是使用一個計數(shù)器記錄隊列中元素的總數(shù)（實際上是隊列長度）。下面我們用第三種方法實現(xiàn)循環(huán)隊列上的六種基本操作，為此先給出循環(huán)隊列的類型定義。l #define queuesize 100l typedef char datatype;l typedef structl int front;l int rear;l int count;l datatype dataqu

53、euesizel cirqueue;（1）置空隊 void initqueue(cirqueue *q) qfront=qrear=0; qcount=0; （2）判斷隊空 int queueempty(cirqueue *q) return qcount=0; （3）判斷隊滿 int queuefull(cirqueue *q) return qcount=queuesize; （4）入隊 void enqueue(cirqueue *q,datatype x) if(queuefull(q) error(“queue overflow”); qcount+; qdataqrear=x; q

54、rear=(qrear+1)%queuesize; （5）出隊 datatype dequeue(cirqueue *q) datatype temp; if(queueempty(q) error(“queue underflow”); temp=qdataqfront; qcount-; qfront=(qfront+1)%queuesize; return temp; （6）取頭指針 datatype queuefront(cirqueue *q) if(queueempty(q) error(“queue is empty.”); return qdataqfront; l3.4.3

55、鏈隊列l(wèi) 隊列的鏈?zhǔn)酱鎯Y(jié)構(gòu)簡稱為鏈隊列，它是限制僅在表頭刪除和表尾插入的單鏈表。顯然僅有單鏈表的頭指針不便于在表尾做插入操作，為此再增加一個尾指針，指向鏈表的最后一個結(jié)點。于是，一個鏈隊列由一個頭指針唯一確定。和順序隊列類似，我們也是將這兩個指針封裝在一起，將鏈隊列的類型linkqueue定義為一個結(jié)構(gòu)類型：l typedef struct queuenodel datatype data;l struct queuenode *next;l queuenode; typedef struct queuenode *front; queuenode *rear; linkqueue;下面給出

56、鏈隊列上實現(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; pnext=null; if(queueempty(q) qfront=qrear=p; else qrearnext=p; qrear=p;

57、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) error(“queue is empty.”); return qfrontdata; 注意：在出隊算法中，一般只需修改隊頭指針。但當(dāng)原隊中只有一

58、個結(jié)點時，該結(jié)點既是隊頭也是隊尾，故刪去此結(jié)點時亦需修改尾指針，且刪去此結(jié)點后隊列變空。 習(xí)題1、設(shè)將整數(shù)以萬計、2、3、4依次進(jìn)棧，但只要出棧時棧非空，則可將出棧操作按任何次序夾入其中，請回答下有問題：（1）若入棧次序為push(1)，pop()，push(2，push(3)，pop()，pop( )，push(4)，pop( )，則出棧的數(shù)字序列為什么？（2）能否得到出棧序列車員423和平共處五項原則432？并說明為什么不能得到或如何得到。（3）請分析1、2、3、4的24種排列中，哪些序列可以通過相應(yīng)的入出棧得到。2、鏈棧中為何不設(shè)頭指針？3、循環(huán)隊列的優(yōu)點是什么？如何判斷它的空和滿？4、

59、設(shè)長度為n的鏈隊列用單循環(huán)鏈表表示，若只設(shè)頭指針，則怎樣進(jìn)行入隊和出隊操作；若只設(shè)尾指針呢？5、利用棧的基本操作，寫一個返回棧s中結(jié)點個數(shù)的算法int stacksize(seqstack s)，并說明s為何不用作為指針參數(shù)？6、利用棧的基本操作，寫一個將棧中所有結(jié)點均刪除算法，并說明s為何要作為指針參數(shù)？7、用第二種方法，即少用一個元素空間的方法來區(qū)別循環(huán)隊列的隊空和隊滿，試設(shè)計置空隊、判隊空、判隊滿、出隊、入隊及取隊頭元素等六個基本操作。8、假設(shè)循環(huán)隊列只設(shè)rear和quelen來分別指示隊尾元素的位置和隊中元素的個數(shù)，試給出判斷此循環(huán)隊列的隊滿條件，并寫出相應(yīng)的入隊和出隊算法，要求出隊時

60、需返回隊頭指針。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=pop(s)!=m) push(t,i);while(! stackempty(t) i=pop(t); push(s,i); 第四章 串l4.1 串類型的定義l4.2 串的表示和實現(xiàn) 4.2.1 定長順序存儲表