計(jì)算機(jī)-數(shù)據(jù)結(jié)構(gòu)

1、數(shù)據(jù)結(jié)構(gòu)第一章 算法與數(shù)據(jù)結(jié)構(gòu)概述 第二章 簡(jiǎn)單數(shù)據(jù)結(jié)構(gòu)第三章 排序 第四章 檢索 第五章 樹結(jié)構(gòu) 第六章 圖結(jié)構(gòu) 第七章 多維數(shù)組、稀疏矩陣和廣義表 第一章 算法與數(shù)據(jù)結(jié)構(gòu)概述1.1 數(shù)據(jù)結(jié)構(gòu)基本概念1.2 數(shù)據(jù)的邏輯結(jié)構(gòu)1.3 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)1.4 數(shù)據(jù)的運(yùn)算1.5 算法及表示1.6 算法時(shí)間及空間復(fù)雜分析1.1 數(shù)據(jù)結(jié)構(gòu)基本概念 數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)科學(xué)的重要基礎(chǔ)，近年來發(fā)展成為一個(gè)專門學(xué)科，經(jīng)過多年的研究，根據(jù)各種實(shí)際問題的要求，提出了許多組織數(shù)據(jù)的方法，構(gòu)造了不同的數(shù)據(jù)結(jié)構(gòu)，而且隨著處理實(shí)際問題的要求，還會(huì)提出新的更加復(fù)雜的數(shù)據(jù)結(jié)構(gòu)。 數(shù)據(jù)結(jié)構(gòu)主要研究要問題的求解方法，典型數(shù)據(jù)結(jié)構(gòu)的算法

2、及程序設(shè)計(jì)方法。 對(duì)于每一種數(shù)據(jù)結(jié)構(gòu)，主要包括3方面的內(nèi)容：數(shù)據(jù)之間的邏輯關(guān)系，稱為數(shù)據(jù)的邏輯結(jié)構(gòu)；數(shù)據(jù)在計(jì)算機(jī)中的存儲(chǔ)方式，稱為數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)；數(shù)據(jù)的運(yùn)算。 討論這三個(gè)問題的主要目的是為了提高數(shù)據(jù)處理效率。所謂提高數(shù)據(jù)處理效率體現(xiàn)為：數(shù)據(jù)處理的速度，盡量節(jié)省數(shù)據(jù)處理過程中所占用計(jì)算機(jī)存儲(chǔ)空間。1.1 數(shù)據(jù)結(jié)構(gòu)基本概念 下面通過實(shí)例來說明數(shù)據(jù)結(jié)構(gòu)組織對(duì)數(shù)據(jù)處理效率的影響： 一、無序表的順序查找與有序表的二分查找。 表1 ： 表2： 若要在表1 中查找一個(gè)元素，由于數(shù)據(jù)存放的沒有規(guī)律，只能從第1個(gè)數(shù)開始順序進(jìn)行查找，直到所有的數(shù)據(jù)找完為止。 若要在表2 中查找一個(gè)元素，由于數(shù)據(jù)是從小到大有規(guī)律存

3、放，可用二分法進(jìn)行查找，提高查找效率。這與字典中的內(nèi)容按順序編輯方便查找是一樣。35 16 78 85 43 29 33 21 54 4616 21 29 33 35 43 46 54 78 851.1 數(shù)據(jù)結(jié)構(gòu)基本概念二、學(xué)生成績(jī)登記表中的數(shù)據(jù)處理。 學(xué)生情況登記表 在表中查找給定學(xué)號(hào)的某學(xué)生的情況是很方便的，只要給定學(xué)號(hào)就要立即查到該學(xué)生的情況（學(xué)號(hào)從小到大排列）。若要查找某個(gè)分?jǐn)?shù)段的學(xué)生情況，只需把以上數(shù)據(jù)重組得到其它的表格，即可得到所查結(jié)果。可見把數(shù)據(jù)組織成不同的形式，便于做某種運(yùn)算，從而提高了數(shù)據(jù)的處理效率。學(xué)號(hào)姓名性別年齡成績(jī)970156張小青女2086970157趙 凱男1983

4、970158李啟明男1970970159劉 華女2191970160張 軍男18801.2 數(shù)據(jù)的邏輯結(jié)構(gòu) 數(shù)據(jù)的邏輯結(jié)構(gòu)是對(duì)數(shù)據(jù)間關(guān)系的描述，形式上或用一個(gè)二元組來表示，即： B=（K，R） K為結(jié)點(diǎn)的有窮集合，即K是由有限個(gè)結(jié)點(diǎn)所構(gòu)成的集合；R是K上的關(guān)系的有窮集合，即R是有限關(guān)系所構(gòu)成的集合，其中關(guān)系都是K到K的關(guān)系。 結(jié)點(diǎn)類型是指結(jié)點(diǎn)的值的組織方式，即數(shù)據(jù)的類型。 可分為初等類型及組合類型兩大類型，只含為一個(gè)基本數(shù)據(jù)類型屬于初等類型（整型、實(shí)型、字符型、指針類型）；組合類型是由初等類型以某種方式組合而成的。 數(shù)據(jù)結(jié)構(gòu)分為線性數(shù)據(jù)結(jié)構(gòu)和非線性結(jié)構(gòu) 線性結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)里有且僅有一個(gè)終端結(jié)點(diǎn)

5、和一個(gè)開始結(jié)點(diǎn)，所有結(jié)點(diǎn)最多只有一個(gè)前驅(qū)的一個(gè)后繼。（數(shù)組） 非線性結(jié)構(gòu)：不滿足線性結(jié)構(gòu)的數(shù)據(jù)。（樹、圖）1.2 數(shù)據(jù)的邏輯結(jié)構(gòu) 線性結(jié)構(gòu)的表示形式： K=A，B，C，D，E，F(xiàn) R=,。 數(shù)據(jù)結(jié)構(gòu)里有且僅有一個(gè)終端結(jié)點(diǎn)和一個(gè)開始結(jié)點(diǎn)，所有結(jié)點(diǎn)最多只有一個(gè)前驅(qū)的一個(gè)后繼。 非線性結(jié)構(gòu)表示形式： K=k1k9 R=, , , ,。ABCDEFk1k3k4k7k8k2k5k6k91.3 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu) 數(shù)據(jù)的邏輯結(jié)構(gòu)與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)無關(guān)，是獨(dú)立于計(jì)算機(jī)的，計(jì)算機(jī)存儲(chǔ)器有有限個(gè)存儲(chǔ)單元，每個(gè)單元有惟一的地址，存儲(chǔ)單元是連續(xù)編址的。建立一個(gè)從結(jié)點(diǎn)到地址單元的映像，體現(xiàn)結(jié)點(diǎn)之間的關(guān)系。有4 種基本的存儲(chǔ)

6、映像方法： 順序方法：主要用于線性數(shù)據(jù)結(jié)構(gòu)。把邏輯上相鄰的結(jié)點(diǎn)存儲(chǔ)在物理上相鄰的存儲(chǔ)單元內(nèi)，結(jié)點(diǎn)之間的關(guān)系由存儲(chǔ)單元的連接關(guān)系來體現(xiàn)。 鏈接方法：每個(gè)結(jié)點(diǎn)附上指針字段，存儲(chǔ)單元內(nèi)容分為二部分：結(jié)點(diǎn)本身與存放后繼結(jié)點(diǎn)的存儲(chǔ)單元地址。 索引方法；在線性結(jié)構(gòu)里，結(jié)點(diǎn)排成序列k1,k2,kn ,每個(gè) ki在序列里都有對(duì)應(yīng)的位置i，這個(gè)位置為結(jié)點(diǎn)的索引，用結(jié)點(diǎn)的 索引號(hào)來確定結(jié)點(diǎn)的存儲(chǔ)地址。 散列法：根據(jù)結(jié)點(diǎn)的值來確定它的存儲(chǔ)地址，用散列函數(shù)。1.4 數(shù)據(jù)的運(yùn)算 各種邏輯結(jié)構(gòu)有其相應(yīng)的運(yùn)算，每種邏輯結(jié)構(gòu)有一個(gè)運(yùn)算集合。數(shù)據(jù)的運(yùn)算是定義在數(shù)據(jù)的邏輯結(jié)構(gòu)上的，運(yùn)算的具體實(shí)現(xiàn)要在存儲(chǔ)結(jié)構(gòu)上進(jìn)行，常見的運(yùn)算有檢

