《數(shù)據(jù)結(jié)構(gòu)(c語(yǔ)言版)》重點(diǎn)知識(shí)

1、v數(shù)據(jù)結(jié)構(gòu)知識(shí)點(diǎn)概括第一章 概 論數(shù)據(jù)就是指能夠被計(jì)算機(jī)識(shí)別、存儲(chǔ)和加工處理的信息的載體。數(shù)據(jù)元素是數(shù)據(jù)的基本單位數(shù)據(jù)項(xiàng)數(shù)據(jù)項(xiàng)是具有獨(dú)立含義的標(biāo)識(shí)單位。數(shù)據(jù)結(jié)構(gòu)的定義：邏輯結(jié)構(gòu)：從邏輯結(jié)構(gòu)上描述數(shù)據(jù)，獨(dú)立于計(jì)算機(jī)。線性結(jié)構(gòu)：一對(duì)一關(guān)系。線性結(jié)構(gòu)：多對(duì)多關(guān)系。存儲(chǔ)結(jié)構(gòu)：是邏輯結(jié)構(gòu)用計(jì)算機(jī)語(yǔ)言的實(shí)現(xiàn)。順序存儲(chǔ)結(jié)構(gòu)：如數(shù)組。鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：如鏈表。稠密索引：每個(gè)結(jié)點(diǎn)都有索引項(xiàng)。稀疏索引：每組結(jié)點(diǎn)都有索引項(xiàng)。散列存儲(chǔ)結(jié)構(gòu)：如散列表。數(shù)據(jù)運(yùn)算。對(duì)數(shù)據(jù)的操作。定義在邏輯結(jié)構(gòu)上，每種邏輯結(jié)構(gòu)都有一個(gè)運(yùn)算集合。常用的有：檢索、插入、刪除、更新、排序。數(shù)據(jù)類型：是一個(gè)值的集合以及在這些值上定義的一組操作的總稱。結(jié)

2、構(gòu)類型：由用戶借助于描述機(jī)制定義，是導(dǎo)出類型。抽象數(shù)據(jù)類型 AD題。優(yōu)點(diǎn)是將數(shù)據(jù)和操作封裝在一起實(shí)現(xiàn)了信息隱藏。數(shù)據(jù)結(jié)構(gòu)。算法是一個(gè)良定義的計(jì)算過程，以一個(gè)或多個(gè)值輸入，并以一個(gè)或多個(gè)值輸出。評(píng)價(jià)算法的好壞的因素：算法是正確的；執(zhí)行算法的時(shí)間；執(zhí)行算法的存儲(chǔ)空間（主要是輔助存儲(chǔ)空間；算法易于理解、編碼、調(diào)試。時(shí)間復(fù)雜度：是某個(gè)算法的時(shí)間耗費(fèi)，它是該算法所求解問題規(guī)模 n 的函數(shù)。漸近時(shí)間復(fù)雜度：是指當(dāng)問題規(guī)模趨向無窮大時(shí)，該算法時(shí)間復(fù)雜度的數(shù)量級(jí)。評(píng)價(jià)一個(gè)算法的時(shí)間性能時(shí)，主要標(biāo)準(zhǔn)就是算法的漸近時(shí)間復(fù)雜度。算法中語(yǔ)句的頻度不僅與問題規(guī)模有關(guān)，還與輸入實(shí)例中各元素的取值相關(guān)。時(shí)間復(fù)雜度按數(shù)量級(jí)遞

3、增排列依次為：常數(shù)階（1log2n、線性階（n（nlog2n（n2O（n3、kO（n（2n?？臻g復(fù)雜度：是某個(gè)算法的空間耗費(fèi)，它是該算法所求解問題規(guī)模 n 的函數(shù)。算法的時(shí)間復(fù)雜度和空間復(fù)雜度合稱算法復(fù)雜度。第二章 線性表線性表是由 n0 個(gè)數(shù)據(jù)元素組成的有限序列。n=0 是空表；非空表，只能有一個(gè)開始結(jié)點(diǎn)，有且只能有一個(gè)終端結(jié)點(diǎn)。線性表上定義的基本運(yùn)算：構(gòu)造空表：Initlist（L）求表長(zhǎng)：Listlength（L）取結(jié)點(diǎn)：GetNode（L，i）查找：LocateNode（L，x）插入：InsertList（L，x，i）刪除：Delete（L，i）順序表是按線性表的邏輯結(jié)構(gòu)次序依次存放在

4、一組地址連續(xù)單元中的各元素的物理位置和邏輯結(jié)構(gòu)中各結(jié)點(diǎn)相鄰關(guān)系是一致的。地址計(jì)算： LOCa（i）=LOCa（1）+（i-1）*d；（首地址為 1）在順序表中實(shí)現(xiàn)的基本運(yùn)算：n/2；平均時(shí)間復(fù)雜度均為（n。刪除：平均移動(dòng)結(jié)點(diǎn)次數(shù)為n-1）/；平均時(shí)間復(fù)雜度均為（n。（即針或鏈。這兩部分信息組成鏈表中的結(jié)點(diǎn)結(jié)構(gòu)。一個(gè)單鏈表由頭指針的名字來命名。單鏈表運(yùn)算：建立單鏈表s-next=head；head=s（n。尾插法：head=rear=null；if（head=null） head=s；else r-next=s；r=s； 平均時(shí)間復(fù)雜度均為 O（n）加頭結(jié)點(diǎn)的算法：對(duì)開始結(jié)點(diǎn)的操作無需特殊處理，

