數(shù)據(jù)結(jié)構(gòu)課程總結(jié).

1、數(shù)據(jù):能夠被計(jì)算機(jī)識(shí)別、存儲(chǔ)和加工處理的信息的載體。數(shù)據(jù)元素:數(shù)據(jù)的基本單位 ,可以由若干個(gè)數(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) :如鏈表。索引結(jié)構(gòu) :索引表。散列存儲(chǔ)結(jié)構(gòu):如散列表。對(duì)數(shù)據(jù)的操作 :定義在邏輯結(jié)構(gòu)上 ,每種邏輯結(jié)構(gòu)都有一個(gè)運(yùn)算集合。常用的 有:檢索、插入、刪除、更新、排序。數(shù)據(jù)類型 :是一個(gè)值的集合以及在這些值上定義的一組操作的總稱。原子類型 簡(jiǎn)單類型 ,由語(yǔ)言提供。

2、結(jié)構(gòu)類型 :由用戶借助于描述機(jī)制定義 ,是導(dǎo)出類型。程序設(shè)計(jì)的實(shí)質(zhì)是對(duì)實(shí)際問(wèn)題選擇一種好的數(shù)據(jù)結(jié)構(gòu) ,設(shè)計(jì)一個(gè)好的算法。算 法取決于數(shù)據(jù)結(jié)構(gòu)。算法是一個(gè)自定義的計(jì)算過(guò)程 ,以一個(gè)或多個(gè)值輸入 ,并以一個(gè)或多個(gè)值輸 出。評(píng)價(jià)算法的好壞的因素 :算法是正確的 ;執(zhí)行算法的時(shí)間 ;執(zhí)行算法的存儲(chǔ)空間 算法易于理解、編碼、調(diào)試。時(shí)間復(fù)雜度 :是某個(gè)算法的時(shí)間耗費(fèi) ,它是該算法所求解問(wèn)題規(guī)模 n 的函數(shù)。漸近時(shí)間復(fù)雜度 :是指當(dāng)問(wèn)題規(guī)模趨向無(wú)窮大時(shí)該算法時(shí)間復(fù)雜度的數(shù)量級(jí)。評(píng)價(jià)一個(gè)算法的時(shí)間性能時(shí) ,主要標(biāo)準(zhǔn)就是算法 的漸近時(shí)間復(fù)雜度。算法中語(yǔ)句的頻度不僅與問(wèn)題規(guī)模有關(guān) ,還與輸入實(shí)例中各元素的取值相關(guān)

3、。時(shí)間復(fù)雜度按數(shù)量級(jí)遞增排列依次為 :常數(shù)階、對(duì)數(shù)階、線性階、線性對(duì)數(shù) 階、平方階、立方階、 k次方階、指數(shù)階?？臻g復(fù)雜度 :是某個(gè)算法的空間耗費(fèi) ,它是該算法所求解問(wèn)題規(guī)模 n 的函數(shù)。算法的時(shí)間復(fù)雜度和空間復(fù)雜度合稱算法復(fù)雜度。線性表是由 n0個(gè)數(shù)據(jù)元素組成的有限序列。 n=0是空表 ;非空表,只能有一個(gè) 開(kāi)始結(jié)點(diǎn) ,有且只能有一個(gè)終端結(jié)點(diǎn)。線性表上定義的基本運(yùn)算 :構(gòu)造空表 :Initlist; 求表長(zhǎng) :Listlength;取結(jié)點(diǎn) :GetNode; 查找 :LocateNode;插入:InsertList;刪除:Delete。順序表是按線性表的邏輯結(jié)構(gòu)次序依次存放在一組地址連續(xù)的存

