傳智播客C和C++與數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)講義

1、輕松入門 實戰(zhàn)應(yīng)用 傳智播客C+課程傳智播客C和C+與數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)講義 傳智掃地僧1、 數(shù)據(jù)結(jié)構(gòu)概念1.1數(shù)據(jù)結(jié)構(gòu)相關(guān)概念1.1.1疑惑1、我學(xué)完了C語言，可是現(xiàn)在感覺還是寫不出代碼。2、為什么會有各種各樣的程序存在？3、程序的本質(zhì)是什么？程序是為了具體問題而存在的 程序需要圍繞問題的解決進行設(shè)計同一個問題可以有多種解決方案如何追求程序的“性價比”？是否有可量化的方法判別程序的好壞？1.1.2數(shù)據(jù)結(jié)構(gòu)起源計算機從解決數(shù)值計算問題到解決生活中的問題現(xiàn)實生活中的問題涉及不同個體間的復(fù)雜聯(lián)系需要在計算機程序中描述生活中個體間的聯(lián)系數(shù)據(jù)結(jié)構(gòu)主要研究非數(shù)值計算程序問題中的操作對象以及它們之間的關(guān)系 不是

2、研究復(fù)雜的算法1.1.3數(shù)據(jù)結(jié)構(gòu)中的基本概念數(shù)據(jù) 程序的操作對象，用于描述客觀事物 (int a, int b,)數(shù)據(jù)的特點：可以輸入到計算機可以被計算機程序處理數(shù)據(jù)是一個抽象的概念，將其進行分類后得到程序設(shè)計語言中的類型。如：int，float，char等等數(shù)據(jù)元素：組成數(shù)據(jù)的基本單位數(shù)據(jù)項：一個數(shù)據(jù)元素由若干數(shù)據(jù)項組成數(shù)據(jù)對象 性質(zhì)相同的數(shù)據(jù)元素的集合 （比如：數(shù)組，鏈表） /友情提示，來自結(jié)構(gòu)體課堂代碼/聲明一個結(jié)構(gòu)體類型struct _MyTeacher /一種數(shù)據(jù)類型charname32;chartile32;intage;charaddr128;int main21()struct

3、 _MyTeacher t1; /數(shù)據(jù)元素struct _MyTeacher tArray30; /數(shù)據(jù)對象memset(&t1, 0, sizeof(t1);strcpy(, "name"); /數(shù)據(jù)項strcpy(t1.addr, "addr"); /數(shù)據(jù)項strcpy(t1.tile, "addr"); /數(shù)據(jù)項t1.age = 1;數(shù)據(jù)元素之間不是獨立的，存在特定的關(guān)系，這些關(guān)系即結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)指數(shù)據(jù)對象中數(shù)據(jù)元素之間的關(guān)系 如：數(shù)組中各個元素之間存在固定的線性關(guān)系 編寫一個“好”的程序之前，必須分析待處理

4、問題中各個對象的特性，以及對象之間的關(guān)系。基本概念總結(jié)：1.1.4數(shù)據(jù)的邏輯結(jié)構(gòu)指數(shù)據(jù)元素之間的邏輯關(guān)系。即從邏輯關(guān)系上描述數(shù)據(jù)，它與數(shù)據(jù)的存儲無關(guān)，是獨立于計算機的。邏輯結(jié)構(gòu)可細分為4類：1.1.5數(shù)據(jù)的物理結(jié)構(gòu)1.1.6數(shù)據(jù)的運算1.2、算法1.2.1算法概念算法是特定問題求解步驟的描述在計算機中表現(xiàn)為指令的有限序列 算法是獨立存在的一種解決問題的方法和思想。對于算法而言，語言并不重要，重要的是思想。1.2.2算法和數(shù)據(jù)結(jié)構(gòu)區(qū)別數(shù)據(jù)結(jié)構(gòu)只是靜態(tài)的描述了數(shù)據(jù)元素之間的關(guān)系高效的程序需要在數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)上設(shè)計和選擇算法=è程序=數(shù)據(jù)結(jié)構(gòu)+算法 總結(jié)：算法是為了解決實際問題而設(shè)計的數(shù)據(jù)

5、結(jié)構(gòu)是算法需要處理的問題載體數(shù)據(jù)結(jié)構(gòu)與算法相輔相成1.2.3算法特性輸入算法具有0個或多個輸入輸出算法至少有1個或多個輸出有窮性算法在有限的步驟之后會自動結(jié)束而不會無限循環(huán)確定性算法中的每一步都有確定的含義，不會出現(xiàn)二義性可行性算法的每一步都是可行的1.2.4算法效率的度量1、事后統(tǒng)計法比較不同算法對同一組輸入數(shù)據(jù)的運行處理時間缺陷 為了獲得不同算法的運行時間必須編寫相應(yīng)程序運行時間嚴重依賴硬件以及運行時的環(huán)境因素算法的測試數(shù)據(jù)的選取相當困難事后統(tǒng)計法雖然直觀，但是實施困難且缺陷多算法效率的度量事前分析估算依據(jù)統(tǒng)計的方法對算法效率進行估算影響算法效率的主要因素算法采用的策略和方法問題的輸入規(guī)模

