1、第二章數(shù)據(jù)結(jié)構(gòu)與算法中 北 大 學 計 算 機 與 控 制 工 程 學 院School of Computer Science and Control Engineering . NUC 1 數(shù)據(jù)結(jié)構(gòu)與算法 內(nèi)容及要求掌握算法在解決實際問題中的重要性、算法的特征、算法的時間復雜度和空間復雜度了解線性數(shù)據(jù)結(jié)構(gòu)，掌握隊列和堆棧的邏輯結(jié)構(gòu)及運算，掌握隊列和堆棧的數(shù)據(jù)結(jié)構(gòu)表示和基本應用了解非線性數(shù)據(jù)結(jié)構(gòu)，掌握二叉樹的定義與運算、二叉樹的遍歷 掌握基本的排序與查找算法，掌握算法的C+語言實現(xiàn)1-1數(shù)據(jù)結(jié)構(gòu)與算法概述 眾所周知，早期電子計算機的應用范圍，幾乎只局限于科學和工程的計算，其處理的對象是純數(shù)值性

2、的信息，通常，人們把這類問題稱為數(shù)值計算。近三十年來，電子計算機的發(fā)展異常迅猛，這不僅表現(xiàn)在計算機本身運算速度不斷提高、信息存儲量日益擴大、價格逐步下降，更重要的是計算機廣泛地應用于情報檢索、企業(yè)管理、系統(tǒng)工程等方面，已遠遠超出了科技計算的范圍，而滲透到人類社會活動的一切領域。與此相應，計算機的處理對象也從簡單的純數(shù)值性信息發(fā)展到非數(shù)值性的和具有一定結(jié)構(gòu)的信息。1、什么是數(shù)據(jù)結(jié)構(gòu)計算機解決一個具體問題時，大致需要經(jīng)過下列幾個步驟：首先要從具體問題中抽象出一個適當?shù)臄?shù)學模型；然后設計一個解此數(shù)學模型的算法（Algorithm）；最后編出程序、進行測試、調(diào)整直至得到最終解答。尋求數(shù)學模型的實質(zhì)是分

3、析問題，從中提取操作的對象，并找出這些操作對象之間含有的關系，然后用數(shù)學的語言加以描述。什么是數(shù)據(jù)結(jié)構(gòu)計算機算法與數(shù)據(jù)的結(jié)構(gòu)密切相關，算法無不依附于具體的數(shù)據(jù)結(jié)構(gòu)，數(shù)據(jù)結(jié)構(gòu)直接關系到算法的選擇和效率。運算是由計算機來完成，這就要設計相應的插入、刪除和修改的算法 。也就是說，數(shù)據(jù)結(jié)構(gòu)還需要給出每種結(jié)構(gòu)類型所定義的各種運算的算法。數(shù)據(jù)結(jié)構(gòu)的直觀定義：數(shù)據(jù)結(jié)構(gòu)是研究程序設計中計算機操作的對象以及它們之間的關系和運算的一門學科。2、基本概念和術(shù)語 數(shù)據(jù)數(shù)據(jù)是人們利用文字符號、數(shù)字符號以及其他規(guī)定的符號對現(xiàn)實世界的事物及其活動所做的描述。在計算機科學中，數(shù)據(jù)的含義非常廣泛，我們把一切能夠輸入到計算機中并

4、被計算機程序處理的信息，包括文字、表格、圖象等，都稱為數(shù)據(jù)。例如，一個個人書庫管理程序所要處理的數(shù)據(jù)可能是一張如表1-1所示的表格。實例表1-1 個人書庫管理程序數(shù)據(jù)實例結(jié)點結(jié)點結(jié)點也叫數(shù)據(jù)元素，它是組成數(shù)據(jù)的基本單位。在程序中通常把結(jié)點作為一個整體進行考慮和處理。例如，在表1-1所示的個人書庫中，為了便于處理，把其中的每一行（代表一本書）作為一個基本單位來考慮，故該數(shù)據(jù)由10個結(jié)點構(gòu)成。一般情況下，一個結(jié)點中含有若干個字段（也叫數(shù)據(jù)項）。例如，在表1-1所示的表格數(shù)據(jù)中，每個結(jié)點都有登錄號、書號、書名、作者、出版社和價格等六個字段構(gòu)成。字段是構(gòu)成數(shù)據(jù)的最小單位。邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)結(jié)點和結(jié)點之間

