数据结构实验四

实验报告学院（系）名称：计算机科学与工程学院姓名赵振宇学号20175302专业计算机科学与技术班级2017级4班实验项目实验四：查找算法应用课程名称数据结构与算法课程代码0661913实验时间2019年6月3日第3、4节实验地点7－219考核标准实验过程25分程序运行20分回答问题15分实验报告30分特色功能5分考勤违纪情况5分成绩成绩栏其它批改意见:教师签字：考核内容评价在实验课堂中的表现，包括实验态度、编写程序过程等内容等。□功能完善,□功能不全□有小错□无法运行○正确○基本正确○有提示○无法回答○完整○较完整○一般○内容极少○无报告○有○无○有○无一、实验目的掌握二叉排序树、AVL树的查找、插入、删除等算法的思想及程序实现；能选择合适散列函数，实现不同冲突处理方法的散列表的查找、建立。能运用折半查找、分块查找、二叉排序树、散列表等查找算法解决具体应用问题。较高要求：利用B+树设计大数据集索引结构。二、实验题目与要求从下面题目中至少选择2题实现：其中第1题必做，2-5题中至少选择1题。1.折半查找算法1）问题描述：从键盘读入一串整数和一个待查关键字，查找在该整数串中是否有这个待查关键字。如果有，输出它在整数串中的位置；如果没有，输出-12）实验要求：利用折半查找算法查找用递归和非递归两种方式实现折半查找算法3)实现提示：递归实现参考书上折半查找算法的实现非递归算法利用栈实现2.构造二叉排序树，并进行中序遍历1）问题描述：从键盘读入一串整数构造一棵二叉排序树，并对得到的二叉排序树进行中序遍历，得到有序序列。2）实验要求：该二叉排序树以二叉链表存储3）实现提示：二叉排序树的构成，可从空的二叉树开始，每输入一个结点数据，就建立一个新结点插入到当前已生成的二叉排序树中，所以它的主要操作是二叉排序树插入运算。在二叉排序树中插入新结点，只要保证插入后仍符合二叉排序树的定义即可。3.对于给定的一个有序序列，创建一颗高度最小的二叉排序树。1）实验要求：该二叉排序树以二叉链表存储2）实验提示：要创建一颗高度最小的二叉排序树，就必须让左右子树的节点个数越接近越好。由于给定的是一个关键字有序序列a[start..end]，所以让其中间位置的关键字a[mid]作为根结点，左序列a[start..mid-1]构造左子树，右序列a[mid+1..end]构造右子树。4.哈希表查找1）问题描述：针对某个集体的“人名”构造哈希表，解决按“人名”进行查找的索引结构。2）实验要求：要求表的平均查找长度不超过R，完成相应的建表和查表程序。3)实现提示：假设人名为汉语拼音形式。代填入哈希表人名共30个，取平均查找长度的上限为2。哈希函数用除留余数法构造，用再散列法处理冲突。5.拼写检查1）问题描述：现在有一些英语单词需要做拼写检查，你的工具是一本词典。需要检查的单词，有的是词典中的单词，有的与词典中的单词相似，你的任务是发现这两种情况。单词A与单词B相似的情况有三种：①删除单词A的一个字母后得到单词B；②用任意一个字母替换单词A的一个字母后得到单词B；③在单词A的任意位置增加一个字母后得到单词B。2）实验要求：发现词典中与给定单词相同或相似的单词。三、实验过程与实验结果1.折半查找算法由于折半查找有两个限制：①要求查找必须采用顺序存储结构，即顺序表；②表中的元素必须按关键字有序排列。由于本题一开始所给出的序列有序，所以定义两个变量low和high，初始时分别指向R[0]和R[n-1]。首先将给定值k与有序表R[0]到R[n-1]的中点mid=(low+high)/2上的关键字R[mid]进行比较，若相等，则查找成功。若kR[mid]，则说明k有可能落在[0...mid-1]区间中，于是修改high，指向mid-1位置，在R[0]到R[mid-1]中继续查找。若kR[mid],则说明k有可能落在[mid+1...n-1]区间中，于是修改low,指向mid+1位置。在R[mid+1]到R[n-1]中继续查找。每通过次比较，区间的长度就缩小一半，如此不断进行下去，直至找到关键字为k的元素(查找成功)或lowhigh,即查找失败为止。主要算法（折半查找）：intbinarysearch(intR[],intk,intn){intlow=0,high=n-1,mid;while(low=high){mid=(low+high)/2;if(R[mid]==k)returnmid+1;elseif(kR[mid])high=mid-1;elselow=mid+1;}return-1;}测试结果：2.构造二叉排序树，并进行中序遍历。数据结构为：typedefstructnode{intdata;structnode*lchild,*rchild;}BSTNode;要构造一个二叉排序树，首先要对输入的数组进行排序，本题我先用冒泡排序对数组进行排序，它的具体步骤为:首先从第一个记录开始，将第一个记录的关键字与第二个记录的关键字进行比较，若两个关键字为逆序(R[0]R[1]),则交换两记录位置；然后比较第二个记录与第三个记录，若两关键字为逆序，同样交换两记录位置；依次类推，直至第n-2个记录和第n-1个记录比较完为止。上述过程称作第一趟冒泡排序，其结果使得n个记录中关键字最大的记录被移到最后一个位置上。然后进行第二趟冒泡排序，即对前n-1个记录重复与第一趟冒泡排序类似的过程，结果使关键字次大的记录被移到第n-1个记录位置上。重复上述过程，直到“在一趟排序过程中没有进行过交换记录的操作”为止。所得录序列就是有序序列。冒泡排序算法：voidsort(intn){inti,j,buf;for(i=0;in-1;++i)//比较n-1轮{for(j=0;jn-1-i;++j)//每轮比较n-1-i次,{if(R[j]R[j+1]){buf=R[j];R[j]=R[j+1];R[j+1]=buf;}}}return;}待数组排好序以后在进行二叉排序树的建立，这道题我直接创建的是最小高度的二叉排序树，要创建一颗高度最小的二叉排序树，就必须让左右子树的结点个数越接近越好。所以我直接采用中间值来作为二叉树的根节点；将原数组分成左右均等或者相差一个数的两个新数组；然后递归的对这两个新数组进行相同的处理，这样对于每一个根节点，其左右子树的高度相差绝对值不会超过1。建立二叉排序树算法：BSTNode*CreateBST(intlow,inthigh){intmid=(low+high)/2;BSTNode*root;if(low=high){root=(BSTNode*)malloc(sizeof(BSTNode));root-data=R[mid];root-lchild=CreateBST(low,mid-1);root-rchild=CreateBST(mid+1,high);returnroot;}elsereturnNULL;}测试结果：3.对于给定的一个有序序列，创建一颗高度最小的二叉排序树。数据结构为：typedefstructnode{intdata;structnode*lchild,*rchild;}BSTNode;与前一道题一样，先要对初始数组排序，这里采用冒泡排序法，首先从第一个记录开始，将第一个记录的关键字与第二个记录的关键字进行比较，若两个关键字为逆序(R[0]R[1]),则交换两记录位置；然后比较第二个记录与第三个记录，若两关键字为逆序，同样交换两记录位置；依次类推，直至第n-2个记录和第n-1个记录比较完为止。上述过程称作第一趟冒泡排序，其结果使得n个记录中关键字最大的记录被移到最后一个位置上。然后进行第二趟冒泡排序，即对前n-1个记录重复与第一趟冒泡排序类似的过程，结果使关键字次大的记录被移到第n-1个记录位置上。重复上述过程，直到“在一趟排序过程中没有进行过交换记录的操作”为止。所得录序列就是有序序列。冒泡排序算法：voidsort(intn){inti,j,buf;for(i=0;in-1;++i)//比较n-1轮{for(j=0;jn-1-i;++j)//每轮比较n-1-i次,{if(R[j]R[j+1]){buf=R[j];R[j]=R[j+1];R[j+1]=buf;}}}return;}待数组排好序以后在进行二叉排序树的建立，要创建一颗高度最小的二叉排序树，就必须让左右子树的结点个数越接近越好。所以我直接采用中间值来作为二叉树的根节点；将原数组分成左右均等或者相差一个数的两个新数组；然后递归的对这两个新数组进行相同的处理，这样对于每一个根节点，其左右子树的高度相差绝对值不会超过1。建立二叉排序树算法：BSTNode*CreateBST(intlow,inthigh){intmid=(low+high)/2;BSTNode*root;if(low=high){root=(BSTNode*)malloc(sizeof(BSTNode));root-data=R[mid];root-lchild=CreateBST(low,mid-1);root-rchild=CreateBST(mid+1,high);returnroot;}elsereturnNULL;}测试结果：4.哈希表查找。数据结构为：typedefstructHash{chardata[50];structHash*next;}Hash;typedefstruct{intdata;structHash*next;}FirstHash[30];将名字拼音字符串的各个字符所对应的ASCII码相加，所得的整数做为哈希表的关键字。用除留余数法构建哈希函数，用伪随机探测再散列法处理冲突。散列表的查找过程和建表过程类似。假设给定的值为k，根据建表时设定的散列函数H,计算出敢列地址H(k),若表中该地址对应的空间未被占用，则查找失败，把k插人该空单元中；否则将该地址中的值与k比较，若相等则查找成功，若不相等，则按事先设定的解决冲突的方法查找下一个地址。如此重复下去，直至某个地址空间未被占用(查找失败把k插人该空单元)或关键字比较相等(查找成功)为止。查找的主要算法：counts=(int)checkname[i][1]%29;if(h[counts]-next==NULL)cout0endl;else{Hash*temp=h[counts]-next;while(temp!=NULL&&strcmp(temp-data,checkname[i])!=0){temp=temp-next;}if(temp==NULL)cout0endl;elsecout1endl;}测试结果：四、收获与体会本次实验联系了几种常用的查找算法、排序算法，基本熟悉了顺序查找和折半查找的思想；也着练习了二叉排序树的创建，值的查找（位置）等，而且对遍历做了进一步练习；对哈希表也做了一些练习，用取余法存储数据建哈希函数，用伪随机探测再散列法处理冲突，然后对哈希表进行查找。再写程序的过程中遇到了很多问题，如结构体的构造、循环的次数判断、递归的入口及终止条件、指针的具体作用等，通过网上提问、询问同学等解决了部分问题，总的来说，这些题目于我感觉还是挺难的，多做练习吧，希望有改善。五、源代码清单1.折半查找算法。#includestdio.h#includestdlib.hintbinarysearch(intR[],intk,intn){intlow=0,high=n-1,mid;while(low=high){mid=(low+high)/2;if(R[mid]==k)returnmid+1;elseif(kR[mid])high=mid-1;elselow=mid+1;}return-1;}intmain(){intn,k;scanf(%d%d,&n,&k);intR[n];for(inta=0;an;a++){scanf(%d,&R[a