<b id="glvx9"></b> 點(diǎn)擊進(jìn)入：2011計(jì)算機(jī)等考二級(jí)公共基礎(chǔ)知識(shí)講義匯總>>
1.7 查找技術(shù)
查找：根據(jù)給定的某個(gè)值，在查找表中確定一個(gè)其關(guān)鍵字等于給定值的數(shù)據(jù)元素。
查找結(jié)果：(查找成功：找到;查找不成功：沒找到。)
平均查找長(zhǎng)度：查找過程中關(guān)鍵字和給定值比較的平均次數(shù)。
1、順序查找
基本思想：從表中的第一個(gè)元素開始，將給定的值與表中逐個(gè)元素的關(guān)鍵字進(jìn)行比較，直到兩者相符，查到所要找的元素為止。否則就是表中沒有要找的元素，查找不成功。
在平均情況下，利用順序查找法在線性表中查找一個(gè)元素，大約要與線性表中一半的元素進(jìn)行比較，最壞情況下需要比較n次。
順序查找一個(gè)具有n個(gè)元素的線性表，其平均復(fù)雜度為O(n)。
下列兩種情況下只能采用順序查找：
1)如果線性表是無序表(即表中的元素是無序的)，則不管是順序存儲(chǔ)結(jié)構(gòu)還是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，都只能用順序查找。
2)即使是有序線性表，如果采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，也只能用順序查找。
2、二分法查找
思想：先確定待查找記錄所在的范圍，然后逐步縮小范圍，直到找到或確認(rèn)找不到該記錄為止。
前提：必須在具有順序存儲(chǔ)結(jié)構(gòu)的有序表中進(jìn)行。
查找過程：
1)若中間項(xiàng)(中間項(xiàng)mid=(n-1)/2，mid的值四舍五入取整)的值等于x，則說明已查到;
2)若x小于中間項(xiàng)的值，則在線性表的前半部分查找;
3)若x大于中間項(xiàng)的值，則在線性表的后半部分查找。
特點(diǎn)：比順序查找方法效率高。最壞的情況下，需要比較log2n次。
二分法查找只適用于順序存儲(chǔ)的線性表，且表中元素必須按關(guān)鍵字有序(升序)排列[注釋1] 。對(duì)于無序線性表和線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)只能用順序查找。在長(zhǎng)度為n的有序線性表中進(jìn)行二分法查找，其時(shí)間復(fù)雜度為O(log2n)。（注釋1：允許相鄰元素值相等。）
1.8 排序技術(shù)
排序是指將一個(gè)無序序列整理成按值非遞減順序排列的有序序列，即是將無序的記錄序列調(diào)整為有序記錄序列的一種操作。
1、交換類排序法(方法：冒泡排序，快速排序)。
2、插入類排序法(方法：簡(jiǎn)單插入排序，希爾排序)。
3、選擇類排序法(方法：簡(jiǎn)單選擇排序，堆排序)。
總結(jié)：各種排序法比較
本章應(yīng)考點(diǎn)撥：本章內(nèi)容在筆試中會(huì)出現(xiàn)5-6個(gè)題目，是公共基礎(chǔ)知識(shí)部分出題量比較多的一章，所占分值也比較大，約10分。
相關(guān)推薦：
2011計(jì)算機(jī)等考二級(jí)公共基礎(chǔ)知識(shí)要點(diǎn)匯總
| 北京 | 天津 | 上海 | 江蘇 | 山東 |
| 安徽 | 浙江 | 江西 | 福建 | 深圳 |
| 廣東 | 河北 | 湖南 | 廣西 | 河南 |
| 海南 | 湖北 | 四川 | 重慶 | 云南 |
| 貴州 | 西藏 | 新疆 | 陜西 | 山西 |
| 寧夏 | 甘肅 | 青海 | 遼寧 | 吉林 |
| 黑龍江 | 內(nèi)蒙古 |
