查找排序实验报告

数据结构实验报告实验名称：查找班 级：12级电气本2学 号：2012081227姓 名：赵雪磊指导教师：梁海丽日 期：2013年11月18日数学与信息技术学院一、 实验目的1.掌握二叉排序树的概念。2.掌握查找的不同方法，并能用高级语言实现查找算法。3.实现二叉排序树的基本操作方法。二、 实验要求给定一个记录关键字的值，与二叉排序树的根结点值比较，如果小于根结点的值，则向左子树查找； 如果大于根结点的值，则向右子树查找。如果查找到叶子结点leaf，仍没有找到记录，则：如果关键字的值小于leaf的值，则插入该leaf结点的左边，做leaf的左孩子，否则做leaf的右孩子。三、 算法描述template class hashdict private: Elem* HT; / 散列表 int M; / 散列表大小 Elem TOMB; /墓碑 int currcnt; / 现有元素数目 Elem EMPTY; / 空槽 int p(Key K, int i) const / 探查函数 return linear(i); int h(int x) const return x % M; / 散列函数 int h(char* x) const / 字符串散列函数 int i, sum; for (sum=0, i=0; xi != 0; i+) sum += (int) xi; return(sum % M); int linear(int i) const return i; /线性探查 int square(int i) const /二次探查 if (i%2=0) return -(i*i/4); else return (i+1)*(i+1)/4; int rehash (Key K, int i) const; int division(int x ) const return x % M; /除余法 int ELFhash ( char* key )const unsigned long h = 0; while(*key) h = ( ch 24; h = g; return h % M; public: hashdict(int sz, Elem e, Elem t)/ 构造函数, e用来定义空槽 M=sz; EMPTY= e; TOMB=t; currcnt=0; HT=new Elemsz; for(int i=0; iM; i+) HTi= EMPTY; hashdict() delete HT; bool hashInsert(const Elem&); bool hashSearch(const Key&, Elem&) const; Elem hashDelete(const Key& K); int size() return currcnt; / 散列表中现有元素数;四、 程序清单#include#include#define OK 1#define ERROR 0int Search_Bin(int score,int length,int key)int low,high,mid;low=1;high=length;while(low=high)mid=(low+high)/2;if(scoremid=key)return mid;else if(keyscoremid)low=mid+1;return ERROR;int main()int score11;int length=10;int key,index;printf(创建查找表:n);for(int i=1;i=length;i+)scanf(%d,&scorei);printf(n输入要查找的关键字n);scanf(%d,&key);if(Search_Bin(score,length,key)index=Search_Bin(score,length,key);printf(n要查找的 %d 在表中的位置是 %d n,key,index);elseprintf(n未查找到 %dn,key);