視頻-data struct數(shù)據(jù)結(jié)構(gòu)與算法

數(shù)據(jù)結(jié)構(gòu)(Data 集合：結(jié)構(gòu)中的數(shù)據(jù)元素除了“同屬于一個集合”外，沒有其關(guān)系線性結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù) 間存在一對一的關(guān)系樹型結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù) 間存在一對多的關(guān)系圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù) 間存在多對多的關(guān)系數(shù)據(jù)結(jié)構(gòu) 方 鏈?zhǔn)浇Y(jié)構(gòu)：在每一個數(shù)據(jù)元素中增加一個存放另一個元素地址的指針(pointer元間的邏輯結(jié)構(gòu)(關(guān)系)。邏輯結(jié) 物理結(jié)線性樹圖

順 結(jié)鏈 結(jié)復(fù) 結(jié)圖1- 邏輯結(jié)構(gòu)與所采用 結(jié)數(shù)據(jù)的邏輯結(jié)線數(shù)據(jù)的邏輯結(jié)線性結(jié)非線性結(jié)串?dāng)?shù)據(jù)邏輯結(jié)構(gòu)層次關(guān)⑴建立(Create)一個數(shù)據(jù)結(jié)構(gòu)⑵消除(Destroy)一個數(shù)據(jù)結(jié)構(gòu)⑶從一個數(shù)據(jù)結(jié)構(gòu)中刪除(Delete)一個數(shù)據(jù)元⑷把一個數(shù)據(jù)元 (Insert)到一個數(shù)據(jù)結(jié)構(gòu)中⑸對一個數(shù)據(jù)結(jié)構(gòu)進 ⑹對一個數(shù)據(jù)結(jié)構(gòu)(中的數(shù)據(jù)元素)進行修⑺對一個數(shù)據(jù)結(jié)構(gòu)進行排⑻對一個數(shù)據(jù)結(jié)構(gòu)進行查找(Search)順序結(jié)構(gòu)中，很容易實現(xiàn)線性表的一用一組任意 單 在一起的雙向鏈表(DoubleLinkedList)指的是構(gòu)成鏈表的每個 雙向鏈表是為了克服單鏈表的單向性的缺陷而引入的??空雙向鏈

??

雙向鏈表結(jié)點??非空雙向鏈結(jié)點的雙向鏈表它們都來自線性表數(shù)據(jù)結(jié)構(gòu)，都是“操作棧在計算機的實現(xiàn)有多種方式 棧(Stack)：是限制在表的一端進行和刪除操作的線性表。又稱為后進先出LIFO(LastInFirstOut)或先進后出FILO(FirstInLastOut) 棧的順 表棧的順序結(jié)構(gòu)簡稱為順序棧，和線性表相類似，用一維數(shù)組來棧。根據(jù)數(shù)的空間；動態(tài)順序棧根據(jù)需要增大棧的空間，但實棧的鏈 表 進先出(FirstInFirstOut，簡稱FIFO)的線性表。 隊尾(rear)：允許進 入元素a1a2an之后，a1是隊首元素，an是隊尾元素。顯然退出隊列的次序也只能是a1,a2,…,an，即隊列的修改是依先進先出的原則進行的(CircularQueue)。01015243d0541e2b3g0152b43g空隊

de,bg入

de出隊列的鏈?zhǔn)浇Y(jié)構(gòu)簡稱為鏈隊列，它是法。樹和二叉樹的各種結(jié)構(gòu)以及建立在各種結(jié)構(gòu)的操作及應(yīng)用等。樹(Tree)是n(n≧0)個結(jié)點的有限集合T，n=0時稱為空樹，否則相交的子集T1T2T3…Tm，其中每個子集本身又是一棵樹，稱其為根的(Subtree)。結(jié)點(node)：一個數(shù)據(jù)元素及其若干指向 的分支結(jié)點的度(degree)、樹的度：結(jié)點所擁有的 AA只有根結(jié)

樹的示例形

