嚴(yán)蔚敏數(shù)據(jù)結(jié)構(gòu)c語言版ppt課件

1、數(shù) 據(jù) 結(jié) 構(gòu)計(jì)算機(jī)系第一章緒論1.11.21.31.4什么是數(shù)據(jù)結(jié)構(gòu)基本概念和術(shù)語抽象數(shù)據(jù)類型的表示與實(shí)現(xiàn)算法和算法分1.4.11.4.21.4.31.4.4算法算法設(shè)計(jì)的要求算法效率的度量算法的存儲(chǔ)空間的需求第一章緒論計(jì)算機(jī)是一門研究用計(jì)算機(jī)進(jìn)行信息表示和處理的科學(xué)。這里面涉及到兩個(gè)問題：信息的表示信息的處理而信息的表示和組又直接關(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)這門課所要研究的問題。1.1什么是數(shù)據(jù)

2、結(jié)構(gòu)眾所周知，計(jì)算機(jī)的程序是對(duì)信息進(jìn)行加工處理。在大多數(shù)情況下，這些信息并不是沒有組織，信息（數(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)碼，如果該電話簿中根本就沒有這個(gè)人，則該算法也能夠報(bào)告沒有這個(gè)人的標(biāo)志。算法的設(shè)計(jì)，依賴于計(jì)算機(jī)如何存儲(chǔ)人的名字和對(duì)應(yīng)的電話號(hào)

3、碼，或者說依賴于名字和其電話號(hào)碼的結(jié)構(gòu)。數(shù)據(jù)的結(jié)構(gòu)，直接影響算法的選擇和效率。上述的問題是一種數(shù)據(jù)結(jié)構(gòu)問題?？蓪⒚趾蛯?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、圖書館的書目檢索系統(tǒng)自動(dòng)化問題例3、教師資料例4、多叉路P3管理系統(tǒng)通燈的管理問題通過以上幾例可以直接地認(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)過這些運(yùn)算后所得到的新結(jié)構(gòu)仍然是原來的結(jié)構(gòu)類型。1.2基本概念和

4、術(shù)語數(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)。通常分為四類基本結(jié)構(gòu)：一、集合結(jié)構(gòu)中的數(shù)據(jù)元素除了同屬于一種類型外，別無其

5、它關(guān)系。二、線性結(jié)構(gòu)對(duì)一的關(guān)系。三、樹型結(jié)構(gòu)結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一對(duì)多的關(guān)系。四、圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)之間存在多對(duì)多的關(guān)系。結(jié)構(gòu)中的數(shù)據(jù)元素?cái)?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)。數(shù)據(jù)對(duì)象可以是有限的，也可以是無限的。數(shù)據(jù)結(jié)構(gòu)不同于數(shù)據(jù)類型，也不同于數(shù)據(jù)對(duì)

6、象，它不僅要描述數(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ì)位置來表示數(shù)據(jù)元素之間的邏輯關(guān)系。 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：在每一個(gè)數(shù)據(jù)元素中增加一個(gè)存放地址的指針（），用此指針來表示數(shù)據(jù)元素之間的邏輯關(guān)系。數(shù)據(jù)類型：在一種程序設(shè)計(jì)語言中，變量所具有的數(shù)據(jù)種

