实验五 查找和排序
1、实验目的
1. 掌握顺序查找的基本方法
2. 掌握简单排序和二分法查找的算法。
2．能运用线性表的查找方法解决实际问题。
2、实验内容
1、给出在一个无序表A，采用顺序查找算法查找值为x的元素的算法
2、给出一个无序表B，采用简单排序方法使该表递增有序，并采用二分查找算法查找值为x的元素的算法。
3、实验步骤
（1）仔细分析实验内容，给出其算法和流程图；
（2）用C语言实现该算法；
（3）给出测试数据，并分析其结果；
（4）在实验报告册上写出实验过程。
4、实验报告要求
实验报告要求书写整齐，步骤完整，实验报告格式如下：
1、［实验目的］
2、［实验设备］
3、［实验步骤］
4、［实验内容］
5、［实验结果(结论)］
1.折半查找算法描述如下：
int Search_Bin(SSTable ST,KeyType key)
low=1;high=ST.length;
while(low<=high){
mid=(low+high)/2;
if EQ(key,ST.elem[mid].key) return mid;
else if LT(key,ST.elem[mid].key) high=mid -1;
else low=mid +1 ;
}
return 0;
}//Search_Bin;
2.顺序查找算法描述如下：
typedef struct {
ElemType *elem;
int length;
}SSTable;
顺序查找：
从表中最后一个记录开始，逐个进行记录的关键字和给定值的比较，若某个记录的
关键字和给定值比较相等，则查找成功，找到所查记录；反之，查找不成功。
int Search_Seq(SSTable ST,KeyType key){
ST.elme[0].key=key;
for(i=ST.length;
!EQ(ST.elem[i].key,key); --i);
return i; }
(3)写出源程序清单（加适当的注释）。
(4)调试说明。包括上机调试的情况、调试所遇到的问题是如何解决的，并对调试过程中的问题进行分析，对执行结果进行分析。
1,问题: malloc无法识别.
解决: 百度得知缺少头文件,导入stdlib.h后解决.
2,问题: 输入后程序无响应.
解决: scanf中缺少&,添加后解决.
3,问题: 结果显示不正确,为ASCII码
解决: 输出改为”%c”.
(5)测试结果及说明。对完成所要执行的功能情况分析。
（1）
（2）
五．实验体会：
通过本次排序和查找的练习，初步掌握了其基本概念和操作。
查找的基本概念：
查找表： 是由同一类型的数据元素（或记录）构成的集合。
查找表的操作：
1、查询某个“特定的”数据元素是否在查找表中。
2、检索某个“特定的”数据元素的各种属性。
3、在查找表中插入一个数据元素；
4、从查找表中刪去某个数据元素。
排序：将一个数据元素的无序序列重新排列成一个按关键字有序的序列。
内部排序：待排序记录存放在计算机随机存储器中进行的排序过程；
外部排序：待排序记录的数量很大，以致内存一次不能容纳全部记录，
在排序过程中尚需对外存进行访问的排序过程。
第二篇：查找和排序实验报告
查找和排序
1．需求分析
1．编写一个程序输出在顺序表{3，6，2，10，1，8，5，7，4，9}中采用顺序方法查找关键字5的过程；
2．编写一个程序输出在顺序表{1，2，3，4，5，6，7，8，9，10}中采用顺序方法查找关键字9的过程；
3．编写一个程序实现直接插入排序算法，并输出{9，8，7，6，5，4，3，2，1，0}的排序过程；
4．编写一个程序实现快速排序算法，并输出{6，8，7，9，0，1，3，2，4，5}的排序过程
2．系统设计
1． 静态查找表的抽象数据类型定义：
ADT StaticSearchTable{
数据对象D：D是具有相同特性的数据元素的集合。各个数据元素均含有类型相同，可惟一标识数据元素的关键字
数据关系R：数据元素同属一个集合
基本操作P：
Create(&ST,n)
操作结果：构造一个含n个数据元素的静态查找表ST
Destroy(&ST)
初始条件：静态查找表ST存在
操作结果：销毁表ST
Search(ST,key)
初始条件：静态查找表ST存在，key为和关键字类型相同的给定值
操作结果：若ST中存在其关键字等于key的数据元素，则函数值为该元素的值或在表中的位置，否则为“空”
Traverse(ST,Visit())
初始条件：静态查找表ST存在，Visit是对元素操作的应用函数
操作结果：按某种次序对ST的每个元素调用函数Visit()一次且仅一次。一旦Visit()失败，则操作失败
}ADT StaticSearchTable
3．调试分析
（1）要在适当的位置调用Print函数，以正确显示排序过程中顺序表的变化
（2）算法的时间复杂度分析：
顺序查找：T(n)=O(n)
折半查找：T(n)=O(logn)
直接插入排序：T(n)=O(n2)
快速排序：T(n)=O(nlogn)
4．测试结果
用需求分析中的测试数据
顺序查找：顺序表3，6，2，10，1，8，5，7，4，9，查找5
折半查找：顺序表1，2，3，4，5，6，7，8，9，10，查找9
直接插入排序：顺序表9，8，7，6，5，4，3，2，1，0，从小到大排序
快速排序：顺序表6，8，7，9，0，1，3，2，4，5，从小到大排序
5．用户手册
（1）输入表长；
（2）依次输入建立顺序表；
（3）查找：输入要查找的关键字
（4）回车输出，查找为下标的移动过程；排序为顺序表的变化过程
6．附录
源程序：
（1）顺序查找
#include <stdio.h>
#include <stdlib.h>
#define ST_INIT_SIZE 200
#define EQ(a,b) ((a)==(b))
#define OVERFLOW -2
typedef int KeyType;
typedef struct{
KeyType key;
}ElemType;
typedef struct{
ElemType *elem;//数据元素存储空间基址,建表时按实际长度分配,0号单元留空
int length;//表长度
}SSTable;
void InitST(SSTable &ST){
ST.elem=(ElemType*)malloc(ST_INIT_SIZE*sizeof(ElemType));
if(!ST.elem)exit(OVERFLOW);
ST.length=0;
}
void CreateST(SSTable &ST){
int i;
printf("输入表长:");
scanf("%d",&ST.length);
for(i=1;i<=ST.length;i++)
scanf("%d",&ST.elem[i].key);
}
void PrintST(SSTable ST){
int i;
for(i=1;i<=ST.length;i++)
printf("%2d",ST.elem[i].key);
printf("\n");
}
int Search_Seq(SSTable ST,KeyType key){
//在顺序表ST中顺序查找其关键字等于key的数据元素
//若找到则函数值为该元素在表中的位置,否则为0
int i;
ST.elem[0].key=key;
printf("下标:");
for(i=ST.length;!EQ(ST.elem[i].key,key);--i)
printf("%d→",i);//从后往前找
return i;
}
void main(){
SSTable ST;KeyType key;
InitST(ST);
CreateST(ST);
printf("顺序查找表:");
PrintST(ST);
printf("输入要查找的关键字:");
scanf("%d",&key);
int found=Search_Seq(ST,key);
if(found)printf("找到,为第%d个数据\n",found);
else printf("没有找到!\n");
}
（2）折半查找
#include <stdio.h>
#include <stdlib.h>
#define ST_INIT_SIZE 200
#define EQ(a,b) ((a)==(b))
#define LT(a,b) ((a)<(b))
#define OVERFLOW -2
typedef int KeyType;
typedef struct{
KeyType key;
}ElemType;
typedef struct{
ElemType *elem;//数据元素存储空间基址,建表时按实际长度分配,0号单元留空
int length;//表长度
}SSTable;
void InitST(SSTable &ST){
ST.elem=(ElemType*)malloc(ST_INIT_SIZE*sizeof(ElemType));
if(!ST.elem)exit(OVERFLOW);
ST.length=0;
}
void CreateST(SSTable &ST){
int i;
printf("输入表长:");
scanf("%d",&ST.length);
for(i=1;i<=ST.length;i++)
scanf("%d",&ST.elem[i].key);
}
void PrintST(SSTable ST){
int i;
for(i=1;i<=ST.length;i++)
printf("%2d",ST.elem[i].key);
printf("\n");
}
int Search_Bin(SSTable ST,KeyType key){
//在有序表ST中折半查找其关键字等于key的数据元素
//若找到,则函数值为该元素在表中的位置,否则为0
int low,high,mid;
low=1;high=ST.length;//置区间初值
printf("下标:");
while(low<=high){
mid=(low+high)/2;
printf("%d→",mid);
if(EQ(key,ST.elem[mid].key))return mid;//找到待查元素
else if(LT(key,ST.elem[mid].key))high=mid-1;//继续在前半区间进行查找
else low=mid+1;
}
return 0;//顺序表中不存在待查元素
}
void main(){
SSTable ST;KeyType key;
InitST(ST);
CreateST(ST);
printf("顺序查找表:");
PrintST(ST);
printf("输入要查找的关键字:");
scanf("%d",&key);
int found=Search_Bin(ST,key);
if(found)printf("找到,为第%d个数据\n",found);
else printf("没有找到!\n");
}
（3）直接插入排序
#include <stdio.h>
#define MAXSIZE 20
#define LT(a,b) ((a)<(b))
typedef int KeyType;
typedef struct{
KeyType key;
}RedType;//记录类型
typedef struct{
RedType r[MAXSIZE+1];//r[0]闲置或用作哨兵单元
int length;//顺序表长度
}SqList;//顺序表类型
void CreateSq(SqList &L){
int i;
printf("输入表长:");
scanf("%d",&L.length);
for(i=1;i<=L.length;i++)
scanf("%d",&L.r[i].key);
}
void PrintSq(SqList L){
int i;
for(i=1;i<=L.length;i++)
printf("%2d",L.r[i].key);
printf("\n");
}
void InsertSort(SqList &L){
//对顺序表L作直接插入排序
int i,j;
printf("排序过程:\n");
for(i=2;i<=L.length;++i){
if(LT(L.r[i].key,L.r[i-1].key)){//"<",需将L.r[i]插入有序子表
L.r[0]=L.r[i];//复制为哨兵
L.r[i]=L.r[i-1];
for(j=i-2;LT(L.r[0].key,L.r[j].key);--j)
L.r[j+1]=L.r[j];//记录后移
L.r[j+1]=L.r[0];//插入到正确位置
}
PrintSq(L);
}
}//InsertSort
void main(){
SqList L;
CreateSq(L);
printf("原始顺序表:");
PrintSq(L);
InsertSort(L);
printf("排序后的顺序表:");
PrintSq(L);
}
（4）快速排序
#include <stdio.h>
#define MAXSIZE 20
typedef int KeyType;
typedef struct{
KeyType key;
}RedType;//记录类型
typedef struct{
RedType r[MAXSIZE+1];//r[0]闲置或用作哨兵单元
int length;//顺序表长度
}SqList;//顺序表类型
void CreateSq(SqList &L){
int i;
printf("输入表长:");
scanf("%d",&L.length);
for(i=1;i<=L.length;i++)
scanf("%d",&L.r[i].key);
}
void PrintSq(SqList L){
int i;
for(i=1;i<=L.length;i++)
printf("%2d",L.r[i].key);
printf("\n");
}
int Partition(SqList &L,int low,int high){
//交换顺序表L中子表r[low…high]的记录,枢轴记录到位,并返回其所在位置,
//此时在它之前/后的记录均不大/小于它
int pivotkey;
L.r[0]=L.r[low];//用子表的第一个记录作枢轴记录
pivotkey=L.r[low].key;//枢轴记录关键字
while(low<high){//从表的两端交替地向中间扫描
while(low<high&&L.r[high].key>=pivotkey)--high;
L.r[low]=L.r[high];//将比枢轴记录小的记录移到低端
while(low<high&&L.r[low].key<=pivotkey)++low;
L.r[high]=L.r[low];//将比枢轴记录大的记录移到高端
}
L.r[low]=L.r[0];//枢轴记录到位
PrintSq(L);
return low;//返回枢轴位置
}//Partition
void QSort(SqList &L,int low,int high){
//对顺序表L中的子序列L.r[low…high]作快速排序
int pivotloc;
if(low<high){//长度大于1
pivotloc=Partition(L,low,high);//将L.r[low…high]一分为二
QSort(L,low,pivotloc-1);//对低子表递归排序,pivotloc是枢轴位置
QSort(L,pivotloc+1,high);//对高子表递归排序
}
}//QSort
void QuickSort(SqList &L){
//对顺序表L作快速排序
printf("排序过程:\n");
QSort(L,1,L.length);
}//QuickSort
void main(){
SqList L;
CreateSq(L);
printf("原始顺序表:");
PrintSq(L);
QuickSort(L);
printf("快速排序后的顺序表:");
PrintSq(L);
}