实验十：查找、排序

计算机学院           12级2班     121102013        李龙

实验目的：

1．  掌握折半查找算法的思想。

2．  实现折半查找的算法。

3．  掌握常见的排序算法（插入排序、交换排序、选择排序等）的思想、特点及其适用条件。

4．  能够分析各种算法的效率。

5．  熟练的掌常见的排序算法的程序步骤。

实验内容：

1．建立一静态有序表。

2．用一个函数实现折半查找算法。

3．在主函数中输入一组数据，测试算法的正确性。

4. 按照快速排序思想实现快速排序算法。

5. 在主函数中输入一段数据，测试算法的正确性。

设计思路：

开始的时候提示输入一组数据。并存入一维数组中，接下来调用一系列查找算法对其进行处理。顺序查找只是从头到尾进行遍历。二分查找则是先对数据进行排序，然后利用三个标志，分别指向最大，中间和最小数据，接下来根据待查找数据和中间数据的比较不断移动标志，直至找到。二叉排序树则是先构造，构造部分花费最多的精力，比根节点数据大的结点放入根节点的右子树，比根节点数据小的放入根节点的左子树，其实完全可以利用递归实现，这里使用的循环来实现的，感觉这里可以尝试用递归。当二叉树建好后，中序遍历序列即为由小到大的有序序列，查找次数不会超过二叉树的深度。这里还使用了广义表输出二叉树，以使得更直观。哈希表则是利用给定的函数式建立索引，方便查找

总体设计：

静态表的存储结构

typedef struct

{

        int *elem;

     int length;

}sstable;

void  CreateData(int data[],int length);//为一个数组赋值

//此函数是折半查找函数。其中data是所查寻的数组，length是数组的长度。x是所要查找的数，返回的值是数据x在数组中的位置

int   Bisearch(int data[],int x,int begin,int last);//折半查找函数，使用过程中只需要给出数组名字，要查找的数值x，数组的起始位置begin及末位置即可。

void PrintData(int data[],int length);//输出一个数组的所有元素。

定义void quickSort(int *arr,int l,int r)函数

实验结果：

输入查找数字：7             如上图

查找--得出结果

排序--得出结果

实验总结：

本次实验程序结构比较简单，无需复杂的函数调用。但是由于本人编程基础不够扎实，在面对需要很多数组声明和调用的时候，经常弄错，在编译的过程中出现了很多次内存调用出错的情况。后来发现是二维数组的定义上没有做好，引入了动态定义的方法解决了这一问题。

通过本次实验，加深了我对查找表的认识。但是，实验中也出现了问题，程序循环不能良好退出。希望经过以后的学习我能解决这些问题。

代码：查找代码---见附表1

       排序代码—见附表2

 

第二篇：冒泡排序和二分查找实验报告

冒泡排序和二分查找实验报告

一实验题目:  基于冒泡排序的二分查找

二 实验要求: 

2.1: 输出在顺序表中利用二分的方法查找关键字 9 的过程。

2.2：实现冒泡排序的过程，并输出｛9，8，7，6，5，4，3，2，1，0｝ 的过程

三 实验内容:

3.1 动态查找表的抽象数据类型:

ADT DynamicSearchTable {

数据对象 D：D是具有相同特性的数据元素的集合。各个数据元素均含有类型相同，可唯一标识数据元素的关键字

数据关系R：数据元素同属一个集合。

基本操作 P：

InitDSTable(&DT);

操作结果：构造一个空的动态查找表DT。

DestroyDSTable(&DT)

初始条件：动态查找表DT存在。

操作结果：销毁动态查找表DT。

SearchDSTable(DT,key);

初始条件：动态查找表DT存在，key为和关键字类型相同的给定值。

操作结果：若DT中存在其关键字等于key的数据元素，则函数值为该元素的值或在表中的位置，否则为“空”。

InsertDSTable(&DT,e);

初始条件：动态查找表DT存在，e为待插入的数据元素。

操作结果：若DT中不存在其关键字等于e.key的数据元素，则插入e到DT。

DeleteDSTable(&DT,key);

初始条件：动态查找表DT存在，key为和关键字类型相同的给定值。

操作结果：若DT中存在其关键字等于key的数据元素，则删除之。

TraverseDSTable(DT,visit());

初始条件：动态查找表DT存在，visit是对结点操作的应用函数。

操作结果：按某种次序对DT的每个结点调用函数visit()一次且至多一次，一旦visit()  失败，则操作失败。

}ADT DynamicSearchTable