5、的邏輯關系稱為數(shù)據(jù)的邏輯結(jié)構(gòu)。在剛才的表格數(shù)據(jù)中，各結(jié)點之間在邏輯上有一種線性關系，它指出了10個結(jié)點在表中的排列順序。存儲結(jié)構(gòu)存儲結(jié)構(gòu)數(shù)據(jù)在計算機中的存儲表示稱為數(shù)據(jù)的存儲結(jié)構(gòu)。在剛才所示的表格數(shù)據(jù)在計算機中可以有多種存儲表示，例如，可以表示成數(shù)組，存放在內(nèi)存中；也可以表示成文件，存放在磁盤上，等等。磁盤內(nèi)存數(shù)據(jù)處理數(shù)據(jù)處理數(shù)據(jù)處理是指對數(shù)據(jù)進行查找、插入、刪除、合并、排序、統(tǒng)計以及簡單計算等的操作過程。在早期，計算機主要用于科學和工程計算，進入八十年代以后，計算機主要用于數(shù)據(jù)處理。據(jù)有關統(tǒng)計資料表明，現(xiàn)在計算機用于數(shù)據(jù)處理的時間比例達到80%以上，隨著時間的推移和計算機應用的進一步普及，計

6、算機用于數(shù)據(jù)處理的時間比例必將進一步增大。數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)（Data Structure）數(shù)據(jù)結(jié)構(gòu)是研究數(shù)據(jù)元素（Data Element）之間抽象化的相互關系和這種關系在計算機中的存儲表示（即所謂數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)），并對這種結(jié)構(gòu)定義相適應的運算，設計出相應的算法，而且確保經(jīng)過這些運算后所得到的新結(jié)構(gòu)仍然是原來的結(jié)構(gòu)類型。為了敘述上的方便和避免產(chǎn)生混淆，通常我們把數(shù)據(jù)的邏輯結(jié)構(gòu)統(tǒng)稱為數(shù)據(jù)結(jié)構(gòu)，把數(shù)據(jù)的物理結(jié)構(gòu)統(tǒng)稱為存儲結(jié)構(gòu)（Storage Structure）。數(shù)據(jù)類型數(shù)據(jù)類型數(shù)據(jù)類型是指程序設計語言中各變量可取的數(shù)據(jù)種類數(shù)據(jù)類型是高級程序設計語言中的一個基本概念，它和數(shù)據(jù)結(jié)構(gòu)的概念密

7、切相關。一方面，在程序設計語言中，每一個數(shù)據(jù)都屬于某種數(shù)據(jù)類型。類型明顯或隱含地規(guī)定了數(shù)據(jù)的取值范圍、存儲方式以及允許進行的運算?？梢哉J為，數(shù)據(jù)類型是在程序設計中已經(jīng)實現(xiàn)了的數(shù)據(jù)結(jié)構(gòu)。另一方面，在程序設計過程中，當需要引入某種新的數(shù)據(jù)結(jié)構(gòu)時，總是借助編程語言所提供的數(shù)據(jù)類型來描述數(shù)據(jù)的存儲結(jié)構(gòu)。算法算法 簡單地說就是解決特定問題的方法（關于算法的嚴格定義，在此不作討論）。特定的問題可以是數(shù)值的，也可以是非數(shù)值的。解決數(shù)值問題的算法叫做數(shù)值算法，科學和工程計算方面的算法都屬于數(shù)值算法，如求解數(shù)值積分，求解線性方程組、求解代數(shù)方程、求解微分方程等。解決非數(shù)值問題的算法叫做非數(shù)值算法，數(shù)據(jù)處理方面的

8、算法都屬于非數(shù)值算法。例如各種排序算法、查找算法、插入算法、刪除算法、遍歷算法等。數(shù)值算法和非數(shù)值算法并沒有嚴格的區(qū)別。3、算法和算法的描述算法是執(zhí)行特定計算的有窮過程：動態(tài)有窮：當執(zhí)行一個算法時，不論是何種情況，在經(jīng)過了有限步驟后，這個算法一定要終止；確定性：算法中的每條指令都必須是清楚的，指令無二義性；輸入：具有0個或0個以上由外界提供的量；輸出：產(chǎn)生1個或多個結(jié)果；可行性：每條指令都充分基本，原則上可由人僅用筆和紙在有限的時間內(nèi)也能完成；注意：算法和程序是有區(qū)別的，即程序未必能滿足動態(tài)有窮。我們只討論滿足動態(tài)有窮的程序。1)算法的描述 一個算法可以用自然語言、數(shù)字語言或約定的符號來描述，

9、也可以用計算機高級程序語言來描述，如Pascal語言、C語言或偽代碼等。課程中，我們選用C+語言作為描述算法的工具。2)算法評價設計一個好的算法應考慮以下幾個方面：正確性運行時間占用的存儲空間簡單性正確性“正確”的含義在通常的用法中有很大的差別，大體可分為以下四個層次： 程序不含語法錯誤； 程序?qū)τ趲捉M輸入數(shù)據(jù)能夠得出滿足規(guī)格說明要求的結(jié)果； 程序?qū)τ诰倪x擇的典型、苛刻而帶有刁難性的幾組數(shù)據(jù)能夠得出滿足規(guī)格說明要求的結(jié)果； 程序?qū)σ磺泻戏ǖ妮斎霐?shù)據(jù)都能產(chǎn)生滿足規(guī)格說明要求的結(jié)果。 運行時間運行時間是指一個算法在計算機上運算所花費的時間。它大致等于計算機執(zhí)行一種簡單操作（如賦值操作、轉(zhuǎn)向操作、

