实验四：查找.docx

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

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

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

4、程序代码#include#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)length=0; return ok;status listinsert(sqlist *l,int i,int e) int k; if (l-length=maxsize) / 顺序线性表已经满 return error; if (il-length

5、+1) / 当i比第一位置小或者比最后一位置后一位置还要大时 return error; if (ilength) / 若插入数据位置不在表尾 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 | il.length) return error; *e=l.datai-1; return ok;/l.datai-1;v

6、oid selectsort(sqlist *l) int i,j,min,temp; for(i=1; ilength; i+) min = i;/ 将当前下标定义为最小值下标 for (j = i+1; jlength; j+) / 循环之后的数据 if (l-dataminl-dataj)/ 如果有小于当前最小值的关键字 min = j;/ 将此关键字的下标赋值给min if(i!=min)/ 若min不等于i，说明找到最小值，交换 temp=l-datai; l-datai=l-datamin; l-datamin=temp; / 交换l-datai与l-datamin的status

7、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; i+) *(*st).elem+i)=ai-1; / 将全局数组r的值依次赋给 (*st).length=n; return ok;int search_seq(sstable st,keytype key) / 在顺序表s

8、t中顺序查找其关键字等于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) / 在有序表st中折半查找其关键字等于key的数据元素。若找到，则函数值为 / 该元素在表中的位置，否则为0。 int low,high,mid; low=1; / 置区间初值 high=st.length; while(l

9、ow=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; / 顺序表中不存在待查元素void print(elemtype c) / traverse()调用的函数 printf(%d,c);int judge(sstable st,int i) /判断是否找到 if(i) print(*(st.elem+i);

10、else printf(没找到nn); return 0;int main() sqlist l; sstable st; int n,j,o; int amaxsize,e; initlist(&l); printf(请输入元素个数：); scanf(%d,&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(