4、儲(chǔ)單元中。 在存儲(chǔ)單元中的各元素的物理位置和邏輯結(jié)構(gòu)中各結(jié)點(diǎn)相鄰關(guān)系是一致的。地址計(jì)算 :?在順序表中實(shí)現(xiàn)的基本運(yùn)算 :插入 :平均移動(dòng)結(jié)點(diǎn)次數(shù)為 ?;平均時(shí)間復(fù)雜度均 為?。刪除 :平均移動(dòng)結(jié)點(diǎn)次數(shù)為 ?;平均時(shí)間復(fù)雜度均為?。線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中結(jié)點(diǎn)的邏輯次序和物理次序不一定相同 ,為了能正確 表示結(jié)點(diǎn)間的邏輯關(guān)系 ,在存儲(chǔ)每個(gè)結(jié)點(diǎn)值的同時(shí) ,還存儲(chǔ)了其后繼結(jié)點(diǎn)的地址信息。這兩部分信息組成鏈表中的結(jié)點(diǎn)結(jié)構(gòu)。一個(gè) 單鏈表由頭指針的名字來(lái)命名。單鏈表運(yùn)算 : 建立單鏈表 ( 頭插法 :生成的順序與輸入順序相反。平均時(shí)間復(fù)雜 度均為?。尾插法 :平均時(shí)間復(fù)雜度均為 ?。加頭結(jié)點(diǎn)的算法 :對(duì)開(kāi)始

5、結(jié)點(diǎn)的操作無(wú)需特殊處理 ,統(tǒng)一了空表和非空表。查找 (按 序號(hào) :與查找位置有關(guān) ,平均時(shí)間復(fù)雜度均為 ?。按值 :與輸入實(shí)例有關(guān) ,平均時(shí)間復(fù)雜度均為。插入運(yùn)算 :p=GetNode;s-next=p- next;p-next=s;平均時(shí)間復(fù)雜度均為 ?,刪除運(yùn)算 :平均時(shí)間復(fù)雜度均為 ?單循環(huán)鏈表是一種首尾相接的單鏈表 ,終端結(jié)點(diǎn)的指針域指向開(kāi)始結(jié)點(diǎn)或頭結(jié) 點(diǎn)。鏈表終止條件是以指針等于頭指針或尾指針。采用單循環(huán)鏈表在實(shí)用中多采用尾指針表示單循環(huán)鏈表。優(yōu)點(diǎn)是查找頭指針和 尾指針的時(shí)間都是 O?,不用遍歷整個(gè)鏈表。雙鏈表就是雙向鏈表 ,就是在單鏈表的每個(gè)結(jié)點(diǎn)里再增加一個(gè)指向其直接前趨 的指針域

6、 prior,形成兩條不同方向的鏈。由頭指針head惟一確定。雙鏈表也可以頭尾相構(gòu)成雙循環(huán)鏈表。雙鏈表上的插入和刪 除時(shí)間復(fù)雜度均為 O?。順序表和鏈表的比較 :基于空間 :順序表的存儲(chǔ)空間是靜態(tài)分配 ,存儲(chǔ)密度為 1;適于線性表事先確定 其大小時(shí)采用。鏈表的存儲(chǔ)空間是動(dòng)態(tài)分配 ,存儲(chǔ)密度 1;適于線性表長(zhǎng)度變化大時(shí)采用?；跁r(shí)間 :順序表是隨機(jī)存儲(chǔ)結(jié)構(gòu) ,當(dāng)線性表的操作主要是查找時(shí) ,宜采用。以 插入和刪除操作為主的線性表宜采用鏈表做存儲(chǔ)結(jié)構(gòu)。若插入和刪除主要發(fā)生在表的首尾兩端 ,則宜采用尾指針表示的單循環(huán) 鏈表。棧是僅限制在表的一端進(jìn)行插入和刪除運(yùn)算的線性表 ,稱插入、刪除這一端為 棧頂,

7、另一端稱為棧底。表中無(wú)元素時(shí)為空棧。棧的修改是按后進(jìn)先出的原則進(jìn)行的 ,我們又稱棧為 LIFO 表。通常棧有順序棧和 鏈棧兩種存儲(chǔ)結(jié)構(gòu)。棧的基本運(yùn)算有六種 :構(gòu)造空棧 :InitStack,判?？?:StackEmpty,判棧滿 :StackFull, 進(jìn)棧 :Push,退棧 :Pop,取棧頂元素 :StackTop在順序棧中有 “上溢”和“下溢”的現(xiàn)象。 “上溢”是棧頂指針指出棧的外面是出 錯(cuò)狀態(tài)。 “下溢 ”可以表示棧為空棧 ,因此用來(lái)作為控制轉(zhuǎn)移的條件。順序棧中的基本操作有六種 :構(gòu)造空棧 ,判棧空 ,判棧滿 ,進(jìn)棧 ,退棧,取棧頂元素鏈棧則沒(méi)有上溢的限制 ,因此進(jìn)棧不要判棧滿。鏈棧不需

8、要在頭部附加頭結(jié)點(diǎn) 只要有鏈表的頭指針就可以了。鏈棧中的基本操作有五種 :構(gòu)造空棧 ,判?？?,進(jìn)棧,退棧 ,取棧頂元素隊(duì)列是一種運(yùn)算受限的線性表 ,插入在表的一端進(jìn)行 ,而刪除在表的另一端進(jìn) 行 ,允許刪除的一端稱為隊(duì)頭 ,允許插入的一端稱為隊(duì)尾,隊(duì)列的操作原則是先進(jìn)先出的 ,又稱作 FIFO 表.隊(duì)列也有順序存儲(chǔ)和鏈 式存儲(chǔ)兩種存儲(chǔ)結(jié)構(gòu)。隊(duì)列的基本運(yùn)算有六種 :置空隊(duì) :InitQueue,判隊(duì)空 :QueueEmpty,判隊(duì) 滿:QueueFull,入隊(duì):EnQueue,出隊(duì) :DeQueue,取隊(duì)頭元素 :QueueFront順序隊(duì)列的 “假上溢 ”現(xiàn)象:由于頭尾指針不斷前移 ,超出向

9、量空間。這時(shí)整個(gè) 向量空間及隊(duì)列是空的卻產(chǎn)生了 “上溢 ”現(xiàn)象。為了克服“假上溢 ”現(xiàn)象引入循環(huán)向量的概念 ,是把向量空間形成一個(gè)頭尾相接的環(huán)形 , 這時(shí)隊(duì)列稱循環(huán)隊(duì)列。判定循環(huán)隊(duì)列是空還是滿 ,方法有三種 :一種是另設(shè)一個(gè)布爾變量來(lái)判斷 ;第二 種是少用一個(gè)元素空間 ,入隊(duì)時(shí)先測(cè)試 %m=front?滿:空;第三種就是用一個(gè)計(jì)數(shù)器記錄隊(duì)列中的元素的總數(shù)。隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)稱為鏈隊(duì)列 ,一個(gè)鏈隊(duì)列就是一個(gè)操作受限的單鏈表。為 了便于在表尾進(jìn)行插入的操作 ,在表尾增加一個(gè)尾指針 ,一個(gè)鏈隊(duì)列就由一個(gè)頭指針和一個(gè)尾指針唯一地確定。鏈隊(duì)列不存在隊(duì) 滿和上溢的問(wèn)題。在鏈隊(duì)列的出隊(duì)算法中 ,要注意當(dāng)原隊(duì)

10、中只有一個(gè)結(jié)點(diǎn)時(shí) ,出隊(duì)后 要同進(jìn)修改頭尾指針并使隊(duì)列變空。串是零個(gè)或多個(gè)字符組成的有限序列。概念空串 :是指長(zhǎng)度為零的串 ,也就是串中不包含任何字符。空白串 :指串中包 含一個(gè)或多個(gè)空格字符的串。在一個(gè)串中任意個(gè)連續(xù)字符組成的子序列稱為該串的子串 ,包含子串的串就稱為主串。子串在 主串中的序號(hào)就是指子串在主串中首次出現(xiàn)的位置。空串是任意串的子串 ,任意串是自身的子串。串分為兩種 : 串常量在程序中只能引用不能改變 ; 串變量的值可以改變。串的基本運(yùn)算有 :求串長(zhǎng) strlen,串復(fù)制 strcpy,串聯(lián)接 strcat,串比較 charcmp,字 符定位 strchr。串是特殊的線性表 ,所

11、以串的存儲(chǔ)結(jié)構(gòu)與線性表的存儲(chǔ)結(jié)構(gòu)類似。串的順序存儲(chǔ)結(jié)構(gòu)簡(jiǎn)稱為順序串順序串又可按存儲(chǔ)分配的不同分為 :靜態(tài)存儲(chǔ)分配 :直接用定長(zhǎng)的字符數(shù)組來(lái) 定義。優(yōu)點(diǎn)是涉及串長(zhǎng)的操作速度快 ,但不適合插入、操作。動(dòng)態(tài)存儲(chǔ)分配 :是在定義串時(shí)不分配存儲(chǔ)空間 ,需要使用時(shí)按所需串 的長(zhǎng)度分配存儲(chǔ)單元。串的鏈?zhǔn)酱鎯?chǔ)就是用單鏈表的方式存儲(chǔ)串值 ,串的這種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)簡(jiǎn)稱為鏈 串。鏈串與單鏈表的差異只是它的結(jié)點(diǎn)數(shù)據(jù)域?yàn)閱蝹€(gè)字符。為了解決 “存儲(chǔ)密度”低的狀況 ,可以讓一個(gè)結(jié)點(diǎn)存儲(chǔ)多個(gè)字符 ,即結(jié)點(diǎn) 的大小。順序串上子串定位的運(yùn)算 :又稱串的 “模式匹配 ”或“串匹配 ”是,在主串中查找出 子串出現(xiàn)的位置。在串匹配中 ,

