【正文】 兩端向中間進行。 冒泡排序(起泡排序)：通過相鄰元素之間比較和交換，使較小移向頂部，從后往前兩兩比較。希爾排序(縮小增量排序)：算法不穩(wěn)定。時間復(fù)雜度最好是O(n)，最壞是O(n2)，所以是O(n2)。 直接插入排序：每次從無序區(qū)取出第一個元素把它插入到有序區(qū)的適當(dāng)位置，使之成為新的有序區(qū)，經(jīng)過n1次插入后完成。評價排序算法的標準：執(zhí)行算法需要的時間，以及算法所需要的附加空間。第七章 排序，經(jīng)過排序后，這些具有相同關(guān)鍵字的記錄之間的相對次序保持不變，該排序方法是穩(wěn)定的；反之，則是不穩(wěn)定的。c、重復(fù)上述步驟，直到全部頂點都已輸出或圖中剩余的頂點中沒有前趨頂點為止。 檢測的方法是：對有向圖構(gòu)造其頂點的拓撲序列，若網(wǎng)中所有頂點都在他的拓撲序列中，則AOV網(wǎng)必定不存在環(huán)。　拓撲排序：子工程稱為活動，頂點代表活動，有向邊代表活動的先后關(guān)系。 最小生成樹：圖的生成樹不唯一，把權(quán)值最小的生成樹稱為最小生成樹（MST）。時間復(fù)雜度為鄰接矩陣O(n2)或鄰接表O(n+e)，空間復(fù)雜度都是O(n)。 深度優(yōu)先搜索遍歷(DFS)類似于前序(先根)遍歷。建立鄰接表的時間復(fù)雜度是O(n+e)。若G是帶權(quán)圖，只要把1換成相應(yīng)邊上的權(quán)值即可，0的位置上可以不動或?qū)⑵鋼Q成無窮大表示。：鄰接矩陣和鄰接表表示法。無向圖的極大連通子圖稱為連通分量，顯然，任何連通圖的連通分量只有一個，即其自身，而非連通的無向圖有多個連通分量。在有向圖中，n的取值范圍是0n(n1)，將具有n(n1)條邊的有向圖稱為有向完全圖。第六章 圖，頂點集合和邊集合，也可以圖G只有頂點而沒有邊。設(shè)計一種長短不等的編碼，則必須保證任一字符的編碼都不是另一個字符編碼的前綴，這種編碼稱為前綴編碼。這棵樹便是哈夫曼樹。 ③ 最優(yōu)二叉樹的形態(tài)不唯一，WPL最小。 哈夫曼樹不一定是二叉樹。對下面(a)圖中所示的森林進行前序遍歷和后序遍歷，則得到該森林的前序序列和后序序列分別為ABCDEFIGJH和BDCAIFJGHE。 　這種存儲結(jié)構(gòu)的最大優(yōu)點是：它和二叉樹的二叉鏈表表示完全一樣。：在存儲結(jié)點信息的同時，附加兩個分別指向該結(jié)點最左孩子和右鄰兄弟的指針域，即可得樹的孩子兄弟鏈表表示。由于樹根沒有兄弟，故樹轉(zhuǎn)化為二叉樹后，二叉樹的根結(jié)點的右子樹必為空。和中序遍歷算法一樣，遞歸過程中對每結(jié)點僅做一次訪問。遞歸工作棧中包括兩項：一項是遞歸調(diào)用的語句編號，另一項則是指向根結(jié)點的指針。二叉樹遍歷算法中的遞歸終止條件是二叉樹為空。建立二叉鏈表方法：a、按廣義表方法，靠近左括號的結(jié)點是在左子樹上，而逗號右邊結(jié)點是在右子樹上。但對于一般二叉樹來說，采用順序存儲時，為了使用結(jié)點在數(shù)組中的相對位置來表示結(jié)點之間的邏輯關(guān)系，就必須增加一些虛結(jié)點使其成為完全二叉樹的形式。編號從0開始①若i=0，則qi為根結(jié)點，無雙親；否則，qi的雙親編號為?(i1)/2?。具有n個結(jié)點的完全二叉樹的深度為。 （2） 在滿二叉樹的最下一層上，從最右邊開始連續(xù)刪去若干結(jié)點后得到的二叉樹仍然是一棵完全二叉樹。完全二叉樹：若一棵深度為k的二叉樹，其前k1層是一棵滿二叉樹，而最下面一層上的結(jié)點都集中在該層最左邊的若干位置上，則此二叉樹稱為完全二叉樹。例如一棵深度為4的二叉樹（a），其終端結(jié)點數(shù)n0為8,度為2的結(jié)點樹為7，則8=7+1，no=n2+1成立（b）其終端結(jié)點數(shù)n0為6,度為2的結(jié)點樹為5，則6=5+1，no=n2+1成立滿二叉樹：一棵深度為k且有2k1個結(jié)點的二又樹稱為滿二叉樹。而在二叉樹中，即使是一個孩子也有左右之分。 森林(Forest)是m(m≥0)棵互不相交的樹的集合。若不特別指明，一般討論的樹都是有序樹。 　除根結(jié)點之外的分支結(jié)點統(tǒng)稱為內(nèi)部結(jié)點。度不為零的結(jié)點稱分支結(jié)點或非終端結(jié)點。第五章 樹和二叉樹：最常用的是樹形圖表示法；還有3種嵌套集合、凹形、廣義表。廣義表的兩個特殊的基本運算：取表頭head(Ls)和取表尾tail(Ls).任何一個非空廣義表的表頭可以是原子，也可以是子表，而其表尾必定是子表。,又稱列表。為了節(jié)省存儲單元，可用壓縮存儲方法只存儲非零元素。一般情況，三角矩陣的常數(shù)c均為零。常見的有對稱矩陣、三角矩陣。但當(dāng)原隊中只有一個結(jié)點時，該結(jié)點既是隊頭也是隊尾，故刪去此結(jié)點時亦需修改尾指針，且刪去此結(jié)點后隊列變空。 return x。 Qfrontnext=NULL。 x=sdata。 pnext=NULL。（3） 入隊：QueueNode *p=(QueueNode *)malloc(sizeof(QueueNode))。它是限制僅在表頭刪除和表尾插入的單鏈表。② 判隊空: return Qrear==Qfront。解決這個問題的方法至少有三種：　　① 另設(shè)一個標志位以區(qū)別隊列是空還是滿；　　② 設(shè)置一個計數(shù)器記錄隊列中元素的總數(shù)（即隊列長度）。4. 循環(huán)隊列：為充分利用數(shù)組空間，克服上溢，可將數(shù)組空間想象為一個環(huán)狀空間，并稱這種環(huán)狀數(shù)組表示的隊列為循環(huán)隊列?！　、诔鲫爼r：刪去front所指的元素，然后將front加1并返回被刪元素。3. 隊列（Queue）是只允許在一端進行插入，而在另一端進行刪除的運算受限的線性表。可采用鏈式存儲結(jié)構(gòu)來存儲棧?？諚r棧頂指針不能是0，只能是1。 進棧操作：進棧時，需要將S＞top加1， ①S＞top==StackSize1表示棧滿②上溢現(xiàn)象當(dāng)棧滿時，再做進棧運算產(chǎn)生空間溢出的現(xiàn)象。存儲密度越大，存儲空間的利用率越高。//② {//在帶頭結(jié)點的雙鏈表中，刪除結(jié)點*p，設(shè)*p為非終端結(jié)點①雙鏈表由頭指針head惟一確定的。涉及遍歷操作時，其終止條件就不再是像非循環(huán)鏈表那樣判別p或p＞next是否為空，而是判別它們是否等于某一指定指針，如頭指針或尾指針等。 Bnext=p。 Anext=Bnextnext。若在尾指針表示的單循環(huán)鏈表上實現(xiàn)，則只需修改指針，無須遍歷，其執(zhí)行時間是O(1)。: 用尾指針rear表示的單循環(huán)鏈表對開始結(jié)點a1和終端結(jié)點an查找時間都是O(1)。④//釋放結(jié)點ai的空間給存儲池算法的時間復(fù)雜度也是O（n）.p指向被刪除的前一個結(jié)點。⑤算法的時間主要耗費在查找結(jié)點上，故時間復(fù)雜度亦為O(n)。s=(ListNode *)malloc(sizeof(ListNode))。amp。表非空，p初始值指向開始結(jié)點 if(i==j) return p。 p=pnext。//從頭結(jié)點開始掃描//終端結(jié)點的指針域置空，或空表的頭結(jié)點指針域置空以上三個算法的時間復(fù)雜度均為O(n)。尾指針初值也指向頭結(jié)點頭結(jié)點數(shù)據(jù)域的陰影表示該部分不存儲信息。 　⒈由于開始結(jié)點的位置被存放在頭結(jié)點的指針域中,所以在鏈表的第一個位置上的操作就和在表的其它位置上操作一致,無須進行特殊處理。rear=p。② //將讀入的數(shù)據(jù)放入新結(jié)點的數(shù)據(jù)域中pnext=head。一個單鏈表可由頭指針唯一確定，因此單鏈表可以用頭指針的名字來命名。：把線性表的數(shù)據(jù)元素按邏輯次序依次存放在一組地址連續(xù)的存儲單元里的方法。(4)LocateNode（L，x）在L中查找第一個值為x 的元素，并返回該元素在L中的位置。，線性表中任意一個元素都可隨機存取，所以順序表是一種隨機存取結(jié)構(gòu)。,用一個正整數(shù)n表示。目前常用的描述算法語言有兩類：類Pascal和類C。關(guān)鍵字是能唯一標識一個元素的一個或多個數(shù)據(jù)項的組合。最常用的檢索、插入、刪除、更新、排序等。數(shù)組、廣義表、樹和圖等數(shù)據(jù)結(jié)構(gòu)都是非線性結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)一般包括以下三方面內(nèi)容：數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲結(jié)構(gòu)、數(shù)據(jù)的運算①數(shù)據(jù)的邏輯結(jié)構(gòu)是從邏輯關(guān)系上描述數(shù)據(jù)，與數(shù)據(jù)元素的存儲結(jié)構(gòu)無關(guān)，是獨立于計算機的。數(shù)據(jù)元素是數(shù)據(jù)的基本單位。 專業(yè)資料整理分享 自考02331數(shù)據(jù)結(jié)構(gòu)重點總結(jié)(最終修訂)第一章 概論：算法+數(shù)據(jù)結(jié)構(gòu)=程序。，即數(shù)據(jù)的組織形式。棧、隊列、串等都是線性結(jié)構(gòu)。③數(shù)據(jù)的運算。（3）索引存儲：索引表由若干索引項組成。算法與程序的區(qū)別：程序必須依賴于計算機程序語言，而一個算法可用自然語言、計算機程序語言、數(shù)學(xué)語言或約定的符號語言來描述。以上幾點最主要的是時間復(fù)雜性，時間復(fù)雜度常用漸進時間復(fù)雜度表示。第二章 線性表，而運算的具體實現(xiàn)是在存儲結(jié)構(gòu)上進行的。(3)GetNode（L，i） 取線性表L中的第i個元素。(6)DeleteList（L，i）刪除線性表L的第i個元素，刪除后表L的長度減1。順序表中結(jié)點ai 的存儲地址: LOC（ai）= LOC（a1）+（i1）*c刪除第i個結(jié)點移動次數(shù)為ni。①//生成新結(jié)點 ①//生成新結(jié)點//新結(jié)點插入空表 ?、矡o論鏈表是否為空，其頭指針都是指向頭結(jié)點的非空指針（空表中頭結(jié)點的指針域空），因此空表和非空表的處理也就統(tǒng)一了。//){ sdata=ch。 rnext=s。rnext=NULL。j=0。ji){//順指針向后掃描，直到pnext為NULL或i=j為止}//當(dāng)i0或i0時，找不到第i個結(jié)點//從開始結(jié)點比較。 while(pamp。//若p=NULL，則查找失敗，否則p指向值為key的結(jié)點時間復(fù)雜度為：O(n)：插入運算是將值為x的新結(jié)點插入到表的第i個結(jié)點的位置上，即插入到ai1與ai之間。④ pnext=s。//將ai從鏈上摘下free(r)。判斷空鏈表的條件是head==headnext。：循環(huán)鏈表的特點是無須增加存儲量，僅對表的鏈接方式稍作改變，即可使得表處理更加方便靈活。//①保存A表的頭結(jié)點位置//③釋放B表的頭結(jié)點//返回新循環(huán)鏈表的尾指針循環(huán)鏈表中沒有NU