826. 单链表
使用数组模拟链表,因为采用结构体+new的方式比较慢,笔试中一般不使用。单链表的用途是邻接表,邻接表的应用场景是存储树和图。
每一个结点存储val(结点值)以及next(指针,指向下个节点的地址),用e[N]数组来存储节点的值,ne[N]数组来存储节点的next指针是多少,此外多定义一个head表示头指针的位置,一个idx表示当前已经用到了哪个点。e[N]和ne[N]是通过下标关联起来。如图所示
对于插入操作,如将红色点插入到头结点的位置(头插法)
void add_to_head(int x){e[idx] = x;ne[idx] = head;head = idx++;
}
将元素插入到下标为k的结点后面
void add(int k, int x){e[idx] = x;ne[idx] = ne[k];ne[k] = idx++;
}
将下标为k的结点后面的结点删掉
void remove(int k){ne[k] = ne[ne[k]];
}
题目思路
- 向链表头插入一个数
- 删除第 k个插入的数后面的一个数
- 在第 k个插入的数后插入一个数
c++ 代码
#include<iostream>
using namespace std;
const int N = 100000;
int ne[N], e[N], head, idx;
//val[i]:表示结点i的值
//e[i]: 表示结点的下个节点的位置
//head:表示头指针的位置
//idx:表示当前已经用到了哪个点
void init(){head = -1;idx = 0;
}//将x查到头结点
void add_to_head(int x){e[idx] = x;ne[idx] = head;head = idx++;
}
void add(int k, int x){e[idx] = x;ne[idx] = ne[k];ne[k] = idx++;
}
void remove(int k){ne[k] = ne[ne[k]];
}
int main(){int m;cin >> m;init();while(m--){int k, x;char op;cin >> op;if(op == 'H'){cin >> x;add_to_head(x);}else if(op == 'D'){cin >> k;if(!k){head = ne[head];}remove(k - 1);}else if(op == 'I'){cin >> k >> x;add(k - 1, x);}}// 将整个结点进行遍历for(int i = head; i != -1; i = ne[i]){cout << e[i] << ' ';}return 0;
}
827. 双链表
题目思路
双链表就是每一个结点有两个指针,一个指向前一个结点,一个指向后一个结点,用两个数组去表示,l[N]表示左边(前面)结点的下标,r[N]表示右边(后边)结点的下标。
这里规定,下标为0的点为头结点head,下标为1的点为尾结点tail,最开始的状态如下(初始化内容)
在k结点右边插入一个元素
//在下标为k的点的右边插入x
void add(int k, int x){e[idx] = x;r[idx] = r[k];l[idx] = k;l[r[k]] = idx;//r[k]先调用,后修改r[k] = idx;}
删除下标为k的结点
void remove(int k){r[l[k]] = r[k];l[r[k]] = l[k];
}
c++代码
#include<iostream>
using namespace std;
const int N = 100005;
int head, tail, r[N], l[N], e[N], idx, m;
void init(){r[0] = 1;l[1] = 0;idx = 2; // 0 ,1已经使用过了
}
//在下标为k的点的右边插入x
void add(int k, int x){e[idx] = x;r[idx] = r[k];l[idx] = k;l[r[k]] = idx;//r[k]先调用,后修改r[k] = idx++;
}
//在k的左边插入一个数等价于在k的左边结点(L[k])后插入一个数//删除第k个点
void remove(int k){r[l[k]] = r[k];l[r[k]] = l[k];
}
int main(){cin >> m;init();while(m--){int k, x;string op;cin >> op;if(op == "L"){cin >> x;add(0, x);}else if(op == "R"){cin >> x;add(l[1], x);//tail结点的左侧}else if(op == "D"){cin >> k;remove(k + 1);}else if(op == "IL"){cin >> k >> x;add(l[k + 1], x);}else if(op == "IR"){cin >> k >> x;add(k + 1, x);}}// 将整个表进行遍历for(int i = r[0]; i != 1; i = r[i]){cout << e[i] << " ";}return 0;
}
828. 模拟栈
栈:后进先出
这里使用数组模拟栈
解题思路
用stk[N]
表示栈,用变量tt
表示栈顶
插入操作
stk[tt++] = x
弹出栈顶元素
tt --;
判断栈是否为空
if(tt > 0){not empty
}else{empty;
}
3302. 表达式求值
思路分析:
中缀表达式,使用中序遍历。
中缀表达式的树形结构如下图所示
中缀表达式这个比较抽象,拿样例进行模拟一下,如下图所示,从左往右,从下往上,先将子树算完,再去计算上一层。
那这个过程如何用代码实现呢?关键在于如何判断某棵子树被遍历完,当前运算符的优先级是低于前一个运算符的优先级,则可以将该子树的值先计算出来。例如,这里x
笔记+
运算优先级高,可以先计算a*b
,往上计算,如果运算符优先级相同,根据从左往右的计算准则,也是先算子树的内容。因此,如何判断某棵子树被遍历完-当前运算符的优先级小于等于上一个运算符的优先级。
c++代码
#include<iostream>
#include<algorithm>
#include<cstring>
#include<stack>
#include<unordered_map>
using namespace std;stack<int>num; // 存数字
stack<int>op;// 存运算符void eval(){ // 操作最后一个运算符auto b = num.top();num.pop();auto a = num.top();num.pop();auto c = op.top();op.pop();int x; // 定义一下答案if(c == '+'){x = a + b;}else if(c == '-'){x = a - b;}else if(c == '*'){x = a * b;}else if(c == '/'){x = a / b;}num.push(x);// 将结果存入栈中
}
int main(){unordered_map<char, int> pr{{'+', 1},{'-', 1},{'*',2},{'/', 2}};// 定义符号的优先级string str;cin >> str;for(int i = 0; i < str.size(); i ++){auto c = str[i];if(isdigit(c)){ //如果是数字int x = 0, j = i;while(j < str.size() && isdigit(str[j])){x = x * 10 + str[j ++] - '0';}i = j - 1;num.push(x);}else if(c == '('){op.push(c);}else if(c == ')'){ // 将栈里的运算符从右往左操作一遍,直到遇到左括号while(op.top() != '('){eval();// 用末尾的运算符操作末尾的两个数}op.pop();}else{ //如果是一般运算符while(op.size() && pr[op.top()] >= pr[c]){// 元素不空,并且栈顶元素的优先级大于当前元素的优先级eval();//操作一下栈顶元素}op.push(c);}}//最后将没有操作过的树全部操作一遍while(op.size()){eval();}//栈顶元素就是答案cout << num.top() << endl;return 0;
}
c++代码
看做一个模版,如果还包含其他运算符,再添加进去。
#include<iostream>
using namespace std;
const int N = 100005;
int stk[N], tt = 0;
void push_x(int x){stk[tt ++] = x;
}
void del(){tt --;
}
int isEmpty(){if(tt == 0){return 1;}else {return 0;}
}
int pop(){int k = tt - 1;return stk[k];
}
int main(){int m;cin >> m;while(m --){int x;string op;cin >> op;if(op == "push"){cin >> x;push_x(x);}else if(op == "pop"){del();}else if(op == "empty"){if(isEmpty()){cout << "YES" << endl;}else{cout << "NO" << endl;}}else if(op == "query"){cout << pop() << endl;}}return 0;
}
领接表
领接表是由多个单链表组成的,拿邻接表存储树和图放到第三章去讲。