数据结构 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) {
//构造一个空的顺序栈SS.base=new SElemType[MAXSIZE]; //为顺序栈动态分配一个最大容量为MAXSIZE的数组空间if(!S.base)exit(OVERFLOW);//存储分配失败S.top=S.base; //top初始为base空栈S.stacksize=MAXSIZE; //stacksize置为栈的最大容量MAXSIZEreturn 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; //栈顶指针减一，将栈顶元素赋给ereturn 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) {
//构造一个空的链栈SS=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;//修改栈顶指针为preturn OK;
}//3.链栈的出栈
Status Pop(LinkStack &S, SElemType &e) {//删除S的栈顶元素，用e返回其值if(S==NULL) return ERROR;//栈空e=S->data;; //将栈顶元素赋给eLinkStack p=S;//用p临时保存栈顶元素空间，以备释放S=S->next;//修改栈顶指针delete p;return OK;
}// 4.取栈顶元素
Status Top(LinkStack S, SElemType &e) { // 通过引用返回栈顶元素// 返回S的栈顶元素，不修改栈顶指针if (S != NULL) {e = S->data; // 将栈顶元素赋值给ereturn 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;
}