數(shù)據(jù)結(jié)構(gòu)1.基本概念數(shù)據(jù)是信息的載體，是對客觀事物的符號表示，是計算機(jī)程序加工的“原料”。數(shù)據(jù)不僅包括整數(shù)、實數(shù)、字符串，還包括圖像和聲音等。數(shù)據(jù)元素是組成數(shù)據(jù)的基本單位，在計算機(jī)程序里往往作為一個整體進(jìn)行考慮和處理，數(shù)據(jù)元素也稱元素、結(jié)點、頂點、記錄。一個數(shù)據(jù)元素可以由若干個數(shù)據(jù)項（也可以成為字段、域、屬性）組成。數(shù)據(jù)項是具有獨立含義的最小標(biāo)識單位，是數(shù)據(jù)元素的基本組成部分，不可再分的數(shù)據(jù)單元。舉例：一個學(xué)生的基本信息數(shù)據(jù)作為數(shù)據(jù)元素，而描述學(xué)生信息的學(xué)號、姓名、性別、班級等為數(shù)據(jù)項。數(shù)據(jù)結(jié)構(gòu)指的是數(shù)據(jù)之間的相互關(guān)系，即數(shù)據(jù)的組織形式。數(shù)據(jù)結(jié)構(gòu)一般包括數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲結(jié)構(gòu)和數(shù)據(jù)的運算（操作集合），這三方面是一個整體，孤立地去理解一個方面，而不注意它們之間的的聯(lián)系是不可取的。邏輯結(jié)構(gòu)是數(shù)據(jù)間的邏輯關(guān)系。基本結(jié)構(gòu)有集合、線性結(jié)構(gòu)、樹形結(jié)構(gòu)、圖狀結(jié)構(gòu)（網(wǎng)狀結(jié)構(gòu)）。包括兩大類：線性結(jié)構(gòu)（線性表，隊列，棧，字符串，數(shù)組，廣義表）；非線性結(jié)構(gòu)（樹和圖）。存儲結(jié)構(gòu)可以用順序、鏈接、索引和散列存儲方法得到。數(shù)據(jù)類型是指一個值的集合以及在這些值上定義的一組操作的總稱。按“值”是否可分解，可將數(shù)據(jù)類型劃分為兩類：原子類型（不可再分）和結(jié)構(gòu)類型（可以再次分解）。時間代價（時間效率）就是當(dāng)問題的規(guī)模以某種單位由1增至n時，解決該問題的算法實現(xiàn)運行時所消耗的時間，也以某種單位由f(1)增至f(n)，則稱該算法的時間代價為f(n)。指標(biāo)為時間復(fù)雜度。空間代價（空間效率）就是當(dāng)問題的規(guī)模以某種單位由1增至n時，解決該問題的算法實現(xiàn)運行時所消耗的空間，也以某種單位由g(1)增至g(n)，則稱該算法的空間代價為g(n)。度量為空間復(fù)雜度。2.線性表：最簡單、最基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)，數(shù)據(jù)元素之間是一對一的關(guān)系均勻性：一表元素屬于同一集合，相同的數(shù)據(jù)類型；有序性：相鄰元素存在序偶關(guān)系；有限性：元素個數(shù)有限，為表長。線性表是由n(n>=0)個數(shù)據(jù)元素（結(jié)點）a1,a2,…an組成的有限序列。n為數(shù)據(jù)元素個數(shù)，即表的長度。元素的線性邏輯關(guān)系：有且只有一個開始結(jié)點（表頭結(jié)點a1）；有且只有一個終端結(jié)點（表尾結(jié)點an）。每個結(jié)點只有一個前驅(qū)結(jié)點（除表頭）和一個后繼結(jié)點（除表尾）?；敬鎯Y(jié)構(gòu)：順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)。順序表：將數(shù)據(jù)元素按其邏輯順序依次存放在內(nèi)存中一組地址連續(xù)的存儲單元中，依次相鄰。特點是：在線性表中邏輯關(guān)系相鄰的數(shù)據(jù)元素在計算機(jī)內(nèi)存物理位置也相鄰。插入：在具有n個元素的線性表第i個元素之前插入一個新元素，必須把從n到第i個之間的元素依次往后移動一個位置，空出第i個位置放新元素，表長變?yōu)閚+1。刪除：從具有n個元素的線性表中刪除第i個元素，就必須把從第i+1個到第n個之間的元素依次往前移動一個位置，以覆蓋前一個位置上的內(nèi)容，表長變?yōu)閚-1。**順序表插入和刪除操作的時間復(fù)雜度均為O(n)。優(yōu)點是表中元素可通過下標(biāo)進(jìn)行直接訪問，查詢效率高（存儲密度為100%）；缺點是插入、刪除操作不方便，需要移動元素。為靜態(tài)分布必須事先估計表長，過大或者過小可能造成存儲空間浪費或出現(xiàn)溢出。適合一旦建立長度將很少改變的應(yīng)用。鏈?zhǔn)酱鎯Y(jié)構(gòu)有線性鏈表、循環(huán)鏈表、雙向鏈表?？蓜討B(tài)存儲也可靜態(tài)存儲。線性鏈表：每個元素的存儲單位稱為結(jié)點，至少包括兩個域：存儲元素信息的數(shù)據(jù)域和存儲其后繼元素存儲位置的指針域。表中元素之間的邏輯關(guān)系通過結(jié)點指針體現(xiàn)，存儲位置不要求相鄰。存儲密度小于1，無需事先估計存儲空間。線性鏈表是動態(tài)地進(jìn)行存儲分配的一種結(jié)構(gòu)，可以根據(jù)需要開辟內(nèi)存單元。包含了申請、使用、釋放內(nèi)存空間三個步驟，實現(xiàn)存儲空間的動態(tài)分配。插入算法的關(guān)鍵是要找到插入的位置，并且標(biāo)記所插入位置的前驅(qū)結(jié)點，很明顯這樣比較次數(shù)為i-1次；其次是修改指針的次序：先執(zhí)行new→next=p→next后，執(zhí)行p→next=new。刪除算法步驟：根據(jù)給定的參數(shù)從頭結(jié)點出發(fā)找到要刪除的結(jié)點的前驅(qū)～修改指針從鏈表中刪除指定結(jié)點，即p→next=p→next→next～釋放被刪除結(jié)點的存儲空間。循環(huán)鏈表與單向鏈表一樣，也是鏈?zhǔn)酱鎯Y(jié)構(gòu)，不同的是，循環(huán)鏈表的最后一個結(jié)點的指針是指向該循環(huán)鏈表的第一個結(jié)點或者表頭結(jié)點，從而構(gòu)成一個環(huán)形的鏈。帶頭結(jié)點的單循環(huán)鏈表中，判斷空鏈表的條件是head==head->next.僅設(shè)尾指針的單循環(huán)鏈表中，判斷空鏈表的條件為rear==rear->next.雙向鏈表既可以用來表示線性結(jié)構(gòu)，也可以用來表示非線性結(jié)構(gòu)，其每個結(jié)點包括三個域：一個數(shù)據(jù)域和兩個指針域，一個指向它的前趨，另一個指向它的后繼。在雙向鏈表中，若d是指向表中任一結(jié)點的指針，則有l(wèi)link(rlink(d))=rlink(llink(d))=d.表示當(dāng)前結(jié)點的后繼結(jié)點的前驅(qū)是自身，當(dāng)前結(jié)點前驅(qū)結(jié)點的后繼結(jié)點也是自身。3.棧和隊列（兩種操作受限的特殊類型的線性表）棧是一種插入、刪除只能在表的一端進(jìn)行的線性表。插入元素稱為入棧，刪除元素稱為出棧。在棧中，允許插入和刪除的一端叫棧頂，不允許插入和刪除的一端叫棧底，位置固定。滿足后進(jìn)先出的原則。特殊的線性表，適用線性存儲結(jié)構(gòu)，有順序存儲和鏈?zhǔn)酱鎯Αｊ犃性趦蓚€方向都有限制，插入只能在表的一端進(jìn)行（只入不出），而刪除只能在表的另一端進(jìn)行（只出不進(jìn)），允許插入的一端稱隊尾（rear），允許刪除的一端稱隊頭（front），隊列的操作原則是先進(jìn)先出。當(dāng)隊伍中沒有元素時，稱之為空隊列，隊列的插入操作稱之為入隊，刪除操作稱之為出隊。4.數(shù)組數(shù)組是由類型相同的數(shù)據(jù)元素構(gòu)成的有序集合。行優(yōu)先：先行后列，先存儲行號較小的元素，行號相同者先存儲列號較小的元素。計算二維數(shù)組的地址：Loc(i,j)=Loc(0,0)+(行標(biāo)*i+j)*L數(shù)組特征：數(shù)組中的元素在內(nèi)存中是連續(xù)存放的～同一數(shù)組的所有元素具有相同的數(shù)據(jù)類型。一般程序設(shè)計中，數(shù)組必須先定義后使用，有數(shù)組的名稱，數(shù)組的維數(shù)和各維類型，數(shù)組元素的數(shù)據(jù)類型。數(shù)組是一種靜態(tài)結(jié)構(gòu)，一旦定義之后其元素的個數(shù)和數(shù)據(jù)類型就確定了，所需的存儲空間也就確定了。主要操作有：取特定位置的元素值及對特定位置的元素進(jìn)行賦值，不需要線性表中的插入和刪除操作。數(shù)組的存儲有兩種形式：一是按行存儲方式，也叫行優(yōu)先存儲；另一種是列存儲方式，也叫列優(yōu)先存儲。大多數(shù)采用行存儲。串（字符串）是一種特殊的線性表，它的字符序列由零個或多個字符組成。a=’’稱為空串，長度為0.求子串序列號：用index(a,sb)表示子串sb在串a(chǎn)中的序號。稀疏矩陣可用一個三元組（i,j,value）表示，將這些三元組按某種次序排成一個線性表。5.樹形結(jié)構(gòu)（一種非常重要的非線性結(jié)構(gòu)，元素之間有分支關(guān)系并且有層次關(guān)系）樹是n個結(jié)點的有限集合，是一類非線性結(jié)構(gòu)。樹的表現(xiàn)形式還有嵌套集合的形式、廣義表的形式和凹入表示法的形式。樹的結(jié)點包含一個數(shù)據(jù)元素及若干指向其子樹的分支。結(jié)點擁有的子樹數(shù)稱為結(jié)點的度。樹的定義具有遞歸性，即一棵樹是由根和若干棵子樹構(gòu)成的，而子樹又可以由更小的子樹構(gòu)成。只能有一個根結(jié)點。特點：層次關(guān)系，分支關(guān)系，樹中無環(huán)路存在。根結(jié)點沒有直接前驅(qū)，除根結(jié)點之外其余結(jié)點均有一個且只有一個直接前驅(qū)。結(jié)點可以有零個或者多個后繼結(jié)點。度為0的結(jié)點稱為葉子或終端結(jié)點，度不為0的結(jié)點稱為非終端結(jié)點或分支結(jié)點。樹內(nèi)各結(jié)點的度的最大值稱為樹的度。結(jié)點的子樹的根稱為該結(jié)點的孩子，相應(yīng)地，該結(jié)點稱為孩子的雙親。樹中結(jié)點的最大層次稱為樹的深度，從一結(jié)點到葉結(jié)點的最長路徑稱為該結(jié)點的高度。森林是m棵互不相交的樹的集合。（對樹中每個結(jié)點而言，其子樹的集合即為森林）二叉樹又是另一種樹型結(jié)構(gòu)，它的特點是每個結(jié)點至多只有兩棵子樹(即二叉樹中不存在度大于2的結(jié)點)，并且其子樹有左右子樹之分，次序不能隨意顛倒。與樹的主要區(qū)別就是要區(qū)分左子樹還是右子樹。二叉樹的性質(zhì)：a.在二叉樹的第i層至多有2^(i-1)個結(jié)點(i>=1).b.深度為k的二叉樹至多有2^k-1個結(jié)點(k>=1).c.對任何一棵二叉樹T，如果其終端結(jié)點數(shù)為n0，度為2的結(jié)點數(shù)為n2,則n0=n2+1.d.具有n個結(jié)點的完全二叉樹的深度為【log2n】+1f.。。。滿二叉樹：一棵深度為k且有2^k-1個結(jié)點的二叉樹。完全二叉樹：深度為k,有n個結(jié)點的二叉樹，當(dāng)且僅當(dāng)其每一個結(jié)點都與深度為k的滿二叉樹中編號從1至n的結(jié)點一一對應(yīng)時。二叉樹存儲結(jié)構(gòu)：順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)。順序存儲結(jié)點的邏輯關(guān)系通過結(jié)點的編號準(zhǔn)確的表示出來，適用于完全二叉樹，即方便訪問又節(jié)省存儲空間。對于一般二叉樹需要增設(shè)虛結(jié)點，轉(zhuǎn)化為完全二叉樹存儲，虛結(jié)點不存在卻占用空間造浪費。而鏈?zhǔn)酱鎯Ρ碇薪Y(jié)點結(jié)構(gòu)包括三個部分：數(shù)據(jù)域，左指針域，右指針域。兩個指針分別存儲左右孩子的結(jié)點的存儲地址。不存在時相應(yīng)指針域的值為空。二叉樹上任一結(jié)點的左子樹深度減去右子樹的差值稱為該結(jié)點的平衡因子，任意結(jié)點左右子樹的深度之差的絕對值<=1,稱為平衡二叉樹。二叉排序樹又稱二叉查找樹，它或者是一棵空樹，或者是具有下列性質(zhì)的二叉樹：（1）若左子樹不空，則左子樹上所有結(jié)點的值均小于它的根結(jié)點的值；（2）若右子樹不空，則右子樹上所有結(jié)點的值均大于它的根結(jié)點的值；（3）左、右子樹也分別為二叉排序樹；遍歷二叉樹：就是按照指定規(guī)則或者某條搜索路徑訪問樹中每一個結(jié)點，且每個結(jié)點均被并且僅被訪問一次。要求不破壞原來的數(shù)據(jù)結(jié)構(gòu)。就是將非線性的二叉樹中結(jié)點排列在一個線性序列上的過程。均為先左后右的規(guī)律可有：先（根）序遍歷、中（根）序遍歷和后（根）序遍歷哈夫曼樹：執(zhí)行路徑最短（算法效率最高）的二叉樹，又稱最優(yōu)二叉樹。為帶權(quán)路徑長度最短?！谌~子結(jié)點數(shù)目相同的二叉樹中，完全二叉樹或者滿二叉樹不一定是最優(yōu)二叉樹，最優(yōu)二叉樹也不一定是深度最小的二叉樹?；舅枷胧亲寵?quán)值最大的葉子離根最近。6.排序排列：是計算機(jī)內(nèi)經(jīng)常進(jìn)行的一種操作，其目的是將一組“無序”的記錄序列調(diào)整為“有序”的記錄序列。分內(nèi)部排序和尾部排序。內(nèi)部排序是指在排序的過程中，記錄全部存放在計算機(jī)的內(nèi)存里，并且在內(nèi)存里調(diào)整記錄之間的相對位置，沒有進(jìn)行、外存數(shù)據(jù)交換。外存排序為大文件排序，即待排序記錄存儲在外存儲器上。待排序記錄無法一次性裝入內(nèi)存，需多次數(shù)據(jù)交換。當(dāng)待排序記錄的關(guān)鍵字均不相同時，則排序結(jié)果是唯一的，否則排序結(jié)果不一定唯一。當(dāng)待排序記錄中存在多個關(guān)鍵字相同的記錄，經(jīng)過排序后這些具有相同關(guān)鍵字的記錄之間的相對次序保持不變，則稱這種排序方式是穩(wěn)定的，否則為不穩(wěn)定的。其中冒泡、插入、基數(shù)、歸并屬于穩(wěn)定排序，選擇、快速、希爾、堆屬于不穩(wěn)定排序。插入排序：分直接插入排序和希爾排序。直接插入排序：順序的將待排序的紀(jì)錄按照關(guān)鍵字的大小插入到已排序的紀(jì)錄子序列的恰當(dāng)位置。共需要n-1趟插入過程就可以將初始的n個記錄排序成按照關(guān)鍵字大小排列的有序序列。操作：前兩個比較排序，第三個按照大小直接插入前兩個排好的序列中形成三個的序列，第四個再根據(jù)大小直接插入前三個排好的序列中……最后直到最后一個記錄排好，完成。算法的事件復(fù)雜度為O（n^2）,空間復(fù)雜度來看，只需要一個記錄大小的輔助空間。（平穩(wěn)）希爾排序：又稱縮小增量排序，先將整個待排序的紀(jì)錄序列分割成若干個子序列分別進(jìn)行直接插入排序，待整個序列中的記錄基本有序時，再對全體記錄作一次直接插入排序。時間復(fù)雜度介于O（nlogn）和O（n^2）之間，（不平穩(wěn)）冒泡排序：將相鄰記錄的關(guān)鍵字進(jìn)行比較，若前面記錄的關(guān)鍵字大于（或小于）后邊記錄的關(guān)鍵字，則將他們交換位置。有n個記錄，需要n-1趟，每趟排序從最后一個記錄開始。操作：找出最大（或最小的）為初始關(guān)鍵字，再每趟一個依次按順序排列，未排列的數(shù)據(jù)不改變原來順序直接寫在后邊。時間復(fù)雜度為O（n^2），記錄的移動交換次數(shù)較多，時間性能不如插入排序。（穩(wěn)定）快速排序：目前已知的常用排序算法中最快的排序方法。通過不斷的比較關(guān)鍵字大小，以某一個記錄為樞軸（支點），將待排序序列分成兩個部分。其中一個部分滿足所有關(guān)鍵字都大于或者等于支點記錄的關(guān)鍵字，另一部分都小于等于。完成一次劃分。對各部分不斷劃分，直到整個序列按關(guān)鍵字排序為止。平均時間復(fù)雜度為O（nlogn）。（不穩(wěn)定）選擇排序：每一趟排序在待排序的序列中選出關(guān)鍵字最?。ㄗ畲螅┑挠涗?，再放在子序列的恰當(dāng)位置。分簡單選擇排序和堆排序。簡單選擇排序：先從全部n個待排序的序列中選出關(guān)鍵字最?。ㄗ畲螅┑挠涗洸⑺托蛄兄械牡谝粋€記錄進(jìn)行交換位置；然后從n-1個不包括第一個位置上的記錄中選擇關(guān)鍵字最小（最大）的記錄并將它和序列中的第二個記錄進(jìn)行交換位置；第i趟從n-i+1個不包括第一個位置上的記錄中選擇關(guān)鍵字最?。ㄗ畲螅┑挠涗洸⑺托蛄兄械牡趇個記錄進(jìn)行交換位置。如此反復(fù)經(jīng)過n-1趟選擇得有序序列。時間復(fù)雜度為O（n^2）。（不穩(wěn)定）堆排序：n個關(guān)鍵字序列Kl，K2，…，Kn稱為（Heap），當(dāng)且僅當(dāng)該序列滿足如下性質(zhì)（簡稱為堆性質(zhì)）：(1)ki<=k(2i）且ki<=k(2i+1)(1≤i≤n），當(dāng)然，這是小根堆，大根堆則換成>=號。//k(i）相當(dāng)于二叉樹的非葉結(jié)點，K(2i）則是左孩子，k(2i+1）是右孩子若將此序列所存儲的向量R[1..n]看做是一棵完全二叉樹的