數(shù)據(jù)結(jié)構(gòu)期末復(fù)習總結(jié)-免費閱讀
【正文】 AOV 網(wǎng)的拓撲排序：在頂點活動網(wǎng)AOV 網(wǎng)中，若不存在回路，則所有活動可排列成一個線性序列，使得每個活動的所有前驅(qū)活動都排在該活動的前面，該序列叫拓撲序列，由AOV 網(wǎng)構(gòu)造拓撲序列的過程叫做拓撲排序。有向無環(huán)圖（directed acycling graph）：一個無環(huán)的有向圖簡稱DAG 圖。圖的遍歷：從圖中某個頂點出發(fā)訪遍圖中其余頂點，并且使圖中的每個頂點僅被訪問一次過程。生成樹： 在一個連通圖G 中，如果取它的全部頂點和一部分邊構(gòu)成一個子圖G?,V(G?)=V(G) E(G?)∈E(G), 若邊集E（G?）中的邊將圖中所有的頂點連通又不形成回路，則稱子圖G?是圖G 的一棵生成樹。即將兩個位置相鄰的有序子序列：第九章圖有向圖：頂點對x, y 是有序的，x, y≠y,x，即E 中為有向邊。頂堆?，即先選得一個關(guān)鍵字為最大的記錄，然后與序列中最后一個記錄交換，之后繼續(xù)對序列中前n1 記錄進行?篩選?，重新將它調(diào)整為一個摯243。即：將記錄序列分成若干子序列，每個子序列分別進行插入排序。（3）表插入排序：為了減少在排序過程中進行的撘198。（2）主要理解B 樹的檢索、插入和刪除。第七章高級字典結(jié)構(gòu)二叉排序樹（二叉查找樹）(1) 定義二叉排序樹或者是一棵空樹；或者是具有如下特性的二叉樹：1）若它的左子樹不空， 則左子樹上所有結(jié)點的值均小于根結(jié)點的值；2）若它的右子樹不空，則右子樹上所有結(jié)點的值均大于根結(jié)點的值；3）它的左、右子樹也都分別是二叉排序樹。所謂摵195。哈夫曼樹的應(yīng)用最廣泛地是在編碼技術(shù)上，它能夠容易地求出給定字符集及其概率分布的最優(yōu)前綴碼。孩子鏈表表示法（就是為樹中每個結(jié)點設(shè)置一個孩子鏈表，并將結(jié)點及相應(yīng)的孩子鏈表的頭指針存放在一個向量中）孩子鏈表表示便于實現(xiàn)涉及孩子結(jié)點及子孫的運算，但不便于實現(xiàn)與雙親有關(guān)的運算。在中序線索樹中查找給定結(jié)點的中序前趨和中序后繼的方法：若結(jié)點*p 的左子樹(或右子樹非空)，則*p 的中序前趨是從*p 的左孩子開始沿著右指針鏈往下查找直到找到一個沒有右孩子的結(jié)點為止，而*p 的中序后繼是從它的右孩子開始沿著左指針鏈往下直到找到一個沒有左孩子的結(jié)點為止。把所有二叉樹的結(jié)點，加上一個指向根結(jié)點的指針就構(gòu)成了二叉樹的鏈式存儲結(jié)構(gòu)，稱為二叉鏈表。鏈隊列不存在隊滿和上溢的問題。為了克服空間浪費，我們引入循環(huán)向量的概念，就好比是把向量空間彎起來，形成一個頭尾相接的環(huán)形，這樣，當存于其中的隊列頭尾指針移到向量空間的上界(尾部)時，再加1 的操作(入隊或出隊)就使指針指向向量的下界，也就是從頭開始。為了解決這種存儲密度過低的狀況，可以讓一個結(jié)點存儲多個字符，事實上這是順序串和鏈串的綜合(折衷)。靜態(tài)的意思可簡單地理解為一個確定的存儲空間，它的長度是不可變的?？瞻状褐复邪粋€或多個空格字符的串。雙鏈表也可以頭尾相鏈接構(gòu)成雙(向)循環(huán)鏈表。循環(huán)鏈表是一種首尾相接的鏈表。對于順序表的插入和刪除運算，其平均時間復(fù)雜度均為O(n)。以保證算法的運行時間不會比它更長。數(shù)據(jù)元素是數(shù)據(jù)的基本單位，有時一個數(shù)據(jù)元素可以由若干個數(shù)據(jù)項組成。當我們評價一個算法的時間性能時，主要標準就是算法的漸近時間復(fù)雜度，因此，在算法分析時，往往對兩者不予區(qū)分，經(jīng)常是將漸近時間復(fù)雜度T(n)=O(f(n))簡稱為時間復(fù)雜度，其中的f(n)一般是算法中頻度最大的語句頻度。就是按線性表的邏輯結(jié)構(gòu)次序依次存放在一組地址連續(xù)的存儲單元中。這兩部分信息組成鏈表中的結(jié)點結(jié)構(gòu)。雙鏈表就是雙向鏈表，就是在單鏈表的每個結(jié)點里再增加一個指向其直接前趨的指針域prior,這樣形成的鏈表就有兩條不同方向的鏈。若插入和刪除主要發(fā)生在表的首尾兩端，則宜采用尾指針表示的單循環(huán)鏈表。空串是任意串的子串，任意串是他自身的子串。串的鏈式存儲就是用單鏈表的方式存儲串值，串的這種鏈式存儲結(jié)構(gòu)簡稱為鏈串。取棧頂元素：StackTop(S),不同與彈出，只是使用棧頂元素的值，該元素仍在棧頂不會改變。第三種就是用一個計數(shù)器記錄隊列中的元素的總數(shù)，這樣就可以隨時知道隊列的長度了，只要隊列中的元素個數(shù)等于向量空間的長度，就是隊滿。一般二叉樹的3 個重要性質(zhì)：第i 層至多有2i 個結(jié)點高度為k 的二叉樹中，最多有2 k+1 －1 個結(jié)點葉子數(shù)＝度2 結(jié)點數(shù)－1二叉樹的順序存儲結(jié)構(gòu)就是把二叉樹的所有結(jié)點按照一定次序(從根結(jié)點起，從上層到下層，從左往右編號就得到了存放的次序)存儲到一片連續(xù)的存儲單元中用順序存儲方式對于完全二叉樹而言其結(jié)構(gòu)簡單又節(jié)省空間，但是對于一般二叉樹并不合適。利用二叉鏈表中的n+1 個空指針域來存放指向某種遍歷次序下的前趨結(jié)點和后繼結(jié)點的指針，這些附加的指針就稱為線索，加上線索的二叉鏈表就稱為線索鏈表。林變二叉：樹變二叉根相連。樹的代價就是樹的帶權(quán)路徑長度，它的值是樹中所有葉結(jié)點的帶權(quán)路徑長度之和。突?現(xiàn)象，即：key1 key2，而
教學(xué)教案相關(guān)推薦
鄂ICP備17016276號-1