12、將主串稱為目標(biāo) ,子串稱為模式。這是比較容易理解的 ,串匹配問(wèn)題就是找出給定模式串 P 在給 定目標(biāo)串 T 中首次出現(xiàn)的有效位移或者是全部有效位移。最壞的情況下時(shí)間復(fù)雜 度是 Om, 假如 m 與 n 同階的話則它是 O。鏈串上的子串定位運(yùn)算位移是結(jié)點(diǎn)地址 而不是整數(shù)。數(shù)組一般用順序存儲(chǔ)的方式表示。存儲(chǔ)的方式有 :行優(yōu)先順序 ,也就是把數(shù)組逐行依次排列。 PASCAL 、C。列優(yōu) 先順序 ,就是把數(shù)組逐列依次排列。 FORTRAN地址的計(jì)算方法 :按行優(yōu)先順序排列的數(shù)組 :LOC(a=?.。按列優(yōu)先順序排列的 數(shù)組 :LOC(a=?.矩陣的壓縮存儲(chǔ) :為多個(gè)相同的非零元素分配一個(gè)存儲(chǔ)空間 ;對(duì)

13、零元素不分配空間特殊矩陣的概念 :所謂特殊矩陣是指非零元素或零元素分布有一定規(guī)律的矩 陣。稀疏矩陣的概念 :一個(gè)矩陣中若其非零元素的個(gè)數(shù)遠(yuǎn)遠(yuǎn)小于零元素的個(gè)數(shù) ,則 該矩陣稱為稀疏矩陣。特殊矩陣的類型 :對(duì)稱矩陣:三角矩陣:上三角陣 ,下三角陣,對(duì)角矩陣 k=f(I,j,廣義表是 n 個(gè)元素的有限序列 ,其中的元素是原子或者是一個(gè)廣義表。廣義表 表頭和表尾的概念 :廣義表有兩種表示法 ,一種是括號(hào)表示法 ,一種是圖形表示法。廣義表有兩個(gè)特殊的基本運(yùn)算 :取表頭 head:取表中的第一個(gè)數(shù)據(jù)元素 ,不能對(duì) 空表操作。取表尾 tail; 取除表頭外 ,其余數(shù)據(jù)元素構(gòu)成的子表 ,不能對(duì)空表操作樹(shù)是 n

14、 個(gè)結(jié)點(diǎn)的有限集合 ,非空時(shí)必須滿足 :只有一個(gè)稱為根的結(jié)點(diǎn) ;其余結(jié)點(diǎn) 形成 m 個(gè)不相交的子集 ,并稱根的子樹(shù)。根是開(kāi)始結(jié)點(diǎn);結(jié)點(diǎn)的子樹(shù)數(shù)稱度 ;度為 0 的結(jié)點(diǎn)稱葉子 ;度不為 0 的結(jié)點(diǎn)稱分支結(jié)點(diǎn) ;除 根外的分支結(jié)點(diǎn)稱內(nèi)部結(jié)點(diǎn) ;有序樹(shù)是子樹(shù)有左 ,右之分的樹(shù) ;無(wú)序樹(shù)是子樹(shù)沒(méi)有左 ,右之分的樹(shù) ;森林是 m 個(gè) 互不相交的樹(shù)的集合 ;樹(shù)的四種不同表示方法 :樹(shù)形表示法 ;嵌套集合表示法 ; 凹入表示法 ;廣義表表示 法。二叉樹(shù)的定義 :是 n0個(gè)結(jié)點(diǎn)的有限集 ,它是空集或由一個(gè)根結(jié)點(diǎn)及兩棵互不 相交的分別稱作這個(gè)根的左子樹(shù)和右子樹(shù)的二叉樹(shù)組成。二叉樹(shù)不是樹(shù)的特殊情形 ,與度數(shù)為 2

15、的有序樹(shù)不同。二叉樹(shù)的 4 個(gè)重 要性質(zhì):二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)就是把二叉樹(shù)的所有結(jié)點(diǎn)按照層次順序存儲(chǔ)到連續(xù)的 存儲(chǔ)單元中。樹(shù)的存儲(chǔ)結(jié)構(gòu)多用的是鏈?zhǔn)酱鎯?chǔ)。二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) ,稱為二叉鏈表。它 就是由根指針 root 唯一確定的。共有 2n 個(gè)指針域 ,n+1個(gè)空指針。根據(jù)結(jié)點(diǎn)的次序不同可得三種遍歷 :先序遍歷 ,中序遍歷、后序遍歷。時(shí)間復(fù) 雜度為。利用二叉鏈表中的 n+1 個(gè)空指針域來(lái)存放指向某種遍歷次序下的前趨結(jié)點(diǎn)和 后繼結(jié)點(diǎn)的指針 ,這些附加的指針就稱為 “線索 ”加,上線索的二叉鏈表就稱為線索鏈表。線索使得查找中序前趨和中序后繼變得簡(jiǎn) 單有效 ,但對(duì)于查找指定結(jié)點(diǎn)的前序前趨和后序后繼并