5、統(tǒng)一了空表和非空表。查找（n。（n。p=GetNod（i-1s-next=p-nextp-next=O（n）p=GetNod（Li-1r=p-nexp-next=r-nexfrerO（n）終止條件是以指針等于頭指針或尾指針。（1，不用遍歷整個(gè)鏈表。prior，形成兩條不同方向的鏈。由頭指針 head 惟一確定。雙鏈表也可以頭尾相鏈接構(gòu)成雙（向）循環(huán)鏈表雙鏈表上的插入和刪除時(shí)間復(fù)雜度均為O （1。順序表和鏈表的比較：基于空間：順序表的存儲(chǔ)空間是靜態(tài)分配，存儲(chǔ)密度為 1；適于線性表事先確定其大小時(shí)采用。鏈表的存儲(chǔ)空間是動(dòng)態(tài)分配，存儲(chǔ)密度1；適于線性表長(zhǎng)度變化大時(shí)采用?；跁r(shí)間：順序表是隨機(jī)存儲(chǔ)結(jié)構(gòu)

6、，當(dāng)線性表的操作主要是查找時(shí)，宜采用。以插入和刪除操作為主的線性表宜采用鏈表做存儲(chǔ)結(jié)構(gòu)。若插入和刪除主要發(fā)生在表的首尾兩端，則宜采用尾指針表示的單循環(huán)鏈表。第三章 棧和隊(duì)列棧（Stack）是僅限制在表的一端進(jìn)行插入和刪除運(yùn)算的線性表，稱插入、刪除這LIFO 表（Last In First Out。通常棧有順序棧和鏈棧兩種存儲(chǔ)結(jié)構(gòu)。棧的基本運(yùn)算有六種： 構(gòu)造空棧：InitStack（S）判?？眨?StackEmpty（S）判棧滿： StackFull（S）進(jìn)棧： Push（S，x）退棧： Pop（S）取棧頂元素：StackTop（S）棧頂指針指出棧的外面是出錯(cuò)狀態(tài)?！跋乱纭笨梢员硎緱榭諚＃虼?/p>

7、用來作為控制轉(zhuǎn)移的條件。順序棧中的基本操作有六種構(gòu)造空棧 判?？?判棧滿進(jìn) 棧退棧棧頂元素要有鏈表的頭指針就可以了。構(gòu)造空棧 判棧空 退棧 取棧頂元素 隊(duì)列（Queue）進(jìn)行，允許刪除的一端稱為隊(duì)頭（front，允許插入的一端稱為隊(duì)尾（rear）FIFO 表（First InFirst Out） .隊(duì)列也有順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)兩種存儲(chǔ)結(jié)構(gòu)隊(duì)列的基本運(yùn)算有六種：置空隊(duì)：InitQueue（Q）判隊(duì)空：QueueEmpty（Q）判隊(duì)滿：QueueFull（Q）入隊(duì)：EnQueue（Q，x）出隊(duì)：DeQueue（Q）取隊(duì)頭元素：QueueFront（Q）順序隊(duì)列的“假上溢”現(xiàn)象：由于頭尾指針不斷前移，

8、超出向量空間。這時(shí)整個(gè)向量空間及隊(duì)列是空的卻產(chǎn)生了“上溢”現(xiàn)象。形，這時(shí)隊(duì)列稱循環(huán)隊(duì)列。判定循環(huán)隊(duì)列是空還是滿，方法有三種：一種是另設(shè)一個(gè)布爾變量來判斷；第二種是少用一個(gè)元素空間，入隊(duì)時(shí)先測(cè)試（rear+）%m = front）？ 滿：空；第三種就是用一個(gè)計(jì)數(shù)器記錄隊(duì)列中的元素的總數(shù)。表尾進(jìn)行插入（入隊(duì)）的鏈隊(duì)列不存在隊(duì)滿和上溢頭尾指針并使隊(duì)列變空。第四章 串串是零個(gè)或多個(gè)字符組成的有限序列?？沾菏侵搁L(zhǎng)度為零的串，也就是串中不包含任何字符（結(jié)點(diǎn)。空白串：指串中包含一個(gè)或多個(gè)空格字符的串。主串。子串在主串中的序號(hào)就是指子串在主串中首次出現(xiàn)的位置。空串是任意串的子串，任意串是自身的子串。串分為兩