6、編譯器所產(chǎn)生的代碼計算機執(zhí)行速度/算法最終編譯成具體的計算機指令/每一個指令，在具體的計算機上運行速度固定/通過具體的n的步驟，就可以推導(dǎo)出算法的復(fù)雜度long sum1(int n) long ret = 0; int* array = (int*)malloc(n * sizeof(int); int i = 0; for(i=0; i<n; i+) arrayi = i + 1; for(i=0; i<n; i+) ret += arrayi; free(array); return ret; long sum2(int n) long ret = 0; int i = 0;

7、 for(i=1; i<=n; i+) ret += i; return ret;long sum3(int n) long ret = 0; if( n > 0 ) ret = (1 + n) * n / 2; return ret;int main() printf("%dn", sum1(100); printf("%dn", sum2(100); printf("%dn", sum3(100); return 0;int func(int a, int len) int i = 0; int j = 0; int

8、s = 0; for(i=0; i<len; i+) n for(j=0; j<len; j+) n s += i*j; /n*n return s; /n*n注意1：判斷一個算法的效率時，往往只需要關(guān)注操作數(shù)量的最高次項，其它次要項和常數(shù)項可以忽略。注意2：在沒有特殊說明時，我們所分析的算法的時間復(fù)雜度都是指最壞時間復(fù)雜度。2、大O表示法算法效率嚴重依賴于操作(Operation)數(shù)量在判斷時首先關(guān)注操作數(shù)量的最高次項操作數(shù)量的估算可以作為時間復(fù)雜度的估算O(5) = O(1)O(2n + 1) = O(2n) = O(n) O(n2+ n + 1) = O(n2)O(3n3+1

9、) = O(3n3) = O(n3)常見時間復(fù)雜度關(guān)系3、算法的空間復(fù)雜度算法的空間復(fù)雜度通過計算算法的存儲空間實現(xiàn)S(n) = O(f(n)其中，n為問題規(guī)模，f(n)為在問題規(guī)模為n時所占用存儲空間的函數(shù)大O表示法同樣適用于算法的空間復(fù)雜度當算法執(zhí)行時所需要的空間是常數(shù)時，空間復(fù)雜度為O(1)空間與時間的策略多數(shù)情況下，算法執(zhí)行時所用的時間更令人關(guān)注如果有必要，可以通過增加空間復(fù)雜度來降低時間復(fù)雜度同理，也可以通過增加時間復(fù)雜度來降低空間復(fù)雜度練習(xí)1：分析sum1 sum2 sum3函數(shù)的空間復(fù)雜度O(4n+12) O(8)=O(1) O(4)=O(1)總結(jié)：實現(xiàn)算法時，需要分析具體問題，

10、對執(zhí)行時間和空間的要求。練習(xí)2：時間換空間 /* 問題： 在一個由自然數(shù)1-1000中某些數(shù)字所組成的數(shù)組中，每個數(shù)字可能出現(xiàn)零次或者多次。 設(shè)計一個算法，找出出現(xiàn)次數(shù)最多的數(shù)字。*/方法1： 排序，然后找出出現(xiàn)次數(shù)最多的數(shù)字方法2：void search(int a, int len) int sp1000 = 0; int i = 0; int max = 0; for(i=0; i<len; i+) int index = ai - 1; spindex+; for(i=0; i<1000; i+) if( max < spi ) max = spi; for(i=0;

11、 i<1000; i+) if( max = spi ) printf("%dn", i+1); int main() int array = 1, 1, 3, 4, 5, 6, 6, 6, 2, 3; search(array, sizeof(array)/sizeof(*array); return 0;把每個數(shù)字出現(xiàn)的次數(shù)的中間結(jié)果，緩存下來；在緩存的結(jié)果中求最大值。2、線性表2.1線性表基本概念2.1.1線性表定義線性表(List)是零個或多個數(shù)據(jù)元素的集合 線性表中的數(shù)據(jù)元素之間是有順序的線性表中的數(shù)據(jù)元素個數(shù)是有限的線性表中的數(shù)據(jù)元素的類型必須相同2.1.

12、2數(shù)學(xué)定義線性表是具有相同類型的 n（ 0）個數(shù)據(jù)元素的有限序列（a1, a2, , an）ai是表項，n 是表長度。2.1.3性質(zhì)a0為線性表的第一個元素，只有一個后繼 an為線性表的最后一個元素，只有一個前驅(qū)除a0和an外的其它元素ai，既有前驅(qū)，又有后繼線性表能夠逐項訪問和順序存取2.1.4練習(xí)下面的關(guān)系中可以用線性表描述的是A.班級中同學(xué)的友誼關(guān)系 N:NB.公司中的上下級關(guān)系 1:NC.冬天圖書館排隊占座關(guān)系 D.花名冊上名字之間的關(guān)系 1:12.2.5線性表的操作創(chuàng)建線性表銷毀線性表清空線性表將元素插入線性表將元素從線性表中刪除獲取線性表中某個位置的元素獲取線性表的長度線性表在程序

13、中表現(xiàn)為一種特殊的數(shù)據(jù)類型線性表的操作在程序中的表現(xiàn)為一組函數(shù)C語言描述=線性表的設(shè)計與實現(xiàn)ADT抽象層 數(shù)據(jù)結(jié)構(gòu)(C語言版).嚴蔚敏_吳偉民.掃描版.pdf p44頁 人生財富庫積累#ifndef _WBM_LIST_H_#define _WBM_LIST_H_typedef void List;typedef void ListNode;/創(chuàng)建并且返回一個空的線性表List* List_Create();/銷毀一個線性表listvoid List_Destroy(List* list);/將一個線性表list中的所有元素清空, 線性表回到創(chuàng)建時的初始狀態(tài)void List_Clear(Li

14、st* list);/返回一個線性表list中的所有元素個數(shù)int List_Length(List* list);/向一個線性表list的pos位置處插入新元素nodeint List_Insert(List* list, ListNode* node, int pos); /獲取一個線性表list的pos位置處的元素ListNode* List_Get(List* list, int pos);/刪除一個線性表list的pos位置處的元素 返回值為被刪除的元素，NULL表示刪除失敗ListNode* List_Delete(List* list, int pos);#endif注意:int

15、 List_Insert(List* list, ListNode* node, int pos); (重點:分離思想) 2.2線性表的順序存儲結(jié)構(gòu)2.2.1基本概念2.2.2設(shè)計與實現(xiàn)插入元素算法判斷線性表是否合法判斷插入位置是否合法把最后一個元素到插入位置的元素后移一個位置將新元素插入線性表長度加1獲取元素操作判斷線性表是否合法判斷位置是否合法直接通過數(shù)組下標的方式獲取元素刪除元素算法判斷線性表是否合法判斷刪除位置是否合法將元素取出將刪除位置后的元素分別向前移動一個位置線性表長度減1鏈表順序存儲插入算法和刪除算法2.2.3優(yōu)點和缺點優(yōu)點：無需為線性表中的邏輯關(guān)系增加額外的空間可以快速的獲取

16、表中合法位置的元素缺點：插入和刪除操作需要移動大量元素當線性表長度變化較大時難以確定存儲空間的容量2.3線性表的鏈式存儲2.3.1基本概念鏈式存儲定義為了表示每個數(shù)據(jù)元素與其直接后繼元素之間的邏輯關(guān)系，每個元素除了存儲本身的信息外，還需要存儲指示其直接后繼的信息。表頭結(jié)點鏈表中的第一個結(jié)點，包含指向第一個數(shù)據(jù)元素的指針以及鏈表自身的一些信息數(shù)據(jù)結(jié)點鏈表中代表數(shù)據(jù)元素的結(jié)點，包含指向下一個數(shù)據(jù)元素的指針和數(shù)據(jù)元素的信息尾結(jié)點鏈表中的最后一個數(shù)據(jù)結(jié)點，其下一元素指針為空，表示無后繼。2.3.2鏈表技術(shù)領(lǐng)域推演2.3.2設(shè)計與實現(xiàn)鏈表鏈式存儲_api實現(xiàn)分析在C語言中可以用結(jié)構(gòu)體來定義鏈表中的指針域

17、鏈表中的表頭結(jié)點也可以用結(jié)構(gòu)體實現(xiàn)帶頭結(jié)點、位置從0的單鏈表返回鏈表中第3個位置處，元素的值LinkListNode* LinkList_Get(LinkList* list, int pos) int i = 0;TLinkList *tList = (TLinkList *)list;LinkListNode *current = NULL;LinkListNode *ret = NULL;if (list=NULL |pos<0 | pos>=tList->length)return NULL;current = (LinkListNode *)tList;for (i

18、=0; i<pos; i+)current = current->next;ret = current->next;return ret ;返回第三個位置的移動pos次以后，當前指針指向哪里？答案：指向位置2，所以需要返回 ret = current->next;備注：循環(huán)遍歷時，遍歷第1次，指向位置0遍歷第2次，指向位置1遍歷第3次，指向位置2遍歷第n次，指向位置n-1;所以如果想返回位置n的元素的值，需要怎么做 ret = current->next;此問題是：指向頭結(jié)點的指針移動n次 和 第n個元素之間的關(guān)系？刪除元素重要技術(shù)場景圖 鏈表鏈式存儲_插入鏈表鏈

19、式存儲_刪除2.3.3優(yōu)點和缺點優(yōu)點：無需一次性定制鏈表的容量 插入和刪除操作無需移動數(shù)據(jù)元素缺點：數(shù)據(jù)元素必須保存后繼元素的位置信息獲取指定數(shù)據(jù)的元素操作需要順序訪問之前的元素2.4循環(huán)鏈表2.4.1基本概念循環(huán)鏈表的定義：將單鏈表中最后一個數(shù)據(jù)元素的next指針指向第一個元素循環(huán)鏈表擁有單鏈表的所有操作創(chuàng)建鏈表銷毀鏈表獲取鏈表長度清空鏈表獲取第pos個元素操作插入元素到位置pos刪除位置pos處的元素新增功能：游標的定義在循環(huán)鏈表中可以定義一個“當前”指針，這個指針通常稱為游標，可以通過這個游標來遍歷鏈表中的所有元素。循環(huán)鏈表新操作將游標重置指向鏈表中的第一個數(shù)據(jù)元素CircleListN

20、ode* CircleList_Reset(CircleList* list);獲取當前游標指向的數(shù)據(jù)元素CircleListNode* CircleList_Current(CircleList* list);將游標移動指向到鏈表中的下一個數(shù)據(jù)元素CircleListNode* CircleList_Next(CircleList* list);直接指定刪除鏈表中的某個數(shù)據(jù)元素 CircleListNode* CircleList_DeleteNode(CircleList* list, CircleListNode* node); / 根據(jù)元素的值 刪除 元素 pk根據(jù)元素的位置 刪除 元

21、素2.4.2循環(huán)鏈表的應(yīng)用 證明循環(huán)鏈表打印兩次。 約瑟夫問題求解約瑟夫問題-循環(huán)鏈表典型應(yīng)用n 個人圍成一個圓圈，首先第 1 個人從 1 開始一個人一個人順時針報數(shù)，報到第 m 個人，令其出列。然后再從下一 個人開始從 1 順時針報數(shù)，報到第 m 個人，再令其出列，如此下去，求出列順序。大話數(shù)據(jù)結(jié)構(gòu) 3.16結(jié)尾：寫書的人，也很累；臨界點2.4.3設(shè)計與實現(xiàn)循環(huán)鏈表插入元素的分析 1） 普通插入元素（和單鏈表是一樣的）2） 尾插法（和單鏈表是一樣的，單鏈表的寫法支持尾插法；因：輔助指針向后跳length次，指向最后面那個元素） CircleList_

22、Insert(list, (CircleListNode*)&v1, CircleList_Length(list);CircleList_Insert(list, (CircleListNode*)&v1, CircleList_Length(list);3） 頭插法（要進行頭插法，需要求出尾結(jié)點，和單鏈表不一樣的地方，保證是循環(huán)鏈表）第一次插入元素時，讓游標指向0號結(jié)點CircleList_Insert(list, (CircleListNode*)&v1, 0);CircleList_Insert(list, (CircleListNode*)&v1, 0

23、);4)第一次插入元素循環(huán)鏈表插入綜合場景分析圖循環(huán)鏈表刪除結(jié)點分析1、 刪除普通結(jié)點2、 刪除頭結(jié)點（刪除0號位置處元素），需要求出尾結(jié)點2.4.4優(yōu)點和缺點優(yōu)點：功能強了。循環(huán)鏈表只是在單鏈表的基礎(chǔ)上做了一個加強循環(huán)鏈表可以完全取代單鏈表的使用循環(huán)鏈表的Next和Current操作可以高效的遍歷鏈表中的所有元素缺點：代碼復(fù)雜度提高了大話數(shù)據(jù)結(jié)構(gòu) 3.16結(jié)尾：寫書的人，也很累；臨界點2.5雙向鏈表2.5.1基本概念 請思考： 為什么需要雙向鏈表？單鏈表的結(jié)點都只有一個指向下一個結(jié)點的指針單鏈表的數(shù)據(jù)元素?zé)o法直接訪問其前驅(qū)元素逆序訪問單鏈表中的元素是極其耗時的操作

24、！len = LinkList_Length(list);for (i=len-1; len>=0; i+) /O(n)LinkListNode *p = LinkList_Get(list, i); /O(n)/訪問數(shù)據(jù)元素p中的元素/雙向鏈表的定義在單鏈表的結(jié)點中增加一個指向其前驅(qū)的pre指針雙向鏈表擁有單鏈表的所有操作創(chuàng)建鏈表銷毀鏈表獲取鏈表長度清空鏈表獲取第pos個元素操作插入元素到位置pos刪除位置pos處的元素2.5.2設(shè)計與實現(xiàn)循環(huán)鏈表一般操作插入操作插入操作異常處理插入第一個元素異常處理在0號位置處插入元素；刪除操作刪除操作異常處理 雙向鏈表的新操作獲取當前游標指向的數(shù)據(jù)

25、元素將游標重置指向鏈表中的第一個數(shù)據(jù)元素將游標移動指向到鏈表中的下一個數(shù)據(jù)元素將游標移動指向到鏈表中的上一個數(shù)據(jù)元素直接指定刪除鏈表中的某個數(shù)據(jù)元素DLinkListNode* DLinkList_DeleteNode(DLinkList* list, DLinkListNode* node);DLinkListNode* DLinkList_Reset(DLinkList* list);DLinkListNode* DLinkList_Current(DLinkList* list);DLinkListNode* DLinkList_Next(DLinkList* list);DLinkLi

26、stNode* DLinkList_Pre(DLinkList* list);/大家一定要注意：教科書不會告訴你 項目上如何用；哪些點是項目的重點；做一個企業(yè)級的財富庫，完成你人生開發(fā)經(jīng)驗的積累，是我們的學(xué)習(xí)重點，要注意！雙向鏈表重要技術(shù)場景循環(huán)鏈表插入結(jié)點技術(shù)場景循環(huán)鏈表刪除結(jié)點技術(shù)場景2.5.3優(yōu)點和缺點優(yōu)點：雙向鏈表在單鏈表的基礎(chǔ)上增加了指向前驅(qū)的指針功能上雙向鏈表可以完全取代單鏈表的使用雙向鏈表的Next，Pre和Current操作可以高效的遍歷鏈表中的所有元素缺點：代碼復(fù)雜3、棧tack和隊列queue3.1棧stack 3.1.1Stack基本概念棧是一種 特殊的線性表 棧僅能在線

27、性表的一端進行操作棧頂(Top)：允許操作的一端棧底(Bottom)：不允許操作的一端3.1.2Stack的常用操作創(chuàng)建棧銷毀棧清空棧進棧出棧獲取棧頂元素獲取棧的大小 C語言描述=棧的設(shè)計與實現(xiàn) 人生財富庫積累#ifndef _MY_STACK_H_#define _MY_STACK_H_typedef void Stack;Stack* Stack_Create();void Stack_Destroy(Stack* stack);void Stack_Clear(Stack* stack);int Stack_Push(Stack* stack, void* item);void* Sta

28、ck_Pop(Stack* stack);void* Stack_Top(Stack* stack);int Stack_Size(Stack* stack);#endif /_MY_STACK_H_3.1.3棧模型和鏈表模型關(guān)系分析3.1.4棧的順序存儲設(shè)計與實現(xiàn)基本概念設(shè)計與實現(xiàn)頭文件#ifndef _MY_SEQLIST_H_ #define _MY_SEQLIST_H_typedef void SeqList;typedef void SeqListNode;SeqList* SeqStack_Create(int capacity);void SeqStack _Destroy(Se

29、qStack * list);void SeqStack _Clear(SeqStack * list);int SeqStack _Length(SeqStack * list);int SeqStack _Capacity(SeqStack * list);int SeqStack _Insert(SeqStack * list, SeqListNode* node, int pos);SeqListNode* SeqList_Get(SeqList* list, int pos);SeqListNode* SeqList_Delete(SeqList* list, int pos);#e

30、ndif /_MY_SEQLIST_H_3.1.5棧的鏈式存儲設(shè)計與實現(xiàn)基本概念設(shè)計與實現(xiàn)頭文件#ifndef _MY_LINKSTACK_H_#define _MY_LINKSTACK_H_typedef void LinkStack;LinkStack* LinkStack_Create();void LinkStack_Destroy(LinkStack* stack);void LinkStack_Clear(LinkStack* stack);int LinkStack_Push(LinkStack* stack, void* item);void* LinkStack_Pop(Li

31、nkStack* stack);void* LinkStack_Top(LinkStack* stack);int LinkStack_Size(LinkStack* stack);#endif /_MY_LINKSTACK_H_3.1.6棧的應(yīng)用案例1：就近匹配應(yīng)用1：就近匹配 幾乎所有的編譯器都具有檢測括號是否匹配的能力如何實現(xiàn)編譯器中的符號成對檢測？#include <stdio.h> int main() int a44; int (*p)4; p = a0; return 0; 算法思路從第一個字符開始掃描當遇見普通字符時忽略，當遇見左符號時壓入棧中當遇見右符號時從棧中彈

32、出棧頂符號，并進行匹配匹配成功：繼續(xù)讀入下一個字符匹配失?。毫⒓赐Ｖ梗箦e結(jié)束：成功: 所有字符掃描完畢，且棧為空失敗：匹配失敗或所有字符掃描完畢但棧非空當需要檢測成對出現(xiàn)但又互不相鄰的事物時可以使用?！昂筮M先出”的特性棧非常適合于需要“就近匹配”的場合計算機的本質(zhì)工作就是做數(shù)學(xué)運算，那計算機可以讀入字符串“9 + (3 - 1) * 5 + 8 / 2”并計算值嗎？案例2：中綴表達式和后綴表達式應(yīng)用2：中綴 后綴計算機的本質(zhì)工作就是做數(shù)學(xué)運算，那計算機可以讀入字符串“9 + (3 - 1) * 5 + 8 / 2”并計算值嗎？后綴表達式 =？符合計算機運算波蘭科學(xué)家在20世紀50年代提出了

33、一種將運算符放在數(shù)字后面的后綴表達式對應(yīng)的，我們習(xí)慣的數(shù)學(xué)表達式叫做中綴表達式=符合人類思考習(xí)慣實例：5 + 4=> 5 4 + 1 + 2 * 3 => 1 2 3 * + 8 + ( 3 1 ) * 5 => 8 3 1 5 * + 中綴表達式符合人類的閱讀和思維習(xí)慣后綴表達式符合計算機的“運算習(xí)慣”如何將中綴表達式轉(zhuǎn)換成后綴表達式？中綴轉(zhuǎn)后綴算法：遍歷中綴表達式中的數(shù)字和符號對于數(shù)字：直接輸出對于符號：左括號：進棧 運算符號：與棧頂符號進行優(yōu)先級比較若棧頂符號優(yōu)先級低：此符合進棧 （默認棧頂若是左括號，左括號優(yōu)先級最低）若棧頂符號優(yōu)先級不低：將棧頂符號彈出并輸出，之后進

34、棧右括號：將棧頂符號彈出并輸出，直到匹配左括號遍歷結(jié)束：將棧中的所有符號彈出并輸出中綴轉(zhuǎn)后綴計算機是如何基于后綴表達式計算的？8 3 1 5 * + 遍歷后綴表達式中的數(shù)字和符號對于數(shù)字：進棧對于符號：從棧中彈出右操作數(shù)從棧中彈出左操作數(shù)根據(jù)符號進行運算將運算結(jié)果壓入棧中遍歷結(jié)束：棧中的唯一數(shù)字為計算結(jié)果棧的神奇！ 中綴表達式是人習(xí)慣的表達方式后綴表達式是計算機喜歡的表達方式通過棧可以方便的將中綴形式變換為后綴形式中綴表達式的計算過程類似程序編譯運行的過程 擴展：給你一個字符串，計算結(jié)果“1 + 2 * (66 / (2 * 3) + 7 )” 1字符串解析詞法語法分析優(yōu)先級分析 數(shù)據(jù)結(jié)構(gòu)選型

35、=棧還是樹？3.2隊列queue3.2.1queue基本概念隊列是一種特殊的線性表 隊列僅在線性表的兩端進行操作隊頭(Front)：取出數(shù)據(jù)元素的一端隊尾(Rear)：插入數(shù)據(jù)元素的一端隊列不允許在中間部位進行操作！3.2.2queue常用操作銷毀隊列清空隊列進隊列出隊列獲取隊頭元素獲取隊列的長度C語言描述=隊列的設(shè)計與實現(xiàn) 人生財富庫積累#ifndef _MY_QUEUE_H_#define _MY_QUEUE_H_typedef void Queue;Queue* Queue_Create();void Queue_Destroy(Queue* queue);void Queue_Clea

36、r(Queue* queue);int Queue_Append(Queue* queue, void* item);void* Queue_Retrieve(Queue* queue);void* Queue_Header(Queue* queue);int Queue_Length(Queue* queue);#endif /_MY_QUEUE_H_3.2.3隊列模型和鏈表模型關(guān)系分析3.2.4隊列的順序存儲設(shè)計與實現(xiàn)1基本概念隊列也是一種特殊的線性表；可以用線性表順序存儲來模擬隊列。2設(shè)計與實現(xiàn)#ifndef _MY_SEQQUEUE_H_#define _MY_SEQQUEUE_H_t

37、ypedef void SeqQueue;SeqQueue* SeqQueue_Create(int capacity);void SeqQueue_Destroy(SeqQueue* queue);void SeqQueue_Clear(SeqQueue* queue);int SeqQueue_Append(SeqQueue* queue, void* item);void* SeqQueue_Retrieve(SeqQueue* queue);void* SeqQueue_Header(SeqQueue* queue);int SeqQueue_Length(SeqQueue* queu

38、e);int SeqQueue_Capacity(SeqQueue* queue);#endif /_MY_SEQQUEUE_H_3.2.5隊列的鏈式存儲設(shè)計與實現(xiàn)1基本概念隊列也是一種特殊的線性表；可以用線性表鏈式存儲來模擬隊列的鏈式存儲。2設(shè)計與實現(xiàn)#ifndef _MY_LINKQUEUE_H_#define _MY_LINKQUEUE_H_typedef void LinkQueue;LinkQueue* LinkQueue_Create();void LinkQueue_Destroy(LinkQueue* queue);void LinkQueue_Clear(LinkQueue*

39、 queue);int LinkQueue_Append(LinkQueue* queue, void* item);void* LinkQueue_Retrieve(LinkQueue* queue);void* LinkQueue_Header(LinkQueue* queue);int LinkQueue_Length(LinkQueue* queue);#endif /_MY_LINKQUEUE_H_4、樹專題 4.1樹基本概念基礎(chǔ)講義：參考數(shù)據(jù)結(jié)構(gòu)_樹A.ppt參考數(shù)據(jù)結(jié)構(gòu)_樹B.ppt非線性結(jié)構(gòu)，一個直接前驅(qū)，但可能有多個直接后繼（1:n）樹的定義1）具有遞歸性，即樹中還有樹2）m

40、顆互不相交的集合根 葉子 森林有序樹 無序樹雙親 孩子 兄弟 堂兄弟 祖先 子孫結(jié)點 結(jié)點的度 結(jié)點的層次 終端結(jié)點 分支結(jié)點樹的度 所有結(jié)點度中的最大值（Max各結(jié)點的度樹的深度指所有結(jié)點中最大的層數(shù)（Max各結(jié)點的層次(或高度)4.2樹的表示法圖形表示法廣義表表示法左孩子右兄弟表示法雙親孩子表示法4.3樹的邏輯結(jié)構(gòu)一對多（1:n），有多個直接后繼（如家譜樹、目錄樹等等），但只有一個根結(jié)點，且子樹之間互不相交。廣義表表示法左孩子右兄弟表示法4.4二叉樹概念4.4.1基本概念二叉樹的結(jié)構(gòu)最簡單，規(guī)律性最強可以證明，所有樹都能轉(zhuǎn)為唯一對應(yīng)的二叉樹，不失一般性定義：是n（n0）個結(jié)點的有限集合，由

41、一個根結(jié)點以及兩棵互不相交的、分別稱為左子樹和右子樹的二叉樹組成二叉樹性質(zhì)性質(zhì)1: 在二叉樹的第i層上至多有2i-1個結(jié)點（i>0）性質(zhì)2: 深度為k的二叉樹至多有2k-1個結(jié)點（k>0）性質(zhì)3: 對于任何一棵二叉樹，若2度的結(jié)點數(shù)有n2個，則葉子數(shù)（n0）必定為n21 （即n0=n2+1）滿二叉樹：一棵深度為k 且有2k -1個結(jié)點的二叉樹。 （特點：每層都“充滿”了結(jié)點）完全二叉樹：深度為k 的，有n個結(jié)點的二叉樹，當且僅當其每一個結(jié)點都與深度為k 的滿二叉樹中編號從1至n的結(jié)點一一對應(yīng)。理解：（k-1層與滿二叉樹完全相同，第k層結(jié)點盡力靠左）數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)：數(shù)據(jù)結(jié)構(gòu)(C語言版)

42、.嚴蔚敏_吳偉民.掃描版.pdf p124 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)：數(shù)據(jù)結(jié)構(gòu)(C語言版).嚴蔚敏_吳偉民.掃描版.pdf p127 性質(zhì)4: 具有n個結(jié)點的完全二叉樹的深度必為ëlog2nû1性質(zhì)5: 對完全二叉樹，若從上至下、從左至右編號，則編號為i 的結(jié)點，其左孩子編號必為2i，其右孩子編號必為2i1；其雙親的編號必為i/2（i1 時為根,除外）二叉樹的存儲結(jié)構(gòu)一、順序存儲結(jié)構(gòu)按二叉樹的結(jié)點“自上而下、從左至右”編號，用一組連續(xù)的存儲單元存儲。答：一律轉(zhuǎn)為完全二叉樹！討論：不是完全二叉樹怎么辦？方法很簡單，將各層空缺處統(tǒng)統(tǒng)補上“虛結(jié)點”，其內(nèi)容為空二、鏈式存儲結(jié)構(gòu)4.4.2二叉樹

