數(shù)據(jù)結(jié)構(gòu)實驗五

1、實驗題目：姓名：數(shù)據(jù)結(jié)構(gòu)實驗報告實驗五、查找排序?qū)W號：142054301班級：1420543系名：計算機工程系專業(yè)：計算機科學(xué)與技術(shù)指導(dǎo)老師：實驗時間:2016年6月14日實驗地點：專業(yè)軟件實驗室【實驗概述】1.實驗?zāi)康募耙竽康模?.掌握哈希表的定義，哈希函數(shù)的構(gòu)造方法。2掌握并比較各種排序算法。要求：預(yù)習(xí)并掌握查找的概念、靜態(tài)查找與動態(tài)查找、順序查找、二分查找、索引查找、 二叉排序樹的概念、平衡二叉樹、哈希查找、直接插入排序、快速排序、冒泡排序、 簡單選擇排序等算法思想。2.實驗原理1、樹的邏輯結(jié)構(gòu)特點：樹(tree)是n(n0)個結(jié)點的有限集T,其中：(1) 有且僅有一個特定的結(jié)點，稱為

2、樹的根(root);(2) 當(dāng)n1時，其余結(jié)點可分為m(m0個互不相交的有限集T1,T2,Tm其中 每一個集合本身又是一棵樹，稱為根的子樹(subtree)。2、樹結(jié)構(gòu)中的基本術(shù)語，以及樹的樹形結(jié)構(gòu)表示。3、二叉樹的邏輯結(jié)構(gòu)特點:1、查找和排序是日常數(shù)據(jù)處理過程中經(jīng)常要進行的操作和運算。2、查找是根據(jù)給定的某個值，在查找表中確定一個其關(guān)鍵字等于給定值的數(shù)據(jù)元素或（記錄）。若查找表中存在這樣一個記錄，則稱“查找成功”，查找結(jié)果：給出 整個記錄的信息，或指示該記錄在查找表中的位置；否則稱“查找不成功”，查找結(jié)果：給出“空記錄”或“空指針”。3、靜態(tài)查找與動態(tài)查找的區(qū)別。平均查找長度。4、查找算法有

3、：靜態(tài)查找中常見的查找算法：順序查找、二分查找、索引查找。動態(tài)查找中常見的算法有二叉排序樹和平衡二叉樹上的查找。平均查找長度為0的哈希查找。5、排序是是將一組“無序”的記錄序列調(diào)整為“有序”的記錄序列。6、排序算法的優(yōu)劣從空間復(fù)雜度、時間復(fù)雜度、穩(wěn)定性三個角度分析。7、常見的排序算法可分為：插入類、交換類、選擇類、歸并排序、基數(shù)排序等。3.實驗環(huán)境（使用的軟件）VC+6.0【實驗內(nèi)容】1.實驗算法設(shè)計設(shè)計一個學(xué)生信息管理系統(tǒng)，學(xué)生對象至少要包含：學(xué)號、姓名、成績等信息。 要求實現(xiàn)以下功能：1、 查找：分別給定學(xué)生學(xué)號、姓名，能夠查找到學(xué)生的基本信息（要求至少實 現(xiàn)改進后的順序查找算法）；2、

4、排序：分別按學(xué)生的學(xué)號、成績進行排序（要求至少用實現(xiàn)直接插入排序、 冒泡排序、簡單選擇排序算法）。2.實驗過程（源代碼及描述、調(diào)試過程及分析）#in clude #in clude using n amespace std; struct stude ntint num; /學(xué)號char name20; / charbanji20; / int c; /Cint datastruct; / ;struct queue姓名班級語言課程成績數(shù)據(jù)結(jié)構(gòu)課程成績struct stude nt a8;in t le nth;；class listprivate:queue d;public:int seq

5、search(list,char *);int bin search(list,i nt, in t,i nt);void in sertsort(list);void selectsort(list);void bubblesort(list);list();void display(list);void show(i nt);list:list()struct stude nt e8=1,王麗,03511,85,76,2,張秋,03511,78,77,3,劉麗,03511,90,79,4,王童,03511,75,86,5,趙陽,03511,60,71,6,李艷,03511,58,68,7,

6、錢娜,03511,95,89,8,孫勝,03511,45,60,；for(int i=0;i8;i+)d.ai=ei;void list:show(i nt i)if(i=-1)coutsorry not foun d!e ndl;elsecout學(xué)號班級vvc+v數(shù)據(jù)結(jié)構(gòu)n;coutvvd.ai. num;coutd.ai. name;coutd.ai.banji;coutd.ai.datastruct;coutd.ai.ce ndl;void list:display(list I)cout學(xué)號班級vvc+v數(shù)據(jù)結(jié)構(gòu)n;for(int i=0;i8;i+)coutvvvl.d.ai. nu

7、 m;coutl.d.ai. name;coutvl.d.ai.banjivv;coutl.d.ai.datastruct;coutl.d.ai.ce ndl;int list:seqsearch(list l,char n ame20)for(int i=0;i8;i+)if(strcmp(l.d.ai. name, name)=0)return i;return -1;void list:i nsertsort(list l)順序查找直接插入排序struct stude nt n;for(int i=1;i=0&strcmp( n.n ame,l.d.aj. name)0)l.d.

8、aj+1=l.d.aj;j-;l.d.aj+1=n;display(l);void list:selectsort(list l)/簡單選擇排序for(i nt i=0;i7;i+)int j=i;for(int k=j;k8;k+)if(l.d.aj.c0;i-)for(i nt j=0;jl.d.aj+1.datastruct)stude nt d=l.d.aj;l.d.aj=l.d.ai+1;l.d.aj+1=d;display(l);void main()list l;coutvv順序查找姓名為趙陽的學(xué)生n;int i=l.seqsearch(l,趙陽);l.show(i);coute

9、 ndl;coutvv直接插入排序?qū)π彰M行排序n;cout排序前的結(jié)果：n;l.display(l);coutvv排序后的結(jié)果：n;l. i nsertsort (l);coutvve ndl;coutvv簡單選擇排序?qū)語言成績進行排序n;coutvv排序前的結(jié)果：n;l.display(l);coutvv排序后的結(jié)果：n;l.selectsort(l);11入的級HH秋Bn童陽艷那勝的級遇舸娜勝麗璧秋陽音插前班壬張劉壬趙李錢孫后班李劉錢孫王王張趙拼接序號序號起則3535353535353535法71688968G879G879的G076G076場coute ndl;coutvv冒泡排序?qū)?/p>

10、數(shù)據(jù)結(jié)構(gòu)成績進行排序n;cout排序前的結(jié)果：n;l.display(l);cout排序后的結(jié)果：n;l.bubblesort(l);coute ndl;3.結(jié)果與結(jié)論(實驗結(jié)果截圖、結(jié)論總結(jié))C:LJ sersa susDe s ktapDe bug1. exe順.序査喪姓名為趙陽的學(xué)生 學(xué)號班級 b*數(shù)據(jù)結(jié)枸5趙陽935117160ZI* C1U$ ers as u sD e? lrtopDebug1. exeXI王宣風(fēng)陽孫勝-序F曲菇卑；愕號班級屮鮎結(jié)構(gòu)r刪1利麗1干那2張秋P主童5就陽6李輔6別海fi03511Q3511035119351 1Q3S1103511onii53511035110351103511伽11835110351103S11Q3511爵7890756G帖45斡55H5C:UsersasusDesktopDebug1.exe通過該實驗，我掌握了查找的