一般的 顯然，若將一棵樹的根結(jié)點刪除，剩余的就構(gòu)EE ABFD JCMGN廣義表形樹的表示形 嵌套集合形二叉樹(Binarytree)是n(n≥0)個結(jié)點的有限集合。若分別稱之為左、右，并且左、右又都是二叉樹。由此可知，二叉樹的定義是遞歸的構(gòu)簡單，效率高，樹的操作算法相對簡單，且任何 A 空二叉 單結(jié)點二叉 為 為 左、 都不二叉樹的基本形性質(zhì)1：在非空二叉樹中，第i層上至多2i-1個結(jié)點(i≧1點（k≧1)。滿二叉樹(FullBinaryTree)。滿二叉樹的特點所有的支結(jié)點都有左、右可對滿二叉樹的結(jié)點進行連續(xù)，若規(guī)定從 –其中2k-1n≦2k-1 45894589123456789(a)滿二叉 (b)完全二叉13非完全二叉13特殊形態(tài)的二叉二叉樹 結(jié)順 結(jié)

(a)完全二叉 (b)非完全二叉 1011abcdefghij 完全二叉樹的順 形 10abcde?h??fg非完全二叉樹的順 形鏈 結(jié) 指向左右子結(jié)點的指針域三叉鏈表結(jié)點。除二叉鏈表的三個域外，再增加一個指針域，用來指向結(jié)點的父結(jié)點(a)二叉鏈表結(jié) (b)三叉鏈表結(jié)鏈表結(jié)點結(jié)構(gòu)形二叉樹的鏈 形 ?aa?? ?aa??bbbbbdd?c??cdd?c??c?e?e??f?e?e??f??f??g??g??g?二叉

二叉鏈二叉樹及其鏈 結(jié)

三叉鏈遍歷二叉樹(TraversingBinaryTree)是指按指定的 若以L、D、R分別表示遍歷左、遍歷根結(jié)點和遍歷右，則有六種遍歷方案：DLR、DLR——先(根)序遍歷LDR——中(根)序遍歷LRD——后(根)序遍歷又名二叉排序用遞歸的方法構(gòu)建實現(xiàn)對樹的增刪改查功找的元素為止。否則就是表中沒有要找的元素，查找不成功。平均要與表中一半以上元素進行比較，情況下如果線性表為無序表，則不管是順序結(jié)構(gòu)還是鏈?zhǔn)浇Y(jié)構(gòu)，都只能用順序查找。即使是有序線性表，如果采用鏈?zhǔn)浇Y(jié)構(gòu)，也只二分法查 需要比較log2n次。二分法查 7

（a)

7

（b) 7

（c)–給定一組記錄序列：{R1,R2,…,Rn}，其相應(yīng)的關(guān)鍵字序列是{K1K2Kn確定12n一個排列p1,p2,…,pn，使其相應(yīng)的關(guān)鍵字滿足如下非遞減(或非遞增)關(guān)系：Kp1≤Kp2Kpn的序列{Kp1Kp2Kpn這種操作稱為排序Ki可以是記錄Ri鍵字或若干數(shù)據(jù)項的組合。=Kj(i≠j，ij=12n)，且在排序前Ri先于Rj(i<j)，排序后的度是O(1待排序的記錄數(shù)不太多，所有的記錄都能存放在內(nèi)存中進行排序，稱為 排序；存中，交換，這樣的排序稱為外部排序。對比較兩個關(guān)鍵字的大小位置的移動，從一個位置移到另一個位置于記錄的方式，具體情況是：記錄在一組連續(xù)地址的空間：記錄之間的邏輯順序關(guān)是通過其物理位置的相鄰來體現(xiàn)，記錄的移動是必不可 記錄采用鏈?zhǔn)椒绞剑河涗浿g的邏輯順序關(guān)系是通過結(jié)點中記錄在一組連續(xù)地址的空間：構(gòu)造另一個輔助表來保存 采用的是以“玩橋牌者”的方法為基礎(chǔ)的。 R1,R2,….,Ri-1已排好序，然后將Ri到已排好序的諸記錄的適當(dāng)位置最基本 排序是直 排(StraightInsertionSort)直 排 R1,R2,….,Ri-1中，得到一個新的、記錄數(shù)增加1的有序表。直到所有的記錄都 R[1…i-1]：已排好序的有序部分R[i…n]：未排好序的無序部分顯然，在剛開始排序時，R[1直 排序示設(shè)有關(guān)鍵字序列為：7,4,-2,19,13,6，直 排序的過初始記錄的關(guān)鍵字： - 第一趟排序： - 第二趟排序：[- 第三趟排序：[- 第四趟排序：[- 第五趟排序：[- 初始記錄的關(guān)鍵字：4-6第一趟排序：-476第二趟排序：-476第三趟排序：-467第四趟排序：-467第五趟