9、種： 串常量在程序中只能引用不能改變；串變量的值可以改變。串的基本運(yùn)算有： 求串長(zhǎng) strlen（char*s）串復(fù)制 strcpy（char*to，char*from）串聯(lián)接 strcat（char*to，char*from）串比較 charcmp（char*s1，char*s2）字符定位 strchr（char*s，charc）串是特殊的線性表（結(jié)點(diǎn)是字符的順序存儲(chǔ)結(jié)構(gòu)簡(jiǎn)稱為順序串。順序串又可按存儲(chǔ)分配的不同分為：靜態(tài)存儲(chǔ)分配：直接用定長(zhǎng)的字符數(shù)組來定義。優(yōu)點(diǎn)是涉及串長(zhǎng)的操作速度 快， 但不適合插入、鏈接操作。儲(chǔ)單元。串的鏈?zhǔn)酱鎯?chǔ)就是用單鏈表的方式串與單鏈表的差異只是它的 結(jié)點(diǎn)數(shù)據(jù)域?yàn)閱蝹€(gè)

10、字符。為了解決“存儲(chǔ)密度”低的狀況，可以讓一個(gè)結(jié)點(diǎn)存儲(chǔ)多個(gè)字符，即結(jié)點(diǎn)的大小。，子串稱為模式（串P T 中首次出現(xiàn)的有效（ n-m+）m n同階（n2。鏈串上的子串定位運(yùn)算位移是結(jié)點(diǎn)地址而不是整數(shù)第五章 多維數(shù)組數(shù)組一般用順序存儲(chǔ)的方式表示。存儲(chǔ)的方式有： 行優(yōu)先順序，也就是把數(shù)組逐行依次排列。PASCAL、C列優(yōu)先順序，就是把數(shù)組逐列依次排列。FORTRANi-1）*n+（j-1） *d.j-1）*n+（i-1） *d.矩陣的壓縮存儲(chǔ)：為多個(gè)相同的非零元素分配一個(gè)存儲(chǔ)空間；對(duì)零元素不分配空間。特殊矩陣的概念：所謂特殊矩陣是指非零元素或零元素分布有一定規(guī)律的矩陣。陣稱為稀疏矩陣。（ij=（ji

11、n+1/2.I=max（i，j，J=mi（i，j，LOCa（ij）=LO（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.對(duì)角矩陣：k=2i+j，LOCa（ij）=LOC（sa0）+k*d.稀疏矩陣的壓縮存儲(chǔ)方式用三元組表把非零元素的值和它所在的行號(hào)列號(hào)做為一隨機(jī)存儲(chǔ)功能。加入行表記錄每行的非零元素在三元組表中的起始位置，即帶行表的三元組表。第六章 樹n m 個(gè)不相交的子集，并稱根的子樹。0 的結(jié)點(diǎn)稱葉子（終端結(jié)點(diǎn)0的結(jié)

12、點(diǎn)稱分支結(jié)點(diǎn)（非終端結(jié)點(diǎn)；除根外的分支結(jié)點(diǎn)稱內(nèi)部結(jié)點(diǎn)；m 互不相交的樹的集合；凹入表示法表示法。二叉樹的定義：是n0 個(gè)結(jié)點(diǎn)的有限集，它是空集（n=0）或由一個(gè)根結(jié)點(diǎn)及兩棵互不相交的分別稱作這個(gè)根的左子樹和右子樹的二叉樹組成。二叉樹不是樹的特殊情形，與度數(shù)為 2 的有序樹不同。4 i 2（i-1（i1k的二叉樹至多有（2）-1 個(gè)結(jié)點(diǎn)（1；n02的結(jié)點(diǎn)數(shù)為n2n0=n2+1；具有 n 個(gè)結(jié)點(diǎn)的完全二叉樹的深度為int（log2n）+1.滿二叉樹是一棵深度為 k，結(jié)點(diǎn)數(shù)為（2k）-1 的二叉樹；完全二叉樹是滿二叉樹在最下層自右向左去處部分結(jié)點(diǎn)；二叉樹的順序存儲(chǔ)結(jié)構(gòu)就是把二叉樹的所有結(jié)點(diǎn)按照層次順

13、序存儲(chǔ)到連續(xù)的存儲(chǔ)單元中。（存儲(chǔ)前先將其畫成完全二叉樹）樹的存儲(chǔ)結(jié)構(gòu)多用的是鏈?zhǔn)酱鎯?chǔ)。 BinTNode 的結(jié)構(gòu)為 lchild|data|rchild，把所有BinTNode 類型的結(jié)點(diǎn)，加上一個(gè)指向根結(jié)點(diǎn)的 BinTree 型頭指針就構(gòu)成了二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，稱為二叉鏈表。它就是由根指針 root 唯一確定的。共有 2n 個(gè)指針域，n+1 個(gè)空指針。根據(jù)訪問結(jié)點(diǎn)的次序不同可得三種遍歷：先序遍歷（前序遍歷或先根遍歷，中序遍歷（或中根遍歷、后序遍歷（或后根遍歷（n。利用二叉鏈表中的 n+1 點(diǎn)的前序前趨和后序后繼并沒有什么作用。樹和森林及二叉樹的轉(zhuǎn)換是唯一對(duì)應(yīng)的。轉(zhuǎn)換方法： 樹變二叉樹：兄弟