16、沒(méi)有什么作用。樹(shù)和森林及二叉樹(shù)的轉(zhuǎn)換是唯一對(duì)應(yīng)的。二叉樹(shù)變樹(shù) :結(jié)點(diǎn)的右孩子與其雙親 連。森林變二叉樹(shù) :樹(shù)變二叉樹(shù) ,各個(gè)樹(shù)的根相連。轉(zhuǎn)換方法?樹(shù)的存儲(chǔ)結(jié)構(gòu) :有雙親鏈表表示法 :孩子鏈表表示法 :雙親孩子鏈表表示法 :孩子 兄弟鏈表表示法 :樹(shù)的前序遍歷與相對(duì)應(yīng)的二叉樹(shù)的前序遍歷一致 ;樹(shù)的后序遍歷與相對(duì)應(yīng)的二 叉樹(shù)的中序遍歷一致。樹(shù)的帶權(quán)路徑長(zhǎng)度 ?最優(yōu)二叉樹(shù) ?完全二叉樹(shù) ?哈夫曼樹(shù)及其性質(zhì) ,變長(zhǎng)編碼技術(shù)可以使頻度高的字符編碼短 ,而頻度低的字符編碼長(zhǎng) ,但是變長(zhǎng) 編碼可能使解碼產(chǎn)生二義性。如 00、01、0001 這三個(gè)碼無(wú)法在解碼時(shí)確定是哪一個(gè) ,所以要求在字符編碼時(shí)任一字符的編

