首页 > 其他分享 >山东大学数据结构实验8 散列表

山东大学数据结构实验8 散列表

时间：2023-04-26 12:55:30浏览次数：35  
标签：数据结构 int NULL next theKey 列表 element 山东大学

要求

使用线性开型寻址实现

描述

给定散列函数的除数D和操作数m，输出每次操作后的状态。
有以下三种操作：

  1. 插入x，若散列表已存在x，输出“Existed”，否则插入x到散列表中，输出所在的下标。
  2. 查询x，若散列表不含有x，输出“-1”，否则输出x对应下标。
  3. 删除x，若散列表不含有x，输出“Not Found”，否则输出删除x过程中移动元素的个数。

格式

输入格式

第一行两个整数D，m。分别代表散列函数的除数D和操作数m。
接下来m行，每行两个整数opt和x，分别代表操作类型和操作数。
若opt为0，代表插入x。
若opt为1，代表查询x。
若opt为2，代表删除x。

输出格式

按要求输出。

样例1

输入

7 12
1 21
0 1
0 13
0 5
0 23
0 26
0 33
1 33
1 33
1 13
1 5
1 1

输出

-1
1
6
5
2
0
3
3
3
6
5
1

样例二

输入

20 30
0 84
0 15
0 54
2 15
2 84
1 54
2 54
0 89
1 89
0 13
0 48
2 89
0 60
0 24
1 13
0 6
1 24
0 31
2 60
2 48
0 49
0 9
1 6
1 13
0 33
2 49
0 60
1 6
2 9
1 60

输出

4
15
14
0
0
14
0
9
9
13
8
0
0
4
13
6
4
11
0
0
9
10
6
13
14
1
0
6
0
0

限制

1s, 1024KiB for each test case.

#include <iostream>

using namespace std;

template<class K, class E>
class hashTable {
public:
    hashTable(int theDivisor = 11);

    void find(const K &) const;

//返回关键字theKey匹配的数对的指针，若不存在匹配的数对，则返回NULL
    void insert( const pair<const K, E>&);

//在字典中插入一个数对thePair,若存在关键字相同的数对,则覆盖
   void erase(const K &theKey);

    int search(const K& theKey) const;


protected:


    pair<const K, E> **table; // 散列表
    int divisor; // 散列函数的除数
    int dSize; // 字典中数对的个数
};

template<class K, class E>
hashTable<K,E>::hashTable(int theDivisor)
{// 构造函数
    divisor = theDivisor;
    dSize=0;
// 分配和初始化散列表数组
    table = new pair<const K, E>* [divisor];
    for (int i = 0; i < divisor; i++) //将所有桶置空
        table[i] = NULL;
}
template<class K, class E>
int hashTable<K,E>::search(const K& theKey) const
{// 搜索一个公开地址散列表，查找关键字为theKey的数对
// 如果匹配的数对存在，则返回它的位置
// 否则返回关键字为theKey的数对可以插入的位置
    int i =(int) theKey % divisor; // 起始桶
    int j = i; // 从起始桶处开始
    do {
        if (table[j]==NULL || table[j]->first == theKey) return j;
        j = (j + 1) % divisor; // 下一个桶
    } while (j != i); // 又返回起始桶?
    return j; // 表已经满
}

template<class K, class E>
void hashTable<K,E>::find(const K& theKey) const
{//返回关键字theKey匹配的数对的指针
//若不存在匹配的数对，则返回NULL
//搜索散列表
    int b = search(theKey);
//判断table[b]是否是匹配数对
    if (table[b] ==NULL || table[b]->first != theKey)
      cout<<-1<<endl;//未找到匹配数对
    else cout<<b<<endl; //找到匹配数对
}
template<class K, class E>
void hashTable<K,E>::insert( const pair<const K, E>& thePair)
{//在字典中插入一个数对thePair,若存在关键字相同的数对，
    int b = search(thePair.first);
// 检查匹配的数对是否存在
//没有匹配的数对，且表不满,则插入数对
    if (table[b]==NULL)
    {table[b] =new pair<const K,E>(thePair) ;
        dSize++;
    cout<<b<<endl;}
    else if (table[b]->first == thePair.first )
    cout<<"Existed"<<endl;

}

// 删除
template<class K, class E>
void hashTable<K, E>::erase(const K& theKey) {
    int b = search(theKey);
    if (table[b] == NULL || table[b]->first != theKey) {
        cout << "Not Found" << endl;
    } else {
        table[b] = NULL; // 删除
        int n = b, a = b; // 设置删除点，便于遍历
        b = (b + 1) % divisor; // 从删除的后一位开始遍历
        int x = 0; // 记录移动个数
        while (table[b] != NULL && b != n) { // 没有遇到空桶或者没有遍历一遍的话继续执行
            int m = (int) table[b]->first % divisor; // b索引中数字应该在的索引位置
            if ((a < b && b < m) || (b < m && m <= a) || (m <= a && a < b)) {
                table[a] = table[b];
                a = b;
                x++;
            }
            b = (b + 1) % divisor; // 指针移动
        }
        table[a] = NULL; // 最后进行删除，使其等于空
        cout << x << endl;
    }

}


