数据结构实验报告-排序与查找

电子科技大学

实验报告

学生姓名:XXX 学号:2013220501018指导教师:刘峤

实验地点:信软机房306实验时间:2014/6/20

一、实验室名称:软件实验室

二、实验项目名称:数据结构与算法—排序与查找

三、实验学时:4

四、实验原理:

快速排序的基本思想是:通过一躺排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一不部分的所有数据都要小,然后再按次方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。

假设要排序的数组是A[1]……A[N],首先任意选取一个数据(通常选用第一个数据)作为关键数据,然后将所有比它的数都放到它前面,所有比它大的数都放到它后面,这个过程称为一躺快速排序。一躺快速排序的算法是:

1)设置两个变量I、J,排序开始的时候I:=1,J:=N

2)以第一个数组元素作为关键数据,赋值给X,即X:=A[1];

3)从J开始向前搜索,即(J:=J-1),找到第一个小于X的值,两者交换;

4)从I开始向后搜索,即(I:=I+1),找到第一个大于X的值,两者交换;

5)重复第3、4步,直到I=J。

二分法查找(折半查找)的基本思想:

(1)确定该区间的中点位置:mid=(low+high)/2

min代表区间中间的结点的位置,low代表区间最左结点位置,high代表区间最右结点位置(2)将待查a值与结点mid的关键字(下面用R[mid].key)比较,若相等,则查找成功,否则确定新的查找区间:

A)如果R[mid].key>a,则由表的有序性可知,R[mid].key右侧的值都大于a,所以等于a的关键字如果存在,必然在R[mid].key左边的表中,这时high=mid-1;

B)如果R[mid].key

C)如果R[mid].key=a,则查找成功。

(3)下一次查找针对新的查找区间,重复步骤(1)和(2)

(4)在查找过程中,low逐步增加,high逐步减少,如果high

五、实验目的:

本实验通过实现快速排序和折半查找算法,使学生理解如何实现快速查找和排序的基本算法思想。通过练习,加强对算法的理解,提高编程能力。

六、实验内容:

(1)实现数据序列的输入;

(2)实现快速排序算法,并对输入的序列排序后输出;

(3)实现折半查找算法,并在步骤(2)排序后的序列上,进行任意地查找,并输出查询结果。

七、实验器材(设备、元器件):

PC机一台,装有C/C++语言集成开发环境。

八、数据结构及程序

#include

#define MAX_LEN 100

void Sort(int *data,int left,int right)

{

int i,j,temp;

i=left;

j=right;

temp=data[left];

if(left>right)

return;

while(i!=j){

while(data[j]>=temp&&j>i)

j--;

if(j>i)

data[i++]=data[j];

while(data[i]<=temp&&j>i)

i++;

if(j>i)

data[j--]=data[i];

}

data[i]=temp;

Sort(data,left,i-1);

Sort(data,i+1,right);

}

int Search(int *data,int start,int end,int key,int num)

{

int result;

int p = (start + end) / 2;

if (data[p] == key&&start<=end) {

result = p;

num++;

if (data[p] > key)

result = Search(data, start, p, key,num);

else

result = Search(data, p + 1, end, key,num);

return result;

}

else if (num==0&&start>end){

result = -1;

printf("\n 404 NO FOUND\n");

return result;

}

else if (num!=0&&start>end){

result=-1;

if (num==1)

printf("\nFounded number only one");

else

printf("\nFounded number more than one");

return result;

}

else if (result!=-1) {

if (data[p] > key)

result = Search(data, start, p - 1, key, num);

else

result = Search(data, p + 1, end, key, num);

return result;

}

else {

result=-1;

return result;

}

}

void loadFile(int *data,char *filename,int n){

int i;

FILE *pfile=NULL;

pfile=fopen(filename,"r");

if (!pfile){

printf("Open file fail\n");

exit(0);

}

else

printf("Open file success!\n");

for(i = 0 ; i < n; i++)

fscanf(pfile , "%d ",&data[i]);

}

int main(int argc, const char * argv[]) {

int input=1,data[MAX_LEN],num=0,key=1,i,cmd;

char filename[100];

printf("Choose Mode :\n 1.Input Mode 2.File Mode\n");

scanf("%d",&cmd);

if (cmd==1) {

printf("Input data :(Enter 0 to detemine)\n");

while (input!=0) {

printf("Enter the %d data :",num+1);

scanf("%d",&input);

if (input!=0){

data[num]=input;

num++;

}

}

}

else{

printf("\nInput the address of the file: ");

scanf("%s",filename);

printf("\nInput the number of elem: ");

scanf("%d",&num);

loadFile(data,filename,--num);

}

Sort(data, 0, num);

printf("\nSort result: ");

for (i=1; i<=num; i++)

printf("%d ",data[i]);

printf("\n\n");

while (key!=0) {

printf("\nInput a key to search :(Enter 0 to detemine)");

scanf("%d",&key);

if (key!=0)

Search(data, 0, num, key, 0);

}

return 0;

}

九、程序运行结果:

1.打开程序:

数据结构实验报告-排序与查找

2.尝试手动输入模式:

数据结构实验报告-排序与查找

3.搜索已存在数:

数据结构实验报告-排序与查找

4.搜索不存在数:

数据结构实验报告-排序与查找

5.尝试文件读入模式并搜索

数据结构实验报告-排序与查找

实验成功。

十、实验结论:

使用好的排序与查找算法对于程序的运行效率至关重要,一个好的算法,适合的算法能使计算机对数据的处理事半功倍,而选用错误的算法,不但可能事倍功半,还有可能造成不稳定因素。

快速排序的时间复杂度为n(log2n),是排序算法中最为快速的一种,但是不稳定,对基本有序的序列效率较差。

二分查找算法在查找算法中,速度快,效率高,但是要求数据要有序。

十一、总结及心得体会:

当空间充足,对稳定性要求不高的情况,排序算法宜使用快速排序。

快速排序和二分查找配合,可以以较高的效率查找目标元素。

相关推荐
相关主题
热门推荐