中国地质大学 数据结构上机实习 2015

### 数据结构上机实习知识点概览 #### 题目一：大数阶乘 **问题背景：** 在计算机科学中，处理大数运算时，通常的整型数据类型（如int、long等）无法满足需求，因为这些类型的取值范围有限。例如，当计算一个较大的数（如20以上）的阶乘时，结果会远远超出标准整型变量所能表示的最大值。本实习项目旨在通过自定义的数据结构和算法来实现大数的阶乘计算。 **知识点详解：** 1. **大数表示与存储** - 由于常规整型数据类型无法存储非常大的数字，因此需要设计一种特殊的数据结构来存储这些大数。在提供的代码中，作者选择了一个整型数组来存储大数，每个数组元素最多存放三位数字。 - **示例代码片段**： ```cpp int b[60]; memset(b, 0, 60); ``` - 这里`b`数组被用于存储大数，每个数组元素代表大数中的某一位。初始化数组元素为0，确保没有意外的初始值干扰计算过程。 2. **大数加法与乘法** - 在进行大数阶乘计算时，核心部分涉及到了大数加法和乘法的操作。 - **大数加法**：对于两个大数相加，需要处理进位问题。示例代码中的`add`函数实现了这一功能，通过遍历两个大数的每一位，并处理进位，完成加法操作。 - **大数乘法**：大数的乘法则更加复杂。示例代码中的`mult`函数通过逐位相乘并累加的方式实现了大数的乘法。同样需要注意的是，当结果超过三位数时，需要进行进位处理。 3. **阶乘算法** - 阶乘算法的基本思路是依次将1到n的整数相乘。在实现过程中，使用了上述介绍的大数加法和乘法算法。 - 示例代码中的`main`函数展示了如何利用之前定义的函数来实现阶乘计算。 4. **输出格式** - 在处理大数的输出时，需要注意格式化输出，确保每位数之间有正确的分隔符。示例代码中的`OutPut`函数负责将大数以正确格式输出。 #### 题目二：表达式求值 **问题背景：** 表达式求值是计算机科学中的一个经典问题，特别是在编译器设计中。通过构建一个栈结构，可以高效地解析和计算表达式的值。此题要求设计一个程序，能够解析并计算给定的数学表达式。 **知识点详解：** 1. **栈的概念** - 栈是一种遵循先进后出（First In Last Out, FILO）原则的数据结构。在表达式求值的问题中，使用栈可以帮助我们处理操作数和运算符之间的关系。 - **示例代码片段**： ```cpp #include "LinkedStack.h" ``` - 这里引入了`LinkedStack.h`头文件，表明使用了链表实现的栈。 2. **优先级处理** - 在计算表达式时，不同运算符具有不同的优先级。示例代码中的`isp`和`icp`函数分别用于获取栈内和栈外运算符的优先级。 - **示例代码片段**： ```cpp int isp(char ch); int icp(char ch); ``` - 这些函数根据不同的运算符返回相应的优先级值，帮助判断何时应该执行运算。 3. **表达式解析** - 表达式求值的核心在于如何正确解析表达式，并按照运算符的优先级顺序执行运算。 - 一般情况下，可以通过先将中缀表达式转换成后缀表达式（逆波兰表示法），然后再计算后缀表达式的值来实现。这种方式避免了处理复杂的括号匹配问题。 这两个题目分别涵盖了大数运算中的阶乘计算以及表达式求值，涉及到的数据结构包括数组和栈，算法方面包括大数加法与乘法、表达式解析等。通过这些实践，学生不仅能够深入了解相关理论知识，还能够在实际编程中应用这些知识解决问题。