17、碼都不 是其他字符編碼的前綴 ,這種碼稱為前綴碼。哈夫曼樹(shù)的應(yīng)用。圖的邏輯結(jié)構(gòu)特征就是其結(jié)點(diǎn)的前趨和后繼的個(gè)數(shù)都是沒(méi)有限制的,即任意兩個(gè)結(jié)點(diǎn)之間之間都可能相關(guān)。圖,有向圖,無(wú)向圖,簡(jiǎn)單路徑,簡(jiǎn)單回路 ,網(wǎng)絡(luò)等及其性質(zhì)。圖的存儲(chǔ)結(jié)構(gòu) :鄰接矩陣表示法 :適合稠密圖。無(wú)向鄰接矩陣是對(duì)稱的。有向 行是出度 ,列是入度。建立鄰接矩陣算法的時(shí)間是O,其時(shí)間復(fù)雜度為 O。鄰接表表示法 :適合稀疏圖。時(shí)間復(fù)雜度為 O,空間復(fù)雜 度為 O。圖的遍歷:深度優(yōu)先遍歷 :借助于鄰接矩陣的列。使用棧保存已結(jié)點(diǎn)。廣度優(yōu) 先遍歷 :借助于鄰接矩陣的行。使用隊(duì)列保存已結(jié)點(diǎn)。生成樹(shù)的定義 :最小生成樹(shù):Prim 算法的時(shí)間復(fù)