7、索、插入、刪除、更新、排序、遍歷。 檢索：是在數(shù)據(jù)結(jié)構(gòu)中查找滿足條件的結(jié)點(diǎn)。 插入：是在數(shù)據(jù)結(jié)構(gòu)中的指定位置增加新的結(jié)點(diǎn)。 刪除：是把指定位置的結(jié)點(diǎn)從數(shù)據(jù)結(jié)構(gòu)中刪除。 更新：是指改變數(shù)據(jù)結(jié)構(gòu)中指定結(jié)點(diǎn)的一個(gè)或多個(gè)字段的值。 排序：是指保持線性結(jié)構(gòu)的結(jié)點(diǎn)序列結(jié)點(diǎn)數(shù)不變，把結(jié)點(diǎn)按某種指定順序重新排列。 遍歷：是指按某種方式，訪問過數(shù)據(jù)結(jié)構(gòu)中的每個(gè)結(jié)點(diǎn)。1.5 算法及表示 算法是為解決一個(gè)問題采取的方法和步驟，換句話說，算法是為實(shí)現(xiàn)某個(gè)計(jì)算過程而規(guī)定的基本動(dòng)作的執(zhí)行序列。算法分為數(shù)值算法與非數(shù)值算法。 算法的五個(gè)特點(diǎn)： 一、有限操作步驟（有窮性） 二、每一步驟都為確定的（確定性） 三、從外界輸入信息

8、（輸入） 四、輸出信息（輸出） 五、每一步驟都應(yīng)有效地執(zhí)行（有效性） 算法的表示： 一、自然語(yǔ)言 用自然語(yǔ)言表示算法，要求寫出算法的步驟。1.5 算法及表示 二、偽代碼表示 可用中文或英文書寫，無論用什么方法書寫，都要標(biāo)志出算法的開始和結(jié)束，中文用“開始”和“結(jié)束”，英文用BEGIN和END。 三、流程圖表示 流程圖是使用規(guī)定的圖形，用流程線連接起來表示算法步驟與過程的圖形，對(duì)于判斷應(yīng)用Yes和No表示程序的分支。 四、結(jié)構(gòu)化流程圖 NS圖，是為提倡結(jié)構(gòu)化程序提出的流程圖形式。它自頂向下，逐步細(xì)化，模塊化設(shè)計(jì)和結(jié)構(gòu)化編碼。 五、PAD圖表示 類似與Windows 操作系統(tǒng)中資源管理器的形式，在

9、左邊形成一條流程線。1.6 算法時(shí)間及空間復(fù)雜分析 評(píng)價(jià)一個(gè)算法與數(shù)據(jù)結(jié)構(gòu)的優(yōu)劣主要有兩點(diǎn)：即算法執(zhí)行過程中所占用的存儲(chǔ)單元數(shù)目和算法執(zhí)行的時(shí)間效率，前者稱空間復(fù)雜度，后者稱為時(shí)間復(fù)雜度。 一、時(shí)間復(fù)雜度 為了分析某一算法的時(shí)間復(fù)雜度，可以將執(zhí)行算法過程中的那些基本操作的次數(shù)分離出來，忽略其它的細(xì)節(jié)問題，僅計(jì)算基本操作的次數(shù)。 一個(gè)算法的時(shí)間復(fù)雜度是指執(zhí)行該算法的基本運(yùn)算次數(shù)。這種基本運(yùn)算次數(shù)的計(jì)算不僅取決于輸入處理數(shù)據(jù)的大小，也取決于數(shù)據(jù)本身的性質(zhì)。 例如：排序算法中的基本運(yùn)算是比較運(yùn)算，而忽略了賦值運(yùn)算。而矩陣乘法算法中的基本運(yùn)算是乘法，而忽略了加法運(yùn)算。即不同的算法中基本運(yùn)算是不同的。1

10、.6 算法時(shí)間及空間復(fù)雜分析 二、空間復(fù)雜度 算法執(zhí)行過程中所占的存儲(chǔ)單元的數(shù)目稱為空間復(fù)雜度。即存放算法本身包含的語(yǔ)句、常數(shù)、變量、輸入數(shù)據(jù)和實(shí)現(xiàn)運(yùn)算所需的數(shù)據(jù)。 但在時(shí)間復(fù)雜度和空間復(fù)雜度中前者比后者更重要，以后的算法復(fù)雜分析時(shí)一般指的是時(shí)間復(fù)雜度。 常見時(shí)間復(fù)雜的表示： O(1): 常數(shù)時(shí)間復(fù)雜度 O(log2n): 對(duì)數(shù)時(shí)間復(fù)雜 O(n): 一次多項(xiàng)式時(shí)間復(fù)雜 O(n2): 二次多項(xiàng)式時(shí)間復(fù)雜 O(2n): 指數(shù)階時(shí)間復(fù)雜第二章 簡(jiǎn)單數(shù)據(jù)結(jié)構(gòu)2.1 線性結(jié)構(gòu)2.2 鏈表2.3 雙向鏈表2.4 動(dòng)態(tài)存儲(chǔ)管理2.1 .1線性表 計(jì)算機(jī)所處理的數(shù)據(jù)，大部分是表格形式。 線性表是一組有序的數(shù)據(jù)

11、元素，線性表中的每個(gè)結(jié)點(diǎn)，除第一個(gè)外，都只有一個(gè)直接前驅(qū)，除最后一個(gè)結(jié)點(diǎn)外，只有一個(gè)直接后繼。 線性結(jié)構(gòu)有線性表、堆棧、隊(duì)列、線性鏈表等。 2.1線性表 1.線性表的概念 一個(gè)線性表可表示為：(a1,a2,an)。 其中a1,a2,an是結(jié)點(diǎn)，也稱為元素，它的下標(biāo)表示結(jié)點(diǎn)的序號(hào)及該結(jié)點(diǎn)在線性表中的位置。n表示表中元素的總數(shù)目，定義為表的長(zhǎng)度，當(dāng)n為0 是，線性表為空。 線性表在計(jì)算機(jī)中的存儲(chǔ)方式 線性存儲(chǔ)：用一組連續(xù)的存儲(chǔ)單元來順序存儲(chǔ)線性表中的2.1 .1線性表結(jié)點(diǎn)。若表中的每個(gè)結(jié)點(diǎn)占有相同的存儲(chǔ)空間，設(shè)為1個(gè)存儲(chǔ)單元，則第i個(gè)元素的地址為： LOC(ai)=LOC(a1)+(i-1) 1其

