試驗(yàn)4數(shù)據(jù)結(jié)構(gòu)報(bào)告

1、淮海工學(xué)院計(jì)算機(jī)科學(xué)系實(shí)驗(yàn)報(bào)告書(shū)課程名：數(shù)據(jù)結(jié)構(gòu)題目：查找、排序的應(yīng)用班級(jí)： 計(jì)055學(xué) 號(hào)：110511522姓名：陶冬維評(píng)語(yǔ):成績(jī)： 指導(dǎo)教師： 批閱時(shí)間：年 月 日«數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告-10 -目的與要求1. 熟悉查找表的存儲(chǔ)結(jié)構(gòu)。2. 熟練掌握順序查找和二分查找方法。3. 熟悉幾種典型的排序方法，并對(duì)各種算法的特點(diǎn)、使用范圍和效率有進(jìn)一步的了解。4. 實(shí)現(xiàn)兩種以上的簡(jiǎn)單排序和快速排序、比較它們的時(shí)間效率。5. 要求獨(dú)立完成實(shí)驗(yàn)內(nèi)容(提交程序清單、相關(guān)實(shí)驗(yàn)數(shù)據(jù)及運(yùn)行結(jié)果)；6. 要求認(rèn)真書(shū)寫(xiě)實(shí)驗(yàn)報(bào)告，并按時(shí)提交。實(shí)驗(yàn)內(nèi)容或題目1、 隨機(jī)產(chǎn)生n=100, 200, 300, 100

2、0, 2000個(gè)整數(shù)并存于數(shù)組r1.n中。對(duì)主要查找算法(順序 查找、插入排序、冒泡排序、堆排序、快速排序)進(jìn)行實(shí)驗(yàn)比較，計(jì)算出平均比較次數(shù)、平均移動(dòng)次數(shù)及執(zhí)行時(shí)間。由程序自動(dòng)計(jì)算，由手工計(jì)時(shí)。2、對(duì)實(shí)驗(yàn)結(jié)果數(shù)據(jù)進(jìn)行對(duì)比分析。實(shí)驗(yàn)步驟與源程序#include <dos.h>#include <conio.h>#include <stdio.h>#define MAX 30 /定義查找表的最大長(zhǎng)度typedef struct(char eIemMAX;int length; SSTabIe;void initial(SSTable &); /初始化線性

