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

1、數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)題目： 實(shí)驗(yàn)五、查找排序 姓名： 學(xué)號(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)查找、順序查找、二分查找、索引查找、二叉排序樹的概念、平衡二叉樹、哈希查找、直接插入排序、快速排序、冒泡排序、簡(jiǎn)單選擇排序等算法思想。2.實(shí)驗(yàn)原理1、樹的邏輯結(jié)構(gòu)特點(diǎn)：樹(tree)是n(n0)個(gè)結(jié)點(diǎn)的有限集T，其中：（1）有且

2、僅有一個(gè)特定的結(jié)點(diǎn)，稱為樹的根(root)；（2）當(dāng)n>1時(shí)，其余結(jié)點(diǎn)可分為m(m>0)個(gè)互不相交的有限集T1,T2,Tm，其中每一個(gè)集合本身又是一棵樹，稱為根的子樹(subtree)。2、樹結(jié)構(gòu)中的基本術(shù)語，以及樹的樹形結(jié)構(gòu)表示。3、二叉樹的邏輯結(jié)構(gòu)特點(diǎn)：1、查找和排序是日常數(shù)據(jù)處理過程中經(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)查

3、找的區(qū)別。平均查找長(zhǎng)度。4、查找算法有：靜態(tài)查找中常見的查找算法：順序查找、二分查找、索引查找。動(dòng)態(tài)查找中常見的算法有二叉排序樹和平衡二叉樹上的查找。平均查找長(zhǎng)度為0的哈希查找。5、排序是是將一組“無序”的記錄序列調(diào)整為“有序”的記錄序列。6、排序算法的優(yōu)劣從空間復(fù)雜度、時(shí)間復(fù)雜度、穩(wěn)定性三個(gè)角度分析。7、常見的排序算法可分為：插入類、交換類、選擇類、歸并排序、基數(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é)生的基本信息（要求至少

4、實(shí)現(xiàn)改進(jìn)后的順序查找算法）；2、排序：分別按學(xué)生的學(xué)號(hào)、成績(jī)進(jìn)行排序（要求至少用實(shí)現(xiàn)直接插入排序、冒泡排序、簡(jiǎn)單選擇排序算法）。2.實(shí)驗(yàn)過程（源代碼及描述、調(diào)試過程及分析）#include<iostream>#include<string>using namespace std;struct studentint num; /學(xué)號(hào)char name20; /姓名char banji20; /班級(jí)int c; /C語言課程成績(jī)int datastruct; /數(shù)據(jù)結(jié)構(gòu)課程成績(jī);struct queuestruct student a8;int lenth;class li

5、stprivate:queue d;public:int seqsearch(list,char *);int binsearch(list,int,int,int);void insertsort(list); void selectsort(list); void bubblesort(list);list();void display(list);void show(int);list:list()struct student e8=1,"王麗","03511",85,76,2,"張秋","03511",78

6、,77,3,"劉麗","03511",90,79,4,"王童","03511",75,86,5,"趙陽","03511",60,71,6,"李艷","03511",58,68,7,"錢娜","03511",95,89,8,"孫勝","03511",45,60,;for(int i=0;i<8;i+)d.ai=ei;void list:show(int

7、i)if(i=-1)cout<<"sorry not found!"<<endl;elsecout<<"學(xué)號(hào)"<<"班級(jí)"<<"c+"<<"數(shù)據(jù)結(jié)構(gòu)n"cout<<""<<d.ai.num<<" " cout<<<<" "cout<<d.ai.banji<<&quo

8、t; "cout<<d.ai.datastruct<<" "cout<<d.ai.c<<endl;void list:display(list l)cout<<"學(xué)號(hào)"<<"班級(jí)"<<"c+"<<"數(shù)據(jù)結(jié)構(gòu)n"for(int i=0;i<8;i+)cout<<""<<l.d.ai.num<<" " cout&l

9、t;<<<" "cout<<l.d.ai.banji<<" "cout<<l.d.ai.datastruct<<" "cout<<l.d.ai.c<<endl;int list:seqsearch(list l,char name20)/順序查找for(int i=0;i<8;i+)if(strcmp(,name)=0)return i;return -1;void list:insertsort

10、(list l)/直接插入排序struct student n;for(int i=1;i<8;i+)n=l.d.ai;int j=i-1;while(j>=0&&strcmp(,)<0)l.d.aj+1=l.d.aj;j-;l.d.aj+1=n;display(l);void list:selectsort(list l)/簡(jiǎn)單選擇排序for(int i=0;i<7;i+)int j=i;for(int k=j;k<8;k+)if(l.d.aj.c<l.d.ak+1.c)j=k+1;if(j!=i)stud

11、ent s=l.d.ai;l.d.ai=l.d.aj;l.d.aj=s;display(l);void list:bubblesort(list l)/冒泡排序for(int i=7;i>0;i-) for(int j=0;j<i;j+)if(l.d.aj.datastruct>l.d.aj+1.datastruct)student d=l.d.aj;l.d.aj=l.d.ai+1;l.d.aj+1=d;display(l);void main()list l;cout<<"順序查找姓名為趙陽的學(xué)生n"int i=l.seqsearch(l,&

12、quot;趙陽");l.show(i);cout<<endl;cout<<"直接插入排序?qū)π彰M(jìn)行排序n" cout<<"排序前的結(jié)果：n"l.display(l);cout<<"排序后的結(jié)果：n"l. insertsort (l);cout<<endl;cout<<"簡(jiǎn)單選擇排序?qū)語言成績(jī)進(jìn)行排序n" cout<<"排序前的結(jié)果：n"l.display(l);cout<<"排序后的結(jié)果：n"l.selectsort(l);cout<<endl;cout<<"冒泡排序?qū)?shù)據(jù)結(jié)構(gòu)成績(jī)進(jìn)行排序n" cout<<"排序前的結(jié)果：n