數(shù)據(jù)結(jié)構(gòu)C語言版期末復(fù)習(xí)匯總

1、-. z.數(shù)據(jù)構(gòu)造C語言版 期末復(fù)習(xí)匯總緒論數(shù)據(jù)構(gòu)造：是一門研究非數(shù)值計算程序設(shè)計中的操作對象，以及這些對象之間的關(guān)系和操作的學(xué)科。數(shù)據(jù)構(gòu)造是一門綜合性的專業(yè)課程，是一門介于數(shù)學(xué)、計算機硬件、計算機軟件之間的一門核心課程。是設(shè)計和實現(xiàn)編譯系統(tǒng)、操作系統(tǒng)、數(shù)據(jù)庫系統(tǒng)及其他系統(tǒng)程序和大型應(yīng)用程序的根底。數(shù)據(jù)：是客觀事物的符號表示，是所有能輸入到計算機中并被計算機程序處理的符號的總稱。如數(shù)學(xué)計算中用到的整數(shù)和實數(shù)，文本編輯中用到的字符串，多媒體程序處理的圖形、圖像、聲音及動畫等通過特殊編碼定義后的數(shù)據(jù)。數(shù)據(jù)的邏輯構(gòu)造劃分：線、樹、圖算法的定義及特性算法：是為了解決*類問題而規(guī)定的一個有限長的操作序列

2、。五個特性：有窮性、確定性、可行性、輸入、輸出評價算法優(yōu)劣的根本標準4個：正確性、可讀性、強健性、高效性及低存儲量第二章 線性表線性表的定義和特點：線性表：由n(n0)個數(shù)據(jù)特性一樣的元素構(gòu)成的有限序列。線性表中元素個數(shù)n(n0)定義為線性表的長度，n=0時稱為空表。非空線性表或線性構(gòu)造，其特點：1存在唯一的一個被稱作第一個的數(shù)據(jù)元素；2存在唯一的一個被稱作最有一個的數(shù)據(jù)元素；3除第一個之外，構(gòu)造中的每個數(shù)據(jù)元素均只有一個前驅(qū)；4除最后一個之外，構(gòu)造中的每個數(shù)據(jù)元素均只有一個后繼。順序表的插入：n個元素在i位插入，應(yīng)移動n-i+1位元素。順序表存儲構(gòu)造的優(yōu)缺點：優(yōu)點：邏輯相鄰，物理相鄰；可隨機