12、中LOC(a1)為線性的起始地址，即表中第一個(gè)元素的地址。存儲(chǔ)形式如下： 2.線性表的運(yùn)算 線性表有以下7種基本運(yùn)算，重點(diǎn)討論元素的插入與刪除，排序及查找在以后的章節(jié)中介紹。 (1) 取出線性表中的第i 個(gè)元素 (2) 修改線性表中第i 個(gè)元素的值 (3) 在線性表中第i 個(gè)元素后插入一個(gè)元素a1a2ai.an2.1 .1線性表 (4) 刪除線性表中的第i 個(gè)元素 (5) 按某種要求重排線性表中元素的順序 (6) 在線性表中查找滿足條件的元素 (7) 判斷線性表是否為空 對(duì)于順序存儲(chǔ)的線性表，經(jīng)過上述運(yùn)算后仍要保持順序存儲(chǔ)。線性表用順序方法存儲(chǔ)稱為順序表。 3.完成線性表的運(yùn)算的C程序： (1

13、) 建立線性表： int creat_list(int *) (2) 刪除第i 個(gè)元素: void del_list(int *,int) (3) 在第i 個(gè)元素后插入一個(gè)元素void insert_list(int *,int,int) (4) 輸出線性表中的元素: void out_list(int *) 作業(yè):編寫刪除與插入元素的函數(shù)。 2.1 .1線性表 4.線性表插入和刪除元素算法的時(shí)間復(fù)雜度： 插入與刪除元素算法的基本運(yùn)算是向后、向前移動(dòng)元素，即計(jì)算出插入與刪除元素的移動(dòng)次數(shù)，就得出了算法的時(shí)間復(fù)雜度。 假設(shè)在線性表中插入與刪除運(yùn)算中，任意位置插入與刪除的概率相等。 若線表中有n個(gè)

14、元素，插入時(shí)需有n+1個(gè)空間，在第j個(gè)位置插入時(shí)移動(dòng)的次數(shù)為： n+1- j； 當(dāng)n=1,2,n+1時(shí)，總的移動(dòng)次的平均值為： 刪除時(shí)的平均移動(dòng)次數(shù)為： 時(shí)間復(fù)雜度為O(n) 112) 1(11njnjnnnjnjnn121)(12.1.2 堆棧 1.堆棧的概念 堆棧又稱為棧，是一種應(yīng)用十分廣泛的數(shù)據(jù)結(jié)構(gòu)。它是一個(gè)特殊的線性表，它只能在表的一端進(jìn)行插入和刪除。因此后進(jìn)入棧的元素必須先退出，先進(jìn)入棧的元素必須后退出。通常稱為“先進(jìn)后出”或“后進(jìn)先出”。在堆棧中有棧底(bottom)和棧頂（top）。如圖所示： 設(shè)棧S=(a1,a2,.,an)， a1是棧底元素， an是棧頂元素，進(jìn)棧序?yàn)椋?a1

15、,a2,.,an，則出棧相反。 2.棧的工作方式： (1)棧底是可動(dòng)的,棧頂是固定的,由棧頂壓入一個(gè)元素,包括棧底在內(nèi)的元素依次下移,一個(gè)元素彈出時(shí),棧內(nèi)元素相應(yīng)上移. (2)棧底是固定的，棧頂是可動(dòng)的。棧頂（top）ana2a1棧底（bottom）a02.1.2 堆棧 3.堆棧的基本運(yùn)算（棧底是固定的，棧頂是可動(dòng)的） 棧的壓入：往棧的頂部壓入元素 void push_stack(int *,int ) 棧的彈出：從棧頂刪除一個(gè)元素 void pop_stack(int *) 讀棧頂元素：棧保持不變，把棧頂元素的值讀入一個(gè)變量x中 int read_stack(int *) 判斷棧是否為空：判

16、斷棧中是否有元素，讀棧頂元素與棧的彈出需要判斷棧是否為空 int empty_stack(int *) 取出棧頂元素：把棧頂元素作為函數(shù)值返回，但要?jiǎng)h除棧頂元素 int ptop_stack(int *) 判斷棧是否為滿：判斷棧中是否能壓入元素，棧頂?shù)膲喝霑r(shí)需要判斷棧是否為滿 int over_stack(int *) 作業(yè)：完成讀棧頂元素，判斷棧是否為空，判斷棧是否為滿，取出棧頂元素的操作。程序?yàn)椋簊tack.cpp2.1.2 堆棧 4.堆棧的應(yīng)用實(shí)例 例1：對(duì)函數(shù)的調(diào)用及返回的處理。調(diào)用函數(shù)時(shí)，將其斷點(diǎn)r,s,t依次壓入堆棧，返回時(shí)將t,s, r依次彈出。如圖所示： 主程序 函數(shù)1 函數(shù)2

17、 函數(shù)3 r s t 例2：堆棧變化的程序。 觀察change_stack.cpp的執(zhí)行結(jié)果，分析堆棧中的數(shù)據(jù)變化。棧tsr2.1.2 堆棧 例3：用堆棧把中綴表達(dá)式變?yōu)楹缶Y表達(dá)式的程序。對(duì)應(yīng)計(jì)算機(jī)編譯系統(tǒng)中的算術(shù)表達(dá)式的編譯。 中綴表達(dá)式 后綴表達(dá)式 A+B AB+ A+B*C ABC*+ A*(B-C)+D ABC-*D+ D+A/(B-C) DABC-/+ “+-*/”四功能表達(dá)式的計(jì)算分二步： (1)、將中綴表達(dá)式變?yōu)榈葍r(jià)的后綴表達(dá)式。 (2)、使用后綴表達(dá)式進(jìn)行計(jì)算。 以上步驟的算法描述如下： 先將中綴表達(dá)式轉(zhuǎn)換為等價(jià)的后綴表達(dá)式，如將： 2.1.2 堆棧 3*(5-2)+7 轉(zhuǎn)換為

18、 3 5 2 -*7 + 算法描述如下： 置初始狀態(tài)，i=0,j=0; 讀入中綴表達(dá)式到數(shù)組e中。 從左向右掃描中綴表達(dá)式，轉(zhuǎn)換為后綴表達(dá)式。 當(dāng)eiq時(shí)，執(zhí)行下列語(yǔ)句： (a)分情況執(zhí)行下列語(yǔ)句： ei=0,9時(shí)執(zhí)行：aj=ei,i+,j+; ei=(或+,-,*,/時(shí)執(zhí)行 ：push(ei) 壓入棧 ei=)時(shí)：w=ptop(),aj=w,j+,pop() 取出棧頂元素，在彈出一個(gè)元素。 ei=q時(shí)循環(huán)結(jié)束。 (b) i=i+1; 輸出a的內(nèi)容。 程序?yàn)椋篶onvert.cppa棧+7*-2-5(3*+2.1.2 堆棧 第2步使用后綴表達(dá)式進(jìn)行計(jì)算： 使用后綴表達(dá)式計(jì)算過程可以用數(shù)棧來實(shí)現(xiàn)

19、，將操作數(shù)送入數(shù)棧，每取一個(gè)運(yùn)算符，取出數(shù)棧棧頂?shù)膬蓚€(gè)數(shù)，進(jìn)行指定的運(yùn)算符的計(jì)算，形成一條計(jì)算指令，將計(jì)算機(jī)結(jié)果送入數(shù)棧，直到所有運(yùn)算符掃描完為止。 3 2 5 +7 *-.q 的計(jì)算來說明數(shù)棧的變化：程序?yàn)椋篺our_calc.cpp 二個(gè)程序合起來可完成表達(dá)式計(jì)算。5+7*-2749333-462.1.3 隊(duì)列 3、隊(duì)列（queue） 隊(duì)列的概念：隊(duì)列簡(jiǎn)稱隊(duì)，是線性表的一種特殊形式，是一種應(yīng)用很廣的數(shù)據(jù)結(jié)構(gòu)，對(duì)隊(duì)列的插入操作中只能在表的一端進(jìn)行，而刪除操作也只能在表的另一端進(jìn)行，插入一端稱為隊(duì)尾，刪除一端稱為隊(duì)頭，分別用R(rear)和F(front)表示。隊(duì)列也稱為先進(jìn)先出表，隊(duì)列操作示

