國家計(jì)算機(jī)二級(jí)考試第一章

1二級(jí)公共基礎(chǔ)知識(shí)第一章數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)2內(nèi)容提要算法:算法的基本概念、算法復(fù)雜度數(shù)據(jù)結(jié)構(gòu)的基本概念：什么是數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)結(jié)構(gòu)的圖形表示、線性結(jié)構(gòu)與非線性結(jié)構(gòu)線性表及其順序存儲(chǔ)結(jié)構(gòu)：線性表的基本概念、順序存儲(chǔ)結(jié)構(gòu)、插入運(yùn)算、刪除運(yùn)算棧和隊(duì)列：棧及其基本運(yùn)算、隊(duì)列及其基本運(yùn)算線性鏈表：基本概念、基本運(yùn)算、循環(huán)鏈表及其基本運(yùn)算樹與二叉樹：樹的基本概念、二叉樹及其基本性質(zhì)、二叉樹的存儲(chǔ)結(jié)構(gòu)、二叉樹的遍歷查找技術(shù)：順序查找、二分法查找排序技術(shù)：交換類排序法、插入類排序法、選擇類排序法31.1算法41.1.1算法的基本概念算法是解題方案的準(zhǔn)確而完整的描述，它不等于程序，也不等計(jì)算方法。1．算法的基本特征可行性(effectiveness)確定性(definiteness)有窮性(finiteness)擁有足夠的情報(bào)2．算法的基本要素算法中對數(shù)據(jù)的運(yùn)算和操作算術(shù)運(yùn)算:包括加、減、乘、除等）邏輯運(yùn)算:包括“與”、“或”、“非”等運(yùn)算）關(guān)系運(yùn)算:包括“大于”、“小于”、“等于”、“不等于”等）數(shù)據(jù)傳輸:包括賦值、輸入、輸出等操作算法的控制結(jié)構(gòu):順序、選擇、循環(huán)51.1.1算法的基本概念3．算法設(shè)計(jì)的基本方法列舉法歸納法遞推遞歸減半遞推技術(shù)回溯法61.1.1算法的基本概念4．算法設(shè)計(jì)的設(shè)計(jì)要求正確性可讀性健壯性效率和低存儲(chǔ)量需求71.1.2算法復(fù)雜度算法復(fù)雜度：時(shí)間復(fù)雜度、空間復(fù)雜度1．算法的時(shí)間復(fù)雜度執(zhí)行算法所需要的計(jì)算工作量與下列因素有關(guān)：書寫算法的程序設(shè)計(jì)語言編譯產(chǎn)生的機(jī)器語言，代碼質(zhì)量機(jī)器執(zhí)行指令的速度問題的規(guī)模81.1.2算法復(fù)雜度問題的規(guī)模函數(shù)算法的工作量=f(n)算法中基本操作重復(fù)執(zhí)行的頻率T(n)，是問題規(guī)模n的某個(gè)函數(shù)f(n)，記作：T(n)=O(f(n))記號(hào)“O”讀作“大O”。表示隨問題規(guī)模n的增加，算法執(zhí)行時(shí)間的增長率和f(n)相應(yīng)增加。常見算法復(fù)雜度：O(1)：常數(shù)階O(n)：作線性階O(n2)：平方階O(n3)：立方階O(logn)：對數(shù)階O(2n)：指數(shù)階91.1.2算法復(fù)雜度n×n矩陣相乘算法：時(shí)間復(fù)雜度為O(n3)。101.1.2算法復(fù)雜度分析算法的工作量兩種方法：平均性態(tài)最壞情況復(fù)雜性111.1.2算法復(fù)雜度2．算法的空間復(fù)雜度算法執(zhí)行過程中所需的最大存儲(chǔ)空間存儲(chǔ)量包括以下三部分算法程序所占的空間輸入的初始數(shù)據(jù)所占的存儲(chǔ)空間算法執(zhí)行過程中所要的額外空間算法空間復(fù)雜度可定義為：S(n)=O(f(n))原地工作(inplace)的算法：記作O(1)壓縮存儲(chǔ)技術(shù)121.2數(shù)據(jù)結(jié)構(gòu)的基本概念131.2.1什么是數(shù)據(jù)結(jié)構(gòu)1．?dāng)?shù)據(jù)結(jié)構(gòu)研究的主要內(nèi)容數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)對各種數(shù)據(jù)結(jié)構(gòu)進(jìn)行的運(yùn)算2．研究數(shù)據(jù)結(jié)構(gòu)目的提高數(shù)據(jù)處理的速度盡量節(jié)省在數(shù)據(jù)處理過程中所占用的計(jì)算機(jī)存儲(chǔ)空間141.2.1什么是數(shù)據(jù)結(jié)構(gòu)1．?dāng)?shù)據(jù)結(jié)構(gòu)研究的主要內(nèi)容數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)對各種數(shù)據(jù)結(jié)構(gòu)進(jìn)行的運(yùn)算2．研究數(shù)據(jù)結(jié)構(gòu)目的提高數(shù)據(jù)處理的速度盡量節(jié)省在數(shù)據(jù)處理過程中所占用的計(jì)算機(jī)存儲(chǔ)空間151.2.1什么是數(shù)據(jù)結(jié)構(gòu)1．?dāng)?shù)據(jù)的邏輯結(jié)構(gòu)2、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)3、數(shù)據(jù)的運(yùn)算：檢索、排序、插入、刪除、修改等。A．線性結(jié)構(gòu)B．非線性結(jié)構(gòu)A順序存儲(chǔ)B鏈?zhǔn)酱鎯?chǔ)線性表?xiàng)ｊ?duì)樹形結(jié)構(gòu)圖形結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的三個(gè)方面161.2.1什么是數(shù)據(jù)結(jié)構(gòu)3．?dāng)?shù)據(jù)結(jié)構(gòu)的定義相互有關(guān)聯(lián)的數(shù)據(jù)元素的集合數(shù)據(jù)元素之間的關(guān)系可以用前后件關(guān)系來描述一個(gè)數(shù)據(jù)結(jié)構(gòu)應(yīng)包含以下兩方面信息：表示數(shù)據(jù)元素的信息表示各數(shù)據(jù)元素之間的前后件關(guān)系171.2.1什么是數(shù)據(jù)結(jié)構(gòu)4．?dāng)?shù)據(jù)的邏輯結(jié)構(gòu)對數(shù)據(jù)元素之間的邏輯關(guān)系的描述只抽象地反映數(shù)據(jù)元素之間的邏輯關(guān)系，與計(jì)算機(jī)中的存儲(chǔ)無關(guān)兩個(gè)要素：數(shù)據(jù)元素的集合，通常記為D；前后件關(guān)系，通常記為R一個(gè)數(shù)據(jù)結(jié)構(gòu)B可以表示為：B=（D，R）181.2.1什么是數(shù)據(jù)結(jié)構(gòu)5．?dāng)?shù)據(jù)的存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)空間中的存放形式常用的存儲(chǔ)結(jié)構(gòu)：順序鏈?zhǔn)剿饕环N數(shù)據(jù)結(jié)構(gòu)可根據(jù)需要采用不同的存儲(chǔ)結(jié)構(gòu)。采用不同的存儲(chǔ)結(jié)構(gòu)，其數(shù)據(jù)處理的效率是不同191.2.2數(shù)據(jù)結(jié)構(gòu)的圖形表示數(shù)據(jù)結(jié)點(diǎn)：用方框表示根結(jié)點(diǎn)、終端結(jié)點(diǎn)前后件關(guān)系：用有向線段表示基本運(yùn)算：插入運(yùn)算刪除運(yùn)算查找、分類、合并、分解、復(fù)制、修改、……201.2.3線性結(jié)構(gòu)與非線性結(jié)構(gòu)空的數(shù)據(jù)結(jié)構(gòu)：一個(gè)數(shù)據(jù)元素都沒有線性結(jié)構(gòu)如果一個(gè)非空數(shù)據(jù)結(jié)構(gòu)滿足下列兩個(gè)條件：有且只有一個(gè)根結(jié)點(diǎn)；每一個(gè)結(jié)點(diǎn)最多有一個(gè)前件，也最多有一個(gè)后件。常見的線性結(jié)構(gòu)有：線性表、棧與隊(duì)列、線性鏈表非線性結(jié)構(gòu)如果一個(gè)數(shù)據(jù)結(jié)構(gòu)不是線性結(jié)構(gòu)常見的非線性結(jié)構(gòu)有：樹、二叉樹、圖211.3線性表及其順序存儲(chǔ)結(jié)構(gòu)221.3.1線性表的基本概念線性表：由n(n≥0)個(gè)相同類型數(shù)據(jù)元素構(gòu)成的有限序列：n定義為線性表的表長；n=0時(shí)的線性表被稱為空表。稱i為在線性表中的位序。例如：英文大寫字母表（A，B，C，D，E，F(xiàn)，…X，Y，Z）同一花色的13張撲克牌(2,3,4,5,6,7,8,9,10,J,Q,K,A)231.3.1線性表的基本概念線性表的結(jié)構(gòu)特征數(shù)據(jù)元素在表中的位置由序號(hào)決定，數(shù)據(jù)元素之間的相對位置是線性的；對于一個(gè)非空線性表，有且只有一個(gè)根結(jié)點(diǎn)a1，它無前件，有且只有一個(gè)終端結(jié)點(diǎn)an，它無后件，除根結(jié)點(diǎn)與終端結(jié)點(diǎn)外，其他所有結(jié)點(diǎn)有且只有一個(gè)前件，也有且只有一個(gè)后件。線性表的存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)鏈?zhǔn)酱鎯?chǔ)241.3.2線性表的順序存儲(chǔ)結(jié)構(gòu)兩個(gè)基本特點(diǎn)：線性表中所有元素所占的存儲(chǔ)空間是連續(xù)的。線性表中各數(shù)據(jù)元素在存儲(chǔ)空間中是按邏輯順序依次存放的。存儲(chǔ)示意圖251.3.3順序表的插入運(yùn)算261.3.4順序表的刪除運(yùn)算27順序表的插入和刪除分析插入算法的分析假設(shè)線性表中含有n個(gè)數(shù)據(jù)元素，在進(jìn)行插入操作時(shí)，若假定在n+1個(gè)位置上插入元素的可能性均等，則平均移動(dòng)元素的個(gè)數(shù)為：刪除算法的分析在進(jìn)行刪除操作時(shí)，若假定刪除每個(gè)元素的可能性均等，則平均移動(dòng)元素的個(gè)數(shù)為：分析結(jié)論順序存儲(chǔ)結(jié)構(gòu)表示的線性表，在做插入或刪除操作時(shí)，平均需要移動(dòng)大約一半的數(shù)據(jù)元素。當(dāng)線性表的數(shù)據(jù)元素量較大，并且經(jīng)常要對其做插入或刪除操作時(shí)，這一點(diǎn)需要值得考慮281.4棧和隊(duì)列291.4.1棧及其基本運(yùn)算1．棧的定義棧（stack）：一種只允許在表的一端進(jìn)行插入或刪除操作的特殊的線性表?xiàng)ｍ?top)：允許進(jìn)行插入與刪除操作的一端棧底(bottom)：不允許插入與刪除操作的另一端先進(jìn)后出（FILO）或后進(jìn)先出(LIFO)的線性表301.4.1棧及其基本運(yùn)算2．棧的順序存儲(chǔ)及其運(yùn)算top=0：?？誸op=m：棧滿棧的基本運(yùn)算入棧運(yùn)算退棧運(yùn)算讀棧頂元素311.4.2隊(duì)列及其基本運(yùn)算1．隊(duì)列的定義限定只能在表的一端進(jìn)行插入和在另一端進(jìn)行刪除操作的線性表隊(duì)尾(rear)：允許插入的一端隊(duì)頭(front)：允許刪除的另一端先進(jìn)先出（FIFO）表或后進(jìn)后出（LILO）線性表基本操作入隊(duì)運(yùn)算：往隊(duì)列的隊(duì)尾插入一個(gè)元素，隊(duì)尾指針rear的變化退隊(duì)運(yùn)算：從隊(duì)列的排頭刪除一個(gè)元素，隊(duì)頭指針front的變化321.4.2隊(duì)列及其基本運(yùn)算2．循環(huán)隊(duì)列及其運(yùn)算隊(duì)列存儲(chǔ)空間的最后一個(gè)位置繞到第一個(gè)位置，形成邏輯上的環(huán)狀空間，供隊(duì)列循環(huán)使用入隊(duì)運(yùn)算：隊(duì)尾指針加1，并當(dāng)rear=m+1時(shí)置rear=1出隊(duì)運(yùn)算：隊(duì)頭指針加1，并當(dāng)front=m+1時(shí)置front=1331.5線性鏈表341.5.1線性鏈表的基本概念1．線性表順序存儲(chǔ)的缺點(diǎn)插入或刪除的運(yùn)算效率很低。在順序存儲(chǔ)的線性表中，插入或刪除數(shù)據(jù)元素時(shí)需要移動(dòng)大量的數(shù)據(jù)元素。線性表的順序存儲(chǔ)結(jié)構(gòu)下，線性表的存儲(chǔ)空間不便于擴(kuò)充。線性表的順序存儲(chǔ)結(jié)構(gòu)不便于對存儲(chǔ)空間的動(dòng)態(tài)分配。351.5.1線性鏈表的基本概念2．線性鏈表線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)物理存儲(chǔ)單元上非連續(xù)、非順序的存儲(chǔ)結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈接來實(shí)現(xiàn)的每個(gè)結(jié)點(diǎn)由兩部分組成：數(shù)據(jù)域和指針域361.5.1線性鏈表的基本概念雙向鏈表：每個(gè)結(jié)點(diǎn)設(shè)置兩個(gè)指針左指針：指向其前件結(jié)點(diǎn)右指針：指向其后件結(jié)點(diǎn)371.5.2線性鏈表的基本運(yùn)算插入刪除合并分解逆轉(zhuǎn)復(fù)制排序查找381.5.2線性鏈表的基本運(yùn)算1．在線性鏈表中查找指定元素鏈表不是隨機(jī)存取結(jié)構(gòu)從鏈表的頭指針出發(fā)，順著鏈域next逐個(gè)結(jié)點(diǎn)往下搜索，直至搜索到第i個(gè)結(jié)點(diǎn)為止2．線性鏈表的插入391.5.2線性鏈表的基本運(yùn)算3．線性鏈表的刪除與順序存儲(chǔ)相比，鏈表的優(yōu)點(diǎn)有：插入和刪除元素時(shí)，不需要移動(dòng)數(shù)據(jù)元素，只需要修改指針即可401.5.3棧和隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)1．棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)——鏈棧411.5.3棧和隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)2．隊(duì)列鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)——鏈隊(duì)列421.5.4循環(huán)鏈表及其基本運(yùn)算循環(huán)鏈表特點(diǎn)：在鏈表中增加了一個(gè)表頭結(jié)點(diǎn)最后一個(gè)結(jié)點(diǎn)的指針域指向表頭結(jié)點(diǎn)，構(gòu)成了一個(gè)環(huán)狀鏈循環(huán)鏈表優(yōu)點(diǎn)：從任一結(jié)點(diǎn)出發(fā)來訪問表中其他所有結(jié)點(diǎn)空表與非空表的運(yùn)算的統(tǒng)一431.6樹與二叉樹1．樹的定義樹(Tree)是n(n≥0)個(gè)結(jié)點(diǎn)的有限集T，T為空時(shí)稱為空樹，否則它滿足如下兩個(gè)條件：（1）有且僅有一個(gè)特定的稱為根(Root)的結(jié)點(diǎn)；（2）其余的結(jié)點(diǎn)可分為m(m≥0)個(gè)互不相交的子集T1，T2，T3，…，Tm，其中每個(gè)子集又是一棵樹，并稱其為子樹。44ABCDEFGHIJKL(b)一般的樹451.6樹與二叉樹2．樹中的基本概念父結(jié)點(diǎn)與樹的根：每個(gè)結(jié)點(diǎn)最多只允許有一個(gè)前件，稱為該結(jié)點(diǎn)的父結(jié)點(diǎn)。沒有前件的結(jié)點(diǎn)中有一個(gè)，稱為樹的根結(jié)點(diǎn)。子結(jié)點(diǎn)與葉子結(jié)點(diǎn)：在樹結(jié)構(gòu)中，每一個(gè)結(jié)點(diǎn)可以有多個(gè)后件，它們都稱為該結(jié)點(diǎn)的子結(jié)點(diǎn)。沒有后件的結(jié)點(diǎn)稱為葉子結(jié)點(diǎn)。結(jié)點(diǎn)的度和樹的度：一個(gè)結(jié)點(diǎn)所擁有后件個(gè)數(shù)稱為該結(jié)點(diǎn)的度。一棵樹中各個(gè)結(jié)點(diǎn)度數(shù)的最大值叫做這棵樹的度。層和樹的深度：樹結(jié)構(gòu)是一種層次結(jié)構(gòu)，根結(jié)點(diǎn)為第一層，根的子結(jié)點(diǎn)為第二層，其余各結(jié)點(diǎn)的層數(shù)逐層由上而下計(jì)算。一棵樹中結(jié)點(diǎn)的最大層數(shù)叫做此樹的深度。461.6.1樹的基本概念樹的特點(diǎn)（1）樹中只有根結(jié)點(diǎn)沒有前件；（2）除根外，其余結(jié)點(diǎn)都有且僅一個(gè)前件；（3）樹的結(jié)點(diǎn)，可以有零個(gè)或多個(gè)后件；（4）除根外的其他結(jié)點(diǎn)，都存在唯一條從根到該結(jié)點(diǎn)的路徑；（5）樹是一種分支結(jié)構(gòu)（除根的結(jié)點(diǎn)外）每個(gè)元素都有且僅有一個(gè)直接前件，有且僅有零個(gè)或多個(gè)直接后件。樹的存儲(chǔ)用多重鏈表來表示471.6.2二叉樹及其基本性質(zhì)1．二叉樹的定義一個(gè)二叉樹是n個(gè)結(jié)點(diǎn)的有限集合（n≥0），此集合或者是空集（n=0），或者是由一個(gè)根結(jié)點(diǎn)及兩棵互不相交的、分別稱為左子樹和右子樹的二叉樹組成，并且左右子樹都是二叉樹。特點(diǎn)：非空二叉樹只有一個(gè)根結(jié)點(diǎn)；每一個(gè)結(jié)點(diǎn)最多有兩棵子樹，且分別稱為該結(jié)點(diǎn)的左子樹與右子樹。481.6.2二叉樹及其基本性質(zhì)2．二叉樹的性質(zhì)性質(zhì)1

