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

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

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

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

4、排序：分別按學(xué)生的學(xué)號(hào)、成績(jī)進(jìn)行排序（要求至少用實(shí)現(xiàn)直接插入排序、 冒泡排序、簡(jiǎn)單選擇排序算法）。2.實(shí)驗(yàn)過(guò)程（源代碼及描述、調(diào)試過(guò)程及分析）#in clude #in clude using n amespace std; struct stude ntint num; /學(xué)號(hào)char name20; / charbanji20; / int c; /Cint datastruct; / ;struct queue姓名班級(jí)語(yǔ)言課程成績(jī)數(shù)據(jù)結(jié)構(gòu)課程成績(jī)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,趙陽(yáng),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é)號(hào)班級(jí)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é)號(hào)班級(jí)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)/簡(jiǎn)單選擇排序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順序查找姓名為趙陽(yáng)的學(xué)生n;int i=l.seqsearch(l,趙陽(yáng));l.show(i);coute

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

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