20、意圖： 隊(duì)列操作的兩種方式： 移位法：占用空間固定，出隊(duì)向后移，進(jìn)隊(duì)后也向后移。這種隊(duì)列操作方式需要的存儲(chǔ)空間比較大。 循環(huán)法：進(jìn)隊(duì)時(shí)當(dāng)隊(duì)尾序號(hào)與隊(duì)長(zhǎng)相同時(shí)，下一個(gè)元素進(jìn)隊(duì)時(shí)占用第一個(gè)元素的位置 。m個(gè)空間可放m-1元素。 出隊(duì)a1a2a3an進(jìn)隊(duì)頭(F)尾(R)2.1.3 隊(duì)列 隊(duì)列的運(yùn)算(循環(huán)隊(duì)列) 隊(duì)列的插入:在隊(duì)列中插入一個(gè)值為x的結(jié)點(diǎn),enq(Q,x); 算法:：QR=x; 若R=m0,則R=1;否則R=R+1; 若R=F,輸出隊(duì)列滿。算法結(jié)束。 隊(duì)列的刪除:在隊(duì)列中刪除一個(gè)結(jié)點(diǎn),deq(Q); 算法：若R=F，則：輸出隊(duì)列空； 否則 若F= m0 ,則F=1； 否則F=F+1； 讀

21、隊(duì)列的頭結(jié)點(diǎn)：將隊(duì)列中頭結(jié)點(diǎn)的值讀入x中,front(Q,x)； 算法：若R=F，輸出錯(cuò)誤；否則x=QF; 判斷隊(duì)列是否為空：返回0或1,qempty(Q); 算法：若R=F，則返回1；否則返回0；2.1.3 隊(duì)列 具體表示算法的C程序： void qen(char x)/*元素進(jìn)隊(duì)*/ if(r=MAX-1) if(f=0) printf(隊(duì)列滿！ n);return; else qr=x;r=0;return; if(r=f-1&qf!=0) printf(隊(duì)列滿！ n);return; qr=x; r+; MAX表示隊(duì)列中可存放元素的個(gè)數(shù)。 x要插入的元素。 f表示隊(duì)頭元素的下標(biāo)

22、。r表示隊(duì)尾元素的下標(biāo)。 q表示存放隊(duì)列元素的數(shù)組。2.1.3 隊(duì)列 具體表示算法的C程序： char den()/*刪除元素*/ char ch; if(f=r) printf(“隊(duì)列空！n)；return NULL; ch=qf; f+; if(f=MAX) then f=0; return ch; MAX表示隊(duì)列中可存放元素的個(gè)數(shù)。ch返回的頭結(jié)點(diǎn)值。 f表示隊(duì)頭元素的下標(biāo)。r表示隊(duì)尾元素的下標(biāo)。 q表示存放隊(duì)列元素的數(shù)組。隊(duì)列操作演示程序 queue.cpp2.2 鏈表 線性鏈表是一種不要求連續(xù)存儲(chǔ)空間的線性表，它定義的每個(gè)結(jié)點(diǎn)不是一個(gè)基本數(shù)據(jù)構(gòu)成的。 1.線性鏈表的基本概念 表的每個(gè)

23、結(jié)點(diǎn)至少由二部分組成，即數(shù)據(jù)域和指針域，數(shù)據(jù)域存放結(jié)點(diǎn)的值，指針域存放下一個(gè)結(jié)點(diǎn)的存儲(chǔ)地址(指針)。線性鏈表就是靠這些指針作為鏈按要求的順序組成了一個(gè)線性表。線性中除了最后一個(gè)結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)只有一個(gè)指向后繼結(jié)點(diǎn)的指針，最后一個(gè)結(jié)點(diǎn)的指針為（空）NULL。 在C語(yǔ)言中結(jié)點(diǎn)的定義是由結(jié)構(gòu)體類型來定義的，一般定義如下： struct link 示意圖： int data; struct link *next; next是指向自己的指針變量。 。2.2 鏈表 2.線性鏈表的存儲(chǔ)分配 若鏈表的結(jié)構(gòu)體定義如下： struct link int data; struct link *next; 結(jié)構(gòu)體類型

24、并不分配存儲(chǔ)空間，這樣的結(jié)構(gòu)可用動(dòng)態(tài)申請(qǐng)存儲(chǔ)空間函數(shù)來分配內(nèi)存，用malloc()函數(shù)來申請(qǐng)。若head是結(jié)構(gòu)體變量，則： head=(struct link *)malloc(sizeof(struct link);即可申請(qǐng)一個(gè)存放以上定義的結(jié)構(gòu)體變量或數(shù)組元素。若通過循環(huán)語(yǔ)句控制，執(zhí)行多次，就可為線性鏈表中的所有元素申請(qǐng)到存儲(chǔ)空間，形成線性鏈表。2.2 鏈表 3.線性鏈表的基本操作 線性鏈表的操作有建立一個(gè)線性鏈表；統(tǒng)計(jì)線性鏈表中的元素個(gè)數(shù)；在線性鏈表中查找某個(gè)元素；把兩個(gè)線性鏈表串接成一個(gè)；在線性鏈表中插入一個(gè)元素；在線性鏈表中刪除某個(gè)元素。 線性鏈表的建立有兩種方法： 第1種方法是簡(jiǎn)單

25、地將把一個(gè)新加入的元素添加到鏈表的起點(diǎn)或終點(diǎn)，即堆棧式鏈表與隊(duì)列式鏈表。 第2 種方法是把新加入的元素添加到它應(yīng)該占有的位置，例如按升序或降序排列，插入新項(xiàng)時(shí)保持鏈表的有序性。這種方法比前一種方法要復(fù)雜，涉及到比較與插入（改變指針的指向）。2.2 鏈表 堆棧式鏈表的建立 建立過程的示意圖(程序?yàn)椋簊tack_link.cpp).數(shù)1.數(shù)2數(shù)2數(shù)n-1數(shù)nphead.數(shù)1.phead.p數(shù)1.head.p.head數(shù)1p-next=head;head=p;2.2 鏈表 隊(duì)列式鏈表的建立(自己編寫滿足下列示意的程序) 建立過程的示意圖(程序?yàn)椋簈ueue_link.cpp).數(shù)1.數(shù)1數(shù)n-1數(shù)2

26、數(shù)1phead.數(shù)1.phead.p數(shù)2.head.p.head數(shù)ntail-next=p;tail=p;.tail.tail.tail2.2 鏈表 線性鏈表的計(jì)數(shù)與遍歷 線性鏈表的計(jì)數(shù)是統(tǒng)計(jì)鏈表中元素的個(gè)數(shù)?？梢杂眠f歸方式調(diào)用函數(shù)來求，也可用普通調(diào)用方式來求。 求結(jié)點(diǎn)個(gè)數(shù)的方法是：判斷頭結(jié)點(diǎn)指針是否為空，若不空，個(gè)數(shù)加1，把頭結(jié)點(diǎn)指針下移一個(gè)結(jié)點(diǎn)；若空返回退出求解。 函數(shù)名：int count_link( struct link *head) 遍歷鏈表是訪問一次僅訪問鏈表中結(jié)點(diǎn)一次的操作，輸出鏈表中的元素，可以用遞歸方式調(diào)用函數(shù)來完成，也可用普通調(diào)用方式來完成。 遍歷鏈表的方法：判斷頭結(jié)點(diǎn)指

