数据结构课程设计（论文）-查找.doc

数据结构课程设计（论文）-查找.doc数据结构课程设计报告设计题目:查找专业:计算机科技院系:计算机学院姓名:XX XX学号:XXXXXXXXX时间:2013年10月7日・2・一实践目的与要求1实践冃的 -2-1・2实践耍求 -2-顺序查找的分析、程序、及运行结果 -2-1系统简介 -2- -2-3顺序查找算法描述 折半查找的分析、程序、及运行结果 ・4・1系统简介 -4- -4-3折半查找算法描述 -5-四二叉排序树查找的分析、程序、及运行结果 -5-1系统简介 -5- -5-3二叉排序树算法描述 -6-五哈希査找的分析、程序、及运行结果 -8-1系统简介 -8- -9- -9-六用户手册 错误!未定义书签。七附件 错误!未定义书签。八参考文献 -16 -一实践目的与要求1・1实践目的掌握各种查找算法的思想及其使用条件;掌握上机实现各种查找算法的基本思想;熟练掌握二叉排序树的构造和查找方法;掌握散列表存储结构的思想,能选择合适的散列表函数,实现不同冲突处理方法的散列表的查找与建立;2实践要求掌握实践是算法。上机运行程序,保存和打卬运行结果,并结合程序进行分析。注意理解折半查找的适用条件。建立二叉排序树、散列表是相同元素的处理。比较各种查找算法的各自特点,能够结合实际情况选择合适的查找方式。二顺序查找的分析、程序、,然后进行关键字查找。如果存在则返回待查元索的位置。2设计思路1)顺序查找的思想对丁给定的关键字K,从表中的一端开始,逐个进行数据元索的关键字和给定值的比较,若当前扫描到的关键字与K相等则查找成功;若扫描结束后,仍未找到关键字等于K的节点,则查找失败。建立一个顺序表,数据元素从下标为1的单元开始放入,下标为0的元素起哨兵作用,将待查的关键字存入下标为0的单元,顺序表从后向前查找,若直到下标为0时才找到关键字则说明查找失败,若不到下标为0时就找到关键字,则查找成功。3顺序查找算法描述/*顺序表结构体定义*/typedefstruct{keytypekey[maxsize];intlen;}stable;/*建立线性表*/stablecreates(stabler){-inti,j=0,k=l;printff请输入顺序表元素,耍为整形,用空格分开,-99为结束标志:\『);seanf &i);while(i!二-99){j++;key[k]=i;k++;scanf &i);}=j;returnr;}/*顺序表查找*/intsearches(keytypek,stable*r)intj;j=r->len;r->key[0]=k;while(r->key[j]!=k)j—;returnj;}三折半查找的分析、程序、,然后进行关键字查找。如果存在则返冋待查元素的位置,否则显示不存在。2设计思路1)折半查找的基本思想设査找表屮的元素存放在数组r屮,数据元素的下标范用为[low,high],查找的关键字值为key,屮间元素的下标为mid=(low+high)/2,(向下取整),令key与r[mid]的关键字比较:若key=r[mid].key,查找成功,下标为m的记录即为所求,返回mid。若keyvr[mid].key,所要找的记录只能在左半部分记录中,在对左半部分记录中,再对左半部分使用折半查找法继续进行查找,搜索区间缩小一半。若key>r[mid].key,所要找的记录只能在右半部分记录中,在对右半部分记录中,再对右半部分使用折半查找法继续进行查找,搜索区间缩小一半。重复上述过程,直到找到查找表屮某个数据元素的关键字的值等于给定的值key说明查找成功,若出现low的值大Thigh的情况,说明查找不成功。建立一个有序表,数据元素从下标为1的单元开始放入。实现查找算法时,首先将low赋值为1,high等于最后一个数据元索的下标,然后将给定的关键字与查找区间now,high冲间的数据元索的关键字比较,实现查找过程。3折半查找算法描述/*顺序表结构体定义*/typedefstruct{keytypekey[maxsize];intlen;}stable;/*折半查找*/intsearchbin(keytypek,stable*r){—intlow,high,mid;1ow=1;high=r->len;while(low<=high){mid=(1ow+high)/2;if(k==r->key[mid])returnmid;elseif(k<r->key[mid])highpmidT;elselow二mid+1;}return0;四二叉排序树查找的分析、程序、