一、实验背景与目的
在计算机科学中，数据结构是程序设计的重要基础。栈作为一种典型的线性数据结构，具有后进先出（LIFO, Last In First Out）的特点，在实际问题求解中有着广泛的应用场景。本次实验旨在通过使用栈实现不同进制之间的数值转换，加深对栈操作原理的理解，并掌握其在算法设计中的具体应用。
二、实验原理
1. 进制转换的基本思想
进制转换的核心在于将一个数从一种进制表示形式转换为另一种进制表示形式。例如，将十进制数转换为二进制数时，可以通过不断除以目标基数并记录余数的方式完成。这种方法本质上是一种递归或迭代的过程。
2. 栈的应用
栈可以用来存储每次计算得到的余数。在进制转换过程中，由于需要从低位到高位依次输出结果，而栈的特性正好符合这一需求——后入栈的数据会先被取出，从而实现按顺序输出。
3. 算法步骤
- 输入待转换的整数和目标进制。
- 使用循环对输入值进行模运算，将每次的结果压入栈中。
- 当输入值变为零时，停止循环。
- 依次弹出栈中的元素，拼接成最终的转换结果。
三、实验环境与工具
- 开发语言：C/C++
- 编译器：Dev-C++ 或其他支持C/C++的集成开发环境
- 测试数据：随机生成的十进制整数及目标进制范围内的多种组合
四、实验代码实现
以下是基于栈实现进制转换的核心代码片段：
```cpp
include
include
using namespace std;
void convertToBase(int num, int base) {
stack
if (base < 2 || base > 36) { // 检查进制合法性
cout << "Invalid base!" << endl;
return;
}
while (num > 0) {
int remainder = num % base; // 计算余数
s.push(remainder);// 将余数压入栈中
num /= base;// 更新输入值
}
// 输出结果
string digits = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"; // 支持扩展到36进制
cout << "Converted number: ";
while (!s.empty()) {
cout << digits[s.top()]; // 根据栈顶元素获取对应字符
s.pop();
}
cout << endl;
}
int main() {
int decimalNumber, targetBase;
cout << "Enter the decimal number: ";
cin >> decimalNumber;
cout << "Enter the target base (2-36): ";
cin >> targetBase;
convertToBase(decimalNumber, targetBase);
return 0;
}
```
五、实验结果分析
1. 功能验证
实验中分别测试了多个十进制数向二进制、八进制、十六进制等常见进制的转换，均得到了正确的结果。例如：
- 输入 `10` 和目标进制 `2`，输出为 `1010`。
- 输入 `255` 和目标进制 `16`，输出为 `FF`。
2. 性能评估
算法的时间复杂度为 \(O(n)\)，其中 \(n\) 是输入数字的位数；空间复杂度也为 \(O(n)\)，主要由栈的空间占用决定。因此该方法适用于中小规模的进制转换任务。
3. 边界条件处理
对于非法进制（如小于2或大于36的情况），程序能够正确提示错误信息，体现了良好的鲁棒性。
六、实验总结
通过本次实验，我们深入理解了栈作为数据结构在解决实际问题中的重要作用。栈不仅简化了进制转换的实现过程，还展示了其在递归逻辑模拟方面的强大能力。此外，通过对代码细节的优化（如支持更大的进制范围），进一步提升了程序的通用性和实用性。
未来可以尝试将此方法推广至更大规模的问题求解中，或者结合其他数据结构（如队列、链表等）进行综合应用研究。
---
以上便是本次实验的全部内容，希望读者能够从中受益！
