查找实验报告

福建工程学院国脉信息学院

学生课程实验报告书

09级计算机科学与信息技术系

网络工程专业02班

学号：0930040250 姓名：郭文明

2010-2011学年 第二学期


实验项目： 实验四 查找

实验目的：
本次实习的主要目的在于熟悉顺序表和有序表的查找方法和特点。其中以熟悉各种顺序表的操作为侧重点。通过本次实习还可帮助读者复习高级语言的使用方法。

实验内容：
【问题描述】
①建立一个查找表，使用顺序查找算法对其元素进行查找，并输出查找时比较的元素和最终的比较的次数。如果没有找到，则把该元素插入到该查找表中。
②建立一个有序查找表，使用二分查找算法对其元素进行查找，并输出查找时比较的元素和最终的比较的次数；如果没有找到，则把该元素插入到该查找表中。
【基本要求】
查找过程中，同时输出查找时比较的元素和最终的比较的次数，当没有找到元素时输出“没有此元素”，然后把该元素插入到该查找表中；否则输出此元素在查找表中的位置。
【测试数据】
1、查找表中的元素{1，5，7，2，8，9，6，0，4，3}，查找元素为8，查找元素10。
2、查找表中的元素{0，1，2，3，4，5，6，7，8，9}，查找元素为8，查找元素10。


实验程序如下：
#include
#include
#include
#include // exit()


#define LIST_INIT_SIZE 100 // 初始化大小
#define LISTINCREMENT 15

#define EQ(a,b) ((a)==(b))
#define LT(a,b) ((a)<(b))
#define LQ(a,b) ((a)<=(b))
#define MT(a,b) ((a)>(b))

#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1 // 不可实行的


typedef int ElemType; // 基本(元素)类型

typedef struct
{
ElemType * elem;
int length;
int listsize;
}SSTable;


int InitTable(SSTable *L)
// 操作结果：构造一个空的顺序线性表
{
(*L).elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));
if(!(*L).elem) // 存储分配失败
exit(OVERFLOW);
(*L).length=0; // 空表长度为0
(*L).listsize=LIST_INIT_SIZE; // 初始存储容量
return OK;
}


int DestroyTable(SSTable *L)
//

初始条件：顺序线性表L已存在。操作结果：销毁顺序线性表L
{
free((*L).elem);
(*L).elem=NULL;
(*L).length=0;
(*L).listsize=0;
return OK;
}


int ClearTable(SSTable *L)
// 初始条件：顺序线性表L已存在。操作结果：将L重置为空表
{
(*L).length=0;
return OK;
}


int TableEmpty(SSTable L)
// 初始条件：顺序线性表L已存在。操作结果：若L为空表，则返回TRUE，否则返回FALSE
{
if(L.length==0)
return TRUE;
else
return FALSE;
}


int TableLength(SSTable L)
// 初始条件：顺序线性表L已存在。操作结果：返回L中数据元素个数
{
return L.length;
}


int GetElem(SSTable L,int i,ElemType *e)
// 初始条件：顺序线性表L已存在，1≤i≤ListLength(L) 。操作结果：用e返回L中第i个数据元素的值
{
if(i<1||i>L.length)
exit(ERROR);
*e=*(L.elem+i-1);
return OK;
}


int LocateElem(SSTable L,ElemType e)
// 初始条件：顺序线性表L已存在。操作结果：返回L中第1个与e相等的数据元素的位序。若这样的数据元素不存在，则返回值为0。
{
ElemType *p;
int i=1; // i的初值为第1个元素的位序
p=L.elem; // p的初值为第1个元素的存储位置
while(i<=L.length&&(*p++!=e))
++i;
if(i<=L.length)
return i;
else
return 0;
}


int PriorElem(SSTable L,ElemType cur_e,ElemType *pre_e)
// 初始条件：顺序线性表L已存在。操作结果：若cur_e是L的数据元素，且不是第一个，则用pre_e返回它的前驱，否则操作失败，pre_e无定义。
{
int i=2;
ElemType *p=L.elem+1;
while(i<=L.length&&*p!=cur_e)
{
p++;
i++;
}
if(i>L.length)
return INFEASIBLE;
else
{
*pre_e=*--p;
return OK;
}
}


