数据结构实验查找表的操作练习

《数据结构实验查找表的操作练习》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、成绩:〔据结构实验查找表的操作练习课程名称:实验项目:姓名:专业:班级:学号:计算机科学与技术学院2017年12月5日实验项目名称：查找表的操作练习一、实验目的1.熟练掌握静态查找表的查找方法1.熟练掌握动态查找表的查找方法二、实验内容1.用二分査找法对查找表进行查找2.建立二叉排序树并对该树进行查找三、实验操作步骤1.顺序查找顺序查找是对无序表查找的一种查找方式，为提高执行效率我们在表头设立监督元。具体实现如下：intres(Sqlist&L，inta){LList[0]=a;inti;for(i=L.length;i>=0;i—){if(L.List[i]==a)retu

2、rni;}returni;2.二分查找二分查找i对有序表的查找，基于分治的的思想，每次与表的中间元素相比较，由于表示有序的，所以如果相等就查找成功了，不相等只需在表的一半中继续二分查找，减小了需要查找的长度，具体实现有两种方案分为递归与非递归。intsearchl(Sqlist&L,inta,intleft,intright)//递归实现{if(left>right)return-1;intmid=(lcft+right)/2;if(L.List[mid]==a)哈尔滨理工大学计算机科学与技术学院实验教学中心returnmid;elseif(L.List[mid]〈a)ret

3、urnsearchl(L,a,mid+1,right);elsereturnsearchl(L，a,left,mid-1);}intsearch(Sqlist&L,inta)//非递归实现{intleft=O;intrigth=L.length-1;while(left<=rigth){intmid=(1eft+rigth)/2;if(L.List[mid]==a)returnmid;if(L.List[mid]〈a)left=mid+l;elserigth=mid-l;}return-1;}1.二叉排序树的建立与查找二叉排序树是左子树小于根小于右子树的一种树，其建立就是动态

4、查找的过程。如果所拿元素小于根去左子树找其所在位置，否则去右子树找其位置。査找的过程则是如果待斉找值等于与了根的值则查找成功，如果小于去左子树查找，否则去右子树查找，以此递归执行。具体实现如下：if(T==NULL)//创建{T=(Bitrcc*)malloc(sizcof(Bitrcc));T->data=a;T->left:NULL;T->rigth=NULL;return1;}else{if(T->data==a)return0;elseif(T->datarigth,a);elsecreatebree(T->1eft,a);哈尔滨理工

5、大学计算机科学与技术学院实验教学中心Bitree*re(Bitree*T,inta)//查找if(T==NULL

6、

7、T->data==a)returnT;elseif(T->data>a)returnre(T->left,a);elsereturnre(T->rigth,a);四、实验结果青输入元素个数:5L5623_青输入待查找的元素置2^rocessreturned0(0x0)executiontime:18.410s〕ressanykeytocontinue.顺序查找结果请输人元素个数:6123456请输入待查找的元素中位置为：5二分査找结果eo)nuX«Tot(n□o

8、cdoetrny一、do5^8et数如素y个果元stulke糸1结元relyI瓜0捉5杳一是依san入S遍2ass输5序1撰中oces请2中O请杳一树prpr二叉排序树查找结果。五、实验主要代码如下1.顺序奔找intres(Sqlist&L,inta)L.List[0]=a;inti;for(i=L.length;i>=0;i—)if(L.List[i]==a)returni;}returni;2.二分查找ight)//递归实现intsearchl(Sqlist&L,inta,intleft,int{if(left>right)return-1;intmid二(left+ri

9、ght)/2;if(LList[mid]==a)returnmid;elseif(L.List[mid]