MagicDevil

Menu

DynamicStack 动态栈C语言算法(链表栈)

动态栈

通过链表形式表示的静态栈,栈的长度可以随时拓展。相比较静态栈,其占用空间会稍大一些。

当通过链表表示动态栈时,为了减少遍历次数,可以把头结点当做栈顶元素,每次出栈与入栈都对头结点操作,可以减少遍历。

 

实现功能

初始化栈

入栈

出栈

清空栈

取栈的大小

打印栈的内容

 

代码

GitHub:https://github.com/MagicDevilZhang/myDataStructProject/blob/master/DynamicStack.cpp

CSDN:https://blog.csdn.net/MagicDevilZhang/article/details/84256749

以下代码纯手工编写,欢迎指出错误和优化方法。

  1. #include <stdio.h>
  2. #include <windows.h>
  3. #define SUCCESS 1
  4. #define ERROR -1
  5. #define ElemType int
  6. #define StatusType int
  7. typedef struct StackNode
  8. {
  9. ElemType data;
  10. structStackNode*next;
  11. } StackNode, *Stack;
  12. //1.初始化栈空间
  13. StatusType InitStack(Stack &S)
  14. {
  15. S = (Stack)malloc(sizeof(StackNode));
  16. S->data = NULL;
  17. S->next = NULL;
  18. return SUCCESS;
  19. }
  20. //2.入栈
  21. StatusType PushStack(Stack &S, ElemType content)
  22. {
  23. if (!S || content == ERROR)
  24. { //但栈未初始化或传入元素不存在返回ERROR
  25. return ERROR;
  26. }
  27. if (!S->data)
  28. { //覆盖空链表栈
  29. S->data = content;
  30. return SUCCESS;
  31. }
  32. //新建一个新链表存放内容
  33. Stack newstack;
  34. InitStack(newstack);
  35. newstack->data = content;
  36. //将新链表设为头结点连接后续链表
  37. newstack->next = S;
  38. S = newstack;
  39. return SUCCESS;
  40. }
  41. //3.出栈
  42. ElemType PopStack(Stack &S)
  43. {
  44. if (S->next)
  45. { //未到栈底
  46. Stack outstack = S;
  47. ElemType out = outstack->data;
  48. S = S->next;
  49. free(outstack);
  50. return out;
  51. }
  52. if (S->data)
  53. { //到达栈底元素时
  54. ElemType out = S->data;
  55. S->data = NULL;
  56. return out;
  57. }
  58. return ERROR;
  59. }
  60. //4.清空栈
  61. StatusType ClearStack(Stack &S)
  62. {
  63. if (S->next)
  64. {
  65. ClearStack(S->next); //遍历所有元素
  66. }
  67. free(S->next); //清空尾巴保留头结点
  68. S->data = NULL;
  69. S->next = NULL;
  70. return SUCCESS;
  71. }
  72. //5.取栈的大小
  73. int getStackNum(Stack &S)
  74. {
  75. if (S->data)
  76. {
  77. return1+getStackNum(S->next);
  78. }
  79. return0;
  80. }
  81. //6.打印栈的内容
  82. StatusType PrintStack(Stack &S)
  83. {
  84. int foot =0;
  85. int flag =0;
  86. int num =0;
  87. Stack stack;
  88. stack = S;
  89. printf("Stack Information\n");
  90. while (flag ==0)
  91. {
  92. if (stack->next==NULL)
  93. { //当遍历到最后一个元素时退出
  94. flag = 1;
  95. }
  96. num++;
  97. printf(" |- Stack %d : %d\n", foot++, stack->data);
  98. stack = stack->next;
  99. }
  100. printf("Num : %d\n", num);
  101. return SUCCESS;
  102. }
  103. int main(int argc, char const *argv[])
  104. {
  105. Stack stack, q;
  106. InitStack(stack);
  107. InitStack(q);
  108. PushStack(stack, 1);
  109. PushStack(stack, 3);
  110. PushStack(stack, 5);
  111. PushStack(stack, 7);
  112. PrintStack(stack);
  113. PushStack(q, PopStack(stack));
  114. PushStack(q, PopStack(stack));
  115. PushStack(q, PopStack(stack));
  116. PushStack(q, PopStack(stack));
  117. PushStack(q, PopStack(stack));
  118. PrintStack(q);
  119. printf("%d\n", getStackNum(stack));
  120. system("pause");
  121. return0;
  122. }
共写了2003个字