02331-數據結構
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+rear−font(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列
寫成
A=[[a0,0,...,a1,n−1],...[am−1,0,...,am−1,n−1]]按行(橫)存:
a00,a01,…,am−1,n−1 ai,j=a00+(n∗i+j)∗d按列(縱)存:
a00,a1,0,…,am−1,n−1 ai,j=a00+(m∗j+i)∗d對稱(存,n=m), 只存n∗(n+1)2,在ai,j順序來存, 它在k的位置
- 下三角矩陣, 即上三角(不包括對角綫)為常數
- 上三角矩陣, 即下三角(不包括對角綫)為常數
- 稀疏矩陣
index | i (行號) | j(列號) | v(value) |
---|---|---|---|
0 | 0 | 1 | 3 |
1 | 0 | 3 | 5 |
2 | 1 | 2 | -2 |
3 | 2 | 0 | 1 |
4 | 2 | 4 | 6 |
5 | 3 | 2 | 8 |
i (行號) | 第i行第一個非零的index | 第i行之前非零元素總數 | 第i行上非零元素個數 |
---|---|---|---|
0 | 0 | 0 | 2 |
1 | 2 | 2 | 1 |
2 | 3 | 3 | 2 |
3 | 5 | 5 | 1 |
廣義表
- 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為下一個元素的指針
tag data/slink link
第五章
二叉樹
- 在i層,最多有2i−1個結點
- 深度為k的二叉樹,最多有2k−1結點
- 終端結點n0,度數為2的結點數為n2,
- 完全二叉樹:深度為k的二叉樹, 在前k−1層是滿樹,第k層的結點都在左邊。則有n結點的深度k
- 分支結點即度不為0的結點。
- 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++;
}
}
}
}
- 前序歷遍:根左右
- 中序歷遍:左根右
- 後序歷遍:左右根
已知前序中序或中序後序確定二叉樹
線二叉樹
lchild ltag Data rtag rchild
這裏前趨後繼是根據前,中和後序其中一㮔排序算法,沒有特別指出,就假設是中序。
樹和森林
- 樹變二叉樹:
- 兄弟連成線, 只保留長子
- 二叉樹變樹:a右結點與a父母連, 並斷與a連, 即與祖父母連, 但與父母斷關係
- 樹前序:根,前序遍歷子樹(左子樹才到右)。變二叉樹後等價前序
- 樹后序:后序遍歷子樹(右子樹才到左),根。變二叉樹後等價中序
哈夫曼樹
- 最小兩個的比重做成一個, 代表原本的放入數列
- 同复上術步驟
- 比重大的一側為1,小的一則為0
- 則可由經過的路徑組成編碼
- n個字符的哈夫曼樹有結點2n−1個
第六章 圖
- 無向圖邊數:e≤n(n−1)2
- 無向圖邊數:e≤ n(n−1)
- 連通圖:任意兩點都有連接
- 任何n個頂點,任何情況下都是連通的, 則至少需多少邊?
搜索遍歷
- 深度搜索遍歷(DFS):
- 矩陣O(n2),鄰接表O(n+e)
- 深度, 找深, 沒有更深時, 找最晚,但有支線是沒有歷遍
- 廣度搜索遍歷(BFS):
- 矩陣O(n2),鄰接表O(n+e)
- 廣度,第一層已遍歷,跟第一層頂點次序遍歷第二層,如此類推
最小生成樹
- 樹是無回路的連通圖
- 極小連通子圖:若在圖中去掉一邊,會變成非連通。若加一邊,則有回路
Prim算法
- 先選一點U=x
- 再從已歸納的點集U中可伸展的邊,選出來, 並將這邊頂點歸納在U中,並重覆,直至U包括了所有的頂點
- O(n2)
- 圖G有n的頂點, 生出來的樹T的邊數是n−1
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.25−1.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+1for some smallest is ais>B for some smallest i,
aj=aisi=isj=j+1- 不穩定的,因為i,j互換數值
- 平均時間O(nlog2n),排序已為有序時,第一趟只固定a1的位置,但還有a2,…an−1,所以時間O(n2)
- 空間時間O(nlog2n),棧最大深度為⌈nlog2n⌉+1
選擇排序
- 直接選擇:
- 從中選出最小的與a1交換,如此類推
- 平均時間O(n2)
- 不穩定
- 堆排序
- 數列變二叉樹,根->左->右->左左->左右
- 從最底開始置換,最大堆,即倒序,孩子必須小於父母,不然就置換
- 從第一棵樹中選出根,其餘再組成最大堆,再取根
- 樹的排序的時間O(nlog2n),並n−1棵樹,所以時間O(nlog2n)
- 不穩定
- 小根堆 k2i+1,k2i+2≥kii≤⌈n2⌉,降序
- 大根堆,升序
歸並排序
- 每一個元素為一組,相鄰的合並,並排序,
- 第一趟後,有⌈n2⌉的組別,如此類推
- 每一趟的排序的時間O(n),並需要log2n趟,所以時間O(nlog2n)
- 穩定
分配排序
- 箱排序/基數排序
- 先將數字用個位數排序
- 排序後再十位數排序
- 如此類推
- r為箱數,上例為10,d為趟數,上例為2
- 初始化和分配n個鏈表為O(n),清空和收集箱子時間為 O(rd),共d趟
- 時間為O(d(rd+n))
內部排序比較
- 時間複雜
- 直接插入、直接選擇、冒泡為O(n2)
- 快速、歸並、堆排為O(nlog2n)
- 希爾O(nlog2n) 或n1.25
- 基數O(d(rd+n))
- 穩定
- 直接插入、冒泡、歸並和基數為穩定
- 直接選擇、希爾、堆排和快速為不穩定
- 空間複雜
- 快速O(log2n)
- 歸並O(n)
- 直接插入、直接選擇、冒泡、希爾和堆排O(1)
- link
第八章 查找
順序查找
- 平均查找長度,Pi概率,Ci列表中第i個元素
- 順序查找
- 二分查找: 要順序排序
- 索引順序查找:又稱分塊查找;塊間有序,塊內無序
樹表查找
B樹
- m≥3階樹
- 每棵樹至多有m棵子樹
- 若樹為非空,根結點至少有1個關鍵字,至多有m−1個關鍵字。
- 所有葉結點都在同一層上,並且不帶信息
- 關鍵字個數 ⌈m2⌉−1≤n≤m−1
- 除結點外, 結點有子樹⌈m2⌉≤n≤m
- 注意,通常關鍵字的數量為m時, 因為包頭尾,子樹數量為m+1
- P.209:生成、插入和刪除過程需要了解
B+樹
- 是B樹的變型樹
- 有k個孩子就有k個關鍵字
- 葉結點中包含了關鍵字的信息及指向相應的指針,且葉子結點本身依照關鍵字的大小自小到大順序鏈接
- 所有非終結點可看成索引部分, 結點中僅含其子樹中最大或最小的關鍵字
- 如k1的子樹
- 沒有子樹的最大值比根的最大值大
散列表查找
- P.215
- 處理沖突的方法
- 開放定址法:線性探插法、二次探查法和雙重散列法,
- 沿著序列逐個單元進行查找,直到空為止
- 拉鏈法:鏈表
- 開放定址法:線性探插法、二次探查法和雙重散列法,
- 上面的要計算平均查找長度ASL
考試常見名詞
- 數據項是具有獨立含義的最小標識單位
- 算法滿足輸入、輸出、有窮性、確定性和可行性
- 數據的四種基本存儲方法是順序,鏈接,索引和散列存儲
- 數據結構是數據的邏輯結構和儲存結構
- 遞歸函數
- 遞歸的最小子問題稱遞歸終止條件
- 有向無環圖
- 父結點或兄弟
- 裝填因子,大則發生沖突機率大
- 儲存地址
- 帶權路徑長度
- 最小生成樹
- 極小連通圖
- 順序存儲結構
- 基數大小
- 分塊查找索引查找
- 數據的運算,即對數據元素施加的操作, 是定義在數據的邏輯結構
- 三元組表
- 索引查找
- 線索取代空指針
- 無序數組用順序查找
- 數據邏輯結構是從邏輯關係上描述數據,它與數據的存儲無關
- 散列存儲,解決沖突方法有開放地址法和拉鏈法
- 頂點表示活動,邊表示活動間的先後關係,稱頂點活動網(AOV)
- 借助一個棧來實現圖的遍歷遍算法是深度遍歷
- 若有向圖中存在排序序列,則一定不存在回路
- 最短路徑Dijkstria,最小生成樹Prim,Kruskal
- 在隊尾加元素,在隊頭減元素
- 二分查找是順序查找結構, 按關鍵字有序
- 分塊查找, 先查索引表,再找相應的塊
- 平均查找長度與結點無關的查找方法是散列查找
- 三種查找方法: 樹表, 順序和散列
- Dijkstra 算法是按照路徑: 長度不減的次序求出各條路徑的
- 一個連通圖的生成樹是包含圖中所有頂點的極小連通子圖
- 箱排序的改進和推廣的算法是基數排序
- 長度為1的廣義表,若有Head(A)=Tail(A),則A=(())