3、查找表int search(SSTable,char); /在線性查找表中查找元素void print(SSTable); /顯示線性查找表中所有元素void main()(SSTable ST; /ST為一線性查找表int loc,flag=1;char j,ch;initial(ST); /初始化線性查找表while(flag) ( printf("請(qǐng)選擇：n");printf("1.顯示所有元素n");printf("2,查找一個(gè)元素 n");printf("3.退出 n");scanf(" %c”

4、,&j);switch(j)(case '1':print(ST); break; / 顯示所有元素case '2':(printf("請(qǐng)輸入要查找的元素(字符)：，scanf(" %c",&ch); /輸入要查找的元素的關(guān)鍵字loc=search(ST,ch); 查找if(loc!=0) printf("該元素所在位置:%dn",loc);else printf("%c 不存在!n",ch); break;default:flag=0;printf(-程序運(yùn)行結(jié)束！按任意鍵退

5、出窗口 !n");getch();void initial(SSTable &v)(int i;printf（-請(qǐng)輸入靜態(tài)表的元素個(gè)數(shù)："）;輸入線性查找表初始化時(shí)的長(zhǎng)度 scanf("%d”,&v.length);printf("請(qǐng)輸入 %d 個(gè)元素(字符):",v.length);getchar();for(i=1;i<=v.length;i+) scanf("%c”,&v.elemi); /輸入線性查找表的各元素int search(SSTable v,char ch)/在線性查找表中查找ch的位置

6、，成功返回其位置，失敗返回0int i;v.elem0=ch; / 設(shè)置"哨兵”for(i=v.length;v.elemi!=ch;-i) ; / 從后往前找return i; 找不到時(shí)，i為0void print(SSTable v)int i;for(i=1;i<=v.length;i+) printf("%c ",v.elemi);printf("n");2、/利用插入排序、起泡排序、快速排序、選擇排序、堆排序、#include <iostream.h>#include <malloc.h>#include

7、 <stdlib.h>#define LS(a,b) (a)<(b)#define LL(a,b) (a)>(b)#define MAXSIZE 1000typedef int KeyType;typedef struct int key;RedType;typedef struct( RedType rMAXSIZE+1;int length;SqList;typedef SqList HeapType;int compare=0;int change=0;int Create_Sq(SqList &L)( int i,k;cout<<”請(qǐng)輸入產(chǎn)生

8、隨機(jī)數(shù)的個(gè)數(shù)cin>>k;L.length=k;for(i=1;i<=k;+i)( L.ri.key=rand();return 1;void Bubble_sort(SqList &L)(/冒泡排序int i,j,l,k=L.length;for(i=1;i<=L.length-1;+i)(for(j=1;j<=k-1;+j)(+compare;if(LL(L.rj.key,L.rj+1.key)(l=L.rj.key;L.rj.key=L.rj+1.key;L.rj+1.key=l;+change;一V ,k,cout<<endl<&

9、lt;"冒泡排序后的序列"<<endl;for(i=1;i<=L.length;i+)cout<<" "<<L.ri.key;cout<<endl;cout<<"冒泡排序的比較次數(shù)：”；cout<<compare<<endl;cout<<"冒泡排序的交換次數(shù)：”；cout<<change<<endl;compare=0;change=0;void InsertSort(SqList &L)(/直接插入排

10、序int i,j;cout<<endl;for(i=2;i<=L.length;+i)if(LS(L.ri.key,L.ri-1.key)(+compare;+change;L.r0=L.ri;L.ri=L.ri-1;for(j=i-2;LS(L.r0.key,L.rj.key);-j)(+compare;L.rj+1=L.rj;L.rj+1=L.r0;cout<<"直接插入排序后的序列"<<endl;for(i=1;i<=L.length;i+)cout<<" "<<L.ri.ke

11、y;cout<<endl;cout<<"直接插入排序的比較次數(shù):"cout<<compare<<endl;cout<<"直接插入排序的交換次數(shù)：”；cout<<change<<endl;compare=0;change=0;void SelectSort(SqList &L)(/簡(jiǎn)單選擇排序int l,i,j;cout<<endl;for(i=1;i<L.length;+i)(L.r0=L.ri;j=i+1;l=i;for(j;j<=L.length

12、;+j)(+compare;if(LL(L.r0.key,L.rj.key)(l=j;L.r0=L.rj;if(l!=i)+change;L.rl=L.ri;L.ri=L.r0;cout<<"簡(jiǎn)單選擇排序后的序列"<<endl;for(i=1;i<=L.length;i+)cout<<" "<<L.ri.key;cout<<endl;cout<<"簡(jiǎn)單選擇排序的比較次數(shù)："；cout<<compare<<endl;cout<&l

13、t;"簡(jiǎn)單選擇排序的交換次數(shù)：”；cout<<change<<endl;compare=0;change=0;int Partition(SqList &L,int low,int high)int pivotkey;L.r0=L.rlow;pivotkey=L.rlow.key;while(low<high)while(low<high&&L.rhigh.key>=pivotkey)+compare;-high;+change;L.rlow=L.rhigh;while(low<high&&L.r

14、low.key<=pivotkey) +compare;+low;+change;L.rhigh=L.rlow;L.rlow=L.r0;return low;void QSort(SqList &L,int low,int high)/遞歸形式的快速排序算法int pivotloc;if(low<high)pivotloc=Partition(L,low,high);QSort(L,low,pivotloc-1);QSort(L,pivotloc+1,high);void QuickSort(SqList &L)int i;QSort(L,1,L.length);c

15、out<<"快速排序后的序列為"<<endl;for(i=1;i<=L.length;i+)cout<<" "<<L.ri.key;cout<<endl;cout<<"快速排序的比較次數(shù)：”；cout<<compare<<endl;cout<<"快速排序的交換次數(shù)：”；cout<<change<<endl;compare=0;change=0;void HeapAdjust(HeapType &am

16、p;H,int s,int m)/堆排序int j;RedType rc;rc=H.rs;for(j=2*s;j<=m;j*=2)if(j<m&&LS(H.r田.key,H.rj+1.key)+compare;+j;if(!LS(rc.key,H.rj.key)+compare;break;H.rs=H.rj;s=j;H.rs=rc;void HeapSort(HeapType &H)int i;for(i=H.length/2;i>0;-i)HeapAdjust(H,i,H.length);for(i=H.length;i>1;-i)(+cha

17、nge;H.r0=H.r1;H.r1=H.ri;H.ri=H.r0;HeapAdjust(H,1,i-1);cout<<”堆排序后的序列為"<<endl;for(i=1;i<=H.length;i+)cout<<" "<<H.ri.key;cout<<endl;cout<<"堆排序的比較次數(shù)：”；cout<<compare<<endl;cout<<"堆排序的交換次數(shù)：”；cout<<change<<endl;

18、compare=0;change=0;void main()(int i;int dltaMAXSIZE;SqList L;Create_Sq(L);cout<<"待排序序列為"<<endl;for(i=1;i<=L.length;i+)cout<<" "<<L.ri.key;冒泡排v序SqList L1=L;Bubble_sort(L1);直接插入排序SqList L2=L;InsertSort(L2);簡(jiǎn)單選擇排序SqList L3=L;SelectSort(L3);快速排序SqList L4=L;QuickSort(L4);堆排序SqList L6=L;HeapSort(L6);測(cè)試數(shù)據(jù)與實(shí)驗(yàn)結(jié)果（可以抓圖粘貼）21數(shù)& 結(jié)御、實(shí)碧A4 內(nèi) Debugschazhao .exe"結(jié)果分析與實(shí)驗(yàn)體會(huì)這次實(shí)驗(yàn)是查找和排序的綜合。實(shí)驗(yàn)的目的是掌握順序查找和二分查找方法和對(duì)各種排序方法 的掌握，并通過(guò)實(shí)際的應(yīng)用來(lái)實(shí)現(xiàn)。五種內(nèi)排序算法，它們是：直接插入排序