43、的表示二叉樹表示法P127頁/*typedef struct BiTNodeintdata; struct BiTNode *lchild, *rchild;BiTNode, *BiTree;*/struct BiTNodeintdata;struct BiTNode *lchild, *rchild;typedef struct BiTNode BiTNode;typedef struct BiTNode * BiTree;樹的三叉鏈表表示/三叉鏈表typedef struct TriTNode int data;/左右孩子指針struct TriTNode *lchild, *rchild

44、;struct TriTNode *parent;TriTNode, *TriTree;雙親鏈表法/雙親鏈表#define MAX_TREE_SIZE 100typedef struct BPTNodeint data;int parentPosition; /指向雙親的指針 /數(shù)組下標char LRTag; /左右孩子標志域BPTNode;typedef struct BPTreeBPTNode nodes100; /因為節(jié)點之間是分散的，需要把節(jié)點存儲到數(shù)組中int num_node; /節(jié)點數(shù)目int root; /根結(jié)點的位置 /注意此域存儲的是父親節(jié)點在數(shù)組的下標BPTree;/用這

45、個數(shù)據(jù)結(jié)構(gòu)能表達出一顆樹，為什么？4.4.3二叉樹的遍歷樹的遍歷本質(zhì)剖析4.5二叉樹編程實踐基本操作typedef struct node int data; struct node *lchild,*rchild； NODE;NODE *root; DLR(NODE *root ) if (root) /非空二叉樹 printf(“%d”,root->data); /訪問DDLR(root->lchild); /遞歸遍歷左子樹DLR(root->rchild); /遞歸遍歷右子樹 中序遍歷算法LDR(NODE *root) if(root !=NULL) LDR(root-

46、>lchild); printf(“%d”,root->data); LDR(root->rchild); 后序遍歷算法LRD (NODE *root)if(root !=NULL) LRD(root->lchild); LRD(root->rchild); printf(“%d”,root->data); 案例1：計算二叉樹中葉子結(jié)點的數(shù)目int sum = 0; /全局變量DLR_CountLeafNum(NODE *root)/采用中序遍歷的遞歸算法 if ( root) /非空二叉樹條件，還可寫成if(root !=NULL ) if(!root-&

47、gt;lchild&&!root->rchild) /是葉子結(jié)點則統(tǒng)計并打印 sum+; printf("%dn",root->data); DLR_CountLeafNum(root->lchild); /遞歸遍歷左子樹，直到葉子處； DLR_CountLeafNum(root->rchild);/遞歸遍歷右子樹，直到葉子處； return(0); 思想：1）求根結(jié)點左子樹的葉子結(jié)點個數(shù)，累計到sum中，求根結(jié)點右子樹的葉子結(jié)點個數(shù)累計到sum中。2）若左子樹還是樹，重復(fù)步驟1；若右子樹還是樹，重復(fù)步驟1。3）全局變量轉(zhuǎn)成函數(shù)參數(shù)4