10、比較操作等等）所需要的時間與算法中進行簡單操作次數(shù)的乘積。通常把算法中包含簡單操作次數(shù)的多少叫做算法的時間復雜性，它是一個算法運行時間的相對量度。時間復雜性【例】計算f=1！+2！+3！+n！。void factorsum(n)int n； int i，j；int f，w； f=0； for (i=1;i=n;i+) w=1； for (j=1;j0，則除a0和an-1外，有且僅有一個直接前趨和一個直接后繼數(shù)據(jù)元素，ai（0in-1）為線性表的第i個數(shù)據(jù)元素，它在數(shù)據(jù)元素ai-1之后，在ai+1之前。a0為線性表的第一個數(shù)據(jù)元素，而an-1是線性表的最后一個數(shù)據(jù)元素；若n=0，則為一個空表，表

11、示無數(shù)據(jù)元素。因此，線性表或者是一個空表（n=0），或者可以寫成：（a0，a1，a2， ai-1，ai，ai+1，an-1）。抽象數(shù)據(jù)類型線性表的定義抽象數(shù)據(jù)類型線性表的定義如下：LinearList=(D,R)其中，D= ai| aiElemSet,i=0,1,2, ，n-1 n1R=| ai-1，aiD, i=0,1,2, ，n-1Elemset為某一數(shù)據(jù)對象集；n為線性表的長度。線性表的主要操作Initiate(L) 初始化：構(gòu)造一個空的線性表L。Insert(L,i,x) 插入：在給定的線性表L中，在第i個元素之前插入數(shù)據(jù)元素x；線性表L長度加1。Delete(L,i) 刪除：在給定的

12、線性表L中，刪除第i個元素；線性表L的長度減1。Locate(L,x) 查找定位：對給定的值x，若線性表L中存在一個元素ai與之相等，則返回該元素在線性表中的位置的序號i，否則返回Null（空）。Length(L) 求長度：對給定的線性表L，返回線性表L的數(shù)據(jù)元素的個數(shù)。2、線性表的順序存儲結(jié)構(gòu)線性表有兩種基本的存儲結(jié)構(gòu)：順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)。在計算機中用一組地址連續(xù)的存儲單元依次存儲線性表的各個數(shù)據(jù)元素，稱作線性表的順序存儲結(jié)構(gòu)。在線性表的順序存儲結(jié)構(gòu)中，其前后兩個元素在存儲空間中是緊鄰的，且前驅(qū)元素一定存儲在后繼元素的前面。由于線性表的所有數(shù)據(jù)元素屬于同一數(shù)據(jù)類型，所以每個元素在存儲

13、器中占用的空間大小相同，因此，要在該線性表中查找某一個元素是很方便的。線性表的順序存儲結(jié)構(gòu)假設線性表中的第一個數(shù)據(jù)元素的存儲地址為Loc(a0)，每一個數(shù)據(jù)元素占d字節(jié)，則線性表中第i個元素ai在計算機存儲空間中的存儲地址為：Loc(ai)= Loc(a0)+id在程序設計語言中，通常利用數(shù)組來表示線性表的順序存儲結(jié)構(gòu)。這是因為數(shù)組具有如下特點：（1）數(shù)據(jù)中的元素間的地址是連續(xù)的；（2）數(shù)組中所有元素的數(shù)據(jù)類型是相同的。而這與線性表的順序存儲空間結(jié)構(gòu)是類似的。示例若定義數(shù)組An= a0，a1，a2，an-1，假設每一個數(shù)組元素占用d個字節(jié)，則數(shù)組元素A0，A1，A2，An-1的地址分別為Loc

14、(A0)，Loc(A0)+d，Loc(A0)+2d，Loc(A0)+（n-1）d 。3、線性表類定義C+語言描述順序存儲結(jié)構(gòu)下的線性表（順序表）如下：typedef int ElemType; /數(shù)據(jù)元素的類型const int MAXSIZE=100; /數(shù)組的容量class SqList private: ElemType elemMAXSIZE; /數(shù)組 int length; /線性表長 public: SqList( void); /構(gòu)造函數(shù) SqList() ; /析構(gòu)函數(shù) void Creat() ; /創(chuàng)建一個線性表 void PrintOut(); /輸出線性表 void I

