电子科技大学

实   验   报   告

             课程名称：   数据结构与算法      

            学生姓名：                

            学    号：           

            点名序号：                    

            指导教师：               

            实验地点：    基础实验大楼          

            实验时间：       5月20日       

20##-20##-2学期

  信息与软件工程学院

实   验   报   告（二）

学生姓名 学号：指导教师：

实验地点：  基础实验大楼              实验时间：5月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<a,则等于a的关键字如果存在，必然在R[mid].key右边的表中。这时low=mid；

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

   （3）下一次查找针对新的查找区间，重复步骤（1）和（2）

   （4）在查找过程中，low逐步增加，high逐步减少，如果high<low，则查找失败。

五、实验目的：

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

六、实验内容：

（1）实现数据序列的输入;

   （2）实现快速排序算法,并对输入的序列排序后输出；

   （3）实现折半查找算法,并在步骤(2)排序后的序列上,进行任意地

查找,并输出查询结果。

七、实验器材（设备、元器件）：

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

八、数据结构与程序：

#include<stdio.h>

#include<stdlib.h>

#define MAX 1000

#define FROMFILE 1

typedef struct JD{

    int key;

}JD;

int binsrch(JD r[],int n,int k)

{  int low,high,mid,found;

   low=1;  high=n; found=0;

   while((low<=high)&&(found==0))

   {  mid=(low+high)/2;

      if(k>r[mid].key)  low=mid+1;

      else if(k==r[mid].key)  found=1;

      else   high=mid-1;

   }

   if(found==1)

      return(mid);

   else

      return(0);

}

void quicksort(JD r[],int low,int high){

    int i,j,k;

    JD x;

    if(low>=high)return;

    i=low;

    j=high;

    x=r[i];

    while(i<j){

        while((i<j)&&(r[j].key>=x.key))j--;

        if(i<j){r[i]=r[j];i++;}

        while((i<j)&&(r[i].key<=x.key))i++;

        if(i<j){r[j]=r[i];j--;}

    }

    r[i]=x;

    quicksort(r,low,j-1);

    quicksort(r,j+1,high);

}//快速排序

int main(){

    printf("欢迎使用快速排序与二分查找。\n\n");

    #ifdef FROMFILE

    printf("请输入你所要查找的数组长度:");

    int length;

    scanf("%d",&length);

    getchar();

    JD a[length+1];

    a[0].key=0;

    int i;

    for(i=1;i<=length;i++){

        printf("输入第%d个数字:",i);

        scanf("%d",&a[i].key);

        getchar();

    }

    #else

    FILE *fp;

    fp = fopen("test.txt","r");

    if(!fp)

    {

      printf("文件不存在!");

      return 0;

    }

   

    JD a[MAX];

    a[0].key=0;

    int i=1;

    while (fscanf(fp,"%d",&a[i++].key)!=EOF);

   

    int length=i-1;

   

    printf("文件内的信息:");

    for (i=1;i<length;i++) {

      printf("%d ",a[i].key);

    }

    printf("\n");

   

    length--;

   

    fclose(fp);

   

    #endif

   

    quicksort(a,0,length);

    printf("\n");

    int key;

    printf("请输入你想查找的数字:");

    scanf("%d",&key);

    getchar();

    printf("\n");

    int location=binsrch(a,length,key);

    printf("位置 :");

    for(i=1;i<=length;i++){

        printf("%3d  ",i);

    }

    printf("\n");

    printf("数字 :");

    for(i=1;i<=length;i++){

        printf("%3d  ",a[i].key);

    }

    printf("\n");

   

    if(location){

        int count=0;

        printf("目标数字出现的位置:");

        for (i=1;i<=length;i++) {

          if (a[i].key==a[location].key) {

            printf("%d ",i);

            count++;

          }

        }

        printf("\n数字%d出现的次数:%d\n",a[location].key,count);

    }

    else{

        printf("该数字不存在!\n\n");

    }

    return 0;

}

九、程序运行结果：

十、实验结论：

    此次操作证明可以用编程实现快速排序并在其后进行二分查找，实验结果正确。

十一、总结及心得体会：

通过本次实验，我对快速排序与二分查找有了更加深刻的了解。我尝试了书上没有的结构体，使自己的感觉丰富了许多，耳目一新，加深了我对学习编程的兴趣。练习了结构体、指针排序、查找等操作，熟练掌握树的操作。对知识的巩固与加深起到了很大的作用，我受益匪浅。

 

第二篇：排序问题实验报告

20##级数据结构实验报告

实验名称： 排序

姓    名：袁彬

班    级： 2009211120

班内序号： 09

学    号： 09210552

日    期： 2010  年12  月19  日

1． 实验要求