int main(){
    int D, m;
    cin >> D >> m;
    hashTable<int,int> a(D);
    for(int i = 0; i < m; i++){
        int op, x;
        cin >> op >> x;
        switch(op){
            case 0: { pair<int, int>p(x, 0);a.insert(p);}
                break;
            case 1: { a.find(x);}
                break;
            case 2: a.erase(x);
                break;
        }
    }

    return 0;
}

要求

使用链表散列方式

描述

给定散列函数的除数D和操作数m，输出每次操作后的状态。

有以下三种操作：

  1. 插入x，若散列表已存在x，输出"Existed"
  2. 查询x，若散列表不含有x，输出"Not Found"，否则输出x所在的链表长度
  3. 删除x，若散列表不含有x，输出"Delete Failed"，否则输出x所在链表删除x后的长度

格式

输入格式

第一行两个整数D(1<=D<=3000)和m(1<=m<=3000)，其中D为散列函数的除数，m为操作数。

接下来的m行，每行两个整数opt和x，分别代表操作类型和操作数。

若opt为0，则代表向散列表中插入x；
若opt为1，代表查询散列表中x是否存在；
若opt为2，(如果散列表中含有x)，删除x。

数据保证散列表不会溢出。

输出格式

按需输出。

样例1

样例输入

    7 12
    1 21
    0 1
    0 13
    0 5
    0 23
    0 26
    0 33
    1 33
    1 33
    1 13
    1 5
    1 1

样例输出

    Not Found
    3
    3
    1
    3
    1

样例2

样例输入

    7 15
    2 10
    0 10
    0 10
    2 10
    1 10
    0 10
    1 10
    0 17
    0 2
    0 16
    0 11
    2 2
    2 10
    1 11
    1 17

样例输出

    Delete Failed
    Existed
    0
    Not Found
    1
    1
    1
    1
    1

数据范围

对于前60%的数据，只包含插入和查询操作
对于后40%的数据，包含插入、查询与删除操作

#include <iostream>

using namespace std;

struct Node {
    int element;
    Node *next;

    Node(int theElement) {
        element = theElement;
    }
};

class linearListHashtable {
public:
    linearListHashtable() {
        firstNode = NULL;
        size = 0;
    }

    ~linearListHashtable();

    void insert(int element);

    void find(int element);

    void erase(int element);


private:
    Node *firstNode;
    int size;

};

void linearListHashtable::insert(int element) {
    int flag = 0;
    Node *cur = firstNode;
    if(cur==NULL){firstNode=new Node(element);size++;firstNode->next=NULL;return ;}
    while (cur->next !=NULL ) {
        if (element == cur->element) {
            cout << "Existed" << endl;
            flag = 1;
            break;
        }
        cur = cur->next;
    }
    if(cur->element==element&&flag==0){cout<<"Existed"<<endl;flag=1;}
    if (flag != 1)
    {cur->next = new Node(element);
    size++;
    cur->next->next=NULL;}
}

void linearListHashtable::find(int element) {
    int flag = 0;
    Node *cur = firstNode;
    if(firstNode==NULL){cout << "Not Found" << endl;return ;}
    while (cur ->next!=NULL ) {
        if (element == cur->element) {
            cout << size << endl;
            flag = 1;
            break;
        }
        cur = cur->next;
    }if(cur->element==element&&flag==0){
        cout<<size<<endl;
        flag=1;
    }
    if (flag == 0)
        cout << "Not Found" << endl;
}

void linearListHashtable::erase(int element) {
    int flag = 0;
    if(firstNode==NULL){cout << "Delete Failed" << endl;return;}
    int Element=firstNode->element;
    if (firstNode->element == element) {
        firstNode = firstNode->next;
        size--;
        cout << size  << endl;
        return;
    }
    Node *cur = firstNode->next;
    Node *pre = firstNode;
    while (cur !=NULL ) {
        if (element == cur->element) {
            pre->next = pre->next->next;
            size--;
            cout << size<<endl;
            flag = 1;
            break;
        }
        cur = cur->next;
        pre = pre->next;
    }
    if (flag == 0)
        cout << "Delete Failed" << endl;

}


