姓名：Far_Rainbow
    学号： 202505000X
    专业： 软件工程
    年级：2020级

    实验名称：实验4 顺序栈的基本操作及应用

    实验内容：

    （1）实验目的
    通过该实验，让学生掌握栈的相关基本概念，认识栈是插入和删除集中在一端进行的线性结构，掌握栈的“先入后出”操作特点。栈在进行各类操作时，栈底指针固定不动，掌握栈空、栈满的判断条件。

    （2）实验内容
    用顺序存储结构，实现教材定义的栈的基本操作，提供数制转换功能，将输入的十进制整数转换成二进制、八进制或十六进制。

    （3）参考界面
    菜单中包括以下功能：
    1.初始化栈，2.销毁栈，3.清空栈，4.栈判空，5.求栈长度，6.获取栈顶元素，7.插入一个 元素，8.删除一个元素，9输出所有元素，10进制转换。

    要求：自定义的函数中不允许出现提示语和输出语句。

    （4）验收/测试用例
    通过菜单调用各个操作，测试点：

    • 没有初始化前进行其他操作，程序是否能控制住；
    • 初始化一个栈； 判栈空，屏幕显示栈为空； 3个数入栈， 2、4、6； 栈长度，屏幕输出3；
    • 取栈顶元素，再判栈空，然后再判栈长度。让学生知道取栈顶元素不改变栈中的内容，栈顶指针不发生改变；
    • 出栈，再判栈长度和输出栈中内容；（多次出栈，直到栈为空；再出栈，是否提示栈为空） 销毁栈，再做其他操作，判断程序是否能控制；
    • 数制转换，（允许用户输入想把十进制转换成几进制），然后灵活的转换成对应的进制。

    实验类型：验证性

    实验的重难点：入栈和出栈、进制转换（十六进制）

    实验环境：TDM-GCC 4.9.2 64-bit

    实验步骤及完成任务情况：

    一、设计思想

    1. 采用模板实现泛型编程，可创建任意数据类型的栈；
    2. 以顺序表为原型实现顺序栈，设立栈顶指针始终指向最后一个元素的下一个地址；
    3. 实现expend()函数，在栈即将溢出时为栈分配新的内存空间；
    4. 使用栈实现进制转换功能

    二、主要源代码

    1. #include <iostream>
    2. #include <string>
    3. #include <map>
    4. #define STACKSIZE 1000
    5. #define STACKINCREMENT 100
    6. using std::cin;
    7. using std::cout;
    8. using std::endl;
    10. template <typename T> class Stack {
    11. private:
    12.     T* base;
    13.     T* top;
    14.     int _length;
    15.     int _capacity;
    16.     void expand();
    18. public:
    19.     void init();
    20.     void destroy();
    21.     void clear();
    22.     Stack() : base(NULL), top(NULL) { }
    23.     ~Stack() {destroy(); }
    24.     bool isempty() const {return _length > 0 ? 0 : 1; }
    25.     bool exist() const {return _capacity > 0 ? 1 : 0; }
    26.     int getlength() const {return _length; }
    27.     T& getop() const {return * (top-1); }
    28.     void push(T const& e);
    29.     T pop() {-- _length; return * -- top; }
    30.     void traverse() const 
    31.     {for(T* ptr = top - 1; ptr >= base; -- ptr) cout<<*ptr<<' '; }
    32. };
    34. template <typename T> void Stack<T>::init()
    35. {
    36.     base = new T[STACKSIZE];
    37.     top = base;
    38.     _length = 0;
    39.     _capacity = STACKSIZE;
    40. }
    42. template <typename T> void Stack<T>::destroy()
    43. {
    44.     delete[] base;
    45.     base = top = NULL;
    46.     _length = 0;
    47.     _capacity = 0;
    48. }
    50. template <typename T> void Stack<T>::clear()
    51. {
    52.     top = base;
    53.     _length = 0;
    54. }
    56. template <typename T> void Stack<T>::expand()
    57. {
    58.     T* newbase = new T[_capacity+STACKINCREMENT];
    59.     for(int i = 0; i < _length; ++ i)    newbase[i] = base[i];
    60.     delete[] base;
    61.     base = newbase;
    62. }
    64. template <typename T> void Stack<T>::push(T const& e)
    65. {
    66.     if (top - base > _capacity)    expand();
    67.     * top ++ = e;
    68.     ++ _length;
    69. }
    71. void conversion(int a, long long int num)
    72. {
    73.     Stack<int> tran;
    74.     tran.init();
    75.     int tmp;
    76.     if (num == 0){
    77.         cout<<num;
    78.         return;
    79.     }
    80.     while(num){
    81.         tran.push(num % a);
    82.         num = num / a;
    83.     }
    84.     while(!tran.isempty()){
    85.         tmp = tran.pop();
    86.         switch(tmp){
    87.             case 10: cout<<'A';break;
    88.             case 11: cout<<'B';break;
    89.             case 12: cout<<'C';break;
    90.             case 13: cout<<'D';break;
    91.             case 14: cout<<'E';break;
    92.             case 15: cout<<'F';break;
    93.             default: cout<<tmp;
    94.         }
    95.     }
    96. }
    98. void conversionmenu()
    99. {
    100.     std::map<int, std::string> mp;
    101.     std::map<int, int> np;
    102.     mp[1] = "二进制"; np[1] = 2;
    103.     mp[2] = "八进制"; np[2] = 8;
    104.     mp[3] = "十六进制"; np[3] = 16;
    105.     int n;
    106.     long long int num;
    107.     char c = 'y';
    108.     cout<<"欢迎使用进制转换功能！\n";
    109.     cout<<"1 二进制     2 八进制     3 十六进制\n\n"; 
    110.     while(true){
    111.         cout<<"\n请选择你想要转换的进制：";
    112.         cin>>n;
    113.         if (n < 1 || n > 4){
    114.             cout<<"请正确输入您的选择！\n";
    115.             continue;
    116.         }
    117.         cout<<"您选择的是十进制转换成"<<mp[n]<<"[y/n]:";
    118.         cin>>c;
    119.         if (c == 'y') {
    120.             cout<<"请输入您想要转换的数：";
    121.             cin>>num;
    122.             cout<<"转换成"<<mp[n]<<"的数是："; 
    123.             conversion(np[n], num);
    124.             return;
    125.         }
    126.         else    continue;
    127.     }
    128. }
    130. int main()
    131. {
    132.     cout<<"\n   顺序栈的基本操作\n\n";
    133.     cout<<"1---初始化栈\n";
    134.     cout<<"2---销毁栈\n";
    135.     cout<<"3---清空栈\n";
    136.     cout<<"4---栈判空\n";
    137.     cout<<"5---求栈长度\n";
    138.     cout<<"6---获取栈顶元素\n";
    139.     cout<<"7---插入一个元素\n";
    140.     cout<<"8---删除一个元素\n";
    141.     cout<<"9---输出所有元素\n";
    142.     cout<<"10--进制转换\n";
    143.     cout<<"\n\t退出，输入一个负数！\n\n";
    144.     Stack<int> s;
    145.     int e;
    146.     while(true){
    147.         int myOption;
    148.         cout<<"\n请输入操作序号：";
    149.         cin>>myOption;
    150.         switch(myOption){
    151.             case 1:{
    152.                 if(s.exist()){
    153.                     cout<<"初始化失败，栈已存在\n";
    154.                     break;
    155.                 }
    156.                 s.init();
    157.                 cout<<"初始化成功!\n";
    158.                 break;
    159.             }
    160.             case 2:{
    161.                 if (!s.exist()){
    162.                     cout<<"销毁失败，栈不存在\n";
    163.                     break; 
    164.                 }
    165.                 s.destroy();
    166.                 cout<<"销毁成功！\n";
    167.                 break;
    168.             } 
    169.             case 3:{
    170.                 if (!s.exist()){
    171.                     cout<<"清空失败，栈不存在\n";
    172.                     break; 
    173.                 }
    174.                 if (s.isempty()) ; 
    175.                 else    s.clear();
    176.                 cout<<"清空成功！\n"; 
    177.                 break;
    178.             }
    179.             case 4:{
    180.                 if (!s.exist()){
    181.                     cout<<"判空失败，栈不存在\n";
    182.                     break; 
    183.                 }
    184.                 if (s.isempty())    cout<<"栈为空！\n";
    185.                 else    cout<<"栈非空！\n"; 
    186.                 break;
    187.             }
    188.             case 5:{
    189.                 if (!s.exist()){
    190.                     cout<<"请先创建栈！\n";
    191.                     break; 
    192.                 }
    193.                 cout<<"栈的长度是"<<s.getlength()<<endl; 
    194.                 break;
    195.             }
    196.             case 6:{
    197.                 if (!s.exist()){
    198.                     cout<<"获取失败，栈不存在\n";
    199.                     break; 
    200.                 }
    201.                 if (s.isempty()){
    202.                     cout<<"栈为空，无栈顶元素！\n";
    203.                     break;
    204.                 }
    205.                 cout<<"栈顶元素是"<<s.getop()<<endl; 
    206.                 break;
    207.             }
    208.             case 7:{
    209.                 if (!s.exist()){
    210.                     cout<<"插入失败，栈不存在！\n";
    211.                     break; 
    212.                 }
    213.                 cout<<"请输入待插入元素e\n"<<"  e为:"; 
    214.                 cin>>e;
    215.                 s.push(e);
    216.                 break;
    217.             }
    218.             case 8:{
    219.                 if (!s.exist()){
    220.                     cout<<"删除失败，栈不存在！\n";
    221.                     break; 
    222.                 }
    223.                 if (s.isempty()){
    224.                     cout<<"栈为空，删除失败！\n";
    225.                     break;
    226.                 }
    227.                 else {
    228.                     e = s.pop();
    229.                     cout<<"被删除的元素是："<<e<<endl;
    230.                 } 
    231.                 break;
    232.             }
    233.             case 9:{
    234.                 if (!s.exist()){
    235.                     cout<<"遍历并输出失败，栈不存在！\n";
    236.                     break; 
    237.                 }
    238.                 if (s.isempty()){
    239.                     cout<<"栈为空！\n";
    240.                     break;
    241.                 }
    242.                 cout<<"栈的所有元素是：";
    243.                 s.traverse();
    244.                 cout<<endl;
    245.                 break;
    246.             }
    247.             case 10:{
    248.                 conversionmenu();
    249.                 cout<<endl;
    250.                 break;
    251.             }
    252.         }
    253.         if(myOption > 10 || myOption == 0)    cout<<"\n请输入小于10的正整数\n\n";
    254.         if(myOption < 0){
    255.             cout<<"\n退出程序！\n";
    256.             break;
    257.         }
    258.     }
    259.     return 0;
    260. }

    实验结果：
    实验4 顺序栈的基本操作及应用 - 图1
    实验4 顺序栈的基本操作及应用 - 图2
    实验4 顺序栈的基本操作及应用 - 图3
    实验4 顺序栈的基本操作及应用 - 图4
    实验4 顺序栈的基本操作及应用 - 图5