18、雜度為 O與邊數(shù)無(wú)關(guān)適于稠密 圖。 Kruskal 算法的時(shí)間復(fù)雜度為 O,主要取決于邊數(shù),較適合于稀疏圖。最短路徑的算法 :Dijkstra 算法 ,時(shí)間復(fù)雜度為 O。拓?fù)渑判?:無(wú)前趨的頂點(diǎn)優(yōu)先 :每次輸出一個(gè)無(wú)前趨的結(jié)點(diǎn)并刪去此結(jié)點(diǎn)及其 出邊,最后得到的序列即拓?fù)湫蛄?。無(wú)后繼的結(jié)點(diǎn)優(yōu)先 :每次輸出一個(gè)無(wú)后繼的結(jié)點(diǎn)并刪去此結(jié)點(diǎn)及其入邊 ,最后得到的序列是逆拓?fù)湫蛄嘘P(guān)于排序關(guān)鍵字項(xiàng) ,關(guān)鍵字。排序是使文件中的記錄按關(guān)鍵字遞增次序排列起來(lái)?；静僮?:比較關(guān)鍵字大小 ; 改變指向記錄的指針或移動(dòng)記錄。存儲(chǔ)結(jié)構(gòu) :順序結(jié)構(gòu)、鏈表結(jié)構(gòu)、索引結(jié)構(gòu)。經(jīng)過(guò)排序后這些具有相同關(guān)鍵字 的記錄之間的相對(duì)次序保

19、持不變 ,則稱這種排序方法是穩(wěn)定的 ,否則排序算法是不穩(wěn)定的。排序過(guò)程中不涉及數(shù)據(jù)的內(nèi)、外存交換則稱之為 “內(nèi)部排序 ”反,之 ,若存在數(shù)據(jù) 的內(nèi)外存交換 ,則稱之為外排序。內(nèi)部排序方法可分五類 :插入排序、選擇排序、交換排序、歸并排序和分配排 序。評(píng)價(jià)排序算法好壞的標(biāo)準(zhǔn)主要有兩條 :執(zhí)行時(shí)間和所需的輔助空間 ,另外算法 的復(fù)雜程序也是要考慮的一個(gè)因素。插入排序 :直接插入排序 ;逐個(gè)向前插入到合適位置 ;哨兵有兩個(gè)作用 ;作為臨變 量存放 Ri;是在查找循環(huán)中用來(lái)監(jiān)視下標(biāo)變量 j 是否越界;直接插入排序是穩(wěn)定排序。時(shí)間復(fù)雜度為 O ?比較次數(shù)為 /2;移動(dòng)次數(shù) 為?。希爾排序 :等間隔的數(shù)據(jù)

