《數(shù)據(jù)結(jié)構(gòu)講義》PPT課件

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

2、是數(shù)據(jù)構(gòu)造l 眾所周知，計算機的程序是對信息進展加工處置。在大多數(shù)情況下，這些信息并不是沒有組織，信息數(shù)據(jù)之間往往具有重要的構(gòu)造關(guān)系，這就是數(shù)據(jù)構(gòu)造的內(nèi)容。那么，什么是數(shù)據(jù)構(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)給定任何一個人的名字時，該算法可以打印出此人的號碼，假設(shè)該簿中根本就沒有這個人，那么該算法也可以報告沒有這個人的標志。l 算法的設(shè)計，依賴于計算機如何存儲人的名字和對應(yīng)的號碼

3、，或者說依賴于名字和其號碼的構(gòu)造。l 數(shù)據(jù)的構(gòu)造，直接影響算法的選擇和效率。l 上述的問題是一種數(shù)據(jù)構(gòu)造問題。可將名字和對應(yīng)的號碼設(shè)計成：二維數(shù)組、表構(gòu)造、向量。l 假定名字和其號碼邏輯上已安排成N元向量的方式，它的每個元素是一個數(shù)對(ai，bi)， 1in l 數(shù)據(jù)構(gòu)造還要提供每種構(gòu)造類型所定義的各種運算的算法。例2、圖書館的書目檢索系統(tǒng)自動化問題例3、教師資料檔案管理系統(tǒng)例4、多叉路口交通燈的管理問題 P3 經(jīng)過以上幾例可以直接地以為：數(shù)據(jù)構(gòu)造就是研討數(shù)據(jù)的邏輯構(gòu)造和物理構(gòu)造以及它們之間相互關(guān)系，并對這種構(gòu)造定義相應(yīng)的運算，而且確保經(jīng)過這些運算后所得到的新構(gòu)造依然是原來的構(gòu)造類型。l 1.

4、2 根本概念和術(shù)語l數(shù)據(jù)(Data):是對信息的一種符號表示。在計算機科學(xué)中是指一切能輸入到計算機中并被計算機程序處置的符號的總稱。l數(shù)據(jù)元素(Data Element):是數(shù)據(jù)的根本單位，在計算機程序中通常作為一個整體進展思索和處置。l 一個數(shù)據(jù)元素可由假設(shè)干個數(shù)據(jù)項組成。數(shù)據(jù)項是數(shù)據(jù)的不可分割的最小單位。l數(shù)據(jù)對象(Data Object)：是性質(zhì)一樣的數(shù)據(jù)元素的集合。是數(shù)據(jù)的一個子集。l數(shù)據(jù)構(gòu)造(Data Structure)：是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。l數(shù)據(jù)構(gòu)造主要指邏輯構(gòu)造和物理構(gòu)造l 數(shù)據(jù)之間的相互關(guān)系稱為邏輯構(gòu)造。通常分為四類根本構(gòu)造：l一、集合 構(gòu)造中的

5、數(shù)據(jù)元素除了同屬于一種類型外，別無其它關(guān)系。l二、線性構(gòu)造 構(gòu)造中的數(shù)據(jù)元素之間存在一對一的關(guān)系。l三、樹型構(gòu)造 構(gòu)造中的數(shù)據(jù)元素之間存在一對多的關(guān)系。l四、圖狀構(gòu)造或網(wǎng)狀構(gòu)造 構(gòu)造中的數(shù)據(jù)元素之間存在多對多的關(guān)系。l l數(shù)據(jù)構(gòu)造的方式定義為：數(shù)據(jù)構(gòu)造是一個二元組：l Data-Structure=(D，S)l其中：D是數(shù)據(jù)元素的有限集，S是D上關(guān)系的有限集。l例 復(fù)數(shù)的數(shù)據(jù)構(gòu)造定義如下：l Complex=(C，R)l其中：C是含兩個實數(shù)的集合C1，C2，分別表示復(fù)數(shù)的實部和虛部。R=P，P是定義在集合上的一種關(guān)系C1，C2。l數(shù)據(jù)構(gòu)造在計算機中的表示稱為數(shù)據(jù)的物理構(gòu)造，又稱為存儲構(gòu)造。l

