数据结构：查找实验.doc

《数据结构：查找实验.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、数据结构实验报告课程数据结构实验实验名称查找系别计算机学院专业班级组别_____________一.实验目的：1.掌握顺序查找，二分查找的算法2.能运用线性表的查找方法解决实际问题二.实验内容（－）实验题目一：写给出一个无序表A中采用顺序查找算法查找值为x的元素的算法1.要点分析：顺序查找首先从表的先端开始，依次与给定值x进行比较，直达找到与其相等的元素值，返回该元素值的下标，查找成功。否则给出查找失败信息。2.程序源代码：#include#defineN10intsearch(intA[],intx,intn){in

2、ti=0;while(i=n)return-1;elsereturni;}voidmain(){inta[N]={2,38,42,44,25,12,3,1,23,89},d,i,k;printf("A数组下标:");for(i=0;i

3、=search(a,d,N);if(k>=0)printf("a[%d]=%d",k,d);elseprintf("%d未找到",d);}3.实验结果（二）实验题目二：编写一个算法，利用二分查找算法在一个有序表中插入一个元素x，并保持表的有序性。1．要点分析：首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找

4、成功，或直到子表不存在为止，此时查找不成功。2．程序源代码：#include#include#definemaxnum100intinput(int*);//输入数据intsearch(int*,int,int);//查找插入位置voidplug(int*,int,int);//插入数据voidmain(){intdata[maxnum],m;intinsert=1;m=input(data);printf("请输入要插入的数据:");//输入插入的数据scanf("%d",data);//输入

5、插入的数据存放在data数组0号位置insert=search(data,1,m);//找到数据要插入的位置plug(data,insert,m);//运用递归的方法插入数据printf("最后结果:");for(insert=1;insert<=m+1;insert++)printf("%d",*(data+insert));getchar();}intinput(int*data){inti,m;printf("请输入该有序表的长度:");scanf("%d",&m);printf("请按大小顺序输入%d个数据",m);

6、for(i=1;i<=m;i++)scanf("%d",data+i);returnm;}intsearch(int*data,intlow,inthigh){intmid;if(low>high)//没有找到插入位置returnlow;else{mid=(low+high)/2;if(*(data+mid)==*data)returnmid;elseif(*(data+mid)<*data)low=mid+1;elseif(*(data+mid)>*data)high=mid-1;}search(data,low,high);}voi

7、dplug(int*data,intinsert,intm)//移动并插入数据{inti;for(i=m;i>=insert;i--)*(data+i+1)=*(data+i);*(data+insert)=*data;}3.实验结果（三）实验题目：设计一个算法，读入一串整数，构造其对应的二叉排序树1.要点分析二叉排序树的递归式定义。二叉排序树又称二叉查找树，它可以是一棵空树，若非空时具有下述性质：1、若根结点的左子树非空，则左子树上所有结点的关键字值均小于等于根结点的关键字值。2、若根结点的右子树非空，则右子树上所有结点的关键字值均大

8、于等于根结点的关键字值。3、根结点的左、右子树也分别为二叉排序树。二叉排序树建立说明：当需要插入一个节点到二叉排序树时，需要先找到它的父节点。其实它就是用插入的节点不断的和每一个节点比较（第一次当然是和根节