devbox
秋刀鱼在做梦
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

数据结构-栈的应用_栈是基础的数据结构,元素操作遵循后进先出的原理。本关卡基于数组存储实现了栈的

作者：秋刀鱼在做梦 | 2024-07-23 08:28:49

赞

踩

栈是基础的数据结构,元素操作遵循后进先出的原理。本关卡基于数组存储实现了栈的

第1关：利用栈实现整数的十进制转八进制

本关必读

栈是基础的数据结构，元素操作遵循后进先出的原理。本关卡基于数组存储实现了栈的基本操作。

 

该方案将栈存储在一片连续空间里，并通过data、top和max三个属性元素。组织成为一个结构：

  • data: 给出栈存储空间的起始地址
  • max: 指明栈存储空间最多可存储的数据元素个数
  • top: 栈顶元素所处数组位置 为了讨论简化，我们假设每个数据元素是一个整数:
    1. typedef int T; // 数据元素的数据类型
    该栈的结构定义如下：
    1. struct Stack{
    2. T* data; // 数据元素存储空间的开始地址
    3. int top; // 栈顶元素所处数组位置
    4. int max; // 栈存储空间最多可存储的数据元素个数
    5. };
    只要创建一个Stack指针对象，就可对栈表进行操作。

对数据元素进行操作处理是一个数据结构的重要组成部分。栈涉及的主要操作如下：

  • 创建栈：创建一个最多可存储max个数据元素的顺序存储的栈，初始状态设置为top=-1。该操作函数具体定义如下，其返回值为Stack指针： Stack* Stack_Create(int max)
  • 释放栈存储空间：释放stk->data所指向的用于存储栈数据元素的存储空间。该操作函数具体定义如下： void Stack_Free(Stack* stk)
  • 置空栈：将当前栈变为一个空栈，实现方法是将stk->top设置为-1。该操作函数具体定义如下： void Stack_MakeEmpty(Stack* stk)
  • 判断栈是否为空：若当前栈是空栈，则返回true,否则返回false。该操作函数具体定义如下： bool Stack_IsEmpty(Stack* stk)
  • 判断栈空间是否为满：若栈顶达到最大长度，则返回true,否则返回false。该操作函数具体定义如下： bool Stack_IsFull(Stack* stk)
  • 返回栈顶元素：返回栈顶元素stk->data[stk->top]。该操作函数具体定义如下： T Stack_Top(Stack* stk)
  • 将元素进栈： 将元素e压入栈顶。若栈满压入失败，返回异常，否则返回栈顶元素。该操作函数具体定义如下 T Stack_Push(Stack* stk, T e)
  • 将元素出栈： 将栈顶元素出栈。若栈空出栈失败，返回异常，否则返回栈顶元素。该操作函数具体定义如下 T Stack_Pop(Stack* stk)

任务描述

本关任务：基于栈stack数据结构解决整数十进制转八进制的问题。

相关知识

为了完成本关任务，你需要掌握：1.如何创建一个栈，2.入栈、出栈操作，3.进制转换。

创建栈

本例已基于数组存储结构实现了栈的创建，通过调用Stack* Stack_Create(int max)创建一个栈实例。

  1. Stack *stk = Stack_Create(32);//创建一个栈实例

入栈和出栈操作

示例如下：

  1. T e = 2018;
  2. Stack_Push(stk, e);//入栈
  3. e = Stack_Pop(stk);//出栈

进制转换

除K取余法，例如十进制数10转二进制：

上图可得：K=2，1010​=10102​ 即：10=1×23+0×22+1×21+0×20

编程要求

本关的编程任务是补全右侧代码片段Decimal_Conversion_Octal中Begin至End中间的代码，具体要求如下：

  • 在Decimal_Conversion_Octal中，利用栈stack的基本操作实现整数的十进制转八进制，并输出八进制结果，末尾换行。

测试说明

平台将自动编译补全后的代码，并生成若干组测试数据，接着根据程序的输出判断程序是否正确。

以下是平台的测试样例：

样例一： 测试输入：71 预期输出：107

样例二： 测试输入：8 预期输出：10

