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

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

3、也能夠報告沒有這個人的標(biāo)志。,5,算法的設(shè)計，依賴于計算機如何存儲人的名字和對應(yīng)的電話號碼，或者說依賴于名字和其電話號碼的結(jié)構(gòu)。 數(shù)據(jù)的結(jié)構(gòu)，直接影響算法的選擇和效率。 上述的問題是一種數(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)類型所定義的各種運算的算法。,6,例2、圖書館的書目檢索系統(tǒng)自動化問題 例3、教師資料檔案管理系統(tǒng) 例4、多叉路口交通燈的管理問題 P3 通過以上幾例可以直接地認為：數(shù)據(jù)結(jié)構(gòu) 就是研究數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)以及它們 之

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

5、,數(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ù)元素除了同屬于一種類型外，別無其它關(guān)系。 二、線性結(jié)構(gòu) 結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一對一的關(guān)系。 三、樹型結(jié)構(gòu) 結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一對多的關(guān)系。 四、圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu) 結(jié)構(gòu)中的數(shù)據(jù)元素之間存在多對多的關(guān)系。,9,數(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

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

7、素在存儲器中的相對位置來表示數(shù)據(jù)元素之間的邏輯關(guān)系。 鏈?zhǔn)酱鎯Y(jié)構(gòu)：在每一個數(shù)據(jù)元素中增加一個存放地址的指針（ ），用此指針來表示數(shù)據(jù)元素之間的邏輯關(guān)系。,12,數(shù)據(jù)類型：在一種程序設(shè)計語言中，變量所具有的數(shù)據(jù)種類。 例1、 在FORTRAN語言中，變量的數(shù)據(jù)類型有整型、實型、和復(fù)數(shù)型 例2、在C語言中 數(shù)據(jù)類型：基本類型和構(gòu)造類型 基本類型：整型、浮點型、字符型 構(gòu)造類型：數(shù)組、結(jié)構(gòu)、聯(lián)合、指針、枚舉型、自定義 數(shù)據(jù)對象：某種數(shù)據(jù)類型元素的集合。 例3、整數(shù)的數(shù)據(jù)對象是-3，-2，-1，0，1，2，3， 英文字符類型的數(shù)據(jù)對象是A，B，C，D，E，F(xiàn)，,13,1.3 抽象數(shù)據(jù)類型的表示和實現(xiàn)

8、 P11,14,1.4 算法和算法分析 算法：是對特定問題求解步驟的一種描述 算法是指令的有限序列，其中每一條指令表示一個或多個操作。 算法具有以下五個特性： （1）有窮性 一個算法必須總是在執(zhí)行有窮步之后結(jié)束，且每一步都在有窮時間內(nèi)完成。 （2）確定性 算法中每一條指令必須有確切的含義。不存在二義性。且算法只有一個入口和一個出口。 （3）可行性 一個算法是可行的。即算法描述的操作都是可以通過已經(jīng)實現(xiàn)的基本運算執(zhí)行有限次來實現(xiàn)的。,15,4）輸入 一個算法有零個或多個輸入，這些輸入取自于某個特定的對象集合。 5）輸出 一個算法有一個或多個輸出，這些輸出是同輸入有著某些特定關(guān)系的量。 1.4.2

9、 算法設(shè)計的要求 評價一個好的算法有以下幾個標(biāo)準(zhǔn): (1) 正確性(Correctness ) 算法應(yīng)滿足具體問題的需求。 (2)可讀性(Readability) 算法應(yīng)該好讀。以有利于閱讀者對程序的理解。 (3)健狀性(Robustness) 算法應(yīng)具有容錯處理。當(dāng)輸入非法數(shù)據(jù)時，算法應(yīng)對其作出反應(yīng)，而不是產(chǎn)年莫名其妙的輸出結(jié)果。,16,(4)效率與存儲量需求 效率指的是算法執(zhí)行的時間；存儲量需求指算法執(zhí)行過程中所需要的最大存儲空間。一般，這兩者與問題的規(guī)模有關(guān)。 1.4.3 算法效率的度量 對一個算法要作出全面的分析可分成兩用人才個階段進行，即事先分析和事后測試 事先分析 求出該算法的一個

