devbox
繁依Fanyi0
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

【数据结构】 链栈的基本操作 （C语言版）_链栈的基本操作实现(c语言)

作者：繁依Fanyi0 | 2024-07-30 23:49:44

赞

踩

链栈的基本操作实现(c语言)

目录

一、链栈

1、链栈的定义：

2、链栈的优缺点：

二、链栈的基本操作算法（C语言）    

1、宏定义

  2、创建结构体

3、链栈的初始化 

 4、链栈的进栈

5、链栈的出栈

6、获取栈顶元素

7、栈的遍历输出

8、链栈的判空

 9、求链栈的栈长

10、链栈的清空

11、链栈的销毁

三、链栈的基本操作完整代码（C语言）

 四、运行结果

一、链栈

1、链栈的定义：

链栈是一种栈的实现方式，它使用链表结构来实现。每个节点包含数据域和指针域，其中数据域用于存储数据，指针域用于指向下一个节点。链栈的栈顶指针指向栈顶元素，栈底指针指向栈底元素。

2、链栈的优缺点：

链栈的优点：

  1. 空间利用率高：链栈可以根据实际情况动态调整栈的大小，避免了顺序栈可能出现的内存溢出等问题。
  2. 时间复杂度低：链栈的入栈和出栈操作只需要改变栈顶指针的指向，时间复杂度为O(1)，不需要像顺序栈一样进行数据的移动，具有比较高的效率。
  3. 方便进行动态扩展：链栈可以方便地进行动态扩展，当需要增加元素时，可以动态地增加存储空间；当需要减少元素时，可以释放未使用的空间。

链栈的 缺点：

  1. 需要额外的指针存储空间，因此占用的存储空间较大。
  2. 插入和删除操作需要修改指针，操作较为复杂。
  3. 无法充分利用内存的连续性优势，因为链表节点的存储位置是分散的。

二、链栈的基本操作算法（C语言）    

1、宏定义
  1. #define OK 1
  2. #define ERROR 0
  3. #define OVERFLOW -1
  4.  
  5.  
  6. typedef int SElemType;
  7. typedef int Status;
  2、创建结构体
  1. //创建结构体
  2. typedef struct StackNode {
  3.     SElemType data;
  4.     struct StackNode *next;
  5. } StackNode, *LinkStack;
3、链栈的初始化 
  1. //初始化
  2. Status InitStack(LinkStack &S) {
  3.     S = NULL;
  4.     return OK;
  5. }
 4、链栈的进栈
  1. //进栈
  2. Status Push(LinkStack &S, SElemType e) {//在栈顶插入元素e
  3.     StackNode *p = new StackNode; //生成新结点
  4.     if (!p) exit(OVERFLOW);
  5.  
  6.     p->data = e;
  7.     p->next = S; //将新结点插入  栈顶
  8.  
  9.     S = p;       //修改栈顶指针为p
  10.     return OK;
  11. }
5、链栈的出栈
  1. //出栈
  2. Status Pop(LinkStack &S, int &e) {//删除S的栈顶元素，用e返回其值
  3.     if (S == NULL) {
  4.         return ERROR;
  5.     }
  6.  
  7.     e = S->data;      //将栈顶元素赋给e
  8.     LinkStack p = S;            //用p临时保存栈顶元素空间，以备释放
  9.     S = S->next;      //修改栈顶指针
  10.     delete p;
  11.     return OK;
  12. }
6、获取栈顶元素
  1.  
  2. //获取栈顶元素
  3. Status Top(LinkStack &S, int &e) {//删除S的栈顶元素，用e返回其值
  4.     if (S == NULL) {
  5.         return ERROR;
  6.     }
  7.     e = S->data;      //将栈顶元素赋给e
  8.     return OK;
  9. }
7、栈的遍历输出
  1. //栈的遍历输出
  2. void StackTraverse(LinkStack S) {
  3.     LinkStack p;  //使用指针p辅助访问栈里元素
  4.     p = S;           //p初始从栈顶开始
  5.     printf("从栈顶依次读出该栈中的元素值为:");
  6.     while (p != NULL) {
  7.         printf("%d ", p->data);
  8.         p = p->next;
  9.     }
  10.     printf("\n");
  11. }
8、链栈的判空
  1. //判空
  2. Status stackEmpty(LinkStack S) {
  3.     if (S == NULL) {如果栈顶的指针域指向空，则栈空
  4.         return true;
  5.     } else {
  6.         return false;
  7.     }
  8. }
 9、求链栈的栈长
  1. //求栈长
  2. Status stackLength(LinkStack S) {
  3.     int len = 0;
  4.     while (S != NULL) {
  5.         len++;
  6.         S = S->next;
  7.     }
  8.     return len;
  9. }
