數(shù)據(jù)結(jié)構(gòu)查找排序?qū)嶒?yàn)報(bào)告

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

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

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

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

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