试验4数据结构报告

1、淮海工学院计算机科学系实验报告书课程名：数据结构题目：查找、排序的应用班级：计055学号：110511522姓名：陶冬维评语:成绩：指导教师：批阅时间:目的与要求1,熟悉查找表的存储结构。2.熟练掌握顺序查找和二分查找方法。3,熟悉几种典型的排序方法，并对各种算法的特点、使用范围和效率有进一步的了解。4,实现两种以上的简单排序和快速排序、比较它们的时间效率。5,要求独立完成实验内容(提交程序清单、相关实验数据及运行结果)；6.要求认真书写实验报告，并按时提交。实验内容或题目I、随机产生n=100,200,300,1000,2000个整数并存于数组r1,n中。对主要查找算法(顺序查找、插入排序、

2、冒泡排序、堆排序、快速排序)进行实验比较，计算出平均比较次数、平均移动次数及执行时间。由程序自动计算，由手工计时。2、对实验结果数据进行对比分析。实验步骤与源程序#include<dos,h>#include<conio,h>#include<stdio,h>#defineMAX30/定义查找表的最大长度typedefstructchareIemMAX;intlength;SSTabIe;voidinitial(SSTable&);/初始化线性查找表intsearch(SSTable,char);/在线性查找表中查找元素voidprint(SSTab

3、le);/显示线性查找表中所有元素voidmain()SSTableST;/ST为一线性查找表intloc,flag=1;charj,ch;initial(ST);/初始化线性查找表while(flag)printf("请选择：n");printf("1.显示所有元素n");printf("2.查找一个元素n");printf("3.退出n");scanf("%c",&j);switch(j)case'1':print(ST);break;/显示所有元素case'

4、2':printf("请输入要查找的元素(字符)：");scanf("%c",&ch);输入要查找的元素的关键字loc=search(ST,ch);查找if(loc!=0)printf("该元素所在位置：%dn",loc);elseprintf("%c不存在！n",ch);break;default:flag=0;printf("程序运行结束！按任意键退出窗口!n");getch();voidinitial(SSTable&v)inti;printf（"请输入静

5、态表的元素个数："）;输入线性查找表初始化时的长度scanf("%d",&v.length);printf("请输入%d个元素(字符):",v.length);getchar();for(i=1;i<=v.length;i+)scanf("%c",&v.elemi);/输入线性查找表的各元素intsearch(SSTablev,charch)/在线性查找表中查找ch的位置，成功返回其位置，失败返回0inti;v.elem0=ch;/设置"哨兵"for(i=v.length;v.ele

6、mi!=ch;-i);/从后往前找returni;找不到时，i为0voidprint(SSTablev)inti;for(i=1;i<=v.length;i+)printf("%c",v.elemi);printf("n");2、/利用插入排序、起泡排序、快速排序、选择排序、堆排序、#include<iostream.h>#include<malloc.h>#include<stdlib.h>#defineLS(a,b)(a)<(b)#defineLL(a,b)(a)>(b)#defineMAXSIZ

7、E1000typedefintKeyType;typedefstructintkey;RedType;typedefstructRedTyperMAXSIZE+1;intlength;SqList;typedefSqListHeapType;intcompare=0;intchange=0;intCreate_Sq(SqList&L)inti,k;cout<<"请输入产生随机数的个数："；cin>>k;L.length=k;for(i=1;i<=k;+i)L.ri.key=rand();return1;voidBubble_sort(S

8、qList&L)/冒泡排序inti,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;-k;cout<<endl<<"冒泡排序后的序列"<<endl;for(i=1;i<=L.length;i+)cout<<""<<L.ri.key;

9、cout<<endl;cout<<"冒泡排序的比较次数："；cout<<compare<<endl;cout<<"冒泡排序的交换次数："；cout<<change<<endl;compare=0;change=0;voidInsertSort(SqList&L)/直接插入排序inti,j;cout<<endl;for(i=2;i<=L.length;+i)if(LS(L.ri.key,L.ri-1.key)(+compare;+change;L.

10、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.key;cout<<endl;cout<<"直接插入排序的比较次数："；cout<<compare<<endl;cout<<

11、;"直接插入排序的交换次数："；cout<<change<<endl;compare=0;change=0;voidSelectSort(SqList&L)/简单选择排序intl,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;+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<&l

12、t;"简单选择排序后的序列"<<endl;for(i=1;i<=L.length;i+)cout<<""<<L.ri.key;cout<<endl;cout<<"简单选择排序的比较次数："；cout<<compare<<endl;cout<<"简单选择排序的交换次数："；cout<<change<<endl;compare=0;change=0;)intPartition(SqList&am

13、p;L,intlow,inthigh)intpivotkey;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.rlow.key<=pivotkey)+compare;+low;)+change;L.rhigh=L.rlow;)L.rlow=L.r0;returnlow;)voidQSort(SqLis

14、t&L,intlow,inthigh)/递归形式的快速排序算法intpivotloc;if(low<high)pivotloc=Partition(L,low,high);QSort(L,low,pivotloc-1);QSort(L,pivotloc+1,high);)voidQuickSort(SqList&L)(inti;QSort(L,1,L.length);cout<<"快速排序后的序列为"<<endl;for(i=1;i<=L.length;i+)cout<<""<<

15、L.ri.key;cout<<endl;cout<<"快速排序的比较次数："；cout<<compare<<endl;cout<<"快速排序的交换次数："；cout<<change<<endl;compare=0;change=0;)voidHeapAdjust(HeapType&H,ints,intm)/堆排序intj;RedTyperc;rc=H.rs;for(j=2*s;j<=m;j*=2)if(j<m&&LS(H.rj.key,

16、H.rj+1.key)+compare;+j;)if(!LS(rc.key,H.rj.key)+compare;break;)H.rs=H.rj;s=j;)H.rs=rc;)voidHeapSort(HeapType&H)inti;for(i=H.length/2;i>0;-i)HeapAdjust(H,i,H.length);for(i=H.length;i>1;-i)(+change;H.r0=H.r1;H.r1=H.ri;H.ri=H.r0;HeapAdjust(H,1,i-1);cout<<"堆排序后的序列为"<<endl

17、;for(i=1;i<=H.length;i+)cout<<""<<H.ri.key;cout<<endl;cout<<"堆排序的比较次数："；cout<<compare<<endl;cout<<"堆排序的交换次数："；cout<<change<<endl;compare=0;change=0;voidmain()(inti;intdltaMAXSIZE;SqListL;Create_Sq(L);cout<<&

18、quot;待排序序列为"<<endl;for(i=1;i<=L.length;i+)cout<<""<<L.ri.key;冒泡排v序SqListL1=L;Bubble_sort(L1);直接插入排序SqListL2=L;InsertSort(L2);简单选择排序SqListL3=L;SelectSort(L3);快速排序SqListL4=L;QuickSort(L4);堆排序SqListL6=L;HeapSort(L6);测试数据与实验结果（可以抓图粘贴）国数&结构、实要4内容日口.exe"结果分析与实验体会这次实验是查找和排序的综合。实验的目的是掌握顺序查找和二分查找方法和对各种排序方法的掌握，并通过实际的应用来实现。五种内排序算法，它们是：直接插入排序