10、链栈的清空
  1. //清空
  2. Status ClearStack(LinkStack &S) {
  3.     StackNode *p;
  4.     while (S != NULL) {
  5.         p = S->next;
  6.         delete S;
  7.         S = p;
  8.     }
  9.     return OK;
  10. }
11、链栈的销毁
  1. //销毁
  2. Status DestoryStack(LinkStack S) {
  3.     StackNode *p;
  4.     while (S) {
  5.         p = S;
  6.         S = S->next;
  7.         delete p;
  8.     }
  9.     S = NULL;
  10.     return OK;
  11. }

三、链栈的基本操作完整代码（C语言）

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. #define OK 1
  5. #define ERROR 0
  6. #define OVERFLOW -1
  7.  
  8.  
  9. typedef int SElemType;
  10. typedef int Status;
  11.  
  12. //创建结构体
  13. typedef struct StackNode {
  14.     SElemType data;
  15.     struct StackNode *next;
  16. } StackNode, *LinkStack;
  17.  
  18. //初始化
  19. Status InitStack(LinkStack &S) {
  20.     S = NULL;
  21.     return OK;
  22. }
  23.  
  24. //进栈
  25. Status Push(LinkStack &S, SElemType e) {//在栈顶插入元素e
  26.     StackNode *p = new StackNode; //生成新结点
  27.     if (!p) exit(OVERFLOW);
  28.  
  29.     p->data = e;
  30.     p->next = S; //将新结点插入  栈顶
  31.  
  32.     S = p;       //修改栈顶指针为p
  33.     return OK;
  34. }
  35.  
  36. //出栈
  37. Status Pop(LinkStack &S, int &e) {//删除S的栈顶元素，用e返回其值
  38.     if (S == NULL) {
  39.         return ERROR;
  40.     }
  41.  
  42.     e = S->data;      //将栈顶元素赋给e
  43.     LinkStack p = S;            //用p临时保存栈顶元素空间，以备释放
  44.     S = S->next;      //修改栈顶指针
  45.     delete p;
  46.     return OK;
  47. }
  48.  
  49. //获取栈顶元素
  50. Status Top(LinkStack &S, int &e) {//删除S的栈顶元素，用e返回其值
  51.     if (S == NULL) {
  52.         return ERROR;
  53.     }
  54.     e = S->data;      //将栈顶元素赋给e
  55.     return OK;
  56. }
  57.  
  58. //获取栈顶元素
  59. Status GetTop(LinkStack S) {//返回S的栈顶元素，不修改栈顶指针
  60.     if (S != NULL) {
  61.         return S->data;
  62.     }
  63. }
  64.  
  65. //栈的遍历输出
  66. void StackTraverse(LinkStack S) {
  67.     LinkStack p;  //使用指针p辅助访问栈里元素
  68.     p = S;           //p初始从栈顶开始
  69.     printf("从栈顶依次读出该栈中的元素值为:");
  70.     while (p != NULL) {
  71.         printf("%d ", p->data);
  72.         p = p->next;
  73.     }
  74.     printf("\n");
  75. }
  76.  
  77. //判空
  78. Status stackEmpty(LinkStack S) {
  79.     if (S == NULL) {如果栈顶的指针域指向空，则栈空
  80.         return true;
  81.     } else {
  82.         return false;
  83.     }
  84. }
  85.  
  86. //求栈长
  87. Status stackLength(LinkStack S) {
  88.     int len = 0;
  89.     while (S != NULL) {
  90.         len++;
  91.         S = S->next;
  92.     }
  93.     return len;
  94. }
  95.  
  96. //清空
  97. Status ClearStack(LinkStack &S) {
  98.     StackNode *p;
  99.     while (S != NULL) {
  100.         p = S->next;
  101.         delete S;
  102.         S = p;
  103.     }
  104.     return OK;
  105. }
  106.  
  107. //销毁
  108. Status DestoryStack(LinkStack S) {
  109.     StackNode *p;
  110.     while (S) {
  111.         p = S;
  112.         S = S->next;
  113.         delete p;
  114.     }
  115.     S = NULL;
  116.     return OK;
  117. }
  118.  
  119. //功能菜单
  120. int choice() {
  121.     printf("==================================\n");
  122.     printf("         链栈操作功能菜单            \n");
  123.     printf("1、进栈  2、出栈  3、获取栈顶元素 \n");
  124.     printf("4、清空  5、销毁   6、批量进栈   \n");
  125.     printf("7、判空           8、链栈的长度 \n");
  126.     printf("9、打印栈内元素     10、退出程序 \n");
  127.     printf("==================================\n");
  128.     return 0;
  129. }
  130.  
  131. int main() {
  132.     LinkStack linkstack;
  133.  
  134.     //初始化
  135.     Status rInitStack = InitStack(linkstack);
  136.     if (rInitStack == OK) {
  137.         printf("链栈初始化成功！\n");
  138.     } else {
  139.         printf("链栈初始化失败！\n");
  140.     }
  141.  
  142.     while (1) {
  143.  
  144.         //功能菜单
  145.         choice();
  146.  
  147.         int flag;
  148.         printf("请输入所需的功能编号：\n");
  149.         scanf("%d", &flag);
  150.  
  151.         switch (flag) {
  152.             case 1: {//进栈
  153.                 Status Pushdata;
  154.                 printf("请输入插入元素(请在英文状态下输入例如:1): \n");
  155.                 scanf("%d", &Pushdata);
  156.                 Status rPush = Push(linkstack, Pushdata);
  157.                 if (rPush == OK) {
  158.                     printf("向链栈进栈%d成功！\n", Pushdata);
  159.                 } else {
  160.                     printf("向链栈进栈失败！\n");
  161.                 }
  162.             }
  163.                 break;
  164.             case 2: {//出栈
  165.                 Status popData;
  166.                 Status rPop = Pop(linkstack, popData);
  167.                 if (rPop == OK) {
  168.                     printf("向链栈出栈%d成功！\n", popData);
  169.                 } else {
  170.                     printf("向链栈出栈失败！\n");
  171.                 }
  172.             }
  173.                 break;
  174.             case 3: {//获取栈顶元素
  175.                 Status topData;
  176.                 Status rTop = Top(linkstack, topData);
  177.                 if (rTop == OK) {
  178.                     printf("向链栈获取栈顶元素：%d\n", topData);
  179.                 } else {
  180.                     printf("向链栈获取栈顶元素失败！\n");
  181.                 }
  182. //                //获取栈顶元素
  183. //                Status rGetTop = GetTop(linkstack);
  184. //                if (rGetTop == OK) {
  185. //                    printf("向链栈获取栈顶元素：%d\n", topData);
  186. //                } else {
  187. //                    printf("向链栈获取栈顶元素失败！\n");
  188. //                }
  189.             }
  190.                 break;
  191.             case 4: { //清空
  192.                 Status rClearStack = ClearStack(linkstack);
  193.                 if (rClearStack == OK) {
  194.                     printf("链栈清空成功！\n");
  195.                 } else {
  196.                     printf("链栈清空失败！\n");
  197.                 }
  198.             }
  199.                 break;
  200.             case 5: {//销毁
  201.                 Status rDestroyStack = DestoryStack(linkstack);
  202.                 if (rDestroyStack == OK) {
  203.                     printf("链栈销毁成功！\n");
  204.                 } else {
  205.                     printf("链栈销毁失败！\n");
  206.                 }
  207.             }
  208.                 break;
  209.             case 6: {//批量插入
  210.                 int on;
  211.                 printf("请输入想要插入的元素个数：\n");
  212.                 scanf("%d", &on);
  213.                 SElemType array[on];
  214.                 for (int i = 1; i <= on; i++) {
  215.                     getchar();
  216.                     printf("向顺序栈第%d个位置插入元素为:", (i));
  217.                     scanf("%d", &array[i]);
  218.                 }
  219.  
  220.                 for (int i = 1; i <= on; i++) {
  221.                     Status rPush = Push(linkstack, array[i]);
  222.                     if (rPush == OK) {
  223.                         printf("向链栈进栈%d成功！\n", array[i]);
  224.                     } else {
  225.                         printf("向链栈进栈失败！\n");
  226.                     }
  227.                 }
  228.             }
  229.                 break;
  230.             case 7: {//判空
  231.                 Status rStackEmpty = stackEmpty(linkstack);
  232.                 if (rStackEmpty == true) {
  233.                     printf("链栈为空栈！\n\n");
  234.                 } else
  235.                     printf("链栈不为空！\n\n");
  236.             }
  237.                 break;
  238.             case 8: {//链栈的长度
  239.                 Status length = stackLength(linkstack);
  240.                 printf("链栈的长度为：%d 。\n\n", length);
  241.             }
  242.                 break;
  243.             case 9: {  //打印栈内元素
  244.                 StackTraverse(linkstack);
  245.             }
  246.                 break;
  247.             case 10: {//退出程序
  248.                 return 0;
  249.             }
  250.                 break;
  251.             default: {
  252.                 printf("输入错误，无此功能，请检查输入:\n\n");
  253.             }
  254.         }
  255.     }
  256.  
  257.     return 1;
  258. }

 四、运行结果

 

本文内容由网友自发贡献，转载请注明出处：【wpsshop博客】
推荐阅读
相关标签

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

  

闽ICP备14008679号