20、比較并按要求順序排列 ,最后間隔為 1;希爾排序是就地 的不穩(wěn)定排序。時(shí)間復(fù)雜度為 O,比較次數(shù)為 ;移動(dòng)次數(shù)為 ;交換排序:冒泡排序 :自下向上確定最輕的一個(gè)。自上向下確定最重的一個(gè)。 冒泡排序是就地的穩(wěn)定排序。時(shí)間復(fù)雜度為 O?比較次數(shù)為?;移動(dòng)次數(shù)為 ?;快速排序:以第一個(gè)元素為參考基準(zhǔn) ,設(shè)定、動(dòng)兩個(gè)指針發(fā)生交換后指針交換位置 ,直到指針重合重復(fù)直到排序完成?？焖倥判蚴遣环€(wěn)定排序。時(shí)間復(fù)雜度為 O?比較次數(shù)為 ?選擇排序 :直接選擇排序 ;選擇最小的放在比較區(qū)前 ;直接選擇排序不穩(wěn)定排 序。時(shí)間復(fù)雜度為 O?。比較次數(shù)為 ?。堆排序 :建堆:按層次將數(shù)據(jù)填入完全二叉樹(shù) ,從 int 處

21、向前逐個(gè)調(diào)整位置。然后將樹(shù)根與最后 一個(gè)葉子交換值并斷開(kāi)與樹(shù)的連接并重建堆 ,直到全斷開(kāi)。堆排序是就地不穩(wěn)定的 排序 ,時(shí)間復(fù)雜度為 O,不適宜于記錄數(shù)較少的文件。歸并排序:先兩個(gè)一組排序 ,形成/2組,再將兩組并一組 ,直到剩下一組為止。歸 并排序是非穩(wěn)定排序 ,時(shí)間復(fù)雜度是 O?基數(shù)排序 :從低位到高位依次對(duì)關(guān)鍵字進(jìn)行箱排序?；鶖?shù)排序是非就穩(wěn)定的排 序 ,時(shí)間復(fù)雜度是 O?。各種排序方法的比較和選擇 :1、待排序的記錄數(shù)目 n;n較大的要用時(shí)間復(fù)雜度為 O的排序方法 ;2、記錄的大小 ;記錄大最好用鏈表作為存儲(chǔ)結(jié)構(gòu) ,而快速排序和堆排序在鏈表 上難于實(shí)現(xiàn) ;3、關(guān)鍵字的結(jié)構(gòu)及其初始狀態(tài) ;4、對(duì)穩(wěn)定性的要求 ;5、語(yǔ)言工具的條件 ;6、存儲(chǔ)結(jié)構(gòu) ;時(shí)間和輔助空間復(fù)雜度。關(guān)于查找查找的同時(shí)對(duì)表做修改操作則相應(yīng)的表稱之為動(dòng)態(tài)查找表 ,否則稱之為靜態(tài)查找表。衡量查找算法效率優(yōu)劣的標(biāo)準(zhǔn)是在查找過(guò)程中對(duì)關(guān)鍵字需要執(zhí)行的平均比較 次數(shù)。線性表查找的方法：順序查找：逐個(gè)查找， ASL= ？;二分查找：取中點(diǎn) int 比較，若小就比左區(qū)間，大就比右區(qū)間。用二叉判定樹(shù) 表示。 ASL= ？;分塊查找： 要求“分塊有序”，將表分成若干塊內(nèi)部不