实验十:查找、排序
计算机学院 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;
}
四 实验结果
实验十查找排序计算机学院12级2班1211020xx李龙实验目的1掌握折半查找算法的思想2实现折半查找的算法3掌握常见的排序算法插…
实验五查找与排序实验课程名数据结构与算法专业班级12级软件工程1班学号20xx40450149姓名刘浩实验时间61462134节实…
电子科技大学信息与软件工程学院实验报告电子科技大学实验报告课程名称学生姓名学号点名序号指导教师实验地点实验时间20xx20xx2学…
实验题91设计一个程序exp91cpp输出在顺序表36210185749中采用顺序方法找关键字5的过程程序如下文件名exp91cp…
近代物理实验报告指导教师:得分:实验时间:2009年11月23日,第十三周,周一,第5-8节实验者:同组者:实验地点:综合楼503…
微波的光学特性实验20XX级光电信息科学与工程XXX摘要微波是一种特定波段的电磁波,其波长范围为1mm~1m。它存在明显的反射、折…
1拟合出直线为X014979t0940592所以水中声速应该为014979cms即14979ms与理论值1464ms误差为23lt…
姓名学号实验一T型波导分支内部场分析实验目的理解和分析T型波导分支内部电磁场分布实验内容建立一个T型波导模型利用HSFF软件求解分…
内蒙古工业大学信息工程学院实验报告课程名称微波技术实验名称衰减的测量实验类型验证性综合性设计性实验室名称通信与控制基础实验室成绩实…
1实验要求实验目的学习实现对比各种排序算法掌握各种排序算法的优劣以及各种算法使用的情况实验内容使用简单数组实现下面各种排序算法并进…