27、針是否為空，若不空，輸出結(jié)點(diǎn)中的值，指針下移一個(gè)結(jié)點(diǎn)；若為空，退出遍歷。 函數(shù)名：printf_link(struct link *head) 以上函數(shù)與建立鏈表程序合在一起才能使用。2.2 鏈表 線性鏈表的串接 線性鏈表的串接是把兩個(gè)鏈表合并成一個(gè)鏈表，形成一個(gè)更大的鏈表。若有鏈表a、b，合并后把b的頭結(jié)點(diǎn)鏈在a的尾結(jié)點(diǎn)。 串接方法是：從頭結(jié)點(diǎn)開始，判斷a-next是否為空，不為空，繼續(xù)向后移動(dòng)指針；若為空，執(zhí)行：a-next=b;完成鏈接。 串接的函數(shù)為：concate_link(struct link *a, struct link *b); 判斷a-next是否為空,可要用普通函數(shù)調(diào)用

28、，也可用遞歸方式調(diào)用函數(shù),以下是遞歸調(diào)用的函數(shù)。 concate_link(struct link *a, struct link *b) if(a-next=NULL) a-next=b;return; else concate_link(a-next,b); 完整程序：conc_link.cpp2.2 鏈表 線性鏈表插入： 在線性鏈表插入一個(gè)結(jié)點(diǎn)的運(yùn)算有三種不同的情況，即將一個(gè)新的結(jié)點(diǎn)插入到線性鏈表中成為新的起始結(jié)點(diǎn)；將一個(gè)新的結(jié)點(diǎn)插入到線性鏈表中任意兩個(gè)結(jié)點(diǎn)之間；將一個(gè)新的結(jié)點(diǎn)插入到線性鏈表中成為新的終點(diǎn)； 插入到線性鏈表的頭： struct link *insert_link1(str

29、uct link * head, struct link * q) q-next=head;head=q;return head; 插入到線性鏈表任意兩個(gè)結(jié)點(diǎn)之間： void insert_link2(struct link *p1, struct link *p2, struct link * q) p1-next=q;q-next=p2; 插入到線性鏈表的尾： void insert_link3(struct link *head, struct link * q) struct link *p1;p1=head; while(p1-next !=NULL)p1=p1-next; p1-n

30、ext=q;q-next=NULL; 程序?yàn)椋篿nsert_link.cppn-121.p1.n.p2head345.qx2.2 鏈表 線性鏈表的刪除： 刪除線性鏈表的中指定的結(jié)點(diǎn)包含兩層含義：一是把指定的結(jié)點(diǎn)從鏈表中刪除，使其變?yōu)闊o用單元；另一是將無用單元釋放，可被其它變量占用,用free()函數(shù)釋放存儲(chǔ)單元。 鏈表中的刪除不需要大量移動(dòng)元素，只需改變指針指向即可刪除，但不能刪除當(dāng)前指針?biāo)傅慕Y(jié)點(diǎn)，如果要?jiǎng)h除當(dāng)前指針?biāo)傅慕Y(jié)點(diǎn)，必需用輔助指針指向當(dāng)前結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)，刪除指定結(jié)點(diǎn)時(shí)，可用p-next-d作為判斷。 刪除當(dāng)前所指結(jié)點(diǎn)的后面結(jié)點(diǎn)，只需執(zhí)行指針賦值語(yǔ)句即可。 q=p-next; p

31、-next =p-next-next; free(q); n-121.p.nhead3452.2 鏈表 刪除線性鏈表的中指定的結(jié)點(diǎn)，首先要查找該結(jié)點(diǎn)的位置，找到后再執(zhí)行刪除操作。 查找指定結(jié)點(diǎn)的方式，不能用p-d來判斷，若用它來判斷，只能找到當(dāng)前指針?biāo)傅慕Y(jié)點(diǎn)，此時(shí)執(zhí)行刪除操作就不能完成，應(yīng)用p-next-d來判斷，才能確定刪除結(jié)點(diǎn)前面的結(jié)點(diǎn)。 刪除時(shí)應(yīng)注意刪除的是頭結(jié)點(diǎn)，此時(shí)執(zhí)行的指針賦值語(yǔ)句是： q=head;head=head-next;free(q);return head;示意圖： 若指定結(jié)點(diǎn)不是頭結(jié)點(diǎn)，用 p-next-d來找結(jié)點(diǎn)，執(zhí)行： q=p-next;p-next=p-nex

32、t-next;free(q); 程序?yàn)椋篸ele_link.cppn-121.p.nhead3452.2 鏈表 建立有序鏈表 有序鏈表是從鏈表的頭開始遍歷鏈表時(shí)，輸出結(jié)點(diǎn)的值是從小到大或從大到小的形式?？梢越⒑笾匦屡判颍@屬于排序內(nèi)容。此時(shí)的要求是在建立時(shí)鏈表就是有序的。 建立有序鏈表的方法是：首先查找輸入的結(jié)點(diǎn)值所在鏈表中插入的位置，然后再插入結(jié)點(diǎn)，在建立鏈表的函數(shù)中需調(diào)用查找函數(shù)和插入函數(shù)。 建立有序鏈表的函數(shù)是： struct link *createsort(); 查找函數(shù)是： struct link *findlink(struct link *,char ); 插入函數(shù)是： st

33、ruct link *insertlink(struct link *, struct link *, struct link *) 完整的程序?yàn)椋簊ort_link.cpp 作業(yè):改為建立從大到小的鏈表2.2 鏈表 作業(yè): 1.利用前面建立棧式鏈表的程序及對(duì)鏈表插入、刪除等函數(shù)，完成真正棧的操作，即插入在棧頂，刪除也在棧頂。 2.利用前面建立隊(duì)列式鏈表的程序及對(duì)鏈表插入、刪除等函數(shù)，完成真正隊(duì)列的操作，即插入在隊(duì)尾，刪除在隊(duì)首。 3.雙向鏈表的插入與刪除。2.3 雙向鏈表 雙向鏈表的基本概念 雙向鏈表與前面講的線性鏈表具有相類似的構(gòu)造形式，只是雙向鏈表的每一個(gè)結(jié)點(diǎn)除了數(shù)據(jù)域外，還包含兩個(gè)指向

34、其它結(jié)點(diǎn)的指針，一個(gè)指向該結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)，即前驅(qū)結(jié)點(diǎn)；另一個(gè)指向該結(jié)點(diǎn)的后一個(gè)結(jié)點(diǎn)，即后繼結(jié)點(diǎn)，用rlink表示指向后繼的指針，用llink表示指前驅(qū)繼的指針。頭結(jié)點(diǎn)包含兩個(gè)指針，一個(gè)指向頭結(jié)點(diǎn)，另一個(gè)指向尾結(jié)點(diǎn)。 雙向鏈表的定義： struct dlink char d; struct dlink *llink; struct dlink *rlink; 2.3 雙向鏈表 雙向鏈表的示意圖： 第一種形式：頭結(jié)點(diǎn)包含兩個(gè)指針的雙向鏈表 。 第二種形式：加入表頭結(jié)點(diǎn)的雙向鏈表 雙向鏈表的優(yōu)點(diǎn)為：能夠正反兩個(gè)方向任意查找；鏈表中某一個(gè)鏈被破壞，可從另一方向讀這個(gè)鏈，使鏈表重新恢復(fù)。 headre

35、arllink d rlinkn2.3 雙向鏈表 雙向鏈表的建立與遍歷 頭結(jié)點(diǎn)包含兩個(gè)指針的雙向鏈表的建立，把每一個(gè)新結(jié)點(diǎn)加入到雙向鏈表末尾。(隊(duì)列 形式) 函數(shù)為：void createdlink(struct dlink *) (建立示意圖) headrearAprear ABpvoid createdlink(struct dlink *p)if(rear=NULL) head=p; rear=p; p-llink=NULL; p-rlink=NULL; else rear-rlink=p; p-rlink=NULL; p-llink=rear; rear=p; 2.3 雙向鏈表 雙向鏈