开始你的任务吧，祝你成功！

  1. //
  2. //  stack_.cpp
  3. //  Stack
  4. //
  5. //  Created by ljpc on 2018/4/17.
  6. //  Copyright © 2018年 ljpc. All rights reserved.
  7. //
  8.  
  9. #include "stack_.h"
  10.  
  11. // 栈操作实现文件
  12. //
  13.  
  14.  
  15. Stack* Stack_Create(int maxlen)
  16. // 创建栈
  17. {
  18.     Stack* stk = (Stack*)malloc(sizeof(Stack));
  19.     stk->data = (T*)malloc(sizeof(T)*maxlen);
  20.     stk->max = maxlen;
  21.     stk->top = -1;
  22.     return stk;
  23. }
  24.  
  25. void Stack_Free(Stack* stk)
  26. // 释放栈
  27. {
  28.     free(stk->data);
  29.     free(stk);
  30. }
  31.  
  32. void Stack_MakeEmpty(Stack* stk)
  33. // 置为空栈
  34. {
  35.     stk->top = -1;
  36. }
  37.  
  38. bool Stack_IsEmpty(Stack* stk)
  39. // 判断栈是否空
  40. {
  41.     return -1 == stk->top;
  42. }
  43.  
  44. bool Stack_IsFull(Stack* stk)
  45. // 判断栈是否满
  46. {
  47.     return stk->top == stk->max-1;
  48. }
  49.  
  50. T Stack_Top(Stack* stk)
  51. // 获取当前栈顶元素
  52. {
  53.     return stk->data[stk->top];
  54. }
  55.  
  56. T Stack_Push(Stack* stk, T e)
  57. // 将元素e压入栈顶
  58. // 返回栈顶点元素
  59. {
  60.     if(Stack_IsFull(stk)) {
  61.         printf("Stack_IsFull(): stack full error when push element to the stack!\n");
  62.         Stack_Free(stk);
  63.         exit(0);
  64.     }
  65.     else{
  66.         stk->top += 1;
  67.         stk->data[stk->top] = e;
  68.         return Stack_Top(stk);
  69.     }
  70. }
  71.  
  72. T Stack_Pop(Stack* stk)
  73. // 将栈顶元素出栈
  74. // 返回栈顶元素
  75. {
  76.     if(Stack_IsEmpty(stk)) {
  77.         printf("Stack_IsEmpty(): stack empty error when pop element of the stack top!\n");
  78.         Stack_Free(stk);
  79.         exit(0);
  80.     }
  81.     else{
  82.         T topE = Stack_Top(stk);
  83.         stk->top -= 1;
  84.         return topE;
  85.     }
  86. }
  87.  
  88. void Stack_Print(Stack* stk)
  89. // 打印栈顶到栈低的元素
  90. {
  91.     if (Stack_IsEmpty(stk)) {
  92.         printf("The stack is empty.\n");
  93.         return;
  94.     }
  95.     
  96.     //printf("The stack contains: ");
  97.     for (int i=stk->top; i>=0; i--) {
  98.         printf("%d", stk->data[i]);
  99.     }
  100.     printf("\n");
  101.     
  102. }
  103.  
  104. void Decimal_Conversion_Octal(T e)
  105. //  利用stack栈实现整数的十进制转八进制
  106. //  输入参数：十进制整数 e
  107. //  打印e的八进制结果，末尾换行
  108. {
  109.     // 请在这里补充代码，完成本关任务
  110.     /********** Begin *********/
  111.     Stack *stk = Stack_Create(100);
  112.     int x;
  113.     int i=0;
  114.     while(e>=8){
  115.         x=e%8;
  116.         i++;
  117.         Stack_Push(stk,x);
  118.         e=e/8;
  119.     }
  120.     Stack_Push(stk,e);
  121.     for(int j=0;j<=i;j++){
  122.         int a = Stack_Pop(stk);
  123.         printf("%d",a);
  124.     }
  125.     free(stk);
  126.     printf("\n");
  127.     
  128.     /********** End **********/
  129. }

第2关：利用栈判断字符串括号是否匹配

任务描述

本关任务：基于栈stack数据结构判断字符串中的括号是否匹配，字符串中仅包含如下字符：( ) [ ] { }。

相关知识

为了完成本关任务，你需要掌握：1.如何创建一个栈，2.入栈、出栈操作。

  • 创建栈、入栈和出栈操作请参考第1关。

编程要求

本关的编程任务是补全右侧代码片段Bracket_Match中Begin至End中间的代码，具体要求如下：

  • 在Bracket_Match中，利用栈stack判断括号是否匹配， 若匹配输出YES，否则输出NO，末尾换行。

测试说明

平台将自动编译补全后的代码，并生成若干组测试数据，接着根据程序的输出判断程序是否正确。

以下是平台的测试样例：

样例一： 测试输入： 6 {[()]} 预期输出： YES

样例二： 测试输入： 4 [(]) 预期输出： NO