15、nsert( int i, ElemType e); /插入函數(shù) ElemType Delete(int i); /刪除函數(shù) ; /類定義結(jié)束 3、線性表類定義SqList:SqList() length=0; /構(gòu)造函數(shù)，構(gòu)造空表void SqList:Creat() /創(chuàng)建線性表函數(shù) coutlength; coutn Input Data:n ; for(int k=0; kelemk; void SqList:PrintOut() /輸出線性表函數(shù) coutn length=length ; coutn PrintOut Data:n ; for(int k=0; klength;k+

16、) coutsetw(6)elemk; coutendl; 順序表的插入操作在長度為length(0 length MAXSIZE-2)的順序表的第i(0i length +1)個數(shù)據(jù)元素之前插入一個新的數(shù)據(jù)元素x時，需將最后一個即第length個至第i個元素（共length -i+1個元素）依次向后移動一個位置，空出第i個位置，然后把x插入到第i個存儲位置，插入結(jié)束后順序表的長度增加1。順序表的插入操作 0 a0 1 a1 2 a2 i-1 ai-1 i ai i+1 ai+1 i+2 ai+2 num anum 0 a0 1 a1 2 a2 i-1 ai-1 i x i+1 ai i+2a

17、i+1 numanum插入x順序表的插入算法【算法2.1 順序表的插入】void SqList:Insert( int i, ElemType e) int j; i-; /邏輯位置換算為C+數(shù)組下標值 if(ilength) cout “ i Error!”i; j-) elemj=elemj-1; /移動元素 elemi=e; /插入元素 length+; /線性表長加1 順序表的刪除操作 在長度為length(0 length MAXSIZE-1)的順序表List，刪除第i(0i length)個數(shù)據(jù)元素，需將第i+1至第length個數(shù)據(jù)元素的存儲位置依次前移，并使順序表的長度減1，若

18、i0或i length ，則無法刪除，如圖所示。 0 a0 1 a1 2 a2 i-1 ai-1 i ai+1 i+1 ai+2 num anum 0 a0 1 a1 2 a2 i-1 ai-1 i ai i+1ai+1 numanum順序表的刪除算法 【算法2.2 順序表的刪除】ElemType SqList:Delete(int i) ElemType x; int j; i-; /轉(zhuǎn)換成C+數(shù)組下標 if(ilength-1) cout i Error!endl; x=-1; /判斷刪除位置 else x=elemi; for(j=i; jno,p-score); p=p-next; w

19、hile(p!=NULL);執(zhí)行結(jié)果：020910 87020915 79020921 92鏈表的順序操作02091087&b02091579&c02092192Nullabc&aheadp=head;do printf(%-10s%dn, p-no,p-score); p=p-next; while(p!=NULL);for(p=head;p!=Null;p=p-next) printf(%-10s%dn, p-no,p-score);動態(tài)鏈表在程序執(zhí)行過程中可從無到有的建立一個鏈表，即按使用開辟結(jié)點，輸入各結(jié)點數(shù)據(jù)，并建立起前后的鏈接關系。從而避免了數(shù)組在使用前必須先定義固定的長度，以便在

20、內(nèi)存中分配存貯空間，對于事前難以確定大小時，即需把數(shù)據(jù)空間定得足夠大而浪費空間的弊端。單鏈表結(jié)點結(jié)構(gòu)定義在C+語言中，實現(xiàn)線性表的鏈式存儲結(jié)構(gòu)的類型定義typedef int ElemType;struct NodeType /結(jié)點類型定義 ElemType data; NodeType *next; ;單鏈表類定義單鏈表類定義如下：class LinkList private: NodeType *Head; /鏈表頭指針 public: LinkList(); /構(gòu)造函數(shù)，初始化空鏈表 LinkList(); /析構(gòu)函數(shù) void Creat(); /創(chuàng)建一個非空鏈表 void Displ