int main() {
    int D, m;
    cin >> D>>m;
    linearListHashtable *a = new linearListHashtable[D];
    int opt;
    int value = 0, index = 0;
    while (m--) {
        cin >> opt;
        switch (opt) {
            case 0: {
                cin >> value;
                index = value % D;
                a[index].insert(value);
            }
                break;
            case 1: {
                cin >> value;
                index = value % D;
                a[index].find(value);

            }
                break;
            case 2: {
                cin>>value;
                index =value % D;
                a[index].erase(value);

            }
                break;


        }


    }
return 0;

}

标签：数据结构,int,NULL,next,theKey,列表,element,山东大学
From： https://www.cnblogs.com/lyz103/p/17355583.html

相关文章

  • python 快速替换csv数据集字符串列表中的表情符号为空，asyncio，re，pandas
     传统的字符串列表替换字符串使用遍历非常慢比如下面这段代码，如果处理几十万或上百万的数据集时，会非常的慢，几小时几天都可能importrep=re.compile(u'['u'\U0001F300-\U0001F64F'u'\U0001F680-\U0001F6FF'u'\u2600-\u2B55\U00010000-\U0010ffff]+')#text="超详细修......
  • 索引列表的制作，中文拼音排序
    业务上最近需要做一个选择人员的页面，右侧会有一个快速索引，样式如下：这个首先要把名字转拼音，然后取首字母，转大写，然后在新建的空对象里进行比对，如果有这个字母，就吧这条数据push进去，没有的话就在对象里创建该首字母的数组，再push进去，这样就形成了一个包含26个英文字母数组的对象结构......
  • C++数据结构(树)
    树是一种递归定义的数据结构，如果树中节点的各子树从左到右是有次序的，不能互换，则称该树为有序树，否则叫无序树。关于树的节点：节点拥有的子树的个数叫做节点的度如果度为0，那么该节点叫做叶节点或终端节点，除了根节点外的分支节点称为内部节点树的度是各节点度的最大值。节点的子......
  • 什么是数据结构？
    数据结构研究计算机数据间关系，包括数据的逻辑结构和存储结构及其操作。我们接触一种数据结构，一定要掌握这三个方面基本概念1.数据（Data）数据即信息的载体，是能够输入到计算机中并且能被计算机识别、存储和处理的符号总称。2.数据元素（DataElement）数据......
  • 初识数据结构
    什么是数据结构，数据结构可以理解为我们规定数据元素之间具有某种关系或规则，程序员根据这些规则能够更好的管理和操作这些数据。数据元素的关系包括三种：线性关系——1：1线性关系即为数据是一对一的关系，即除了开头的数据元素和最后的数据元素，其他如何应该数据元素有......
  • 2023年电子科技大学ACM-ICPC暑假前集训-数据结构
    Preface学校针对大一新生的暑假前集训的第一个专题DS，由于要求集体写题解就顺便把写好的发上来了由于下面都写了题意所以直接看也能有很多收获，当然非电专的学生的话就没法交题了代码的话由于专题还没结束怕放上来然后被CV导致被爆破，所以应该在这周六专题结束后会放上来下面都是......
  • 山东大学数据结构实验七
    卡片游戏tips：这个题还要参考，同学要加油啦~~要求创建队列类，使用数组描述的循环队列实现卡片游戏描述假设桌上有一叠扑克牌，依次编号为1-n（从上至下）。当至少还有两张的时候，可以进行操作：把第一张牌扔掉，然后把新的第一张（原先扔掉的牌下方的那张牌,即第二张牌）放到整叠牌的最后。......
  • 山东大学数据结构实验六
    计算表达式tips：不要全文复制，会被查重哦注意因为精度问题，请使用double存数据。要求创建栈类，采用数组描述；计算数学表达式的值。输入数学表达式，输出表达式的计算结果。数学表达式由单个数字和运算符+、-、*、/、(、)构成，例如2+3*(4+5)-6/4。假定表达式输入格式合法。格式......
  • 山东大学数据结构实验一（2）
    题目描述现有一个有n个元素的序列\(a=[a_{1},a_{2},\cdots,a_{n}]\)，定义其价值为\(\sum_{i=1}^{n}a_{i}\oplusi\)给出这样一个序列，求其所有排列的价值\(v_{i}\)的或\(v_{1}|v_{2}|\cdots|v_{n-1}|v_{n}\)其中\(|\)为位运算或操作，\(\oplus\)为位运算异......
  • 山东大学数据结构实验一（1）
    题目描述现有一个有\(n\)个元素的序列\(a=[a_1,a_2,\cdots,a_n]\)，定义这个序列的价值为\(\sum_{i=1}^{n}i\timesa_i\)。空序列的价值为\(0\)。先给你一个长度为\(n\)的序列\(a\)，求\(a\)中所有子集价值的异或和，要求子集中元素的相对位置保持不变。异或和:位运算的一种。如果a......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99