C++第三次作业

Kiyotaka Wang Lv3

C++第三次作业

整数计算器

请使用函数指针完成该题。

现有一个整数计算器,可以对两个正整数x和y进行运算,并输出一个整数结果。计算器支持的运算指令如下:

add: x+y。

sub: x-y。

mul: x*y。

lcm: x和y的最小公倍数。

gcd: x和y的最大公约数。

quo:x/y的商。

res:x/y的余数。

输入描述

第1行为一个正整数N,表示后续的输入行数。

第2~N+1行,每行的输入为“x y [运算指令]”。

输出描述

N行整数,分别对应第2~N+1行指令的运算结果。

示例

示例 1

输入

3
1 2 add
9 11 sub
4 2 mul

输出

3
-2
8

示例 2

输入

4
1 2 lcm
4 2 gcd
33 11 quo
5 2 res

输出

2
2
3
1

分析

求最小公倍数的方法就是两数相乘除以最大公约数,似乎离散数学学过,但当时忘了,还是上网查的。。。

然后这题我一开始写的时候使用的是getline然后分割字符串处理,但其实cin就能解决一切的问题了。。。虽然ac的挺顺利的,但现在的版本明显更简单。

#include <iostream>
using namespace std;
int add(int x, int y){
    return  x + y;
}

int sub(int x, int y){
    return x - y;
}

int mul(int x, int y){
    return x * y;
}

int gcd(int x, int y){
    while(y != 0){
        int rem = x % y;
        x = y;
        y = rem;
    }
    return x;
}

int lcm(int x, int y){
    return x * y / gcd(x,y);
}

int quo(int x, int y){
    return x / y;
}

int res(int x, int y){
    return x % y;
}

int func(int (*p)(int, int), int x, int y){
    return p(x, y);
}

int main(){
    int n;
    cin >> n;
    for(int i = 0; i < n; i++){
        string temp;
        int x,y;
        cin >> x >> y >> temp;
        if(temp == "add"){
            cout << func(add, x, y) << endl;
        }else if(temp == "sub"){
            cout << func(sub, x, y) << endl;
        }else if(temp == "mul"){
            cout << func(mul, x, y) << endl;
        }else if(temp == "lcm"){
            cout << func(lcm, x, y) << endl;
        }else if(temp == "gcd"){
            cout << func(gcd, x, y) << endl;
        }else if(temp == "quo"){
            cout << func(quo, x, y) << endl;
        }else if(temp == "res"){
            cout << func(res, x, y) << endl;
        }
    }
    return 0;
}

HashDict

现在设计一个由数组和链表共同组成的一个存储键值对的数据结构HashDict,结构图如下。

hashdict

该数据结构内部包含了一个 Entry 类型的数组 table。每个 Entry 存储着键值对。它包含了四个字段(hashCode, key, value, next),从 next 字段我们可以看出 Entry 是一个链表中的节点。即数组中的每个位置被当成一个桶,一个桶存放一个链表。其中键值对中key为整数,value为字符串。

这个数据结构存储数据时的几种操作说明如下:

  • 添加元素:当要向该数据结构中添加一个键值对(key-value)时,先对key做哈希运算,哈希函数:hash = | 3key^3+5key^2+7*key+11 | ,上述公式中的 | 是绝对值符号,获取key的hash值,然后用hash值对数组table的长度length取模获取键值对应该存储的位置pos,公式为 pos = hash % length 。如果出现哈希冲突的情况,即计算出的位置pos已经存储了数据,则将键值对插入到当前位置已有的链表中,要求插入之后链表是按从小到大排序(按键排序);如果没有出现哈希冲突,则在当前位置中保存一个单节点链表。

  • 删除元素:按照和添加元素同样的逻辑获取对应的键值对所在的位置pos,然后在这个位置里的链表中剔除掉相应的链表节点,如果是单节点链表,则直接把当前位置的链表置为null。

  • 扩容:

    在两种情况下需要进行扩容操作:

    1. HashDict中节点个数超过了现有数组长度(不包括相等)
    2. 向某一个桶中的链表增加元素后,该链表长度超过4(不包括4)

    每次扩容操作是将数组长度变为之前数组的两倍+1(如原来长度为8,扩容后为17),并将原有的键值对按照添加元素的规则(重新计算hash值取模)重新添加到新的数组中

  • 查询:查询数组的指定位置存储了哪些键值对。

输入格式

首先输入一个数字L,L代表数组table的初始长度。

然后输入一个数字N,N代表操作次数,下面N行是具体的操作。

操作行的输入格式:

  • 添加元素:add [key] [value], add 代表该行执行添加操作,[key]和[value]是键值对的相应值。如add 1 cpp代表向HashDict中添加key为1,value为cpp的一个键值对。
  • 删除元素:delete [key], delete 代表该行执行删除操作,[key]是要删除的键值对的键值。保证这个键值一定在HashDict中已经存在。
  • 查询:search [pos],search代表执行查询操作,[pos]代表要查询的数组位置,需要输出该位置的链表。保证pos小于数组table的长度。如search 0代表查询数组table第一个位置中存储了哪些键值对。