21、ay(); /輸出鏈表的數(shù)據(jù)元素 void Insert(int i,ElemType x); /插入 ElemType Delete(int i ); /刪除第i個結(jié)點 ;/類定義結(jié)束單鏈表生成算法void LinkList: Creat() NodeType *p; p=new NodeType; /頭結(jié)點,不是第一個結(jié)點。 p-next=NULL; Head=p; for(int i=1;idata=i;p-next=Head-next; /難點Head-next=p; /難點 單鏈表插入算法void LinkList:Insert(int i,ElemType x) NodeType

22、*p,*q,*s; int k=1; /計數(shù)器k，用于尋找i位置 q=Head; p=Head -next; while(knext; k+; if(k=i) s=new NodeType; s-data=x; s-next=p ; q-next=s; coutn 插入成功。 endl; else coutn i1或i太大，不存在。endl; coutnext; /q指向頭指針，p指向第一個數(shù)據(jù)結(jié)點 while(knext; k+; if(p!=NULL) x=p-data; q-next=p-next; delete p; coutn 刪除結(jié)點成功。endl; else coutn i1或i

23、太大，i不存在。endl; x=-1; return x; 鏈表特點鏈式存貯雖然比順序存貯多占用一些指針空間，但存貯中的碎片可得到充分利用。刪除后的結(jié)點也都會釋放，等待重新使用；鏈式存取只能順序存取，不能隨機存?。粚Σ迦牒蛣h除操作，則利用鏈接存貯比較方便，無需移動元素。顯然：各種存貯結(jié)構(gòu)各有優(yōu)缺點，使用中應根據(jù)實際應用需求選用適宜的存貯結(jié)構(gòu)。1-4棧和隊列從數(shù)據(jù)結(jié)構(gòu)上看，棧和隊列也是線性表，不過是兩種特殊的線性表。棧只允許在表的一端進行插入或刪除操作，而隊列只允許在表的一端進行插入操作、而在另一端進行刪除操作。因而，棧和隊列也可以被稱為操作受限的線性表。棧棧（stack）是一種只允許在一端進行

24、插入和刪除的線性表，它是一種操作受限的線性表。在表中只允許進行插入和刪除的一端稱為棧頂（top），另一端稱為棧底(bottom)。棧的插入操作通常稱為入?；蜻M棧(push)，而棧的刪除操作則稱為出?；蛲藯?pop)。當棧中無數(shù)據(jù)元素時，稱為空棧。根據(jù)棧的定義可知，棧頂元素總是最后入棧的，因而是最先出棧；棧底元素總是最先入棧的，因而也是最后出棧。這種表是按照后進先出（LIFO，last in first out ）的原則組織數(shù)據(jù)的，因此，棧也被稱為“后進先出”的線性表。棧的抽象數(shù)據(jù)類型ADT Stack 數(shù)據(jù)對象：D=ai |aiElemSet , i=1,2,n,n0 ; 數(shù)據(jù)關系：R= |

25、ai-1 ,aiD, i=2,3,n 約定an 端為棧頂，a1 端為棧底。 基本操作：初始化一個空棧； 判?？眨諚７祷豑rue,否則返回False； 進棧，在棧頂插入一個元素； 出棧，在棧頂刪除一個元素； 取棧頂元素值； 置棧為空狀態(tài)； 求棧中數(shù)據(jù)元素的個數(shù)； 銷毀棧； ADT Stack；棧的順序存儲結(jié)構(gòu) 棧的順序存儲結(jié)構(gòu)是利用一批地址連續(xù)的存儲 單元依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素，同時設指針top指向棧頂元素的位置。 采用順序存儲的方式存儲的棧稱之為順序棧。 通常用一維數(shù)組來實現(xiàn)棧的順序存儲，將下標1設為棧底，這樣空棧時棧頂指針top=0； 進棧時，棧頂指針top加，當top達到數(shù)組的最

26、大下標值時為棧滿； 出棧時，棧頂指針top減。順序棧類定義 typedef int ElemType; /數(shù)據(jù)元素的類型const int MAXSIZE=100; /數(shù)組的容量class SqStack private: ElemType elemMAXSIZE; int top; public: SqStack () top=0； /構(gòu)造函數(shù)，初始化一個空棧 SqStack(); /析構(gòu)函數(shù) void SetEmpty() top=0； /置已有的棧為空棧 int IsEmpty() ; /判斷棧是否為空 void Push( ElemType e); /進棧 ElemType Pop()

27、; /出棧 void PrintOut(); /輸出棧中數(shù)據(jù)元素 ElemType GetPop(); /取棧頂元素數(shù)據(jù) ;順序棧類定義 void SqStack:PrintOut() /輸出函數(shù),不可改變top coutn PrintOut Data:n ; if(top=0)coutn 已是空棧！ /或用語句if(IsEmpty() cout=1;k-) coutsetw(6)elemk; coutendl; int SqStack:IsEmpty() /判斷棧是否為空 if(top=0) return 1; else return 0; 順序棧的進棧算法 假設要在棧頂插入數(shù)據(jù)元素e。首先

28、判斷棧是否為滿，棧不滿才能執(zhí)行進棧操作。在進棧時，先使棧頂指針top自加1，然后使數(shù)據(jù)元素e進棧。算法實現(xiàn)如下：void SqStack:Push( ElemType e) if(top=MAXSIZE-1) coutn棧滿溢出endl; /判斷棧是否為滿 else top+; elemtop=e; /數(shù)據(jù)元素e進棧 順序棧的出棧算法 假設要在棧頂刪除數(shù)據(jù)元素e。首先判別棧是否為空，棧不空時才能出棧。出棧時先把棧頂元素值保存，然后棧頂指針top自減，最后返回刪除的數(shù)據(jù)元素值。 ElemType SqStack:Pop() ElemType x; if(top=0) cout n 棧為空，不能進

29、行出棧操作endl; x=0; /表示未曾出棧 else x=elemtop; /出棧 top-; return x; 隊列隊列（queue）是一種只允許在一端進行插入，而在另一端進行刪除的線性表，它是一種操作受限的線性表。在表中只允許進行插入的一端稱為隊尾（rear），只允許進行刪除的一端稱為隊頭(front)。隊列的插入操作通常稱為入隊列或進隊列，而隊列的刪除操作則稱為出隊列或退隊列。當隊列中無數(shù)據(jù)元素時，稱為空隊列。根據(jù)隊列的定義可知，隊頭元素總是最先進隊列的，也總是最先出隊列；隊尾元素總是最后進隊列，因而也是最后出隊列。這種表是按照先進先出（FIFO，first in first ou

30、t ）的原則組織數(shù)據(jù)的，因此，隊列也被稱為“先進先出”表。隊列的抽象數(shù)據(jù)類型 ADT Queue 數(shù)據(jù)對象：D=ai | aiElemSet , i=1,2,n, n0 ; 數(shù)據(jù)關系：R= |ai-1,aiD, i=2,3,n /約定a1端為隊頭，an端為隊尾。 基本操作：初始化一個空隊列； 判隊空，空隊返回True,否則返回False； 入隊，在隊尾插入一個元素； 出隊，在隊頭刪除一個元素； 取隊頭數(shù)據(jù)元素值； 置隊列為空狀態(tài)； 銷毀隊列； ADT Queue;隊列順序存儲結(jié)構(gòu) 隊列的順序存儲常用一維數(shù)組來存儲隊列中的元素。為了指示隊頭和隊尾的位置，需要設置隊頭front和隊尾rear兩個指

31、針，并約定：頭指針front指向隊列頭元素的前一位置，尾指針rear指向隊尾元素。 隊列順序存儲結(jié)構(gòu) 隊列順序存儲結(jié)構(gòu) 存在問題：“假溢出”解決方法： 采用平移元素方法 采用循環(huán)隊列解決隊列順序存儲結(jié)構(gòu)循環(huán)隊列 隊列順序存儲結(jié)構(gòu)循環(huán)隊列循環(huán)隊列判斷隊空條件是：rear=front循環(huán)隊列判斷隊滿條件是：(rear+1)%MAXSIZE=front進隊操作如下：rear=(rear+1)% MAXSIZE; elemrear=x; 出隊操作的如下：front=(front+1)% MAXSIZE; 循環(huán)隊列類定義class SeQueue private: ElemType elemMAXSIZ

32、E; int front,rear; public: SeQueue() front=0; rear=0; /初始化空隊列 SeQueue() ; int Empty(); void Display(); /輸出隊列 void AddQ(ElemType x); /進隊 ElemType DelQ(); /出隊 ElemType GetFront(); ; /循環(huán)隊列類定義結(jié)束循環(huán)隊列類定義int SeQueue:Empty() /判斷循環(huán)隊列是否為空 if(rear=front) return 1; else return 0; ElemType SeQueue:GetFront() /取隊

33、首元素，不出隊 ElemType x; if(front= rear) /判斷隊列是否為空 coutn Queu is Empty! endl; x=-1; else x= elem(front+1)%MAXSIZE; return x; 循環(huán)隊列的進隊算法 void SeQueue:AddQ(ElemType x) if(rear+1) % MAXSIZE=front) /判斷是否滿隊 coutn Queu is Full! endl; else rear=(rear+1) % MAXSIZE; /尾指針加1 elemrear=x; /x進隊列 循環(huán)隊列的出隊算法 ElemType SeQu

34、eue:DelQ () if(front=rear) /判斷隊列是否為空 coutn Queue is Empty! =0)個結(jié)點的有限集。在任意一棵非空樹中：(1)有且僅有一個特定的稱為根的結(jié)點；(2)當n1時,其余結(jié)點可分為m(m0)個互不相交的有限集T1,T2,.Tm，其中每一個集合本身又是一棵樹，并且稱為根的子樹。樹的基本概念 結(jié)點擁有的子樹數(shù)稱為結(jié)點的度。度為0的結(jié)點稱為葉子或終端結(jié)點。度不為0的結(jié)點稱為非終端結(jié)點或分支結(jié)點。樹的基本概念 結(jié)點的層次 樹中根結(jié)點的層次為1，根結(jié)點子樹為第2層，以此類推。 樹的度 樹中所有結(jié)點度的最大值。 樹的深度 樹中所有結(jié)點層次的最大值。 有序樹、

