数据结构 C/C++(实验二:栈)
（大家好，今天分享的是数据结构的相关知识，大家可以在评论区进行互动答疑哦~加油！💕）
目录
提要：实验题目
一、实验目的
二、实验内容及要求
三、算法思想
实验1
实验2
四、源程序及注释
实验1代码（顺序存储结构）
实验2代码（链式存储结构）
五、实验结果
实验1结果
实验2结果
提要：实验题目
1. 栈顺序存储结构下基本操作的实现
2. 栈链式存储结构下基本操作的实现
一、实验目的
1．掌握栈的顺序存储表示和链式存储表示。
2．掌握顺序栈和链栈的基本操作算法的实现。
3．了解栈的两种不同存储结构的特点，会灵活运用栈解决某些实际问题。
二、实验内容及要求
1. 栈的基本操作的实现（初始化、进栈、出栈、取栈顶元素、判断栈是否为空、遍历等），要求分别采用顺序和链式存储结构。
2. 写一个程序，将输入的十进制数据转换为八进制数据。在此基础上修改程序，实现十进制数据向N （2或8或16）进制的转换。
3. 算术表达式求值。以字符序列的形式从终端输入语法正确的、不含变量的整数表达式。利用教材中表3.1给出的算符优先关系，实现对算术四则混合运算表达式的求值。
【测试数据】
3*(7-1)；1+2+3+4；88-1*5；(20+2)*(6/2)；6+2*(3+6)。
注：前两个题目必做，第3题选做。
三、算法思想
实验1
顺序存储结构栈的基本操作算法
(1)初始化
算法：分配一个预定大小的数组作为栈的存储空间，并初始化栈顶指针为-1（表示空栈）。
(2)进栈（Push）
算法：检查栈是否已满，若未满，则将新元素添加到栈顶，并更新栈顶指针。
(3)出栈（Pop）
算法：检查栈是否为空，若不为空，则移除栈顶元素，并更新栈顶指针。
(4)取栈顶元素（Top）
算法：检查栈是否为空，若不为空，则返回栈顶元素的值但不删除它。
(5)判断栈是否为空（IsEmpty）
算法：检查栈顶指针是否为-1。
(6)遍历
算法：从栈底到栈顶依次访问栈中的每个元素。这通常通过循环或递归实现，但在顺序栈中，由于元素是连续存储的，所以可以直接通过索引访问。
(7)十进制数据转换为八进制数据的算法
（利用栈的后进先出特性）
将十进制数除以8，记录余数。
将商作为新的十进制数，重复步骤1，直到商为0。
将记录的余数按逆序排列，即为八进制数。
在实现过程中，可以使用栈来存储每次除法的余数，这样最后出栈的顺序就是逆序的余数，即八进制数。
(8)算术表达式求值的算法
（利用栈的后进先出特性和运算符优先级）
将算术表达式转换为逆波兰表达式（后缀表达式）。
使用两个栈，一个用于存储操作数，另一个用于存储运算符。
遍历逆波兰表达式，对于每个元素：
如果是操作数，则将其压入操作数栈。
如果是运算符，则从操作数栈中弹出两个操作数，根据运算符进行计算，并将结果压回操作数栈。
遍历结束后，操作数栈中应只剩下一个元素，即为表达式的值。
在实现过程中，需要注意运算符的优先级和括号的处理。这通常通过定义运算符的优先级和括号的特殊处理规则来实现。
实验2
对于链式存储结构栈的基本操作及其相关算法，由于其实现方式与顺序存储结构有所不同（使用链表而非数组来存储栈元素），但基本操作的逻辑和算法思想是相似的。主要区别在于链表需要动态分配和释放内存，以及通过指针来访问栈顶元素和下一个元素。
四、源程序及注释
实验1代码（顺序存储结构）
#include<iostream> //输入输出流头文件
#include<fstream> //文件操作头文件
#include<string> //字符串操作头文件
#include<iomanip> //输入输出操纵运算头文件
#include<stack> // 引入 STL stack 进行栈操作
#include<cctype> // 引入字符处理函数
using namespace std;//调用命名空间std中所有标识符
//预定义常量及预定义类型
#define OK 1
#define ERROR 0
#define OVERFLOW -2
#define MAXSIZE 100
typedef int Status; //Status 是函数返回值类型，其值是函数结果状态代码。
typedef char SElemType;
//表示部分：
typedef struct {
SElemType *base;
SElemType *top;
int stacksize;
} SqStack;
//实现部分：
//1.初始化
Status InitStack(SqStack &S) {
//构造一个空的顺序栈S
S.base=new SElemType[MAXSIZE]; //为顺序栈动态分配一个最大容量为MAXSIZE的数组空间
if(!S.base)
exit(OVERFLOW);//存储分配失败
S.top=S.base; //top初始为base空栈
S.stacksize=MAXSIZE; //stacksize置为栈的最大容量MAXSIZE
return OK;
}
//2.顺序栈的入栈
Status Push(SqStack &S, SElemType e) {
//插入元素e为新的栈顶元素
if(S.top-S.base==S.stacksize) return ERROR;//栈满
*S.top++=e; //将元素e压入栈顶，栈顶指针加一
return OK;
}
//3.顺序栈的出栈
Status Pop(SqStack &S, SElemType &e) {
//删除S的栈顶元素，用e返回其值
if(S.top==S.base) return ERROR;//栈空
e=*--S.top; //栈顶指针减一，将栈顶元素赋给e
return OK;
}
//4.取栈顶元素
Status Top(SqStack S,SElemType &e) {
//返回S的栈顶元素，不修改栈顶指针
if (S.top != S.base) { // 非空
e = *(S.top - 1); // 返回栈顶元素，栈顶指针不变
return OK;
}
return ERROR; // 栈空
}
//5.判空
Status StackEmpty(SqStack S) {
if(S.top==S.base) return OK;
else return ERROR;
}
//6.判满
Status FullEmpty(SqStack S) {
if(S.top-S.base==S.stacksize) return OK;
else return ERROR;
}
//7.遍历
void printStack(SqStack S) {
printf("栈内元素为：");
SElemType *p=S.base;
while(p!=S.top) {
printf("%c",*p);
p++;
}
printf("\n");
}
//8. 求长
Status StackLength(SqStack S) {
return S.top-S.base;
}
//9. 清空
Status ClearStack(SqStack &S) {
S.top=S.base;
return OK;
}
//10. 销毁
Status DestoryStack(SqStack &S) {
if(S.base) {
delete S.base;
S.stacksize=0;
S.top=S.base=NULL;
}
return OK;
}
//11.数制转换
void conversion(int N) {
SqStack S;
InitStack(S);
char e;
while(N) {
Push(S,N%8);
N=N/8;
}
while(!StackEmpty(S)) {
Pop(S,e);
printf("%d",e);
}
}
//12.括号匹配
Status Matching() {
SqStack S;
InitStack(S);
SElemType ch, x,e;
Status flag = 1;
printf("请输入需要匹配的括号(以#结束)：\n");
scanf("%c", &ch);
while (ch != '#' && flag) {
switch (ch) {
case '(':
case '[':
Push(S, ch);
break;
case ')':
if (!StackEmpty(S) && Top(S,e) == '(') {
Pop(S, x);
} else {
flag = 0;
}
break;
case ']':
if (!StackEmpty(S) && Top(S,e) == '[') {
Pop(S, x);
} else {
flag = 0;
}
break;
}
//ch = getche();
scanf("%c", &ch);
}
if (StackEmpty(S) && flag) {
return true;
} else {
return false;
}
}
// 13. 算术表达式求值
// 计算两个数的运算
int applyOp(int a, int b, char op) {
switch (op) {
case '+': return a + b;
case '-': return a - b;
case '*': return a * b;
case '/':
if (b == 0) {
cout << "Error: Division by zero!" << endl;
exit(ERROR);
}
return a / b;
}
return 0;
}
// 获取运算符优先级
int precedence(char op) {
if (op == '+' || op == '-') return 1;
if (op == '*' || op == '/') return 2;
return 0;
}
// 算术表达式求值
int evaluateExpression(const string &expression) {
stack<int> values; // 存储数字
stack<char> ops; // 存储运算符
for (int i = 0; i < expression.length(); i++) {
// 当前字符是空格，跳过
if (isspace(expression[i])) continue;
// 当前字符是数字
if (isdigit(expression[i])) {
int val = 0;
while (i < expression.length() && isdigit(expression[i])) {
val = (val * 10) + (expression[i] - '0');
i++;
}
values.push(val);
i--; // 调整i，避免跳过下一个字符
}
// 当前字符是运算符
else if (expression[i] == '+' || expression[i] == '-' ||
expression[i] == '*' || expression[i] == '/') {
while (!ops.empty() && precedence(ops.top()) >= precedence(expression[i])) {
int b = values.top(); values.pop();
int a = values.top(); values.pop();
char op = ops.top(); ops.pop();
values.push(applyOp(a, b, op));
}
ops.push(expression[i]);
}
}
// 处理剩余的运算符
while (!ops.empty()) {
int b = values.top(); values.pop();
int a = values.top(); values.pop();
char op = ops.top(); ops.pop();
values.push(applyOp(a, b, op));
}
return values.top();
}
void calculateExpression() {
string expression;
cout << "请输入一个算术表达式（不含变量，支持 + - * /）：";
cin.ignore(); // 清除输入缓冲区
getline(cin, expression); // 读取整行
int result = evaluateExpression(expression);
cout << "表达式的值为：" << result << endl;
}
void showMenu() {
cout << "****************************\n";
cout << "**** 1. 初始化 ****\n";
cout << "**** 2. 入栈 ****\n";
cout << "**** 3. 出栈 ****\n";
cout << "**** 4. 取栈顶元素 ****\n";
cout << "**** 5. 判空 ****\n";
cout << "**** 6. 判满 ****\n";
cout << "**** 7. 遍历 ****\n";
cout << "**** 8. 求长 ****\n";
cout << "**** 9. 清空 ****\n";
cout << "**** 10. 销毁 ****\n";
cout << "**** 11. 数制转换 ****\n";
cout << "**** 12. 括号匹配 ****\n";
cout << "**** 13. 表达式求值****\n";
cout << "**** 0. 退出 ****\n";
cout << "****************************\n";
}
int main() {
SqStack S;
char e,i;
int N,choose= -1;
showMenu();
while (choose != 0) {
cout << "Please select（0-13）:";
cin >> choose;
switch (choose) {
case 1://初始化
InitStack(S);
cout << "Init successfully：\n";
break;
case 2: //入栈
cout << "Please input the elem in English ：";
cin >> e;
Push(S,e);
break;
case 3://出栈
Pop(S,e);
cout << "出栈元素为"<<e<<endl;
break;
case 4: //取栈顶元素
Top(S,i);
cout << "栈顶元素为"<<i<<endl;
break;
case 5: //判空
cout << (StackEmpty(S) == OK ? "栈为空" : "栈不为空") << endl;
break;
case 6: //判满
cout << (FullEmpty(S) == OK ? "栈满" : "栈不满") << endl;
break;
case 7: //遍历
printStack(S);
break;
case 8: //求长
cout << "栈的长度: " << StackLength(S) << endl;
break;
case 9: //清空
ClearStack(S);
cout << "栈已清空" << endl;
break;
case 10: //销毁
DestoryStack(S);
cout << "栈已销毁" << endl;
break;
case 11: //数制转换
cout << "Please input the Number (10进制) ：";
cin >> N;
cout << "10进制数字转换为8进制后数字为：";
conversion(N);
cout << endl;
break;
case 12: //括号匹配
if (Matching() == OK) {
cout << "括号匹配成功！" << endl;
} else {
cout << "括号匹配失败！" << endl;
}
break;
case 13: // 算术表达式求值
calculateExpression();
break;
}
}
return 0;
}实验2代码（链式存储结构）
#include<iostream> //输入输出流头文件
#include<fstream> //文件操作头文件
#include<string> //字符串操作头文件
#include<iomanip> //输入输出操纵运算头文件
#include <stack>
using namespace std;//调用命名空间std中所有标识符
//预定义常量及预定义类型
#define OK 1
#define ERROR 0
#define OVERFLOW -2
#define MAXSIZE 100
typedef int Status; //Status 是函数返回值类型，其值是函数结果状态代码。
typedef char SElemType;
//表示部分：
typedef struct StackNode{
SElemType data;
struct StackNode *next;
} StackNode,*LinkStack;
//实现部分：
//1.初始化
Status InitStack(LinkStack &S) {
//构造一个空的链栈S
S=NULL;
return OK;
}
//2.链栈的入栈
Status Push(LinkStack &S, SElemType e) {
//插入元素e为新的栈顶元素
StackNode *p=new StackNode;
if(!p) exit(OVERFLOW);
p->data=e;
p->next=S;//将新节点插入栈顶
S=p;//修改栈顶指针为p
return OK;
}
//3.链栈的出栈
Status Pop(LinkStack &S, SElemType &e) {
//删除S的栈顶元素，用e返回其值
if(S==NULL) return ERROR;//栈空
e=S->data;; //将栈顶元素赋给e
LinkStack p=S;//用p临时保存栈顶元素空间，以备释放
S=S->next;//修改栈顶指针
delete p;
return OK;
}
// 4.取栈顶元素
Status Top(LinkStack S, SElemType &e) { // 通过引用返回栈顶元素
// 返回S的栈顶元素，不修改栈顶指针
if (S != NULL) {
e = S->data; // 将栈顶元素赋值给e
return OK;
}
return ERROR; // 栈空
}
//5.判空
Status StackEmpty(LinkStack S) {
if(S==NULL) return OK;
else return ERROR;
}
//6.遍历
void StackTraverse(LinkStack S) {
LinkStack p;//使指针p辅助访问栈内元素
p=S;
printf("栈内元素为：");
while(p!=NULL) {
printf("%c",p->data);
p=p->next;
}
printf("\n");
}
//7. 求长
Status StackLength(LinkStack S) {
int len=0;
while(S!=NULL){
len++;
S=S->next;
}
return len;
}
//8. 清空
Status ClearStack(LinkStack &S) {
StackNode *p;
while(S!=NULL){
p=S->next;
delete S;
S=p;
}
return OK;
}
//9. 销毁
Status DestroyStack(LinkStack &S) {
StackNode *p;
while (S) {
p = S;
S = S->next;
delete p;
}
S = NULL;
return OK;
}
//10.数制转换
void conversion(int N) {
LinkStack S;
InitStack(S);
char e;
while (N) {
Push(S, '0' + (N % 8)); // 将数字转换为字符
N = N / 8;
}
while (!StackEmpty(S)) {
Pop(S, e);
cout << e; // 输出转换的数字
}
cout << endl;
}
//11.括号匹配
Status Matching() {
LinkStack S;
InitStack(S);
SElemType ch, e;
Status flag = OK;
cout << "请输入需要匹配的括号(以#结束)：\n";
cin >> ch;
while (ch != '#' && flag == OK) {
switch (ch) {
case '(':
case '[':
Push(S, ch);
break;
case ')':
if (!StackEmpty(S) && Top(S, e) == OK && e == '(') {
Pop(S, e);
} else {
flag = ERROR;
}
break;
case ']':
if (!StackEmpty(S) && Top(S, e) == OK && e == '[') {
Pop(S, e);
} else {
flag = ERROR;
}
break;
}
cin >> ch;
}
return (StackEmpty(S) && flag == OK) ? OK : ERROR;
}
// 12.算术表达式求值
// 定义优先级
int precedence(char op) {
if (op == '+' || op == '-') return 1;
if (op == '*' || op == '/') return 2;
return 0;
}
// 进行简单的运算
int applyOp(int a, int b, char op) {
switch (op) {
case '+': return a + b;
case '-': return a - b;
case '*': return a * b;
case '/':
if (b != 0) return a / b;
else {
cout << "Error: Division by zero!" << endl;
exit(1);
}
}
return 0;
}
int evaluateExpression(const string &expr) {
stack<int> values; // 存储操作数
stack<char> ops; // 存储操作符
for (int i = 0; i < expr.length(); i++) {
// 当前字符是空格则跳过
if (isspace(expr[i])) continue;
// 当前字符是数字
if (isdigit(expr[i])) {
int val = 0;
while (i < expr.length() && isdigit(expr[i])) {
val = val * 10 + (expr[i] - '0');
i++;
}
values.push(val);
i--; // 因为外面的 for 循环还会自增
}
// 当前字符是操作符
else {
while (!ops.empty() && precedence(ops.top()) >= precedence(expr[i])) {
int val2 = values.top(); values.pop();
int val1 = values.top(); values.pop();
char op = ops.top(); ops.pop();
values.push(applyOp(val1, val2, op));
}
ops.push(expr[i]);
}
}
// 处理剩余操作符
while (!ops.empty()) {
int val2 = values.top(); values.pop();
int val1 = values.top(); values.pop();
char op = ops.top(); ops.pop();
values.push(applyOp(val1, val2, op));
}
return values.top();
}
void showMenu() {
cout << "****************************\n";
cout << "**** 1. 初始化 ****\n";
cout << "**** 2. 入栈 ****\n";
cout << "**** 3. 出栈 ****\n";
cout << "**** 4. 取栈顶元素 ****\n";
cout << "**** 5. 判空 ****\n";
cout << "**** 6. 遍历 ****\n";
cout << "**** 7. 求长 ****\n";
cout << "**** 8. 清空 ****\n";
cout << "**** 9. 销毁 ****\n";
cout << "**** 10. 数制转换 ****\n";
cout << "**** 11. 括号匹配 ****\n";
cout << "**** 12. 表达式求值****\n";
cout << "**** 0. 退出 ****\n";
cout << "****************************\n";
}
int main() {
LinkStack S;
string expression;
char e,i;
int N,choose= -1;
showMenu();
while (choose != 0) {
cout << "Please select（0-12）:";
cin >> choose;
switch (choose) {
case 1://初始化
InitStack(S);
cout << "Init successfully：\n";
break;
case 2: //入栈
cout << "Please input the elem：";
cin >> e;
Push(S,e);
break;
case 3://出栈
Pop(S,e);
cout << "出栈元素为"<<e<<endl;
break;
case 4: //取栈顶元素
if (Top(S, i) == OK) { // 检查返回值
cout << "栈顶元素为 " << i << endl;
} else {
cout << "栈为空，无法获取栈顶元素。" << endl;
}
break;
case 5: //判空
cout << (StackEmpty(S) == OK ? "栈为空" : "栈不为空") << endl;
break;
case 6: //遍历
StackTraverse(S);
break;
case 7: //求长
cout << "栈的长度: " << StackLength(S) << endl;
break;
case 8: //清空
ClearStack(S);
cout << "栈已清空" << endl;
break;
case 9: //销毁
DestroyStack(S);
cout << "栈已销毁" << endl;
break;
case 10: //数制转换
cout << "Please input the Number (10进制) ：";
cin >> N;
cout << "10进制数字转换为8进制后数字为：";
conversion(N);
cout << endl;
break;
case 11: //括号匹配
if (Matching() == OK) {
cout << "括号匹配成功！" << endl;
} else {
cout << "括号匹配失败！" << endl;
}
break;
case 12: // 表达式求值
cout << "请输入算术表达式（不含空格）: ";
cin >> expression;
cout << "表达式 " << expression << " 的值为: " << evaluateExpression(expression) << endl;
break;
}
}
return 0;
}
五、实验结果
实验1结果
实验2结果
（今日分享暂时到此为止啦！为不断努力的自己鼓鼓掌吧🥳。今日文案分享：以如常为喜，以如愿为安。）