首页 > 代码库 > 顺序查找,折半查找,二叉排序树的建立,哈希表的建立

顺序查找,折半查找,二叉排序树的建立,哈希表的建立

以下四个验证性实验都做。

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();}