35、無序樹 如果樹中每棵子樹從左向右的排列擁有一定的順序，不得互換，則稱為有序樹，否則稱為無序樹。二叉樹是由 n(n=0) 個結(jié)點的有限集合構(gòu)成，此集合或者為空集，或者由一個根結(jié)點及兩棵互不相交的左右子樹組成，并且左右子樹都是二叉樹。二叉樹結(jié)點的子樹要區(qū)分左子樹和右子樹，即使只有一棵子樹也要進行區(qū)分，說明它是左子樹，還是右子樹,這是二叉樹與樹的最主要的差別。二叉樹 滿二叉樹:一顆深度為k 且有2k -1個結(jié)點的二叉數(shù)稱為滿二叉樹 完全二叉樹：有一棵深度為k，有n個結(jié)點的二叉樹，當且僅當其每一個結(jié)點都與深度為k的滿二叉樹中編號為1n的結(jié)點位置一一對應時，則稱這棵二叉樹為完全二叉樹。二叉樹的 5 種形

36、式(a)空二叉樹A (b)根和空的左右子樹AB (c)根和左子樹AB(d)根和右子樹ACB (e)根和左右子樹二叉樹的性質(zhì) 【性質(zhì)1】 在二叉樹的第i層上最多有2i-1個結(jié)點（i1）。 【性質(zhì)2】 深度為K的二叉樹最多有2K-1個結(jié)點（K1）。 【性質(zhì)3】 對于任意一棵二叉樹BT，如果度為0 的結(jié)點個數(shù)為n0，度為2的結(jié)點個數(shù)為n2，則n0=n2+1。 【性質(zhì)4】 具有n個結(jié)點的完全二叉樹的深度為 log2n+1。其中，log2n 的結(jié)果是不大于log2n的最大整數(shù)。二叉樹的性質(zhì)【性質(zhì)5】 對于有n個結(jié)點的完全二叉樹中的所有結(jié)點按從上到下，從左到右的順序進行編號，則對任意一個結(jié)點i （1in）