14、相連，保留長(zhǎng)子的連線。二叉樹變樹：結(jié)點(diǎn)的右孩子與其雙親連。森林變二叉樹：樹變二叉樹，各個(gè)樹的根相連。data | paren十分方便，但不適于求指定結(jié)點(diǎn)的孩子及后代。data | next data| firstchild 存放在一個(gè)向量中。雙親孩子鏈表表示法：將雙親鏈表和孩子鏈表結(jié)合。孩子兄弟鏈表表示法：結(jié)點(diǎn)結(jié)構(gòu)leftmostchild |data | rightsibing，附加兩個(gè)分別指向該結(jié)點(diǎn)的最左孩子和右鄰兄弟的指針域。樹的前序遍歷與相對(duì)應(yīng)的二叉樹的前序遍歷一致；樹的后序遍歷與相對(duì)應(yīng)的二叉樹的中序遍歷一致。的二叉樹就稱為最優(yōu)二叉樹（即哈夫曼樹。在葉子的權(quán)值相同的二叉樹中，完全二叉樹

15、的路徑長(zhǎng)度最短。n 2n-1 1 格二叉樹。00、01、0001 要求在字符編碼時(shí)任一字符的編碼都不是其他字符編碼的前綴，這種碼稱為前綴碼（其實(shí)是非前綴碼。01，然后從上到下到葉結(jié)點(diǎn)的相應(yīng)路徑上的代碼的序列就是該結(jié)點(diǎn)的最優(yōu)前綴碼。第七章 圖（頂點(diǎn)個(gè)結(jié)點(diǎn)之間之間都可能相關(guān)。GraphG（V，E，V E DigraphUndigraph：每條邊沒有方向。有向完全圖：具有 n*（n-1）條邊的有向圖；無向完全圖：具有 n*（n-1）/2 條邊的無向圖；簡(jiǎn)單回路是開始和終端重的簡(jiǎn)單路徑；網(wǎng)絡(luò)：是帶權(quán)的圖。圖的存儲(chǔ)結(jié)構(gòu)：鄰接矩陣表示法：用一個(gè) n 階方陣來表示圖的結(jié)構(gòu)是唯一的，適合稠密圖。無向圖：鄰接矩

16、陣是對(duì)稱的。有向圖：行是出度，列是入度。（n+n2+e（n2）鄰接表表示法：用頂點(diǎn)表和鄰接表構(gòu)成不是唯一的，適合稀疏圖。頂點(diǎn)表結(jié)構(gòu) vertex | firstedge，指針域存放鄰接表頭指針。鄰接表：用頭指針確定。 無向圖稱邊表；有向圖又分出邊表和逆鄰接表；鄰接表結(jié)點(diǎn)結(jié)構(gòu)為 adjvex | next，（n+（n+e。圖的遍歷： 深度優(yōu)先遍歷：借助于鄰接矩陣的列。使用棧保存已訪問結(jié)點(diǎn)。廣度優(yōu)先遍歷：借助于鄰接矩陣的行。使用隊(duì)列保存已訪問結(jié)點(diǎn)。時(shí)經(jīng)過的邊和圖的所有頂點(diǎn)構(gòu)成的子圖稱作該圖的生成樹。最小的生成樹稱為最小生成樹（MST。構(gòu)造最小生成樹的算法： Prim O（n2）稠密圖。Kruska

17、l（lg，主要取決于邊數(shù)，較適合于稀疏圖。Dijkstra （n2prim拓?fù)渑判颍菏菍⒂邢驘o環(huán)圖G （u v 之前，這種線性序列稱為拓?fù)湫蛄?。拓?fù)渑判蛞灿袃煞N方法：序列即拓?fù)湫蛄?。到的序列是逆拓?fù)湫蛄小５诎苏?排序記錄中可用某一項(xiàng)來標(biāo)識(shí)一個(gè)記錄，則稱為關(guān)鍵字項(xiàng)，該數(shù)據(jù)項(xiàng)的值稱為關(guān)鍵字。排序是使文件中的記錄按關(guān)鍵字遞增（或遞減）次序排列起來。基本操作：比較關(guān)鍵字大??；改變指向記錄的指針或移動(dòng)記錄。存儲(chǔ)結(jié)構(gòu)：順序結(jié)構(gòu)、鏈表結(jié)構(gòu)、索引結(jié)構(gòu)。法是穩(wěn)定的，否則排序算法是不穩(wěn)定的。排序過程中不涉及數(shù)據(jù)的內(nèi)、外存交換則稱之為“內(nèi)部排序（內(nèi)排序存在數(shù)據(jù)的內(nèi)外存交換，則稱之為外排序。內(nèi)部排序方法可分五類：插入