开始你的任务吧，祝你成功！

  1. //
  2. //  stack_.cpp
  3. //  Bracket_Match
  4. //
  5. //  Created by ljpc on 2018/4/18.
  6. //  Copyright © 2018年 ljpc. All rights reserved.
  7. //
  8.  
  9. #include "stack_.h"
  10.  
  11. // 栈表操作实现文件
  12. //
  13.  
  14.  
  15. Stack* Stack_Create(int maxlen)
  16. // 创建栈
  17. {
  18.     Stack* stk = (Stack*)malloc(sizeof(Stack));
  19.     stk->data = (T*)malloc(sizeof(T)*maxlen);
  20.     stk->max = maxlen;
  21.     stk->top = -1;
  22.     return stk;
  23. }
  24.  
  25. void Stack_Free(Stack* stk)
  26. // 释放栈
  27. {
  28.     free(stk->data);
  29.     free(stk);
  30. }
  31.  
  32. void Stack_MakeEmpty(Stack* stk)
  33. // 置为空栈
  34. {
  35.     stk->top = -1;
  36. }
  37.  
  38. bool Stack_IsEmpty(Stack* stk)
  39. // 判断栈是否空
  40. {
  41.     return -1 == stk->top;
  42. }
  43.  
  44. bool Stack_IsFull(Stack* stk)
  45. // 判断栈是否满
  46. {
  47.     return stk->top == stk->max-1;
  48. }
  49.  
  50. T Stack_Top(Stack* stk)
  51. // 获取当前栈顶元素
  52. {
  53.     return stk->data[stk->top];
  54. }
  55.  
  56. T Stack_Push(Stack* stk, T e)
  57. // 将元素e压入栈顶
  58. // 返回栈顶点元素
  59. {
  60.     if(Stack_IsFull(stk)) {
  61.         printf("Stack_IsFull(): stack full error when push element to the stack!\n");
  62.         Stack_Free(stk);
  63.         exit(0);
  64.     }
  65.     else{
  66.         stk->top += 1;
  67.         stk->data[stk->top] = e;
  68.         return Stack_Top(stk);
  69.     }
  70. }
  71.  
  72. T Stack_Pop(Stack* stk)
  73. // 将栈顶元素出栈
  74. // 返回栈顶元素
  75. {
  76.     if(Stack_IsEmpty(stk)) {
  77.         printf("Stack_IsEmpty(): stack empty error when pop element of the stack top!\n");
  78.         Stack_Free(stk);
  79.         exit(0);
  80.     }
  81.     else{
  82.         T topE = Stack_Top(stk);
  83.         stk->top -= 1;
  84.         return topE;
  85.     }
  86. }
  87.  
  88. void Stack_Print(Stack* stk)
  89. // 打印栈顶到栈低的元素
  90. {
  91.     if (Stack_IsEmpty(stk)) {
  92.         printf("The stack is empty.\n");
  93.         return;
  94.     }
  95.     
  96.     //printf("The stack contains: ");
  97.     for (int i=stk->top; i>=0; i--) {
  98.         printf("%d", stk->data[i]);
  99.     }
  100.     printf("\n");
  101.     
  102. }
  103.  
  104. void Bracket_Match(T* str, int len)
  105. //  利用stack栈判断括号是否匹配
  106. //  输入参数：字符串序列，字符串长度
  107. //  若匹配输出YES，否则输出NO，末尾换行
  108. {
  109.     // 请在这里补充代码，完成本关任务
  110.     /********** Begin *********/
  111.     Stack *s = Stack_Create(200);
  112.     for (int i=0; i<len; i++) {
  113.         if(str[i]=='(' || str[i]=='[' || str[i]=='{'){
  114.             Stack_Push(s, str[i]);
  115.         }
  116.         else{
  117.             if(Stack_Top(s)=='(' && str[i]==')'){
  118.                 Stack_Pop(s);
  119.             }
  120.             else 
  121.             if(Stack_Top(s)=='[' && str[i]==']')
  122.             {
  123.                 Stack_Pop(s);
  124.             }
  125.             else 
  126.             if(Stack_Top(s)=='{' && str[i]=='}')
  127.             {
  128.                 Stack_Pop(s);
  129.             }
  130.             else{
  131.                 printf("NO\n");
  132.                 return;
  133.             }
  134.         }
  135.     }
  136.     if(Stack_IsEmpty(s)){
  137.         printf("YES\n");
  138.     }
  139.     else{
  140.         printf("NO\n");
  141.     }
  142.     /********** End **********/
  143. }
  144.

第3关：利用栈判断字符串是否为回文串

任务描述

本关任务：基于栈stack数据结构判断字符串是否为“回文串”。

相关知识

为了完成本关任务，你需要掌握：1.如何创建一个栈，2.入栈、出栈操作，3.“回文串”概念。

  • 创建栈、入栈和出栈操作请参考第1关

回文串

简单来说，“回文串”是一个正读和反读都一样的字符串： noon是回文串 moon不是回文串

编程要求

本关的编程任务是补全右侧代码片段Palindrome中Begin至End中间的代码，具体要求如下：

  • 在Palindrome中，利用栈stack判断字符串是否为回文串， 若是回文串输出YES，否则输出NO，末尾换行。

测试说明

平台将自动编译补全后的代码，并生成若干组测试数据，接着根据程序的输出判断程序是否正确。