37、，都有： （1）如果i=1，則結(jié)點i是這棵完全二叉樹的根，沒有雙親；否則其雙親結(jié)點的編號為 i/2。 （2）如果2in，則結(jié)點i沒有左孩子；否則其左孩子結(jié)點的編號為2i。 （3）如果2i+1n，則結(jié)點i沒有右孩子；否則其右孩子結(jié)點的編號為2i+1。遍歷二叉樹 二叉樹是一種非線性的數(shù)據(jù)結(jié)構(gòu)，在對它進行操作時，總是需要逐一對每個數(shù)據(jù)元素實施操作，這樣就存在一個操作順序問題，由此提出了二叉樹的遍歷操作。 所謂遍歷二叉樹就是按某種順序訪問二叉樹中的每個結(jié)點一次且僅一次的過程。這里的訪問可以是輸出、比較、更新、查看元素內(nèi)容等等各種操作。遍歷二叉樹的三種方法 先序1訪問根結(jié)點2先序訪問左子樹3先序訪問右子

38、樹中序1中序訪問左子樹2中序訪問根結(jié)點3中序訪問右子樹后序1后序訪問左子樹2后序訪問右子樹3訪問根結(jié)點G HD E FB CA先序序列：ABDGCEFH中序序列：DGBAECHF后序序列：GDBEHFCA遍歷二叉樹的三種方法練習先序遍歷結(jié)果：1,2,4,5,6,7,3 1-6查找與排序1.順序查找 順序查找是一種最簡單的查找方法。其基本思想是將查找表作為一個線性表，可以是順序表，也可以是鏈表，依次用查找條件中給定的值與查找表中數(shù)據(jù)元素的關鍵字值進行比較，若某個記錄的關鍵字值與給定值相等，則查找成功，返回該記錄的存儲位置，反之，若直到最后一個記錄，其關鍵字值與給定值均不相等，則查找失敗，返回查找

39、失敗標志。查找 2 折半查找 折半查找要求查找表用順序存儲結(jié)構(gòu)存放且各數(shù)據(jù)元素按關鍵字有序（升序或降序）排列，也就是說折半查找只適用于對有序順序表進行查找。折半查找的基本思想 首先以整個查找表作為查找范圍，用查找條件中給定值k與中間位置結(jié)點的關鍵字比較，若相等，則查找成功。 否則,如果k的值小于關鍵字的值，查找的數(shù)據(jù)元素只有可能在表的前半部分，繼續(xù)對左子表進行折半查找；若k的值大于中間結(jié)點的關鍵字值，在右半部分子表中，所以應該繼續(xù)對右子表進行折半查找。 每進行一次折半查找，要么查找成功，要么將查找范圍縮小一半，重復，直到查找成功或查找范圍縮小為空即查找失敗為止。假設待查有序（升序）順序表中數(shù)據(jù)

40、元素的關鍵字序列為（8,18,27,42,47,50,56, 68,95,120），用折半查找方法查找關鍵字值為27的數(shù)據(jù)元素。折半查找過程示例折半查找的完整算法int bin_search (Se_List a, keytype k) low=1; high=n; /置初始查找范圍的低、高端指針 while (low=high) mid=(low+high)/2; /計算中間項位置 if (k=amid.key) break; /找到，結(jié)束循環(huán) else if (k amid.key) high=mid-1;/給定值k小 else low=mid+1; /給定值k大 if (low=high

41、) return mid ; /查找成功 else return 0 ; /查找失敗排序排序 是把一組無序的數(shù)據(jù)元素按照關鍵字值遞增（或遞減）的順序重新排列。 1.直接插入排序首先將待排序記錄序列中的第一個記錄作為一個有序段，將記錄序列中的第二個記錄插入到上述有序段中形成由兩個記錄組成的有序段，再將記錄序列中的第三個記錄插入到這個有序段中，形成由三個記錄組成的有序段，依此類推，每一趟都是將一個記錄插入到前面的有序段中。1.直接插入排序假設當前欲處理第i個記錄，則應該將這個記錄插入到由前i-1個記錄組成的有序段中，從而形成一個由i個記錄組成的按關鍵字值排列的有序序列，直到所有記錄都插入到有序段中