48、）按照先序、中序、后序方式計算葉子結(jié)點，=三種遍歷的本質(zhì)思想強化：訪問結(jié)點的路徑都是一樣的，計算結(jié)點的時機不同。案例2：求二叉樹的深度思想：1）求根結(jié)點左子樹高度，根結(jié)點右子樹高度，比較的子樹最大高度，再+1。2）若左子樹還是樹，重復(fù)步驟1；若右子樹還是樹，重復(fù)步驟1。案例3：完全Copy二叉樹 思想：1）malloc新結(jié)點，2）拷貝左子樹，拷貝右子樹，讓新結(jié)點連接左子樹，右子樹3）若左子樹還是樹，重復(fù)步驟1、2；若右子樹還是樹，重復(fù)步驟1、2。案例4：樹的非遞歸遍歷(中序遍歷)中序 遍歷的幾種情況分析1：什么時候訪問根、什么時候訪問左子樹、什么訪問右子樹 當左子樹為空或者左子樹已經(jīng)訪問完畢以

49、后，再訪問根 訪問完畢根以后，再訪問右子樹。分析2：非遞歸遍歷樹，訪問結(jié)點時，為什么是棧，而不是其他模型（比如說是隊列）。 先走到的后訪問、后走到的先訪問，顯然是棧結(jié)構(gòu)分析3：結(jié)點所有路徑情況步驟1：如果結(jié)點有左子樹，該結(jié)點入棧；如果結(jié)點沒有左子樹，訪問該結(jié)點；步驟2：如果結(jié)點有右子樹，重復(fù)步驟1；如果結(jié)點沒有右子樹（結(jié)點訪問完畢），根據(jù)棧頂指示回退，訪問棧頂元素，并訪問右子樹，重復(fù)步驟1如果棧為空，表示遍歷結(jié)束。 注意：入棧的結(jié)點表示，本身沒有被訪問過，同時右子樹也沒有被訪問過。分析4：有一個一直往左走入棧的操作，中序遍歷的起點作業(yè)：自己編寫堆棧函數(shù)原型，實現(xiàn)中序遍歷非遞歸算法4.6二叉樹的