3、存取任一元素；存儲空間使用緊湊；缺點：插入、刪除操作需要移動大量的元素；預(yù)先分配空間需按最大空間分配，利用不充分；表容量難以擴大；線性表的應(yīng)用：一般線性表的合并：*算法2.1：LA=(7,5,3,11) LB=(2,6,3)合并后 LA=(7,5,3,11,2,6)算法思想：擴大線性表LA，將存在于線性表LB中而不存在于線性表LA中的數(shù)據(jù)元素插入到線性表LA中去。只要從線性表LB中依次取得每個數(shù)據(jù)元素，并依值在線性表LA中進展查訪，假設(shè)不存在，則插入之。有序表的合并：*算法2.2：LA=(3,5,8,11) LB=(2,6,8,9,11,15,20)則 LC=(2,3,5,6,8,9,11,1

4、1,15,20)算法思想：首先創(chuàng)立一個空表LC，通過比擬指針pa和pb所指向的元素的值，依次從LA或LB中摘取元素值較小的結(jié)點插入到LC表的最后，當其中一個表變空是，說明此表的元素已歸并完，則只要將另一個非空表的剩余結(jié)點依次插入在LC表的最后即可。線性鏈表：線性鏈表的插入：插入元素師，指針的指向變化：上述指針修改用語句描述即為：s-ne*t=p-ne*t; p-ne*t=s;單鏈表的插入：*void insertnode(linklist head，datetype *，int i) listnode * p，*q; p=getnode(head，i-1);if(p=NULL) error(p

5、osition error); q=(listnode *) malloc(sizeof(listnode); qdata=*; qne*t=pne*t; pne*t=q; 課本中：s=new LNode;s-data =e;s-ne*t=p-ne*t;p-ne*t=s;線性鏈表的刪除：刪除元素，指針的指向變化：上述指針修改用語句描述即為：p-ne*t=p-ne*t-ne*t;單鏈表的刪除：*void deletelist(linklist head， int i) listnode * p， *r; p=getnode(head，i-1); if(p= =NULL | pne*t= =NUL

6、L) return ERROR; r=pne*t; pne*t=rne*t; free( r ) ;課本中：q=p-ne*t;p-ne*t=q-ne*t;單鏈表特點：它是一種動態(tài)構(gòu)造，整個存儲空間為多個鏈表共用；不需預(yù)先分配空間；指針占用額外存儲空間；不能隨機存取，查找速度慢。第三章 棧和隊列棧的類型定義：棧(Stack)是限制在表的一端進展插入和刪除運算的線性表，通常稱插入、刪除的這一端為棧頂(Top)，另一端為棧底(Bottom)。當表中沒有元素時稱為空棧。假設(shè)棧S=(a1，a2，a3，an)，則a1稱為棧底元素，an為棧頂元素。棧中元素按a1，a2，a3，an的次序進棧，退棧的第一個元素

7、應(yīng)為棧頂元素。即，棧的修改是按后進先出的原則進展的。因此，棧稱為后進先出表LIFO。棧的進棧、出棧順序：例：*對于一個棧，給出輸入項A、B、C，如果輸入項序列由ABC組成，試給出所有可能的輸出序列。 A進 A出 B進 B出 C進 C出 ABC A進 A出 B進 C進 C出 B出 ACB A進 B進 B出 A出 C進 C出 BAC A進 B進 B出 C進 C出 A出 BCA A進 B進 C進 C出 B出 A出 CBA不可能產(chǎn)生輸出序列CAB棧的應(yīng)用：數(shù)值轉(zhuǎn)換大題算法思想：首先將按照上述計算過程中得到的八進制樹的各位依次進棧，然后將棧中的八進制數(shù)依次出棧輸出，輸出結(jié)果就是該是十進制數(shù)轉(zhuǎn)換得到的八進

8、制數(shù)。N=(N div d)d + N mod d 其中：div 為整除運算，mod 為求余運算例如 (1348)10=(2504)8，其運算過程如下：N N div 8 N mod 81348 168 4168 21 021 2 52 0 2算法：【此為課件算法同課本算法一致】*void conversion() initstack ( s );/構(gòu)造空棧 scanf ( % , n); while( n ) push ( s , n % 8 ); n = n / 8; while( ! Stackempty ( s )/當棧非空時 pop ( s , e ); printf ( % d ,

9、 e );/conversion隊列的類型定義：定義：隊列是限定只能在表的一端進展插入，在表的另一端進展刪除的線性表隊尾(rear)：允許插入的一端隊頭(front)：允許刪除的一端隊列特點：先進先出 ( FIFO )第四章 串、數(shù)組和廣義表串的類型定義：串是字符串的簡稱。它是一種在數(shù)據(jù)元素的組成上具有一定約束條件的線性表，即要求組成線性表的所有數(shù)據(jù)元素都是字符，所以，人們經(jīng)常又這樣定義串：串是一個有窮字符序列。串一般記作：s= a1a2.an (n0) 其中，s是串的名稱，用雙引號括起來的字符序列是串的值；ai可以是字母、數(shù)字或其他字符；串中字符的數(shù)目n被稱作串的長度。當n=0時，串中沒有任

10、何字符，其串的長度為0，通常被稱為空串。子串、主串：串中任意連續(xù)的字符組成的子序列被稱為該串的子串。包含子串的串又被稱為該子串的主串。廣義表的定義：廣義表是n(n=0)個元素a1,a2,a3,an的有限序列，其中ai或者是原子項，或者是一個廣義表。通常記作LS=a1,a2,a3,an)。LS是廣義表的名字，n為它的長度。假設(shè)ai是廣義表，則稱它為LS的子表。廣義表的構(gòu)造特點:1) 廣義表的元素可以是子表，而子表的元素還可以是子表廣義表是一個多層次的構(gòu)造2) 廣義表可為其他廣義表所共享3) 廣義表可以是一個遞歸的表，即廣義表也可以是其本身的一個子表廣義表的兩個重要運算：取表頭GetHead(LS

11、)，取表尾GetTail(LS)任何一個非空廣義表LS = ( 1, 2, , n )均可分解為表頭 Head(LS) = 1 和表尾 Tail(LS) = ( 2, , n )兩局部。例如：*廣義表LS=a，b，c，d，c，運用GetHead和GetTail函數(shù)取出原子d的運算過程為：GetHead(GetTail(GetTail(GetHead(GetTail(LS)第五章 樹和二叉樹數(shù)的定義： 樹(tree)是n(n0)個結(jié)點的有限集T，其中：有且僅有一個特定的結(jié)點，稱為樹的根(root)；當n1時，其余結(jié)點可分為m(m0)個互不相交的有限集T1,T2,Tm，其中每一個集合本身又是一棵樹

12、，稱為根的子樹(subtree)。特點：樹中至少有一個結(jié)點：根樹中各子樹是互不相交的集合線性構(gòu)造與樹形構(gòu)造的區(qū)別線性構(gòu)造樹形構(gòu)造第一個數(shù)據(jù)元素?zé)o前驅(qū) 根結(jié)點 無前驅(qū)最后一個數(shù)據(jù)元素?zé)o后繼 多個葉子結(jié)點無后繼其它數(shù)據(jù)元素一個前驅(qū)，一個后繼其它數(shù)據(jù)元素一個前驅(qū)、多個后繼樹的根本術(shù)語：結(jié)點(node) ：表示樹中的元素，包括數(shù)據(jù)元素及假設(shè)干指向其子樹的分支結(jié)點的度(degree) ：結(jié)點擁有的子樹數(shù)樹的度 ： 一棵樹中最大的結(jié)點度數(shù)葉子(leaf) ：度為0的結(jié)點終端結(jié)點孩子(child) ：結(jié)點子樹的根稱為該結(jié)點的雙親(parents) ：孩子結(jié)點的上層結(jié)點叫該結(jié)點的兄弟(sibling) ：同一

13、雙親的孩子子孫 ： 以*結(jié)點為根的子樹中的所有結(jié)點都被稱為是該結(jié)點的祖先 ：從根結(jié)點到該結(jié)點路徑上的所有結(jié)點堂兄弟 ：雙親在同一層的結(jié)點互為結(jié)點的層次(level) ： 從根結(jié)點算起，根為第一層，它的孩子為第二層深度(depth) ： 樹中結(jié)點的最大層次數(shù)森林(forest) ： m(m0)棵互不相交的樹的集合有序樹、無序樹 ： 如果樹中每棵子樹從左向右的排列擁有一定的順序，不得互換，則稱為有序樹，否則稱為無序樹對于課本P96樹形圖：*結(jié)點A的度：3結(jié)點B的度：2結(jié)點M的度：0結(jié)點A的層次：1結(jié)點M的層次：4結(jié)點B，C，D為兄弟結(jié)點K，L為兄弟葉子：K，L，F(xiàn)，G，M，I，J結(jié)點A的孩子：B，

14、C，D結(jié)點B的孩子：E，F(xiàn)結(jié)點I的雙親：D結(jié)點L的雙親：E結(jié)點F，G為堂兄弟結(jié)點A是結(jié)點F，G的祖先樹的深度：4樹的度：3二叉樹的定義：二叉樹是n(n0)個結(jié)點的有限集，它或為空樹(n=0)，或由一個根結(jié)點和兩棵分別稱為左子樹和右子樹的互不相交的二叉樹構(gòu)成。特點每個結(jié)點至多有二棵子樹(即不存在度大于2的結(jié)點)；二叉樹的子樹有左、右之分，且其次序不能任意顛倒。二叉樹的性質(zhì)：性質(zhì)1：在二叉樹的第i層上最多有2i-1個結(jié)點i1；性質(zhì)2：深度為K的二叉樹最多有2K-1個結(jié)點K1；性質(zhì)3：對任何一棵二叉樹T，如果其終端結(jié)點數(shù)為n0，度為2的結(jié)點數(shù)為n2，則n0=n2+1；完全二叉樹定義：一棵深度為h，具

15、有n個結(jié)點的二叉樹，假設(shè)將它與一棵同深度的滿二叉樹中的所有結(jié)點按從上到下，從左到右的順序分別進展編號，且該二叉樹中的每個結(jié)點分別與滿二叉樹中編號為1n的結(jié)點位置一一對應(yīng)，則稱這棵二叉樹為完全二叉樹。特點：葉子結(jié)點只可能在層次最大的兩層上出現(xiàn);對任一結(jié)點，假設(shè)其右分支下子孫的最大層次為L，則其左分支下子孫的最大層次必為L或L+1。性質(zhì)4：具有n個結(jié)點的完全二叉樹的深度為log2n+1。其中，log2n 的結(jié)果是不大于log2n的最大整數(shù)。性質(zhì)5：對于有n個結(jié)點的完全二叉樹中的所有結(jié)點按從上到下，從左到右的順序進展編號，則對任意一個結(jié)點i 1in，都有：1如果i=1，則結(jié)點i是這棵完全二叉樹的根，

16、沒有雙親。否則其雙親結(jié)點的編號為 i/2；2如果2in，則結(jié)點i沒有左孩子。否則其左孩子結(jié)點的編號為2i；3如果2i+1n，則結(jié)點i沒有右孩子。否則其右孩子結(jié)點的編號為2i+1。 遍歷二叉樹：*先序遍歷：先訪問根結(jié)點,然后分別先序遍歷左子樹、右子樹【包絡(luò)法】中序遍歷：先中序遍歷左子樹，然后訪問根結(jié)點，最后中序遍歷右子樹【垂直映射法】后序遍歷：先后序遍歷左、右子樹，然后訪問根結(jié)點例：1先序遍歷：A.B.D.E.F.G.K.M.C.H.J 中序遍歷：D.B.F.E.K.A.M.G.H.C.J P105 貼紙1例：2后序遍歷：E.I.F.G.B.C.J.K.N.O.L.M.H.D.A P105貼紙2

17、赫夫曼樹遍歷：*例：W= 5，29，7，8，14，23，3，11 第六章 圖圖的定義：圖(Graph)：圖G是由兩個集合V(G)和E(G)組成的,記為：G=(V,E)其中：V(G)是頂點的非空有限集；E(G)是邊的有限集合，邊是頂點的無序?qū)蛴行驅(qū)ΑＳ邢驁D，無向圖頂點的度：無向圖中，頂點的度為與每個頂點相連的邊數(shù)；有向圖中，頂點的度分成入度與出度入度：以該頂點為頭的弧的數(shù)目出度：以該頂點為尾的弧的數(shù)目路徑：路徑是頂點的序列V=Vi0,Vi1,Vin，滿足(Vij-1,Vij)E 或 E,(1r2.key，則交換；然后比擬第二個記錄與第三個記錄；依次類推，直至第n-1個記錄和第n個記錄比擬為止第

18、一趟冒泡排序，結(jié)果關(guān)鍵字最大的記錄被安置在最后一個記錄上對前n-1個記錄進展第二趟冒泡排序，結(jié)果使關(guān)鍵字次大的記錄被安置在第n-1個記錄位置重復(fù)上述過程，直到在一趟排序過程中沒有進展過交換記錄的操作為止。課件上的算法：void BubbleSort(int a, int n) int i, j, e*change; int tmp; for (i = 0; i i; j-) /比擬，找出最小關(guān)鍵字的記錄 if (aj 0)&(flag=1)flag=0;/flag置為0，如果本趟排序沒有發(fā)生交換，則不會執(zhí)行下一趟排序for(j=1;jL.rj+1.key)flag=1;/flag置為1，表示本趟排序發(fā)生了交換t=L