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