寫在前面
為迎接期末，總結了下知識點，供個人複習使用，僅供參考。
本文用到的複習資料：點我跳轉，提取碼：6q5q
若需要本文markdown檔案下方評論留言看到即回
緒論
知識點
1.邏輯結構：資料之間的互相關系。（與計算機無關）
- 集合 結構中的資料元素除了同屬于一種類型外，别無其它關系。
- 線性結構 資料元素之間一對一的關系
- 樹形結構 資料元素之間一對多的關系
- 圖狀結構或網狀結構 結構中的資料元素之間存在多對多的關系
也可分為線性結構(可了解成一條直線能串起來)和非線性結構
2.存儲結構分為順序存儲結構和鍊式存儲結構（散列、索引） （與計算機有關）
3.算法五個特性： 有窮性、确定性、可行性、輸入、輸出
4.算法設計要求：正确性、可讀性、健壯性、高效性。 (好的算法)
5.typedef可以了解成給現有資料類型起個别名
例如：typedef struct{…}SqList，即給struct{…}起了個名字叫SqList
也用于類似于typedef int ElemType; 給int 起個别名叫ElemType即ElemType a;等價于int a;
這樣做的好處是代碼中用ElemType定義變量，如果想修改變量類型隻需修改typedef ** ElemType即可，而不用一一修改。
我們注意到有時候會有typedef struct LNode{…}LNode，即struct後有個LNode,這是因為如果結構體内部有指向結構體的指針則必須在struct後面加上LNode(單連結清單裡有next指針struct LNode *next)
6.時間複雜度：基本操作的執行次數（可以了解成就看執行了多少次）
7.研究資料結構就是研究資料的邏輯結構、存儲結構及其基本操作
8.抽象資料類型的三個組成部分為資料對象、資料關系、基本操作。
9.資料：描述客觀事物的符号
資料元素：是資料的基本機關（元素、結點）
資料項：組成資料元素的最小機關 （如學生資訊表中的學号、姓名等）
資料對象：相同性質的資料元素的集合（如大寫字母）
大小關系為：資料=資料對象 > 資料元素 > 資料項
10.資料結構：互相之間存在一種或多種特定關系的資料元素的集合
11.資料的運算包含：插入、删除、修改、查找、排序
12.算法：解決某類問題而規定的一個有限長的操作序列
13.算法的空間複雜度：算法在運作時所需存儲空間的度量
習題
1.通常要求同一邏輯結構中的所有資料元素具有相同的特性， 這意味着( B )。
A. 資料具有同一特點
B. 不僅資料元素所包含的資料項的個數要相同， 而且對應資料項的類型要一緻
C. 每個資料元素都一樣
D. 資料元素所包含的資料項的個數要相等
2.以下說法正确的是( D )。
A. 資料元素是資料的最小機關
B. 資料項是資料的基本機關
C. 資料結構是帶有結構的各資料項的集合
D. 一些表面上很不相同的資料可以有相同的邏輯結構
答：資料元素是資料的基本機關，資料項是資料的最小機關，資料結構是帶有結構的各資料元素的集合
3.算法的時間複雜度取決于（ D ）。
A．問題的規模 B．待處理資料的初态 C．計算機的配置 D． A 和 B
答：肯定與問題規模(難和簡單的問題)有關，不過也與初态有關，比如某些排序算法，若初始已經排好序可能時間複雜度就會降低。
4.下列算法時間複雜度為
count=0;
for(k=1;k<=n;k*=2)
for(j=1;j<=n;j+=1)
count++;
答：最外層循環數值為20,21,22…是以假設執行m次即2m=n是以外層執行了log2n次
内層執行了n次，是以時間複雜度為nlog2n（可了解為log2n個n相加）
int fact(int n){
if(n<=1) return 1;
return n*fact(n-1);
}
答：第一次是n*fact(n-1)，然後是n*(n-1)*fact(n-2)…一直到n(n-1)(n-2)…2*1
但是我們要看執行了多少次，也就是函數fact調用了多少次，從n到1也就是n次，是以時間複雜度為O(n)
線性表
知識點
1.線性結構：第一個無前驅，最後一個無後繼，其他都有前驅和後繼
2.順序表插入一個元素平均移動n/2個元素，删除平均移(n-1)/2個
插入的那一位置需要向後移，删除的位置那一位不用移(直接覆寫)是以删除少1
3.首元結點：存儲第一個有效資料元素的結點
頭結點：首元結點之前指向首元結點的結點，為處理友善而設
頭指針：指向第一個結點(有頭結點指頭結點沒有指首元結點)的指針
單連結清單通常用頭指針命名
4.随機存取：可以像數組一樣根據下标直接取元素
順序存取：隻能順藤摸瓜從前往後一個一個來
5.單連結清單加一個前驅指針prior就變成了雙向連結清單
6.單連結清單最後一個元素的next指針指向第一個結點即為循環連結清單 (屬于線性表！)
7.線性表和有序表合并的時間複雜度
線性表的合并時間複雜度為O(m*n)
A=(7,5,3,11)，B=(2,6,3)，結果為A=(7,5,3,11,2,6)
算法需要循環周遊B(O(n))且LocateElem(A)(判斷是否與B重複為O(m))是以為O(m*n)
有序表的合并時間複雜度為O(m+n)
A=(3,5,8,11)，B=(2,6,8)，結果為A=(2,3,5,6,8,11)
算法隻需同時周遊A和B，然後将還沒周遊完的那個直接插到最後就行，是以是相加
8.順序表和單連結清單的比較
9.單連結清單也是線性表(一對一的關系，用繩子可以穿起來)的一種
10.順序表存儲密度(資料占比/結點占比)等于1，單連結清單的小于1(因為要存指針)
習題
1.線性表隻能用順序存儲結構實作 （X）也可用鍊式如單連結清單
2.在雙向循環連結清單中，在 p指針所指的結點後插入 q所指向的新結點，其修改指針的操作是（ C ）。
A. p->next = q; q->prior = p; p->next->prior = q; q->next = q;
B. p->next = q; p->next->prior = q; q->prior=p; q->next = p->next;
C. q->prior = p; q->next = p->next; p->next->prior = q; p->next = q;
D. q->prior = p; q->next = p->next; p->next = q; p->next->prior = q;
答：這樣的題隻能畫圖看看對不，但是我們可以看到在p的後面插入，那麼p->next就不能非常早的更改否則就會出現找不到的情況，是以排除A,B。C和D畫個圖試下
3.在一個有127個元素的順序表中插入一個新元素并保持原來順序不變，平均要移動的元素個數為（ B）。
A. 8 B. 63.5 C. 63 D. 7
答：插入平均移動n/2即63.5，注意不用取整
棧和隊列
知識點
1.棧和隊列是操作受限的線性表（1對1）
2.棧後進先出，隻能在棧頂(表尾)插入删除
3.隊列先進先出，隊頭删除，隊尾插入(和平常排隊一樣排後面)
4.順序棧棧空時：S.top=S.base 棧頂指針等于棧底指針
棧滿時：S.top-S.base=S.stacksize 棧頂-棧底等于最大空間
5.鍊棧在棧頂操作，用連結清單頭部作為棧頂即可，不需要頭結點
棧空：S=NULL (指向第一個結點的指針為空)
6.棧的應用：括号比對，表達式求值(中綴式求值)，遞歸轉非遞歸、函數調用
7.中綴表達式：符号在中間，如a+b，字首就是+ab（字首中綴指的是符号的位置）
8.循環隊列隊空：Q.front=Q.rear
隊滿：(Q.rear+1)%MAXSIZE==Q.front
隊列元素個數：(Q.rear-Q.front+MAXSIZE)%MAXSIZE
入隊：Q.rear=(Q.rear+1)%MAXSIZE
出隊：Q.front=(Q.front+1)%MAXSIZE
習題
1.若一個棧以向量V[1…n]存儲，初始棧頂指針 top設為n+1, 則元素x進棧的正确操
作 是（ C ）。
A. top++; V[top]=x; B. V[top]=x; top++; C. top–; V[top]= x; D. V[top]=x; top–;
答：注意初始top為n+1，而存儲下标為v[1]~v[n]，是以就不存在ABD中的v[n+2]或者v[n+1]。應該先讓top減一使得指向最後一個位址v[n]，可以把它看成是倒過來的棧，然後存v[n-1]，v[n-2]…
2.用連結方式存儲的隊列，在進行删除運算時（ D ）。
A. 僅修改頭指針 B. 僅修改 尾指針 C. 頭、尾指針都要修改 D. 頭、尾指針可能都要修改
答：由于隻能在隊頭删除，一般隻需修改頭指針(head=head->next)即可。但當删最後一個元素時(此時head=rear)删除後(delete p)尾指針就丢失了也得修改
3.一個遞歸算法必須包括( B )。
A. 遞歸部分 C. 疊代部分 B. 終止條件和遞歸部分 D. 終止條件和疊代
答：算法有窮形是以都得有終止條件，遞歸算法那肯定得有遞歸部分
4.最不适合用作隊列的連結清單是( A )。
A.隻帶隊首指針的非循環雙連結清單 B.隻帶隊首指針的循環雙連結清單
C.隻帶隊尾指針的循環雙連結清單 D.隻帶隊尾指針的循環單連結清單
答：就看找頭尾指針好不好找，A隻有頭指針還非循環隻能從頭到尾周遊找到尾指針
5.表達式a*(b+c)-d的字尾表達式是( B )。
A. abcd*± B. abc+*d- C. abc*+d- D. -+*abcd
答：字首字尾指的是運算符号位置，先看原運算順序，先算(b+c)字尾表達式是bc+
原式然後算*，a*(bc+)字尾表達式是abc+*，然後是abc+*d-
6.已知循環隊列存儲在一維數組A[0…n-1]中，且隊列非空時front和rear分别指向隊頭元素和隊尾元素。若初始時隊列為空，且要求第1個進入隊列的元素存儲在A[0]處，則初始時front和rear的值分别是（ B ）。
A.0，0 B.0，n-1 C.n-1，0 D.n-1，n-1
答：平常入隊時先在rear位置指派，再把rear+1，即rear指向的是隊尾元素的下一位置，是以入隊時先指派再加一。但是此題說的是rear指向隊尾。也即第一個入隊後隊尾指向的是第一個元素的位置也即0，是以入隊前rear那就是0前面的n-1而front預設都為0
串、數組和廣義表
知識點
1.求next數組和nextval數組
當j=1(即第一個字元)時為特殊情況next和nextval均為0
1️⃣ next數組：其值為目前字母前方的最大前字尾+1
例如：j=3(A)，前面有A，B。沒有前字尾即為0，0+1=1
j=4(B)，前面有ABA，有字首和字尾A，即前字尾為1，1+1=2
j=5(A)，前面有ABAB，前字尾為AB，2+1=3 //ABA和BAB不等，是以AB為最大前字尾
next[j]=k,它的意思是，當模式串的第j位與主串的第i位失配時，這時主串的位置不回退，而是将模式串退到第k位，再次與主串的第i位進行比對。
比如主串為ABAA，不比對時next[4]=2，将模式串中的2位置即B與主串的最後A比較也就達到了不比對時直接根據前字尾移動的目的
2️⃣ nextval數組：兩種情況
若是不比對就看next[j]數值，若目前字母和next[j]字母不等時，nextval等于上面落下來的next[j]
若是不比對就看next[j]數值，若目前字母和next[j]字母相等時，nextval值為前面的那個nextval[]
不等就用自家的，相等直接拿過來
例如：j=2，next[2]為1表不比對時退到下标為1的位置，1的位置是A和目前2對應的B不等用自家的是以next[2]落下來成為nextval[2]
j=3，next[3]=1表不比對時模式串回退到下标為1的位置，1的位置是A和目前3對應的A相等，是以把前面的nextval數值拿過來即為nextval[3]
2.行優先和列優先
其實就是行優先就是從上到下先一行一行的存，列優先就是從左到右一列一列的存
無論是哪個其元素如a[2][3]位置不變(但順序變了)，行優先就是先存上面2行再到它，列優先就是先存左面3列再存它
3.廣義表是線性表的推廣，也稱清單（暫時了解成python裡的清單）
4.廣義表元素可為原子或子表
廣義表長度：即元素個數(最外層括号裡的小括号算一個元素)
廣義表深度：就看有多少對括号就行(注意要将裡面的子表全部展開)
5.表頭(Head)和表尾(Tail)：當表非空時，第一個元素為表頭其餘均為表尾
注意表頭是第一個元素是以不帶最外層的那個括号，表尾帶最外層的括号
例如A=((a,b),c)，表頭為(a,b)而表尾為(c)
6.串的子串個數為n(n+1)/2+1（1+1+2+…+n，空串也算是以加1）
7.主串長度為n，模式串長度為m，KMP算法時間複雜度為O(m+n)
習題
1.求子串數目
2.串 “ababaabab” 的 nextval 為（A）
A. 010104101 B. 010102101 C. 010100011 D0101010
3.設有數組 A[i,j], 數組的每個元素長度為 3 位元組， i 的值為 1~8 , j的值為 1~10 ,
數組從記憶體首位址 BA 開始順序存放， 當用以列為主存放時， 元素 A[5,8]的存儲首位址為（B）
A. BA+ 141 B. BA+ 180 C. BA+222 D. BA+225
答：以列為主那就是一列一列的存，[5,8]表示這是第8列，前面有7列是存滿的，是以這是第(7*8)+5=61個元素，而其位址為BA+(61-1)*3=BA+180
注意要不要減1的問題，可先試下，假如是第二個元素隻需要加一倍的3即BA+3是以要減1
4.二維數組 A 的每個元素是由 10 個字元組成的串，其行下标 i=0,1, …,8，列下标j=1,2, , ,10 。若 A 按行先存儲，元素 A[8,5] 的起始位址與當 A 按列先存儲時的元素（B）的起始位址相同。設每個字元占一個位元組。
A． A[8,5] B ． A[3,10] C. A[5,8] D ． A[0,9]
答：一定要注意下标是否從0開始，這裡共有9行
行優先，[8,5]前面有8行(0,1,2,3,4,5,6,7共8行)是以是第8*10+5=85個元素
列優先，[3,10]前面有9列，是以是第9*9+4=85個元素 （注意行标從0開始）
計算總數記住行乘列，列乘行
5.廣義表 ((a,b,c,d)) 的表頭是（ C ），表尾是（ B ）
A． a B ． ( ) C． (a,b,c,d) D． (b,c,d)
答：第一個元素為表頭其餘均為表尾，是以表尾要帶個外層的括号
6.設廣義表 L=((a,b,c)) ，則 L 的長度和深度分别為（ 1和2 ）。
答：長度就看有多長(元素個數)，深度就看有多深（括号層數）
7.以行序為主序方式，将n階對稱矩陣A的下三角形的元素(包括主對角線上所有元素)依次存放于一維數組B［1…(n(n+1))/2-1］中，則在B中确定aij (i<j) 的位置k的關系為( B ) 。
A.i*(i-1)/2+j B.j*(j-1)/2+i C.i*(i+1)/2+j D.j*(j+1)/2+i
答：注意題目說的是确定aij (i<j) ，i要小于j，但存的是下三角元素，假如a13=5，确定a13的位置就是确定5的位置，而a13=a31也就是根據i,j (i=1,j=3) 确定a31的位置，B中代入即3*1+1=4，而a31位置正是4(前面是1+2)
樹和二叉樹
知識點
1.滿二叉樹(最完美最滿的狀态) 完全二叉樹(編号是連續的即最右面缺而且是最後一層缺)
完全二叉樹度為1的結點個數為0或1
目前結點編号為i，它的左孩子編号為2i，右孩子為2i+1（從1開始時）
2.二叉樹常用性質
- n0 = n2+1 即葉子節點個數為度為2的結點個數加1
- 有 n 個結點的完全二叉樹的深度為⎣log2 n⎦+1 (沒記住可以一個一個試)
- 深度為k的二叉樹最多有2k-1個結點(滿二叉樹)
3.二叉樹周遊
- 先序周遊NLR：根節點->左子樹->右子樹。
- 中序周遊LNR：左子樹->根節點->右子樹。必須要有中序周遊才能畫出相應二叉樹
- 後續周遊LRN：左子樹->右子樹->根節點。
- 助記：先後中周遊指的是根結點在先還是中還是右，且時間複雜度均為O(n)
- 層次周遊：一層一層從上到下，從左到右
4.二叉樹線索化目的是加快查找結點的前驅或後繼的速度。實質上就是周遊一次二叉樹，檢查目前結點左，右指針域是否為空，若為空，将它們改為指向前驅結點或後繼結點
5.哈夫曼樹即帶權路徑最短樹，也稱最優樹。
樹的帶權路徑長度=樹根到各葉子結點的路徑(樹根到該結點要走幾步)乘對應權值；通常記作 WPL=∑wi×li
6.哈夫曼編碼是最優字首編碼(任一個編碼都不是其他編碼的字首，便于通信減少資料傳輸)
哈夫曼樹沒有度為1的結點，且不一定是完全二叉樹
7.樹的存儲結構有三種:雙親表示法、孩子表示法、孩子兄弟表示法,其中孩子兄弟表示法是最常用的表示法,任意一棵樹都能通過孩子兄弟表示法轉換為二叉樹進行存儲。
8.含有n個節點的二叉樹共有(2n)!/(n!*(n+1)!) (常考3個節點共5種)
9.二叉樹的高度是最大層次數(根節點為第一層)
10.樹和二叉樹均可以為空(注意樹可為空是在嚴蔚敏教材中可空，有的地方規定不能為空)
11.樹的先序對應二叉樹的先序，樹的後序對應二叉樹的中序(這裡的二叉樹一般指經孩子兄弟法轉換的樹)
12.哈弗曼樹屬于二叉樹有左右子樹之分
習題
1.
答：n0= n2+1 n1=0或n1=1 n0+n1+n2=1001
**2.**注意題目說的是存儲樹，而樹的存儲結構中，孩子兄弟表示法又稱二叉連結清單表示法
3.在一顆度為4的樹T中，若有20個度為4的結點，10個度為3的結點，1個度為2的結點，10個度為1的結點，則樹T的葉結點個數是______82_。
答：任何樹中，分支數(度數之和)比節點數少1
題目中，分支數為20*4+10*3+1*2+10*1=122，是以有123個節點
度為0的節點為123-20-10-1-10=82
也可用公式n0=1*n2+2*n3+3*n4+1=1+2*10+3*20+1=82
**4.**設哈夫曼樹中有199 個結點,則該哈夫曼樹中有_100__個葉子結點
答：哈弗曼樹沒有度為1的結點,n0=n2+1,n0+n2=199,是以n0=100
**5.**一棵高度為4的完全二叉樹至少有______8_個結點
答：前三層是滿二叉樹，最後一層隻有一個即1+2+4+1=8
6.
後是左右根，是以C是根，根據中序(左根右)得到DEBA均是C左子根
根據後序的DABE得到E是DABE的根，再由中序的DEBA得到D是E的左字根，BA是E的右子根
後序是左右根是AB，而中序是左根右是BA，正好相反則當沒有左時正好是右根和根右，即B是根A是右
7.一顆高度為h的完全二叉樹至少有_____2h-1__個結點
答：最少的情況就是前h-1層是滿的，第h層隻有一個。
即2h-1-1(前h-1層)+1(第h層)
8.有n個結點，高度為n的二叉樹的數目為_____2n-1__
答：結點數和高度相同，那麼每層都隻有一個結點。對于除根節點以外的結點都可能是左子樹或右子樹，即有兩種可能，n-1個2相乘即為2n-1
9.二叉樹周遊
注意中序先通路C的左而不是先通路W的左
10.樹與森林之間的轉換（左孩子右兄弟）
11.隻要LTag為1表明線索為真即它肯定沒左子樹，為0表示一定有左子樹
圖
知識點
1.完全圖：任意兩個頂點都有邊，都可達，有向完全圖的邊數(n*(n-1))是無向完全圖的2倍
2.子圖：一個圖的一部分稱為其子圖
3.回路或環：簡單來說就是轉個圈
4.簡單回路：轉圈的過程不能有重複的點
5.連通圖：圖的每兩個頂點都有一個到另一個的路徑，若都互相可達就是強連通(不一定是完全圖)
6.生成樹：含圖的全部頂點但隻有n-1條邊而且是連通圖(就是用線串起來所有頂點)
7.鄰接矩陣存儲圖，若沒權值1代表有邊，0代表沒邊。若有權值，有邊存權值，沒邊存無窮大
8.圖中度數之和為邊數之和的2倍(一條邊被兩個頂點共用是以是2倍)
9.完全圖要求每兩個頂點都有一條邊(無向時)，連通圖隻要求兩個頂點之間存在路徑就行(可能是多條邊)
10.深度優先(DFS)即越深越好,直到不能再深了這時退到上一層繼續深度優先。類似先序借助于棧(遞歸)
廣度優先(BFS)就是越廣越好類似層次周遊，而且先被通路的節點其子節點也先被通路。借助于隊列(存放被通路的結點)
廣度和深度若用鄰接矩陣實作時間複雜度為O(n2)，鄰接表是O(n+e)即O(頂點+邊)
層次周遊就是一層一層從左到右周遊
樹的先序，中序，後序周遊用棧，層次周遊用隊列。
11.最小生成樹：權重連通圖的最小權值生成樹，常用于修一條路使得可到所有頂點且花費最小
普裡姆(Prim)算法：加點不構成回（選可達的最小的點）适合稠密圖
克魯斯卡爾(Kruskal)算法：加邊不構成回（選現有的最小的邊）适合稀疏圖
12.v(vertex)是頂點，e(edge)是邊
13.求某個點到其餘各點的最短路徑：迪傑斯特拉(Dijkstra)算法O(n2)（必考）
求每對頂點的最短路徑：弗洛伊德(Floyd)算法O(n3)（不常考）
Floyd：比如求v0到其他頂點，在鄰接矩陣中，v0這一行這一列這一主對角線劃掉，剩下的中間經過v0看是否比原來路徑短，若短則更新
14.拓撲排序：對有向無環圖的頂點的一種排序
15.AOV網：在有向圖中，用頂點表示活動，弧表示活動間的優先關系，則稱此有向圖為用頂點表示活動的網絡（Activity On Vertex Network翻譯即在頂點上的活動）
16.拓撲排序可以解決先決條件問題，比如學院有的課是其他課的基礎，怎樣排課的問題
找到入度為0的點輸出，删除該點的所有出邊，找到剩餘點中入度為0的點輸出，删除所有出邊，重複操作(借用隊列實作，若入度為0則入隊，目前沒有入度為0的點則出隊，也可用棧二者結果不同)
17.AOE網：用頂點表示事件，弧表示活動(注意和AOV網相反)，弧上的權值表示活動持續時間(Activity On Edge Network)。其用于研究 1.完成工程最短時間 2.哪些活動是影響工程的關鍵
18.關鍵路徑：即從源點(起始點)到彙點(最終點)最長的路徑，路徑上的活動稱為關鍵活動
19.事件的最早發生時間：從前往後找前驅節點到目前節點的最大時間 前面的都完成就發生就是最早
事件的最遲發生時間：從後往前，後繼節點的最遲-邊的權值（找其中最小的）超過最遲後面就無法完成
源點和彙點的最早(都為0)和最晚(路徑最大值)相同
20.有向圖的極大強連通子圖，稱為強連通分量
習題
1.
答：若要讓頂點最少，就是頂點之間的邊盡可能的多，最好每兩個點都有邊，又說是非連通，那麼可以一個連通圖加一個點。8個頂點有(8*7)/2=28條邊加一個點就是非連通，是以是9個點
2.一個有n個結點的圖,最少有(1 )個連通分量,最多有(n )個連通分量
答：最少就是整體是連通圖時，最多就是每個頂點都是孤立的點，那麼每個點都是連通分量，注意不可能有0個連通分量，隻要有點(哪怕一個)就得是連通分量
3.N個頂點的無向連通圖用鄰接矩陣表示時,該矩陣 至少有 2(n-1) 個非零元素。
答：鄰接矩陣非零元素的個數即圖的邊數之和的2倍(因為無向一條邊會被存兩次)，圖最少有n-1條邊，那麼矩陣最少有2(n-1)個非零元素
4.深度優先和廣度優先周遊結果均不唯一
5.最小生成樹問題
若是Kruskal算法即加邊，第一次選取最小的一條邊即(v1,v4)第二次最小的邊是8即圖中所示三個邊
若是Prim算法即加點法，從V4開始，v4可到達的點中到達v1最小，然後v1和v4所能到達的其他點中(v1,v3)和(v4,v3)最小，是以答案為(v2,v3)
6.下圖共有3種拓撲排序P
7.判斷一個圖是否有回路除了用拓撲排序還可以用深度優先周遊（若周遊轉一圈回到自身即存在回路）
8.有向圖可拓撲排序的判别條件是____不存在環____(拓撲排序的定義就是對有向無環圖定義的)
9.鄰接表示例 ，注意存的是頂點的數組下标，即使有權值也是存下标
10最小生成樹計算過程(加邊不構成回)
11.最短路徑問題
12.AOE網問題
13.由鄰接矩陣寫成深度優先和廣度優先周遊結果
深度優先：要求越深越好。第一行1和7有邊，然後由7出發，7和3有邊，然後由3出發，3和4有邊…
廣度優先：要求越廣越好。第一行1和7,1和9有邊(是以7和9是1的左右孩子)，然後7和9同時出發…
14.由鄰接表寫成深度優先和廣度優先周遊結果
廣度優先：0出發，0後面有1，2，3。是以周遊結果為0 1 2 3
深度優先：0出發，0後面第一個為1，由1出發，1後面第一個0通路過了，是以通路2，由2出發。2後面0和1都被通路過了，是以通路3也是 0 1 2 3
注意深度優先給出鄰接表不能畫圖求，畫圖比如0後面的1 2 3是沒有次序的，先通路哪個都行。但是若給出鄰接表那麼一定先通路1，是以鄰接表求深度優先周遊是唯一的
雖然這題二者結果相同，但思想不同(越深越好和越廣越好)
15.用DFS周遊一個無環有向圖，并在DFS算法退棧傳回時列印相應的頂點，則輸出的頂點序列是____逆拓撲有序___
答：比如有A->B->C。A先入棧，然後A可到B是以B入棧，B可到C是以C入棧，C沒有可達的是以C出棧，然後是BA出棧。而拓撲排序先是A，删除A的出邊，B入度為0是以是B，以此類推得到ABC
這題說的退棧傳回列印頂點不是按照深度優先搜尋的順序輸出，最先通路的在棧底最後才能彈出
16.假設一個有n個頂點和e條弧的有向圖用鄰接表表示，則删除與某個頂點V1相關的所有弧的時間複雜度是（C）
A.O(n) B.O(e) C.O(n+e) D.O(n*e)
答：要找到所有指向這個頂點的邊，必須得周遊鄰接表所有頂點然後周遊每個頂點的邊看是否和V1相連，相當于對鄰接表周遊，而鄰接表周遊深度優先和廣度優先都是O(n+e)，注意不是O(n*e)
查找
知識點
1.線性表的查找（靜态查找表）
- 順序查找 （就是最簡單的按順序一個一個比較）
- 算法簡單對表結構無要求
- 折半查找(二分查找) （要求是順序存儲有序表）
- data[mid] == k 找到元素，傳回下标mid
- data[mid] > k high=mid-1 (k比中間值小，要向中間值左邊繼續找)
- data[mid] < k low=mid+1 (k比中間值大，要向中間值右邊繼續找)
- 助記：就是找到中間值比較待查元素和中間值，再換個中間值再比較
- 優點：比較次數少查找效率高，但不适于經常變動
- 分塊查找 塊之間有序(左塊最大小于右塊最小)，塊内任意，另建索引表放每塊最大關鍵字
- 适用于既要快速查找又經常動态變化
2.折半查找的判定樹：把中間位置的值作為樹根，左邊和右邊的記錄作為根的左子樹和右子樹
判定樹的中序周遊(左根右)得到的是有序的序列(判定樹左子樹比根節點小，右子樹比根節點大)
3.加入監視哨(存待查元素) 免去每一步查找都要判斷是否查找完的情況，隻要讀到監視哨就說明沒查到
4.樹表的查找（動态(可插入删除)查找表）
- 二叉排序樹（判定樹就是二叉排序樹，左比根小右比根大）
- 時間複雜度最好為O(log2n),最差退化成O(n)的順序查找(如都隻有1個分支)
- 平衡二叉樹（AVL） 左右子樹高度差絕對值不超過1
- 平衡因子：左子樹的高度減去右子樹的高度隻能為0、-1、+1
- 由于後人發現樹越矮查找效率越高是以發明了AVL，時間複雜度為O(log2n)
- B-樹 适合外存檔案系統索引
- B+樹 适合做檔案系統的索引
5.二叉排序樹的删除：缺右補左，缺左補右，不缺左(左子樹)中(中序)後(最後一個)
6.平衡調整：當插入一個結點破壞了平衡性就要調整
- LL型調整
- LR型調整
- RR型調整
- LR型調整
LL、LR等是對不平衡狀态的描述
若是LL和RR型就把畫圈的中間的那個掂起來（想想有重量，另外倆即自己落下去了）
若是LR和RL型就把畫圈的最下面那個掂起來（另外倆也落到它兩邊）
若新插入結點在最小不平衡根節點的左(L)孩子的左(L)子樹上即為LL型調整
若新插入結點在最小不平衡根節點的右®孩子的右左(L)子樹上即為RL型調整
7.B-樹（B樹） m階B-樹，階數其實就是樹的度數 适合外存檔案系統索引
- 根結點最少有兩個分支 （葉子節點除外）
- 非終端結點最少有(m/2)上限個分支（根節點除外）
- 有n個分支的結點有n-1個關鍵字遞增從左到右排列
- 葉子結點(失敗結點)在同一層可用空指針表示，是查找失敗到達的位置
8.B-樹的查找 (類似于二叉樹的查找，但是可以有三個或多個方向)
如查找關鍵字42。首先在根結點查找，因為42>30，則沿着根結點中指針p[1](下标從0開始)往右下走;因為39<42<45,則沿着子樹根結點中指針p[1]往下走，在下層結點中查找關鍵字42成功，查找結束。
9.B+樹是B-樹的變型樹，更适合做檔案系統的索引。
- 葉子結點包含所有關鍵字從左到右遞增且順序連接配接
- 可從根節點随機查找也可從葉子結點順序查找 （嚴格來講，不算是樹了）
10.散清單：根據給定的關鍵字計算關鍵字在表中的位址
負載(裝載因子)：表中結點/表的空間，是以表越滿越容易發生沖突
沖突：不相等的關鍵字計算出了相同的位址
同義詞：發生沖突的兩個關鍵字
11.散清單的構造方法
- 數字分析法 取關鍵字的若幹位或其組合做哈希位址
- 适用于事先知道關鍵字集合且關鍵字位數比散列位址位數多
- 平方取中法 關鍵字平方後取中間若幹位
- 适用于不了解關鍵字或難從關鍵字找到取值較分散的幾位
- 折疊法 分割關鍵字後将這幾部分疊加(舍去進位)
- 适用于散列位址位數少，關鍵字位數多
- 除留取餘法 取模運算（最常用）
12.處理沖突的方法
- 開放位址法
- 線性探測法 看下一個元素是否為空，當成一個循環表來看 (可能二次聚集)
- 二次探測法 原基礎加12、-12、22、-22、32… (可避免二次聚集)
- 僞随機探測法 原基礎加個僞随機數 (可避免二次聚集)
- 鍊位址法 相同位址的記錄放到同一個單連結清單中 (可避免二次聚集)
習題
1.折半查找求判定樹
答：先找中間的值，(1+20)/2=10，是以1-9為10的左子樹(比根小)，11-20為10的右子樹。
比較時先和10比較，若比10小，則比較1-9，那先和誰比較呢，1-9中的中間值為(1+9)/2=5，是以先和5比較(即5和10相連)。如果還比5小，那就要和1-4比了，同樣1-4先和誰比呢，1-4的中間值(1+4)/2=2，是以先和2比較(即2和5相連比5小在左邊)，其他依次類推
查找為4的有1、3、6、8、11、13、16、19(依次和10,15,18,19比較是以4次)
2.用順序表和單連結清單表示的有序表均可使用折半查找方法來提高查找速度。 （錯）
答：單連結清單無法使用折半查找必須是順序存儲，因為要取中間值
3.二叉排序樹序列判定
答：二叉排序樹序列可了解為一個元素與二叉排序樹比較的記錄構成的序列。A中91後面是24說明待查元素X比91小是以後面是24，而24後面是94，說明X比24大，但是24前面已經比較過91了(說明已經肯定比91小了)，現在後面又來了個94顯然是錯的
4.
答：裝填因子越大就越滿越可能發生沖突。沖突少減少不必要的查找。
不能完全避免聚集(不是同義詞卻搶相同位址)隻能減少但可避免二次聚集
5.n個元素的表做順序查找時,若查找每個元素的機率相同，則平均查找長度為_______(n+1)/2______
答：總查找次數為1+2+3+…+n=n(n+1)/2，則平均查找長度為N/n=(n+1)/2
6.如果要求一個線性表既能較快的查找，又能适應動态變化的要求，最好采用 （C）
A.順序查找 B.折半查找 C.分塊查找 D.哈希查找
答：分塊查找的優點是：在表中插入和删除資料元素時，隻要找到該元素對應的塊， 就可以在該塊内進行插入和删除運算。由于塊内是無序的，故插入和删除比較容易，無需進行大量移動。如果線性表既要快速查找又經常動态變化，則可采用分塊查找。嚴版P198
7.對22個記錄的有序表作折半查找，當查找失敗時，至少需要比較 ( 4 ) 次關鍵字。
答：4層的滿二叉樹有24-1=15個結點，5層的有31。題目是22個結點，是以是前4層是滿二叉樹，第五層不是滿的，是以最少4次，最多5次。
8.下面關于 B- 和 B+ 樹的叙述中，不正确的是（ C）。
A． B- 樹和 B+ 樹都是平衡的多叉樹 B． B- 樹和 B+ 樹都可用于檔案的索引結構
C． B- 樹和 B+ 樹都能有效地支援順序檢索 D． B- 樹和 B+ 樹都能有效地支援随機檢索
答：B+樹支援順序(從最小的關鍵字葉子起從左到右)，而B-樹因為其葉子結點互相沒連接配接隻支援從根節點起随機檢索
9.假定對有序表: (3， 4，5，7，24，30，42，54，63，72，87，95) 進行折半查找,
①畫出描述折半查找過程的判定樹;
②若查找元素90，需依次與哪些元素比較?
③假定每個元素的查找機率相等，求查找成功時的平均查找長度。
答：1️⃣ 畫判定樹一般先畫出坐标的判定樹，再根據坐标填值即可，注意取下界及low和high的變化
2️⃣ 需要與30、63、87、95比較
3️⃣ 前3層：1+2*2+4*3=17 第四層：5*4=20
ASL=（17+20）/ 12 = 3.08 即總查找次數除總個數
10.設哈希函數 H(K) =3 K mod 11 ，哈希位址空間為 0～ 10 ，對關鍵字序列（ 32， 13 ，49， 24 ， 38， 21 ， 4， 12），按下述兩種解決沖突的方法構造哈希表，并分别求出等機率下查找成功時和查找失敗時的平均查找長度 ASLsucc 和 ASLunsucc 。
① 線性探測法；
② 鍊位址法。
答：1️⃣ 散列位址就是若算的關鍵字為空就放裡面，不為空就往後找
ASLsucc = （ 1+1+1+2+1+2+1+2 ） /8=11/8
ASLunsucc =（ 1+2+1+8+7+6+5+4+3+2+1 ） /11=40/11
因為最多成功查8個元素，是以查找成功時分母為8，分子就是每個元素查找的次數之和
而查找失敗時可能計算得到的位址有11種，即分母為11，而關鍵字為空的查一次就知道失敗了(要是有也不會為空)，若不為空要往後找直到找到第一個空元素(說明确實沒有這個元素不然該放到這個空着的位置了)
2️⃣ 鍊位址就是要是位址被占了放後面挂着就行
ASLsucc = （ 1*5+2*3 ） /8=11/8 第一列查一次就知道了第二列要查兩次
ASLunsucc =（ 1+2+1+2+3+1+3+1+3+1+1 ） /11=19/11
失敗的情況：查一次若為空說明肯定不存在，若不為空繼續向下查直到為空說明到底了查找失敗(比如第二行需要查兩次，第一次查到為4，第二次查到了空，記住不是查一次就行)
總結：查找成功看位置，查找失敗就找空
11.适宜于對動态查找表進行高效率查找的組織結構是 （C）
A.有序表 B. 分塊有序表 C. 三叉排序表 D. 線性
答：如果線性表既要快速查找又要經常動态變化，則可采用分塊查找。而這裡說的是動态查找表，分塊查找屬于靜态查找表。動态即要進行修改。有序表和線性不适合修改操作
排序
知識點
1.穩定性：排序前和排序後相同關鍵字的相對位置不發生變化就是穩定的
若關鍵字都不重複穩定與否無關緊要，若重複就得具體分析
2.排序算法的分類 （以下均是非遞減排序的情況）
- 插入排序：一個有序的序列，新來的一個插入後仍然有序
- 直接插入排序：第n趟将第n個待排序關鍵字插入到前面(前n個有序)
- 折半插入排序：與直接插入不同的是查找插入位置時用的是折半查找
- 希爾排序：對間隔為n的元素排序，縮小間隔直至為1後簡單插入排序
- 交換排序：核心在于交換，比如排高低，每倆換一下後，可能還得換
- 冒泡排序：1号與2号比較然後2号與3号比較…，可确定最大的元素放在最後
- 快速排序：選一樞軸，兩邊指針往中間移(先移右)使得比樞軸小的移到其左邊
- 選擇排序：核心是選擇，每趟選最大或最小與第一個或最後一個元素交換
- 簡單選擇排序：第n趟選擇最小和第n個位置元素交換
- 樹形選擇(錦标賽)排序：對樹如8個選4個最小,4個選倆,2選1,置最小無窮大
- 堆排序：調整成堆，根和末尾編号交換輸出(每趟得到一個最大值)，重複操作
- 歸并排序：比如每兩個歸并成一組有序序列，再每兩組歸并成一大組有序序列
- 基數排序：選個位放到對應桶中再選十位放到對應桶中，依次類推
3.各方法時間空間複雜度和穩定性比較
| 排序方法 | 時間複雜度 | 空間複雜度 | 穩定性 |
|---|---|---|---|
| 直接插入排序 | O(n2) n比較×n移動 | O(1) 插入排序都為1 | 穩定 |
| 折半插入排序 | O(n2) n比較×n移動 | O(1) | 穩定 |
| 希爾排序 | O(n1.3) 研究證明 | O(1) | 不穩定 |
| 冒泡排序 | O(n2) | O(1) | 穩定 |
| 簡單選擇排序 | O(n2) | O(1) | 不穩定 |
| 錦标賽排序 | O(nlog2n) | O(n) | 穩定 |
| 快速排序 | O(nlog2n) | O(log2n) | 不穩定 |
| 堆排序 | O(nlog2n) | O(1) | 不穩定 |
| 歸并排序 | O(nlog2n) | O(n) | 穩定 |
| 基數排序 | O(d(n+rd)) 每個記錄d個關鍵字 | O(n+rd) n個記錄 | 穩定 |
穩定性：希爾快速選擇堆不穩，其他都穩
時間：
- 除特例外插入和交換類時間都是O(n2)，剩下的時間都是O(nlog2n)
- 可記憶為因為簡單是以時間長，快速是最快的不可能是O(n2)，希爾是最怪的，基數是最長的
空間：
- 樹形(錦标賽)分叉多或賽道多而歸并要一級一級選占空間最多，快速去掉n，基數去掉d
- 其他都是O(1)
4.關鍵字較少 ，選取簡單的：
- 直接插入排序 （最簡單，性能最佳）
- 冒泡排序
關鍵字較多，就用先進的：
- 關鍵字較亂，不要求穩定性：快速排序
- 關鍵字基本有序，就用堆排序或歸并排序
- 不要求穩定性：堆排序
- 要求穩定性：歸并排序
關鍵字多但都較小：基數排序
習題
1.設待排序的關鍵字序列為{12,2, 16, 30, 28, 10, 16*, 20, 6, 18}, 試分别寫出使用以下排序方法， 每趟排序結束後關鍵字序列的狀态
①直接插入排序 (第n趟将第n個待排序關鍵字插入到前面已排序的序列)
原序列為{12,2, 16, 30, 28, 10, 16*, 20, 6, 18}
[2] 12 16 30 28 10 16* 20 6 18 第一趟第一個有序
[2 12] 16 30 28 10 16* 20 6 18 第2個即12與前面的排序
[2 12 16] 30 28 10 16* 20 6 18 第3個即16與前面的排序
[2 12 16 30] 28 10 16* 20 6 18 前4個有序
[2 12 16 28 30] 10 16* 20 6 18 前5個有序
[2 10 12 16 28 30] 16* 20 6 18
[2 10 12 16 16* 28 30] 20 6 18
[2 10 12 16 16* 20 28 30] 6 18
[2 6 10 12 16 16* 20 28 30] 18
[2 6 10 12 16 16* 18 20 28 30] 最後一個與前面的排序 (查找插入位置是依次比)
②折半插入排序
排序過程同①，隻不過查找插入位置用的是折半查詢
③希爾排序 (增量選取5,3,1)
原序列為{12,2, 16, 30, 28, 10, 16*, 20, 6, 18}
10 2 16 6 18 12 16* 20 30 28 （增量選取 5）第1個和第6個排序，第2和第7…
6 2 12 10 18 16 16* 20 30 28 （增量選取 3）第1和第4，第2和第5…
2 6 10 12 16 16* 18 20 28 30 （增量選取 1) 就是直接插入排序
④冒泡排序 （1号與2号比較然後2号與3号比較…，可确定最大的元素放在最後）
原序列為{12,2, 16, 30, 28, 10, 16*, 20, 6, 18}
2 12 16 28 10 16* 20 6 18 [30] 12與2比較交換，12和16比較，16和30比較…
2 12 16 10 16* 20 6 18 [28 30] 每一趟确定一個最大的放最後
2 12 10 16 16* 6 18 [20 28 30] 第3趟确定3個最大
2 10 12 16 6 16* [18 20 28 30] 确定4個最大
2 10 12 6 16 [16* 18 20 28 30]
2 10 6 12 [16 16* 18 20 28 30]
2 6 10 [12 16 16* 18 20 28 30]
2 6 10 12 16 16* 18 20 28 30]
⑤快速排序 （選一樞軸，兩邊指針往中間移使得比樞軸小的移到其左邊,先移右指針）
原序列為{12,2,16, 30, 28, 10, 16*, 20, 6, 18}
12 [6 2 10] 12 [28 30 16* 20 16 18] 先讓右指針往左移
6 [2] 6 [10] 12 [28 30 16* 20 16 18 ] 一般選第一個為樞軸
28 2 6 10 12 [18 16 16* 20 ] 28 [30 ]
18 2 6 10 12 [16* 16] 18 [20] 28 30
16* 2 6 10 12 16* [16] 18 20 28 30
⑥簡單選擇排序 （第n趟選擇最小和第n個位置元素交換）
原序列為{12,2,16, 30, 28, 10, 16*, 20, 6, 18}
[2] 12 16 30 28 10 16* 20 6 18 最小的2和第一個12交換
[2 6 ]16 30 28 10 16* 20 12 18 最小的6和第二個12交換
[2 6 10 ]30 28 16 16* 20 12 18 最小的10和第三個16交換
[2 6 10 12] 28 16 16* 20 30 18 最小的12和第四個30交換
[2 6 10 12 16] 28 16* 20 30 18
[2 6 10 12 16 16* ]28 20 30 18
[2 6 10 12 16 16* 18 ]20 30 28
[2 6 10 12 16 16* 18 20 ]28 30
[2 6 10 12 16 16* 18 20 28] 30
⑦堆排序
原序列為{12,2, 16, 30, 28, 10, 16*, 20, 6, 18}
18 12 16 20 28 10 16* 2 6 [30] 得到最大值30，繼續調整交換
6 20 16 18 12 10 16* 2 [28 30] 得到兩個最大值，繼續調整交換
… 由于此題沒有答案，下面類似
建堆(按編号即層次周遊)然後調整堆(從最後面的非葉子結點向前選擇最大的放到根，可能不止調整一趟)。
然後交換根和最後一個編号(注意不是最小)，再重新調整交換重複操作
⑧二路歸并排序 (每兩個歸并成一組有序序列，再每兩組歸并成一組有序序列)
原序列為{12,2, 16, 30, 28, 10, 16*, 20, 6, 18}
[2 12] [16 30] [10 28] [16 * 20] [6 18] 每兩個合為一組
[2 12 16 30] [10 16* 20 28] [6 18] 每兩組即四個合為一組
[2 10 12 16 16* 20 28 30] [6 18] 每兩組即八個合為一組
[2 6 10 12 16 16* 18 20 28 30 ]
2.樹形選擇(錦标賽)排序
原序列為{49,38, 65, 97, 76, 13, 27, 49*}
對樹8個選4個最小,4個選倆,2選1,選中13為最小輸出，置最下面13為無窮大，重複操作
3.基數排序
原序列為{278,109,063,930,589,184,505,269,008,083}
準備10個桶，第一趟收集按個位放到對應桶中
即結果為：930 063 083 184 505 278 008 109 589 269 (個位已經有序)
第二趟收集按十位放到對應桶中
即結果為：505 008 109 930 063 269 278 083 184 589
我們可以看到最低2位已經有序了，隻需再來一趟收集即可，就不寫了
4.根據結果寫排序方法
5.對 n 個不同的排序碼進行冒泡排序， 在元素無序的情況下比較的次數最多為( )
答：比較次數最多時，第一趟比較 n-1 次，第二趟比較 n-2 次, 最後一趟比較 1
次，即 (n-1)+(n-2)+…+1= n(n-1)/2
6.若一組記錄的排序碼為（ 46, 79 ， 56，38 ， 40，84），則利用快速排序的方法，以第一個記錄為基準得到的一次劃分結果為（）
答：左右設兩指針，右指針先移，84比46大不移動，40比46小是以40覆寫46的位置，然後該左邊的指針移動了，79比46大，是以移到空着的原40的位置。然後該右指針移了，38比46小是以38覆寫空着的原79位置，左邊的56比46大移到空着的原38，然後将46放到空着的原56即可。結果為：40,38,46,56,79,84
7.資料表中有 10000 個元素，如果僅要求求出其中最大的 10 個元素，則采用 ( D )
算法最節省時間
A．冒泡排序 B ．快速排序 C．簡單選擇排序 D．堆
答：堆用大根堆一趟選取一個最大的最快
冒泡每兩個比較，有10000個肯定慢。快速是選樞軸，再左右移動也慢
簡單選擇每一趟都幾乎快周遊一遍也肯定慢
8.下列排序算法中， （ A ）不能保證每趟排序至少能将一個元素放到其最終的位置上
A．希爾排序 B ．快速排序 C. 冒泡排序 D．堆
答：快速排序的每趟排序能将作為樞軸的元素放到最終位置；冒泡排序的每趟排序能将最大或最小的元素放到最終位置；堆排序的每趟排序能将最大或最小的元素放到最終位置。而希爾排序隻是對間隔為n的元素排序是以不确定。
這種讓選擇哪個排序的需要知道每個排序大緻是咋排的就很好選擇
各類型存儲結構
順序表
#define MAXSIZE 100 //順序表可能達到的最大長度
typedef struct
{
ElemType *elem; //存儲空間的基位址(例如用L.elem[0]取元素)
int length; //目前長度
}SqList;
L.elem[i]取值 //L.length-1=>i>=0，如元素為1,2,3，L.length=3，i=0,1,2
單連結清單
typedef struct LNode
{
ElemType data; //結點的資料域
struct LNode *next; //結點的指針域，指向下一結點
}LNode,*LinkList; //LinkList為指向結構體LNode的指針類型(相當于LNode *)
若帶頭結點，空表條件為L->next==NULL（L為頭指針指向頭結點永不為空）
若不帶頭結點，空表條件為L==NULL
雙向連結清單
typedef struct DuLNode
{
ElemType data; //結點的資料域
struct DuLNode *prior; //指向直接前驅
struct DuLNode *next; //指向直接後繼
}DuLNode,*DuLinkList;
順序棧
#define MAXSIZE 100 //順序棧存儲空間的初始配置設定量
typedef struct
{
SElemType *base; //棧底指針
SElemType *top; //棧頂指針
int stacksize; //棧可用的最大容量
}SqStack;
棧空：S.top==S.base //首尾指針相同
棧滿：S.top-S.base==S.stacksize //尾-首等于最大容量即為滿
鍊棧
//定義類似，類似操作受限的單連結清單
typedef struct StackNode
{
ElemType data; //資料域
struct StackNode *next; //指向下一結點
}StackNode,*LinkStack;
鍊棧一定是沒有頭結點，是以棧空的條件為：S==NULL
循環隊列
#define MAXSIZE 100 //隊列可能達到的最大長度
typedef struct
{
QElemType *base; //存儲空間的基位址
int front; //頭指針（隻是有指針的作用,例如用Q.base[Q.front]取元素）
int rear; //尾指針
}SqQueue;
隊空：Q.front==Q.rear //首尾指針相同
//尾指針指向的為最後一個元素的下一個位址(永遠為空)，是以+1
隊滿：(Q.rear+1)%MAXSIZE==Q.front
鍊隊
//隻看第一個定義和單連結清單類似，不同的是第二個設了隊頭和隊尾指針
typedef struct QNode
{
QElemType data; //資料域
struct QNode *next; //指向下一結點
}QNode,*QueuePtr;
typedef struct
{
QueuePtr front; //隊頭指針(相等于QNode *front)
QueuePtr rear; //隊尾指針
}LinkQueue;
隊空：Q.front=Q.rear
由于串、數組、廣義表的存儲結構不是重點在這裡就不再列出其存儲結構
小結
棧和隊列除了鍊棧都有頭尾指針
順序二叉樹(不常用)
#define MAXSIZE 100 //二叉樹的最大結點數
typedef TElemType SqBiTree[MAXSIZE] //0号存儲根結點
SqBiTree bt;
二叉連結清單(常用)
typedef struct BiTNode
{
TElemType data; //結點資料域
struct BiTNode *lchild,*rchild; //左右孩子指針
}BiTNode,*BiTree;
線索二叉樹
typedef struct BiThrNode
{
TElemType data;
struct BiThrNode *lchild,*rchild; //左右孩子指針
int LTag,RTag; //左右标志
}BiThrNode,*BiThrTree;
孩子兄弟二叉樹
tyrpedef struct CSNode //又稱二叉連結清單表示，本質存的是樹用類似存二叉樹的方法存
{
ElemType data;
struct CSNode *firstchild,*nextsibling; //即左是孩子右是兄弟
}CSNode,*CSTree;
鄰接矩陣
#define MaxInt 32767 //表示極大值，即∞
#define MVNum 100 //最大頂點數
typedef char VertexType; //假設頂點的資料類型為字元型
typedef int ArcType; //假設邊的權值類型為整型
typedef struct{
VertexType vexs[MVNum]; //頂點表
ArcType arcs[MVNum][MVNum]; //鄰接矩陣
int vexnum,arcnum; //圖的頂點數和邊數
}AMGraph;
鄰接表
//注意存的是頂點數組下标不是存的頂點本身
typedef struct ArcNode { //邊結構
int adjvex; //該邊所指向的頂點位置
struct ArcNode *nextarc; //指向下一條邊的指針
OtherInfo info; //和邊相關的資訊
} ArcNode；
#define MVNum 100
typedef struct VNode{ //頂點結構
VertexType data; //頂點資訊
ArcNode * firstarc; //指向依附該頂點的第一條弧的指針
} VNode, AdjList[MVNum];
typedef struct { //圖結構
AdjList vertics ; //鄰接表
int vexnum, arcnum; //頂點數和弧數
int kind; //圖的種類
} ALGraph;