int NextElem(SSTable L,ElemType cur_e,ElemType *next_e)
// 初始条件：顺序线性表L已存在。操作结果：若cur_e是L的数据元素，且不是最后一个，则用next_e返回它的后继，否则操作失败，next_e无定义
{
int i=1;
ElemType *p=L.elem;
while(i{
i++;
p++;
}
if(i==L.length)
return INFEASIBLE;
else
{
*next_e=*++p;
return OK;
}
}


int TableInsert(SSTable *L,int i,ElemType e)
// 初始条件：顺序线性表L已存在，1≤i≤ListLength(L)+1 。操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1
{
ElemType *newbase,*q,*p;
if(i<1||i>(*L).length+1) // i值不合法
return ERROR;
if((*L).length>=(*L).listsize) // 当前存储空间已满，增加分配
{

newbase=(ElemType *)realloc((*L).elem,((*L).listsize+LISTINCREMENT)*sizeof(ElemType));
if(!newbase) // 存储分配失败
exit(OVERFLOW);
(*L).elem=newbase; // 新基址
(*L).listsize+=LISTINCREMENT; // 增加存储容量
}
q=(*L).elem+i-1; // q为插入位置
for(p=(*L).elem+(*L).length-1;p>=q;--p) // 插入位置及之后的元素右移
*(p+1)=*p;
*q=e; // 插入e
++(*L).length; // 表长增1
return OK;
}


int TableDelete(SSTable *L,int i,ElemType *e)
// 初始条件：顺序线性表L已存在，1≤i≤ListLength(L) 。操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1
{
ElemType *p,*q;
if(i<1||i>(*L).length) // i值不合法
return ERROR;
if((*L).length==0) // i值不合法
return ERROR;
p=(*L).elem+i-1; // p为被删除元素的位置
*e=*p; // 被删除元素的值赋给e
q=(*L).elem+(*L).length-1; // 表尾元素的位置
for(++p;p<=q;++p) // 被删除元素之后的元素左移
*(p-1)=*p;
(*L).length--; // 表长减1
return OK;
}


int Search_Seq(SSTable ST,ElemType key)
{
//在顺序表ST中顺序查找其关键字等于key的数据元素。若找到，则函数值为该元素在表中的位置，否则为0。
int i,j,k=0;
for(i=ST.length-1;!EQ(ST.elem[i],key)&&i>=0;--i)//从后往前找
{
k++;
printf("比较的元素为：%d\n",ST.elem[i]);
}
if(!EQ(ST.elem[i],key))
{
printf("比较的次数为：%d\n",k);
j=TableInsert(&ST,ST.length+1,key);
return 1;
}
else
{
k++;
printf("比较的元素为：%d\n",ST.elem[i]);
printf("比较的次数为：%d\n",k);
return 0;
}
}


int Search_Bin(SSTable ST,ElemType key)
{
//在有序表ST中折半查找其他关键字等于key的数据元素。若找到，则函数值为该元素在表中的位置，否则为0。
int low,high,mid,j,k=0;
low=0;
high=ST.length-1; //置区间初值
while(low<=high)
{
mid=(low+high)/2;
if(EQ(key,ST.elem[mid]))
{
k++;
printf("比较的元素为：%d\n",ST.elem[mid]);
printf("比较的次数为：%d\n",k); //找到待查元素
return 0;
}
else if(LT(key,ST.elem[mid]))
{
k++;
printf("比较的元素为：%d\n",ST.elem[mid]);
high=mid-1; //继续在前半区间进行

查找
}
else if(MT(key,ST.elem[mid]))
{
k++;
printf("比较的元素为：%d\n",ST.elem[mid]);
low=mid+1;
}
}
if(!EQ(key,ST.elem[mid]))
{
printf("比较的次数为：%d\n",k);//没有找到待查元素
if(LT(key,ST.elem[mid]))
j=TableInsert(&ST,mid+1,key);
else if(MT(key,ST.elem[mid]))
j=TableInsert(&ST,ST.length+1,key);
}
return 1;
}


int Menu()
{
int choice;
printf("************************\n");
printf(" 1.新建静态查找表\n");
printf(" 2.输出静态查找表\n");
printf(" 3.顺序查找\n");
printf(" 4.二分查找查找\n");
printf(" 5.退出\n");
printf("============================\n");
printf("请选择：");
scanf("%d", &choice);
return choice;
}


void print(ElemType *c)
{
printf("%d ",*c);
}


int main()
{
SSTable L;
int i,j,k,m,n,ch;
while (ch!=5)
{
ch=Menu();
switch(ch)
{
case 1:printf("请输入表L的元素个数n的值：");
scanf("%d",&n);
InitTable(&L); // 创建空表L成功
printf("请输入顺序表L的%d个元素（格式为：元素1 元素2）：\n",n);
for(j=1;j<=n;j++) // 在表L中插入n个元素
{
scanf("%d",&k);
i=TableInsert(&L,j,k);
}
break;
case 2:printf("顺序表L的元素分别为："); // 输出表L的内容
for(i=0;iprint(&L.elem[i]);
printf("\n");
break;
case 3:printf("请输入查找的元素的值m：");
scanf("%d",&m);
if(Search_Seq(L,m))
L.length=L.length+1;
printf("查找后L的元素分别为：\n"); // 输出表L的内容
for(i=0;iprint(&L.elem[i]);
printf("\n");
break;
case 4:printf("请输入查找的元素的值m：");
scanf("%d",&m);
if(Search_Bin(L,m))
L.length=L.length+1;
printf("查找后L的元素分别为：\n"); // 输出表L的内容
for(i=0;iprint(&L.elem[i]);
printf("\n");
break;
case 5:printf("结束程序。\n");
return 0;
break;
defau

lt:printf("输入错误！请重新输入！\n\n");
break;
}
}
}


实验输出：
************************
1.新建静态查找表
2.输出静态查找表
3.顺序查找
4.二分查找查找
5.退出
============================
请选择：1
请输入表L的元素个数n的值：10
请输入顺序表L的10个元素（格式为：元素1 元素2）：
1 5 7 2 8 9 6 0 4 3
************************
1.新建静态查找表
2.输出静态查找表
3.顺序查找
4.二分查找查找
5.退出
============================
请选择：2
顺序表L的元素分别为：1 5 7 2 8 9 6 0 4 3
************************
1.新建静态查找表
2.输出静态查找表
3.顺序查找
4.二分查找查找
5.退出
============================
请选择：3
请输入查找的元素的值m：8
比较的元素为：3
比较的元素为：4
比较的元素为：0
比较的元素为：6
比较的元素为：9
比较的元素为：8
比较的次数为：6
查找后L的元素分别为：
1 5 7 2 8 9 6 0 4 3
************************
1.新建静态查找表
2.输出静态查找表
3.顺序查找
4.二分查找查找
5.退出
============================
请选择：3
请输入查找的元素的值m：10
比较的元素为：3
比较的元素为：4
比较的元素为：0
比较的元素为：6
比较的元素为：9
比较的元素为：8
比较的元素为：2
比较的元素为：7
比较的元素为：5
比较的元素为：1
比较的次数为：10
查找后L的元素分别为：
1 5 7 2 8 9 6 0 4 3 10
************************
1.新建静态查找表
2.输出静态查找表
3.顺序查找
4.二分查找查找
5.退出
============================
请选择：1
请输入表L的元素个数n的值：10
请输入顺序表L的10个元素（格式为：元素1 元素2）：
0 1 2 3 4 5 6 7 8 9
************************
1.新建静态查找表
2.输出静态查找表
3.顺序查找
4.二分查找查找
5.退出
============================
请选择：2
顺序表L的元素分别为：0 1 2 3 4 5 6 7 8 9
************************
1.新建静态查找表
2.输出静态查找表
3.顺序查找
4.二分查找查找
5.退出
============================
请选择：4
请输入查找的元素的值m：8
比较的元素为：4
比较的元素为：7
比较的元素为：8
比较的次数为：3
查找后L的元素分别为：
0 1 2 3 4 5 6 7 8 9
************************
1.新建静态查找表
2.输出静态查找表
3.顺序查找
4.二分查找查找
5.退出
============================
请选择：4
请输入查找的元素的值m：10
比较的元素为：4
比较的元素为：7
比较的元素为：8
比较

的元素为：9
比较的次数为：4
查找后L的元素分别为：
0 1 2 3 4 5 6 7 8 9 10
************************
1.新建静态查找表
2.输出静态查找表
3.顺序查找
4.二分查找查找
5.退出
============================
请选择：5
结束程序。
Press any key to continue