18、排序、選擇排序、交換排序、歸并排序和分配排序。評(píng)價(jià)排序算法好壞的標(biāo)準(zhǔn)主要有兩條：執(zhí)行時(shí)間和所需的輔助空間，另外算法的復(fù)雜程序也是要考慮的一個(gè)因素。直接插入排序： 逐個(gè)向前插入到合適位置。哨兵（監(jiān)視哨）有兩個(gè)作用： 作為臨變量存放 Ri是在查找循環(huán)中用來監(jiān)視下標(biāo)變量 j 是否越界。直接插入排序是就地的穩(wěn)定排序。時(shí)間復(fù)雜度為 O（n2，比較次數(shù)為（n+2）（n-1）/；移動(dòng)次數(shù)為（n+4（n-1）/；希爾排序： 等間隔的數(shù)據(jù)比較并按要求順序排列，最后間隔為 1.（n1.255移動(dòng)次數(shù)為（1.6n1.25；下向上確定最輕的一個(gè)，后自上向下確定最重的一個(gè)。（n223n（n-1）/2；換位置，直到指針重

19、合。重復(fù)直到排序完成。（nlog2n（n-1）/2；直接選擇排序： 選擇最小的放在比較區(qū)前。（nn（n-1）/2；堆排序 建堆：按層次將數(shù)據(jù)填入完全二叉樹，從 int（n/2）處向前逐個(gè)調(diào)整位置。然后將樹根與最后一個(gè)葉子交換值并斷開與樹的連接并重建堆，直到全斷開。堆排序是就地不穩(wěn)定的排序，時(shí)間復(fù)雜度為 （nlog2n的文件。先兩個(gè)一組排序，形成組為止。（nlog2n，接所有非空箱。（n。從低位到高位依次對(duì)關(guān)鍵字進(jìn)行箱排序。（d*n+d*r。各種排序方法的比較和選擇： 待排序的記錄數(shù)目 n；n 較大的要用時(shí)間復(fù)雜度為O（nlog2n）的排序方法；記錄的大?。ㄒ?guī)模鏈表上難于實(shí)現(xiàn)；關(guān)鍵字的結(jié)構(gòu)及其初

20、始狀態(tài)；對(duì)穩(wěn)定性的要求；語(yǔ)言工具的條件；存儲(chǔ)結(jié)構(gòu)；時(shí)間和輔助空間復(fù)雜度。一般形式為hi（ke+di%mim-放定址法要求散列表的裝填因子1.開放定址法類型： 線性探查法：address=（hash（x）+i）%m；二次探查法：address=（hash（x）+i2）%m；雙重散列法：address=（hash（x）+i*hash（y） %m；拉鏈法： 是將所有關(guān)鍵字為同義詞的結(jié)點(diǎn)鏈接在同一個(gè)單鏈表第九章 查找（如插入或刪除稱之為靜態(tài)查找表。衡量查找算法效率優(yōu)劣的標(biāo)準(zhǔn)是在查找過程中對(duì)關(guān)鍵字需要執(zhí)行的平均比較次數(shù)（AS。中?？臻g；拉鏈法的優(yōu)點(diǎn)： 拉鏈法處理沖突簡(jiǎn)單，且無堆積現(xiàn)象；鏈表上的結(jié)點(diǎn)空間是

21、動(dòng)態(tài)申請(qǐng)的適于無法確定表長(zhǎng)的情況；拉鏈法中可以大于 1，結(jié)點(diǎn)較大時(shí)其指針域可忽略，因此節(jié)省線性表查找的方法： 順序查找：逐個(gè)查找，ASL=（n+1）/2；int（n/2）定樹表示。ASL（每層結(jié)點(diǎn)數(shù)層數(shù)）/N.的最大關(guān)鍵字及其位置建立有序索引表。它的左子樹非空，則左子樹上所有結(jié)點(diǎn)的值均小于根結(jié)點(diǎn)的值；若它的右子樹非空，則右子樹上所有結(jié)點(diǎn)的值均大于根結(jié)點(diǎn)的值；左、右子樹本身又是一棵二叉排序樹。（nlog2n。二叉排序樹的刪除操作可分三種情況進(jìn)行處理： *P 是葉子，則直接刪除*P，即將*P 的雙親*parent 中指向*P 的指針域置空即可。*P 只有一個(gè)孩子*child，此時(shí)只需將*child

22、 和*p 的雙親直接連接就可刪去*p.*p 結(jié)點(diǎn)的中序后繼結(jié)點(diǎn)的數(shù)據(jù)到B-樹（多路平衡查找樹。它適合在磁盤等直接存取設(shè)備上組織動(dòng)態(tài)的查找表，是一種外查找算法。建立的方式是從下向上拱起。選擇有兩條標(biāo)準(zhǔn)：簡(jiǎn)單和均勻。常見的散列函數(shù)構(gòu)的造方法：平方取中法：hash=int（ x2）%100）除余法：表長(zhǎng)為 m，hash=x%m相乘取整法：hash=int（m*（x*A-int（x*A）；A=0.618hash=rando（x。拉鏈法構(gòu)造的散列表刪除結(jié)點(diǎn)易實(shí)現(xiàn)。拉鏈法也有缺點(diǎn)：當(dāng)結(jié)點(diǎn)規(guī)模較小時(shí)，用拉鏈法中的指針域也要占用額外空間， 還是開放定址法省空間。第十章 排序排序的基本概念插入排序選擇排序交換排