10、時間界限函數(shù) 事后測試 收集此算法的執(zhí)行時間和實際占用空間的統(tǒng)計資料。 定義：如果存在兩個正常數(shù)c和n0，對于所有的nn0，有f(n) cg(n) 則記作 f(n)=O(g(n),17,一般情況下，算法中基本操作重復(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; ,18,由于是一個三重循環(huán)，每個循環(huán)從1到n，則總次數(shù)為: nnn=n3 時間復(fù)雜度為T(n)=O(n3) 頻度：是指該語句重復(fù)執(zhí)行的次

11、數(shù) 例 +x;s=0; 將x自增看成是基本操作，則語句頻度為，即時間復(fù)雜度為(1) 如果將s=0也看成是基本操作，則語句頻度為，其時間復(fù)雜度仍為(1)，即常量階。 例、for(I=1;I=n;+I) +x;s+=x; 語句頻度為：2n其時間復(fù)雜度為：O(n) 即時間復(fù)雜度為線性階。,19,例、for(I=1;I=n;+I) for(j=1;j=n;+j) +x;s+=x; 語句頻度為：2n2 其時間復(fù)雜度為：O(n2) 即時間復(fù)雜度為平方階。 定理：若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;

12、+I) for(j=2;j=i-1;+j) +x;ai，j=x;,20,語句頻度為： 1+2+3+n-2=(1+n-2) (n-2)/2 =(n-1)(n-2)/2 =n2-3n+2 時間復(fù)雜度為O(n2) 即此算法的時間復(fù)雜度為平方階. 一個算法時間為O(1)的算法，它的基本運算執(zhí)行的次數(shù)是固定的。因此，總的時間由一個常數(shù)（即零次多項式）來限界。而一個時間為O(n2)的算法則由一個二次多項式來限界。,21,以下六種計算算法時間的多項式是最常用的。其關(guān)系為： O(1)O(logn)O(n)O(nlogn) O(n2)O(n3) 指數(shù)時間的關(guān)系為： O(2n)O(n!)O(nn) 當(dāng)n取得很大時

13、，指數(shù)時間算法和多項式時間算法在所需時間上非常懸殊。因此，只要有人能將現(xiàn)有指數(shù)時間算法中的任何一個算法化簡為多項式時間算法，那就取得了一個偉大的成就。,22,有的情況下，算法中基本操作重復(fù)執(zhí)行的次數(shù)還隨問題的輸入數(shù)據(jù)集不同而不同。例如： Void bubble-sort(int a，int n) for(I=n-1;change=TURE;I1 change=TURE 最好情況：0次,23,最壞情況：1+2+3+n-1 =n(n-1)/2 平均時間復(fù)雜度為:O(n2) 1.4.4算法的存儲空間需求 空間復(fù)雜度:算法所需存儲空間的度量，記作: S(n)=O(f(n) 其中n為問題的規(guī)模(或大小)

14、,24,第二章 線性表,2.1 線性表的類型定義 2.2 線性表的順序表示和實現(xiàn) 2.3 線性表的鏈?zhǔn)奖硎竞蛯崿F(xiàn) 2.3.1 線性鏈表 2.3.2 循環(huán)鏈表 2.3.3 雙向鏈表 2.4 一元多項式的表示及相加,25,2.1 線性表的邏輯結(jié)構(gòu) 線性表(Linear List) ：由n(n)個數(shù)據(jù)元素(結(jié)點)a1，a2， an組成的有限序列。其中數(shù)據(jù)元素的個數(shù)n定義為表的長度。當(dāng)n=0時稱為空表，常常將非空的線性表(n0)記作： (a1，a2，an) 這里的數(shù)據(jù)元素ai(1in)只是一個抽象的符號，其具體含義在不同的情況下可以不同。 例1、26個英文字母組成的字母表 （A，B，C、Z） 例2、某

15、校從1978年到1983年各種型號的計算機擁有量的變化情況。 （6，17，28，50，92，188）,26,例3、學(xué)生健康情況登記表如下：,27,例4、一副撲克的點數(shù) （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)。 數(shù)據(jù)的運算是定義在邏輯結(jié)構(gòu)上的，而運算的具體實現(xiàn)則是在存儲結(jié)構(gòu)上進行的。 抽象數(shù)據(jù)

16、類型的定義為：P19,28,算法2.1 例2-1 利用兩個線性表LA和LB分別表示兩個集合A和B，現(xiàn)要求一個新的集合A=AB。 void union(List if(!locateelem(la，e，equal)listinsert(la，+la-en，e) ,29,算法2.2 例2-2 巳知線性表LA和線性表LB中的數(shù)據(jù)元素按值非遞減有序排列，現(xiàn)要求將LA和LB歸并為一個新的線性表LC，且LC中的元素仍按值非遞減有序排列。 此問題的算法如下：,30,void mergelist(list la，list lb，list while(I=la-len)getelem(lb，j，bj); if(

17、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);listinsert(lc，+k，bi); ,32,2.2 線性表的順序存儲結(jié)構(gòu) 2.2.1 線性表 把線性表的結(jié)點按邏輯順序依次存放在一組地址連續(xù)的存儲單元里。用這種方法存儲的線性表簡稱順序表。 假設(shè)線性表的每個元素需占用l個存儲單元，并以所占的第一個單元的存儲地址作為數(shù)據(jù)元素的存儲位置。則線性表

18、中第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,33,由于C語言中的一維數(shù)組也是采用順序存儲表示，故可以用數(shù)組類型來描述順序表。又因為除了用數(shù)組來存儲線性表的元素之外，順序表還應(yīng)該用一個變量來表示線性表的長度屬性，所以我們用結(jié)構(gòu)類型來定義順序表類型。 # define ListSize 100 typedef int DataType; typedef struc DataType dataLi

19、stSize; int length; Sqlist;,34,2.2.2 順序表上實現(xiàn)的基本操作 在順序表存儲結(jié)構(gòu)中，很容易實現(xiàn)線性表的一些操作，如線性表的構(gòu)造、第i個元素的訪問。 注意：C語言中的數(shù)組下標(biāo)從“0”開始，因此，若L是Sqlist類型的順序表，則表中第i個元素是l.dataI-1。 以下主要討論線性表的插入和刪除兩種運算。 1、插入 線性表的插入運算是指在表的第I(1in+1個位置上，插入一個新結(jié)點x，,35,使長度為n的線性表 (a1，a i-1，ai，an) 變成長度為n+1的線性表 (a1，a i-1，x，ai，an) 算法2.3 Void InsertList(Sqlis

20、t*L，DataType x，int I) int j; if(Il.length+1) printf(“Position error”); return ERROR,36,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+; ,37,現(xiàn)在分析算法的復(fù)雜度。 這里的問題規(guī)模是表的長度，設(shè)它的值為。該算法的時間主要化費在循環(huán)的結(jié)點后移語句上，該語句的執(zhí)行次數(shù)（即移動結(jié)點的次數(shù)）是。由此可看出，所需

21、移動結(jié)點的次數(shù)不僅依賴于表的長度，而且還與插入位置有關(guān)。 當(dāng)時，由于循環(huán)變量的終值大于初值，結(jié)點后移語句將不進行；這是最好情況，其時間復(fù)雜度O（1）； 當(dāng)=1時，結(jié)點后移語句將循環(huán)執(zhí)行n次，需移動表中所有結(jié)點，這是最壞情況，,38,其時間復(fù)雜度為O（n）。 由于插入可能在表中任何位置上進行，因此需分析算法的平均復(fù)雜度 在長度為n的線性表中第i個位置上插入一個結(jié)點，令Eis(n)表示移動結(jié)點的期望值（即移動的平均次數(shù)），則在第i個位置上插入一個結(jié)點的移動次數(shù)為n-I+1。故 Eis(n)= pi(n-I+1) 不失一般性，假設(shè)在表中任何位置(1in+1)上插入結(jié)點的機會是均等的，則 p1=p2=

22、p3=p n+1=1/(n+1) 因此，在等概率插入的情況下， Eis(n)= (n-I+1)/(n+1)=n/2,39,也就是說，在順序表上做插入運算，平均要移動表上一半結(jié)點。當(dāng)表長 n較大時，算法的效率相當(dāng)?shù)?。雖然Eis(n)中n的的系數(shù)較小，但就數(shù)量級而言，它仍然是線性階的。因此算法的平均時間復(fù)雜度為O(n)。 2、刪除 線性表的刪除運算是指將表的第i(1in)結(jié)點刪除，使長度為n的線性表： (a1，a i-1，ai，a i+1，an) 變成長度為n-1的線性表 (a1，a i-1，a i+1，an),40,Void deleteList(Sqlist*L，int I) int j; i

23、f(Il.length) printf(“Position error”); return ERROR for(j=i;j=l.length-1;j+) l.dataj-1=l.dataj; l.length-; ,41,該算法的時間分析與插入算法相似，結(jié)點的移動次數(shù)也是由表長n和位置i決定。 若I=n，則由于循環(huán)變量的初值大于終值，前移語句將不執(zhí)行，無需移動結(jié)點； 若I=1，則前移語句將循環(huán)執(zhí)行n-1次，需移動表中除開始結(jié)點外的所有結(jié)點。這兩種情況下算法的時間復(fù)雜度分別為O(1)和O(n)。 刪除算法的平均性能分析與插入算法相似。在長度為n的線性表中刪除一個結(jié)點，令Ede(n)表示所需移動結(jié)

24、點的平均次數(shù)，刪除表中第i個結(jié)點的移動次數(shù)為n-i，故 Ede(n)= pi(n-I) 式中，pi表示刪除表中第i個結(jié)點的概率。在等,42,概率的假設(shè)下， p1=p2=p3=pn=1/n 由此可得： Ede(n)= (n-I)/n=(n-1)/2 即在順序表上做刪除運算，平均要移動表中約一半的結(jié)點，平均時間復(fù)雜度也是O(n)。 2.3 線性表的鏈?zhǔn)奖硎竞蛯崿F(xiàn) 線性表的順序表示的特點是用物理位置上的鄰接關(guān)系來表示結(jié)點間的邏輯關(guān)系，這一特點使我們可以隨機存取表中的任一結(jié)點，但它也使得,43,插入和刪除操作會移動大量的結(jié)點.為避免大量結(jié)點的移動，我們介紹線性表的另一種存儲方式， 鏈?zhǔn)酱鎯Y(jié)構(gòu)，簡稱為

25、鏈表(Linked List)。 2.3.1 線性鏈表 鏈表是指用一組任意的存儲單元來依次存放線性表的結(jié)點，這組存儲單元即可以是連續(xù)的，也可以是不連續(xù)的，甚至是零散分布在內(nèi)存中的任意位置上的。因此，鏈表中結(jié)點的邏輯次序和物理次序不一定相同。為了能正確表示結(jié)點間的邏輯關(guān)系，在存儲每個結(jié)點值的同時，還必須存儲指示其后繼結(jié)點的地址（或位置）信息，這個信息稱為指針(pointer)或鏈(link)。這兩部分組成了鏈表中的結(jié)點結(jié)構(gòu)：,44,其中：data域是數(shù)據(jù)域，用來存放結(jié)點的值。next是指針域（亦稱鏈域），用來存放結(jié)點的直接后繼的地址（或位置）。鏈表正是通過每個結(jié)點的鏈域?qū)⒕€性表的n個結(jié)點按其邏輯

26、次序鏈接在一起的。由于上述鏈表的每一個結(jié)只有一個鏈域，故將這種鏈表稱為單鏈表（Single Linked)。 顯然，單鏈表中每個結(jié)點的存儲地址是存放在其前趨結(jié)點next域中，而開始結(jié)點無前趨，故應(yīng)設(shè)頭指針head指向開始結(jié)點。同時，由于 終端結(jié)點無后繼，故終端結(jié)點的指針域為空，即null（圖示中也可用表示)。 例1、線性表:(bat，cat，eat，fat，hat，jat，lat，mat),45,的單鏈表示意圖如下：, 110 130 135 160 頭指針 head 165 170 200 205 ,46,head,bat,cat,eat,mat ,單鏈表是由表頭唯一確定，因此單鏈表可以用頭

