2第一節什么是數據結構一、數據結構概述一般來說，用計算機解決一個具體問題時，大致需經過以下幾個步驟：1、從具體問題抽象出一個適當的數學模型。2、設計一個解此數據模型的算法。3、編出程序，進行測試、調整直至得到最終解答。如：求解梁架結構中應力的數學模型為線性方程組；預報人口增長情況的數學模型為微分方程。然而：更多的非數值計算問題無法用數學方程加以描述。特點：每個學生的信息占據一行，所有學生的信息按學號順序依次排列構成一張表格；表中每個學生的信息依據學號的大小存在著一種前后關系，這就是我們所說的線性結構；對它的操作通常是插入某個學生的信息，刪除某個學生的信息，更新某個學生的信息，按條件檢索某個學生的信息等等。例子：P1例1.1學生健康情況管理。圖書館的書目檢索系統自動化問題。查號系統自動化；倉庫賬目管理……例子：求一組（n個）整數中的最大值。算法：基本操作是“比較兩個數的大小”。特點：在求解過程中，所處理的數據之間具有層次關系，這是我們所說的樹形結構；對它的操作有：建立樹形結構，輸出最低層結點內容等等。另外例子：#字棋。教材P1例1.2人事檔案管理。例子：計算機對弈。算法：對弈的規則和策略。其他例子：多叉路口交通燈的管理問題。教材P1例1.3在n個城市之間建立通信網絡。特點課程之間的先后關系用圖結構描述；通過實施創建圖結構，按要求將圖結構中的頂點進行線性排序。結論1、當今計算機應用的特點：所處理的數據量大且具有一定的關系；對其操作不再是單純的數值計算，而更多地是需要對其進行組織、管理和檢索。2、《數據結構》課程研究的主要內容。計算機的操作對象的關系更加復雜，不再是單純的數值計算，而更多地是非數值性處理。數據結構描述現實世界實體的數學模型（非數值計算）及其上的操作在計算機中的表示和實現。數據結構研究非數值計算的程序設計問題中數據以及它們之間的邏輯關系和對數據的操作的一門課程。重點分析數據之間的抽象的相互關系，而不涉及數據的具體內容。二、數據結構的發展概況起源于程序設計的發展，程序設計經歷三個階段：無結構階段；結構化程序設計階段；面向對象階段。教材中詳述第二個階段，即P2-4中（2）-（5）。三、數據結構與其他課程的關系數據結構是介于數學、計算機硬件和計算機軟件三者之間的一門核心課程。第二節基本概念和術語一、數據是對客觀事物的符號表示。在計算機科學中其含義是指所有能夠輸入到計算機中并被計算機程序處理的符號集合。含義極為廣泛：圖像、聲音等。二、數據元素（節點）：數據的基本單位是數據集合中的一個實體，是計算機程序中加工處理的基本單位。如學籍管理中每個學生的信息；“樹”中的每一點；“圖”中的每一個圓圈。數據元素按其組成可分為簡單型數據元素和復雜型數據元素。簡單型數據元素由一個數據項組成，所謂數據項就是數據中不可再分割的最小單位；復雜型數據元素由多個數據項組成，它通常攜帶著一個概念的多方面信息。三、邏輯結構：數據元素之間的邏輯關系。數據結構中所說的“關系”實際上是指數據元素之間的邏輯關系，又稱此為邏輯結構。如前后關系；上下層關系；先后關系。根據數據元素之間的邏輯結構可將數據結構分為三類：線性結構——一個對一個。如，線性表、棧、隊列。樹形結構——一個對多個。如，樹。圖狀結構——多個對多個，如，圖。四、存儲結構（物理結構）是指數據結構在計算機存儲器中的具體實現。與孤立的數據元素表示形式不同，數據結構中的數據元素不但要表示其本身的實際內容，還要表示清楚數據元素之間的邏輯結構。即數據元素的表示和關系的表示兩部分。1、數據元素的表示：位數據域元素或結點（表示信息的最小單位）（子位串，對應于各數據項）（位串）2、關系的表示：即常見的存儲結構順序存儲結構：特點是借助于數據元素的相對存儲位置來表示數據元素之間的邏輯結構；P6圖1.5a鏈式存儲結構：特點是借助于指示數據元素地址的指針表示數據元素之間的邏輯結構。P6圖1.5b數據的邏輯結構與存儲結構密切相關：算法設計 邏輯結構 算法實現 存儲結構 五、數據結構：帶結構的數據元素的集合。簡單地說，就是相互之間存在一種或多種特定關系的數據元素的集合。常見的數據結構有：線性結構、樹形結構和圖形結構。1、根據數據元素之間關系的不同特征，通常有下列四類基本結構：集合（散列）；線性結構（1：1）；樹形結構（1：N）；圖狀結構（M：N）。2、數據結構的形式定義：數據結構是一個二元組（D，S）。其中D是數據元素的有限集，S是D上關系的有限集。例如：六.數據類型:數據的取值范圍及其操作的總稱。例:C語言中，提供int,char,float,double等基本數據類型，數組、結構體、共用體、枚舉等構造數據類型，還有指針、空(void)類型等。用戶也可用typedef自定義數據類型第二講課題名稱：第一章緒論 第3節抽象數據類型的表示和實現 第4節算法教學目標： 1、使學生了解數據類型的表示和實現； 2、使學生了解用類C語言對算法的表示和實現。教學重點和難點：類C語言的理解主要教學方法和手段：多媒體課件講授教學課時：2課時課的類型：講授課教學內容：第三節抽象數據類型的表示與實現為了表示一個算法，可以用不同的方法。常用的有自然語言、傳統流程圖、偽代碼、PAD圖等。1、用自然語言表示算法：通俗易懂，但文字冗長，易出現“歧義性”。如：“張先生對李先生說他的孩子考上了大學。”2、用流程圖表示算法：直觀形象，易于理解。三種基本結構的表示：順序結構、先擇結構、循環結構。只有一個入口，只有一個出口，結構內的每一部分都有機會被執行到，結構內不存在“死循環”。僅適用于小問題，現在已很少用。3、用偽代碼表示算法：4、用計算機語言表示算法：如C或PASCAL5、用類C或類PASCAL語言算法描述：介于偽碼與C之間選擇算法描述語言的準則（1）該語言應該具有描述數據結構和算法的基本功能；（2）該語言應該盡可能地簡捷，以便于掌握、理解；（3）使用該語言描述的算法應該能夠比較容易地轉換成任何一種程序設計語言。“類C”描述語言是通過對C語言進行精心篩選保留的一個核心子集，并為了便于描述，又做了若干擴展修改，從而，增強了語言的描述功能。以下對類C做簡要說明。1.預定義常量及類型#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineINFEASIBLE-1#defineOVERFLOW-2數據元素被約定為EntryType類型，用戶需要根據具體情況，自行定義該數據類型。數據結構的表示（即存儲結構的表示）使用類型定義（typedef）描述。2.算法描述為以下的函數形式：函數類型函數名（函數參數表）{語句序列；}為了簡化函數的書寫，提高算法描述的清晰度，我們規定除函數參數表中的參數需要說明數據類型外，函數中使用的局部變量可以不做變量說明，必要時給出相應的注釋即可。另外，在書寫算法時，應該養成對重點語句段落添加注解的良好習慣。一般而言：abcde等用作數據元素名；ijklmn等用作整型變量名；pqr等用作指針變量名；當函數返回值為函數結構狀態代碼時，函數定義為Status類型；除值調用方式外，增添C++的引用調用的參數傳遞方式（&）。3.在算法描述中可以使用的賦值語句形式有：簡單賦值變量名=表達式；串聯賦值變量名1=變量名2=...=變量名n=表達式；成組賦值（變量名1，...，變量名n）=（表達式1，...，表達式n）；變量名[]=表達式；變量名[始下標..終下標]=變量名[始下標..終下標]；結構賦值結構名1=結構名2；結構名=（值1，值2，...，值n）；條件賦值變量名=條件表達式?表達式1：表達式2；交換賦值變量名1?變量名2；4.在算法描述中可以使用的選擇結構語句形式有：條件語句1if（表達式）語句；條件語句2if（表達式）語句；else語句；開關語句1switch（表達式）{case值1：語句序列1；break；case值2：語句序列2；break；...case值n：語句序列n；break；default：語句序列n+1；}開關語句2switch{case條件1：語句序列1；break；case條件2：語句序列2；break；...case條件n：語句序列n；break；default：語句序列n+1；}5.在算法描述中可以使用的循環結構語句形式有：for循環語句for（賦初值表達式;循環條件表達式;修改表達式序列）語句；while循環語句while（循環條件表達式）語句；do-while循環語句do{語句序列；}while（循環條件表達式）；6.在描述算法中可以使用的結束語句形式有：函數結束語句return表達式；return;case或循環結束語句break;異常結束語句exit（異常代碼）；7.在算法描述中可以使用的輸入輸出語句形式有：輸入語句scanf([格式串]，變量名1，...，變量名n)；輸出語句printf([格式串]，表達式1，...，表達式n);方括號（[]）中的內容是可以省略的部分。8.在算法描述中使用的注釋格式為：單行注釋//文字序列9.在算法描述中可以使用的擴展函數有：求最大值max（表達式1，...，表達式n）求最小值min（表達式1，...，表達式n）求絕對值abs(表達式)求不足整數值floor(表達式)求進位整數值ceil(表達式)判定文件結束eof(文件變量)或eof判定行結束eoln(文件變量)或eoln10.邏輯運算約定與運算&&對于A&&B，當A的值為0時，不再對B求值。或運算||對于A||B，當A的值為非0時，不再對B求值。例子：【算法1-1】用類C描述將三個數值排序的算法。viodThree_Sort(int*x,int*y,int*z){//將x,y,z三個指針所指示的內容按從小到大的順序重新排列if(*y<*x&&*y<*z)*x?*y;//挑選出最小的數值并換到x指針所指的存儲單元中elseif(*z<*x&&*z<*y)*x?*z;if(*z<*y)*y?*z;//在y和z所指示的存儲單元中挑選出較小者換到y中}第四節算法1.4.1算法的概念算法是解決某個特定問題的一種方法或一個過程。計算機對數據的操作可以分為數值性和非數值性兩種類型。在數值性操作中主要進行的是算術運算；而在非數值性操作中主要進行的是檢索、排序、插入、刪除等等。算法是執行特定計算的有窮過程，是對特定問題求解步驟的一種描述，它是指令的有限序列，其中每一條指令表示一個或多個操作。算法應該具有下列五個特性（1）動態有窮：一個算法必須（對任何合法的輸入值）在執行有窮步之后結束，且每一步都可在有窮時間內完成。算法必須是一個可執行完的步驟，但一個具有死循環的程序亦稱之為程序，這是算法與程序的區別。有窮的概念不是純數學的，而是在實際上合理和可以接受的。注意：算法和程序是有區別的，即程序未必能滿足動態有窮。但在本課程中，只討論滿足動態有窮的程序，因此“算法”和“程序”是通用的。（2）確定性：算法中的每一步，必須有確切的含義，在他人理解時不會產生二義性。（“手舉過頭頂”）（3）可行性：算法中描述的每一步操作都可以通過已有的基本操作執行有限次實現。（4）輸入：一個算法應該有零個或多個輸入。（獲得信息。）（5）輸出：一個算法應該有一個或多個輸出。這里所說的輸出是指與輸入有某種特定關系的量。（目的）舉例問題：按從小到大的順序重新排列x，y，z三個數值的內容。算法：（1）輸入x，y，z三個數值；（2）從三個數值中挑選出最小者并換到x中；（3）從y，z中挑選出較小者并換到y中；（4）輸出排序后的結果。=>算法就是一個具有次序、步驟清楚、最后一定會執行結束的可執行步驟。算法與程序不同之處在于上述第一條。1.4.2算法的設計要求(1)正確性：要求算法能夠正確地執行預先規定的功能，并達到所期望的性能要求。(2)可讀性：為了便于理解、測試和修改算法，算法應該具有良好的可讀性。(3)健壯性：算法中擁有對輸入數據、打開文件、讀取文件記錄、分配內存空間等操作的結果檢測，并通過與用戶對話的形式做出相應的處理選擇。(4)時間與空間效率：算法的時間與空間效率是指將算法變換為程序后，該程序在計算機上運行時所花費的時間及所占據空間的度量。1.4.3算法效率的度量一、算法的時間效率算法的時間效率主要由兩個因素決定：l 所需處理問題的數據量大小，數據量大，所花費的時間就多；l 在解決問題的過程中，基本操作的執行次數。時間特性的分析如果我們將一個算法所花費的時間設計成一個以數據量n為自變量的函數T(n)，這個函數在正整數定義域范圍內一定是單調遞增的。好的算法應該能夠在數據量n增長的同時，函數T(n)的增長速度比較緩慢。P11例子。二、空間效率的分析一個算法的空間效率是指在算法的執行過程中，所占據的輔助空間數量。輔助空間就是除算法代碼本身和輸入輸出數據所占據的空間外，算法臨時開辟的存儲空間單元。在有些算法中，占據輔助空間的數量與所處理的數據量有關，而有些卻無關。后一種是較理想的情況。在設計算法時，應該注意空間效率。第三講課題名稱：第二章棧和隊列 第1節棧 第2節棧的應用舉例教學目標： 1、使學生了解棧的表示和實現； 2、使學生掌握棧的應用。教學重點和難點：棧的應用主要教學方法和手段：多媒體課件講授教學課時：2課時課的類型：講授課教學內容：從邏輯上看，棧和隊列都屬于線性結構，是兩種特殊的線性表。其特殊性在于它們的操作是線性表操作的子集。確切地說就是，線性表上的插入、刪除操作是不受限制的，而棧和隊列上的插入、刪除操作是受某種特殊的限制的。因此，棧和隊列稱作操作受限的線性表。3.1.1棧的定義棧是一種特殊的線性表。其特殊性在于限定插入和刪除數據元素的操作只能在線性表的一端進行。如下所示：進行插入和刪除的一端是浮動端，通常被稱為棧頂，并用一個“棧頂指針”指示；而另一端是固定端，通常被稱為棧底。我們經常將棧用下圖形式描述：棧：插入和刪除在一端進行的線性表。棧頂：進行插入和刪除的浮動端。用棧頂指針指示。棧底：固定端。進棧（入棧）：數據存入。棧頂指針加1。出棧（退棧）：數據讀出，棧頂指針減1。空棧：當棧中沒有元素時，稱棧為空棧。亦稱為后進先出表（LIFO），亦稱下推表。結論：后進先出（LastInFirstOut），簡稱為LIFO線性表。舉例1：家里吃飯的碗，通常在洗干凈后一個一個地落在一起存放，在使用時，若一個一個地拿，一定最先拿走最上面的那只碗，而最后拿出最下面的那只碗。舉例2：在建筑工地上，使用的磚塊從底往上一層一層地碼放，在使用時，將從最上面一層一層地拿取。因此，棧結構的基本操作有以下五種：（1）初始化棧InitStack(S)（2）入棧Push(S,item)：將參數item中數據元素入棧S（3）出棧Pop(S,item)（4）獲取棧頂元素內容GetTop(S,item)（5）判斷棧是否為空StackEmpty(S)3.1.2棧的順序存儲棧的順序存儲結構是用一組連續的存儲單元依次存放棧中的每個數據元素，并用起始端作為棧底；用一個變量來指示當前的棧頂位置。因此，棧的順序存儲的類型定義如下所示：#defineMAX_STACK10//棧的最大數據元素數目typedefstructstack{StackEntryitem[MAX_STACK];//存放棧中數據元素的存儲單元inttop;//棧頂指針}STACK;棧的動態示意：上溢（滿棧時進行入棧運算）與下溢（空棧時進行出棧運算）問題。3.1.3棧的鏈式存儲若是棧中元素的數目變化范圍較大或不清楚棧元素的數目，就應該考慮使用鏈式存儲結構。人們將用鏈式存儲結構表示的棧稱作“鏈棧”。鏈棧通常用一個無頭結點的單鏈表表示。由于棧的插入刪除操作只能在一端進行，而對于單鏈表來說，在首端插入刪除結點要比尾端相對地容易一些，所以，我們將單鏈表的首端作為棧頂端，即將單鏈表的頭指針作為棧頂指針。棧的鏈式存儲結構在C語言中可用下列類型定義實現：typestructnode{//鏈棧的結點結構StackEntryitem;//棧的數據元素類型structnode*next;//指向后繼結點的指針}NODE;typedefstructstack{NODE*top;}STACK;3.1.4棧的應用舉例【舉例1】將從鍵盤輸入的字符序列逆置輸出比如，從鍵盤上輸入：tsetasisihT；算法將輸出：Thisisatest下面我們給出解決這個問題的完整算法。 typedefcharStackEntry; voidReverseRead() { STACKS;//定義一個棧結構S charch; InitStack(&S);//初始化棧 while((ch=getchar())!=’\n’) //從鍵盤輸入字符，直到輸入換行符為止 Push(&S,ch);//將輸入的每個字符入棧 while(!StackEmpty(S)){ //依次退棧并輸出退出的字符 Pop(&S,&ch); putchar(ch); } putchar(‘\n’); }【舉例2】十進制數值轉換成二進制使用展轉相除法將一個十進制數值轉換成二進制數值。即用該十進制數值除以2，并保留其余數；重復此操作，直到該十進制數值為0為止。最后將所有的余數反向輸出就是所對應的二進制數值。比如：(692)10=(1010110100)2。【舉例3】檢驗表達式中的括號匹配情況假設在一個算術表達式中，可以包含三種括號：圓括號“（”和“）”，方括號“[”和“]”和花括號“{”和“}”，并且這三種括號可以按任意的次序嵌套使用。比如，...[...{...}...[...]...]...[...]...(...)..。現在需要設計一個算法，用來檢驗在輸入的算術表達式中所使用括號的合法性。算術表達式中各種括號的使用規則為：出現左括號，必有相應的右括號與之匹配，并且每對括號之間可以嵌套，但不能出現交叉情況。檢驗括號是否匹配的方法可用“期待的急迫程度”這個概念描述。而這個處理過程恰與棧的特點相吻合。由此，在算法中設置一個棧。我們可以利用一個棧結構保存每個出現的左括號，當遇到右括號時，從棧中彈出左括號，檢驗匹配情況。在檢驗過程中，若遇到以下幾種情況之一，就可以得出括號不匹配的結論。（1）當遇到某一個右括號時，棧已空，說明到目前為止，右括號多于左括號；（2）從棧中彈出的左括號與當前檢驗的右括號類型不同，說明出現了括號交叉情況；（3）算術表達式輸入完畢，但棧中還有沒有匹配的左括號，說明左括號多于右括號。因此，在算法的開始和結束時，棧都應該是空的。P53-54:解決這個問題的完整算法。第四講課題名稱：第二章棧和隊列 第3節隊列 第4節隊列的應用舉例教學目標： 1、使學生了解隊列的表示和實現； 2、使學生了解隊列的應用。教學重點和難點：隊列的理解主要教學方法和手段：多媒體課件講授教學課時：2課時課的類型：講授課教學內容：第三節3.3.1隊列的定義隊列特殊性在于限定插入在線性表的一端進行，刪除在線性表的另外一端進行。如圖所示： 隊頭 隊尾3.3出隊：隊頭，刪除端，前端，front，front+1入隊：隊尾，插入端，后端，rear，rear+1插入端和刪除端都是浮動的。通常我們將插入端稱為隊尾，用一個“隊尾指針”rear指示；而刪除端被稱為隊頭，用一個“隊頭指針”front指示。結論：先進先出（FirstInFirstOut），簡稱為FIFO線性表。舉例1：到醫院看病，首先需要到掛號處掛號，然后，按號碼順序救診。舉例2：乘坐公共汽車，應該在車站排隊，車來后，按順序上車。舉例3：在Windows這類多任務的操作系統環境中，每個應用程序響應一系列的“消息”，像用戶點擊鼠標；拖動窗口這些操作都會導致向應用程序發送消息。為此，系統將為每個應用程序創建一個隊列，用來存放發送給該應用程序的所有消息，應用程序的處理過程就是不斷地從隊列中讀取消息，并依次給予響應。下面我們給出隊列結構的基本操作：（1）初始化隊列InitQueue(Q)（2）入隊EnQueue(Q,e):rear+1（3）出隊DeQueue(Q,e):front+1（4）獲取隊頭元素內容GetHead(Q,e)（5）判斷隊列是否為空QueueEmpty(Q)其他基本操作參看P46-473.3.3隊列的鏈式存儲在用鏈式存儲結構表示隊列時，需要設置隊頭指針和隊尾指針，以便指示隊頭結點和隊尾結點。為了操作方便，我們也給隊列添加一個頭結點，并令頭指針指向頭結點。由此，空的鏈隊列的判決條件為頭指針和尾指針均指向頭結點。下面是在C語言中，實現隊列鏈式存儲結構的類型定義：typestructnode{//鏈式隊列的結點結構QElemTypedata;//隊列的數據元素類型structQNode*next;//指向后繼結點的指針}Qnode,*QueuePtr;typedefstructqueue{//鏈式隊列QueuePtr*front;//隊頭指針QueuePtr*rear;//隊尾指針}LinkQueue;假設將要入隊的新結點s已被創建。入隊需要執行下面三條語句：s->next=NULL;//\新結點s的next域為空rear->next=s;//原尾指針指向的結點的next域指向srear=s;//尾指針指向s下面我們給出鏈式隊列的基本操作算法。（1）初始化隊列Q：創建頭結點并將頭指針與尾指針指向該結點voidInitQueue(LinkQueue*Q){Q->front=(QNode*)malloc(sizeof(QNode));if(Q->front==NULL)exit(ERROR);Q->rear=Q->front;Q.front.->next=NULL;}（2）入隊voidEnQueue(LinkQueue*Q,QElemTypee){s=(QNode*)malloc(sizeof(QNode));if(!s)exit(ERROR);s->data=e;//以上三句為創建新結點ss->next=NULL;Q->rear->next=s;Q->rear=s;//以上三句為s入列操作}（3）出隊voidDeQueue(LinkQueue*Q,QElemType*e){if(QueueEmpty(*Q))exit(ERROR);else{*e=Q->front->next->data;s=Q->front->next;Q->front->next=s->next;//修改指針free(s);}}（4）獲取隊頭元素內容voidGetHead(LinkQueueQ,QElemType*e){if(QueueEmpty(Q))exit(ERROR);else*e=Q->front->next->data;}（5）判斷隊列Q是否為空intQueueEmpty(LinkQueueQ){if(Q->front==Q->rear)returnTRUE；elsereturnFALSE;}3.3.4隊列的順序存儲和順序棧類似，在隊列的順序存儲結構中，除了用一組地址連續的存儲單元依次存放從隊列頭到隊列尾的元素之外，尚需附設兩個指針front和rear分別指示隊列頭元素和尾元素的位置。隊列的順序存儲結構如下圖所示：問題1：當隊空時，隊頭和隊尾指針都為-1，隊列將處于下圖所示的狀態：此時若進行入隊操作，就需要讓隊頭和隊尾指針都增1，再將新數據元素放入該位置。也就是說，這樣設置隊頭、隊尾指針位置，在進行入隊操作時，空隊與非空隊狀態所需要執行的操作不完全一樣。解決方法：在算法中，需要對這兩種情況加以區分，這勢必增加了算法的復雜性。因此，人們設想了一種解決方法，即讓隊頭指針指向隊列真正隊頭元素的前一個位置，如下圖所示。問題2：由于順序存儲結構的存儲空間屬于靜態分配，所以，在添加數據元素時，可能會出現沒有剩余單元的情況。對于隊列來說，這一點又有它的特殊性。如下圖所示的隊列。 即所謂“假溢出”現象。解決方法：將存儲隊列元素的一維數組首尾相接，形成一個環狀。我們將這種形式表示的隊列稱之為循環隊列。假設為隊列開辟的數組單元數目為MAX_QUEUE，在C語言中，它的下標在0~MAX_QUEUE-1之間，若增加隊頭或隊尾指針，可以利用取模運算（一個整數數值整除以另一個整數數值的余數）實現。如下所示：front=(front+1)%MAX_QUEUE；rear=(rear+1)%MAX_QUEUE；當front或rear為MAXQUEUE-1時，上述兩個公式計算的結果就為0。這樣，就使得指針自動由后面轉到前面，形成循環的效果。各項基本操作算法。（1）初始化隊列QvoidInitQueue(QUEUE*Q){Q.base=(QElemType*)malloc(MAX_QUEUE*sizeof(QElemType));if(!Q.base)exit(OVERFLOW);Q->front=-1;Q->rear=-1;}（2）入隊溢出判斷voidEnQueue(QUEUE*Q,QElemTypee){if((Q->rear+1)%MAX_QUEUE==Q->front)exit(OVERFLOW);else{Q->rear=(Q->rear+1)%MAX_QUEUE;Q.base[Q->rear]=e;}}3）出隊voidDeQueue(QUEUE*Q,QElemType*e){if(QueueEmpty(*Q))exit(“Queueisempty.”);else{Q->front=(Q->front+1)%MAX_QUEUE;*e=Q.base[Q->front];}}（4）獲取隊頭元素內容voidGetFront(QUEUEQ,QElemType*e){if(QueueEmpty(Q))exit(“Queueisempty.”);else*e=Q.base[(Q.front+1)%MAX_QUEUE];}（5）判斷隊列Q是否為空intQueueEmpty(QueueQ){if(Q.front==Q.rear)returnTRUE;elsereturnFALSE;}第四節【舉例1】汽車加油站。隨著城市里汽車數量的急速增長，汽車加油站也漸漸多了起來。通常汽車加油站的結構基本上是：入口和出口為單行道，加油車道可能有若干條。每輛車加油都要經過三段路程，第一段是在入口處排隊等候進入加油車道；第二段是在加油車道排隊等候加油；第三段是進入出口處排隊等候離開。實際上，這三段都是隊列結構。若用算法模擬這個過程，就需要設置加油車道隊列3個和2個出口車道和入口車道隊列。【舉例2】模擬打印機緩沖區。在主機將數據輸出到打印機時，會出現主機速度與打印機的打印速度不匹配的問題。這時主機就要停下來等待打印機。顯然，這樣會降低主機的使用效率。為此人們設想了一種辦法：為打印機設置一個打印數據緩沖區，當主機需要打印數據時，先將數據依次寫入這個緩沖區，寫滿后主機轉去做其他的事情，而打印機就從緩沖區中按照先進先出的原則依次讀取數據并打印，這樣做即保證了打印數據的正確性，又提高了主機的使用效率。由此可見，打印機緩沖區實際上就是一個隊列結構。【舉例3】CPU分時系統在一個帶有多個終端的計算機系統中，同時有多個用戶需要使用CPU運行各自的應用程序，它們分別通過各自的終端向操作系統提出使用CPU的請求，操作系統通常按照每個請求在時間上的先后順序，將它們排成一個隊列，每次把CPU分配給當前隊首的請求用戶，即將該用戶的應用程序投入運行，當該程序運行完畢或用完規定的時間片后，操作系統再將CPU分配給新的隊首請求用戶，這樣即可以滿足每個用戶的請求，又可以使CPU正常工作。【舉例4】農夫過河問題一個農夫帶著一只狼、一只羊和一棵白菜，身處河的南岸。他要把這些東西全部運到北岸。問題是他只有一條小船，船小到只能容下他和一件物品，另外，只有農夫能撐船。顯然：狼吃羊，羊吃白菜，狼不吃白菜。請問：農夫采取什么方案才能將所有的東西運過河呢？求解這個問題的最簡單的方法是一步步進行試探，每一步都搜索所有可能的選擇，對前一步合適的選擇再考慮下一步的各種方案。用計算機實現上述求解的搜索過程可以采用兩種不同的策略。一種是廣度優先搜索：依賴的數據結構是隊列。一種是深度優先搜索：依賴的數據結構是棧。廣度優先的含義是：在搜索過程中，總是首先搜索下面一步的所有可能狀態，然后再進一步考慮更后面的各種情況。搜索到的下面一步的所有可能狀態，放在隊列里，然后順序取出來對其分別進行處理，處理過程中再把下一步的狀態放在隊列里……。由于先進先出原則，前一步情況處理完后，才開始后面一步各情況的處理。下面是具體解決方案。首先選擇一個對問題中每個角色的位置進行描述的方法。用四位二進制數分別順序表示農夫、狼、白菜、羊的位置：0表示在南岸；1表示在北岸。如：0101表示農夫和白菜在南岸，狼和羊在北岸。此時是否為一安全狀態？農夫過河問題即為從0000到1111狀態的動作序列問題。下圖標出了送入隊列的各個狀態（位置分布）和搜索過程中經歷結點的順序編號。請注意廣度優先搜索法在面臨多個選擇時采用怎樣的訪問順序。即從初始狀態0到最終狀態15的動作序列為：農夫把羊帶到北岸；農夫獨自回到南岸；農夫把白菜帶到北岸；農夫帶羊返回南岸；農夫把狼帶到北岸；農夫獨自返回南岸；農夫把羊帶到北岸。【舉例5】離散事件模擬假設某銀行有四個窗口對外接待客戶。由于每個窗口在某個時刻只能接待一個客戶，因此在客戶人數眾多時需在每個窗口前順次排隊，對于剛進入銀行的客戶，如果某個窗口的業務員正空閑，則可上前辦理業務，反之，若四個窗口均有客戶，他會排在人數最少的隊伍后面。現在需要編制一個程序以模擬銀行的這種業務活動并計算一天中客戶在銀行逗留的平均時間。逗留：指到達與離開的時間差。逗留的平均時間=所有客戶逗留時間總和/客戶數。事件：稱客戶到達銀行和離開銀行這兩個時刻發生的事情為“事件”。（到達事件、離開事件）整個模擬程序將按事件發生的先后順序進行處理，這樣一種模擬程序稱做事件驅動模擬。下面討論模擬程序的實現。首先討論模擬程序中需要的數據結構及其操作。1、處理的主要對象是“事件”。事件主要信息是事件類型和事件發生的時刻。客戶到達事件：隨客戶到來自然形成客戶離開事件：客戶事務所需時間與等待時間決定由于程序驅動是按事件發生時刻的先后順序進行，則事件表應是有序表，其主要操作是插入和刪除事件。2、模擬程序中需要的另一種數據結構是表示客戶排隊的隊列。四個窗口à四個隊列。隊列中有關客戶的主要信息是客戶到達的時刻和客戶辦理事務所需時間。每個隊列中的頭客戶即為正在窗口辦理事務的客戶。（而每個頭客戶都存在一個將要驅動的客戶離開事件。）因此，在任何時刻即將發生的事件只有下列五種可能：新的客戶到達；1號窗口客戶離開；2號窗口客戶離開；3號窗口客戶離開；4號窗口客戶離開。從以上分析，這個模擬程序只需要兩種數據結構：有序鏈表和隊列。有序鏈表用于表達事件；隊列用于表達客戶排隊狀態。3、兩個主要操作步驟的實現：（1）新客戶到達事件的處理。在實際的銀行中，客戶到達的時刻及其辦理事務所需時間都是隨機的，在模擬程序中可用隨機數來代替。隨機數：其一為此時刻到達的客戶辦理事務所需時間durtime；其二為下一客戶將到達的時間間隔intertime。（則下一客戶到達時刻為occurtime+intertime）。所以：應產生一個新的客戶到達事件插入事件表；剛到達的客戶則應插入到當前所含元素最少的隊列中；若該隊列在插入前為空，則還產生一個客戶離開事件插入事件表。（2）客戶離開事件的處理：首先計算該客戶在銀行逗留的時間；然后從隊列中刪除該客戶后查看隊列是否為空；若不空，則設定一個新的隊頭客戶離開事件。第五講課題名稱：第三章串 第1節串的邏輯結構 第2節串的表示和實現教學目標： 1、使學生了解串的概念； 2、使學生了解串的表示和實現。教學重點和難點：串的理解主要教學方法和手段：多媒體課件講授教學課時：2課時課的類型：講授課教學內容：第一節3.1.1串是由零個或多個字符組成的有限序列。它是一種在數據元素的組成上具有一定約束條件的線性表，即要求組成線性表的所有數據元素都是字符，所以，人們經常又這樣定義串：串是一個有窮字符序列。串一般記作：s=‘a1a2...an’(n30)其中，s是串的名稱，用單引號或雙引號括起來的字符序列是串的值；ai可以是字母、數字或其他字符；串中字符的數目n被稱作串的長度。當n=0時，串中沒有任何字符，其串的長度為0，通常被稱為空串?。如：s1=‘’而：s2=‘’與之不同。s1中沒有字符，是一個空串；而s2中有兩個空格字符，它的長度等于2，它是由空格字符組成的串，一般稱此為空格串。相關概念：子串、主串：串中任意連續的字符組成的子序列被稱為該串的子串。包含子串的串又被稱為該子串的主串。例如，有下列四個串a，b，c，d：a=“WelcometoBeijing”b=“Welcome”c=“Bei”d=“welcometo”?子串的位置：子串在主串中第一次出現的第一個字符的位置。兩個串相等：兩個串的長度相等，并且各個對應的字符也都相同。例如，有下列四個串a，b，c，d：a=“program”b=“Program”c=“pro”d=“program”串的邏輯結構與線性表極為相似，區別僅在于串的數據對象約束為字符集。即串中的每一個數據元素僅由一個字符組成。然而，串的基本操作和線性表有很大區別。線性表的操作大多以“單個元素”作為操作對象。如：在線性表中查找某個元素、求取某個數據元素、在某個位置上插入一個元素和刪除一個元素…………串的基本操作通常以“串的整體”作為操作對象。如：在串中查找某個子串、求取一個子串、在串的某個位置上插入一個子串以及刪除一個子串…………4.1.2串的基本操作：（1）創建串StrAssign(T,chars)：串賦值。即創建串T，并將chars的內容賦予它。即生成一個值等于chars的串T。（2）判斷串是否為空StrEmpty(S)（3）計算串長度StrLength(S)（4）串連接Concat(T，S1，S2)：將串S2接在串S1后構成一個新串T（5）求子串SubString(sub,S,pos,len)：將串S中從第pos個字符開始的連續len個字符組成的新子串賦給sub串。（6）串的定位Index(S,T)：即求串T在S中位置。“串的模式匹配”S稱為主串；T稱為子串或模式串。（7）串復制strCopy(T,S)：串S存在，復制得串T。（8）串比較StrCompare(S,T):如果S>T則返回值>0；如果S=T則返回值=0；如果S<T則返回值<0。（9）串清空ClearString(S)：將串清空為空串。（10）串銷毀DestroyString(s):與串清除之區別。以上五種黃色字體操作為串類型的最小操作子集。即：這些操作不可能利用其他串操作來實現，但是其他串操作均可在這個最小操作子集上實現。（串清除與串銷毀除外）如：將s2串插入到串s1的第i個字符后面。SubString(s3,s1,1,i);SubString(s4,s1,i+1,Length(s1)-i);Concat(s3,s2);Concat(s3,s4);StrAssign(s1,s3);再如：刪除串s中第i個字符開始的連續j個字符。SubString(s1,s,1,i-1);SubString(s2,s,i+j,Length(s)-i-j+1);Concat(s1,s2);StrAssign(s,s1);再如：Index(s1，s2，pos)串的定位函數的實現。可利用判等（串比較）、求串長和求子串等操作實現之。算法的基本思想是：在主串s1中取從第i（i的初值為pos）個字符起、長度和串s2相等的子串和串s2比較；若相等，則求得函數值為i，否則i值增1直至串s1中不存在和串s2相等的子串為止。作業：P764.44.54.6第二節4.2.1順序存儲結構串的順序存儲結構與線性表的順序存儲類似，用一組連續的存儲單元依次存儲串中的字符序列。在C語言中，有兩種實現方式：1.第一種稱為“定長順序存儲結構”是事先定義字符串的最大長度，字符串存儲在一個定長的存儲區中。類型定義如下所示：#defineMAX_STRING255//用戶可在255以內定義最大串長typedefunsignedcharSString[MAX_STRING];//0號單元存放串的長度，字符從1號單元開始存放說明：1、串的實際長度可在這予定義長度的范圍內隨意。超過予定義長度的串值則被舍去，稱之為“截斷”。2、對串長有兩種表示方法：（1）如上述定義描述的一樣，以下標為0的數組分量存放串的實際長度。（2）在串值后面加一個不計入串長的結束標記字符。如\0。此時的串長為隱含值，顯然不便于進行某些串操作。在這種存儲結構表示時如何實現串的操作。下面以串聯接和求子串為例討論之。1、串聯接Concat(s1,s2)聯接后串s1的值的后一段和串s2的值相等，則只要進行相應的“串值復制”操作即可，只是需按前述約定，對超長部分實施“截斷”操作。基于串s1和串s2長度的不同情況，串值的產生可能有以下三種情況：(1)s1[0]+s2[0]<=MAX_STRING得到的新串是正確的結果。(2)s1[0]<MAX_STRING而s1[0]+s2[0]>MAX_STRING則將串s2的一部分截斷，得到的串只是包含s2的一個子串。(3)s1[0]=MAX_STRING則得到的串并非聯接結果。算法見P63-64。2、求子串SubString(s1,s2,start,len)求子串的過程即為復制字符序列的過程，將串s2中從第start個字符開始長度為len的字符序列復制到串s1中。顯然，本操作不會有需截斷的情況，但是有可能產生用戶給出的參數不符合操作的初始條件，當參數非法時，返回ERROR。算法見P64。總結：1、綜上兩個操作可見，在順序存儲結構中，實現串操作的原操作為“字符序列的復制”。2、另一操作特點是，如果在操作中出現串值序列的長度超過上界MAX_STRING時，約定用截尾法處理。這種情況不僅在求聯接串時可能發生，在串的其他操作中，如插入、置換等也可能發生。克服這種弊端，唯有不限定串長的最大長度，即動態分配串值的存儲空間。2.第二種稱為“堆分配存儲”。是在程序執行過程中，利用標準函數malloc和free動態地分配或釋放存儲字符串的存儲單元，并以一個特殊的字符作為字符串的結束標志，它的好處在于：可以根據具體情況，靈活地申請適當數目的存儲空間，從而提高存儲資源的利用率。類型定義如下所示：typedefstruct{char*ch;//若是非空串，則按串長分配存儲區，否則*ch為NULLintlength;//串長度}HString;這種存儲結構表示時的串操作仍是基于“字符序列的復制”進行的。如：串復制StrCopy(&T,S)：若串T已存在，則先釋放串T所占空間，當串S不空時，首先為串T分配大小和串S長度相等的存儲空間，然后將串S的值復制到串T中。串插入StrInsert(&S,pos,T)：為串S重新分配大小等于串S和串T長度之和的存儲空間，然后進行串值復制。不同的定義形式，算法中的處理也略有不同。下面我們給出在堆分配存儲方式下串的幾個基本操作的算法。（1）串的賦值StatusStrAssign(HString*s,char*chars){if(s->ch)free(s->ch);//若s已經存在，將它占據的空間釋放掉for(len=0,c=chars;ch;len++,c++);//求chars串的長度if(!len){//空串s->ch=(char*)malloc(sizeof(char));s->ch[0]=’\0’;s->length=0;}else{s->ch=(char*)malloc((len+1)*sizeof(char));//分配空間if(!s->ch)returnERROR;s->ch[0..len]=chars[0..len];//對應的字符賦值,包括串結束標志s->length=len;//賦予字符串長度}returnOK;}2）判斷串是否為空intStrEmpty(HStrings){if(!s.length)returnTRUE;elsereturnFALSE;}（3）求串的長度intStrLength(HStrings){returns.length;}4）串連接intConcat(HString*s1,HString*s2){HStrings;StrAssign(&s,s1->ch);//將s1原來的內容保留在s中len=StrLength(s1)+StrLength(s2);//計算s1和s2的長度之和free(s1->ch);//釋放s1原來占據的空間s1->ch=(char*)malloc((len+1)*sizeof(char));//重新為s1分配空間if(!s1)returnERROR;else{//連接兩個串的內容s1->ch[0..StrLength(s)-1]=s->ch[0..StrLength(s)-1)];s1->ch[StrLength(s)..len+1]=s2->ch[0..StrLength(s2)];s1->length=len;free(s->ch);//釋放為臨時串s分配的空間returnOK;}}（5）求子串StatusSubString(HString*s1,HString*s2,intstart,intlen){len2=StrLength(s2);//計算s2的長度if(start<1||start>len2||len2<=0||len>len2-start+1){//判斷start和len的合理性，如果不合理則返回空串s1s1->ch=(char*)malloc(sizoef(char));s1->ch[0]=’\0’;s1->length=0;returnERROR;}s1->ch=(char*)malloc((len+1)*sizeof(char));if(!s1.ch)returnERROR;s1->ch[0..len-1]=s2.ch[start-1..start+len-2];s1->ch[len]=’\0’;//串尾s1->length=len;returnOK;}（6）串的定位**(串的模式匹配，即求子串s2中s1中的位置）intIndex(HStrings1,HStrings2){len1=StrLength(s1);len2=StrLength(s2);//計算s1和s2的長度i=0;j=0;//設置兩個掃描指針while(i<len1&&j<len2){if(s1.ch[i]==s2.ch[j]){i++;j++;}else{i=i-j+1;j=0;}//對應字符不相等時，重新比較}if(j==len2)returni-len2+1;//找到s2在s1中的位置elsereturn0;}//P72圖4.24.2.2鏈式存儲結構由于串結構中每個數據元素為一個字符，所以最直接的鏈式存儲結構是每個結點的數據域存放一個字符。優點是操作方便；不足之處是存儲密度較低。所謂存儲密度為： 由于串中的字符個數不一定是每個結點存放字符個數的整倍數，所以，需要在最后一個結點的空缺位置上填充特殊的字符。這種存儲形式優點是存儲密度高于結點大小為1的存儲形式；不足之處是做插入、刪除字符的操作時，可能會引起結點之間字符的移動，算法實現起來比較復雜。P68塊鏈存儲的類型定義。作業：P774.74.8第五講課題名稱：第四章數組和廣義表 第1節數組的定義數組的順序表示和實現矩陣的壓縮存儲教學目標： 1、使學生了解數組和矩陣的概念； 2、使學生了解數組和矩陣的表示和實現。教學重點和難點：數組的理解主要教學方法和手段：多媒體課件講授教學課時：2課時課的類型：講授課教學內容：第一節4.1數組的定義1、數組是我們很熟悉的一種數據結構，它可以看作線性表的推廣。數組作為一種數據結構其特點是結構中的元素本身可以是具有某種結構的數據，但屬于同一數據類型，比如：一維數組可以看作一個線性表，二維數組可以看作“數據元素是一維數組”的一維數組，三維數組可以看作“數據元素是二維數組”的一維數組，依此類推。2、由于數組中各元素具有統一的類型，并且數組元素的下標一般具有固定的上界和下界，因此，數組的處理比其它復雜的結構更為簡單。多維數組是一維數組的推廣。例如，二維數組A：AAm×n=a11a12…aa21a22…a…………am1am2…amn3、二維數組A可以看成是由m個行向量組成的向量，也可以看成是n個列向量組成的向量。4、數組一旦被定義，它的維數和維界就不再改變。因此，除了結構的初始化和銷毀之外，數組只有存取元素和修改元素值的操作。第二節4．2.1數組順序存放原因1、由于計算機的內存結構是一維的，因此用一維內存來表示多維數組，就必須按某種次序將數組元素排成一列序列，然后將這個線性序列存放在存儲器中。2、數組一旦建立，結構中的元素個數和元素間的關系就不再發生變化。因此，一般采用順序存儲的方法來表示數組。4.2.2數組存放1、行優先順序或以行為主序存儲方式：將數組元素按行排列，第i+1個行向量緊接在第i個行向量后面。以二維數組為例，按行優先順序存儲的線性序列為：a11,a12,…,a1n,a21,a22,…a2n,……,am1,am2,…,amn在PASCAL、C等語言中，數組就是按行優先順序存儲的。AAm×n=a11a12…aa21a22…a…………am1am2…amn2、行優先順序——先排最右的下標，從右到左，最后排最左下標。列優先順序——先排最左下標，從右向左，最后排最左下標。例如：三維數組Am*n*p以行優先方式順序存儲，則LOC(aijk)=LOC(a111)+[(i-1)*m*n+(j-1)*n+(k-1)]*d4.2.3數組存儲的特點只要知道開始結點的存放地址（即基地址）、維數和每維的上、下界，以及每個數組元素所占用的單元數，就可以將數組元素的存放地址表示為其下標的線性函數。因此，數組中的任一元素可以在相同的時間內存取，即順序存儲的數組是一個隨機存取結構。第三節4.3.1相關概念1、壓縮存儲：為多個值相同的非零元素只分配一個存儲空間；對零元素不分配空間。2、特殊矩陣：非零元素按照一定的規律分布。常見的特殊矩陣有對稱矩陣、三角矩陣、對角矩陣等。對稱矩陣：元素的值按照主對角線對稱a1a1,1a1,2…a1,a2,1a2,2…a2,……ai,j…an,1an,2…an,naij=aji12341234213433144441對稱矩陣3、三角矩陣：上(下)三角矩陣是指矩陣的下（上）三角（不包括對角線）中的元素均為常數或零的n階矩陣，即非零元素的分布在矩陣中呈現為三角形。例如：一個4*4的三角矩陣。188818882188331844411234912349134991499914、上述各種特殊矩陣，其非零元素的分布都是有規律的，因此總能找到一種方法將它們壓縮存儲到一維數組中，并且一般都能找到矩陣中的元素與該一維數組元素的對應關系，通過這個關系，仍能對矩陣的元素進行隨機存取。4.3.2稀疏矩陣定義：簡單說，設矩陣A中有s個非零元素，若s遠遠小于矩陣元素的總數（即s<<m×n），則稱A為稀疏矩陣。設在矩陣A中，有s個非零元素。令e=s/(m*n)，稱e為矩陣的稀疏因子。通常認為e≤0.05時稱之為稀疏矩陣。2、存儲：在存儲稀疏矩陣時，由于非零元素的分布一般是沒有規律的，因此在存儲非零元素的同時，還必須同時記下它所在的行和列的位置（i,j)。反之，一個三元組(i,j,aij)惟一確定了矩陣A的一個非零元。因此，稀疏矩陣可由表示非零元的三元組及其行列數唯一確定。假設以順序存儲結構來表示三元組表，則可得到稀疏矩陣的一種壓縮存儲方法——三元組順序表。#definemaxsize10000typedefintdatatype;typedefstruct{inti,j;datatypev;}triple;/*三元組*/typedefstruct{tripledata[maxsize];intm,n,t;}tripletable;第六講課題名稱：第四章數組和廣義表 第4節廣義表的定義 第5節廣義表的存儲結構教學目標： 1、使學生了解廣義表的概念； 2、使學生掌握廣義表的存儲結構。教學重點和難點：、廣義表的應用主要教學方法和手段：多媒體課件講授教學課時：2課時課的類型：講授課教學內容：第一節4.4廣義表是線性表的推廣L=(a1,a2,...,an),n≥0,ai可以是單元素，也可以是一個表。例如：A=()B=(e)C=(a,(b,c,d))D=(A,B,C)E=(a,E)廣義表的長度廣義表的深度非空廣義表表頭(Head)：第一個元素表尾(Tail)：除第一個元素外其余元素構成的表鏈表存儲C=(a,(b,c,d))D=(A,B,C)E=(a,E)第二節m元多項式的表示P(x,y,z)=x10y3z2+2x6y3z2+3x5y2z2+x4y4z+6x3y4z+2yz+15=(x10y3+2x6y3+3x5y2)z2+(x4y4+6x3y4+2y)z+15=Az2+Bz+15A(x,y)=x10y3+2x6y3+3x5y2=(x10+2x6)y3+3x5y2=Cy3+Dy2B(x,y)=x4y4+6x3y4+2y=(x4+6x3)y4+2y=Ey4+Fy