23、序 復(fù)雜度和穩(wěn)定性直接選擇排序，堆排序 冒泡排序，快速排序10.1 排序的基本概念排序是對(duì)數(shù)據(jù)元素序列建立某種有序排列的過程。排序的目的：便于查找。關(guān)鍵字是要排序的數(shù)據(jù)元素集合中的一個(gè)域，排序是以關(guān)鍵字為基準(zhǔn)進(jìn)行的。關(guān)鍵字分主關(guān)鍵字和次關(guān)鍵字兩種。對(duì)要排序的數(shù)據(jù)元素集合來說，如果關(guān)鍵足主關(guān)鍵字定義的關(guān)鍵字稱為次關(guān)鍵字。排序的種類：分為內(nèi)部排序和外部排序兩大類。若待排序記錄都在內(nèi)存中，稱為內(nèi)部排序；若待排序記錄一部分在內(nèi)存，一部分在外存，則稱為外部排序。注：外部排序時(shí)，要將數(shù)據(jù)分批調(diào)入內(nèi)存來排序，中間結(jié)果還要及時(shí)放入外存，顯然外部排序要復(fù)雜得多。temp = ai + 1; j = i;whil

24、e(j -1 & temp aj)5.排序算法好壞的衡量標(biāo)準(zhǔn)：aj + 1 = aj;(1)時(shí)間復(fù)雜度 它主要是分析記錄關(guān)鍵字的比較次數(shù)和記錄的移動(dòng)次數(shù)。j -;(2)空間復(fù)雜度算法中使用的內(nèi)存輔助空間的多少。(3)穩(wěn)定性若兩個(gè)記錄 A 和 B 的關(guān)鍵字值相等，但排序后 A、B 的先后次序保持不aj + 1 = temp;變，則稱這種排序算法是穩(wěn)定的。10.2 插入排序已經(jīng)排好序的一組對(duì)象的適當(dāng)位置上，直到對(duì)象全部插入為止。簡(jiǎn)言之，邊插入邊排序，保證子序列中隨時(shí)都是排好序的。常用的插入排序有：直接插入排序和希爾排序兩種。10.2.1 直接插入排序1、其基本思想是：順序地把待排序的數(shù)據(jù)元素按其關(guān)

25、鍵字值的大小插入到已排序數(shù)據(jù)元素子集合的適當(dāng)位置。133195請(qǐng)寫出直接插入排序的中間過程序列。初始關(guān)鍵字序列：【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，1