7、類。例1、 在FORTRAN語言中，變量的數(shù)據(jù)類型有整型、實(shí)型、和復(fù)數(shù)型例2、在C語言中數(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，1.3 抽象數(shù)據(jù)類型的表示和實(shí)現(xiàn) P111.4算法和算法分析算法：是對(duì)特定問題求解步驟的一種描述算法是指令的有限序列，其中每一條指令表示一個(gè)或多個(gè)操作。算法具有以下五個(gè)特性：（1）有窮性一個(gè)算法必須總是在執(zhí)行有窮步之后結(jié)束，且每一步都在有窮時(shí)間內(nèi)完成。（2）確定性算法中

8、每一條指令必須有確切的含義。不存在二義性。且算法只有一個(gè)入口和一個(gè)出口。（3）可行性一個(gè)算法是可行的。即算法描述的操作都是可以通過已經(jīng)實(shí)現(xiàn)的基本運(yùn)算執(zhí)行有限次來實(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 )的需求。(2) 可讀性(Readability)算法應(yīng)滿足具體問題算法應(yīng)該好讀。以有利于閱讀者對(duì)程序的理解。(3)健狀性(Robustness) 算法應(yīng)具有容錯(cuò)處理。當(dāng)輸入非法數(shù)據(jù)時(shí)，算法應(yīng)對(duì)其

9、作出反應(yīng)，而不是產(chǎn)年莫名其妙的輸出結(jié)果。(4)效率與存儲(chǔ)量需求效率指的是算法執(zhí)行的時(shí)間；存儲(chǔ)量需求指算法執(zhí)行過程中所需要的最大存儲(chǔ)空間。一般，這兩者與問題的規(guī)模有關(guān)。1.4.3 算法效率的度量對(duì)一個(gè)算法要作出全面的分析可分成兩用人才個(gè)階段進(jìn)行，即事先分析和事后測(cè)試事先分析事后測(cè)試求出該算法的一個(gè)時(shí)間界限函數(shù)收集此算法的執(zhí)行時(shí)間和實(shí)際占用空間的統(tǒng)計(jì)資料。定義：如果存在兩個(gè)正常數(shù)c和n0，對(duì)于所有的nn0，有f(n) cg(n) 則記作f(n)=O(g(n)一般情況下，算法中基本操作重復(fù)執(zhí)行的次數(shù)是問題規(guī)模n的某個(gè)函數(shù)，算法的時(shí)間量度記作T(n)=O(f(n)稱作算法的漸近時(shí)間復(fù)雜度。例、for(

10、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(n)=O(n3) 頻度：是指該語句重復(fù)執(zhí)行的次數(shù) 例 +x;s=0; 將x自增看成是基本操作，則語句頻度為， 即時(shí)間復(fù)雜度為(1) 如果將s=0也看成是基本操作，則語句頻度為，其時(shí)間復(fù)雜度仍為(1)，即常量階。 例、for(I=1;I=n;+I)+x;s+=x;語句頻度為：2n其時(shí)間復(fù)雜度為：O(n)即時(shí)間復(fù)雜度為線性階。 例、for(I=1;I=n;+I)for(j=1;j=n;+j)+x;

11、s+=x;語句頻度為：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; 語句頻度為：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)式） 來限界。而一個(gè)時(shí)間為O(n2)的算法則由一個(gè)二次

12、多項(xiàng)式來限界。 以下六種計(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ǔ)空間的度量， 記作:S(n)=O(f(n) 其中n為問題的規(guī)模(或大小)第二章線性表 2.1 線性表的類型定義 2.2 線性表的順序表示和實(shí)現(xiàn) 2.3 線

13、性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)2.3.12.3.22.3.3線性鏈表循環(huán)鏈表雙向鏈表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è)英文字母組成的字母表（A，B，C、Z） 例2、某校從1978年到1983年各種型號(hào)的計(jì)算機(jī)擁有量的變化情況。（6，17，28，50，92，188）例3、學(xué)生健康情況

14、登記表如下：姓 名學(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è)開始結(jié)點(diǎn)a1， 它沒有直接前趨，而僅有一個(gè)直接后繼a2； 有且僅有一個(gè)終端結(jié)點(diǎn)an，它沒有直接后繼，而僅有一個(gè)直接前趨a n-1；其余的內(nèi)部結(jié)點(diǎn)ai(2in-1)都有且僅有一個(gè)直接前趨a i-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ù)類型的

15、定義為：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)listinsert(la，+la-en，e)算法2.2巳知線性表LA和線性表LB中的數(shù) 例2-2據(jù)元素按值非遞減有序排列，現(xiàn)要求將LA和LB歸并為一個(gè)新的線性表LC，且LC中的元素仍按值非遞減有序排列。此問題的算

16、法如下：voidmergelist(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)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