50、創(chuàng)建4.6.1中序和先序創(chuàng)建樹1、根據(jù)中序遍歷的結(jié)果能確定一棵樹嗎？中序遍歷：結(jié)果為：“12345”，這個“12345”能確定一棵樹嗎？請思考，會有多少種形狀。2、如何才能確定一棵樹？結(jié)論：通過中序遍歷和先序遍歷可以確定一個樹 通過中序遍歷和后續(xù)遍歷可以確定一個樹通過先序遍歷和后序遍歷確定不了一個樹。單獨先序遍歷：能求解根，但不能求解左子樹什么時候結(jié)束、右子樹什么時候開始。3、根據(jù)先序和中序結(jié)果畫樹算法1、通過先序遍歷找到根結(jié)點A，再通過A在中序遍歷的位置找出左子樹，右子樹2、在A的左子樹中，找左子樹的根結(jié)點（在先序中找），轉(zhuǎn)步驟13、在A的右子樹中，找右子樹的根結(jié)點（在先序中找），轉(zhuǎn)步驟1講解：先序遍歷結(jié)果：ADEBCF中序遍歷結(jié)果：DEACFB練習(xí)：先序遍歷結(jié)果：ABDHKECFIGJ中序遍歷結(jié)果：HKDBEAIFCGJ4、學(xué)習(xí)算法可借助工具、動畫光盤有