实验名称： 查找、排序

电子工程学院 雷电132班 2013021234 2013021249 李川徽 周成钊 实验目的：

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

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

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

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

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

设计思路：

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

主要C程序代码：

/*带哨兵的顺序查找方式*/

int Search_Seq(SSTable ST, KeyType key){

int i;

ST.elem[0] = key; //“哨兵”

for(i = ST.length; ST.elem[i] != key; i--)

return i; //找到的话，则i != 0,否则i = 0

/*不带哨兵的顺序查找方式*/

int ungard_Search_Seq(SSTable ST, KeyType key){

int i;

for(i=1; i<=ST.length && ST.elem[i] != key; i++ )

;

if(i<=ST.length)

return i;

else

return 0;

}

void main()

{

int i,j, key;

SSTable T;

T.elem = (KeyType*)malloc(sizeof(KeyType)); 折半查找

int binary_search(SSTable ST, KeyType key){

int l=0,h,mid; h=ST.length; while(l<=h){ } if (l<=h) return mid; else return 0; mid = (l+h)/2; if(ST.elem[mid]==key) break; else if(key>ST.elem[mid]) l=mid+1; else h=mid-1;

void bubble_sort(SSTable ST){

int flag = 1,t,j;

flag=1;

while(flag>0){ flag=0; for( j=1;j<=ST.length-1;j++) if(ST.elem[j]>ST.elem[j+1]){ t = ST.elem[j]; ST.elem[j]=ST.elem[j+1]; ST.elem[j+1]=t; flag = 1;

void main()

int m,n;

clock_t start, finish; //生命start和finish是两个时间

double time; //定义运行时间

int i,j, key;

SSTable T;

printf("How Many elements Do You Want input\n");

scanf("%d", &T.length);

T.elem = (KeyType *)malloc(sizeof(KeyType)*T.length);

printf("Please wait the %d elements are random generated \n",T.length); for(i=1; i<=T.length; i++)

T.elem[i] = rand()%1000;

for (i=1; i<=T.length; i++)

printf("%5d",T.elem[i]); //显示已经输入的所有数据

printf("\nafter data sorting.......................\n");

bubble_sort(T);

for (i=1; i<=T.length; i++)

printf("%5d",T.elem[i]); //显示排序以后的所有数据

冒泡排序

void InsertSort(Sqlist L, int n)

int i, j, over; SortItem p; for (i = 0; i < n - 1; i++) over = 1; for (j = n - 1; j > i; j--) if (L[j].key < L[j - 1].key ) p = L[j]; L[j] = L[j - 1]; L[j - 1] = p; over = 0; if (over) break;

 

第二篇：查找排序实验报告

实验十：查找、排序

计算机学院           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