02331-數據結構

4 minute read

Published:

第一章

  • 算法滿足輸入、輸出、有窮性、確定性和可行性
  • 評價算法優劣
    • 時間複雜性
    • 空間複雜性
    • 可讀性和可操作性

第三章 棧和隊列

  • 先進後出
  • a1,a2,,an
  • 棧頂TOP:an
  • 棧底BOTTOM:a1
  • 入出的也在棧頂
  • 出的元素順序an,,a1
  • 進棧: S.top+1
  • 退棧: S.top-1
  • 棧空: S.top=-1
  • 棧滿: S.top==stackSize-1

隊列

  • 先進先出

數組隊列

  • 空隊列時
    • font=0, rear=0
  • 非空隊列時
    • font是出隊,非空隊列font是有內容
    • rear是入隊,非空隊列rear是最後有內容的後一個位置,沒有內容
    Q-->data[Q-->rear]=x;
    Q-->rear=(Q-->rear+1) %n
    
    • 測滿: (Q-->rear+1) %n==(Q-->font)
  • 元素個數:

    n+rearfont(mod n)

    n為隊列長度

鏈隊列

  • 空隊列時
Q->font=head=Q->rear
head->next=Null
  • 非空隊列時
    • font的指針指向head,但head沒有內容
    • rear的指針指向隊尾,p->rear->data是有內容的

中綴表達和后綴表達

中綴表達式運算付棧OS (棧)后綴表達式(隊列)
9-(2+4*7)/5+3 ##
)/5+3#-(+*9347
/5+3#-9347*+
5+3#-/9347*+
+3#-/9347*+5
3#+9347*+5/-
#9347*+5/-3+
  • 總結兩個規則
  • ()集齊了,()內的符號退棧, 進棧到后綴中
  • 若下一個運算符號優先次序低於棧中, 先將運算棧中的全部運算符號退棧, 再將低優先次序的符號進棧

第四章 多維數組和廣義表

矩陣

  • m行,n
Am×n=[a0,0a0,n1am1,0am1,n1]

寫成

A=[[a0,0,...,a1,n1],...[am1,0,...,am1,n1]]
  • 按行(橫)存:

    a00,a01,,am1,n1 ai,j=a00+(ni+j)d
  • 按列(縱)存:

    a00,a1,0,,am1,n1 ai,j=a00+(mj+i)d
  • 對稱(存,n=m), 只存n(n+1)2,在ai,j順序來存, 它在k的位置