6、數(shù)據(jù)對象可以是有限的，也可以是無限的。l數(shù)據(jù)構(gòu)造不同于數(shù)據(jù)類型，也不同于數(shù)據(jù)對象，它不僅要描畫數(shù)據(jù)類型的數(shù)據(jù)對象，而且要描畫數(shù)據(jù)對象各元素之間的相互關(guān)系。l籠統(tǒng)數(shù)據(jù)類型：一個數(shù)學(xué)模型以及定義在該模型上的一組操作。l籠統(tǒng)數(shù)據(jù)類型實踐上就是對該數(shù)據(jù)構(gòu)造的定義。由于它定義了一個數(shù)據(jù)的邏輯構(gòu)造以及在此構(gòu)造上的一組算法。l用三元組描畫如下：l，l數(shù)據(jù)構(gòu)造在計算機中有兩種不同的表示方法：l 順序表示和非順序表示l由此得出兩種不同的存儲構(gòu)造：順序存儲構(gòu)造和鏈式存儲構(gòu)造l順序存儲構(gòu)造:用數(shù)據(jù)元素在存儲器中的相對位置來表示數(shù)據(jù)元素之間的邏輯關(guān)系。l鏈式存儲構(gòu)造：在每一個數(shù)據(jù)元素中添加一個存放地址的指針 ，用此指

7、針來表示數(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ù)組、構(gòu)造、結(jié)合、指針、枚舉型、自定義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(xiàn)，l 1.3 籠統(tǒng)數(shù)據(jù)類型的表示和實現(xiàn)lP11l 1.4 算法和算法分析l算法：是對特定問題求解步驟的一種描畫l 算法是指令的有限序列，其中每一條指令表示一個或多個操作

8、。l 算法具有以下五個特性：l1有窮性 一個算法必需總是在執(zhí)行有窮步之后終了，且每一步都在有窮時間內(nèi)完成。l2確定性 算法中每一條指令必需有確切的含義。不存在二義性。且算法只需一個入口和一個出口。l3可行性 一個算法是可行的。即算法描畫的操作都是可以經(jīng)過曾經(jīng)實現(xiàn)的根本運算執(zhí)行有限次來實現(xiàn)的。l4輸入 一個算法有零個或多個輸入，這些輸入取自于某個特定的對象集合。l5輸出 一個算法有一個或多個輸出，這些輸出是同輸入有著某些特定關(guān)系的量。l1.4.2 算法設(shè)計的要求l評價一個好的算法有以下幾個規(guī)范:l(1) 正確性(Correctness ) 算法應(yīng)滿足詳細問題的需求。l(2)可讀性(Readabi

9、lity) 算法應(yīng)該好讀。以有利于閱讀者對程序的了解。l (3)健狀性(Robustness) 算法應(yīng)具有容錯處置。當(dāng)輸入非法數(shù)據(jù)時，算法應(yīng)對其作出反響，而不是產(chǎn)年莫名其妙的輸出結(jié)果。l(4)效率與存儲量需求 效率指的是算法執(zhí)行的時間；存儲量需求指算法執(zhí)行過程中所需求的最大存儲空間。普通，這兩者與問題的規(guī)模有關(guān)。l1.4.3 算法效率的度量l 對一個算法要作出全面的分析可分成兩用人才個階段進展，即事先分析和事后測試l事先分析 求出該算法的一個時間界限函數(shù)l事后測試 搜集此算法的執(zhí)行時間和實踐占用空間的統(tǒng)計資料。l定義：假設(shè)存在兩個正常數(shù)c和n0，對于一切的nn0，有f(n) cg(n) l那么

10、記作 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假設(shè)將s=0也看成是根本操作，那么語句頻度為，其時間復(fù)雜度仍為(1)，即常量階。

11、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定理：假設(shè)A(n)=a m n m +a m-1 n m-1 +a1n+a0是一個m次多項式，那么A(n)=O(n m)l證略。l例for(i=2;i=n;+I)l for(j=2;j=i-1;+j)l +x;ai，j=x;l語句頻度為：l 1+2+3+n-2=(1+n-2) (n-2)/2l =(n-1)

12、(n-2)/2l =n2-3n+2l 時間復(fù)雜度為O(n2)l 即此算法的時間復(fù)雜度為平方階.l 一個算法時間為O(1)的算法，它的根本運算執(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) l aj aj+1;l change=TUREl l 最好情況

