数据结构题目-哈希

目录

A.Hash表-线性探测法解决冲突

B.求3阶B-树的深度

C.输出3阶B-树的构造过程

D.Hash表-链表法解决冲突 

***************************仅作储存代码使用*********************

A.Hash表-线性探测法解决冲突

#include<bits/stdc++.h>
typedef unsigned long long ll;
using namespace std;
 
int main()
{
    int n;
    cin>>n;
    string a[15];
    for(int i=0;i<10;i++)
    a[i]="#";
    while(n--)
    {
        string s;
        cin>>s;
        int len=s.length();
        int num=0;
        for(int i=len-1;i>=len-4;i--)
            num+=int(s[i])-48;
        num=num%10;
        for(int i=0;i<=10;i++)
        {
            if(a[num+i]=="#")
            {
                a[num+i]=s;
                break;
            }
            if(a[num-i]=="#")
            {
                a[num-i]=s;
                break;
            }
        }
    }
    for(int i=0;i<10;i++)
        cout<<a[i]<<endl;
}

B.求3阶B-树的深度

#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
 
 
struct BTreeNode{
    int n;
    bool leaf;
    int keys[4];
    BTreeNode* child[4];
    BTreeNode* parent;
    int level;
};
 
BTreeNode* Init(){
    BTreeNode* node=new BTreeNode();
    node->leaf=true;
    node->n=0;
    node->parent=nullptr;
    for(int i=0;i<4;i++)
    {
        node->child[i]=nullptr;
        node->keys[i]=0;
    }
    node->level=0;
    return node;
}
 
struct BTree{
    BTreeNode* root;
    int degree;
};
 
void dfs(const BTreeNode* root)
{
    for(int i=0;i<root->level;i++)
    {
        cout<<"    ";
    }
    for(int i=0;i<root->n;i++)
    {
        cout<<root->keys[i]<<" ";
    }
    cout<<endl;
    if(root->leaf)
    return ;
    for(int i=0;i<root->n;i++)
    {
        root->child[i]->leaf=root->level+1;
        dfs(root->child[i]);
    }
}
 
void print(BTree &b)
{
    dfs(b.root);
}
 
BTreeNode *find(BTreeNode* root,int key)
{
    int i=0;
    for(i=0;i<root->n;i++)
    {
        if(root->keys[i]>=key)
        {
            break;
        }
    }
    if(root->leaf)
    {
        return root;
    }
    else
    {
        return find(root->child[i],key);
    }
}
 
int insert(BTreeNode* &node,int key)
{
    int index=node->n;
    while(index>=1&&node->keys[index-1]>key)
    {
        node->keys[index]=node->keys[index-1];
        node->child[index+1]=node->child[index];
        index--;
    }
    node->keys[index]=key;
    node->n++;
    return index;
}
 
void split(BTree &b,BTreeNode* &node)
{
    BTreeNode* temp=node;
    BTreeNode* node1=Init();
    BTreeNode* node2=Init();
    node1->leaf=node2->leaf=node->leaf;
    node1->n=node2->n=1;
    node1->keys[0]=node->keys[0];
    node1->child[0]=node->child[0];
    node1->child[1]=node->child[1];
    if(node1->child[0]!=nullptr)
    {
        node1->child[0]->parent=node1;
    }
    if(node1->child[1]!=nullptr)
    {
        node1->child[1]->parent=node1;
    }
 
 
    node2->keys[0]=node->keys[2];
    node2->child[0]=node->child[2];
    node2->child[1]=node->child[3];
    if(node2->child[0]!=nullptr)
    {
        node2->child[0]->parent=node2;
    }
    if(node2->child[1]!=nullptr)
    {
        node2->child[1]->parent=node2;
    }
 
    BTreeNode* parent=node->parent;
    if(parent==nullptr)
    {
        parent=Init();
        parent->leaf=false;
        parent->n=1;
        parent->keys[0]=node->keys[1];
        parent->child[0]=node1;
        parent->child[1]=node2;
        node1->parent=node2->parent=parent;
        b.root=parent;
    }
    else
    {
        int index=insert(parent,node->keys[1]);
        parent->child[index]=node1;
        parent->child[index+1]=node2;
        node1->parent=node2->parent=parent;
        if(parent->n==b.degree)
        {
            split(b,parent);
        }
    }
    delete temp;
}
 
void insert(BTree &b,int key)
{
    if(b.root==nullptr)
    {
        b.root=Init();
        b.root->keys[0]=key;
        b.root->n=1;
    }
    else
    {
        BTreeNode* node=find(b.root,key);
        insert(node,key);
        if(node->n==b.degree)
        {
            split(b,node);
        }
    }
}
 
int depth(BTreeNode* root)
{
    if(root->leaf)
    {
        return 1;
    }
    else
    {
        return depth(root->child[0])+1;
    }
}
 
 
int main()
{
    BTree b;
    b.degree=3;
    b.root=nullptr;
    int n;
    cin>>n;
    while(n--)
    {
        int temp;
        cin>>temp;
        insert(b,temp);
    }
    cout<<depth(b.root);
    return 0;
}