36、表的遍歷可以通過頭指針head,也可通過尾指針rear,用head遍歷時(shí)應(yīng)使用指針rlink ，用rear遍歷時(shí)應(yīng)使用指針llink 。 void outdrlink(struct dlink *p) if(p=NULL)printf(NULLn); else printf(%c-,p-d); outdrlink(p-llink); void outdllink(struct dlink *p) if(p=NULL) printf(NULLn); else printf(%c-,p-d); outdllink(p-rlink); 2.3 雙向鏈表 雙向鏈表的刪除要改變兩個(gè)方向指針的指向才能實(shí)現(xiàn)

37、。若刪除p所指結(jié)點(diǎn)，示意圖如下：headrear ApBCDheadrear ApBCDp-llink-rlink=p-rlinkp-rlink-llinkp-llinkp-rlink-llink=p-llinkp-llink-rlink2.3 雙向鏈表 雙向鏈表的插入要改變兩個(gè)方向指針的指向才能實(shí)現(xiàn)。若在結(jié)點(diǎn)p后插入結(jié)點(diǎn)q，示意圖如下：具體程序自已編寫。headrear ApBCDheadrear ApBCD1、q-llink=p;2、q-rlink=p-rlink;p-rlink-llink3、p-rlink-llink=q;4、p-rlink=qp-rlinkxqxq2.4 動(dòng)態(tài)存儲(chǔ)管理

38、 程序運(yùn)行是在內(nèi)存中進(jìn)行的，如何管理好內(nèi)存，使程序順利地運(yùn)行，特別是多任務(wù)，即多個(gè)程序同時(shí)運(yùn)行時(shí)，內(nèi)存的管理問題更加突出。 動(dòng)態(tài)存儲(chǔ)管理的基本問題是：系統(tǒng)如何響應(yīng)用戶提出的“請(qǐng)求”分配內(nèi)存，又如何收回那些用戶不在使用而“釋放”的內(nèi)存？ 類似于操作系統(tǒng)中的內(nèi)存管理，DOS是固定分配。Windows系統(tǒng)是動(dòng)態(tài)分配，即將所有空閑區(qū)連接成一個(gè)較大的區(qū)域，等待用戶申請(qǐng)。 具體分配方法有：最先適應(yīng)；最佳適應(yīng)、最差適應(yīng)。 申請(qǐng)和收回都是通過指針來實(shí)現(xiàn)。第三章 排序3.1 基本概念3.2 插入排序3.3 選擇排序3.4 交換排序3.5 各種排序方法比較3.1 基本概念 排序碼與排序: 排序中通常將結(jié)點(diǎn)稱為記錄

39、,記錄的集合稱為文件,這里的文件可理解為線性表等。 排序碼是指結(jié)點(diǎn)中的一個(gè)字段，該字段是排序的依據(jù)。排序碼可以是關(guān)鍵碼，也可不是。排序碼的類型可以是C語(yǔ)言中的數(shù)據(jù)類型，整型、實(shí)型、字符型是排序中的常見類型。 按排序碼排列的順序分類，排序有兩種，一種是按照排序碼的遞增順序排序稱為升序；一種是按照排序碼遞減的順序排序稱為降序，所講內(nèi)容都是升序排列。 排序的方法： 排序方法有5 大類，即插入排序、選擇排序、交換排序、分配排序和歸并排序。每一大類中又分若干種，下面介紹各大類中各種排序方法：3.1 基本概念 插入排序：直接插入、二分插入、表插入、Shell排序。 選擇排序：直接選擇、樹型選擇、堆排序。

40、交換排序：起泡排序、快速排序。 分配排序：基數(shù)排序 歸并排序： 排序算法評(píng)價(jià)： 評(píng)價(jià)排序算法主要有以下兩個(gè)方面： 一是算法執(zhí)行所需要的時(shí)間：以時(shí)間開銷作為算法好壞的最重要的標(biāo)志，取決于算法中執(zhí)行比較次數(shù)和移動(dòng)次數(shù)。應(yīng)考慮最壞的情況，即排序之前數(shù)據(jù)已是升序排列或降序排列。 二是算法執(zhí)行時(shí)所需的附加空間：即交換時(shí)所用的空間。 以上分別稱為時(shí)間復(fù)雜度和類似問題復(fù)雜度。3.2 插入排序 插入排序的基本方法是：每一步將待排序的記錄按其排序碼值的大小，插入到已經(jīng)排好序的序列的適當(dāng)位置，直到全部插入為止。插入時(shí)所用的基本運(yùn)算是比較和移動(dòng)。 一、直接插入排序（insert_sort.cpp） 1.直接插入排序

41、的過程如下：假設(shè)R1,R2,Rn-1已排好序，將Rn插入到它的合適位置，首先要找位置，然后向后移動(dòng)元素，執(zhí)行插入。 插入排序示意圖： 初始序列：7 2 5 1 9 6 8 3 第一次插入：2 7 5 1 9 6 8 3 第二次插入：2 5 7 1 9 6 8 3 直到最后一個(gè)數(shù)插入。3.2 插入排序 2.直接插入排序的算法： 通過上面實(shí)例，已說明了直接插入排序的算法，下面用C程序來描述(假設(shè)排序的數(shù)據(jù)為10個(gè))。 void insertsort( ) int i,j,k,x; for(i=1;i10;i+) x=ai;k=i;/* 該元素可能是最大的*/ for(j=0;ji-1;j+) if

42、(x=k;j-) /*向后移動(dòng)元素*/ aj+1=aj; ak=x; 3.2 插入排序 3.直接插入排序的算法復(fù)雜度： 直接插入排序的算法中的基本操作主要由兩種，一種是比較操作，另一種是移動(dòng)操作，兩者合起來的次數(shù)為直接插入排序的算法的時(shí)間復(fù)雜度，比較次數(shù)多，移動(dòng)次數(shù)就少，比較次數(shù)少，移動(dòng)次數(shù)就多。 考慮比較次數(shù)，需要從最好情況和最壞情況考慮，并計(jì)算出平均比較次數(shù)及移動(dòng)次數(shù)。 最好的情況，即所提供的排序碼是逆序的，如： n、n-1 、3、2、1。 每次插入的關(guān)鍵碼只需比較1次，總次為 n-1次，但移動(dòng)的次數(shù)的總和為1+2+3+n-1= 。 最壞的情況，即所提供的排序碼就是有序的，如： 1、2 、

43、n-1、n。 每次插入的關(guān)鍵碼需比較次數(shù)為：1次、2次、n-1次，總次數(shù)為： 1+2+3+n-1= 但不移動(dòng)元素。 總體來看，時(shí)間復(fù)雜度為O(n2)。)1(21nn)1(21nn3.2 插入排序 二、二分法插入排序 1.二分法插入排序的基本概念：假設(shè)R1,R2,Rn-1已排好序，將Rn插入到它的合適位置，首先要找位置，找位置的方法是用二分法來找的，加速了查找速度，找到位置后，從最后到找到位置開始向后移動(dòng)元素，執(zhí)行插入操作。 二分法插入排序示意圖： 有序序列： 1 2 5 6 7 8 9 現(xiàn)有數(shù)字4要插入； 此時(shí)下界為 0，上界為6，中間下標(biāo)為3。而4a1則：下界變?yōu)?，上界不變還為2，中間下標(biāo)

44、為1。而4a1則：下界變?yōu)?，上界不變還為2，中間下標(biāo)為2。而4a2則：下界不變還為2，上界變?yōu)?，此時(shí)下界大于上界，找到下標(biāo)2為插入位置： 序列變?yōu)椋? 2 4 5 6 7 8 9 直到最后一個(gè)數(shù)插入。3.2 插入排序 2.二分法插入排序的算法： 通過上面實(shí)例，已說明了二分法插入排序的算法，下面用C程序來描述(假設(shè)排序的數(shù)據(jù)為10個(gè))。void tinsert( ) int i,j,m,n,k,x; /*M元素個(gè)數(shù)，m下界，n上界，k中間下標(biāo)*/ for(i=1;iM;i+) x=ai; m=0;n=i-1; while(m=n) k=(m+n)/2; if(x=k;j-) aj+1=aj;

