數(shù)據(jù)結(jié)構(gòu)(C語言版)-期末復(fù)習(xí)匯總
數(shù)據(jù)結(jié)構(gòu)（C語言版） 期末復(fù)習(xí)匯總 第一章?緒論
數(shù)據(jù)結(jié)構(gòu)
：是一門研究非數(shù)值計算程序設(shè)計中的操作對象，以及這些對象之間的關(guān)系和操作的學(xué)科。 數(shù)據(jù)結(jié)構(gòu)是一門綜合性的專業(yè)課程，是一門介于數(shù)學(xué)、計算機(jī)硬件、計算機(jī)軟件之間的一門核心課程。是設(shè)計和實現(xiàn)編譯系統(tǒng)、操作系統(tǒng)、數(shù)據(jù)庫系統(tǒng)及其他系統(tǒng)程序和大型應(yīng)用程序的基礎(chǔ)。
數(shù)據(jù)
：是客觀事物的符號表示，是所有能輸入到計算機(jī)中并被計算機(jī)程序處理的符號的總稱。如數(shù)學(xué)計算中用到的整數(shù)和實數(shù)，文本編輯中用到的字符串，多媒體程序處理的圖形、圖像、聲音及動畫等通過特殊編碼定義后的數(shù)據(jù)。 數(shù)據(jù)的邏輯結(jié)構(gòu)劃分：
線、樹、圖
算法的定義及特性
算法
：是為了解決某類問題而規(guī)定的一個有限長的操作序列。 五個特性：
有窮性、確定性、可行性、輸入、輸出
評價算法優(yōu)劣的基本標(biāo)準(zhǔn)（4個）：
正確性、可讀性、健壯性、高效性及低存儲量
第二章 線性表 線性表的定義和特點：
線性表：
由n(n≥0)個數(shù)據(jù)特性相同的元素構(gòu)成的有限序列。線性表中元素個數(shù)n(n≥0)定義為線性表的長度，n=0時稱為空表。
非空線性表或線性結(jié)構(gòu)，其特點：
（1）存在唯一的一個被稱作
“第一個”
的數(shù)據(jù)元素； （2）存在唯一的一個被稱作
“最有一個”
的數(shù)據(jù)元素； （3）除第一個之外，結(jié)構(gòu)中的每個數(shù)據(jù)元素均只有一個
前驅(qū)
； （4）除最后一個之外，結(jié)構(gòu)中的每個數(shù)據(jù)元素均只有一個
后繼
。 順序表的插入：n個元素在i位插入，應(yīng)移動
（n-i+1）
位元素。
順序表存儲結(jié)構(gòu)的優(yōu)缺點：
優(yōu)點： 邏輯相鄰，物理相鄰；可隨機(jī)存取任一元素；存儲空間使用緊湊； 缺點： 插入、刪除操作需要移動大量的元素；預(yù)先分配空間需按最大空間分配，利用不充分； 表容量難以擴(kuò)充； 線性表的應(yīng)用：
一般線性表的合并：★★★
算法2.1：LA=(7,5,3,11)??LB=(2,6,3) 合并后?LA=(7,5,3,11,2,6)
算法思想
：擴(kuò)大線性表LA，將存在于線性表LB中而不存在于線性表LA中的數(shù)據(jù)元素插入到線性表LA中去。只要從線性表LB中依次取得每個數(shù)據(jù)元素，并依值在線性表LA中進(jìn)行查訪，若不存在，則插入之。
有序表的合并：★★★
算法2.2：LA=(3,5,8,11)?LB=(2,6,8,9,11,15,20) 則 LC=(2,3,5,6,8,9,11,11,15,20)
算法思想
：首先創(chuàng)建一個空表LC，通過比較指針pa和pb所指向的元素的值，依次從LA或LB中“摘取”元素值較小的結(jié)點插入到LC表的最后，當(dāng)其中一個表變空是，說明此表的元素已歸并完，則只要將另一個非空表的剩余結(jié)點依次插入在LC表的最后即可。 線性鏈表： 線性鏈表的插入：插入元素師，指針的指向變化： ? 上述指針修改用語句描述即為：
s->next=p->next; p->next=s;
單鏈表的插入：★★★
void?insertnode(linklist?head，datetype?x，int?i){ ???????listnode?* p，*q; ???????p=getnode(head，i-1); ???????if(p==NULL) ???????????error(〝position?error〞); ????????q=(listnode *) ???????malloc(sizeof(listnode));
????????q–>data=x;
????????q–>next=p–next;
?????????p–>next=q;
??????} 課本中：
s=new LNode;
s->data =e;
s->next=p->next;
p->next=s;
線性鏈表的刪除：刪除元素，指針的指向變化： ? 上述指針修改用語句描述即為：
p->next=p->next->next;
單鏈表的刪除：★★★
void?deletelist(linklist head， int i) ???{??listnode * p， *r; ??????p=getnode(head，i-1); ??????if(p= =NULL || ????????p–>next= =NULL) ??????return ERROR;
??????r=p–>next;
??????p–>next=r–>next;
???????free( r ) ;???} 課本中：
q=p->next;
p->next=q->next;
單鏈表特點：
它是一種動態(tài)結(jié)構(gòu)，整個存儲空間為多個鏈表共用； 不需預(yù)先分配空間； 指針占用額外存儲空間； 不能隨機(jī)存取，查找速度慢。 第三章 棧和隊列
棧的類型定義：
棧
(Stack)是限制在表的一端進(jìn)行插入和刪除運算的線性表，通常稱插入、刪除的這一端為棧頂(Top)，另一端為棧底(Bottom)。當(dāng)表中沒有元素時稱為空棧。 假設(shè)棧S=(a1，a2，a3，…an)，則
a1稱為棧底元素
，
an為棧頂元素
。棧中元素按a1，a2，a3，…an的
次序進(jìn)棧
，退棧的第一個元素應(yīng)為棧頂元素。即，棧的修改是按后進(jìn)先出的原則進(jìn)行的。因此，棧稱為
后進(jìn)先出
表（LIFO）。
棧的進(jìn)棧、出棧順序：
例：★★★
對于一個棧，給出輸入項A、B、C，如果輸入項序列由ABC組成，試給出所有可能的輸出序列。
??A進(jìn) A出 B進(jìn) B出 C進(jìn) C出????????ABC ??A進(jìn) A出 B進(jìn) C進(jìn) C出 B出????????ACB ??A進(jìn) B進(jìn) B出 A出 C進(jìn) C出????????BAC ??A進(jìn) B進(jìn) B出 C進(jìn) C出 A出????????BCA ??A進(jìn) B進(jìn) C進(jìn) C出 B出 A出????????CBA 不可能產(chǎn)生輸出序列CAB 棧的應(yīng)用：數(shù)值轉(zhuǎn)換[大題]
算法思想：首先將按照上述計算過程中得到的八進(jìn)制樹的各位依次進(jìn)棧，然后將棧中的八進(jìn)制數(shù)依次出棧輸出，輸出結(jié)果就是該是十進(jìn)制數(shù)轉(zhuǎn)換得到的八進(jìn)制數(shù)。
N=(N div d)×d + N mod d （其中：div 為整除運算，mod 為求余運算） 例如 (1348)10=(2504)8，其運算過程如下： N?????????N div 8 ??N mod 8 1348???????168????????????4 168????????21?????????????0 21?????????2??????????????5 2??????????0??????????????2 算法：【此為課件算法同課本算法一致】
★★★
?????
void conversion(?) {
?????????????initstack ( s );//構(gòu)造空棧
?????????????scanf ( “ % ” , n);
?????????????while( n ){
???????????????????push ( s , n % 8 );
???????????????????n = n / 8;
?????????????????}
?????????????while( ! Stackempty ( s )){//當(dāng)棧非空時
???????????????????pop ( s , e );
???????????????????printf ( “ % d ” , e );}?}//conversion
隊列的類型定義：
定義：隊列是限定只能在表的一端進(jìn)行插入，在表的另一端進(jìn)行刪除的線性表
隊尾(rear)：允許插入的一端 隊頭(front)：允許刪除的一端
隊列特點：先進(jìn)先出 ( FIFO )
第四章 串、數(shù)組和廣義表
串的類型定義：
串是字符串的簡稱。它是一種在數(shù)據(jù)元素的組成上具有一定約束條件的線性表，即要求組成線性表的所有數(shù)據(jù)元素都是字符，所以，人們經(jīng)常又這樣定義串：串是一個有窮字符序列。
串一般記作：
?????????????
s= “a1a2...an”???(n≥0)
?????????????其中，s是串的名稱，用雙引號（“”）括起來的字符序列是串的值；ai可以是字母、數(shù)字或其他字符；串中字符的數(shù)目n被稱作串的長度。當(dāng)n=0時，串中沒有任何字符，其串的長度為0，通常被稱為空串。
子串、主串：
串中任意連續(xù)的字符組成的子序列被稱為該串的子串。包含子串的串又被稱為該子串的主串。
廣義表的定義：
廣義表是n(n>=0)個元素a1,a2,a3,…,an的有限序列，其中ai或者是原子項，或者是一個廣義表。通常記作LS=（a1,a2,a3,…,an)。LS是廣義表的名字，n為它的長度。若ai是廣義表，則稱它為LS的子表。
廣義表的結(jié)構(gòu)特點:
1)?廣義表的元素可以是子表，而子表的元素還可以是子表……廣義表是一個多層次的結(jié)構(gòu) 2)?廣義表可為其他廣義表所共享 3)?廣義表可以是一個遞歸的表，即廣義表也可以是其本身的一個子表
廣義表的兩個重要運算：取表頭GetHead(LS)，取表尾GetTail(LS)
任何一個非空廣義表 ?????LS = ( a1, a2, …, an ) 均可分解為 ????表頭?Head(LS) = a1?? 和 ????表尾?Tail(LS) = ( a2, …, an ) 兩部分。
例如：★★★
已知廣義表LS=（a，（b，c，d），c），運用GetHead和GetTail函數(shù)取出原子d的運算過程為
：GetHead(GetTail(GetTail(GetHead(GetTail(LS))))) 第五章 樹和二叉樹
數(shù)的定義：
樹(tree)是n(n≥0)個結(jié)點的有限集T，其中： 有且僅有一個特定的結(jié)點，稱為樹的根(root)； 當(dāng)n>1時，其余結(jié)點可分為m(m>0)個互不相交的有限集T1,T2,……Tm，其中每一個集合本身又是一棵樹，稱為根的子樹(subtree)。
特點：
樹中至少有一個結(jié)點：根 樹中各子樹是互不相交的集合
線性結(jié)構(gòu)與樹形結(jié)構(gòu)的區(qū)別
線性結(jié)構(gòu) 樹形結(jié)構(gòu) 第一個數(shù)據(jù)元素（無前驅(qū)） ?????????????????? 根結(jié)點 （無前驅(qū)） 最后一個數(shù)據(jù)元素（無后繼） ????????????????????? 多個葉子結(jié)點（無后繼） 其它數(shù)據(jù)元素（一個前驅(qū)，一個后繼） 其它數(shù)據(jù)元素（一個前驅(qū)、多個后繼）
樹的基本術(shù)語：
結(jié)點(node) ：表示樹中的元素，包括數(shù)據(jù)元素及若干指向其子樹的分支 結(jié)點的度(degree) ：結(jié)點擁有的子樹數(shù) 樹的度 ： 一棵樹中最大的結(jié)點度數(shù) 葉子(leaf) ：度為0的結(jié)點（終端結(jié)點） 孩子(child) ：結(jié)點子樹的根稱為該結(jié)點的~~ 雙親(parents) ：孩子結(jié)點的上層結(jié)點叫該結(jié)點的~~ 兄弟(sibling) ：同一雙親的孩子 子孫 ： 以某結(jié)點為根的子樹中的所有結(jié)點都被稱為是該結(jié)點的~~ 祖先 ：從根結(jié)點到該結(jié)點路徑上的所有結(jié)點 堂兄弟 ：雙親在同一層的結(jié)點互為~~ 結(jié)點的層次(level) ： 從根結(jié)點算起，根為第一層，它的孩子為第二層…… 深度(depth) ： 樹中結(jié)點的最大層次數(shù) 森林(forest) ： m(m30)棵互不相交的樹的集合 有序樹、無序樹 ： 如果樹中每棵子樹從左向右的排列擁有一定的順序，不得互換，則稱為有序樹，否則稱為無序樹
對于課本P96樹形圖
：★★★ 結(jié)點A的度：3 結(jié)點B的度：2 結(jié)點M的度：0 結(jié)點A的層次：1 結(jié)點M的層次：4 結(jié)點B，C，D為兄弟 結(jié)點K，L為兄弟 葉子：K，L，F(xiàn)，G，M，I，J 結(jié)點A的孩子：B，C，D 結(jié)點B的孩子：E，F(xiàn) 結(jié)點I的雙親：D 結(jié)點L的雙親：E 結(jié)點F，G為堂兄弟 結(jié)點A是結(jié)點F，G的祖先 樹的深度：4 樹的度：3
二叉樹的定義：
二叉樹是n(n≥0)個結(jié)點的有限集，它或為空樹(n=0)，或由一個根結(jié)點和兩棵分別稱為左子樹和右子樹的互不相交的二叉樹構(gòu)成。 特點 每個結(jié)點至多有二棵子樹(即不存在度大于2的結(jié)點)； 二叉樹的子樹有左、右之分，且其次序不能任意顛倒。
二叉樹的性質(zhì)：
性質(zhì)1：在二叉樹的第i層上最多有2i-1個結(jié)點（i≥1）；
性質(zhì)2：深度為K的二叉樹最多有2K-1個結(jié)點?（K≥1）；
性質(zhì)3： 對任何一棵二叉樹T，如果其終端結(jié)點數(shù)為n0，度為2的結(jié)點數(shù)為n2，則n0=n2+1；
完全二叉樹
定義：一棵深度為h，具有n個結(jié)點的二叉樹，若將它與一棵同深度的滿二叉樹中的所有結(jié)點按從上到下，從左到右的順序分別進(jìn)行編號，且該二叉樹中的每個結(jié)點分別與滿二叉樹中編號為1~n的結(jié)點位置一一對應(yīng)，則稱這棵二叉樹為
完全二叉樹
。
特點：
葉子結(jié)點只可能在層次最大的兩層上出現(xiàn);
對任一結(jié)點，若其右分支下子孫的最大層次為L，則其左分支下子孫的最大層次必為L或L+1。
性質(zhì)4：具有n個結(jié)點的完全二叉樹的深度為?log2n?+1。（其中，?log2n??的結(jié)果是不大于log2n的最大整數(shù)。）
性質(zhì)5：
對于有n個結(jié)點的完全二叉樹中的所有結(jié)點按從上到下，從左到右的順序進(jìn)行編號，則對任意一個結(jié)點i （1≤i≤n），都有： （1）如果i=1，則結(jié)點i是這棵完全二叉樹的根，沒有雙親。否則其雙親結(jié)點的編號為 ?i/2?； （2）如果2i>n，則結(jié)點i沒有左孩子。否則其左孩子結(jié)點的編號為2i； （3）如果2i+1>n，則結(jié)點i沒有右孩子。否則其右孩子結(jié)點的編號為2i+1。 ???????????
遍歷二叉樹：★★★
先序遍歷：先訪問根結(jié)點,然后分別先序遍歷左子樹、右子樹【包絡(luò)法】
中序遍歷：先中序遍歷左子樹，然后訪問根結(jié)點，最后中序遍歷右子樹【垂直映射法】
后序遍歷：先后序遍歷左、右子樹，然后訪問根結(jié)點
例：（1）
先序遍歷：A.B.D.E.F.G.K.M.C.H.J??????????????
中序遍歷：D.B.F.E.K.A.M.G.H.C.J??????????????????????P105 貼紙（1）
后序遍歷：D.F.K.M.A.E.B.H.J.C.G
層次遍歷：A.B.C.D.E.H.J.F.G.K.M
例：（2）
先序遍歷：A.B.E.F.I.G.C.D.H.J.K.L.N.O.M
后序遍歷：E.I.F.G.B.C.J.K.N.O.L.M.H.D.A????????????????P105貼紙（2）
層次遍歷：A.B.C.D.E.F.G.H.I.J.K.L.M.N.O
赫夫曼樹遍歷：★★★
例：W={ 5，29，7，8，14，23，3，11 }
?
第六章 圖 圖的定義：圖(Graph)：圖G是由兩個集合V(G)和E(G)組成的,記為：G=(V,E) 其中：V(G)是頂點的非空有限集；E(G)是邊的有限集合，邊是頂點的無序?qū)蛴行驅(qū)Α?
有向圖，無向圖
頂點的度：無向圖中，頂點的度為與每個頂點相連的邊數(shù)； 有向圖中，頂點的度分成入度與出度
入度：以該頂點為頭的弧的數(shù)目
出度：以該頂點為尾的弧的數(shù)目
路徑：路徑是頂點的序列V={Vi0,Vi1,……Vin}，滿足(Vij-1,Vij)
??
E 或?
?
E,(1 ? V, Vi ? Vj,從Vi到Vj 和從Vj到?Vi都存在路徑，則稱G是~
鄰接表：
?
深度遍歷：
方法：從圖的某一頂點V0出發(fā)，訪問此頂點；然后依次從V0的未被訪問的鄰接點出發(fā)，深度優(yōu)先遍歷圖，直至圖中所有和V0相通的頂點都被訪問到；若此時圖中尚有頂點未被訪問，則另選圖中一個未被訪問的頂點作起點，重復(fù)上述過程，直至圖中所有頂點都被訪問為止。
?圖一
?圖二
?圖三
?圖四
必須說明，若不給定存儲結(jié)構(gòu)，深度優(yōu)先遍歷的結(jié)果不唯一 。因為哪個頂點是第一鄰接點未確定。給定存儲結(jié)構(gòu)后，深度優(yōu)先遍歷的結(jié)果是唯一的。
廣度遍歷：【不考，比較深度遍歷記憶】
方法：從圖的某一頂點V0出發(fā)，訪問此頂點后，依次訪問V0的各個未曾訪問過的鄰接點；然后分別從這些鄰接點出發(fā)，廣度優(yōu)先遍歷圖，直至圖中所有已被訪問的頂點的鄰接點都被訪問到；若此時圖中尚有頂點未被訪問，則另選圖中一個未被訪問的頂點作起點，重復(fù)上述過程，直至圖中所有頂點都被訪問為止。
圖一中：廣度遍歷：V1T?V2 TV3 T?V4 TV5 TV6 TV7 TV8
第七章 查找
折半查找法（考圖形過程）：★★★
（1）有序表：{ 5,16,20,27,30,36,44,55,60,67,71}
課本P167，例7.1?P168 圖7.1
?
（2）折半查找過程示例：有序表{5,13,19,21,37,56,64,75,80,88,92}
?
?
?
第八章 排序
★★★ 冒泡排序：
排序過程：
將第一個記錄的關(guān)鍵字與第二個記錄的關(guān)鍵字進(jìn)行比較，若為逆序r[1].key>r[2].key，則交換；然后比較第二個記錄與第三個記錄；依次類推，直至第n-1個記錄和第n個記錄比較為止——第一趟冒泡排序，結(jié)果關(guān)鍵字最大的記錄被安置在最后一個記錄上
對前n-1個記錄進(jìn)行第二趟冒泡排序，結(jié)果使關(guān)鍵字次大的記錄被安置在第n-1個記錄位置
重復(fù)上述過程，直到“在一趟排序過程中沒有進(jìn)行過交換記錄的操作”為止。
?
課件上的算法：
void BubbleSort(int a[], int n)
{
????int i, j, exchange;
????int tmp;
????for (i = 0; i < n-1; i++)
{ exchange=0;
????for (j = n-1; j>i; j--) ??//比較，找出最小關(guān)鍵字的記錄
????if (a[j] < a[j -1])
????{
????????tmp = a[j]; ???????????????//a[j]與a[j-1]進(jìn)行交換，將最小關(guān)鍵字記錄前移
????????a[j] = a[j - 1];
????????a[j -1] = tmp;
????????exchange=1;
????}
????if (exchange==0) ??//本趟未發(fā)生交換時結(jié)束算法
?????????return; }}
課本上的偽碼算法：
void BubbleSort(SqList &L){
//對順序表L做冒泡排序
m=L.length-1;flag=1;
while((m>0)&&(flag==1)){
flag=0;//flag置為0，如果本趟排序沒有發(fā)生交換，則不會執(zhí)行下一趟排序
for(j=1;j<=m;j++)
??if(L.r[j].key>L.r[j+1].key){
flag=1;//flag置為1，表示本趟排序發(fā)生了交換
t=L.r[j];L.r[j]=L.r[j+1];L.r[j+1]=t;//交換前后兩個記錄
}//if
--m;
}//while
}//BubbleSort
C語言冒泡排序法：
#include
