实验四查找docx

1、成绩：实 验 报 告课程名称：数据结构实验实验项目：查找表的操作练习姓 名：李翠超专 业：计算机科学与技术班 级：计算机16-6班学 号：1609040307计算机科学与技术学院实验教学中心2017年12月11日实验项目名称： 查找表的操作练习 一、实验目的1.学习掌握查找的含义2.学习掌握基本查找的操作算法与实现。二、实验内容1.实现顺序查找，在输入的数组纪录中顺序查找所需的纪录。2.用二分查找，也称折半查找方法，对已知的有序序列进行查找。3.考虑输入无序数时如何实现折半查找。 三、实验步骤1.顺序查找建立一个线性表，对表中数据元素存放的先后次序没有任何要求。输入待查数据元素的关键字进行查找

2、。为了简化算法，数据元素只含一个整型量关键字字段，数据元素的其余数据部分忽略不考虑。从表的一端开始，顺序扫描线性表，依次将扫描到的结点关键字和待找的值相比较，若相等，则查找成功，若整个表扫描完毕，仍末找到关键字等于的元素，则查找失败。顺序查找既适用于顺序表，也适用于链表。若用顺序表，查找可从前往后扫描，也可从后往前扫描，但若采用单链表，则只能从前往后扫描。另外，顺序查找的表中元素可以是无序的。2.二分查找表的存储结构为有序表，即表中记录按关键字大小排序存放。输入待查数据元素的 关键字进行查找。为了简化算法，记录只含一个整型量关键字字段，记录的其余数据部分忽略不考虑。此程序中要求对整型量关键字数

3、据的输入按从小到大排序输入。二分查找是一种高效率的查找方法。但二分查找有条件限制：要求表必须用向量作存贮结构，且表中元素必须按关键字有序(升序或降序均可)。基本思想是：首先将待查值K与有序表R1到Rn的中点mid上的关键字Rmid.key进行比较，若相等，则查找成功；否则，若Rmid.key>k ， 则在R1到Rmid-1中继续查找，若有Rmid.key<k ， 则在Rmid+1到Rn中继续查找。每通过一次关键字的比较，区间的长度就缩小一半，区间的个数就增加一倍，如此不断进行下去，直到找到关键字为K的元素；若当前的查找区间为空(表示查找失败)。 四、实验结果实验结果如图所示，按照要

4、求将数据输入五、程序代码#include<stdio.h>#define OK 1#define ERROR 0#define MAXSIZE 100typedef int Status;typedef int KeyType; / 设关键字域为整型#define EQ(a,b) (a)=(b)#define LT(a,b) (a)<(b)#define LQ(a,b) (a)<=(b)typedef struct KeyType key; ElemType;ElemType aMAXSIZE;typedef struct ElemType *elem; / 数据元素存

5、储空间基址，建表时按实际长度分配，0号单元留空 int length; / 表长度 SSTable;typedef struct int dataMAXSIZE; / 数组，存储数据元素 int length; / 线性表当前长度 SqList;Status InitList(SqList *L) L->length=0; return OK;Status ListInsert(SqList *L,int i,int e) int k; if (L->length=MAXSIZE) / 顺序线性表已经满 return ERROR; if (i<1 | i>L->l

6、ength+1) / 当i比第一位置小或者比最后一位置后一位置还要大时 return ERROR; if (i<=L->length) / 若插入数据位置不在表尾 for(k=L->length-1; k>=i-1; k-) / 将要插入位置之后的数据元素向后移动一位 L->datak+1=L->datak; L->datai-1=e; / 将新元素插入 L->length+; return OK;Status GetElem(SqList L,int i,int *e) if(L.length=0 | i<1 | i>L.lengt

7、h) return ERROR; *e=L.datai-1; return OK;/L.datai-1;void SelectSort(SqList *L) int i,j,min,temp; for(i=1; i<L->length; i+) min = i;/ 将当前下标定义为最小值下标 for (j = i+1; j<=L->length; j+) / 循环之后的数据 if (L->datamin>L->dataj)/ 如果有小于当前最小值的关键字 min = j;/ 将此关键字的下标赋值给min if(i!=min)/ 若min不等于i，说明找

8、到最小值，交换 temp=L->datai; L->datai=L->datamin; L->datamin=temp; / 交换L->datai与L->datamin的Status Creat_Seq(SSTable *ST,ElemType a,int n) / 操作结果: 构造一个含n个数据元素的静态顺序查找表ST int i; (*ST).elem=(ElemType *)calloc(n+1,sizeof(ElemType); / 动态生成n个数据元素空间 if(!(*ST).elem) return ERROR; for(i=1; i<=n

9、; i+) *(*ST).elem+i)=ai-1; / 将全局数组r的值依次赋给 (*ST).length=n; return OK;int Search_Seq(SSTable ST,KeyType key) / 在顺序表ST中顺序查找其关键字等于key的数据元素。若找到，则函数值为该元素在表中的位置;否则为0。 int i; ST.elem0.key=key; / 哨兵 for(i=ST.length; !EQ(ST.elemi.key,key); -i); / 从后往前找 return i; / 找不到时，i为0int Search_Bin(SSTable ST,KeyType key

10、) / 在有序表ST中折半查找其关键字等于key的数据元素。若找到，则函数值为 / 该元素在表中的位置，否则为0。 int low,high,mid; low=1; / 置区间初值 high=ST.length; while(low<=high) mid=(low+high)/2; if EQ(key,ST.elemmid.key) / 找到待查元素 return mid; else if LT(key,ST.elemmid.key) high=mid-1; / 继续在前半区间进行查找 else low=mid+1; / 继续在后半区间进行查找 return 0; / 顺序表中不存在待查

11、元素void print(ElemType c) / Traverse()调用的函数 printf("%d",c);int judge(SSTable ST,int i) /判断是否找到 if(i) print(*(ST.elem+i); else printf("没找到nn"); return 0;int main() SqList L; SSTable st; int N,j,o; int aMAXSIZE,e; InitList(&L); printf("请输入元素个数："); scanf("%d",

12、&N); for(j=1; j<=N; j+) printf("请输入元素%d =:",j); scanf("%d",&o); ListInsert(&L,j,o); SelectSort(&L); for(j=1; j<=N; j+) aj-1=GetElem(L,j,&e); Creat_Seq(&st,a,N); printf("请输入要查找的数："); int s,i,p; scanf("%d",&s); printf("顺序查找:"); i=Search_Seq(st,s); judge(st,i); printf("折半查找法：");