k={i(i+1)2+jij(lower triangle)j(j+1)2+ii<j(upper triangle)
  • 下三角矩陣, 即上三角(不包括對角綫)為常數
k={i(i+1)2+jijn(n+1)2i<j
  • 上三角矩陣, 即下三角(不包括對角綫)為常數
k={i(2ni+1)2+jiijn(n+1)2i>j
  • 稀疏矩陣
indexi (行號)j(列號)v(value)
0013
1035
212-2
3201
4246
5328
i (行號)第i行第一個非零的index第i行之前非零元素總數第i行上非零元素個數
0002
1221
2332
3551

廣義表

  • P.98
  • 空表: (),長度為0
  • (()),長度為1
  • C=(a,(b,c)),長度為2
  • (e,(e,(e,…)))為無限廣義表,深度為,長度為2
  • A=(a,(b,c,d),e,(f,g))
    • A的第一個元素,head(A)=a
    • A刪除第一個元素的廣義表,tail(A)=((b,c,d),e,(f,g))
  • 通常采用鏈式存儲結構, 可用一個結點表示
    • tag=0,表示為子表,用slink
    • tag=1,表示為結點,用data
    • link為下一個元素的指針
    tagdata/slinklink

第五章

二叉樹

  • i層,最多有2i1個結點
  • 深度為k的二叉樹,最多有2k1結點
  • 終端結點n0,度數為2的結點數為n2,
n0=n2+1
  • 完全二叉樹:深度為k的二叉樹, 在前k1層是滿樹,第k層的結點都在左邊。則有n結點的深度k
  • 分支結點即度不為0的結點。
k=logn+1ork=log(n+1)
  • P.113:從data[], 轉換成樹
void create (int* Data, int n)
{
  BinTNode *Q[100],*Bt=NULL,*p;
  int font=0;rear=0,k;
  for (k=0;k<n;k++)
  {
    p=NULL;
    if (data[k]!=0)
    {
      p=(BinTree)malloc(sizeof (BinTNode));
      p->data=data[k];
      p->lchild=p->rchild=NULL;
    }
    Q[rear++]=p;
    if (rear==1) Bt=p;
    else 
    {
      if (p!=NULL && Q[font]!=NULL)
      {
        if (rear%2==0) Q[font]->lchild=p;
        else Q[font]->rchild=p;
        if (rear%2==1) font++;

      }
    }
  }
}
  • 前序歷遍:根左右
  • 中序歷遍:左根右
  • 後序歷遍:左右根
  • 已知前序中序或中序後序確定二叉樹

  • 線二叉樹

    lchildltagDatartagrchild
ltag={0lchild指向左孩子1lchild指向前趨 rtag={0rchild指向右孩子1rchild指向后繼

這裏前趨後繼是根據前,中和後序其中一㮔排序算法,沒有特別指出,就假設是中序。

樹和森林

  • 樹變二叉樹:
    • 兄弟連成線, 只保留長子
  • 二叉樹變樹:a右結點與a父母連, 並斷與a連, 即與祖父母連, 但與父母斷關係
  • 樹前序:根,前序遍歷子樹(左子樹才到右)。變二叉樹後等價前序
  • 樹后序:后序遍歷子樹(右子樹才到左),根。變二叉樹後等價中序

哈夫曼樹

  • 最小兩個的比重做成一個, 代表原本的放入數列
  • 同复上術步驟
  • 比重大的一側為1,小的一則為0
  • 則可由經過的路徑組成編碼
  • n個字符的哈夫曼樹有結點2n1

第六章 圖

  • 無向圖邊數:en(n1)2
  • 無向圖邊數:e n(n1)
  • 連通圖:任意兩點都有連接
  • 任何n個頂點,任何情況下都是連通的, 則至少需多少邊?
(n1)(n2)223+1

搜索遍歷

  • 深度搜索遍歷(DFS):
    • 矩陣O(n2),鄰接表O(n+e)
    • 深度, 找深, 沒有更深時, 找最晚,但有支線是沒有歷遍
  • 廣度搜索遍歷(BFS):
    • 矩陣O(n2),鄰接表O(n+e)
    • 廣度,第一層已遍歷,跟第一層頂點次序遍歷第二層,如此類推

最小生成樹

  • 樹是無回路的連通圖
  • 極小連通子圖:若在圖中去掉一邊,會變成非連通。若加一邊,則有回路

Prim算法

  • 先選一點U=x
  • 再從已歸納的點集U中可伸展的邊,選出來, 並將這邊頂點歸納在U中,並重覆,直至U包括了所有的頂點
  • O(n2)
  • 圖G有n的頂點, 生出來的樹T的邊數是n1

Kruskal算法

  • 所有頂點在原處,選最小權的邊,直至成為連通圖

最短路徑

Dijkstra

  • 尋找某一點V0到其他點的最短路徑
  • 無路徑通往的頂點設為
  • 選連通權數最少又不在集合U中的頂點加入U,更新加入U後的有限路徑中選取權數最少的路徑
  • 重覆上述步驟, 直至U包括所有的頂點, 這時V0到其他頂點的最短路徑產生

拓扑排序

  • 入度為0的頂點, 輸出它,並刪除它與它的出線
  • 重覆以上動作,就找到排序
  • 排序不唯一

第七章 排序

相同紀錄,若排序時相對位置持保持,則稱為穩定

插入排序

  • 直接排序
    • A=a1 為以排序的,B=a2,,an 為未排序
    • B中與A最後的元素比較,比A小的才向前移動,直至不再比較小,將元素直接插入A,並向後移動比它大的,如此類推
    • i中,最多向後移動i+1次,最多比較i
    • 最好的情況O(n),最壞的情況O(n2),平均O(n2)
    • 空間O(1)
    • 穩定的
  • 希爾排序
    • d為增量序列
    • a1為數列第一項,不是a0,z設d1為間距,將數列分成

      {a1,a1+d1,a1+2d1}{a2,a2+d1,a2+2d1}
    • 在上述集合中進行直接排序

    • d2<d1,重覆上述

      {a1,a1+d2,a1+2d2}{a2,a2+d2,a2+2d2}
    • 最後隔距dl=1
    • n很大時,比直接排序時間和移動少很多,
    • 移動和比較次數約為n1.251.6n1.25
    • 不穩定的,因為d會令相同數值的後面的元素向前移動

交換排序

  • 冒泡排序
    • 從後到前,有後比前小的交換,第一個出來的一定是最少
    • 如此類推,直至排序完成
    • 若第一趟沒有置換,則排序完成
    • 最好的情況O(n),最壞的情況O(n2),平均O(n2)
    • 穩定的
  • 快速排序
    • B=a1為基準
    • i=1,j=n
    • for some biggest jb ajb<B for some biggest j,

      ai=ajbj=jbi=i+1
    • for some smallest is ais>B for some smallest i,

      aj=aisi=isj=j+1
    • 不穩定的,因為i,j互換數值
    • 平均時間O(nlog2n),排序已為有序時,第一趟只固定a1的位置,但還有a2,an1,所以時間O(n2)
    • 空間時間O(nlog2n),棧最大深度為nlog2n+1

選擇排序

  • 直接選擇:
    • 從中選出最小的與a1交換,如此類推
    • 平均時間O(n2)
    • 不穩定
  • 堆排序
    • 數列變二叉樹,根->左->右->左左->左右
    • 從最底開始置換,最大堆,即倒序,孩子必須小於父母,不然就置換
    • 從第一棵樹中選出根,其餘再組成最大堆,再取根
    • 樹的排序的時間O(nlog2n),並n1棵樹,所以時間O(nlog2n)
    • 不穩定
    • 小根堆 k2i+1,k2i+2kiin2,降序
    • 大根堆,升序

歸並排序

  • 每一個元素為一組,相鄰的合並,並排序,
  • 第一趟後,有n2的組別,如此類推
  • 每一趟的排序的時間O(n),並需要log2n趟,所以時間O(nlog2n)
  • 穩定

分配排序

  • 箱排序/基數排序
    • 先將數字用個位數排序
    • 排序後再十位數排序
    • 如此類推
    • r為箱數,上例為10,d為趟數,上例為2
    • 初始化和分配n個鏈表為O(n),清空和收集箱子時間為 O(rd),共d
    • 時間為O(d(rd+n))

內部排序比較

  • 時間複雜
    1. 直接插入、直接選擇、冒泡為O(n2)
    2. 快速、歸並、堆排為O(nlog2n)
    3. 希爾O(nlog2n)n1.25
    4. 基數O(d(rd+n))
  • 穩定
    • 直接插入、冒泡、歸並和基數為穩定
    • 直接選擇、希爾、堆排和快速為不穩定
  • 空間複雜
    • 快速O(log2n)
    • 歸並O(n)
    • 直接插入、直接選擇、冒泡、希爾和堆排O(1)
  • link

第八章 查找

順序查找

  • 平均查找長度,Pi概率,Ci列表中第i個元素
ASL=PiCi
  • 順序查找
  • 二分查找: 要順序排序
  • 索引順序查找:又稱分塊查找;塊間有序,塊內無序

樹表查找

B樹

  • m3階樹
(m,p0,k1,p1,k2,,km,pm)
  • 每棵樹至多有m棵子樹
  • 若樹為非空,根結點至少有1個關鍵字,至多有m1個關鍵字。
  • 所有葉結點都在同一層上,並且不帶信息
  • 關鍵字個數 m21nm1
  • 除結點外, 結點有子樹m2nm
  • 注意,通常關鍵字的數量為m時, 因為包頭尾,子樹數量為m+1
  • P.209:生成、插入和刪除過程需要了解

B+樹

  • 是B樹的變型樹
  • k個孩子就有k個關鍵字
  • 葉結點中包含了關鍵字的信息及指向相應的指針,且葉子結點本身依照關鍵字的大小自小到大順序鏈接
  • 所有非終結點可看成索引部分, 結點中僅含其子樹中最大或最小的關鍵字
(m,k1,p1,k2,,km,pm)
  • k1的子樹
((k11,p1),(k1,p2))
  • 沒有子樹的最大值比根的最大值大

散列表查找

  • P.215
  • 處理沖突的方法
    • 開放定址法:線性探插法、二次探查法和雙重散列法,
      • 沿著序列逐個單元進行查找,直到空為止
    • 拉鏈法:鏈表
  • 上面的要計算平均查找長度ASL

考試常見名詞

  • 數據項是具有獨立含義的最小標識單位
  • 算法滿足輸入、輸出、有窮性、確定性和可行性
  • 數據的四種基本存儲方法是順序,鏈接,索引和散列存儲
  • 數據結構是數據的邏輯結構和儲存結構
  • 遞歸函數
  • 遞歸的最小子問題稱遞歸終止條件
  • 有向無環圖
  • 父結點或兄弟
  • 裝填因子,大則發生沖突機率大
  • 儲存地址
  • 帶權路徑長度
  • 最小生成樹
  • 極小連通圖
  • 順序存儲結構
  • 基數大小
  • 分塊查找索引查找
  • 數據的運算,即對數據元素施加的操作, 是定義在數據的邏輯結構
  • 三元組表
  • 索引查找
  • 線索取代空指針
  • 無序數組用順序查找
  • 數據邏輯結構是從邏輯關係上描述數據,它與數據的存儲無關
  • 散列存儲,解決沖突方法有開放地址法拉鏈法
  • 頂點表示活動,邊表示活動間的先後關係,稱頂點活動網(AOV)
  • 借助一個棧來實現圖的遍歷遍算法是深度遍歷
  • 若有向圖中存在排序序列,則一定不存在回路
  • 最短路徑Dijkstria,最小生成樹Prim,Kruskal
  • 隊尾加元素,在隊頭減元素
  • 二分查找是順序查找結構, 按關鍵字有序
  • 分塊查找, 先查索引表,再找相應的
  • 平均查找長度與結點無關的查找方法是散列查找
  • 三種查找方法: 樹表, 順序和散列
  • Dijkstra 算法是按照路徑: 長度不減的次序求出各條路徑的
  • 一個連通圖的生成樹是包含圖中所有頂點的極小連通子圖
  • 箱排序的改進和推廣的算法是基數排序
  • 長度為1的廣義表,若有Head(A)=Tail(A),則A=(())