《數(shù)據(jù)結構c語言版》知識點概括.doc

數(shù)據(jù)結構知識點概括第一章 概 論數(shù)據(jù)就是指能夠被計算機識別、存儲和加工處理的信息的載體。數(shù)據(jù)元素是數(shù)據(jù)的基本單位，可以由若干個數(shù)據(jù)項組成。數(shù)據(jù)項是具有獨立含義的最小標識單位。數(shù)據(jù)結構的定義：邏輯結構：從邏輯結構上描述數(shù)據(jù)，獨立于計算機。線性結構：一對一關系。線性結構：多對多關系。存儲結構：是邏輯結構用計算機語言的實現(xiàn)。順序存儲結構：如數(shù)組。鏈式存儲結構：如鏈表。索引存儲結構：稠密索引：每個結點都有索引項。稀疏索引：每組結點都有索引項。散列存儲結構：如散列表。數(shù)據(jù)運算。對數(shù)據(jù)的操作。定義在邏輯結構上，每種邏輯結構都有一個運算集合。常用的有：檢索、插入、刪除、更新、排序。數(shù)據(jù)類型：是一個值的集合以及在這些值上定義的一組操作的總稱。結構類型：由用戶借助于描述機制定義，是導出類型。 抽象數(shù)據(jù)類型ADT：是抽象數(shù)據(jù)的組織和與之的操作。相當于在概念層上描述問題。 優(yōu)點是將數(shù)據(jù)和操作封裝在一起實現(xiàn)了信息隱藏。程序設計的實質是對實際問題選擇一種好的數(shù)據(jù)結構，設計一個好的算法。算法取決于數(shù)據(jù)結構。算法是一個良定義的計算過程，以一個或多個值輸入，并以一個或多個值輸出。評價算法的好壞的因素：算法是正確的；執(zhí)行算法的時間；執(zhí)行算法的存儲空間（主要是輔助存儲空間）；算法易于理解、編碼、調試。時間復雜度：是某個算法的時間耗費，它是該算法所求解問題規(guī)模n的函數(shù)。漸近時間復雜度：是指當問題規(guī)模趨向無窮大時，該算法時間復雜度的數(shù)量級。評價一個算法的時間性能時，主要標準就是算法的漸近時間復雜度。算法中語句的頻度不僅與問題規(guī)模有關，還與輸入實例中各元素的取值相關。時間復雜度按數(shù)量級遞增排列依次為：常數(shù)階O（1）、對數(shù)階O（log2n）、線性階O（n）、線性對數(shù)階O（nlog2n）、平方階O（n2）、立方階O（n3）、k次方階O（nk）、指數(shù)階O（2n）?？臻g復雜度：是某個算法的空間耗費，它是該算法所求解問題規(guī)模n的函數(shù)。算法的時間復雜度和空間復雜度合稱算法復雜度。第二章 線性表線性表是由n0個數(shù)據(jù)元素組成的有限序列。n=0是空表；非空表，只能有一個開始結點，有且只能有一個終端結點。線性表上定義的基本運算：構造空表：Initlist（L）求表長：Listlength（L）取結點：GetNode（L，i）查找：LocateNode（L，x）插入：InsertList（L，x，i）刪除：Delete（L，i）順序表是按線性表的邏輯結構次序依次存放在一組地址連續(xù)的存儲單元中。在存儲單元中的各元素的物理位置和邏輯結構中各結點相鄰關系是一致的。地址計算：LOCa（i）=LOCa（1）+（i-1）*d；（首地址為1）在順序表中實現(xiàn)的基本運算：插入：平均移動結點次數(shù)為n/2；平均時間復雜度均為O（n）。 刪除：平均移動結點次數(shù)為（n-1）/2；平均時間復雜度均為O（n）。線性表的鏈式存儲結構中結點的邏輯次序和物理次序不一定相同，為了能正確表示結點間的邏輯關系，在存儲每個結點值的同時，還存儲了其后繼結點的地址信息（即指針或鏈）。這兩部分信息組成鏈表中的結點結構。 一個單鏈表由頭指針的名字來命名。單鏈表運算：建立單鏈表頭插法：s->next=head；head=s；生成的順序與輸入順序相反。平均時間復雜度均為O（n）。尾插法：head=rear=null；if（head=null） head=s；else r->next=s；r=s； 平均時間復雜度均為O（n）加頭結點的算法：對開始結點的操作無需特殊處理，統(tǒng)一了空表和非空表。查找按序號：與查找位置有關，平均時間復雜度均為O（n）。按值：與輸入實例有關，平均時間復雜度均為O（n）。插入運算：p=GetNode（L，i-1）；s->next=p->next；p->next=s；平均時間復雜度均為O（n）刪除運算：p=GetNode（L，i-1）；r=p->next；p->next=r->next；free（r）；平均時間復雜度均為O（n）單循環(huán)鏈表是一種首尾相接的單鏈表，終端結點的指針域指向開始結點或頭結點。鏈表終止條件是以指針等于頭指針或尾指針。采用單循環(huán)鏈表在實用中多采用尾指針表示單循環(huán)鏈表。優(yōu)點是查找頭指針和尾指針的時間都是O（1），不用遍歷整個鏈表。雙鏈表就是雙向鏈表，就是在單鏈表的每個結點里再增加一個指向其直接前趨的指針域prior，形成兩條不同方向的鏈。由頭指針head惟一確定。雙鏈表也可以頭尾相鏈接構成雙（向）循環(huán)鏈表。雙鏈表上的插入和刪除時間復雜度均為O （1）。順序表和鏈表的比較：基于空間： 順序表的存儲空間是靜態(tài)分配，存儲密度為1；適于線性表事先確定其大小時采用。鏈表的存儲空間是動態(tài)分配，存儲密度1；適于線性表長度變化大時采用。基于時間：順序表是隨機存儲結構，當線性表的操作主要是查找時，宜采用。以插入和刪除操作為主的線性表宜采用鏈表做存儲結構。若插入和刪除主要發(fā)生在表的首尾兩端，則宜采用尾指針表示的單循環(huán)鏈表。第三章 棧和隊列棧（Stack）是僅限制在表的一端進行插入和刪除運算的線性表，稱插入、刪除這一端為棧頂，另一端稱為棧底。表中無元素時為空棧。棧的修改是按后進先出的原則進行的，我們又稱棧為LIFO表（Last In First Out）。通常棧有順序棧和鏈棧兩種存儲結構。棧的基本運算有六種： 構造空棧：InitStack（S）判?？眨?StackEmpty（S）判棧滿： StackFull（S）進棧： Push（S，x）退棧： Pop（S）取棧頂元素：StackTop（S）在順序棧中有“上溢”和“下溢”的現(xiàn)象。 “上溢”是棧頂指針指出棧的外面是出錯狀態(tài)?！跋乱纭笨梢员硎緱榭諚?，因此用來作為控制轉移的條件。順序棧中的基本操作有六種：構造空棧 判?？?判棧滿 進棧 退棧 取棧頂元素鏈棧則沒有上溢的限制，因此進棧不要判棧滿。鏈棧不需要在頭部附加頭結點，只要有鏈表的頭指針就可以了。鏈棧中的基本操作有五種：構造空棧 判棧空 進棧 退棧 取棧頂元素隊列（Queue）是一種運算受限的線性表，插入在表的一端進行，而刪除在表的另一端進行，允許刪除的一端稱 為隊頭（front），允許插入的一端稱為隊尾（rear） ，隊列的操作原則是先進先出的，又稱作FIFO表（First In First Out） .隊列也有順序存儲和鏈式存儲兩種存儲結構。隊列的基本運算有六種：置空隊：InitQueue（Q）判隊空：QueueEmpty（Q）判隊滿：QueueFull（Q）入隊：EnQueue（Q，x）出隊：DeQueue（Q）取隊頭元素：QueueFront（Q）順序隊列的“假上溢”現(xiàn)象：由于頭尾指針不斷前移，超出向量空間。這時整個向量空間及隊列是空的卻產生了“上溢”現(xiàn)象。為了克服“假上溢”現(xiàn)象引入循環(huán)向量的概念，是把向量空間形成一個頭尾相接的環(huán)形，這時隊列稱循環(huán)隊列。判定循環(huán)隊列是空還是滿，方法有三種： 一種是另設一個布爾變量來判斷；第二種是少用一個元素空間，入隊時先測試（rear+1）%m = front）？ 滿：空；第三種就是用一個計數(shù)器記錄隊列中的元素的總數(shù)。隊列的鏈式存儲結構稱為鏈隊列，一個鏈隊列就是一個操作受限的單鏈表。為了便于在表尾進行插入（入隊）的 操作，在表尾增加一個尾指針，一個鏈隊列就由一個頭指針和一個尾指針唯一地確定。鏈隊列不存在隊滿和上溢的問題。在鏈隊列的出隊算法中，要注意當原隊中只有一個結點時，出隊后要同進修改頭尾指針并使隊列變空。第四章 串串是零個或多個字符組成的有限序列?？沾菏侵搁L度為零的串，也就是串中不包含任何字符（結點）?？瞻状褐复邪粋€或多個空格字符的串。在一個串中任意個連續(xù)字符組成的子序列稱為該串的子串，包含子串的串就稱為主串。子串在主串中的序號就是指子串在主串中首次出現(xiàn)的位置?？沾侨我獯淖哟?，任意串是自身的子串。串分為兩種： 串常量在程序中只能引用不能改變；串變量的值可以改變。串的基本運算有： 求串長strlen（char*s）串復制strcpy（char*to，char*from）串聯(lián)接strcat（char*to，char*from）串比較charcmp（char*s1，char*s2）字符定位strchr（char*s，charc）串是特殊的線性表（結點是字符），所以串的存儲結構與線性表的存儲結構類似。串的順序存儲結構簡稱為順序串。順序串又可按存儲分配的不同分為： 靜態(tài)存儲分配：直接用定長的字符數(shù)組來定義。優(yōu)點是涉及串長的操作速度 快，但不適合插入、鏈接操作。動態(tài)存儲分配：是在定義串時不分配存儲空間，需要使用時按所需串的長度分配存儲單元。串的鏈式存儲就是用單鏈表的方式存儲串值，串的這種鏈式存儲結構簡稱為鏈串。鏈串與單鏈表的差異只是它的 結點數(shù)據(jù)域為單個字符。為了解決“存儲密度”低的狀況，可以讓一個結點存儲多個字符，即結點的大小。順序串上子串定位的運算：又稱串的“模式匹配”或“串匹配”，是在主串中查找出子串出現(xiàn)的位置。在串匹配中，將主串稱為目標（串），子串稱為模式（串）。這是比較容易理解的，串匹配問題就是找出給定模式串P在給定目標串T中首次出現(xiàn)的有效位移或者是全部有效位移。最壞的情況下時間復雜度是O（n-m+1）m），假如m與n同階的話則它是O（n2）。鏈串上的子串定位運算位移是結點地址而不是整數(shù)第五章 多維數(shù)組數(shù)組一般用順序存儲的方式表示。存儲的方式有： 行優(yōu)先順序，也就是把數(shù)組逐行依次排列。PASCAL、C 列優(yōu)先順序，就是把數(shù)組逐列依次排列。FORTRAN地址的計算方法： 按行優(yōu)先順序排列的數(shù)組：LOCa（ij）=LOCa（11）+（i-1）*n+（j-1）*d. 按列優(yōu)先順序排列的數(shù)組：LOCa（ij）=LOCa（11）+（j-1）*n+（i-1）*d.矩陣的壓縮存儲：為多個相同的非零元素分配一個存儲空間；對零元素不分配空間。特殊矩陣的概念：所謂特殊矩陣是指非零元素或零元素分布有一定規(guī)律的矩陣。稀疏矩陣的概念：一個矩陣中若其非零元素的個數(shù)遠遠小于零元素的個數(shù)，則該矩陣稱為稀疏矩陣。 特殊矩陣的類型： 對稱矩陣：滿足a（ij）=a（ji）。元素總數(shù)n（n+1）/2.I=max（i，j），J=min（i，j），LOCa（ij）=LOC（sa0）+（I*（I+1）/2+J）*d.三角矩陣： 上三角陣：k=i*（2n-i+1）/2+j-i，LOCa（ij）=LOC（sa0）+k*d. 下三角陣：k=i*（i+1）/2+j，LOCa（ij）=LOC（sa0）+k*d.對角矩陣：k=2i+j，LOCa（ij）=LOC（sa0）+k*d.稀疏矩陣的壓縮存儲方式用三元組表把非零元素的值和它所在的行號列號做為一個結點存放在一起，用這些結點組成的一個線性表來表示。但這種壓縮存儲方式將失去隨機存儲功能。加入行表記錄每行的非零元素在三元組表中的起始位置，即帶行表的三元組表。第六章 樹樹是n個結點的有限集合，非空時必須滿足：只有一個稱為根的結點；其余結點形成m個不相交的子集，并稱根的子樹。根是開始結點；結點的子樹數(shù)稱度；度為0的結點稱葉子（終端結點）；度不為0的結點稱分支結點（非終端結點）；除根外的分支結點稱內部結點；有序樹是子樹有左，右之分的樹；無序樹是子樹沒有左，右之分的樹；森林是m個互不相交的樹的集合；樹的四種不同表示方法：樹形表示法；嵌套集合表示法；凹入表示法廣義表表示法。二叉樹的定義：是n0個結點的有限集，它是空集（n=0）或由一個根結點及兩棵互不相交的分別稱作這個根的左子樹和右子樹的二叉樹組成。二叉樹不是樹的特殊情形，與度數(shù)為2的有序樹不同。二叉樹的4個重要性質： 二叉樹上第i層上的結點數(shù)目最多為2（i-1）（i1）。；深度為k的二叉樹至多有（2k）-1個結點（k1）；在任意一棵二叉樹中，若終端結點的個數(shù)為n0，度為2的結點數(shù)為n2，則n0=n2+1；具有n個結點的完全二叉樹的深度為int（log2n）+1.滿二叉樹是一棵深度為k，結點數(shù)為（2k）-1的二叉樹；完全二叉樹是滿二叉樹在最下層自右向左去處部分結點；二叉樹的順序存儲結構就是把二叉樹的所有結點按照層次順序存儲到連續(xù)的存儲單元中。（存儲前先將其畫成完全二叉樹）樹的存儲結構多用的是鏈式存儲。BinTNode的結構為lchild|data|rchild，把所有BinTNode類型的結點，加上一個指向根結點的BinTree型頭指針就構成了二叉樹的鏈式存儲結構，稱為二叉鏈表。它就是由根指針root唯一確定的。共有2n個指針域，n+1個空指針。根據(jù)訪問結點的次序不同可得三種遍歷：先序遍歷（前序遍歷或先根遍歷），中序遍歷（或中根遍歷）、后序遍歷（或后根遍歷）。時間復雜度為O（n）。利用二叉鏈表中的n+1個空指針域來存放指向某種遍歷次序下的前趨結點和后繼結點的指針，這些附加的指針就稱為“線索”，加上線索的二叉鏈表就稱為線索鏈表。線索使得查找中序前趨和中序后繼變得簡單有效，但對于查找指定結點的前序前趨和后序后繼并沒有什么作用。樹和森林及二叉樹的轉換是唯一對應的。轉換方法： 樹變二叉樹：兄弟相連，保留長子的連線。二叉樹變樹：結點的右孩子與其雙親連。森林變二叉樹：樹變二叉樹，各個樹的根相連。樹的存儲結構：有雙親鏈表表示法：結點data | parent，對于求指定結點的雙親或祖先十分方便，但不適于求指定結點的孩子及后代。孩子鏈表表示法：為樹中每個結點data | next設置一個孩子鏈表firstchild，并將data | firstchild存放在一個向量中。雙親孩子鏈表表示法：將雙親鏈表和孩子鏈表結合。孩子兄弟鏈表表示法：結點結構leftmostchild |data | rightsibing，附加兩個分別指向該結點的最左孩子和右鄰兄弟的指針域。樹的前序遍歷與相對應的二叉樹的前序遍歷一致；樹的后序遍歷與相對應的二叉樹的中序遍歷一致。樹的帶權路徑長度是樹中所有葉結點的帶權路徑長度之和。樹的帶權路徑長度最小的二叉樹就稱為最優(yōu)二叉樹（即哈夫曼樹）。在葉子的權值相同的二叉樹中，完全二叉樹的路徑長度最短。哈夫曼樹有n個葉結點，共有2n-1個結點，沒有度為1的結點，這類樹又稱為嚴格二叉樹。變長編碼技術可以使頻度高的字符編碼短，而頻度低的字符編碼長，但是變長編碼可能使解碼產生二義性。如00、01、0001這三個碼無法在解碼時確定是哪一個，所以要求在字符編碼時任一字符的編碼都不是其他字符編碼的前綴，這種碼稱為前綴碼（其實是非前綴碼）。哈夫曼樹的應用最廣泛地是在編碼技術上，它能夠容易地求出給定字符集及其概率分布的最優(yōu)前綴碼。哈夫曼編碼的構造很容易，只要畫好了哈夫曼樹，按分支情況在左路徑上寫代碼0，右路徑上寫代碼1，然后從上到下到葉結點的相應路徑上的代碼的序列就是該結點的最優(yōu)前綴碼。第七章 圖圖的邏輯結構特征就是其結點（頂點）的前趨和后繼的個數(shù)都是沒有限制的，即任意兩個結點之間之間都可能相關。圖GraphG=（V，E），V是頂點的有窮非空集合，E是頂點偶對的有窮集。有向圖Digraph：每條邊有方向；無向圖Undigraph：每條邊沒有方向。有向完全圖：具有n*（n-1）條邊的有向圖；無向完全圖：具有n*（n-1）/2條邊的無向圖；有根圖：有一個頂點有路徑到達其它頂點的有向圖；簡單路徑：是經過頂點不同的路徑；簡單回路是開始和終端重的簡單路徑；網絡：是帶權的圖。圖的存儲結構：鄰接矩陣表示法：用一個n階方陣來表示圖的結構是唯一的，適合稠密圖。無向圖：鄰接矩陣是對稱的。有向圖：行是出度，列是入度。建立鄰接矩陣算法的時間是O（n+n2+e），其時間復雜度為O（n2）鄰接表表示法：用頂點表和鄰接表構成不是唯一的，適合稀疏圖。頂點表結構 vertex | firstedge，指針域存放鄰接表頭指針。鄰接表：用頭指針確定。 無向圖稱邊表；有向圖又分出邊表和逆鄰接表；鄰接表結點結構為 adjvex | next，時間復雜度為O（n+e）。，空間復雜度為O（n+e）。圖的遍歷： 深度優(yōu)先遍歷：借助于鄰接矩陣的列。使用棧保存已訪問結點。廣度優(yōu)先遍歷：借助于鄰接矩陣的行。使用隊列保存已訪問結點。生成樹的定義：若從圖的某個頂點出發(fā)，可以系統(tǒng)地訪問到圖中所有頂點，則遍歷時經過的邊和圖的所有頂點構成的子圖稱作該圖的生成樹。最小生成樹：圖的生成樹不唯一，從不同的頂點出發(fā)可得到不同的生成樹，把權值最小的生成樹稱為最小生成樹（MST）。構造最小生成樹的算法： Prim算法的時間復雜度為O（n2）與邊數(shù)無關適于稠密圖。Kruskal算法的時間復雜度為O（lge），主要取決于邊數(shù)，較適合于稀疏圖。最短路徑的算法：Dijkstra算法，時間復雜度為O（n2）。類似于prim算法。拓撲排序：是將有向無環(huán)圖G中所有頂點排成一個線性序列，若<u，v>E（G），則在線性序列u在v之前，這種線性序列稱為拓撲序列。拓撲排序也有兩種方法：無前趨的頂點優(yōu)先，每次輸出一個無前趨的結點并刪去此結點及其出邊，最后得到的序列即拓撲序列。無后繼的結點優(yōu)先：每次輸出一個無后繼的結點并刪去此結點及其入邊，最后得到的序列是逆拓撲序列。第八章 排序記錄中可用某一項來標識一個記錄，則稱為關鍵字項，該數(shù)據(jù)項的值稱為關鍵字。排序是使文件中的記錄按關鍵字遞增（或遞減）次序排列起來?；静僮鳎罕容^關鍵字大?。桓淖冎赶蛴涗浀闹羔樆蛞苿佑涗?。存儲結構：順序結構、鏈表結構、索引結構。經過排序后這些具有相同關鍵字的記錄之間的相對次序保持不變，則稱這種排序方法是穩(wěn)定的，否則排序算法是不穩(wěn)定的。排序過程中不涉及數(shù)據(jù)的內、外存交換則稱之為“內部排序”（內排序），反之，若存在數(shù)據(jù)的內外存交換，則稱之為外排序。內部排序方法可分五類：插入排序、選擇排序、交換排序、歸并排序和分配排序。評價排序算法好壞的標準主要有兩條：執(zhí)行時間和所需的輔助空間，另外算法的復雜程序也是要考慮的一個因素。插入排序：直接插入排序： 逐個向前插入到合適位置。哨兵（監(jiān)視哨）有兩個作用： 作為臨變量存放Ri是在查找循環(huán)中用來監(jiān)視下標變量j是否越界。直接插入排序是就地的穩(wěn)定排序。時間復雜度為O（n2），比較次數(shù)為（n+2）（n-1）/2；移動次數(shù)為（n+4）（n-1）/2；希爾排序： 等間隔的數(shù)據(jù)比較并按要求順序排列，最后間隔為1.希爾排序是就地的不穩(wěn)定排序。時間復雜度為O（n1.25），比較次數(shù)為（n1.25）；移動次數(shù)為（1.6n1.25）；交換排序：冒泡排序：自下向上確定最輕的一個。自上向下確定最重的一個。自下向上確定最輕的一個，后自上向下確定最重的一個。冒泡排序是就地的穩(wěn)定排序。時間復雜度為O（n2），比較次數(shù)為n（n-1）/2；移動次數(shù)為3n（n-1）/2；快速排序：以第一個元素為參考基準，設定、動兩個指針，發(fā)生交換后指針交換位置，直到指針重合。重復直到排序完成?？焖倥判蚴欠蔷偷氐牟环€(wěn)定排序。時間復雜度為O（nlog2n），比較次數(shù)為n（n-1）/2；選擇排序：直接選擇排序： 選擇最小的放在比較區(qū)前。直接選擇排序就地的不穩(wěn)定排序。時間復雜度為O（n2）。比較次數(shù)為n（n-1）/2；堆排序 建堆：按層次將數(shù)據(jù)填入完全二叉樹，從int（n/2）處向前逐個調整位置。然后將樹根與最后一個葉子交換值并斷開與樹的連接并重建堆，直到全斷開。堆排序是就地不穩(wěn)定的排序，時間復雜度為O（nlog2n），不適宜于記錄數(shù)較少的文件。歸并排序： 先兩個一組排序，形成（n+1）/2組，再將兩組并一組，直到剩下一組為止。歸并排序是非就地穩(wěn)定排序，時間復雜度是O（nlog2n），分配排序：箱排序： 按關鍵字的取值范圍確定箱子數(shù)，按關鍵字投入箱子，鏈接所有非空箱。箱排序的平均時間復雜度是線性的O（n）。基數(shù)排序：從低位到高位依次對關鍵字進行箱排序。基數(shù)排序是非就穩(wěn)定的排序，時間復雜度是O（d*n+d*rd）。各種排序方法的比較和選擇： 待排序的記錄數(shù)目n；n較大的要用時間復雜度為O（nlog2n）的排序方法；記錄的大小（規(guī)模）；記錄大最好用鏈表作為存儲結構，而快速排序和堆排序在鏈表上難于實現(xiàn)；關鍵字的結構及其初始狀態(tài)；對穩(wěn)定性的要求；語言工具的條件； 存儲結構；時間和輔助空間復雜度。第九章 查找查找的同時對表做修改操作（如插入或刪除）則相應的表稱之為動態(tài)查找表，否則稱之為靜態(tài)查找表。衡量查找算法效率優(yōu)劣的標準是在查找過程中對關鍵字需要執(zhí)行的平均比較次數(shù)（即平均查找長度ASL）。線性表查找的方法： 順序查找：逐個查找，ASL=（n+1）/2；二分查找：取中點int（n/2）比較，若小就比左區(qū)間，大就比右區(qū)間。用二叉判定樹表示。ASL=（每層結點數(shù)*層數(shù)）/N.分塊查找。要求“分塊有序”，將表分成若干塊內部不一定有序，并抽取各塊中的最大關鍵字及其位置建立有序索引表。二叉排序樹（BST）定義是：二叉排序樹是空樹或者滿足如下性質的二叉樹： 若它的左子樹非空，則左子樹上所有結點的值均小于根結點的值；若它的右子樹非空，則右子樹上所有結點的值均大于根結點的值；左、右子樹本身又是一棵二叉排序樹。二叉排序樹的插入、建立、刪除的算法平均時間性能是O（nlog2n）。二叉排序樹的刪除操作可分三種情況進行處理： *P是葉子，則直接刪除*P，即將*P的雙親*parent中指向*P的指針域置空即可。*P只有一個孩子*child，此時只需將*child和*p的雙親直接連接就可刪去*p.*p有兩個孩子，則先將*p結點的中序后繼結點的數(shù)據(jù)到*p，刪除中序后繼結點。關于B-樹（多路平衡查找樹）。它適合在磁盤等直接存取設備上組織動態(tài)的查找表，是一種外查找算法。建立的方式是從下向上拱起。散列技術：將結點按其關鍵字的散列地址存儲到散列表的過程稱為散列。散列函數(shù)的選擇有兩條標準：簡單和均勻。常見的散列函數(shù)構的造方法：平方取中法：hash=int（x2）%100）除余法：表長為m，hash=x%m相乘取整法：hash=int（m*（x*A-int（x*A）；A=0.618 隨機數(shù)法：hash=random（x）。處理沖突的方法：開放定址法： 一般形式為hi=（h（key）+di）%m1im-1，開放定址法要求散列表的裝填因子1. 開放定址法類型： 線性探查法：address=（hash（x）+i）%m；二次探查法：address=（hash（x）+i2）%m； 雙重散列法：address=（hash（x）+i*hash（y）%m； 拉鏈法： 是將所有關鍵字為同義詞的結點鏈接在同一個單鏈表中。 拉鏈法的優(yōu)點： 拉鏈法處理沖突簡單，且無堆積現(xiàn)象； 鏈表上的結點空間是動態(tài)申請的適于無法確定表長的情況； 拉鏈法中可以大于1，結點較大時其指針域可忽略，因此節(jié)省空間；拉鏈法構造的散列表刪除結點易實現(xiàn)。拉鏈法也有缺點：當結點規(guī)模較小時，用拉鏈法中的指針域也要占用額外空間，還是開放定址法省空間。第十章 排序10.1 排序的基本概念 10.2 插入排序10.3 選擇排序10.4 交換排序本章主要知識點：排序的基本概念和衡量排序算法優(yōu)劣的標準，其中衡量標準有算法的時間復雜度、空間復雜度和穩(wěn)定性直接插入排序，希爾排序直接選擇排序，堆排序冒泡排序，快速排序10.1排序的基本概念1.排序是對數(shù)據(jù)元素序列建立某種有序排列的過程。2.排序的目的：便于查找。3.關鍵字是要排序的數(shù)據(jù)元素集合中的一個域，排序是以關鍵字為基準進行的。 關鍵字分主關鍵字和次關鍵字兩種。對要排序的數(shù)據(jù)元素集合來說，如果關鍵字滿足數(shù)據(jù)元素值不同時該關鍵字的值也一定不同，這樣的關鍵字稱為主關鍵字。不滿足主關鍵字定義的關鍵字稱為次關鍵字。4.排序的種類：分為內部排序和外部排序兩大類。 若待排序記錄都在內存中，稱為內部排序；若待排序記錄一部分在內存，一部分在外存，則稱為外部排序。 注：外部排序時，要將數(shù)據(jù)分批調入內存來排序，中間結果還要及時放入外存，顯然外部排序要復雜得多。 5.排序算法好壞的衡量標準：(1)時間復雜度 它主要是分析記錄關鍵字的比較次數(shù)和記錄的移動次數(shù)。(2)空間復雜度算法中使用的內存輔助空間的多少。(3)穩(wěn)定性若兩個記錄A和B的關鍵字值相等，但排序后A、B的先后次序保持不變，則稱這種排序算法是穩(wěn)定的。10.2 插入排序 插入排序的基本思想是：每步將一個待排序的對象，按其關鍵字大小，插入到前面已經排好序的一組對象的適當位置上，直到對象全部插入為止。 簡言之，邊插入邊排序，保證子序列中隨時都是排好序的。 常用的插入排序有：直接插入排序和希爾排序兩種。10.2.1 直接插入排序1、其基本思想是： 順序地把待排序的數(shù)據(jù)元素按其關鍵字值的大小插入到已排序數(shù)據(jù)元素子集合的適當位置。 例1：關鍵字序列T=（13，6，3，31，9，27，5，11），請寫出直接插入排序的中間過程序列。初始關鍵字序列：【13】, 6, 3, 31, 9, 27, 5, 11第一次排序： 【6, 13】, 3, 31, 9, 27, 5, 11第二次排序： 【3, 6, 13】, 31, 9, 27, 5, 11第三次排序： 【3, 6, 13，31】, 9, 27, 5, 11第四次排序： 【3, 6, 9, 13，31】, 27, 5, 11第五次排序： 【3, 6, 9, 13，27, 31】, 5, 11第六次排序： 【3, 5, 6, 9, 13，27, 31】, 11第七次排序： 【3, 5, 6, 9, 11，13，27, 31】 注：方括號 中為已排序記錄的關鍵字，下劃橫線的 關鍵字表示它對應的記錄后移一個位置。2.直接插入排序算法public static void insertSort(int a)int i, j, temp;int n = a.Length;for(i = 0; i < n - 1; i +) temp = ai + 1; j = i; while(j > -1 && temp < aj)aj + 1 = aj;j -; aj + 1 = temp;初始關鍵字序列：【13】, 6, 3, 31, 9, 27, 5, 11第一次排序： 【6, 13】, 3, 31, 9, 27, 5, 11第二次排序： 【3, 6, 13】, 31, 9, 27, 5, 113、直接插入排序算法分析(1)時間效率：當數(shù)據(jù)有序時，執(zhí)行效率最好，此時的時間復雜度為O(n)；當數(shù)據(jù)基本反序時，執(zhí)行效率最差，此時的時間復雜度為O(n2)。所以當數(shù)據(jù)越接近有序，直接插入排序算法的性能越好。 (2)空間效率：僅占用1個緩沖單元O（1） (3)算法的穩(wěn)定性：穩(wěn)定8.2.2 希爾（shell）排序 （又稱縮小增量排序）1、基本思想：把整個待排序的數(shù)據(jù)元素分成若干個小組，對同一小組內的數(shù)據(jù)元素用直接插入法排序；小組的個數(shù)逐次縮小，當完成了所有數(shù)據(jù)元素都在一個組內的排序后排序過程結束。 2、技巧：小組的構成不是簡單地“逐段分割”，而是將相隔某個增量d的記錄組成一個小組,讓增量d逐趟縮短（例如依次取5,3,1），直到d1為止。3、優(yōu)點：讓關鍵字值小的元素能很快前移，且序列若基本有序時，再用直接插入排序處理，時間效率會高很多。例2：設待排序的序列中有12個記錄，它們的關鍵字序列 T=(65，34，25，87，12，38，56，46，14，77，92，23），請寫出希爾排序的具體實現(xiàn)過程。public static void shellSort(int a, int d, int numOfD)int i, j, k, m, span;int temp;int n = a.Length;for(m = 0; m < numOfD; m +)/共numOfD次循環(huán)span = dm; /取本次的增量值for(k = 0; k < span; k +)/共span個小組for(i = k; i < n-span; i = i + span)temp = ai+span;j = i;while(j > -1 && temp < aj)aj + span = aj;j = j - span;aj + span = temp;算法分析：開始時d 的值較大，子序列中的對象較少，排序速度較快；隨著排序進展，d 值逐漸變小，子序列中對象個數(shù)逐漸變多，由于前面工作的基礎，大多數(shù)記錄已基本有序，所以排序速度仍然很快。 時間效率：O(n(log2n)2) 空間效率：O（1）因為僅占用1個緩沖單元 算法的穩(wěn)定性：不穩(wěn)定 練習：1. 欲將序列（Q, H, C, Y, P, A, M, S, R, D, F, X）中的關鍵碼按字母升序重排，則初始d為4的希爾排序一趟的結果是？答： 原始序列： Q, H, C, Y, P, A, M, S, R, D, F, Xshell一趟后： P,A,C,S,Q,D,F,X,R,H,M,Y2. 以關鍵字序列（256，301，751，129，937，863，742，694，076，438）為例，寫出執(zhí)行希爾排序（取d=5,3,1）算法的各趟排序結束時，關鍵字序列的狀態(tài)。解：原始序列: 256，301，751，129，937，863，742，694，076，438希爾排序第一趟d=5 256 301 694 076 438 863 742 751 129 937 第二趟d=3 076 301 129 256 438 694 742 751 863 937第三趟d=1 076 129 256 301 438 694 742 751 863 93710.3 選擇排序 選擇排序的基本思想是：每次從待排序的數(shù)據(jù)元素集合中選取關鍵字最?。ɑ蜃畲螅┑臄?shù)據(jù)元素放到數(shù)據(jù)元素集合的最前（或最后），數(shù)據(jù)元素集合不斷縮小，當數(shù)據(jù)元素集合為空時選擇排序結束。常用的選擇排序算法： （1）直接選擇排序 （2）堆排序10.3.1直接選擇排序1、其基本思想 每經過一趟比較就找出一個最小值，與待排序列最前面的位置互換即可。（即從待排序的數(shù)據(jù)元素集合中選取關鍵字最小的數(shù)據(jù)元素并將它與原始數(shù)據(jù)元素集合中的第一個數(shù)據(jù)元素交換位置；然后從不包括第一個位置的數(shù)據(jù)元素集合中選取關鍵字最小的數(shù)據(jù)元素并將它與原始數(shù)據(jù)集合中的第二個數(shù)據(jù)元素交換位置；如此重復，直到數(shù)據(jù)元素集合中只剩一個數(shù)據(jù)元素為止。）2、優(yōu)缺點優(yōu)點：實現(xiàn)簡單缺點：每趟只能確定一個元素，表長為n時需要n-1趟例3：關鍵字序列T= （21，25，49，25*，16，08），請給出直接選擇排序的具體實現(xiàn)過程。原始序列： 21，25，49，25*，16，08第1趟 08，25，49，25*，16，21第2趟 08，16, 49，25*，25，21第3趟 08，16, 21，25*，25，49第4趟 08，16, 21，25*，25，49第5趟 08，16, 21，25*，25，49public static void selectSort(int a)int i, j, small;int temp;int n = a.Length;for(i = 0; i < n - 1; i +) small = i; /設第i個數(shù)據(jù)元素最小 for(j = i + 1; j < n; j +)/尋找最小的數(shù)據(jù)元素 if(aj < asmall) small = j; /記住最小元素的下標 if(small != i) /當最小元素的下標不為i時交換位置 temp = ai; ai = asmall; asmall = temp; 3、算法分析時間效率： O(n2)雖移動次數(shù)較少，但比較次數(shù)仍多。 空間效率：O（1）沒有附加單元（僅用到1個temp)算法的穩(wěn)定性：不穩(wěn)定4、穩(wěn)定的直接選擇排序算法例：關鍵字序列T= （21，25，49，25*，16，08），請給出穩(wěn)定的直接選擇排序的具體實現(xiàn)過程。原始序列： 21，25，49，25*，16，08第1趟08, 21 , 25 , 49 , 25 *, 16 第2趟08，16, 21，25，49 ，25 *第3趟08，16, 21，25，49 ，25 *第4趟08，16, 21，25，49 ，25 *第5趟08，16, 21，25，25 * ，49public static void selectSort2(int a)int i,j,small;int temp;int n = a.Length;for(i = 0; i < n-1; i+) small = i; for(j = i+1; j < n; j+) /尋找最小的數(shù)據(jù)元素 if(aj < asmall) small = j; /記住最小元素的下標 if(small != i)temp = asmall; for(j = small; j > i; j-) /把該區(qū)段尚未排序元素依次后移aj = aj-1;ai = temp; /插入找出的最小元素 8.3.2 堆排序1. 什么是堆？ 2. 怎樣建堆？ 3. 怎樣堆排序？堆的定義：設有n個數(shù)據(jù)元素的序列 k0，k1，kn-1，當且僅當滿足下述關系之一時，稱之為堆。 解釋：如果讓滿足以上條件的元素序列 （k，k，kn）順次排成一棵完全二叉樹，則此樹的特點是： 樹中所有結點的值均大于（或小于）其左右孩子，此樹的根結點（即堆頂）必最大（或最?。＠?：有序列T1=（08, 25, 49, 46, 58, 67）和序列T2=（91, 85, 76, 66, 58, 67, 55）,判斷它們是否 “堆”？2. 怎樣建堆？步驟：從第一個非終端結點開始往前逐步調整，讓每個雙親大于（或小于）子女，直到根結點為止。終端結點（即葉子）沒有任何子女，無需單獨調整例：關鍵字序列T= (21，25，49，25*，16，08），請建最大堆。解：為便于理解，先將原始序列畫成完全二叉樹的形式： 這樣可以很清晰地從(n-1-1)/2開始調整。public static void createHeap(int a, int n, int h)int i, j, flag;int temp;i = h; j = 2 * i + 1; / j為i結點的左孩子結點的下標temp = ai;flag = 0; while(j < n && flag != 1)/尋找左右孩子結點中的較大者,j為其下標if(j < n - 1 && aj < aj + 1) j+;if (temp >= aj) /ai>=ajflag = 1; /標記結束篩選條件else/否則把aj上移ai = aj;i = j;j = 2 * i + 1;ai = temp; 利用上述createHeap（a,n,h）函數(shù)，初始化創(chuàng)建最大堆的過程就是從第一個非葉子結點ai開始，到根結點a0為止，循環(huán)調用createHeap（a,n,h）的過程。初始化創(chuàng)建最大堆算法如下：public static void initCreateHeap(int a)int n = a.Length;for(int i = (n-1-1) / 2; i >= 0; i -)createHeap(a, n, i);3. 怎樣進行整個序列的堆排序？*基于初始堆進行堆排序的算法步驟： 堆的第一個對象a0具有最大的關鍵碼，將a0與an-1對調，把具有最大關鍵碼的對象交換到最后;再對前面的n-1個對象，使用堆的調整算法，重新建立堆（調整根結點使之滿足最大堆的定義）。結果具有次最大關鍵碼的對象又上浮到堆頂，即a0位置;再對調a0和an-2，然后對前n-2個對象重新調整，如此反復，最后得到全部排序好的對象序列。例5：對剛才建好的最大堆進行排序：public static void heapSort(int a)int temp;int n = a.Length;initCreateHeap(a); /初始化創(chuàng)建最大堆for(int i = n - 1; i > 0; i -)/當前最大堆個數(shù)每次遞減1/把堆頂a0元素和當前最大堆的最后一個元素交換temp = a0;a0 = ai;ai = temp;createHeap(a,i, 0); /調整根結點滿足最大堆4、堆排序算法分析：時間效率：O(nlog2n)?？臻g效率：O(1)。穩(wěn)定性： 不穩(wěn)定。練習1：以下序列是堆的是（ ）75,65,30,15,25,45,20,10 B. 75,65,45,10,30,25,20,15C. 75,45,65,30,15,25,20,10 D. 75,45,65,10,25,30,20,15 練習2：有一組數(shù)據(jù)15,9,7,8,20,1,7*,4，建成的最小堆為（ ）。A.1,4,8,9,20,7,15,7* B.1,7,15,7*,4,8,20,9C.1,4,7,8,20,15,7*,9 D.以上都不對練習3：已知序列503，87，512，61，908，170，897，275，653，462，寫出采用堆排序對該序列作非遞減排列時的排序過程。排序好的序列為：61，87，170，275，462，503，512，653，897，90810.4 交換排序交換排序的基本思想是：利用交換數(shù)據(jù)元素的位置進行排序的方法。交換排序的主要算法有： 1) 冒泡排序 2) 快速排序10.4.1 冒泡排序1、基本思路：每趟不斷將記錄兩兩比較，并按“前小后大”（或“前大后小”）規(guī)則交換。2、優(yōu)點：每趟結束時，不僅能擠出一個最大值到最后面位置，還能同時部分理順其他元素；一旦下趟沒有交換發(fā)生，還可以提前結束排序。例：關鍵字序列 T=(21，25，49，25*，16，08），請按從小到大的順序，寫出冒泡排序的具體實現(xiàn)過程。初態(tài)：21，25，49， 25*，16， 08第1趟21，25，25*，16， 08 ， 49第2趟21，25， 16， 08 ，25*，49第3趟21，16， 08 ，25， 25*，49第4趟16，08 ，21， 25， 25*，49第5趟08，16， 21， 25， 25*，493、冒泡排序算法public static void bubbleSort(int a)int i, j, flag=1;int temp;int n = a.Length;for(i = 1; i < n && flag = 1; i+)flag = 0;for(j = 0; j < n-i; j+)if(aj > aj+1)flag = 1;temp = aj;aj = aj+1;aj+1 = temp;4、冒泡排序的算法分析時間效率：O（n2) 因為要考慮最壞情況（數(shù)據(jù)元素全部逆序），當然最好情況是數(shù)據(jù)元素已全部排好序，此時循環(huán)n-1次，時間復雜度為O（n) 空間效率：O（1） 只在交換時用到一個緩沖單元 穩(wěn) 定 性： 穩(wěn)定 25和25*在排序前后的次序未改變練習：關鍵字序列 T=(31，15，9，25，16，28），請按從小到大的順序，寫出冒泡排序的具體實現(xiàn)過程。初態(tài)：31，15，9， 25，16， 28第1趟15，9，25，16， 28， 31第2趟9，15， 16， 25，28，31第3趟9，15， 16，25， 28，311、基本思想：設數(shù)組a中存放了n個數(shù)據(jù)元素，low為數(shù)組的低端下標，high為數(shù)組的高端下標，從數(shù)組a中任取一個元素（通常取alow）做為標準元素，以該標準元素調整數(shù)組a中其他各個元素的位置，使排在標準元素前面的元素均小于標準元素，排在標準元素后面的均大于或等于標準元素。這樣一次排序過程結束后，一方面將標準元素放在了未來排好序的數(shù)組中該標準元素應位于的位置上，另一方面將數(shù)組中的元素以標準元素為中心分成了兩個子數(shù)組，位于標準元素左邊子數(shù)組中的元素均小于標準元素，位于標準元素右邊子數(shù)組中的元素均大于等于或標準元素。對這兩個子數(shù)組中的元素分別再進行方法類同的遞歸快速排序。算法的遞歸出口條件是lowhigh。 例、關鍵字序列 T=(60，55，48，37，10，90，84，36），請按從小到大的順序，寫出快速排序的具體實現(xiàn)過程。 快速排序算法各次快速排序過程 3、快速排序算法public static void quickSort(int a, int low, int high)int i, j;int temp;i = low;j = high;temp = alow; /取第一個元素為標準數(shù)據(jù)元素 while(i < j) /在數(shù)組的右端掃描while(i < j && temp <= aj) j-;if(i < j)ai = aj;i+; /在數(shù)組的左端掃描 while(i < j && ai < temp) i+;if(i < j)aj = ai;j-; ai = temp; if(low < i) quickSort(a, low, i-1); /對左端子集合遞歸 if(i < high) quickSort(a, j+1, high); /對右端子集合遞歸4、快速排序算法分析：時間效率：一般情況下時間復雜度為O(nlog2n)，最壞情況是數(shù)據(jù)元素已全部正序或反序有序，此時每次標準元素都把當前數(shù)組分成一個大小比當前數(shù)組小1的子