17、-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( 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語言中的一維數(shù)組也是

18、采用順序存儲(chǔ)表示，故可以用數(shù)組類型來描述順序表。又因?yàn)槌擞脭?shù)組來存儲(chǔ)線性表的元素之外，順序表還應(yīng)該用一個(gè)變量來表示線性表的長(zhǎng)度屬性，所以我們用結(jié)構(gòu)類型來定義順序表類型。# define ListSize100typedeftypedefintDataType;strucDataTypedataListSize;intlength; Sqlist; 2.2.2順序表上實(shí)現(xiàn)的基本操作在順序表存儲(chǔ)結(jié)構(gòu)中，很容易實(shí)現(xiàn)線性表的一些操作，如線性表的構(gòu)造、第i 個(gè)元素的訪問。注意：C語言中的數(shù)組下標(biāo)從“0”開始， 因此，若L是Sqlist類型的順序表，則表中第i個(gè)元素是l.dataI-1。以下主要討論線性

19、表的插入和刪除兩種運(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.3 Void InsertList(Sqlist*L，DataType x，int I) int j;if(Il.length+1) printf(“Position error”);if(l.length=ListSize)printf(“overflow”); exit(overflow);for(j=l.length-1;j=I-1;j-)l.dataj+1=l.data

20、j;l.dataI-1=x; l.length+; 現(xiàn)在分析算法的復(fù)雜度。這里的問題規(guī)模是表的長(zhǎng)度，設(shè)它的值為。該算法的時(shí)間主要化費(fèi)在循環(huán)的結(jié)點(diǎn)后移語句上，該語句的執(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)后移語句將不進(jìn)行；這是最好情況， 其時(shí)間復(fù)雜度O（1）； 當(dāng)=1時(shí)，結(jié)點(diǎn)后移語句將循環(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)的

21、期望值（即移動(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+1)/(n+1)=n/2也就是說，在順序表上做插入運(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

22、，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 ERRORfor(j=i;jdata=ch;pnext=head;head=p;ch=getchar( );return (head);listlinkcreatelist(int n)int data;linklisthead;listnode *phead=null; for(i=n;i0;-i)p=(listnode*)malloc(s

23、izeof(listnode); scanf( %d ，&pdata); pnext=head;head=p;return(head);2、尾插法建表頭插法建立鏈表雖然算法簡(jiǎn)單，但生成的鏈表中結(jié)點(diǎn)的次序和輸入的順序相反。若希望二者次序一致，可采用尾插法建表。該方法是將新結(jié)點(diǎn)插入到當(dāng)前鏈表的表尾上，為此必須增加一個(gè)尾指針r，使其始終指向當(dāng)前鏈表的尾結(jié)點(diǎn)。例：linklistcreater()charch;linklisthead;listnode*p，*r;/(， *head;)head=NULL;r=NULL;while(ch=getchar( )!=n)p=(listnode *)mallo

24、c(sizeof(listnode); pdata=ch;if(head=NULL) head=p;elsernext=p;r=p;if (r!=NULL)rnext=NULL; return(head);說明：第一個(gè)生成的結(jié)點(diǎn)是開始結(jié)點(diǎn)，將開始結(jié)點(diǎn)插入到空表中，是在當(dāng)前鏈表的第一個(gè)位置上插入，該位置上的插入操作和鏈表中其它位置上的插入操作處理是不一樣的，原因是開始結(jié)點(diǎn)的位置是存放在頭指針（指針變量）中，而其余結(jié)點(diǎn)的位置是在其前趨結(jié)點(diǎn)的指針域中。算法中的第一個(gè)if語句就是用來對(duì)第一個(gè)位置上的插入操作做特殊處理。算法中的第二個(gè)if 語句的作用是為了分別處理空表和非空表兩種不同的情況，若讀入的第一

25、個(gè)字符就是結(jié)束標(biāo)志符，則鏈表head是空表，尾指針r亦為空，結(jié)點(diǎn)*r不存在；否則鏈表head非空，最后一個(gè)尾結(jié)點(diǎn)*r是終端結(jié)點(diǎn)，應(yīng)將其指針域置空。如果我們?cè)阪湵淼拈_始結(jié)點(diǎn)之前附加一個(gè)結(jié)點(diǎn)，并稱它為頭結(jié)點(diǎn)，那么會(huì)帶來以下兩個(gè)優(yōu)點(diǎn)：a、由于開始結(jié)點(diǎn)的位置被存放在頭結(jié)點(diǎn)的指針域中，所以在鏈表的第一個(gè)位置上的操作就和在表的其它位置上的操作一致，無需進(jìn)行特殊處理；b、無論鏈表是否為空，其頭指針是指向頭結(jié)點(diǎn)在的非空指針（空表中頭結(jié)點(diǎn)的指針域?yàn)榭眨?因此空表和非空表的處理也就統(tǒng)一了。其算法如下：linklist createlistr1()charch;linklisthead=(linklist)mal

26、loc(sizeof(listnode);listnode*p，*rr=head;while(ch=getchar( )!=n p=(listnode*)malloc(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)。二、查

27、找運(yùn)算1、按序號(hào)查找在鏈表中，即使知道被訪問結(jié)點(diǎn)的序號(hào)i，也不能象順序表中那樣直接按序號(hào)i訪問結(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)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;elseret

28、urn NULL;2、按值查找按值查找是在鏈表中，查找是否有結(jié)點(diǎn)值等于給定值key的結(jié)點(diǎn)，若有的話，則返回首次找到的其值為key的結(jié)點(diǎn)的存儲(chǔ)位置；否則返回NULL。查找過程從開始結(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)

29、插入到表的第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)系的變化，插入過程如：具體算法如下：insertnode(linklisthead，datetypex，intvoidi)listnode* p，*q; p=getnode(head，i-1);if(p=NULL)error(positionerror);q=(listnode *)malloc(sizeof(listnode); qdata=x;qn

30、ext=pnext;pnext=q;設(shè)鏈表的長(zhǎng)度為n，合法的插入位置是1in+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)a a i-1的指針域next中，所以我們必須首先找到a i-1的存儲(chǔ)位置p。然后令pnext指向ai的直接后繼結(jié)點(diǎn)，即把a(bǔ)i從鏈上摘下。最后釋放結(jié)點(diǎn)ai 的空間，將其歸還給“存儲(chǔ)池”。此過程為

31、：具體算法如下：voiddeletelist(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 ) ;設(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í)，才能確定被

32、刪結(jié)點(diǎn)存在。顯然此算法的時(shí)間復(fù)雜度也是O(n)。從上面的討論可以看出，鏈表上實(shí)現(xiàn)插入和刪除運(yùn)算，無須移動(dòng)結(jié)點(diǎn)，僅需修改指針。2.3.2循環(huán)鏈表循環(huán)鏈表時(shí)一種頭尾相接的鏈表。其特點(diǎn)是無須增加存儲(chǔ)量，僅對(duì)表的鏈接方式稍作改變，即可使得表處理更加方便靈活。單循環(huán)鏈表：在單鏈表中，將終端結(jié)點(diǎn)的指針域NULL改為指向表頭結(jié)點(diǎn)的或開始結(jié)點(diǎn)，就得到了單鏈形式的循環(huán)鏈表，并簡(jiǎn)單稱為單循環(huán)鏈表。為了使空表和非空表的處理一致，循環(huán)鏈表中也可設(shè)置一個(gè)頭結(jié)點(diǎn)。這樣，空循環(huán)鏈表僅有一個(gè)自成循環(huán)的頭結(jié)點(diǎn)表示。如下圖所示：.head 非空表 空表在用頭指針表示的單鏈表中，找開始結(jié)點(diǎn)a1 的時(shí)間是O(1)，然而要找到終端結(jié)點(diǎn)

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

34、b2，b3，bn)鏈接成一個(gè)線性表的運(yùn)算。linklistconnect(linklist heada，linklist headb)linklistp=headanext;headanext=(headbnext)nextfree(headbnext); headbnext=p; return(headb);2.3.3雙鏈表雙向鏈表(Double linked list):在單鏈表的每個(gè)結(jié)點(diǎn)里再增加一個(gè)指向其直接前趨的指針域prior。這樣就形成的鏈表中有兩個(gè)方向不同的鏈，故稱為雙向鏈表。形式描述為：typedef struct dlistnode datatype data;struc d

35、listnode *prior，*next;dlistnode;typedef dlistnode * dlinklist; dlinklist head;和單鏈表類似，雙鏈表一般也是由頭指針唯一確定的，增加頭指針也能使雙鏈表上的某些運(yùn)算變得方便，將頭結(jié)點(diǎn)和尾結(jié)點(diǎn)鏈接起來也能構(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 dinse

36、rtbefor(dlistnode *p，datatype x)dlistnode *q=malloc(sizeof(dlistnode); qdata=x;qprior=pprior; qnext=p; ppriornext=q; pprior=q;voidddeletenode(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 棧的表

37、示和實(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á)式求值3.1.1棧3.1.1 棧的定義及基本運(yùn)算棧(Stack)是限制在表的一端進(jìn)行插入和刪除運(yùn)算的線性表，通常稱插入、刪除的這一端為棧頂(Top)，另一端為棧底(Bottom)。當(dāng)表中沒有元素時(shí)稱為空棧。假設(shè)棧S=(a1，a2，a3，an)，則a1稱為棧底元素，an為棧頂元素。棧中元素按a1，a2， a3，an的次序進(jìn)棧，退棧的第一個(gè)元素應(yīng)為棧頂元素。換句話說，棧的修改是按后進(jìn)先出的原則進(jìn)行的。因此，棧稱為后進(jìn)先出表（LIFO）。3.1.2順序棧由于棧是運(yùn)算受限的

38、線性表，因此線性表的存儲(chǔ)結(jié)構(gòu)對(duì)棧也適應(yīng)。棧的順序存儲(chǔ)結(jié)構(gòu)簡(jiǎn)稱為順序棧，它是運(yùn)算受限的線性表。因此，可用數(shù)組來實(shí)現(xiàn)順序棧。因?yàn)闂５孜恢檬枪潭ú蛔兊模?所以可以將棧底位置設(shè)置在數(shù)組的兩端的任何一個(gè)端點(diǎn)；棧頂位置是隨著進(jìn)棧和退棧操作而變化的，故需用一個(gè)整型變量top例、一疊書或一疊盤子。棧的抽象數(shù)據(jù)類型的定義如下：P44棧頂棧底a na n-1a2a17654321-1top來指示當(dāng)前棧頂?shù)奈恢?，通常稱top為棧頂指針。因此，順序棧的類型定義只需將順序表的類型定義中的長(zhǎng)度屬性改為top即可。順序棧的類型定義如下：# define StackSize 100typedefchar datatype;t

39、ypedef struct datatypeint top;seqstack;datastacksize;設(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)棧空時(shí)再做退棧運(yùn)算也將產(chǎn)生溢出，簡(jiǎn)稱“下溢”。上溢是一種出錯(cuò)狀態(tài)，應(yīng)該設(shè)法避免之；下溢則可能是正?，F(xiàn)象， 因?yàn)闂Ｔ诔绦蛑惺褂脮r(shí)，其初態(tài)或終態(tài)都是空棧，所以下溢常常用來作為程序控制轉(zhuǎn)移的條件。3、判斷棧滿in

40、t stackfull(seqstack*s)return(stop=stacksize-1);4、進(jìn)棧voidpush(seqstack*s，datatypex)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=s

41、datatop;stop-; return(x)/return(sdatastop-);6、取棧頂元素Datatypestacktop(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)行操作，故鏈表沒有必要像單鏈表那樣附加頭結(jié)點(diǎn)。棧頂指針就是鏈表的頭指針。鏈棧的類型說明如下：typedefstructstacknodedatatypedatastruct stacknode *ne

42、xtstacknode;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;Datatypepop(linkstack*p)datatypex;stacknode*q=ptop;if(stackempty(p)error(“stack underflow.”); x=qdata;ptop=qnext; free(q);return x;datatypestack 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ī)實(shí)現(xiàn)計(jì)算的基本問題,其解決方法很多,其中一個(gè)簡(jiǎn)單算法基于下列原理:N=(n div d)*d+n m