27、,指針的名字來命名。,例如：若頭指針名是head，則把鏈表稱為表head。,用C語言描述的單鏈表如下：,Typedef char datatype;,Typedef struct node datatype data; struct node *next; listnode;,47,typedef listnode *linklist; listnode *p; linklist head; 注意區(qū)分指針變量和結(jié)點變量這兩個不同的概念。 P為動態(tài)變量，它是通過標(biāo)準(zhǔn)函數(shù)生成的，即 p=(listnode*)malloc(sizeof(listnode); 函數(shù)malloc分配了一個類型為list

28、node的結(jié)點變量的空間，并將其首地址放入指針變量p中。一旦p所指的結(jié)點變量不再需要了，又可通過標(biāo)準(zhǔn)函數(shù) free(p) 釋放所指的結(jié)點變量空間。,48,指針變量P和（其值為結(jié)點地址）和結(jié)點變量*P之間的關(guān)系。,49,一、建立單鏈表 假設(shè)線性表中結(jié)點的數(shù)據(jù)類型是字符，我們逐個輸入這些字符型的結(jié)點，并以換行符n為輸入結(jié)束標(biāo)記。動態(tài)地建立單鏈表的常用方法有如下兩種： 1、頭插法建表 該方法從一個空表開始，重復(fù)讀入數(shù)據(jù)，生成新結(jié)點，將讀入數(shù)據(jù)存放到新結(jié)點的數(shù)據(jù)域中，然后將新結(jié)點插入到當(dāng)前鏈表的表頭上，直到讀入結(jié)束標(biāo)志為止。,50,linklist createlistf(void) char ch;

29、 linklist head; listnode *p; head=null; ch=getchar( ); while (ch!=n p=(listnode*)malloc(sizeof(listnode); pdata=ch; pnext=head;,51,head=p; ch=getchar( ); return (head); ,52,listlink createlist(int n) int data; linklist head; listnode *p head=null; for(i=n;i0;-i) p=(listnode*)malloc(sizeof(listnode);

30、 scanf(%d， ,53,return(head); 2、尾插法建表 頭插法建立鏈表雖然算法簡單，但生成的鏈表中結(jié)點的次序和輸入的順序相反。若希望二者次序一致，可采用尾插法建表。該方法是將新結(jié)點插入到當(dāng)前鏈表的表尾上，為此必須增加一個尾指針r，使其始終指向當(dāng)前鏈表的尾結(jié)點。例：,54,linklist creater( ) char ch; linklist head; listnode *p，*r; /(， *head;) head=NULL;r=NULL; while(ch=getchar( )!=n) p=(listnode *)malloc(sizeof(listnode); pd

31、ata=ch; if(head=NULL) head=p; else,55,rnext=p; r=p; if (r!=NULL) rnext=NULL; return(head); 說明：第一個生成的結(jié)點是開始結(jié)點，將開始結(jié)點插入到空表中，是在當(dāng)前鏈表的第一個位置上插入，該位置上的插入操作和鏈表中其它位置上的插入操作處理是不一樣的，原因是開始結(jié)點的位置是存放在頭指針（指針變量）中，,56,而其余結(jié)點的位置是在其前趨結(jié)點的指針域中。算法中的第一個if語句就是用來對第一個位置上的插入操作做特殊處理。算法中的第二個if語句的作用是為了分別處理空表和非空表兩種不同的情況，若讀入的第一個字符就是結(jié)束標(biāo)志

32、符，則鏈表head是空表，尾指針r亦為空，結(jié)點*r不存在；否則鏈表head非空，最后一個尾結(jié)點*r是終端結(jié)點，應(yīng)將其指針域置空。 如果我們在鏈表的開始結(jié)點之前附加一個結(jié)點，并稱它為頭結(jié)點，那么會帶來以下兩個優(yōu)點： a、由于開始結(jié)點的位置被存放在頭結(jié)點的指針域中，所以在鏈表的第一個位置上的操作就,57,和在表的其它位置上的操作一致，無需進行特殊處理； b、無論鏈表是否為空，其頭指針是指向頭結(jié)點 在的非空指針（空表中頭結(jié)點的指針域為空），因此空表和非空表的處理也就統(tǒng)一了。 其算法如下： linklist createlistr1( ) char ch; linklist head=(linklis

33、t)malloc(sizeof(listnode); listnode *p，*r,58,r=head; while(ch=getchar( )!=n p=(listnode*)malloc(sizeof(listnode); pdata=ch; pnext=p; r=p; rnext=NULL; return(head); ,59,上述算法里動態(tài)申請新結(jié)點空間時未加錯誤處理，可作下列處理： p=(listnode*)malloc(sizeof(listnode) if(p=NULL) error(No space for node can be obtained); return ERROR

34、; 以上算法的時間復(fù)雜度均為O(n)。,60,二、查找運算 1、按序號查找 在鏈表中，即使知道被訪問結(jié)點的序號i，也不能象順序表中那樣直接按序號i訪問結(jié)點，而只能從鏈表的頭指針出發(fā)，順鏈域next逐個結(jié)點往下搜索，直到搜索到第i個結(jié)點為止。因此，鏈表不是隨機存取結(jié)構(gòu)。 設(shè)單鏈表的長度為n，要查找表中第i個結(jié)點，僅當(dāng)1in時，i的值是合法的。但有時需要找頭結(jié)點的位置，故我們將頭結(jié)點看做是第0 個結(jié)點，其算法如下：,61,Listnode * getnode(linklist head ， int i) int j; listnode * p; p=head;j=0; while(pnext ,6

35、2,else return NULL; 2、按值查找 按值查找是在鏈表中，查找是否有結(jié)點值等于給定值key的結(jié)點，若有的話，則返回首次找到的其值為key的結(jié)點的存儲位置；否則返回NULL。查找過程從開始結(jié)點出發(fā)，順著鏈表逐個將結(jié)點的值和給定值key作比較。其算法如下：,63,Listnode * locatenode(linklist head，int key) listnode * p=headnext; while( p 該算法的執(zhí)行時間亦與輸入實例中的的取值key有關(guān)，其平均時間復(fù)雜度的分析類似于按序號查找，也為O(n)。,64,三、插入運算 插入運算是將值為x的新結(jié)點插入到表的第i個結(jié)

36、點的位置上，即插入到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)系的變化，插入過程如：,65,具體算法如下： 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

37、=x; qnext=pnext; pnext=q; ,66,設(shè)鏈表的長度為n，合法的插入位置是1in+1。注意當(dāng)i=1時，getnode找到的是頭結(jié)點，當(dāng) i=n+1時，getnode找到的是結(jié)點an。因此，用i-1做實參調(diào)用getnode時可完成插入位置的合法性檢查。算法的時間主要耗費在查找操作getnode上，故時間復(fù)雜度亦為O(n)。 四、刪除運算 刪除運算是將表的第i個結(jié)點刪去。因為在單鏈表中結(jié)點ai的存儲地址是在其直接前趨結(jié)點a a i-1的指針域next中，所以我們必須首先找到,67,a i-1的存儲位置p。然后令pnext指向ai的直接后繼結(jié)點，即把ai從鏈上摘下。最后釋放結(jié)點a

38、i的空間，將其歸還給“存儲池”。此過程為：,68,具體算法如下： void deletelist(linklist head， int i) listnode * p， *r; p=getnode(head，i-1); if(p= =NULL | pnext= =NULL) return ERROR; r=pnext; pnext=rnext; free( r ) ; ,69,設(shè)單鏈表的長度為n，則刪去第i個結(jié)點僅當(dāng)1in時是合法的。注意，當(dāng)i=n+1時，雖然被刪結(jié)點不存在，但其前趨結(jié)點卻存在，它是終端結(jié)點。因此被刪結(jié)點的直接前趨*p存在并不意味著被刪結(jié)點就一定存在，僅當(dāng)*p存在（即p!=NU

39、LL）且*p不是終端結(jié)點 （即pnext!=NULL）時，才能確定被刪結(jié)點存在。 顯然此算法的時間復(fù)雜度也是O(n)。 從上面的討論可以看出，鏈表上實現(xiàn)插入和刪除運算，無須移動結(jié)點，僅需修改指針。,70,2.3.2 循環(huán)鏈表 循環(huán)鏈表時一種頭尾相接的鏈表。其特點是無須增加存儲量，僅對表的鏈接方式稍作改變，即可使得表處理更加方便靈活。 單循環(huán)鏈表：在單鏈表中，將終端結(jié)點的指針域NULL改為指向表頭結(jié)點的或開始結(jié)點，就得到了單鏈形式的循環(huán)鏈表，并簡單稱為單循環(huán)鏈表。 為了使空表和非空表的處理一致，循環(huán)鏈表中也可設(shè)置一個頭結(jié)點。這樣，空循環(huán)鏈表僅有一個自成循環(huán)的頭結(jié)點表示。如下圖所示：,71,a1,

40、an,.,head, 非空表, 空表,在用頭指針表示的單鏈表中，找開始結(jié)點a1的時間是O(1)，然而要找到終端結(jié)點an，則需從頭指針開始遍歷整個鏈表，其時間是O(n),72,在很多實際問題中，表的操作常常是在表的首尾位置上進行，此時頭指針表示的單循環(huán)鏈表就顯得不夠方便.如果改用尾指針rear來表示單循環(huán)鏈表，則查找開始結(jié)點a1和終端結(jié)點an都很方便，它們的存儲位置分別是(rearnext) next和rear，顯然，查找時間都是O(1)。因此，實際中多采用尾指針表示單循環(huán)鏈表。 由于循環(huán)鏈表中沒有NULL指針，故涉及遍歷操作時，其終止條件就不再像非循環(huán)鏈表那樣判斷p或pnext是否為空，而是判

41、斷它們是否等于某一指定指針，如頭指什或尾指針等。,73,例、在鏈表上實現(xiàn)將兩個線性表(a1，a2，a3，an)和(b1，b2，b3，bn)鏈接成一個線性表的運算。 linklist connect(linklist heada，linklist headb) linklist p=headanext; headanext=(headbnext)next free(headbnext); headbnext=p; return(headb); ,74,2.3.3雙鏈表 雙向鏈表(Double linked list):在單鏈表的每個結(jié)點里再增加一個指向其直接前趨的指針域prior。這樣就形成的鏈

42、表中有兩個方向不同的鏈，故稱為雙向鏈表。形式描述為： typedef struct dlistnode datatype data; struc dlistnode *prior，*next; dlistnode; typedef dlistnode * dlinklist; dlinklist head;,75,和單鏈表類似，雙鏈表一般也是由頭指針唯一確定的，增加頭指針也能使雙鏈表上的某些運算變得方便，將頭結(jié)點和尾結(jié)點鏈接起來也能構(gòu)成循環(huán)鏈表，并稱之為雙向鏈表。 設(shè)指針p指向某一結(jié)點，則雙向鏈表結(jié)構(gòu)的對稱性可用下式描述： (pprior)next=p=(pnext)prior 即結(jié)點*p的存

43、儲位置既存放在其前趨結(jié)點*(pprior)的直接后繼指針域中，也存放 在它的后繼結(jié)點*(pnext)的直接前趨指針域中。,76,雙向鏈表的前插操作算法如下： void dinsertbefor(dlistnode *p，datatype x) dlistnode *q=malloc(sizeof(dlistnode); qdata=x; qprior=pprior; qnext=p; ppriornext=q; pprior=q; ,77,void ddeletenode(dlistnode *p) ppriornext=pnext; pnextprior=pprior; free(p); 注

44、意：與單鏈表的插入和刪除操作不同的是，在雙鏈表中插入和刪除必須同時修改兩個方向上的指針。上述兩個算是法的時間復(fù)雜度均為O(1)。,78,第三章 棧和隊列,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 表達式求值,79,3.1.1 棧 3.1.1 棧的定義及基本運算 棧(Stack)是限制在表的一端進行插入和刪除運算的線性表，通常稱插入、刪除的這一端為棧頂(Top)，另一端為棧底(Bottom)。當(dāng)表中沒有元素時稱為空棧。 假設(shè)棧S=(a1

45、，a2，a3，an)，則a1稱為棧底元素，an為棧頂元素。棧中元素按a1，a2，a3，an的次序進棧，退棧的第一個元素應(yīng)為棧頂元素。換句話說，棧的修改是按后進先出的原則進行的。因此，棧稱為后進先出表（LIFO）。,80,3.1.2 順序棧 由于棧是運算受限的線性表，因此線性表的存儲結(jié)構(gòu)對棧也適應(yīng)。 棧的順序存儲結(jié)構(gòu)簡稱為順序棧，它是運算受限的線性表。因此，可用數(shù)組來實現(xiàn)順序棧。因為棧底位置是固定不變的，所以可以將棧底位置設(shè)置在數(shù)組的兩端的任何一個端點；棧頂位置是隨著進棧和退棧操作而變化的，故需用一個整型變量top,81,例、一疊書或一疊盤子。 棧的抽象數(shù)據(jù)類型的定義如下：P44,棧頂,棧底,8

46、2,top,7 6 5 4 3 2 1,-1,83,來指示當(dāng)前棧頂?shù)奈恢茫ǔ７Qtop為棧頂指針。因此，順序棧的類型定義只需將順序表的類型定義中的長度屬性改為top即可。順序棧的類型定義如下： # define StackSize 100 typedef char datatype; typedef struct datatype datastacksize; int top; seqstack;,84,設(shè)S是SeqStack類型的指針變量。若棧底位置在向量的低端，即sdata0是棧底元素，那么棧頂指針stop是正向增加的，即進棧時需將stop加1，退棧時需將stop 減1。因此，stopto

47、p =stacksize-1表示棧滿。當(dāng)棧滿時再做進棧運算必定產(chǎn)生空間溢出，簡稱“上溢”;當(dāng)?？諘r再做退棧運算也將產(chǎn)生溢出，簡稱“下溢”。上溢是一種出錯狀態(tài)，應(yīng)該設(shè)法避免之；下溢則可能是正?，F(xiàn)象，因為棧在程序中使用時，其初態(tài)或終態(tài)都是空棧，所以下溢常常用來作為程序控制轉(zhuǎn)移的條件。,85,3、判斷棧滿 int stackfull(seqstack *s) return(stop=stacksize-1); 4、進棧 void push(seqstack *s，datatype x) if (stackfull(s) error(“stack overflow”); sdata+stop=x; ,

48、86,1、置空棧 void initstack(seqstack *s) stop=-1; 2、判斷?？?int stackempty(seqstack *s) return(stop=-1); ,87,5、退棧 datatype pop(seqstack *s) if(stackempty(s) error(“stack underflow”); x=sdatatop; stop-; return(x) /return(sdatastop-); ,88,6、取棧頂元素 Datatype stacktop(seqstack *s) if(stackempty(s) error(“stack i

49、s enpty”); return sdatastop; ,89,3.1.3 鏈棧 棧的鏈?zhǔn)酱鎯Y(jié)構(gòu)稱為鏈棧，它是運算是受限的單鏈表，克插入和刪除操作僅限制在表頭位置上進行.由于只能在鏈表頭部進行操作，故鏈表沒有必要像單鏈表那樣附加頭結(jié)點。棧頂指針就是鏈表的頭指針。 鏈棧的類型說明如下： typedef struct stacknode datatype data struct stacknode *next stacknode;,90,Void initstack(seqstack *p) ptop=null; int stackempty(linkstack *p) return ptop

50、=null; ,91,Void push(linkstack *p,datatype x) stacknode *q q=(stacknode*)malloc(sizeof(stacknode); qdata=x; qnext=ptop; ptop=p; ,92,Datatype pop(linkstack *p) datatype x; stacknode *q=ptop; if(stackempty(p) error(“stack underflow.”); x=qdata; ptop=qnext; free(q); return x; ,93,datatype stack top(lin

51、kstack *p) if(stackempty(p) error(“stack is empty.”); return ptopdata; ,94,3.2 棧的應(yīng)用舉例 由于棧結(jié)構(gòu)具有的后進先出的固有特性，致使棧成為程序設(shè)計中常用的工具。以下是幾個棧應(yīng)用的例子。 3.2.1 數(shù)制轉(zhuǎn)換 十進制N和其它進制數(shù)的轉(zhuǎn)換是計算機實現(xiàn)計算的基本問題,其解決方法很多,其中一個簡單算法基于下列原理: N=(n div d)*d+n mod d ( 其中:div為整除運算,mod為求余運算) 例如 (1348)10=(2504)8，其運算過程如下：,95,n n div 8 n mod 8 1348 168

52、4 168 21 0 21 2 5 2 0 2,96,void conversion( ) initstack(s); scanf (“%”,n); while(n) push(s,n%8); n=n/8; while(! Stackempty(s) pop(s,e); printf(“%d”,e); ,97,3.2.2 括號匹配的檢驗 假設(shè)表達式中充許括號嵌套,則檢驗括號是否匹配的方法可用“期待的急迫程度”這個概念來描述。例： （）（） （） 3.2.3 行編輯程序 在編輯程序中，設(shè)立一個輸入緩沖區(qū)，用于接受用戶輸入的一行字符，然后逐行存入用戶數(shù)據(jù)區(qū)。允許用戶輸入錯誤，并在發(fā)現(xiàn)有誤時可以及時

53、更正。,98,行編輯程序算法如下: void lineedit( ) initstack(s); ch=gether( ); while(ch!=eof) while(ch!=eof ,99,ch=getchar( ); clearstack(s); if(ch!=eof) ch=gethar( ); destroystack(s); ,100,3.2.4 迷宮求解 入口,出口,101,3.4 隊列 3.4.1 抽象數(shù)據(jù)類型隊列的定義 隊列(Queue)也是一種運算受限的線性表。它只允許在表的一端進行插入，而在另一端進行刪除。允許刪除的一端稱為隊頭(front)，允許插入的一端稱為隊尾(rea

54、r)。 例如：排隊購物。操作系統(tǒng)中的作業(yè)排隊。先進入隊列的成員總是先離開隊列。因此隊列亦稱作先進先出(First In First Out)的線性表，簡稱FIFO表。 當(dāng)隊列中沒有元素時稱為空隊列。在空隊列中依次加入元素a1,a2,an之后，a1是隊頭元素，an是隊尾元素。顯然退出隊列的次序也只能是a1,a2,an ，也就是說隊列的修改是依先進先出的原則進行的。,102,下圖是隊列的示意圖： a1a2an,出隊,入隊,隊頭,隊尾,隊列的抽象數(shù)據(jù)定義見書59,3.4.2 循環(huán)隊列隊列的順序表示和實現(xiàn) 隊列的順序存儲結(jié)構(gòu)稱為順序隊列，順序隊列實際上是運算受限的順序表，和順序表一樣，順序隊列也是必須

55、用一個向量空間來存放當(dāng)前隊,103,列中的元素。由于隊列的隊頭和隊尾的位置是變化的，因而要設(shè)兩個指針和分別指示隊頭和隊尾元素在隊列中的位置，它們的初始值地隊列初始化時均應(yīng)置為。入隊時將新元素插入所指的位置，然后將加。出隊時，刪去所指的元素，然后將加并返回被刪元素。由此可見，當(dāng)頭尾指針相等時隊列為空。在非空隊列里，頭指針始終指向隊頭元素，而尾指針始終指向隊尾元素的下一位置。 0 1 2 3,Front rear,Front rear,(a)隊列初始為空（b）A,B,C入隊,104,front rear front rear,（c) a出隊 (d) b,c出隊，隊為空 和棧類似，隊列中亦有上溢和下

56、溢現(xiàn)象。此外，順序隊列中還存在“假上溢”現(xiàn)象。因為在入隊和出隊的操作中，頭尾指針只增加不減小，致使被刪除元素的空間永遠無法重新利用。因此，盡管隊列中實際的元素個數(shù)遠遠小于向量空間的規(guī)模，但也可能由于尾指針?biāo)瘸鱿蛄靠臻g的上界而不能做入隊操作。該現(xiàn)象稱為假上溢。,105,為充分利用向量空間?？朔鲜黾偕弦绗F(xiàn)象的方法是將向量空間想象為一個首尾相接的圓環(huán)，并稱這種向量為循環(huán)向量，存儲在其中的隊列稱為循環(huán)隊列（Circular Queue)。在循環(huán)隊列中進行出隊、入隊操作時，頭尾指針仍要加1，朝前移動。只不過當(dāng)頭尾指針指向向量上界（QueueSize-1）時，其加1操作的結(jié)果是指向向量的下界0。 這種循環(huán)意義下的加1操作可以描述為： if(I+1=QueueSize) i=0; else i+; 利用模運算可簡化為： i=(i+1)%QueueSize,106,顯然，因為循環(huán)隊列元素的空間可以被利用，除非向量空間真的被隊列元素全部占用，否則不會上溢。因此，除一些簡單的應(yīng)用外，真正實用的順序隊列是循環(huán)隊列