写在前面
数据结构的实现是多种多样的，在本篇实现多种数据结构的过程中会尽可能的使用动态内存的形式，避免使用宏定义的形式，宏定义的形式是很老旧的版本，在实际运用中很少使用，掌握动态运用内存是必备的技能
对于二叉树的遍历创建方法有多种多样，这里使用的是leetcode等平台力荐的递归形式，递归完成二叉树遍历是较为标准和简单的方式
如果对二叉树的遍历不熟悉，最好优先复习二叉树是如何进行递归遍历和创建的
assert函数仅仅是编写代码时便于调试所加，可以删除，不会造成影响
下载链接
数制转换
问题描述
将十进制数N和其他d进制数之间进行转换是计算机实现计算的基本问题，解决方案很多，其中最简单的方法是除d取余法。例如，（1348）10=（2504）8，其转化过程如下所示：
N N div 8 N mod 8 1348 168 4 168 21 0 21 2 5 2 0 2
从中可以看出，最先产生的余数4是转换结果的最低位，这正好符合栈的“后进先出”的特性。所以可以用顺序栈来模拟这个过程。
题目解析
很简单的题，写一个栈入余数即可
需要注意的是，超过十进制的数有字母的参与，因此可以提前写一个数组，然后把栈内元素当成下标，再用下标元素访问数组内元素，就可以达到输出数字和字母的效果
#include <stdio.h> #include <stdlib.h> #include <assert.h> #include <stdbool.h> //1. 将十进制数N和其他d进制数之间进行转换是计算机实现计算的基本问题，解决方案很多，其中最简单的方法是除d取余法。 // 例如，（1348）10 = （2504）8，其转化过程如下所示： //N N div 8 N mod 8 //1348 168 4 //168 21 0 //21 2 5 //2 0 2 //从中可以看出，最先产生的余数4是转换结果的最低位，这正好符合栈的“后进先出”的特性。所以可以用顺序栈来模拟这个过程。 typedef int STDataType; typedef struct Stack { STDataType* a; int capacity; int top; }Stack; void StackInit(Stack* pst) { pst->a = (STDataType*)malloc(sizeof(STDataType) * 4); if (pst->a == NULL) { perror("malloc fail"); return; } pst->capacity = 4; pst->top = 0; } STDataType StackTop(Stack* pst) { assert(pst); assert(pst->top); return pst->a[pst->top - 1]; } void StackPop(Stack* pst) { assert(pst); assert(pst->top); pst->top--; } void StackPush(Stack* pst, STDataType x) { assert(pst); if (pst->capacity = pst->top) { STDataType* tmp = NULL; int newcapacity = pst->capacity * 2; tmp = (STDataType*)realloc(pst->a, sizeof(STDataType) * newcapacity); if (tmp == NULL) { perror("realloc fail"); return; } pst->a = tmp; pst->capacity = newcapacity; } pst->a[pst->top] = x; pst->top++; } bool StackEmpty(Stack* pst) { if (pst->top == 0) return true; else return false; } //被除数 dividend //除数 divisor //商 result //余数 remainder void Calculate(Stack* pst, int dividend, int divisor) { int remainder; while (dividend) { remainder = dividend % divisor; StackPush(pst, remainder); dividend = dividend / divisor; } } void Print(Stack* pst, int dividend, int divisor) { char array[16] = { '0', '1','2','3','4','5','6','7','8','9','A','B','C','D','E','F' }; printf("%d(10)=", dividend); while (!StackEmpty(pst)) { printf("%c", array[StackTop(pst)]); StackPop(pst); } printf("(8)\n"); } int main() { int dividend = 1348; printf("输入十进制数->"); scanf("%d", ÷nd); int divisor = 8; printf("输入要改变的进制数->"); scanf("%d", &divisor); Stack st; StackInit(&st); Calculate(&st, dividend, divisor); Print(&st, dividend, divisor); return 0; }
表达式求值
题目描述
从键盘输入一个算术表达式并输出它的结果，算术表达式可包含加、减、乘、除、十进制整数和小括号，利用栈实现。
题目解析
在解决问题前要先明确前缀表达式，中缀表达式，后缀表达式的概念：
中缀表达式：
通常来说在日常中遇到最多的就是中缀表达式，例如：
( 2 + 3 ) × 4 - 5
前缀表达式：
前缀表达式又称波兰式，前缀表达式的运算符位于操作数之前：
例如：中缀表达式 ( 2 + 3 ) × 4 - 5，采用前缀表达式为：- × + 2 3 4 5
后缀表达式：
例如：中缀表达式 ( 2 + 3 ) × 4 - 5，采用后缀表达式为：2 3 4 5 + × -
在知晓了三个表达式的概念后再看题目，题目中的要求其实就是，给定一个中缀表达式，要求将它转换成一个后缀表达式，再利用栈的原理来解决，那么就需要完成两个工作，如何将中缀表达式转换成后缀表达式？如何将后缀表达式借助栈计算出具体的结果？
中缀表达式转换为后缀表达式
实现操作：
- 对于操作数来说：
直接进行输出即可
- 对于操作符来说
- 如果栈为空，则进行入栈的操作
- 与栈顶元素进行比较，如果优先级比栈顶的操作符的优先级高，则进行入栈操作
- 与栈顶元素进行比较，如果优先级比栈顶的操作符的优先级低，则进行出栈顶操作符操作
- 出栈所有的操作符
- 循环上面的步骤直到没有操作符
下面用一个例子来解释这个操作的原理
如何利用后缀表达式计算结果
- 操作数入栈
- 操作符，取栈顶的两个操作数运算，运算结果再入栈
对于带左右括号的情况又如何解决？可以转换为递归的子问题来处理，当遇到右括号的时候为出栈条件之后再进行上面的步骤即可
本题由于较复杂，使用STL较为方便，因此这里使用C++来处理
#include <bits/stdc++.h> using namespace std; int cal(int a, int b, char opera) { switch (opera) { case '+': return a + b; case '-': return a - b; case '*': return a * b; case '/': return a / b; default: throw invalid_argument("bad opera"); } } int calculate(string s) { string tmp; for (char i : s) { if (i != ' ') { tmp.push_back(i); } } s = std::move(tmp); stack<int> result; stack<char> operas; operas.push('+'); result.push(0); for (int i = 0; i < s.size();) { if (s[i] >= '0' && s[i] <= '9') { operas.push('+'); int val = 0; while (s[i] >= '0' && s[i] <= '9') { val = val * 10 + (s[i] - 48); i++; } result.push(val); } else if (s[i] == '(') { operas.push('+'); result.push(-1); i++; } else if (s[i] == ')') { int val = 0; while (result.top() != -1) { val = cal(val, result.top(), operas.top()); result.pop(); operas.pop(); } if (operas.top() == '*' || operas.top() == '/') { result.pop(); val = cal(result.top(), val, operas.top()); operas.pop(); } if (val >= 0) { result.top() = val; } else { result.top() = -val; if (operas.top() == '+') { operas.top() = '-'; } else operas.top() = '+'; } i++; } else { char opera = s[i]; i++; if (s[i] == '(') { result.push(-1); i++; operas.push(opera); } else { int val = 0; while (s[i] >= '0' && s[i] <= '9') { val = val * 10 + (s[i] - 48); i++; } if (opera == '*' || opera == '/') { result.top() = cal(result.top(), val, opera); } else { operas.push(opera); result.push(val); } } } } int val = 0; while (!result.empty()) { val = cal(val, result.top(), operas.top()); result.pop(); operas.pop(); } return val; } int main() { //string s = "(1+(4+5+2)-3)+(6+8)*2"; string s; cout << "输入中缀表达式，例如(1+(4+5+2)-3)+(6+8)*2" << endl; cin >> s; cout << calculate(s) << endl; return 0; }
回文判断
题目描述
假设称正读和反读都相同的字符序列为“回文”，例如，’abba’和’abcba’是回文，’abcde’和’ababab’则不是回文。请编写一个程序判别读入的一个以’@’为结束符的字符序列是否是“回文”。提示：由于依次输入的字符序列中不含特殊的分隔符，则在判别是否是“回文”时，一种比较合适的做法是，同时利用“栈”和“队列”两种结构。
题目解析
本题也很简单，创建队列和栈两个数据结构，分别取Top比较再Pop，放到while循环里即可
//3. 假设称正读和反读都相同的字符序列为“回文”，例如，’abba’和’abcba’是回文，’abcde’和’ababab’则不是回文。 //请编写一个程序判别读入的一个以’@’为结束符的字符序列是否是“回文”。 //提示：由于依次输入的字符序列中不含特殊的分隔符，则在判别是否是“回文”时，一种比较合适的做法是，同时利用“栈”和“队列”两种结构。\ #include <stdio.h> #include <stdlib.h> #include <assert.h> #include <stdbool.h> typedef char QueueDataType; typedef struct QNode { QueueDataType data; struct QNode* next; }QNode; typedef struct Queue { QNode* phead; QNode* ptail; }Queue; void QueueInit(Queue* pq) { pq->phead = NULL; pq->ptail = NULL; } QNode* BuynewQNode(QueueDataType x) { QNode* newnode = (QNode*)malloc(sizeof(QNode)); if (newnode == NULL) { perror("malloc fail"); return NULL; } newnode->data = x; newnode->next = NULL; return newnode; } void QueuePush(Queue* pq, QueueDataType x) { assert(pq); QNode* newnode = BuynewQNode(x); if (pq->phead == NULL) { pq->phead = pq->ptail = newnode; } else { pq->ptail->next = newnode; pq->ptail = newnode; } } void QueuePop(Queue* pq) { assert(pq); assert(pq->phead); pq->phead = pq->phead->next; } QueueDataType QueueTop(Queue* pq) { assert(pq); assert(pq->phead); return pq->phead->data; } bool QueueEmpty(Queue* pq) { assert(pq); if (pq->phead == NULL) { return true; } else { return false; } } typedef char STDataType; typedef struct Stack { STDataType* a; int capacity; int top; }Stack; void StackInit(Stack* pst) { pst->a = (STDataType*)malloc(sizeof(STDataType) * 4); if (pst->a == NULL) { perror("malloc fail"); return; } pst->capacity = 4; pst->top = 0; } STDataType StackTop(Stack* pst) { assert(pst); assert(pst->top); return pst->a[pst->top - 1]; } void StackPop(Stack* pst) { assert(pst); assert(pst->top); pst->top--; } void StackPush(Stack* pst, STDataType x) { assert(pst); if (pst->capacity = pst->top) { STDataType* tmp = NULL; int newcapacity = pst->capacity * 2; tmp = (STDataType*)realloc(pst->a, sizeof(STDataType) * newcapacity); if (tmp == NULL) { perror("realloc fail"); return; } pst->a = tmp; pst->capacity = newcapacity; } pst->a[pst->top] = x; pst->top++; } bool StackEmpty(Stack* pst) { if (pst->top == 0) return true; else return false; } void Input(Queue* pq, Stack* ps) { char ret; printf("输入回文字符，以@结尾->"); while (1) { scanf("%c", &ret); if (ret == '@') break; QueuePush(pq, ret); StackPush(ps, ret); } } void Judge(Queue* pq, Stack* ps) { while (!QueueEmpty(pq)) { char que = QueueTop(pq); QueuePop(pq); char st = StackTop(ps); StackPop(ps); if (que!=st) { printf("不是回文\n"); return; } } printf("是回文\n"); return; } int main() { Queue q; Stack s; QueueInit(&q); StackInit(&s); Input(&q, &s); Judge(&q, &s); return 0; }
二叉树的创建、遍历及其它基本操作的实现
问题描述
- 以二叉链表作存储结构创建如下二叉树：
- 输出二叉树的中序遍历序列和后序遍历序列，以验证所建二叉树的正确性；
- 按二叉树的层次输出所建二叉树各层的结点，要求同层的结点自左向右排列。（提示：用到两个队列P、Q。其中P存放当前层上的结点，Q存放下一层的结点。）
题目解析
本实验就是对二叉树的简单操作，熟悉二叉树即可
二叉树介绍链接：
注意：
创建二叉树的方法有很多种，标准的创建二叉树的方法是用递归调用进行创建，基本原理可以在上文链接寻找
#include <stdio.h> #include <stdlib.h> #include <assert.h> #include <string.h> #include <stdbool.h> typedef struct BinaryTreeNode* QDataType; typedef struct QNode { QDataType data; struct QNode* next; }QNode; typedef struct Queue