输出格式:

只有查询操作需要输出,如果查询位置没有键值对,则直接输出null,如果有,则按照

[key]:[value]->[key]:[value]的格式输出(参考示例)。

示例1

输入:

4
4
add 10 cpp
add 5 cat
add 3 dog
search 2

输出:

3:dog->5:cat

示例2

输入:

2
11
add 5 cat
add 3 dog
search 0
add 10 cpp
search 0
search 1
add 7 bird
add 17 pig
search 4
delete 7
search 4

输出:

3:dog->5:cat
null
5:cat->10:cpp
7:bird->17:pig
17:pig

示例3

输入:

4
10
add 5 cat
add 3 dog
add 7 cat1
add 11 dog1
search 2
add 9 cpp
search 2
search 5
search 6
search 8

输出:

3:dog->5:cat->7:cat1->11:dog1
7:cat1->9:cpp
3:dog
5:cat->11:dog1
null

分析

首先是要理解这道题目,我一开始没看明白题目,一直看不懂样例二为什么第二次search 0就是null了,后来经提醒才发现原来是节点数超过了length就要扩容,而不是什么index大于length(本来就取模了index也不可能大于啊)。。。

然后链表是一个一个插入的,不需要写什么排序算法,只需要在插入的时候注意点就行了。总之这道题花了6小时,其中水通识课的三小时是一事无成的,当然还有个原因是对C++指针的不熟练,比如二维数组Entry的声明那边我一开始并没有写出正确的语法,于是直接开了10000。。。

还有个问题就是hashcode需要用long long存储,不然会出现运行异常。rehash这件事情我并没有从数学角度上面理解,但是确确实实是需要的,并且也是有这个可能性的,不然会有三个错误。

#include <iostream>
#include <cmath>
#include <map>
using namespace std;
struct Node{
    long long hashcode;
    int k;
    string value;
    Node *next;
    Node(int x, string s, long long hashcode) : hashcode(hashcode), k(x), value(std::move(s)), next(nullptr){}
    Node(int x, string s, Node *next) : hashcode(0), k(x), value(std::move(s)), next(next){}
};

long long myhash(int key){
    return (long long)abs( 3 * pow(key, 3) + 5 * pow(key, 2) + 7 * key + 11);
}

int lenOfLinkedList(Node *head){
    int len = 0;
    while (head != nullptr){
        head = head->next;
        len++;
    }
    return len;
}

Node* add(Node *head, int key, string value, long long hashcode){
    Node *dummy = new Node(-1, "", head);
    Node *p = dummy;
    while (p->next != nullptr){
        if (key < p->next->k){
            Node *temp = p->next;
            p->next = new Node(key, std::move(value), hashcode);
            p->next->next = temp;
            return dummy->next;
        }
        p = p->next;
    }
    p->next = new Node(key, std::move(value), hashcode);
    return dummy->next;
}

Node* del(Node *head, int key){
    Node *dummy = new Node(-1, "", head);
    Node *p = dummy;
    while (p->next != nullptr){
        if (p->next->k == key){
            p->next = p->next->next;
            return dummy->next;
        }
        p = p->next;
    }
    return dummy->next;
}

void print(Node *head){
    while (head != nullptr){
        cout << head->k << ":" << head->value;
        if (head->next != nullptr)cout << "->";
        head = head->next;
    }
    cout << endl;
}

bool check(Node **Entry, int L){
    for (int i = 0; i < L; ++i) {
        if (lenOfLinkedList(Entry[i]) > 4){
            return true;
        }
    }
    return false;
}

int main(){
    int L, N;
    cin >> L >> N;
    Node **Entry = new Node*[L];
    map<int, string> Map;
    for (int i = 0; i < L; ++i) {
        Entry[i] = nullptr;
    }
    int cnt = 0;
    for(int i = 0; i < N; i++){
        string dir, value;
        int key;
        long long hashcode;
        cin >> dir;
        cin >> key;
        if (dir == "add"){
            cnt++;
            cin >> value;
            hashcode = myhash(key);
            int index = hashcode % L;
            if (cnt > L){
                L = 2 * L + 1;
                Entry = new Node * [L];
                index = hashcode % L;
                for (int m = 0; m < L; ++m) {
                    Entry[m] = nullptr;
                }
                for (pair<int, string> p : Map) {
                    long long hashcode1 = myhash(p.first);
                    Entry[hashcode1 % L] = add(Entry[hashcode1 % L], p.first, p.second, hashcode1);
                }
            }
            Entry[index] = add(Entry[index], key, value, hashcode);
            Map[key] = value;
            // 有用例需要多次rehash
            while (check(Entry, L)){
                L = 2 * L + 1;
                Entry = new Node * [L];
                for (int m = 0; m < L; ++m) {
                    Entry[m] = nullptr;
                }
                for (pair<int, string> p : Map) {
                    long long hashcode1 = myhash(p.first);
                    Entry[hashcode1 % L] = add(Entry[hashcode1 % L], p.first, p.second, hashcode1);
                }
            }

        }else if(dir == "delete"){
            hashcode = myhash(key);
            int index = hashcode % L;
            Entry[index] = del(Entry[index], key);
            Map.erase(key);
        }else{
            int index = key;
            if (Entry[index] == nullptr)cout << "null" << endl;
            else print(Entry[index]);
        }
    }
}