26、3，27, 31】注：方括號(hào) 中為已排序記錄的關(guān)鍵字，下劃?rùn)M線的 關(guān)鍵表示它對(duì)應(yīng)的記錄后移一個(gè)位置。直接插入排序算法public static void insertSort(int int i, j, temp;int n = a.Length;for(i = 0; i n - 1; i +)初始關(guān)鍵字序列：【13】, 6, 3, 31, 9, 27, 5, 11第一次排序：【6,13】,3, 31,9, 27,5, 11第二次排序：【3, 6, 13】, 31, 9, 27, 5, 113、直接插入排序算法分析時(shí)間效率：當(dāng)數(shù)據(jù)有序時(shí)，執(zhí)行效率最好，此時(shí)的時(shí)間復(fù)雜度為 O(n)；當(dāng)數(shù)據(jù)基本反

27、序時(shí)，執(zhí)行效率最差，此時(shí)的時(shí)間復(fù)雜度為O(n2)入排序算法的性能越好。1 O（1）算法的穩(wěn)定性：穩(wěn)定8.2.2 希爾（shell）排序 （又稱縮小增量排序）1、基本思想：把整個(gè)待排序的數(shù)據(jù)元素分成若干個(gè)小組，對(duì)同一小組內(nèi)的數(shù)據(jù)元素用直接插入法排序小組的個(gè)數(shù)逐次縮小當(dāng)完成了所有數(shù)據(jù)元素都在一個(gè)組內(nèi)的排序排序過程結(jié)束。2、技巧：小組的構(gòu)成不是簡(jiǎn)單地“逐段分割”，而是將相隔某個(gè)增量d 的記錄組成一個(gè)小,讓增量d 逐趟縮（例如依次取5,3,1直 d1 為止。3、優(yōu)點(diǎn)：讓關(guān)鍵字值小的元素能很快前移，且序列若基本有序時(shí)，再用直接插入排序處理，時(shí)間效率會(huì)高很多。212 T=(65，34，25，87，12，

28、38，56，46，14，77，92，23，請(qǐng)寫出希爾排序的具體實(shí)現(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次循span = dm;/取本次的增量值for(k = 0; k span; k +)/span 個(gè)小組for(i = k; i -1 & temp aj)1、其基本思想aj + span = aj;每經(jīng)過一趟比較就找出一個(gè)最小值，與待排序列最前面的位置互

29、換即可。j = j - span;（即從待排序的數(shù)據(jù)元素集合中選取關(guān)鍵字最小的數(shù)據(jù)元素并將它與原始數(shù)據(jù)元素集aj + span = temp;到數(shù)據(jù)元素集合中只剩一個(gè)數(shù)據(jù)元素為止。）2、優(yōu)缺點(diǎn)優(yōu)點(diǎn)：實(shí)現(xiàn)簡(jiǎn)單算法分析：開始時(shí)d d 時(shí)間效率：O(n(log2n)2)空間效率：O（1）因?yàn)閮H占用 1 個(gè)緩沖單元算法的穩(wěn)定性：不穩(wěn)定練習(xí)：欲將序列 H, C, P, A, M, S, R, D, F, 中的關(guān)鍵碼按字母升序重排，則初始d為 4 的希爾排序一趟的結(jié)果是？答： 原始序列：Q, H, C, P, A, M, S, R, D, F, Xshell 一趟后： P,A,C,S,Q,D,F,X,R,

30、H,M,Y2. 以關(guān)鍵字序列（256，301，751，129，937，863，742，694，076，438）為例，寫出執(zhí)行希爾排序（取 d=5,3,1）算法的各趟排序結(jié)束時(shí)，關(guān)鍵字序列的狀態(tài)。解：原始序列: 256，301，751，129，937，863，742，694，076，438希爾排序第一趟d=5256301694076438863742751129937第二趟d=3076301129256438694742751863937第三趟d=1076129256301438694742751863937選擇排序（或最大的數(shù)據(jù)元素放到數(shù)據(jù)元素集合的最前（或最后，數(shù)據(jù)元素集合不斷縮小，當(dāng)數(shù)據(jù)元

31、素集合為空時(shí)選擇排序結(jié)束。缺點(diǎn)：每趟只能確定一個(gè)元素，表長(zhǎng)為 n 時(shí)需要n-1 趟3：關(guān)鍵字序列T=（21249251608過程。原始序列：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，49 public static void selectSort(int a)int i, j, small; int temp;int n = a.Length;for(i = 0; i n -

32、1; i +)small = i;/i 個(gè)數(shù)據(jù)元素最小for(j = i + 1; j n; j +)/尋找最小的數(shù)據(jù)元素if(aj asmall) small = j;/記住最小元素的下if(small != i)/當(dāng)最小元素的下標(biāo)不為i 時(shí)交換位置temp = ai; ai = asmall;asmall = temp;n k0，k1，kn-1，當(dāng)且僅當(dāng)滿足下述關(guān)系之一時(shí)，稱之為堆。3、算法分析時(shí)間效率： O(n2)空間效率：O（1）沒有附加單元（1 temp) 算法的穩(wěn)定性：不穩(wěn)定4、穩(wěn)定的直接選擇排序算法例：關(guān)鍵字序列T=（21249251608實(shí)現(xiàn)過程。原始序列： 21，25，49，

33、25*，16，08第1 趟08,21 ,25 ,49 ,25 *, 16解釋：如果讓滿足以上條件的元素序列 （k，k，kn）順次排成一棵完全二叉樹，則此樹的特點(diǎn)是：樹中所有結(jié)點(diǎn)的值均大于（或小于）其左右孩子，此樹的根結(jié)點(diǎn)（即堆頂）必最大（或最小。4T1=（08, 25, 49, 46, 58, 67 ）T2=（91, 85, 76, 66, 58, 67, 55 ）,判斷它們是否 “堆”？怎樣建堆？步驟：從第一個(gè)非終端結(jié)點(diǎn)開始往前逐步調(diào)整，讓每個(gè)雙親大于（或小于）子女，直到根結(jié)點(diǎn)為止。第 2 趟 08，16,21，25，49，25 *終端結(jié)點(diǎn)（即葉子）沒有任何子女，無需單獨(dú)調(diào)整第 3 趟 08

34、，16,21，25，49，25 *T= (21，2549，25，16，08，請(qǐng)建最大堆。第 4 趟 08，16,21，25，49，25 *解：為便于理解，先將原始序列畫成完全二叉樹的形式：第 5 趟 08，16,21，25，25* ，49這樣可以很清晰地從(n-1-1)/2 開始調(diào)整。public static void selectSort2(int a) int i,j,small;int temp;int n = a.Length;for(i = 0; i n-1; small = i;for(j = i+1; j n; j+)/尋找最小的數(shù)據(jù)元素if(aj i; j-)/把該區(qū)段尚未排

35、序元素依次后移aj = aj-1;ai = temp;/插入找出的最小元素8.3.2 堆排序1. 什么是堆？ 2. 怎樣建堆？3. 怎樣堆排序？public static void createHeap(int a, int n, int h) int i, j, flag;int temp; i = h;j = 2 * i + 1;/ j 為i 結(jié)點(diǎn)的左孩子結(jié)點(diǎn)的下標(biāo)temp = ai; flag = 0;while(j n & flag != 1)/尋找左右孩子結(jié)點(diǎn)中的較大者,j 為其下標(biāo)if(j n - 1 & aj = aj)flag = 1;/標(biāo)記結(jié)束篩選條件else/aj上移ai

36、= aj; i = j;j = 2 * i + 1;ai = temp;利用上述 createHeap（a,n,h）函數(shù)，初始化創(chuàng)建最大堆的過程就是從第一個(gè)非練習(xí)1：以下序列是堆的是（）75,65,30,15,25,45,20,10B. 75,65,45,10,30,25,20,15aia0createHeap（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. 怎樣進(jìn)行整個(gè)

37、序列的堆排序？*基于初始堆進(jìn)行堆排序的算法步驟：a0a0an-1的對(duì)象交換到最后;n-1 個(gè)對(duì)象，使用堆的調(diào)整算法，重新建立堆（最大堆的定義a0;a0an-2，然后對(duì)前n-2 排序好的對(duì)象序列。例 5：對(duì)剛才建好的最大堆進(jìn)行排序： public static void heapSort(int a)int temp;int n = a.Length;initCreateHeap(a);/初始化創(chuàng)建最大堆for(int i = n - 1; i 0; i -)/當(dāng)前最大堆個(gè)數(shù)每次遞減/把堆頂 a0元素和當(dāng)前最大堆的最后一個(gè)元素交換temp = a0;a0 = ai; ai = temp;crea

38、teHeap(a,i, 0);/調(diào)整根結(jié)點(diǎn)滿足最大堆4、堆排序算法分析： 時(shí)間效率：O(nlog2n)?？臻g效率：O(1)。穩(wěn)定性： 不穩(wěn)定。C. 75,45,65,30,15,25,20,10D. 75,45,65,10,25,30,20,15練習(xí)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*,9D.以上都不對(duì)3503，87，512，61，908，170，897，275，653，462，寫出采用堆排序?qū)υ撔蛄凶鞣沁f減排列時(shí)的排序過程。排序好的序列為：61

39、，87，170，275，462，503，512，653，897，908交換排序交換排序的基本思想是：利用交換數(shù)據(jù)元素的位置進(jìn)行排序的方法。交換排序的主要算法有：冒泡排序快速排序10.4.1 冒泡排序1、基本思路：每趟不斷將記錄兩兩比較，并按“前小后大”（或“前大后小”）規(guī)則交換。2、優(yōu)點(diǎn)：每趟結(jié)束時(shí)，不僅能擠出一個(gè)最大值到最后面位置，還能同時(shí)部分理順其他元素；一旦下趟沒有交換發(fā)生，還可以提前結(jié)束排序。T=(22549251608的具體實(shí)現(xiàn)過程。初態(tài)：21，25，49， 25*，16， 081 21，25，25*，1608 ， 49 2 21，251608 ，25*，49 3 21，1608 ，

40、2525*，49 4 16，08 ，212525*，49 5 08，16212525*，49 3、冒泡排序算法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 aj+1)flag = 1; temp = aj; aj = aj+1;int i = low; j = high;temp = alow;/取第一個(gè)元素為標(biāo)準(zhǔn)數(shù)據(jù)元素aj+1 = temp;while(i j)/在數(shù)組的右

41、端掃描while(i j & temp = aj) j-;if(i j)4、冒泡排序的算法分析（n2) 因?yàn)橐紤]最壞情況（數(shù)據(jù)元素全部逆序n-1 O（n)空間效率：O（1） 只在交換時(shí)用到一個(gè)緩沖單元ai = aj; i+;/在數(shù)組的左端掃描while(i j & ai temp) i+;穩(wěn) 定 性： 穩(wěn)定 25 和 25*在排序前后的次序未改變T=(3159251628的具體實(shí)現(xiàn)過程。初態(tài)：31，15，9， 25，16， 281 15，9，25，16282 9，15， 16， 3 9，1516，2528，311、基本思想：設(shè)數(shù)組 a 中存放了 n 個(gè)數(shù)據(jù)元素，low 為數(shù)組的低端下標(biāo)，hi

42、gh 為數(shù)組的高端下標(biāo)，從數(shù)組a中任取一個(gè)元素（通常取alow）做為標(biāo)準(zhǔn)元素，以該標(biāo)準(zhǔn)元素if(i j)aj = j-;ai = temp;if(low i) quickSort(a, low, i-1);/對(duì)左端子集合遞歸if(i high) quickSort(a, j+1, high);/對(duì)右端子集合遞歸a lowhigh。例、關(guān)鍵字序列 T=(6，55，48，37，10，9084，36快速排序的具體實(shí)現(xiàn)過程?？焖倥判蛩惴ǜ鞔慰焖倥判蜻^程3、快速排序算法public static void quickSort(int a, int low, int high) int i, j;4、快速排序算法分析：O(nlog2n)1 O(n2)空間效率：O（log2n）因?yàn)檫f歸要用棧穩(wěn) 定 性： 不 穩(wěn) 定 因?yàn)橛刑S式交換。練習(xí)：已知序列503,87,512,61,908,170,897,275,653,462，給出采用快速排序?qū)υ撔蛄凶鞣沁f減排序時(shí)每趟的結(jié)果。第一趟【4628727561170 】 503【897908653512】第二趟【1708727561 】 462503512653】 897908】第三趟【6187】 170【275】462503512 【653】897908第四趟：61 【87】1702754625035126