13、：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 線性表的鏈式表示和實現(xiàn)l 2.3.1 線性鏈表l 2.3.2 循環(huán)鏈表l 2.3.3 雙向鏈表l 2.4 一元多項式的表示及相加l2.1 線性表的邏輯構(gòu)造l線性表(Linear List) ：由n(n)個數(shù)據(jù)元素(結(jié)點)a1，a2， an組成的有限序列。其中數(shù)據(jù)元素的個數(shù)n定義為表的長度。當(dāng)n=0時稱

14、為空表，經(jīng)常將非空的線性表(n0)記作：l (a1，a2，an) l這里的數(shù)據(jù)元素ai(1in)只是一個籠統(tǒng)的符號，其詳細含義在不同的情況下可以不同。l例1、26個英文字母組成的字母表l A，B，C、Zl例2、某校從1978年到1983年各種型號的計算機擁有量的變化情況。l 6，17，28，50，92，188姓 名學(xué) 號性 別年齡 健康情況王小林790631 男 18 健康陳 紅790632 女 20 一般劉建平790633 男 21 健康張立立790634 男 17 神經(jīng)衰弱 . . .l例4、一副撲克的點數(shù)l 2，3，4，J，Q，K，Al 從以上例子可看出線性表的邏輯特征是：l在非空的線性

15、表，有且僅有一個開場結(jié)點a1，它沒有直接前趨，而僅有一個直接后繼a2；l有且僅有一個終端結(jié)點an，它沒有直接后繼，而僅有一個直接前趨a n-1；l其他的內(nèi)部結(jié)點ai(2in-1)都有且僅有一個直接前趨a i-1和一個直接后繼a i+1。l 線性表是一種典型的線性構(gòu)造。l數(shù)據(jù)的運算是定義在邏輯構(gòu)造上的，而運算的詳細實現(xiàn)那么是在存儲構(gòu)造上進展的。l籠統(tǒng)數(shù)據(jù)類型的定義為：P19 算法2.1例2-1 利用兩個線性表LA和LB分別表示兩個集合A和B，現(xiàn)要求一個新的集合A=AB。 void union(List &La，List Lb) La-len=listlength(La); Lb-len=

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