45、 ak=x; 3.2 插入排序 3.二分法插入排序的算法復(fù)雜度： 二分法插入排序的算法中的基本操作主要由兩種，一種是比較操作，另一種是移動(dòng)操作，兩者合起來的次數(shù)為二分法插入排序的算法的時(shí)間復(fù)雜度。 考慮比較次數(shù)，二方法插入排序的比較次數(shù)與排序碼的初始狀態(tài)無關(guān)，只依賴于參加排序數(shù)的個(gè)數(shù)n。即比較的次數(shù)為log2n。 數(shù)的個(gè)數(shù) 比較的次數(shù) n=1 0 n=2 1 n=3,4 2 總的比較次為0+1+2+2+k+k+k=n log2n 20個(gè) 21 個(gè) 2k-1個(gè) 最壞情況，當(dāng)初始序列是從小到大排列時(shí)，移動(dòng)次數(shù)與直接插入排序相同，總體來看，時(shí)間復(fù)雜度為O(n2)。3.2 插入排序 三、Shell排序

46、 1. Shell排序的過程如下(n代表參加排序數(shù)據(jù)的個(gè)數(shù)) 第1步，取整數(shù)d1n，把全部參加排序的數(shù)據(jù)分為d1個(gè)組，所有相距為d1的數(shù)據(jù)放在一個(gè)組中，在各組內(nèi)進(jìn)行排序。 第2步，取整數(shù)d2=1) printf(%d:,k); for(i=k;i=0&xaj) aj+k=aj; j=j-k; aj+k=x; k=k/2; if(k!=0&k%2=0) k+; /*確保k取奇數(shù)*/ Shell排序的算法復(fù)雜度為O(n1.3),在其它書中有介紹，這里不作推導(dǎo)。3.3 選擇排序 選擇排序的基本思想是：每步從待排序的數(shù)據(jù)中選出排序碼最小的，順序存放在已排序的數(shù)據(jù)后面，直到全部排完。(

47、choice_sort.cpp) 一、直接選擇排序： 1.直接選擇排序的方法如下，首先在所有排序的數(shù)據(jù)中選出排序碼最小的數(shù)據(jù)與第1個(gè)數(shù)據(jù)交換，然后在其余的數(shù)據(jù)中選出排序碼最小的數(shù)據(jù)與第2個(gè)數(shù)據(jù)交換，依次類推。直到所有的數(shù)據(jù)排完為止。 直接選擇排序算法的排序演示： 原始序列： 41 67 34 0 69 24 78 58 62 64 第1次 0 67 34 41 69 24 78 58 62 64 第2次 0 24 34 41 69 67 78 58 62 64 第3次 0 24 34 41 69 67 78 58 62 64 第4次 0 24 34 41 69 67 78 58 62 64 第