双向队列

题目描述

使用链表实现一个双端队列,双端队列的头部和尾部均可以进行插入值取出值操作,你可以使用以下5种指令操作双端队列:

  1. pushFront [val],其中val为一个int,且val ≥ 0, 例如pushFront 1,该指令可以将val放在节点中插入到双端队列的最前面
  2. pushBack [val],其中val为一个int,且val ≥ 0, 例如pushBack 2,该指令可以将val放在节点中插入到双端队列的最后面
  3. popFront,该指令可以打印双端队列最前面有效节点val,并且将其移出双端队列,如果双端队列内没有有效节点,则打印-1
  4. popBack,该指令可以打印双端队列最后面有效节点val,并且将其移出双端队列,如果双端队列内没有有效节点,则打印-1
  5. getSize,该指令可以打印双端队列的有效节点数

结构设计

我们设计好了部分结构体和部分方法声明,可以将它们运用到自己的代码中,也可以自己进行设计和实现,但必须使用链表

//链表节点
struct Node{
    Node* next;//后一个节点
    Node* prev;//前一个节点
    int val;//该节点存放的数字
};

//双端队列
struct Deque{
    int size;//有效节点数
    Node* front;//虚拟头节点,不作为有效节点
    Node* rear;//虚拟尾节点,不作为有效节点
};

void push_front (Deque* self, int value);
void push_back (Deque* self, int value);
void pop_front (Deque* self);
void pop_back (Deque* self);

输入输出

输入

第一行输入一个自然数n,表示接下来会进行n次操作。

接下来的n行每行为一条指令,具体如题目描述所示。

输出

popFrontpopBackgetSize三条指令存在输出,均输出int,且需要进行换行。

输入输出示例

示例1

输入

5
pushFront 1
pushBack 2
popBack
popBack
popFront

输出

2 //popBack的输出
1 //popBack的输出
-1 //popFront的输出
示例2

输入

复制代码

5
pushFront 1
pushFront 2
getSize
popBack
getSize

输出

复制代码

2 //getSize的输出
1 //popBack的输出
1 //getSize的输出

分析

这道题比较基础,属于基本的链表的使用,不过需要注意一些边界条件(不过这也是链表的基操)。

#include <iostream>
using namespace std;
//链表节点
struct Node{
    Node* next;//后一个节点
    Node* prev;//前一个节点
    int val;//该节点存放的数字
};

//双端队列
struct Deque{
    int size;//有效节点数
    Node* front;//虚拟头节点,不作为有效节点
    Node* rear;//虚拟尾节点,不作为有效节点
};

void push_front (Deque* self, int value);
void push_back (Deque* self, int value);
void pop_front (Deque* self);
void pop_back (Deque* self);
int main(){
    int n;
    cin >> n;
    auto *list = new Deque{0, nullptr, nullptr};
    for (int i = 0; i < n; ++i) {
        string dir;
        cin >> dir;
        int val;
        if (dir == "pushFront"){
            cin >> val;
            push_front(list, val);
        }else if(dir == "pushBack"){
            cin >> val;
            push_back(list, val);
        }else if(dir == "popFront"){
            pop_front(list);
        }else if(dir == "popBack"){
            pop_back(list);
        }else{
            cout << list->size << endl;
        }
    }
    return 0;
}
void push_front (Deque* self, int value){
    Node *p = new Node{self->front, nullptr, value};
    if (self->front == nullptr){
        self->front = p;
        self->rear = p;
        self->size++;
        return;
    }
    self->front->prev = p;
    self->front = p;
    self->size++;
}
void push_back (Deque* self, int value){
    Node *p = new Node{nullptr, self->rear, value};
    if (self->rear == nullptr){
        self->rear = p;
        self->front = p;
        self->size++;
        return;
    }
    self->rear->next = p;
    self->rear = p;
    self->size++;
}
void pop_front (Deque* self){
    Node *p = self->front;
    if (p == nullptr){
        cout << -1 << endl;
        return;
    }
    self->front = p->next;
    cout << p->val << endl;
    self->size--;
    if (self->size == 0){
        self->front = nullptr;
        self->rear = nullptr;
    }
    delete p;
}
void pop_back (Deque* self){
    Node *p = self->rear;
    if (p == nullptr){
        cout << -1 << endl;
        return;
    }
    self->rear = p->prev;
    cout << p->val << endl;
    self->size--;
    if (self->size == 0){
        self->front = nullptr;
        self->rear = nullptr;
    }
    delete p;
}
  • 标题: C++第三次作业
  • 作者: Kiyotaka Wang
  • 创建于 : 2022-10-21 22:41:18
  • 更新于 : 2022-11-21 13:02:01
  • 链接: https://hmwang2002.github.io/2022/10/21/c-di-san-ci-zuo-ye/
  • 版权声明: 本文章采用 CC BY-NC-SA 4.0 进行许可。