以下是平台的测试样例：

样例一： 测试输入： 4 1221 预期输出： YES

样例二： 测试输入： 7 abababa 预期输出： YES

开始你的任务吧，祝你成功！

  1.  //
  2. //  stack_.cpp
  3. //  Palindrome
  4. //
  5. //  Created by ljpc on 2018/4/18.
  6. //  Copyright © 2018年 ljpc. All rights reserved.
  7. //
  8. #include "stack_.h"
  9. // 栈表操作实现文件
  10. //
  11. Stack* Stack_Create(int maxlen)
  12. // 创建栈
  13. {
  14.     Stack* stk = (Stack*)malloc(sizeof(Stack));
  15.     stk->data = (T*)malloc(sizeof(T)*maxlen);
  16.     stk->max = maxlen;
  17.     stk->top = -1;
  18.     return stk;
  19. }
  20. void Stack_Free(Stack* stk)
  21. // 释放栈
  22. {
  23.     free(stk->data);
  24.     free(stk);
  25. }
  26. void Stack_MakeEmpty(Stack* stk)
  27. // 置为空栈
  28. {
  29.     stk->top = -1;
  30. }
  31. bool Stack_IsEmpty(Stack* stk)
  32. // 判断栈是否空
  33. {
  34.     return -1 == stk->top;
  35. }
  36. bool Stack_IsFull(Stack* stk)
  37. // 判断栈是否满
  38. {
  39.     return stk->top == stk->max-1;
  40. }
  41. T Stack_Top(Stack* stk)
  42. // 获取当前栈顶元素
  43. {
  44.     return stk->data[stk->top];
  45. }
  46. T Stack_Push(Stack* stk, T e)
  47. // 将元素e压入栈顶
  48. // 返回栈顶点元素
  49. {
  50.     if(Stack_IsFull(stk)) {
  51.         printf("Stack_IsFull(): stack full error when push element to the stack!\n");
  52.         Stack_Free(stk);
  53.         exit(0);
  54.     }
  55.     else{
  56.         stk->top += 1;
  57.         stk->data[stk->top] = e;
  58.         return Stack_Top(stk);
  59.     }
  60. }
  61. T Stack_Pop(Stack* stk)
  62. // 将栈顶元素出栈
  63. // 返回栈顶元素
  64. {
  65.     if(Stack_IsEmpty(stk)) {
  66.         printf("Stack_IsEmpty(): stack empty error when pop element of the stack top!\n");
  67.         Stack_Free(stk);
  68.         exit(0);
  69.     }
  70.     else{
  71.         T topE = Stack_Top(stk);
  72.         stk->top -= 1;
  73.         return topE;
  74.     }
  75. }
  76. void Stack_Print(Stack* stk)
  77. // 打印栈顶到栈低的元素
  78. {
  79.     if (Stack_IsEmpty(stk)) {
  80.         printf("The stack is empty.\n");
  81.         return;
  82.     }
  83.     //printf("The stack contains: ");
  84.     for (int i=stk->top; i>=0; i--) {
  85.         printf("%d", stk->data[i]);
  86.     }
  87.     printf("\n");
  88. }
  89. void Palindrome(T* str, int len)
  90. //  利用stack栈判断字符串是否为回文串
  91. //  输入参数：字符串序列，字符串长度
  92. //  若是回文串输出YES，否则输出NO，末尾换行
  93. {
  94.     // 请在这里补充代码，完成本关任务
  95.     /********** Begin *********/
  96.     Stack *st = Stack_Create(200);
  97.     for (int i=0; i<len/2; i++) {
  98.         Stack_Push(st, str[i]);
  99.     }
  100.     int j = (len&1)?(len/2+1):(len/2);
  101.     for (int i=j; i<len; i++) {
  102.         if(str[i]!=Stack_Top(st)){
  103.             printf("NO\n");
  104.             return;
  105.         }else{
  106.             Stack_Pop(st);
  107.         }
  108.     }
  109.     printf("YES\n");
  110.     /********** End **********/
  111. }

第4关：栈之巩固练习

任务描述

根据栈的相关知识以及前面关卡的内容完成相关选择题。

开始你的任务吧，祝你成功！

  • 1、

    以下哪些项是栈元素操作的基本特点：（BC）

    A、先进先出
    B、先进后出
    C、后进先出
    D、后进后出

  • 2、

    利用栈实现十进制整数1234转八进制，以下哪项栈表状态符合实际情况： (B)

  • A、   A
    D、   D

  • B、   B
    C、   C

  • 3、

    若已知一个栈的入栈顺序是A、B、C、D，其出栈序列为P1、P2、P3、P4，则P2、P4不可能是（C）

    A、     B、D
    B、     C、A
    C、     D、C
    D、     C、D

 

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/秋刀鱼在做梦/article/detail/869031
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号