查找算法效率比较.doc

《数据结构》课程设计报告 姓名 杨方 学号实验室A209 座位号 组号 提交日期 8.15 成绩 指导教师 卢欣华 问题解析（对问题的分析、解题思路与解题方法）：问题告诉算法分两步，第一步从文件读数据建立查找表，那么首先要生成数据并建立文件，第二步读数据查找，对于顺序查找，不需要预处理直接进行查找，对于二叉查找树查找则必须先建立二叉树，对于哈希算法则必须先建立哈希表，做完预处理后再进行查找，统计比较次数，实际运行时间，占用内存空间等因素判断算法性能 任务分工及进度安排：第一天做的工作：第一步解决数据生成，采用随机数很容易实现；第二步对数据进行预处理，如进行完全正序排序，逆序排序，将处理后的数据存入data.in中；第二天做的工作：第三步编写顺序查找函数，二叉树查找函数，哈希查找函数，最后读关键字查询，将查询结果输出到data.out文件中；第三天完善程序，写报告 数据结构选择（包括改进或给出）、算法设计：顺序查找采用数组，二叉树查找采用类，哈希查找采用元素为链表的数组；对于顺序查找采用for循环从前到后比较；对于二叉查找树查找，从根节点开始比较，若相等，返回比较结果，若小如根节点对应的数值，则与根节点的左儿子对应的数值进行比较，若大如根节点对应的数值，则与根节点右儿子对应数值进行比较，一直进行下去，返回比较结果；对于哈希查找，先确定关键字在哪条链表，然后遍历链表查找 编程与程序清单：#includeiostream #includetime.h #includefstream #includestring #includecassert #includestdlib.h #includealgorithm using namespace std; templateclass T int Find_s(T data[], int n,T key,int icmp) //顺序查找(从n维数组中查找key,并且给出比较的次数icmp { icmp=0; for(int i=0;in;i++) { icmp++; if(data[i]==key) return i; } return -1; } ///以下是二叉查找树查找法 templateclass T class BintreeNode { public: T data; BintreeNode* left; BintreeNode*right; BintreeNode():left(0),right(NULL){} BintreeNode(T item):data(item),left(NULL),right(NULL){} ~BintreeNode(){ if(left!=0) delete left; if(right!=0) delete right; } }; templateclass T class Bintree { public: int num; BintreeNodeT* root; BintreeNodeT* Find_bt(T key,int icmp,int itype=0)//一个二叉树查找算法，itype=1时有插入功能（不同的值时） { icmp=0; if(root==0) { icmp++; if(itype==0) return NULL; else { num++; return root=new BintreeNodeT(key); } } else { BintreeNodeT* ptr=root,*p; while(ptr!=NULL) { icmp++; p=ptr; if(ptr-data==key) return ptr; else { if(ptr-datakey) ptr=ptr-left; else ptr=ptr-right; } } if(itype) { num++; if(p-datakey) return p-left=new BintreeNodeT(key); else return p-right=new (BintreeNodeT)(key); } return NULL; }//else }//Find_bt Bintree():root(0),num(0){} ~Bintree(){delete root