[关闭]
@coder-pig 2016-01-02T14:28:58.000000Z 字数 2209 阅读 1551

小猪的数据结构辅助教程——3.2 栈与队列中的链栈

数据结构


1.本节引言:

嗯,本节没有学习路线图哈,因为栈我们一般都用的是顺序栈,链栈还是顺带提一提吧,
栈因为只是栈顶来做插入和删除操作,所以较好的方法是将栈顶放在单链表的头部,栈顶
指针与单链表的头指针合二为一~所以本节只是讲下链栈的存储结构和基本操作!

2.链栈的存储结构与示意图

存储结构

  1. typedef struct StackNode
  2. {
  3. SElemType data; //存放的数据
  4. struct StackNode *next;
  5. }StackNode,*LinkStackPtr;
  6. typedef struct LinkStack
  7. {
  8. LinkStackPtr top; //Top指针
  9. int count; //栈元素计数器
  10. }LinkStack;

示意图

由上图可以发现一点,链栈不会出现栈满的情况...


3.链栈基本操作的代码实现

代码实现

  1. #include <stdio.h>
  2. #define STACK_INIT_SIZE 10 //存储空间的初始分配量
  3. #define OK 1
  4. #define ERROR 0
  5. #define TRUE 1
  6. #define FALSE 0
  7. typedef int Status;
  8. typedef int SElemType;
  9. //存储结构
  10. typedef struct StackNode
  11. {
  12. SElemType data; //存放的数据
  13. struct StackNode *next;
  14. }StackNode,*LinkStackPtr;
  15. typedef struct LinkStack
  16. {
  17. LinkStackPtr top; //Top指针
  18. int count; //栈元素计数器
  19. }LinkStack;
  20. //1.构建一个空栈
  21. Status InitStack(LinkStack *S)
  22. {
  23. S ->top = (LinkStackPtr)malloc(sizeof(StackNode));
  24. if(!S ->top)return ERROR;
  25. S ->top = NULL;
  26. S ->count = 0;
  27. return OK;
  28. }
  29. //2.将栈置空
  30. Status ClearStack(LinkStack *S)
  31. {
  32. LinkStackPtr p,q;
  33. p = S->top;
  34. while(p)
  35. {
  36. q = p;
  37. p = p ->next;
  38. free(q);
  39. }
  40. S ->count = 0;
  41. return OK;
  42. }
  43. //3.判断栈是否为空
  44. Status StackEmpty(LinkStack S)
  45. {
  46. return S.count == 0?TRUE:FALSE;
  47. }
  48. //4.获得栈中的元素个数
  49. int StackLength(LinkStack S)
  50. {
  51. return S.count;
  52. }
  53. //5.获得栈顶元素
  54. Status GetTop(LinkStack *S,SElemType *e)
  55. {
  56. LinkStackPtr p;
  57. if(StackEmpty(*S))return ERROR;
  58. *e = S ->top->data;
  59. p = S ->top;
  60. return OK;
  61. }
  62. //6. 往链栈中插入元素(入栈)
  63. Status PushStack(LinkStack *S,SElemType e)
  64. {
  65. LinkStackPtr s = (LinkStackPtr)malloc(sizeof(StackNode));
  66. if(!s)return ERROR;
  67. s ->data = e;
  68. s ->next = S ->top;
  69. S ->top = s;
  70. S ->count++;
  71. return OK;
  72. }
  73. //7.删除栈顶元素*出栈(
  74. Status PopStack(LinkStack *S,SElemType *e)
  75. {
  76. LinkStackPtr p;
  77. if(StackEmpty(*S))return ERROR;
  78. * e = S ->top ->data;
  79. p = S ->top; //获取栈顶结点
  80. S ->top = S ->top ->next; //栈顶指针下移一位
  81. free(p); //释放结点p
  82. S ->count--;
  83. return OK;
  84. }
  85. //8.遍历栈
  86. Status StackTraverse(LinkStack S)
  87. {
  88. LinkStackPtr p;
  89. p = S.top;
  90. while(p)
  91. {
  92. visit(p->data);
  93. p=p->next;
  94. }
  95. printf("\n");
  96. return OK;
  97. }
  98. //定义一个打印元素的方法
  99. Status visit(SElemType c)
  100. {
  101. printf("%d ",c);
  102. return OK;
  103. }
  104. int main()
  105. {
  106. int i,e;
  107. LinkStack s;
  108. InitStack(&s);
  109. printf("初始化链栈,接着插入10个元素~\n");
  110. for(i = 1;i <= 10;i++)
  111. {
  112. PushStack(&s,i);
  113. }
  114. printf("此时栈中的元素依次为:\n");
  115. StackTraverse(s);
  116. printf("此时栈中有%d个元素\n",StackLength(s));
  117. PopStack(&s,&e);
  118. printf("出栈,出栈结点为:%d\n",e);
  119. printf("此时栈中的元素依次为:\n ");
  120. StackTraverse(s);
  121. ClearStack(&s);
  122. printf("清空栈,此时栈中有%d个元素!\n\n",StackLength(s));
  123. return 0;
  124. }

运行结果

代码比较简单,就不解释了~


4.本节代码下载:

https://github.com/coder-pig/Data-structure-auxiliary-tutorial/blob/master/Stack/Stack3.c

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注