第七講課題名稱：第六章樹和二叉樹第1節樹的定義和基本術語第2節二叉樹教學目標： 1、使學生了解樹的定義和基本術語等主要內容； 2、使學生了解二叉樹的存儲結構。教學重點和難點：二叉樹的定義、基本運算以及存儲結構。主要教學方法和手段：多媒體課件講授教學課時：2課時課的類型：講授課教學內容：第一節樹的定義和基本術語1、樹：是n（n≥0）個結點的有限集。當n=0時，稱為空樹；在任意一棵非空樹中滿足如下條件：(1)有且僅有一個特定的稱為根（root）的結點，它沒有直接前驅，但有零個或多個直接后繼。(2)當n>1時，其余n-1個結點可以劃分成m（m>0）個互不相交的有限集T1，T2，T3，…，Tm，其中Ti又是一棵樹，稱為根root的子樹。每棵子樹的根結點有且僅有一個直接前驅，但有零個或多個直接后繼。由此可以看出，樹的定義是遞歸。JJIACBDHGFEKLM2、樹的結點：包含一個數據元素及若干指向子樹的分支；結點的度：節點擁有的子樹數（結點的孩子數目）；終端結點（葉子）：度為0的結點；非終端結點（分支結點）：度不為0的結點；結點的層次：樹中根結點的層次為1，根結點子樹的根為第2層，以此類推；樹的度：樹中所有結點度的最大值；樹的深度：樹中所有結點層次的最大值；孩子結點：結點的子樹的根稱為該結點的孩子；父結點：B是A的孩子，則A是B的父親；兄弟結點：同一雙親的孩子結點；堂兄弟結點：其父結點在同一層上的結點；祖先結點：從根到該結點所經分支上的所有結點；子孫結點：以某結點為根的子樹中任一結點都稱為該結點的子孫。3、有序樹和無序樹：在樹中，如果各子樹Ti是按照一定的次序從左向右安排的，且相對次序是不能隨意改變的，則稱為有序樹，否則稱為無序樹。森林：m（m≥0）棵互不相交的樹的集合。將一棵非空樹的根結點刪去，樹就變成一個森林；反之，給m棵獨立的樹增加一個根結點，并把這m棵樹作為該結點的子樹，森林就變成一棵樹。第二節二叉樹6.2.1二叉樹的定義二叉樹是由n(n>=0)個結點的有限集合構成，此集合或者為空集，或者由一個根結點及兩棵互不相交的左右子樹組成，并且左右子樹都是二叉樹。二叉樹可以是空集合，根可以有空的左子樹或空的右子樹。二叉樹不是樹的特殊情況。二叉樹結點的子樹要區分左子樹和右子樹，即使只有一棵子樹也要進行區分，說明它是左子樹，還是右子樹。這是二叉樹與樹的最主要的差別。二叉樹的5種基本形態其中：(c)和（d）是不同的兩棵二叉樹。(a)(a)空二叉樹AABABACB(b)只有根的二叉樹(c)根和左子樹(d)根和右子樹(e)根和左右子樹二叉樹的5種基本形式6.2.2二叉樹的性質1、性質1：在二叉樹的第i層上至多有2i-1個結點證明：用數學歸納法1)當i=1時，整個二叉樹只有一根結點，此時2i-1=20=1，結論成立。2)設i=k時結論成立，即第k層上結點總數最多為2k-1個。現證明當i=k+1時，結論成立：因為二叉樹中每個結點的度最大為2，則第k+1層的結點總數最多為第k層上結點最大數的2倍，即2×2k-1=2(k+1)-1，故結論成立。2、性質2：深度為k的二叉樹至多有2k-1個結點證明：因為深度為k的二叉樹，其結點總數的最大值是將二叉樹每層上結點的最大值相加，所以深度為k的二叉樹的結點總數至多為深度為k的m叉樹至多有個結點。3、性質3：任何一個二叉樹中度為2的結點數目(n2)比度為0的結點數目(n0)少1，即n2＝n0-1。證明：設二叉樹中結點總數為n，n1為二叉樹中度為1的結點總數，設二叉樹中分支數目為B。①n=n0+n1+n2除根結點外，每個結點均對應一個進入它的分支：②n=B+1二叉樹中的分支都是由度為1和度為2的結點發出③B=n1+2n24、滿二叉樹深度為k且有2k-1個結點的二叉樹。在滿二叉樹中，每層結點都是滿的，即每層結點都具有最大結點數。滿二叉樹的順序表示，即從二叉樹的根開始，層間從上到下，層內從左到右，逐層進行編號（1，2，…，n）。高度為高度為3的滿二叉樹5、完全二叉樹深度為k，結點數為n的二叉樹，如果其結點1~n的位置序號分別與滿二叉樹的結點1~n的位置序號一一對應，則為完全二叉樹，滿二叉樹必為完全二叉樹，而完全二叉樹不一定是滿二叉樹。6、性質4：一個有n個結點的完全二叉樹的深度為?log2n?+1或élog2(n+1)ù證明：設n個結點的完全二叉樹的深度為k，根據性質2有2k-1-1＜n≤2k-1可得2k-1≤n＜2k，即k-1≤log2n＜k因為k是整數，所以k-1=?log2n?，k=?log2n?+1,故結論成立。2k-1＜n+1≤2k→k-1＜log2(n+1)≤k→k=élog2(n+1)ù7、性質5：完全二叉樹中的某結點編號為i，則1)若該結點有左孩子，則左孩編號為2i2）若該結點有右孩子，則右孩子結點編號為2i+13）若該結點有雙親，則雙親結點編號為?i/2?6.2.3.1二叉樹的順序存儲二叉樹的順序存儲指的是用元素在數組中的下標表示一個結點與其孩子和父結點的關系.1、完全二叉樹的順序存儲EDEDCFABABCDEF123456789101112#defineMAX_TREE_SIZE100typedefTelemTypeSqBiTree[MAX_TREE_SIZE];SqBiTreebt;2、非完全二叉樹的順序存儲EEGFCDABABCDEFG12