数据结构大作业.doc

本文档描述的是一个基于数据结构的大学作业，目标是实现一个能够处理算术表达式求值的程序。这个程序运用了数据结构中的栈来处理操作数和运算符，以此来解析和计算输入的表达式。以下是关于这个作业的详细知识点： 1. **数据结构**：在这个任务中，主要使用了两种数据结构——顺序栈。顺序栈是一种特殊的线性表，仅允许在表的一端（称为栈顶）进行插入和删除操作，这种特性使得它非常适合处理具有后进先出（LIFO）性质的问题，如表达式求值。 2. **表达式求值**：算术表达式由操作数、运算符和界限符组成。在这个实验中，操作数被限制为正整数，运算符包括加、减、乘、除四种，而界限符则有左右括号和表达式起始和结束符号“#”。 3. **栈的实现**： - **操作数栈**：用于存储表达式中的操作数。当读取到非运算符字符时，将其压入操作数栈。 - **运算符栈**：用于存储运算符。根据运算符的优先级与当前栈顶运算符的关系进行操作，如将运算符压入栈或执行相应的计算。 4. **栈操作**： - **push_opnd()**：将操作数压入操作数栈。 - **pop_opnd()**：从操作数栈中弹出一个操作数。 - **push_optr()**：将运算符压入运算符栈。 - **pop_optr()**：从运算符栈中弹出一个运算符。 5. **优先级判断**：通过函数`relation()`比较运算符的优先级。如果当前运算符的优先级高于栈顶运算符，就将当前运算符压入栈；如果优先级相同，则弹出栈顶运算符并执行相应的计算。 6. **总体设计**：程序首先清空操作数栈，将表达式起始符“#”作为运算符栈的栈底元素。然后，依次读取表达式中的字符，根据字符类型决定是否压入操作数栈或运算符栈，或者进行计算，直到整个表达式求值完成。 7. **用户界面**：用户通过输入包含算术表达式的字符串，程序会输出计算结果。例如，输入"3+5#"或"(3+2)*(4+1)/2"。 8. **程序实现**：程序使用C语言编写，包含了一些基本的库函数，如<stdio.h>、<stdlib.h>、<dos.h>和<conio.h>。定义了两个栈（操作数栈和运算符栈），并实现了栈的入栈和出栈操作。主函数`main()`负责接收用户输入，进行表达式求值。 9. **学习体验**：作者在完成这个项目的过程中，加深了对堆栈应用的理解，也提高了程序设计能力。尽管遇到困难，但通过查阅资料和请教他人，最终成功解决问题，收获颇丰。 10. **附录**：包含了源代码，定义了堆栈大小、操作函数以及主程序的实现细节。 通过这个大作业，学生不仅掌握了数据结构中栈的应用，还锻炼了解决问题和编程的能力，同时对表达式求值的算法有了深入的理解。