3.2存储结构的定义;

///二分查找

#define maxn 100

typedef struct

{

    int key;

    char data[10];

}NodeType;

typedef NodeType SeqList[maxn];

///冒泡排序

#define maxn  20

typedef struct

{

    int key;

    char data[10];

} RecType;

3.3基本操作实现:

int BinSearch(SeqList R, int n ,int k)

{

    int l = 0, r = n - 1,mid , count = 0;

    while(l <= r)

    {

        mid = (l + r)/2;

        printf("  第 %d 次比较：在[ %d , %d ] 中比较元素 R[%d]: %d\n",++count,l,r,mid,R[mid].key);

        if(R[mid].key == k)

        {

            return mid;

        }

        else if(R[mid].key > k)

        {

            r = mid - 1;

        }

        else

        {

            l = mid + 1;

        }

    }

    return -1;

}

void BubbleSort(RecType R[],int n)

{

    int i, j, k;

    RecType temp;

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

    {

        for(j = n - 1; j > i; --j)

        {

            if(R[j].key < R[j - 1].key)

            {

                temp = R[j];

                R[j] = R[j - 1];

                R[j - 1] = temp;

            }

        }

        printf("i = %d ， 冒出的最小关键字： %d ， 结果为：",i, R[i].key);

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

            printf("%2d",R[k].key);

        printf("\n");

    }

}

3.4解题思路：

二分查找：因为原本便是顺序表，是递增序列，所以在一个区间中，我们只要每次判断中间节点和被查找的关键字的大小关系，就可以判断被查找的节点在那一段区间了，然后再进行二分即可。

冒泡排序：通过一次一次的交换，把无序序列中关键字最小的节点的值交换到前面即可。

3.5解题过程：

实验源代码如下：

3.5.1二分查找

#include <stdio.h>

#define maxn 100

typedef struct

{

    int key;

    char data[10];

}NodeType;

typedef NodeType SeqList[maxn];

int BinSearch(SeqList R, int n ,int k)

{

    int l = 0, r = n - 1,mid , count = 0;

    while(l <= r)

    {

        mid = (l + r)/2;

        printf("  第 %d 次比较：在[ %d , %d ] 中比较元素 R[%d]: %d\n",++count,l,r,mid,R[mid].key);

        if(R[mid].key == k)

        {

            return mid;

        }

        else if(R[mid].key > k)

        {

            r = mid - 1;

        }

        else

        {

            l = mid + 1;

        }

    }

    return -1;

}

int main( )

{

    SeqList R;

    int k = 9;

    int a[] = {1,2,3,4,5,6,7,8,9,10},i, n = 10;

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

    {

        R[i].key = a[i];

    }

    printf("关键字序列：");

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

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

    printf("\n");

    printf("查找 %d 的比较过程如下：\n",k);

    if((i = BinSearch(R, n , k)) != -1)

        printf("元素 %d 的位置是：%d\n",k, i);

    else

        printf("元素 %d 不在表中\n",k);

    return 0;

}

3.5.2冒泡排序

#include <stdio.h>

#define maxn  20

typedef struct

{

    int key;

    char data[10];

} RecType;

void BubbleSort(RecType R[],int n)

{

    int i, j, k;

    RecType temp;

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

    {

        for(j = n - 1; j > i; --j)

        {

            if(R[j].key < R[j - 1].key)

            {

                temp = R[j];

                R[j] = R[j - 1];

                R[j - 1] = temp;

            }

        }

        printf("i = %d ， 冒出的最小关键字： %d ， 结果为：",i, R[i].key);

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

            printf("%2d",R[k].key);

        printf("\n");

    }

}

int main( )

{

    int i, k, n = 10;

    int a[] = {9,8,7,6,5,4,3,2,1,0};

    RecType R[maxn];

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

        R[i].key = a[i];

    printf("初始关键字：");

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

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

    printf("\n");

    BubbleSort(R,n);

    printf("最后结果：");

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

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

    printf("\n");

    return 0;

}

四 实验结果