1、貴州大學實驗報告學院： 電子信息學院 專業(yè)： 通信工程 班級：2012級1班姓名學號實驗組實驗時間2014.5.15指導教師成績實驗項目名稱查找 排序?qū)嶒災(zāi)康暮鸵?1、掌握常用的查找、排序方法，及相應(yīng)的算法實現(xiàn)。 2、能實現(xiàn)并應(yīng)用某一種查找算法。理解各種排序方法的特點，并能加以靈活應(yīng)用。 3、了解各種排序算法的時間復雜度分析。實驗原理1、根據(jù)實驗內(nèi)容編程，上機調(diào)試、得出正確的運行程序。2、編譯運行程序，觀察運行情況和輸出結(jié)果。實驗儀器運行Visual c+的微機一臺實驗內(nèi)容和步驟1、查找相關(guān)實驗內(nèi)容及步驟。 建立順序存儲結(jié)構(gòu)，構(gòu)建一個順序表，實現(xiàn)順序查找算法。 typedef struct

2、ElemType *elem; /數(shù)據(jù)元素存儲空間基址，建表時按實際長度分配，號單元留空 int length; /表的長度 SSTable; 對順序表先排序后，實現(xiàn)行二分法查找相關(guān)操作。 定義二叉樹節(jié)點，根據(jù)節(jié)點的值進行查找，并且實現(xiàn)節(jié)點的插入，刪除等操作。 typedef struct BiTnode /定義二叉樹節(jié)點 int data; /節(jié)點的值 struct BiTnode *lchild,*rchild; BiTnode,*BiTree; 定義哈希表以及要查找的節(jié)點元素，創(chuàng)建哈希表，實現(xiàn)其相關(guān)查找操作。 typedef struct int num; Elemtype; /定義查找

3、的結(jié)點元素 typedef struct Elemtype *elem; /數(shù)據(jù)元素存儲基址 int count; /數(shù)據(jù)元素個數(shù) int sizeindex; HashTable;/定義哈希表。 2. 排序相關(guān)實驗內(nèi)容及步驟。 定義記錄類型。 typedef struct int key; /關(guān)鍵字項 RecType; 實現(xiàn)直接插入排序：每次將一個待排序的記錄，按其關(guān)鍵字大小插入到前面已排序好的子文件中的適當位置，直到全部記錄插入完成為止。 實現(xiàn)冒泡排序：設(shè)想被排序的記錄數(shù)組R1n垂直排序。根據(jù)輕氣泡不能在重氣泡之下的原則，從下往上掃描數(shù)組R，凡掃描到違反本原則的輕氣泡，就使其向上“漂浮”（

4、交換），如此反復進行，直到最后任意兩個氣泡都是輕者在上，重者在下為止。 實現(xiàn)快速排序：在待排序的n個記錄中任取一個記錄（通常取第一個記錄），把該記錄作為支點（又稱基準記錄）（pivot），將所有關(guān)鍵字比它小的記錄放置在它的位置之前，將所有關(guān)鍵字比它大的記錄放置在它的位置之后(稱之為一次劃分過程)。之后對所分的兩部分分別重復上述過程，直到每部分只有一個記錄為止。 實現(xiàn)直接選擇排序：第i趟排序開始時，當前有序區(qū)和無序區(qū)分別為R1i-1和Rin（1in-1），該趟排序則是從當前無序區(qū)中選擇出關(guān)鍵字最小的記錄Rk，將它與無序區(qū)的的第一個記錄Ri交換，有序區(qū)增加一個記錄，使R1i,和Ri+1n分別為新的

5、有序區(qū)和新的無序區(qū)。如此反復進行，直到排序完畢。 實現(xiàn)堆排序：它是一種樹型選擇排序，特點是：在排序的過程中，將R1n看成是一個完全二叉樹的順序存儲結(jié)構(gòu)，利用完全二叉樹中雙親結(jié)點和孩子結(jié)點之間的內(nèi)在關(guān)系，在當前無序區(qū)中選擇關(guān)鍵字最大（或最小）的記錄。即：把待排序文件的關(guān)鍵字存放在數(shù)組R1n子中，將R看成是一棵二叉樹，每個結(jié)點表示一個記錄，源文件的第一個記錄R1作為二叉樹的根，以下各記錄R2n依次逐層從左到右排列，構(gòu)成一棵完全二叉樹，任意結(jié)點Ri的左孩子是R2i，右孩子是R2i+1，雙親是Ri/2。 實現(xiàn)二路歸并排序：假設(shè)初始序列n個記錄，則可看成是n個有序的子序列，每個子序列的長度為1，然后兩兩歸并，得到n/2個長度為2或1的有序子序列；再兩兩歸并，如此重復，直到一個長度為n的有序序列為止。 3、編寫一個主函數(shù)，