C.输出3阶B-树的构造过程

#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
 
 
struct BTreeNode{
    int n;
    bool leaf;
    int keys[4];
    BTreeNode* child[4];
    BTreeNode* parent;
    int level;
};
 
BTreeNode* Init(){
    BTreeNode* node=new BTreeNode();
    node->leaf=true;
    node->n=0;
    node->parent=nullptr;
    for(int i=0;i<4;i++)
    {
        node->child[i]=nullptr;
        node->keys[i]=0;
    }
    node->level=0;
    return node;
}
 
struct BTree{
    BTreeNode* root;
    int degree;
};
 
void dfs(const BTreeNode* root)
{
    for(int i=0;i<root->level;i++)
    {
        cout<<"    ";
    }
    for(int i=0;i<root->n;i++)
    {
        cout<<root->keys[i]<<" ";
    }
    cout<<endl;
    if(root->leaf)
    return ;
    for(int i=0;i<root->n+1;i++)
    {
        root->child[i]->level=root->level+1;
        dfs(root->child[i]);
    }
}
 
void print(BTree &b)
{
    dfs(b.root);
}
 
BTreeNode *find(BTreeNode* root,int key)
{
    int i=0;
    for(i=0;i<root->n;i++)
    {
        if(root->keys[i]>=key)
        {
            break;
        }
    }
    if(root->leaf)
    {
        return root;
    }
    else
    {
        return find(root->child[i],key);
    }
}
 
int insert(BTreeNode* &node,int key)
{
    int index=node->n;
    while(index>=1&&node->keys[index-1]>key)
    {
        node->keys[index]=node->keys[index-1];
        node->child[index+1]=node->child[index];
        index--;
    }
    node->keys[index]=key;
    node->n++;
    return index;
}
 
void split(BTree &b,BTreeNode* &node)
{
    BTreeNode* temp=node;
    BTreeNode* node1=Init();
    BTreeNode* node2=Init();
    node1->leaf=node2->leaf=node->leaf;
    node1->n=node2->n=1;
    node1->keys[0]=node->keys[0];
    node1->child[0]=node->child[0];
    node1->child[1]=node->child[1];
    if(node1->child[0]!=nullptr)
    {
        node1->child[0]->parent=node1;
    }
    if(node1->child[1]!=nullptr)
    {
        node1->child[1]->parent=node1;
    }
 
 
    node2->keys[0]=node->keys[2];
    node2->child[0]=node->child[2];
    node2->child[1]=node->child[3];
    if(node2->child[0]!=nullptr)
    {
        node2->child[0]->parent=node2;
    }
    if(node2->child[1]!=nullptr)
    {
        node2->child[1]->parent=node2;
    }
 
    BTreeNode* parent=node->parent;
    if(parent==nullptr)
    {
        parent=Init();
        parent->leaf=false;
        parent->n=1;
        parent->keys[0]=node->keys[1];
        parent->child[0]=node1;
        parent->child[1]=node2;
        node1->parent=node2->parent=parent;
        b.root=parent;
    }
    else
    {
        int index=insert(parent,node->keys[1]);
        parent->child[index]=node1;
        parent->child[index+1]=node2;
        node1->parent=node2->parent=parent;
        if(parent->n==b.degree)
        {
            split(b,parent);
        }
    }
    delete temp;
}
 
void insert(BTree &b,int key)
{
    if(b.root==nullptr)
    {
        b.root=Init();
        b.root->keys[0]=key;
        b.root->n=1;
    }
    else
    {
        BTreeNode* node=find(b.root,key);
        insert(node,key);
        if(node->n==b.degree)
        {
            split(b,node);
        }
    }
}
 
int depth(BTreeNode* root)
{
    if(root->leaf)
    {
        return 1;
    }
    else
    {
        return depth(root->child[0])+1;
    }
}
 
 
int main()
{
    BTree b;
    b.degree=3;
    b.root=nullptr;
    int n;
    cin>>n;
    while(n--)
    {
        int temp;
        cin>>temp;
        cout<<"====insert a key:"<<temp<<endl;
        insert(b,temp);
        print(b);
        cout<<"=================="<<endl;
    }
    return 0;
}

D.Hash表-链表法解决冲突 

#include<bits/stdc++.h>
typedef unsigned long long ll;
using namespace std;
 
int main()
{
    int n;
    cin>>n;
    string a[15];
    for(int i=0;i<10;i++)
    a[i]="#";
    while(n--)
    {
        string s;
        cin>>s;
        int len=s.length();
        int num=0;
        for(int i=len-1;i>=len-4;i--)
            num+=int(s[i])-48;
        num=num%10;
        if(a[num]=="#")
            a[num]=s;
        else
            a[num]=s+" "+a[num];
         
    }
    for(int i=0;i<10;i++)
        cout<<a[i]<<endl;
}