【文章內(nèi)容簡(jiǎn)介】 定的元素。1．順序查找順序查找又稱(chēng)順序搜索。一般是在線(xiàn)性表中查找指定的元素?；静僮鞣椒ㄊ牵簭木€(xiàn)性表的第一個(gè)元素開(kāi)始，與被查元素進(jìn)行比較，相等則查找成功，否則繼續(xù)向后查找。如果所有的元素均查找完畢后都不相等，則該元素在指定的線(xiàn)性表中不存在。順序查找的最好情況：要查找的元素在線(xiàn)性表的第一個(gè)元素，則查找效率最高；如果要查找的元素在線(xiàn)性表的最后或根本不存在，則查找需要搜索所有的線(xiàn)性表元素，這種情況是最差情況。對(duì)于線(xiàn)性表而言，順序查找效率很低。但對(duì)于以下的線(xiàn)性表，也只能采用順序查找的方法：l 線(xiàn)性表為無(wú)序表，即表中的元素沒(méi)有排列不是按大小順序進(jìn)行排列的，這類(lèi)線(xiàn)性表不管它的存儲(chǔ)方式是順序存儲(chǔ)還是鏈?zhǔn)酱鎯?chǔ)，都只能按順序查找方式進(jìn)行查找l 即使是有序線(xiàn)性表，如果采用鏈?zhǔn)酱鎯?chǔ)，也只能采用順序查找方式例如，現(xiàn)有線(xiàn)性表：4，要在序列中查找元素6，查找的過(guò)程是：l 整個(gè)線(xiàn)性表的長(zhǎng)度為5l 查找計(jì)次n=1，將元素6與序列的第一個(gè)7元素進(jìn)行比較，不等，繼續(xù)查找l n=2，將6與第二個(gè)元素2進(jìn)行比較，不等，繼續(xù)l n=3，將6與第三個(gè)元素1進(jìn)行比較，不等，繼續(xù)l n=4，將6與第四個(gè)元素5進(jìn)行比較，不等，繼續(xù)l n=5，將6與第五個(gè)元素9進(jìn)行比較，不等，繼續(xù)l n=6，將6與第六個(gè)元素4進(jìn)行比較，不等，繼續(xù)l n=7，超出線(xiàn)性表的長(zhǎng)度，查找結(jié)束，則該表中不存在要查找的元素。2．二分查找二分查找只適用于順序存儲(chǔ)的有序表。此處所述的有序表是指線(xiàn)性中的元素按值非遞減排列（即由小到大，但允許相鄰元素值相等）。二分查找的方法如下：將要查找的元素與有序序列的中間元素進(jìn)行比較：l 如果該元素比中間元素大，則繼續(xù)在線(xiàn)性表的后半部分（中間項(xiàng)以后的部分）進(jìn)行查找l 如果要查找的元素的值比中間元素的值小，則繼續(xù)在線(xiàn)性表的前半部分（中間項(xiàng)以前的部分）進(jìn)行查找這個(gè)查找過(guò)程一直按相同的順序進(jìn)行下去，一直到查找成功或子表長(zhǎng)度為0（說(shuō)明線(xiàn)性表中沒(méi)有要查找的元素）有序線(xiàn)性表的二分法查找，條件是必須這個(gè)有序線(xiàn)性表的存儲(chǔ)方式是順序存儲(chǔ)的。它的查找效率比順序查找要高得多，它的最壞情況的查找次數(shù)是log2n次，而順序查找的最壞情況的查找次數(shù)是n次。當(dāng)然，二分查找的方法也支持順序存儲(chǔ)的遞減序列的線(xiàn)性表。有非遞減有序線(xiàn)性表：9，要查找元素6。查找的方法是：l 序列長(zhǎng)度為n=6，中間元素的序號(hào)m=[(n+1)/2]=3l 查找計(jì)次k=1，將元素6與中間元素即元素4進(jìn)行比較，不等，64l 查找計(jì)次k=2，查找繼續(xù)在后半部分進(jìn)行，后半部分子表的長(zhǎng)度為3，計(jì)算中間元素的序號(hào)：m=3+[(3+1)/2]=5，將元素與后半部分的中間項(xiàng)進(jìn)行比較，即第5個(gè)元素中的7進(jìn)行比較，不等，67l 查找計(jì)次k=3，繼續(xù)查找在后半部分序列的前半部分子序列中查找，子表長(zhǎng)度為1，則中間項(xiàng)序號(hào)即為m=3+[(1+1)/2]=4，即與第4個(gè)元素5進(jìn)行比較，不相等，繼續(xù)查找的子表長(zhǎng)度為0，則查找結(jié)束（八）排序技術(shù)排序即是將一個(gè)無(wú)序的序列整理成按值非遞減順序排列的有序序列。在這里，我們討論的是順序存儲(chǔ)的線(xiàn)性表的排序操作。1．交換類(lèi)排序法交換類(lèi)排序法，即是借助于數(shù)據(jù)元素之間的互相交換進(jìn)行排序的方法。1）冒泡排序法冒泡排序法即是利用相鄰數(shù)據(jù)元素之間的交換逐步將線(xiàn)性表變成有序序列的操作方法。操作過(guò)程如下：l 從表頭開(kāi)始掃描線(xiàn)性表，在掃描過(guò)程中逐次比較相鄰兩個(gè)元素的大小，若相鄰兩個(gè)元素中前一個(gè)元素的值比后一個(gè)元素的值大，將兩個(gè)元素位置進(jìn)行交換，當(dāng)掃描完成一遍時(shí)，則序列中最大的元素被放置到序列的最后。l 再繼續(xù)對(duì)序列從頭進(jìn)行掃描，這一次掃描的長(zhǎng)度是序列長(zhǎng)度減1，因?yàn)樽畲蟮脑匾呀?jīng)就位了，采用與前相同的方法，兩兩之間進(jìn)行比較，將次大數(shù)移到子序列的末尾。l 按相同的方法繼續(xù)掃描，每次掃描的子序列的長(zhǎng)度均比上一次減1，直至子序列的長(zhǎng)度為1時(shí)，排序結(jié)束。例如，有序列6，將該序列從小到大進(jìn)行排列。采用冒泡排序法，具體操作步驟如下：序列長(zhǎng)度n=7原序列 5 2 9 4 1 7 6第一遍（從前往后） 5172。174。 2 9 4 1 7 6 2 5 9172。174。 4 1 7 6 2 5 4 9172。174。 1 7 6 2 3 4 1 9172。174。 7 6 2 5 4 1 7 9172。174。 6第一遍結(jié)束后 2 5 4 1 7 6 9第二遍（從前往后） 2 5172。174。 4 1 7 6 9 2 4 5172。174。 1 7 6 9 2 4 1 5 7172。174。 6 9 2 4 1 5 6 7 9第二遍結(jié)束后 2 4 1 5 6 7 9第三遍（從前往后） 2 4172。174。 1 5 6 7 9 2 1 4 5 6 7 9第三遍結(jié)束 2 1 4 5 6 7 9第四遍（從前往后） 2172。174。 1 4 5 6 7 9 1 2 4 5 6 7 9第四遍結(jié)束 1 2 4 5 6 7 9最后結(jié)果 1 2 4 5 6 7 9掃描的次數(shù)，最多需要掃描n1次，如果序列已經(jīng)就位，則掃描結(jié)束。測(cè)試是否已經(jīng)就位，可設(shè)置一個(gè)標(biāo)志，如果該次掃描沒(méi)有數(shù)據(jù)交換，則說(shuō)明數(shù)據(jù)排序結(jié)束。2）快速排序法冒泡排序方法每次交換只能改變相鄰兩個(gè)元素之間的逆序，速度相對(duì)較慢。如果將兩個(gè)不相鄰的元素之間進(jìn)行交換，可以消除多個(gè)逆序?？焖倥判虻姆椒ㄊ牵簭木€(xiàn)性表中選取一個(gè)元素，設(shè)為T(mén)，將線(xiàn)性表后面小于T的元素移到前面，而前面大于T的元素移到后面，結(jié)果將線(xiàn)性表分成兩個(gè)部分（稱(chēng)為兩個(gè)子表），T插入到其分界線(xiàn)的位置處，這個(gè)過(guò)程稱(chēng)為線(xiàn)性表的分割。對(duì)過(guò)對(duì)線(xiàn)性表的一次分割，就以T為分界線(xiàn)，將線(xiàn)性表分成前后兩個(gè)子表，且前面子表中的所有元素均不大于T，而后面的所有元素均不小于T。再將前后兩個(gè)子表再進(jìn)行相同的快速排序，將子表再進(jìn)行分割，直到所有的子表均為空，則完成快速排序操作。在快速排序過(guò)程中，隨著對(duì)各子表不斷的進(jìn)行分割，劃分出的子表會(huì)越來(lái)越多，但一次又只能對(duì)一個(gè)子表進(jìn)行分割處理，需要將暫時(shí)不用的子表記憶起來(lái)，這里可用棧來(lái)實(shí)現(xiàn)。對(duì)某個(gè)子表進(jìn)行分割后，可以將分割出的后一個(gè)子表的第一個(gè)元素與最后一個(gè)元素的位置壓入棧中，而繼續(xù)對(duì)前一個(gè)子表進(jìn)行再分割；當(dāng)分割出的子表為空時(shí)，可以從棧中退出一個(gè)子表進(jìn)行分割。這個(gè)過(guò)程直到棧為空為止，說(shuō)明所有子表為空，沒(méi)有子表再需分割，排序就完成。2．插入類(lèi)排序法1）簡(jiǎn)單插入排序插入排序，是指將無(wú)序序列中的各元素依次插入到已經(jīng)有序的線(xiàn)性表中。插入排序操作的思路：在線(xiàn)性表中，只包含第1個(gè)元素的子表，作為該有序表。從線(xiàn)性表的第2個(gè)元素開(kāi)始直到最后一個(gè)元素，逐次將其中的每一個(gè)元素插入到前面的有序的子表中。該方法與冒泡排序方法的效率相同，最壞的情況下需要n(n1)/2次比較。例如，有序列6，將該序列從小到大進(jìn)行排列。采用簡(jiǎn)單插入排序法，具體操作步驟如下：序列長(zhǎng)度n=7 5 2 9 4 1 7 6 173。j=2 2 5 9 4 1 7 6 173。j=3 2 5 9 4 1 7 6 173。j=4 2 4 5 9 1 7 6 173。j=5 1 2 4 5 9 7 6 173。j=6 1 2 4 5 7 9 6 173。j=7插入排序后的結(jié)果 1 2 4 5 6 7 92）希爾排序法希爾排序法的基本思想：將整個(gè)無(wú)序序列分割成若干小的子序列分別進(jìn)行插入排序。子序列的分割方法：將相隔某個(gè)增量h的元素構(gòu)成一個(gè)子序列，在排序的過(guò)程中，逐次減小這個(gè)增量，最后當(dāng)h減小到1時(shí)，再進(jìn)行一次插入排序操作，即完成排序。增量序列一般取ht=n/2k(k=1,2,…,[log2n])，其中n為待排序序列的長(zhǎng)度。3．選擇類(lèi)排序法1）簡(jiǎn)單選擇排序法基本思路：掃描整個(gè)線(xiàn)性表，從中選出最小的元素，將它交換到表的最前面，然后對(duì)后面的子表采用相同的方法，直到子表為空為止。對(duì)于長(zhǎng)度為n的序列，需要掃描n1次，每一次掃描均找出剩余的子表中最小的元素，然后將該最小元素與子表的第一個(gè)元素進(jìn)行交換。例如，有序列6，將該序列從小到大進(jìn)行排列。采用簡(jiǎn)單選擇排序法，具體操作步驟如下：原序列 5 2 9 4 1 7 6第一遍掃描 1 2 9 4 5 7 6第二遍掃描 1 2 9 4 5 7 6第三遍掃描 1 2 4 9 5 7 6第四遍掃描 1 2 4 5 9 7 6第五遍掃描 1 2 4 5 6 7 9第六遍掃描 1 2 4 5 6 7 9排序結(jié)果 1 2 4 5 6 7 92）堆排序法堆排序法屬于選擇類(lèi)排序方法。堆的定義：具有n個(gè)元素的序列（h1,h2,…,hn），當(dāng)且僅當(dāng)滿(mǎn)足 （I=1,2,…,n/2）時(shí)稱(chēng)之為堆。本節(jié)只討論滿(mǎn)足前者條件的堆。由堆的定義看，堆頂元素（即第一個(gè)元素）必為最大項(xiàng)?？梢杂靡痪S數(shù)組或完全二叉樹(shù)來(lái)表示堆的結(jié)構(gòu)。用完全二叉樹(shù)表示堆時(shí)，樹(shù)中所有非葉子結(jié)點(diǎn)值均不小于其左右子樹(shù)的根結(jié)點(diǎn)的值，因此堆頂（完全二叉樹(shù)的根結(jié)點(diǎn)）元素必須為序列的n個(gè)元素中的最大項(xiàng)。例如，有序列6，將該序列從小到大進(jìn)行排列。利用堆排序法將該序列進(jìn)行排序。操作方式即：先將無(wú)序堆的根結(jié)點(diǎn)5與左右子樹(shù)的根結(jié)點(diǎn)9進(jìn)行比較，59，將5與9進(jìn)行交換；整后，對(duì)左右子樹(shù)進(jìn)行堆調(diào)整，左子樹(shù)的根結(jié)點(diǎn)2小于其左葉子結(jié)點(diǎn)5，調(diào)整；右子樹(shù)的根結(jié)點(diǎn)5小于其左右子結(jié)點(diǎn)7和6，根據(jù)堆的要求，將5與7進(jìn)行調(diào)整。根據(jù)堆的定義，可以得到堆排序的方法：（1）首先將一個(gè)無(wú)序序列建成堆（2）然后將堆頂元素（序列中的最大項(xiàng)）與堆中最后一個(gè)元素交換（最大項(xiàng)應(yīng)該在序列的最后）。三、本章應(yīng)考點(diǎn)撥本章內(nèi)容在筆試中會(huì)出現(xiàn)56個(gè)題目，是公共基礎(chǔ)知識(shí)部分出題量比較多的一章，所占分值也比較大，約10分。第二章 程序設(shè)計(jì)基礎(chǔ)一、內(nèi)容要點(diǎn)（一）程序設(shè)計(jì)方法與風(fēng)格程序設(shè)計(jì)方法：主要經(jīng)過(guò)了面向過(guò)程的結(jié)構(gòu)化程序設(shè)計(jì)和面向?qū)ο蟮某绦蛟O(shè)計(jì)方法。程序設(shè)計(jì)風(fēng)格，是指編寫(xiě)程序時(shí)所表現(xiàn)出來(lái)的特點(diǎn)、習(xí)慣和邏輯思路。通常，要求程序設(shè)計(jì)的風(fēng)格應(yīng)強(qiáng)調(diào)簡(jiǎn)單和清晰，必須是可以讀的，可以理解的。要形成良好的程序設(shè)計(jì)的風(fēng)格，應(yīng)考慮如下因素：1．源程序文檔化（1）符號(hào)名的命名：符號(hào)名的命名要具有一定的實(shí)際含義，便于對(duì)程序的理解，即通常說(shuō)的見(jiàn)名思義；（2）程序注釋?zhuān)赫_的程序注釋能夠幫助他人理解程序。注釋一般包括序言性注釋和功能性注釋?zhuān)唬?）視覺(jué)組織：為了使程序一目了然，可以對(duì)程序的格式進(jìn)行設(shè)置，適當(dāng)?shù)赝ㄟ^(guò)空格、空行、縮進(jìn)等使程序?qū)哟吻逦?．?dāng)?shù)據(jù)說(shuō)明方法（1）數(shù)據(jù)說(shuō)明的次序規(guī)范化；（2）說(shuō)明語(yǔ)句中變量安排有序化；（3）使用注釋來(lái)說(shuō)明復(fù)雜的數(shù)據(jù)結(jié)構(gòu)。3．語(yǔ)句的結(jié)構(gòu)（1）在一行內(nèi)只寫(xiě)一條語(yǔ)句；（2）程序的編寫(xiě)應(yīng)該優(yōu)先考慮清晰性；（3）除非對(duì)效率有特殊的要求，否則，應(yīng)做到清晰第一，效率第二；（4）首先保證程序的正確，然后再要求速度；（5）避免使用臨時(shí)變量使程序的可讀性下降；（7）盡量使用庫(kù)函數(shù)，即盡量使用系統(tǒng)提供的資源；（8）避免采用復(fù)雜的條件語(yǔ)句；（9）盡量減少使用“否定”條件的條件語(yǔ)句；（10）數(shù)據(jù)結(jié)構(gòu)要有利于程序的簡(jiǎn)化；（11）要模塊化，使模塊功能盡可能單一化；（12）利用信息隱蔽，確保每一個(gè)模塊的獨(dú)立性；（13）從數(shù)據(jù)出發(fā)去構(gòu)造程序；（14）不要修補(bǔ)不好的程序，要重新編寫(xiě)。4．輸入和輸出（1）對(duì)所有的輸入輸出數(shù)據(jù)都要檢驗(yàn)數(shù)據(jù)的合法性；（2）檢查輸入項(xiàng)的各種重要組合的合理性；（3）輸入格式要簡(jiǎn)單，以使得輸入的步驟和操作盡可能簡(jiǎn)單；（4）輸入數(shù)據(jù)時(shí)，應(yīng)允許自由格式；（5）應(yīng)允許缺省值；（6）輸入一批數(shù)據(jù)時(shí)，最好使用輸入結(jié)束標(biāo)志；（7）以交互式輸入輸出方式進(jìn)行輸入時(shí)，要在屏幕上使用提示符明確輸入的請(qǐng)求，同時(shí)在數(shù)據(jù)輸入過(guò)程中和輸入結(jié)束時(shí)，應(yīng)在屏幕上給出狀態(tài)信息；（8）當(dāng)程序設(shè)計(jì)語(yǔ)言對(duì)輸入格式有嚴(yán)格要求時(shí)，應(yīng)保持輸入格式與輸入語(yǔ)句的一致性；給所有的輸出加注釋?zhuān)⒃O(shè)計(jì)輸出報(bào)表格式。（二）結(jié)構(gòu)化程序設(shè)計(jì)1．結(jié)構(gòu)化程序設(shè)計(jì)的原則結(jié)構(gòu)化程序設(shè)計(jì)方法的主要原則：自頂而下、逐步求精，模塊化，限制使用goto語(yǔ)句。1）自頂而下程序設(shè)計(jì)時(shí)，應(yīng)先考慮總體，后考慮細(xì)節(jié)；先考慮全局，后考慮局部目標(biāo)。即先從最上層總目標(biāo)開(kāi)始設(shè)計(jì)，逐步使問(wèn)題具體化。2）逐步求精對(duì)復(fù)雜問(wèn)題，應(yīng)設(shè)計(jì)一些子目標(biāo)作為過(guò)渡，逐步細(xì)化。3）模塊化一個(gè)復(fù)雜問(wèn)題，都是由若干個(gè)稍簡(jiǎn)單的問(wèn)題構(gòu)成的。模塊化即是將復(fù)雜問(wèn)題進(jìn)行分解，即將解決問(wèn)題的總目標(biāo)分解成若干個(gè)分目標(biāo)，再進(jìn)一步分解為具體的小目標(biāo)，把每一個(gè)小目標(biāo)稱(chēng)作一個(gè)模塊。4）限制使用goto語(yǔ)句goto語(yǔ)句可以提高效率，但對(duì)程序的可讀性、維護(hù)性都造成影響，因此應(yīng)盡量不用goto語(yǔ)句。2．結(jié)構(gòu)化程序設(shè)計(jì)的基本結(jié)構(gòu)與特點(diǎn)結(jié)構(gòu)化程序設(shè)計(jì)是程序設(shè)計(jì)的先進(jìn)方法和工具，采用結(jié)構(gòu)化程序設(shè)計(jì)可以使程序結(jié)構(gòu)良好、易讀、易理解、易維護(hù)。1）順序結(jié)構(gòu)順序結(jié)構(gòu)即是順序執(zhí)行的結(jié)構(gòu)，是按照程序語(yǔ)句行的自然順序，一條一條語(yǔ)句地執(zhí)行程序。2）選擇結(jié)構(gòu)選擇結(jié)構(gòu)又稱(chēng)分支結(jié)構(gòu)，它包括簡(jiǎn)單選擇和多分支選擇結(jié)構(gòu)。程序的執(zhí)行是根據(jù)給定的條件，選擇相應(yīng)的分支來(lái)執(zhí)行。3）重復(fù)結(jié)構(gòu)重復(fù)結(jié)構(gòu)又稱(chēng)循環(huán)結(jié)構(gòu)，根據(jù)給定的條件，決定是否重復(fù)執(zhí)行某一相同的或類(lèi)似的程序段。利用重復(fù)結(jié)構(gòu)可以大量簡(jiǎn)化程序行。3．結(jié)構(gòu)化程序設(shè)計(jì)原則和方法的應(yīng)用1．使用程序設(shè)計(jì)語(yǔ)言中的順序、選擇、循環(huán)等有限的控制結(jié)構(gòu)表示程序的控制邏輯；2．選用的控制結(jié)構(gòu)只允許有一個(gè)入口和一個(gè)出口；3．程序語(yǔ)句組成容易識(shí)別的塊，每塊只有一個(gè)入口和一個(gè)出口；4．復(fù)雜結(jié)構(gòu)應(yīng)該用嵌套的基本控制結(jié)構(gòu)進(jìn)行組合嵌套來(lái)實(shí)現(xiàn)；5．語(yǔ)言中所有沒(méi)有的控制結(jié)構(gòu)，應(yīng)該采用前后一致的方法來(lái)模擬；6．嚴(yán)格控制goto