17、istlength(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;l elselistinsert(lc，+k，bj);+j;l l while(I=la-len)l getelem(la，I+，ai);listinsert(lc，+k，ai);l l while(j=lb-len)l getelem(lb，j+，bj);listinsert(lc，+k，bi);l l l 2.2 線性表的順序存儲構(gòu)造l2.2.1 線性表l 把線

18、性表的結(jié)點按邏輯順序依次存放在一組地址延續(xù)的存儲單元里。用這種方法存儲的線性表簡稱順序表。l 假設(shè)線性表的每個元素需占用l個存儲單元，并以所占的第一個單元的存儲地址作為數(shù)據(jù)元素的存儲位置。那么線性表中第I+1個數(shù)據(jù)元素的存儲位置LOC( a i+1)和第i個數(shù)據(jù)元素的存儲位置LOC(a I )之間滿足以下關(guān)系：l LOC(a i+1)=LOC(a i)+ll 線性表的第i個數(shù)據(jù)元素ai的存儲位置為：l LOC(ai)=LOC(a1)+(I-1)*ll l l由于C言語中的一維數(shù)組也是采用順序存儲表示，故可以用數(shù)組類型來描畫順序表。又由于除了用數(shù)組來存儲線性表的元素之外，順序表還應(yīng)該用一個變量來

19、表示線性表的長度屬性，所以我們用構(gòu)造類型來定義順序表類型。l # define ListSize 100l typedef int DataType;l typedef strucl DataType dataListSize;l int length;l Sqlist;l2.2.2 順序表上實現(xiàn)的根本操作l 在順序表存儲構(gòu)造中，很容易實現(xiàn)線性表的一些操作，如線性表的構(gòu)造、第i個元素的訪問。l 留意：C言語中的數(shù)組下標從“0開場，因此，假設(shè)L是Sqlist類型的順序表，那么表中第i個元素是l.dataI-1。l 以下主要討論線性表的插入和刪除兩種運算。l 1、插入l 線性表的插入運算是指在表的

20、第I(1in+1個位置上，插入一個新結(jié)點x，使長度為n的線性表 (a1，a i-1，ai，an) 變生長度為n+1的線性表 (a1，a i-1，x，ai，an) 算法2.3Void InsertList(Sqlist*L，DataType x，int I) int j; if(Il.length+1) printf(“Position error); return ERROR l if(l.length=ListSize)l printf(“overflow);l exit(overflow);l for(j=l.length-1;j=I-1;j-)l l.dataj+1=l.dataj;l

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

22、望值即挪動的平均次數(shù)，那么在第i個位置上插入一個結(jié)點的挪動次數(shù)為n-I+1。故l Eis(n)= pi(n-I+1)l 不失普通性，假設(shè)在表中任何位置(1in+1)上插入結(jié)點的時機是均等的，那么l p1=p2=p3=p n+1=1/(n+1)l 因此，在等概率插入的情況下，l Eis(n)= (n-I+1)/(n+1)=n/2l 也就是說，在順序表上做插入運算，平均要挪動表上一半結(jié)點。當(dāng)表長 n較大時，算法的效率相當(dāng)?shù)汀ｋm然Eis(n)中n的的系數(shù)較小，但就數(shù)量級而言，它依然是線性階的。因此算法的平均時間復(fù)雜度為O(n)。 2、刪除 線性表的刪除運算是指將表的第i(1in)結(jié)點刪除，使長度為n

23、的線性表： (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; linklist head; listnode *p head=null; for(

24、i=n;i0;-i) p=(listnode*)malloc(sizeof(listnode); scanf(%d，&pdata); pnext=head; head=p; return(head); 2、尾插法建表 頭插法建立鏈表雖然算法簡單，但生成的鏈表中結(jié)點的次序和輸入的順序相反。假設(shè)希望二者次序一致，可采用尾插法建表。該方法是將新結(jié)點插入到當(dāng)前鏈表的表尾上，為此必需添加一個尾指針r，使其一直指向當(dāng)前鏈表的尾結(jié)點。例： linklist creater( ) char ch; linklist head; listnode *p，*r; /(， *head;) head=NULL

25、;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é)點的位置是存放在頭指針指針變量中， 而其他結(jié)點的位置是在其前趨結(jié)點的指針域中。算法中的第一個if語句就是用來對

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

27、 其算法如下：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=(listnode*)malloc(sizeof(listnode) if(p=NUL

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

29、) int j; listnode * p; p=head;j=0; while(pnext & jnext; j+; if (i=j) return p; else return NULL; 2、按值查找 按值查找是在鏈表中，查找能否有結(jié)點值等于給定值key的結(jié)點，假設(shè)有的話，那么前往初次找到的其值為key的結(jié)點的存儲位置；否那么前往NULL。查找過程從開場結(jié)點出發(fā)，順著鏈表逐個將結(jié)點的值和給定值key作比較。其算法如下：Listnode * locatenode(linklist head，int key) listnode * p=headnext; while( p &

30、 pdata!=key) p=pnext; return p; 該算法的執(zhí)行時間亦與輸入實例中的的取值key有關(guān)，其平均時間復(fù)雜度的分析類似于按序號查找，也為O(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(linklist head，datetype x，int i) listnod

31、e * 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時可完成插入位置的合法性檢查。算法的時間主要耗費在查找操作getnode上，故時間復(fù)雜度亦為O(n)。四、刪除運算 刪除運算是將表的第i個結(jié)點刪去。由

32、于在單鏈表中結(jié)點ai的存儲地址是在其直接前趨結(jié)點a a i-1的指針域next中，所以我們必需首先找到 a i-1的存儲位置p。然后令pnext指向ai的直接后繼結(jié)點，即把ai從鏈上摘下。最后釋放結(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=rnext; free( r ) ; 設(shè)單鏈表的長度為n，那么刪去第i個結(jié)

33、點僅當(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)插入和刪除運算，無須挪動結(jié)點，僅需修正指針。2.3.2 循環(huán)鏈表 循環(huán)鏈表時一種頭尾相接的鏈表。其特點是無須添加存儲量，僅對表的鏈接方式稍作改動，即可使得表處置更加方便靈敏。單循環(huán)鏈表：在單鏈表中，將終端結(jié)點的指針域NULL改為指向表頭結(jié)點的或開場結(jié)點，就得到了單鏈方式

34、的循環(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īng)常是在表的首尾位置上進展，此時頭指針表示的單循環(huán)鏈表就顯得不夠方便.假設(shè)改用尾指針rear來表示單循環(huán)鏈表，那么查找開場結(jié)點a1和終端結(jié)點an都很方便，它們的存儲位置分別是(rearnext) next和rear，顯然，查找時間都是O(1)。因

35、此，實踐中多采用尾指針表示單循環(huán)鏈表。 由于循環(huán)鏈表中沒有NULL指針，故涉及遍歷操作時，其終止條件就不再像非循環(huán)鏈表那樣判別p或pnext能否為空，而是判別它們能否等于某一指定指針，如頭指什或尾指針等。例、在鏈表上實現(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); 2.3

36、.3雙鏈表 雙向鏈表(Double linked list):在單鏈表的每個結(jié)點里再添加一個指向其直接前趨的指針域prior。這樣就構(gòu)成的鏈表中有兩個方向不同的鏈，故稱為雙向鏈表。方式描畫為： typedef struct dlistnode datatype data; struc dlistnode *prior，*next; dlistnode; typedef dlistnode * dlinklist; dlinklist head; 和單鏈表類似，雙鏈表普通也是由頭指針獨一確定的，添加頭指針也能使雙鏈表上的某些運算變得方便，將頭結(jié)點和尾結(jié)點鏈接起來也能構(gòu)成循環(huán)鏈表，并稱之為雙向鏈表

37、。 設(shè)指針p指向某一結(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; ppriornext=q; pprior=q; void ddeletenode(d

38、listnode *p) ppriornext=pnext; pnextprior=pprior; free(p); 留意：與單鏈表的插入和刪除操作不同的是，在雙鏈表中插入和刪除必需同時修正兩個方向上的指針。上述兩個算是法的時間復(fù)雜度均為O(1)。3.1 棧 3.1.1 籠統(tǒng)數(shù)據(jù)類型棧的定義 3.1.2 棧的表示和實現(xiàn)3.2 棧的運用舉例 3.2.1 數(shù)制轉(zhuǎn)換 3.2.2 括號匹配的檢驗 3.2.4 行編輯程序 3.2.5 迷宮求解 3.2.5 表達式求值 3.1.1 棧3.1.1 棧的定義及根本運算 棧(Stack)是限制在表的一端進展插入和刪除運算的線性表，通常稱插入、刪除的這一端為棧頂(

39、Top)，另一端為棧底(Bottom)。當(dāng)表中沒有元素時稱為空棧。 假設(shè)棧S=(a1，a2，a3，an)，那么a1稱為棧底元素，an為棧頂元素。棧中元素按a1，a2，a3，an的次序進棧，退棧的第一個元素應(yīng)為棧頂元素。換句話說，棧的修正是按后進先出的原那么進展的。因此，棧稱為后進先出表LIFO。3.1.2 順序棧 由于棧是運算受限的線性表，因此線性表的存儲構(gòu)造對棧也順應(yīng)。 棧的順序存儲構(gòu)造簡稱為順序棧，它是運算受限的線性表。因此，可用數(shù)組來實現(xiàn)順序棧。由于棧底位置是固定不變的，所以可以將棧底位置設(shè)置在數(shù)組的兩端的任何一個端點；棧頂位置是隨著進棧和退棧操作而變化的，故需用一個整型變量top例、一

40、疊書或一疊盤子。 棧的籠統(tǒng)數(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類型的指針變量。假設(shè)棧底位置在向量的低端，即sdata0是棧底元素，那么棧頂指針stop是正向添

41、加的，即進棧時需將stop加1，退棧時需將stop 減1。因此，stoptop =stacksize-1表示棧滿。當(dāng)棧滿時再做進棧運算必定產(chǎn)生空間溢出，簡稱“上溢;當(dāng)棧空時再做退棧運算也將產(chǎn)生溢出，簡稱“下溢。上溢是一種出錯形狀，應(yīng)該設(shè)法防止之；下溢那么能夠是正常景象，由于棧在程序中運用時，其初態(tài)或終態(tài)都是空棧，所以下溢經(jīng)常用來作為程序控制轉(zhuǎn)移的條件。3、判別棧滿 int stackfull(seqstack *s) return(stop=stacksize-1); 4、進棧 void push(seqstack *s，datatype x) if (stackfull(s) error(“

42、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、取棧頂元素 Datatype stacktop(seqstack *s) if(stackempt

43、y(s) error(“stack is enpty); return sdatastop; 3.1.3 鏈棧 棧的鏈式存儲構(gòu)造稱為鏈棧，它是運算是受限的單鏈表，克插入和刪除操作僅限制在表頭位置上進展.由于只能在鏈表頭部進展操作，故鏈表沒有必要像單鏈表那樣附加頭結(jié)點。棧頂指針就是鏈表的頭指針。 鏈棧的類型闡明如下： typedef struct stacknode datatype data struct stacknode *next stacknode; Void initstack(seqstack *p) ptop=null; int stackempty(linkstack *p)

44、return ptop=null; lVoid push(linkstack *p,datatype x)l l stacknode *q q=(stacknode*)malloc(sizeof(stacknode);l qdata=x;l qnext=ptop;l ptop=p;l Datatype pop(linkstack *p) datatype x; stacknode *q=ptop; if(stackempty(p) error(“stack underflow.); x=qdata; ptop=qnext; free(q); return x; datatype stack t

45、op(linkstack *p) if(stackempty(p) error(“stack is empty.); return ptopdata; 3.2 棧的運用舉例 由于棧構(gòu)造具有的后進先出的固有特性，致使棧成為程序設(shè)計中常用的工具。以下是幾個棧運用的例子。 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，其運算過程如下： n n div 8 n mod 8 1348 168 4

46、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è)表達式中充許括號嵌套,那么檢驗括號能否匹配的方法可用“等待的急迫程度這個概念來描畫。例： 3.2.3 行編輯程序 在編輯程序中，設(shè)立一個輸入緩沖區(qū)，用于接受用戶輸入的一行字符，然后逐行存入用戶數(shù)據(jù)區(qū)。允許用戶輸入錯誤，并在發(fā)現(xiàn)有誤時可以及時更正。 行編輯程序算法如下: void

47、 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 隊列3.4.1 籠統(tǒng)數(shù)據(jù)類型隊列的定義 隊列(Queue)也是一種運算受限的線性表。它只允許在表的一端

48、進展插入，而在另一端進展刪除。允許刪除的一端稱為隊頭(front)，允許插入的一端稱為隊尾(rear)。例如：排隊購物。操作系統(tǒng)中的作業(yè)排隊。先進入隊列的成員總是先分開隊列。因此隊列亦稱作先進先出(First In First Out)的線性表，簡稱FIFO表。當(dāng)隊列中沒有元素時稱為空隊列。在空隊列中依次參與元素a1,a2,an之后，a1是隊頭元素，an是隊尾元素。顯然退出隊列的次序也只能是a1,a2,an ，也就是說隊列的修正是依先進先出的原那么進展的。以下圖是隊列的表示圖： a1a2an出隊入隊隊頭隊尾隊列的籠統(tǒng)數(shù)據(jù)定義見書593.4.2 循環(huán)隊列隊列的順序表示和實現(xiàn)隊列的順序存儲構(gòu)造稱為

49、順序隊列，順序隊列實踐上是運算受限的順序表，和順序表一樣，順序隊列也是必需用一個向量空間來存放當(dāng)前隊列中的元素。由于隊列的隊頭和隊尾的位置是變化的，因此要設(shè)兩個指針和分別指示隊頭和隊尾元素在隊列中的位置，它們的初始值地隊列初始化時均應(yīng)置為。入隊時將新元素插入所指的位置，然后將加。出隊時，刪去所指的元素，然后將加并前往被刪元素。由此可見，當(dāng)頭尾指針相等時隊列為空。在非空隊列里，頭指針一直指向隊頭元素，而尾指針一直指向隊尾元素的下一位置。 0 1 2 3FrontrearabcFront rear (a)隊列初始為空bA,B,C入隊 b c front rear front rear c) a出隊

50、 (d) b,c出隊，隊為空和棧類似，隊列中亦有上溢和下溢景象。此外，順序隊列中還存在“假上溢景象。由于在入隊和出隊的操作中，頭尾指針只添加不減小，致使被刪除元素的空間永遠無法重新利用。因此，雖然隊列中實踐的元素個數(shù)遠遠小于向量空間的規(guī)模，但也能夠由于尾指針巳超出向量空間的上界而不能做入隊操作。該景象稱為假上溢。為充分利用向量空間。抑制上述假上溢景象的方法是將向量空間想象為一個首尾相接的圓環(huán)，并稱這種向量為循環(huán)向量，存儲在其中的隊列稱為循環(huán)隊列Circular Queue)。在循環(huán)隊列中進展出隊、入隊操作時，頭尾指針仍要加1，朝前挪動。只不過當(dāng)頭尾指針指向向量上界QueueSize-1時，其加

51、1操作的結(jié)果是指向向量的下界0。這種循環(huán)意義下的加1操作可以描畫為： if(I+1=QueueSize) i=0; else i+; 利用模運算可簡化為： i=(i+1)%QueueSize 顯然，由于循環(huán)隊列元素的空間可以被利用，除非向量空間真的被隊列元素全部占用，否那么不會上溢。因此，除一些簡單的運用外，真正適用的順序隊列是循環(huán)隊列。 如下圖：由于入隊時尾指針向前追逐頭指針，出隊時頭指針向前追逐尾指針，故隊空和隊滿時頭尾指針均相等。因此，我們無法經(jīng)過front=rear來判別隊列“空還是“滿。 處理此問題的方法至少有三種： 其一是另設(shè)一個布爾變量以匹別隊列的空和滿；其二是少用一個元素的空間

52、，商定入隊前，測試尾指針在循環(huán)意義下加1后能否等于頭指針，假設(shè)相等那么以為隊滿留意：rear所指的單元一直為空；其三是運用一個計數(shù)器記錄隊列中元素的總數(shù)實踐上是隊列長度。下面我們用第三種方法實現(xiàn)循環(huán)隊列上的六種根本操作，為此先給出循環(huán)隊列的類型定義。 #define QueueSize 100 typedef char DataType; typedef Struct int front; int rear; int count; datatype dataqueuesize cirqueue;1置空隊 void initqueue(cirqueue *q) qfront=qrear=0; q

53、count=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; qrear=(qrear+1)%queuesize; 5出隊 datatype dequeue(cirqueue *q) datatype temp; if

54、(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 鏈隊列l(wèi) 隊列的鏈式存儲構(gòu)造簡稱為鏈隊列，它是限制僅在表頭刪除和表尾插入的單鏈表。顯然僅有單鏈表的頭指針不便于在表尾做插入操作，為此再添加一個尾指針，指向鏈表的最后一

55、個結(jié)點。于是，一個鏈隊列由一個頭指針獨一確定。和順序隊列類似，我們也是將這兩個指針封裝在一同，將鏈隊列的類型LinkQueue定義為一個構(gòu)造類型：l typedef struct queuenodel datatype data;l struct queuenode *next;l queuenode; typedef struct queuenode *front; queuenode *rear; linkqueue;下面給出鏈隊列上實現(xiàn)的根本運算： void initqueue(linkqueue *q) qfront=qrear=null; int queueempty(linkque

56、ue *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; Datatype dequeue(linkqueue *q) datatype x; queuenode *p if(queueempty(q) error(“que

57、ue 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)原隊中只需一個結(jié)點時，該結(jié)點既是隊頭也是隊尾，故刪去此結(jié)點時亦需修正尾指針，且刪去此結(jié)點后隊列變空。 習(xí)題1、設(shè)將整數(shù)以萬計、2、3、4依次進棧，但只需出棧時棧非空，那么可將出棧操作

58、按任何次序夾入其中，請回答下有問題：1假設(shè)入棧次序為push(1)，pop()，push(2，push(3)，pop()，pop( )，push(4)，pop( )，那么出棧的數(shù)字序列為什么？2能否得到出棧序列車員423和平共處五項原那么432？并闡明為什么不能得到或如何得到。3請分析1、2、3、4的24種陳列中，哪些序列可以經(jīng)過相應(yīng)的入出棧得到。2、鏈棧中為何不設(shè)頭指針？3、循環(huán)隊列的優(yōu)點是什么？如何判別它的空和滿？4、設(shè)長度為n的鏈隊列用單循環(huán)鏈表表示，假設(shè)只設(shè)頭指針，那么怎樣進展入隊和出隊操作；假設(shè)只設(shè)尾指針呢？5、利用棧的根本操作，寫一個前往棧s中結(jié)點個數(shù)的算法int stacksiz

59、e(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)的入隊和出隊算法，要求出隊時需前往隊頭指針。9、指出以下程序段的功能是什么？ (1) void demo1(seqstack *s) int I;arr64;n=0; while (!stacke

60、mpty(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)l 4.2.1 定長順序存儲表示l 4.2.2 堆分配存儲表示l 4.2.3 串的塊鏈存儲表示 4.1 串類型的定義一、串和根本概念 串(String)是零個或多個字符組成的有限序列。普通記作S=“a1a2a