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