1. 首页
  2. 文章中心
  3. 数据结构

数据结构入门系列——用栈解决实际问题（2）

107 阅读 0 评论
我是靠谱客的博主 飘逸心锁，这篇文章主要介绍数据结构入门系列——用栈解决实际问题（2），现在分享给大家，希望可以做个参考。

进制转换（栈）

复制代码
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
void DuiZhan(int num)
{
	SqStack st;
	InitStack(st); char x;
	char sixteen[] = { '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'A', 'B', 'C', 'D', 'E', 'F' };
	int j;
	cout << "要将num转为哪种进制" << endl;
	cin >> j;
	switch (j)
	{
	case 2:case 8:
		while (num)
		{
			push(st, sixteen[num%j]);
			num = num / j;
		}
		while (!StackEmpty(st))
		{
			pop(st, x);
			cout << x;
		}
		cout << endl;
		break;
	case 16:
		while (num)
		{
			push(st, sixteen[num % 16]);
			num = num / 16;
		}
		while (!StackEmpty(st))
		{
			pop(st, x);
			cout << x;
		}
		cout << endl;
		break;
	}
}

进制转换（递归）

复制代码
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
void Digui(int num)
{
	if (num == 0)
		return;
	else {
		Digui(num/16);
		if (num % 16 >= 10)
			switch (num % 16)
			{
			case 10:
				cout << "A";
				break;
			case 11:
				cout << "B";
				break;
			case 12:
				cout << "C";
				break;
			case 13:
				cout << "D";
				break;
			case 14:
				cout << "E";
				break;
			case 15:
				cout << "F";
				break;
			default:break;
			}
		else
			cout << num % 16;
	}
}

总代码：

复制代码
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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
//进制转换
#include <iostream>
using namespace std;
//五、分别用栈和递归来实现十进制转换为16进制。
#define maxsize 10
typedef struct
{
	char data[maxsize];
	int top;
}SqStack;
void InitStack(SqStack &st)
{
	st.top = -1;
}
void DestroyStack(SqStack st)
{}
int push(SqStack &st, char x)//进栈
{
	if (st.top == maxsize)
		return 0;
	else
	{
		st.top++;
		st.data[st.top] = x;
		return 1;
	}
}
int pop(SqStack &st, char &x)//出栈
{
	if (st.top == -1)
		return 0;
	else {
		x = st.data[st.top];
		st.top--;
		return 1;
	}
}
int StackEmpty(SqStack &st)//判断是否栈空 ，是：1；否：0.
{
	if (st.top == -1)
		return 1;
	else
		return 0;
}
int GetTop(SqStack &st, char &x)
{
	if (st.top == -1)
		return 0;
	else {
		x = st.data[st.top];
		return 1;
	}
}
void OutputStack(SqStack st)
{
	SqStack sts = st;
	while (sts.top != -1)
	{
		cout<< sts.data[sts.top] << " ";
		sts.top--;
	}
	cout << endl;
}
void DuiZhan(int num)
{
	SqStack st;
	InitStack(st); char x;
	char sixteen[] = { '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'A', 'B', 'C', 'D', 'E', 'F' };
	int j;
	cout << "要将num转为哪种进制" << endl;
	cin >> j;
	switch (j)
	{
	case 2:case 8:
		while (num)
		{
			push(st, sixteen[num%j]);
			num = num / j;
		}
		while (!StackEmpty(st))
		{
			pop(st, x);
			cout << x;
		}
		cout << endl;
		break;
	case 16:
		while (num)
		{
			push(st, sixteen[num % 16]);
			num = num / 16;
		}
		while (!StackEmpty(st))
		{
			pop(st, x);
			cout << x;
		}
		cout << endl;
		break;
	}
}

void Digui(int num)
{
	if (num == 0)
		return;
	else {
		Digui(num/16);
		if (num % 16 >= 10)
			switch (num % 16)
			{
			case 10:
				cout << "A";
				break;
			case 11:
				cout << "B";
				break;
			case 12:
				cout << "C";
				break;
			case 13:
				cout << "D";
				break;
			case 14:
				cout << "E";
				break;
			case 15:
				cout << "F";
				break;
			default:break;
			}
		else
			cout << num % 16;
	}
}
void main()
{
	int m;
	cout << "请输入num" << endl;
	cin >> m;
	DuiZhan(m);
	Digui(m);
}

后缀表达式

复制代码
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
int fuhaocal(char fuhao, int x, int y)
{
	switch (fuhao)
	{
	case'+':
		return x + y;
	case '-':
		return x - y;
	case '*':
		return x * y;
	case '/':
		return x / y;
	default:
		cout << "false" << endl;
		return 0;
	}

	}
int calculate(char *str, int *result)
{
	char ch;
	SqStack *st = new SqStack;
	InitStack(*st);
	int i = 0;
	int c,x,y;
	while (str[i] != '=')
	{
		ch = str[i];
		if (ch >= '0'&&ch <= '9')
		{
			c = ch - '0';
			if (push(*st, c) != 1)
			{
				cout << "超出界限" << endl;
				return 0;
			}
		}
		else if (ch == '+' || ch == '-' || ch == '*' || ch == '/')
		{
			pop(*st, x);
			pop(*st, y);
			int item = fuhaocal(ch,y, x);
			push(*st, item);
		}
		i++;
	}
	*result = st->data[st->top];
	return 0;
}

中缀表达式

复制代码
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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
#include<iostream>
#include<string>
#include"head.h"
using namespace std;
int priority(char a)
{
	int i = 1;
	switch (a)
	{
	case '#':
		i = 0;
		break;
	case '+':
	case '-':
		i = 1;
		break;
	case '*':
	case '/':
		i = 2;
		break;
	case '(':
		i = 3;
		break;
	default:
		break;
	}
	return i;
}
string caculate(char a, string a1, string a2)
{
	double re=0;
	double b1, b2;
	string result;
	b1 = atof(a1.c_str());
	b2 = atof(a2.c_str());
	switch (a)
	{
	case '+':
		re = b2 + b1;
		break;
	case '-':
		re = b2 - b1;
		break;
	case '*':
		re = b2 * b1;
		break;
	case '/':
		re = b2 / b1;
		break;
	default:
		break;
	}
	result = to_string(re);
	return result;
}
void main()
{
	stackNode *data,*symbol;
	initNode(&data);
	initNode(&symbol);
	string question;
	double result;
	cin >> question;
	question = '#' + question + '#';
	for (int i = 0; i < question.length(); i++)
	{
		if (isdigit(question[i]))
		{
			string d;
			d.push_back(question[i]);
			data = push(data, d);
		}
		else
		{
			if (judge(symbol))
			{
				string s;
				s.push_back(question[i]);
				symbol = push(symbol, s);
				continue;
			}
			if (question[i] == '(')
			{
				string s;
				s.push_back(question[i]);
				symbol = push(symbol, s);
				continue;
			}
			if (question[i] == ')')
			{
				while (getTop(symbol)[0] != '(')
				{
					string s, d1, d2;
					symbol = pop(symbol, s);
					data = pop(data, d1);
					data = pop(data, d2);
					d1 = caculate(s[0], d1, d2);
					data = push(data, d1);
				}
				string s1;
				symbol = pop(symbol, s1);
				continue;
			}
			else
			{
				if (getTop(symbol)[0] == '(')
				{
					string s;
					s.push_back(question[i]);
					symbol = push(symbol, s);
					continue;
				}
				int iThis, iBefore;
				iThis = priority(question[i]);
				iBefore = priority(getTop(symbol)[0]);
				if (iThis > iBefore)
				{
					string s;
					s.push_back(question[i]);
					symbol = push(symbol, s);
				}
				if (iThis <= iBefore)
				{
					if (question[i] == '#'&&getTop(symbol)[0] == '#')
						continue;
					while (getTop(symbol)[0] != '#'&& getTop(symbol)[0] != '(')
					{
						string s, d1,d2;
						symbol = pop(symbol, s);
						data = pop(data, d1);
						data = pop(data, d2);
						d1 = caculate(s[0],d1,d2);
						data = push(data, d1);
					}
					string s;
					s.push_back(question[i]);
					symbol = push(symbol, s);
				}
			}
		}
	}
	cout << getTop(data) << endl;
}

附：递归算法

斐波那契数列

该问题可以用递归形式来表示，即有递归公式：
fibo=fibonacci(n-1)+fibonacci(n-2)
递归结束条件为：当n=1或n=2，fibo=1
可以构建一个递归子函数int fibonacci(int n)来实现求第n项的值，主函数中调用该递归子函数。

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
int fibos(int n)
{
	int fibo;
	if (n == 1 || n == 2)
	{
		fibo=1;
	}
	else {
		fibo = fibos(n - 1) + fibos(n - 2);//递归调用
	}
	return fibo;
}

当函数是void

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
void shunxu(int m)
{
	if (m == 0)
	{
		return;
	}
	else {
		mix(m - 1);
		cout << m << " ";
	}
}

在这里插入图片描述
由于递归是内存自动建立栈，所以可以这样理解。递归函数先找到出口，从出口反向运算到初始条件。这就与栈表现相似。

最后

以上就是飘逸心锁最近收集整理的关于数据结构入门系列——用栈解决实际问题（2）的全部内容，更多相关数据结构入门系列——用栈解决实际问题（2）内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
点赞(71)

相关文章

数据结构入门系列——用栈解决实际问题（1）
数据结构入门系列——用栈解决实际问题（1）
其实MyBatis的插件机制可以帮我们解决工作很多问题，建议收藏1.2 配置拦截器1.3 运行程序2. 插件实现原理2.1 初始化操作2.2.2 StatementHandler2.2.3 ParameterHandler2.2.4 ResultSetHandler2.3 执行流程3. PageHelper分析3.1 PageHelper的应用4.应用场景分析
其实MyBatis的插件机制可以帮我们解决工作很多问题，建议收藏1.2 配置拦截器1.3 运行程序2. 插件实现原理2.1 初始化操作2.2.2 StatementHandler2.2.3 ParameterHandler2.2.4 ResultSetHandler2.3 执行流程3. PageHelper分析3.1 PageHelper的应用4.应用场景分析
学习Mybatis之02--＞配置文件开发之代理开发模式一、代理开发以及案例二、动态SQL语句三、SQL片段抽取四、核心配置文件深入五、plugins标签
学习Mybatis之02--＞配置文件开发之代理开发模式一、代理开发以及案例二、动态SQL语句三、SQL片段抽取四、核心配置文件深入五、plugins标签
MyBatis--------应用案例详解
MyBatis--------应用案例详解
数据结构入门系列——用栈解决实际问题（2）
数据结构入门系列——用栈解决实际问题（2）
Mybatis[4] - 配置文件 - plugins
Mybatis[4] - 配置文件 - plugins
MyBatis框架总结二---全局配置全局配置文件
MyBatis框架总结二---全局配置全局配置文件
MyBatis 实际使用案例-总结
MyBatis 实际使用案例-总结

评论列表共有 0 条评论

立即
投稿
返回
顶部