试验目的：

通过选择试验内容中的两个题目之一，学习、实现、对比各种排序的算法，掌握各种排序算法的优缺点，以及各种算法使用的情况。

试验内容：

题目一：

使用简单数组实现下面各种排序算法，并进行比较。

排序算法如下：

①插入排序；

②希尔排序

③冒泡排序；

④快速排序；

⑤简单选择排序；

⑥堆排序

⑦归并排序

⑧基数排序

⑨其他。

具体要求如下：

①测试数据分为三类：正序，逆序，随机数据。

②对于这三类数据，比较上述排序算法中关键字的比较次数和移动次数（其中关键字交换记为三次移动）。

③对于这三类数据，比较上述排序算法中不同算法的执行时间，精确到微妙。

④对②和③的结果进行分析，验证上述各种算法的时间复杂度。

⑤编写main()函数测试各种排序算法的正确性。

题目二：

使用链表实现下面各种排序算法，并进行比较。

排序算法如下：

①插入排序；

②冒泡排序；

③快速排序；

④简单选择排序；

⑤其他。

具体要求如下：

①测试数据分为三类：正序，逆序，随机数据。

②对于这三类数据，比较上述排序算法中关键字的比较次数和移动次数（其中关键字交换记为三次移动）。

③对于这三类数据，比较上述排序算法中不同算法的执行时间，精确到微妙（选作）

④对②和③的结果进行分析，验证上述各种算法的时间复杂度。

⑤编写main()函数测试各种排序算法的正确性。

2. 程序分析

2.1 存储结构

程序中每一个算法均是用一个类来表示的，类中有自己的构造函数、排序函数。

程序的储存结构采用数组。数组的第一个位置不存储数据。数据从第二个位置开始。数组中的相对位置为数组的下标。   

2.2 关键算法分析

㈠、关键算法：

1、 插入排序函数：Insertsort(int n)

①、从2开始做循环，依次和前面的数进行比较：for(int i=2;i<=n;i++)

②、如果后面的比前面的小，则进行前移：if(number[i]<number[i-1])

③、设置哨兵：number[0]=number[i];

④、如果后面的比前面的小，前面的进行后移：for(j=i-1;number[0]<number[j];j--)

⑤、前面的进行后移：number[j+1]=number[j];

⑥、将比较的数据放置到正确位置：number[j+1]=number[0];

2、希尔排序函数：Shellinsert(int n)

①、以长度的一半为间隔进行循环：for(int d=n/2;d>=1;d=d/2)

②、在自己的间隔中进行简单插入排序，进行循环：for(int i=d+1;i<=n;i++)

③、如果后面的数据比前面的小，进行前移：if(number[i]<number[i-d])    

④、设置哨兵：number[0]=number[i];

⑤、在自己的间隔中进行简单插入排序：for(j=i-d;number[0]<number[j]&&j>0;j=j-d)

⑥、大的数据后移：number[j+d]=number[j];

⑦、哨兵归位：number[j+d]=number[0];

3、冒泡排序函数：Bubblesort(int n)

①、设置有序无序的边界点：int pos=n;

②、当边界点不为空进行循环：while(pos!=0)

③、边界点传递给bound：int bound=pos;   

④、从开始到边界点进行循环：for(int i=1;i<bound;i++)

⑤、如果前面的数据比后面的大，进行交换：if(number[i]>number[i+1])

⑥、交换：number[0]=number[i];number[i]=number[i+1];number[i+1]=number[0];

⑦、从小设置边界点：pos=i;

4、一趟快速排序函数：partion(int first,int end)

①、传递设置整个数据的起点和终点：int i=first;int j=end;

②、设置中轴：number[0]=number[i];

③、当end大于first进行循环：while(i<j)

④、当后面的数据大于中轴，后面的游标前移：while((i<j)&&(number[j]>=number[0]))                           j--;

⑤、中轴和比它大的数据进行交换：number[i]=number[j];

⑥、当前面的数据小于中轴，前面的游标后移：while((i<j)&&(number[i]<=number[0])) i++;

⑦、中轴和比它小的数据进行交换：number[j]=number[i];

⑧、将中轴进行归位：number[i]=number[0];

5、递归快速排序函数：Qsort(int i,int j)

①、 如果数组不为空，进行排序：if(i<j)

②、 一趟冒泡排序：int pivotloc=partion(i,j);

③、递归将左右半面进行排序：Qsort(i,pivotloc-1); Qsort(pivotloc+1,j);

6、简单选择排序函数：Selectsort(int n)

①、从数组开始到结尾进行遍历：for(int i=1;i<n;i++)

②、设置最小数据标记：int index=i;

③、在无序区进行循环：for(int j=i+1;j<=n;j++)