42、。一共需要經(jīng)過n-1趟就可以將初始序列的n個記錄重新排列成按關鍵字值大小排列的有序序列。直接插入排序例子例如:設待排序的記錄共7個,關鍵碼分別為8,3,2,5,9,1,6直接插入排序算法將第i個記錄插入到由前面i-1個記錄構(gòu)成的有序段中主要有兩個步驟： 將待插入記錄ai 保存在a0中，即a0=ai; 搜索插入位置：j=i-1; /j最初指示i的前一個位置while (a0.key aj.key) aj+1=aj; /后移關鍵字值大于a0.key的記錄 j=j-1; /將j指向前一個記錄，為下次比較做準備aj+1=a0; /將a0放置在第j+1個位置上直接插入排序算法void insertsor

43、t (DataType a, int n) for (i=2; i=n; i+) /需要n-1趟 a0=ai; /將ai賦予監(jiān)視哨 j=i-1; while (a0.keyaj+1），則將其交換，最終達到有序化。其處理過程為： （1）將整個待排序的記錄序列劃分成有序區(qū)和無序區(qū)，初始狀態(tài)有序區(qū)為空，無序區(qū)包括所有待排序的記錄。 （2）對無序區(qū)從前向后依次將相鄰記錄的關鍵字進行比較，若逆序?qū)⑵浣粨Q，從而使得關鍵字值小的記錄向上“飄浮”（左移），關鍵字值大的記錄好像石塊，向下“墮落”（右移）。冒泡排序 每經(jīng)過一趟冒泡排序，都使無序區(qū)中關鍵字值最大的記錄進入有序區(qū)，對于由n個記錄組成的記錄序列，最多經(jīng)

44、過n-1趟冒泡排序，就可以將這n個記錄重新按關鍵字順序排列。冒泡排序例子例如:設待排序文件的關鍵碼為: 38,19,65,13,97,49,41,95,1,73冒泡排序算法void BubbleSort1 (DataType a,int n) for (i=n；i1；i-） for (j=1;ja j+1.key） temp=aj；aj=aj+1；aj+1=temp； 3.簡單選擇排序 簡單選擇排序的基本思想是：每一趟在n-i+1(i=1,2,3,.,n-1)個記錄中選取關鍵字最小的記錄作為有序序列中的第i個記錄。它的具體實現(xiàn)過程為：簡單選擇排序的基本思想(1) 將整個記錄序列劃分為有序區(qū)域和

45、無序區(qū)域，有序區(qū)域位于最左端，無序區(qū)域位于右端，初始狀態(tài)有序區(qū)域為空，無序區(qū)域含有待排序的所有n個記錄。簡單選擇排序的基本思想 設置一個整型變量index，用于記錄在一趟比較過程中關鍵字值最小的記錄位置。 開始將它設定為無序區(qū)域的第一個位置，然后用它與無序區(qū)域中其他記錄比較，若發(fā)現(xiàn)有比它的關鍵字還小的記錄，就將index改為這個新的最小記錄位置。 隨后再用aindex.key 與后面的記錄進行比較，隨時修改index的值，一趟選擇后index中保留的就是本趟關鍵字最小的記錄位置。簡單選擇排序的基本思想(3) 將index位置的記錄交換到無序區(qū)域的第一個位置，使得有序區(qū)域擴展了一個記錄，而無序區(qū)

46、域減少了一個記錄。 不斷重復 (2)、(3)，直到無序區(qū)域剩下一個記錄為止。此時所有的記錄已經(jīng)按關鍵字從小到大的順序排列就位。選擇排序例子例如:設待排序的記錄共7個,關鍵碼分別為8,3,2,5,9,1,6“第i 趟簡單選擇排序”的算法 (1)初始化：假設無序區(qū)域中的第一個記錄為關鍵字值最小的元素，即將index=i; （2）搜索無序區(qū)域中關鍵字值最小的記錄位置：for (j=i+1;j=n;j+)if (aj.keya.index.key) index=j; （3）將無序區(qū)域中關鍵字最小的記錄與無序區(qū)域的第一個記錄進行交換，使得有序區(qū)域由原來的i-1個記錄擴展到i個記錄。簡單選擇排序完整算法void selecsort ( DataType a, int n) for( i=1; in; i+) /對n個記錄進行n-1趟的簡單選擇排序 index=i; /初始化第i趟簡單選