在二叉樹的第k層上，最多有個(gè)結(jié)點(diǎn)。性質(zhì)2

深度為m的二叉樹最多有個(gè)結(jié)點(diǎn)。性質(zhì)3

在任意一棵二叉樹中，度數(shù)為0的結(jié)點(diǎn)（即葉子結(jié)點(diǎn)）總比度為2的結(jié)點(diǎn)多一個(gè)。即：其中，n0表示度數(shù)為0的結(jié)點(diǎn)數(shù)，n2表示度數(shù)為2的結(jié)點(diǎn)數(shù)。性質(zhì)4

具有n個(gè)結(jié)點(diǎn)的二叉樹的深度至少為，其中表示取的整數(shù)部分。491.6.2二叉樹及其基本性質(zhì)3．滿二叉樹和完全二叉樹滿二叉樹：除最后一層外，每一層上的所有結(jié)點(diǎn)都有兩個(gè)子結(jié)點(diǎn)。完全二叉樹：除最后一層外，每一層上的結(jié)點(diǎn)數(shù)均達(dá)到最大值；在最后一層上只缺少右邊的若干結(jié)點(diǎn)。501.6.2二叉樹及其基本性質(zhì)性質(zhì)5具有n個(gè)結(jié)點(diǎn)的完全二叉樹深度為。性質(zhì)6設(shè)完全二叉樹共有n個(gè)結(jié)點(diǎn)，如果從根結(jié)點(diǎn)開始，按層序（每一層從左到右）用自然數(shù)1，2，…，n給結(jié)點(diǎn)進(jìn)行編號(hào)，則對于編號(hào)為k（k=1，2，…，n）的結(jié)點(diǎn)有以下結(jié)論：①若k=1，則該結(jié)點(diǎn)為根結(jié)點(diǎn)，它沒有父結(jié)點(diǎn)；若k>1，則該結(jié)點(diǎn)的父結(jié)點(diǎn)的編號(hào)為INT(k/2)。②若2k≤n，則編號(hào)為k的左子結(jié)點(diǎn)編號(hào)為2k；否則該結(jié)點(diǎn)無左子結(jié)點(diǎn)（顯然也沒有右子結(jié)點(diǎn)）。③若2k+1≤n，則編號(hào)為k的右子結(jié)點(diǎn)編號(hào)為2k+1；否則該結(jié)點(diǎn)無右子結(jié)點(diǎn)。511.6.3二叉樹的存儲(chǔ)結(jié)構(gòu)普通二叉樹采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)存儲(chǔ)結(jié)點(diǎn)由兩部分組成：數(shù)據(jù)域與指針域兩個(gè)指針域：左指針域右指針域滿二叉樹與完全二叉樹采用順序存儲(chǔ)結(jié)構(gòu)521.6.4二叉樹的遍歷二叉樹的遍歷：不重復(fù)地訪問二叉樹中的所有結(jié)點(diǎn)1．前序遍歷（DLR）首先訪問根結(jié)點(diǎn)，然后遍歷左子樹，最后遍歷右子樹；并且，在遍歷左右子樹時(shí)，仍然先訪問根結(jié)點(diǎn)，然后遍歷左子樹，最后遍歷右子樹。2．中序遍歷（LDR）首先遍歷左子樹，然后訪問根結(jié)點(diǎn)，最后遍歷右子樹；并且，在遍歷左、右子樹時(shí)，仍然先遍歷左子樹，然后訪問根結(jié)點(diǎn)，最后遍歷右子樹3．后序遍歷（LRD）首先遍歷左子樹，然后遍歷右子樹，最后訪問根結(jié)點(diǎn)，并且，在遍歷左、右子樹時(shí)，仍然先遍歷左子樹，然后遍歷右子樹，最后訪問根結(jié)點(diǎn)。531.6.4二叉樹的遍歷前序遍歷：A、B、D、G、C、E、F中序遍歷：D、G、B、A、E、C、F后序遍歷：G、D、B、E、F、C、AP16-33圖54ABCDEF551.7查找技術(shù)561.7查找技術(shù)查找（Searching）：根據(jù)給定的某個(gè)值，在查找表中確定一個(gè)其關(guān)鍵字等于給定值的數(shù)據(jù)元素。查找結(jié)果：查找成功：找到查找不成功：沒找到平均查找長度：查找過程中關(guān)鍵字和給定值比較的平均次數(shù)571.7.1順序查找基本思想：從表中的第一個(gè)元素開始，將給定的值與表中逐個(gè)元素的關(guān)鍵字進(jìn)行比較，直到兩者相符，查到所要找的元素為止。否則就是表中沒有要找的元素，查找不成功。平均要與表中一半以上元素進(jìn)行比較，最壞情況下需要比較n次。下列兩種情況下只能采用順序查找：如果線性表是無序表（即表中的元素是無序的），則不管是順序存儲(chǔ)結(jié)構(gòu)還是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，都只能用順序查找。即使是有序線性表，如果采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，也只能用順序查找。581.7.2二分法查找思想：先確定待查找記錄所在的范圍，然后逐步縮小范圍，直到找到或確認(rèn)找不到該記錄為止。前提：必須在具有順序存儲(chǔ)結(jié)構(gòu)的有序表中進(jìn)行。查找過程：1）若中間項(xiàng)的值等于x,則說明已查到。2）若x小于中間項(xiàng)的值，則在線性表的前半部分查找；3）若x大于中間項(xiàng)的值，則在線性表的后半部分查找。特點(diǎn)：比順序查找方法效率高。最壞的情況下，需要比較log2n次。591.7.2二分法查找例：查找元素22過程：601.8排序技術(shù)611.8.1交換類排序法基本思想兩兩比較待排序記錄的關(guān)鍵字，發(fā)現(xiàn)兩個(gè)記錄的次序相反時(shí)即進(jìn)行交換，直到?jīng)]有反序的記錄為止。方法冒泡排序快速排序621.冒泡排序基本思想對存放原始數(shù)據(jù)的數(shù)組，按從后往前的方向進(jìn)行多次掃描，當(dāng)發(fā)現(xiàn)相鄰兩個(gè)數(shù)據(jù)的次序與排序要求的“遞增次序”不符合時(shí)，即將這兩個(gè)數(shù)據(jù)進(jìn)行互換。這樣，較小的數(shù)據(jù)就會(huì)逐單元向前移動(dòng)，好象氣泡向上浮起一樣。性能分析假設(shè)線性表的長度n，則在最壞情況下，需要的比較次數(shù)為n(n-1)/2。631.冒泡排序642．快速排序基本思想任取待排序序列中的某個(gè)元素作為基準(zhǔn)（一般取第一個(gè)元素），通過一趟排序，將待排元素分為左右兩個(gè)子序列，左子序列元素的排序碼均小于或等于基準(zhǔn)元素的排序碼，右子序列的排序碼則大于基準(zhǔn)元素的排序碼，然后分別對兩個(gè)子序列繼續(xù)進(jìn)行排序，直至整個(gè)序列有序?？焖倥判虻钠骄鶗r(shí)間復(fù)雜度為O(nlog2n)。652．快速排序P66-5:快速排序法初始順序:661351768126576923

一次交換:231351768126576966二次交換:23135166

8126576976三次交換:23135157

8126666976四次交換:23135157

66

2681

6976五次交換:23135157

26

6681

697666671.8.2插入類排序法基本思想：每次將一個(gè)待排序的記錄，按其關(guān)鍵字大小插入到前面已經(jīng)排好序的子序列中的適當(dāng)位置，直到全部記錄插入完成為止。方法:簡單插入排序希爾排序681．簡單插入排序法基本思想：把n個(gè)待排序的元素看成為一個(gè)有序表和一個(gè)無序表，開始時(shí)有序表中只包含一個(gè)元素，無序表中包含有n-1個(gè)元素，排序過程中每次從無序表中取出第一個(gè)元素，把它的排序碼依次與有序表元素的排序碼進(jìn)行比較，將它插入到有序表中的適當(dāng)位置，使之成為新的有序表。在最壞的情況下，需要n(n-1)/2次比較