④、当出现比标记还小的数据，就进行交换：if(number[j]<number[index]) index=j;

⑤、如果最小的不是末尾的数，就进行交换：if(index!=i)

⑥、进行交换：                                                                               

number[0]=number[i];number[i]=number[index];number[index]=number[0];

7、一趟堆排序函数：sift(int k,int m)

①、设置根节点和孩子的位置：int i=k,j=2*k;

②、从左右孩子中选择出最小的孩子：if(j<m&&number[j]>number[j+1]) j++;

③、判断根节点是不是最小的，不是就进行交换：if(number[i]<number[j]) break;

④、进行交换：number[0]=number[i];number[i]=number[j];number[j]=number[0];

⑤、将根节点和孩子位置后移，继续排序：i=j;j=2*i;

8、递归堆排序函数：Heapsort(int n)

① 、从最大非叶子节点，进行一趟堆排序：for(i=n/2;i>=1;i--)

②、进行数组长度值的循环：for(i=1;i<n;i++)

③、 将根节点和尾节点进行交换：number[0]=number[1];number[1]=number[n-i+1];number[n-i+1]=number[0];

④、 在进行一趟堆排序：sift(1,n-i);

 9、一趟归并排序函数：Merge(int *r, int *r1, int s, int m, int t)

①、传递设置两个数组的起点和终点：int i=s;int j=m+1;int k=s;

②、当任意一个数组没有达到终点时，进行循环：while(i<=m&&j<=t)

③、进行循环，将较小的值传给r1数组：if(r[i]<r[j])

④、将较小的值传给r1数组：r1[k++]=r[i++];else r1[k++]=r[j++];

⑤、当一个数字已经比较完，做循环将其续借到r1数组中：if(i<=m) while(i<=m) r1[k++]=r[i++];

⑤、 当另一个数字已经比较完，做循环将其续借到r1数组中：if(j<=t) while(j<=t) r1[k++]=r[j++];

10、递归归并排序函数：MergeSort(int *r, int *r1, int s, int t)

①、创建新数字指针存储排序序列：int *r2=new int[t];

②、当序列中只有一个数据时，令其相等：if(s==t) r1[s]=r[s];

③、否则，进行递归：else

④、将原数组折半：int m=(s+t)/2;

⑤、将前半数组进行递归调用：MergeSort(r,r2,s,m);

⑥、将后半数组进行递归调用：MergeSort(r,r2,m+1,t);

⑦、将数组进行递归调用：Merge(r2,r1,s,m,t);

㈡、关键算法的时间、空间复杂度

①、直接插入排序函数：时间复杂度 O（n²）

②、希尔排序函数：时间复杂度 O(n㏒₂ n)

③、起泡排序：时间复杂度O（n²）

④、快速排序：时间复杂度 O(n㏒₂ n)

⑤、简单选择排序：时间复杂度 O（n²）

⑥、堆排序：时间复杂度 O(n㏒₂ n)

⑦、归并排序：时间复杂度 O(n㏒₂ n)

3. 程序运行结果

测试主函数流程：

程序流程图如下：

           

 

                               b

                   a

 

4.  总结  

（1）、出现的问题及调试的方法

       这次试验总的来说是比较简单的，因为这七种排序算法的代码书上都有，在理解的基础上参考书上的代码输入基本上不会有太大的问题，但问题还是有的。例如：一组待排序的整数存在一个数组中，当采用一种排序算法对这个数组进行排序后，数组就被修改了，变为有序的序列，这是一个问题，于是我动态申请了七个数组，每次排序对不同的数组进行，这个问题就解决了

（2）、心得体会

这次试验是我对排序运算有了深刻的理解，对我们课堂上的知识进行回顾。

在程序编译和链接时还报了一些错，最后我对排序运算有了深刻的理解，对我们课堂上的知识进行回顾。

在程序编译和链接时还报了一些错，最后通过一步一步的测试，也很快解决了问题。

通过这次程序我感觉我对C++调试有个很深的理解，对程序的调试有了很多心得，也对我的程序调试和编写有了进一步的提高。同时对C++编程进一步熟悉，同时对数据结构有了一个整体的认识，对各种排序中函数成员实现的原理、代码进一步了解。同时对各种排序的优缺点有了进一步的认识和了解。

在这个程序中，我觉得下一步程序可以进一步对时间复杂度进行优化，通过将程序的冗长的代码删除，优化算法等，让程序得到结果所需要的时间更短、更快，删除一些代码，让程序的空间复杂度和时间复杂度都减小。

（3）、下一步的改进

程序中代码有一部分不是太简洁，例如七个数组、统计比较了移动次数这些代码显得比较乱。