首页 > 代码库 > 顺序查找,折半查找,二叉排序树的建立,哈希表的建立
顺序查找,折半查找,二叉排序树的建立,哈希表的建立
以下四个验证性实验都做。
(1)顺序查找验证
(2)折半查找验证
(3)二叉排序树的建立
(4)哈希表的建立
#include<iostream>#include<cstdio>#include<cmath>#include<cstdlib>#include<string.h>#include<algorithm>using namespace std;class dijiuzhang{public: int a[10]; struct Node { int data; Node * rchild; Node * lchild; Node(int a):data(a),rchild(NULL),lchild(NULL) {} Node():rchild(NULL),lchild(NULL) {} }; Node * head; Node * cur; dijiuzhang() { Node * head = new Node(); for(int i = 0 ; i < 10 ; i ++) { int tem; while(1) { int flag = 0; tem = rand()%10; for(int j = 0 ; j < i ; j++) { if(tem == a[j]) { flag = 1; break; } } if(flag==0) { a[i] = tem; break; } } cout<<a[i]<<" "; } cout<<endl; } void shunxu(int b)//顺序查找 { cout<<"顺序查找"<<endl; for(int i = 0 ; i < 10 ; i++) { if(a[i] == b) { cout<<"Find!"<<endl; cout<<"i="<<i<<endl; return; } } cout<<"not find"<<endl; } void zheban(int b)//折半查找 { cout<<"折半查找:"<<endl; int low,high,mid; low = 0; high = 9; sort(a,a+10); while(low <= high) { mid = (low + high) / 2; if(a[mid] == b) { cout<<"Find!"<<endl; cout<<"i="<<mid<<endl; return; } else if(a[mid] > b) { high = mid - 1; } else { low = mid + 1; } } cout<<"not find"<<endl; return; } void erchapaixushu()//二叉排序树 { cout<<"二叉排序树dfs"<<endl; for(int i = 0 ; i < 10 ; i++) { Node * tem = new Node(a[i]); if(i==0) { head = tem; cur = tem; continue; } while(1) { if(cur -> data <= tem -> data && cur -> rchild == NULL) { cur -> rchild = tem; cur = head; break; } else if(cur -> data <= tem -> data) { cur = cur -> rchild; } if(cur -> data > tem -> data && cur -> lchild == NULL) { cur -> lchild = tem; cur = head; break; } else if(cur -> data > tem -> data) { cur = cur -> lchild; } } } } void dfs(Node * tem) { if(tem) { dfs(tem -> lchild); cout<<tem -> data<<" "; dfs(tem -> rchild); } } void haxi()//哈希表 { int tem[10]; int chongtu[10] = {1,-1,2,-2,3,-3,4,-4,5,-5}; memset(tem , 0 , sizeof(int)*10); for(int j = 0 ; j < 10 ; j ++) { int temi = 0; int temchongtu = 0; while(1) { if(tem[a[j]%11+temchongtu]==0) { tem[a[j]%11+temchongtu] = a[j]; break; } else { temchongtu = chongtu[temi++]; } } } cout<<endl; cout<<"建立的哈希表:"<<endl; for(int i = 0 ; i < 10 ; i++) { cout<<tem[i]<<" "; } }};int main(){ dijiuzhang duskcl; int a = 3; duskcl.zheban(a); duskcl.shunxu(a); duskcl.erchapaixushu(); duskcl.dfs(duskcl.head); duskcl.haxi();}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。