C++第三次作业
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,结构图如下。
该数据结构内部包含了一个 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。
扩容:
在两种情况下需要进行扩容操作:
- HashDict中节点个数超过了现有数组长度(不包括相等)
- 向某一个桶中的链表增加元素后,该链表长度超过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种指令操作双端队列:
pushFront [val]
,其中val
为一个int
,且val
≥ 0, 例如pushFront 1
,该指令可以将val
放在节点中插入到双端队列的最前面。pushBack [val]
,其中val
为一个int
,且val
≥ 0, 例如pushBack 2
,该指令可以将val
放在节点中插入到双端队列的最后面。popFront
,该指令可以打印双端队列最前面有效节点的val
,并且将其移出双端队列,如果双端队列内没有有效节点,则打印-1。popBack
,该指令可以打印双端队列最后面有效节点的val
,并且将其移出双端队列,如果双端队列内没有有效节点,则打印-1。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
行每行为一条指令,具体如题目描述所示。
输出
popFront
,popBack
,getSize
三条指令存在输出,均输出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 进行许可。