48、5次 0 24 34 41 58 67 78 69 62 64 第6次 0 24 34 41 58 62 78 69 67 64 第7次 0 24 34 41 58 62 64 69 67 78 第8次 0 24 34 41 58 62 64 67 69 78 第9次 0 24 34 41 58 62 64 67 69 78 從上面序列變化可看出，每一次都有一個(gè)數(shù)放入合適的位置。 3.3 選擇排序 2.直接選擇排序的算法： 通過以上演示已說明了直接選擇排序的算法，下面用C程序來描述。 void dchoice( ) int i,j,k,t; for(i=0;iM-1;i+) k=i; for(

49、j=i+1;jaj) k=j; if(k!=i) t=ai;ai=ak;ak=t; 3.3 選擇排序 3.直接選擇排序算法的時(shí)間復(fù)雜度： 完成直接選擇排序的算法的操作主要是比較和交換元素的值，可用比較次數(shù)及移動(dòng)的次之和表示。 比較的次數(shù)與參加排序數(shù)據(jù)的原始排列無關(guān)，總的比較次最壞的為(n-1)+(n-2)+ +2+1= 交換次數(shù)與排序碼的初始順序有關(guān)，當(dāng)初始數(shù)據(jù)已是一升序排列的序列時(shí)，交換次數(shù)為0，但在最壞的情況下，即初始數(shù)據(jù)是一個(gè)降序序列時(shí)，每次都要交換，總的移動(dòng)次數(shù)為三倍的(n-1)。 總體來看，時(shí)間復(fù)雜度為O(n2)。 )1(21nn3.3 選擇排序 二、樹型選擇排序： 1.樹型選擇排序

50、的方法如下： 第1步 把n個(gè)排序碼兩兩進(jìn)行比較，取出n/2個(gè)較小的排序碼作為第一次的比較結(jié)果保存下來； 第2步 再把n/2個(gè)較小的排序碼兩兩進(jìn)行比較，取出n/4個(gè)較小的排序碼作為第二次的比較結(jié)果保存下來； 第3步 反復(fù)進(jìn)行上述操作一直到比較出最小的排序碼為止。 將最小的排序碼所在的位置上放一個(gè)最大的數(shù)（比所有的排序碼都大），接著再重復(fù)1 、2、 3步，如此進(jìn)行下去，直到所有的排序碼排完為止，但注意每次要保存比較得出最小的排序碼。 3.3 選擇排序 2.樹型選擇排序的算法的演示： 例如有8個(gè)排序碼7，2，5，1，9，6，8，3。 第一次比較找出的最小數(shù)： 第二次比較找出的最小數(shù)： 直到把倒數(shù)第二

51、個(gè)數(shù)8找出為止。725196832163113725968325632233.3 選擇排序 3.樹型選擇排序算法的時(shí)間復(fù)雜度： 這種排序方法雖然速度有很大的提高，但排序結(jié)果要另開辟存儲(chǔ)單元，即在比較過程中為了保存前面的比較結(jié)果需用另外的存儲(chǔ)單元。 比較次數(shù)：第一次需要(n-1)次，以后每次的比較次不超過log2n總體來看?？偟谋容^次為nlog2n，結(jié)點(diǎn)移動(dòng)的次數(shù)不超過比較次數(shù)，總的時(shí)間復(fù)雜度為O(nlog2n )。 樹型選擇排序程序編寫以后講。 三、堆排序 使用完全二叉樹結(jié)構(gòu)來完成，講到完全二叉樹結(jié)構(gòu)時(shí)完成。3.4 交換排序 交換排序的基本方法是：兩兩比較待排序的排序碼，并交換不滿足順序要求的

52、那些偶對(duì)，直到滿足條件為止。Shift_sort.cpp 一、起泡排序 1.起泡排序的基本概念 起泡排序又稱冒泡排序，它的排序方法是： 第1步 先比較k0和k1，若k0k1，則交換k0和k1 ，否則不交換。繼續(xù)對(duì)k1和k2重復(fù)上述過程，直到處理完畢kn-1和kn 。這時(shí)最大的排序碼就交換到了最終的位置，稱第1次起泡。共執(zhí)行了n-1次比較。 第2步 與第1步類似，但只從(k0,k1)比較 (kn-2,kn-1) ,共執(zhí)行n-2次比較，這時(shí)次大的排序碼交換到了n-1的位置，稱為第2次起泡。 第3步 共作n-1次起泡，完成整個(gè)排序過程。下面是5個(gè)數(shù)的起泡排序演示： 原始數(shù)據(jù)： 41 67 34 0

53、69 第1次起泡： 41 34 0 67 69 第2次起泡： 34 0 41 67 69 第3次起泡： 0 34 41 67 69 第4次起泡： 0 34 41 67 69 3.4 交換排序 2.起泡排序的算法的C程序 介紹了起泡排序的算法及演示后，下面介紹起泡排序的C語(yǔ)言程序：void bubble() int i,j,t; for(i=0;iM-1;i+) for(j=0;jaj+1) t=aj;aj=aj+1;aj+1=t; M參加排序數(shù)據(jù)的個(gè)數(shù)，第一個(gè)循環(huán)控制幾次起泡。 3.4 交換排序 3.起泡排序算法的時(shí)間復(fù)雜度 起泡排序算法中的操作主要有兩種，一種是比較，另一種是交換。 最好的情

54、況是當(dāng)排序的排序碼是從小到大排列的，此時(shí)只比較而不交換，比較的次數(shù)為算法的時(shí)間復(fù)雜度，總的比較次為：n-1+n-2+1= 最壞的情況是當(dāng)排序的排序碼是從大到小排列的，此時(shí)既要比較也要交換。 比較次數(shù)為： n-1+n-2+1= 移動(dòng)次為： 3( n-1+n-2+1)= 通過分析，總體來看，起泡排序算法的時(shí)間復(fù)雜度為O(n2)1(21nn)1(23nn)1(21nn3.4 交換排序 二 、快速排序 1.快速排序的基本概念 快速排序又稱分區(qū)交換排序，它的排序方法是： 第1步 在待排序的排序碼中任選一個(gè)數(shù)據(jù)，以該數(shù)據(jù)為標(biāo)準(zhǔn)，將所有的記錄分為2組，第1組中的所有排序碼都小于任選的數(shù)據(jù)，第2組中的所有排序

55、碼都大于任選的數(shù)據(jù)，并把所選排序碼排在這兩組數(shù)中間。 第2步 對(duì)所分的兩組數(shù)據(jù)與第1步一樣作相同的處理。 第3步 直到所有的排序碼都 排到相應(yīng)的位置為止。一般情況都是選第1個(gè)數(shù)作為任選數(shù)據(jù)。下面是10個(gè)數(shù)的快速排序演示： 原始數(shù)據(jù)： 41 67 34 0 69 24 78 58 62 64 第1次比較交換: 24 0 34 41 69 67 78 58 62 64 第2次比較交換: 0 24 34 41 69 67 78 58 62 64 第3次比較交換: 0 24 34 41 64 67 62 58 69 78 第4次比較交換: 0 24 34 41 58 62 64 67 69 78 第5

56、次比較交換: 0 24 34 41 58 62 64 67 69 78 3.4 交換排序 2.快速排序的算法的C程序 介紹了快速排序的算法及演示后，下面介紹快速排序的C語(yǔ)言程序：void quick(int *a,int l,int h) int i,j,x; x=al; i=l;j=h; while(i=x&ji) j-; if(ij) ai=aj;i+; while (aii) i+; if(ij)aj=ai;j-; ai=x; if(li-1) quick(a,l,i-1); if(j+1h) return -1; else if(x=am) return m; else if(

57、xam) return mid_find(a,m+1,h,x); else return mid_find(a,l,m-1,x); 該函數(shù)為遞歸調(diào)用函數(shù)，可改為非遞歸調(diào)用的函數(shù),留為作業(yè)。4.3 二分檢索 3.二分檢索算法的復(fù)雜度 用二分檢索，每經(jīng)過一次比較就會(huì)把檢索的范圍縮小一半，比較的次數(shù)約為log2n的數(shù)量級(jí)。 比較次數(shù) 可能涉及的結(jié)點(diǎn)數(shù) 1 1=20 2 2=21 3 4=22 x 2x-1 由以上可知：n= 20 + 21 + 2x-1 = 2x-1； x=log2(n+1)。 4.二分檢索的優(yōu)缺點(diǎn)： 優(yōu)點(diǎn)：檢索速度快，以線性表排序?yàn)榇鷥r(jià)；缺點(diǎn)：用于順序的結(jié)構(gòu)中，插入、刪除頻繁不方便

58、。4.4 分塊檢索 1. 分塊檢索的基本思想 第1步：把線性表分成若干塊，每一塊中的結(jié)點(diǎn)存放是任意的，但塊與塊之間是按關(guān)鍵碼值從小到大排列的，即： 第1塊任意關(guān)鍵碼小于第2塊任意關(guān)鍵碼； 第2塊任意關(guān)鍵碼小于第3塊任意關(guān)鍵碼； 第2步：建立索引表，存放每塊最大關(guān)鍵碼值，及分塊的起始地址。 第3步：檢索時(shí)，首先用待查關(guān)鍵碼在索引中表中用順序或二分法查找，確定結(jié)點(diǎn)在哪一塊，然后在塊內(nèi)順序檢索到結(jié)果。 在分塊時(shí)，每塊的個(gè)數(shù)最好接近總數(shù)的平方根。如有15個(gè)數(shù)，分三塊，每塊有5個(gè)元素。4.4 分塊檢索 2. 分塊檢索的圖示 如有15個(gè)數(shù)，分為三塊，每塊有5個(gè)元素。形如如下的圖示： (作業(yè)：編寫分塊檢索程

59、序,分塊查找.cpp)keylinkA022A144A266keylink2211181512keylink4855616657keylink3032442642B1B2B34.4 分塊檢索 3. 分塊檢索的速度 分塊檢索的速度比順序檢索的速度快，但速度不如二分檢索，如果分的塊較多，且塊內(nèi)結(jié)點(diǎn)多，對(duì)查找所在塊的位置可用二分查找。分塊檢索的優(yōu)點(diǎn)是插入和刪除結(jié)點(diǎn)容易，在塊內(nèi)任意存放，不需移動(dòng)，速度快。代價(jià)是增加輔助數(shù)組A的存儲(chǔ)空間，初始線性分塊的操作運(yùn)算較復(fù)雜，經(jīng)過多次插入與刪除，各塊中結(jié)點(diǎn)分布不均勻時(shí)，檢索速度下降。 各種檢索方法的比較：n為表的長(zhǎng)度 順序： （n+1） 二分法： nlog2n

60、分塊： n第5章 樹結(jié)構(gòu)5.1 樹結(jié)構(gòu)的概念5.2 周游樹結(jié)構(gòu)5.3 樹結(jié)構(gòu)的存儲(chǔ)5.4 樹應(yīng)用舉例 樹結(jié)構(gòu)的概念 1.樹的邏輯結(jié)構(gòu)的描述 樹是包含n個(gè)結(jié)點(diǎn)的有窮集合K(n0)，且在K上定義了一個(gè)關(guān)系N，關(guān)系N滿足以下條件： 有且有一個(gè)結(jié)點(diǎn)k0K，它對(duì)于關(guān)系N來說沒有前驅(qū)，結(jié)點(diǎn)k0稱為樹的根。 除結(jié)點(diǎn)k0外，K中的每個(gè)結(jié)點(diǎn)對(duì)于關(guān)系N來說都有且僅有一個(gè)前驅(qū)。 除結(jié)點(diǎn)k0外的任何結(jié)點(diǎn)kK,都存在一個(gè)結(jié)點(diǎn)序列k0， k1 ， ks，使得k0是樹根, ks為結(jié)點(diǎn)k,有序?qū)(1is),這樣的一個(gè)結(jié)點(diǎn)序列稱為根到結(jié)點(diǎn)k的一條路徑。 樹結(jié)構(gòu)在客觀世界大量存在。如：家族的血統(tǒng)關(guān)系；國(guó)家、省、地、縣的關(guān)系；書、章、節(jié)、小節(jié)的關(guān)系。 樹結(jié)構(gòu)