LiaN

是一只废物捏

0%

【总结】数据结构（总结自《算法笔记》和《王道》）

发表于 更新于 分类于 本文字数： 3.2k 阅读时长 ≈ 3 分钟
  • 随便记记

栈

1
2
3
4
5
#include<stack>
stack<int>st;
st.push(i);//O(1)
st.top();//O(1) 取得栈顶元素
st.pop();//O(1) 弹出栈顶元素

队列

1
2
3
4
#include<queue>
queue<int>q;//以下时间复杂度都是O(1)
q.front(); q.back();
q.push();  q.pop();

中缀转后缀,求后缀表达式

题目链接

《算法笔记》P249

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include<iostream>
#include<cstdio>
#include<queue>
#include<map>
#include<stack>
#include<string>
using namespace std;
struct node{
	double num;
	char op;
	bool flag;
};
string str;
queue<node>q;//后缀表达式 
stack<node>s;//符号栈 
map<char,int>op;
//中缀转后缀 
void Change(){
	double num;
	node temp;
	for(int i=0;i<str.length();){
		if(str[i]>='0'&&str[i]<='9'){
			temp.flag=true;
			temp.num=str[i]-'0';
			i++;
			while(i<str.length()&&str[i]>='0'&&str[i]<='9'){
				temp.num = temp.num*10+(str[i]-'0');
				i++;
			}
			q.push(temp); //数字存入后缀表达式队列中
		}else{
			temp.flag=false;
			while(!s.empty()&&op[str[i]]<=op[s.top().op]){
				q.push(s.top());
				s.pop();
			}//如果优先级不大于栈顶符号,把栈顶符号弹出,压入到后缀表达式中
			temp.op=str[i];//直到优先级大于栈顶符号时,压入符号栈中
			s.push(temp);
			i++;
		}
	}
	while(!s.empty()){//符号栈剩余符号压入后缀表达式中
		q.push(s.top());
		s.pop();
	}
}
//计算后缀表达式 
double Cal(){
	double temp1,temp2;
	node temp;
	while(!q.empty()){
		auto t=q.front();
		q.pop();
		if(t.flag) s.push(t);
		else{
			temp.flag=true;
			temp2=s.top().num; s.pop();
			temp1=s.top().num; s.pop();
			if(t.op=='+') temp.num =temp1+temp2;
			else if(t.op=='-') temp.num=temp1-temp2;
			else if(t.op=='*') temp.num=temp1*temp2;
			else temp.num=temp1/temp2;
			s.push(temp);
		}
	}
	return s.top().num;
} 
int main(){
	op['+']=op['-']=1;
	op['/']=op['*']=2;
	while(getline(cin,str),str!="0"){
		for(string::iterator it=str.end();it!=str.begin();it--){
			if(*it==' ') str.erase(it);
		}
		while(!s.empty()) s.pop();
		Change();
		printf("%.2lf\n",Cal());
	}
}

括号匹配

题目链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<bits/stdc++.h>
using namespace std;
int main(){
	int n;
	cin>>n;
	while(n--){
		string str;
		cin>>str;
		stack<char>s;
		bool flag = true;
		for(int i=0;i<str.size();i++){
			if(str[i]=='['||str[i]=='('||str[i]=='{') s.push(str[i]);
			if(str[i]==']'){
				if(s.empty()||s.top()!='['){
					flag = false;break;
				}else s.pop();
			}
			if(str[i]==')'){
				if(s.empty()||s.top()!='('){
					flag = false;break;
				}else s.pop();
			}
			if(str[i]=='}'){
				if(s.empty()||s.top()!='{'){
					flag = false;break;
				}else s.pop();
			}
		}
		if(!flag||!s.empty()) cout<<"no"<<endl;
		else cout<<"yes"<<endl;
	}
}

链表

图的存储

图的邻接表转换为邻接矩阵存储

算法思想： 设图的顶点分别存储在数组v[n]中。首先初始化邻接矩阵。遍历邻接表，在依次遍历顶点v[i]的边链表时，修改邻接矩阵的第i行的元素值。若链表边结点的值为j，则置arcs[i][j]=1。无向、有向图均适用。

1
2
3
4
5
6
7
8
9
void Convert(ALGraph &G, int arcs[M][N]){
	for(int i = 0; i < n; i++){
        p = (G -> v[i]).firstarc;
        while(p != null){
            arcs[i][p -> data] = 1;
            p = p ->nextarc;
        }
    }
}