当前位置:   article > 正文

顺序栈的表示和实现

顺序栈的表示和实现

参考书目:《数据结构(C语言版)》,严蔚敏

/~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

思考:对于栈和栈的Pop()函数的理解。

我原本以为Pop()函数就是一个删除栈顶元素的函数,但如果这样的话,那么他和线性表中的delete函数又有啥区别呢?

思考之后我觉得应这样理解:栈可以看成是一个后进先出的buffer。数据进栈后,待栈中元素满足程序要求时,便要进行出栈操作,这时就要调用Pop()函数,当栈中所有的元素都出栈后,此时栈就空了,等待下次数据的到来,这有点类似单片机中具有LIFO(last in first out)结构的buffer。

(完全是自己悟的,也不知道理解的对不对,还请各位指正)

当然栈也可以当做线性表来用,毕竟栈就是由线性表而来的,但我感觉实际应用没有必要这样。因为既然重新定义栈这样的数据结构,在实际应用中栈的这种操作必然有其用武之地。

注意:鉴于以上分析,程序中调用的StackDisp()函数并未按照后进先出这一规定显示stack的,当然完全可以将其改为按后进先出的规定来显示stack的,不过我估计在实际应用中StackDisp()函数未必排得上用场。

/~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

common.h

  1. #ifndef _COMMON_H_
  2. #define _COMMON_H_
  3. #define TRUE 1
  4. #define FALSE 0
  5. #define OK 1
  6. #define ERROR 0
  7. #define INFEASIBLE -1
  8. #define OVERFLOW -2
  9. typedef int Status;
  10. //Status Equal(int a, int b);
  11. #endif


stack.h

  1. #ifndef _STACK_H_
  2. #define _STACK_H_
  3. #define STACK_INIT_SIZE 10
  4. #define STACKINCREMENT 10
  5. typedef int SElemType;
  6. typedef struct
  7. {
  8. SElemType *base; //在栈构造之前和销毁之后,base的值为NULL
  9. SElemType *top; //栈顶指针
  10. int stacksize; //当前已分配的存储空间,以元素为单位
  11. }SqStack;
  12. Status InitStack(SqStack *S);
  13. //构造一个空栈S
  14. Status StackScanf(SqStack *S);
  15. //向指定的stack输入数据
  16. Status StackDisp(SqStack *S);
  17. //显示指定的stack
  18. int StackLength(SqStack *S);
  19. //返回指定stack的元素个数,即栈的长度
  20. Status GetTop(SqStack *S,SElemType *e);
  21. //若栈不空,则将S的栈顶元素传递给*e,并返回OK;否则返回ERROR
  22. Status Push(SqStack *S,SElemType e);
  23. //插入数据e为新的栈顶元素
  24. Status Pop(SqStack *S,SElemType *e);
  25. //若栈不空,则删除指定栈的栈顶元素,并用e返回其值,并返回OK;否则返回ERROR。
  26. Status DestroyStack(SqStack *S);
  27. //销毁指定栈
  28. Status ClearStack(SqStack *S);
  29. //清空指定栈
  30. Status StackEmpty(SqStack *S);
  31. //判断指定栈是否为空,若为空栈,则返回TRUE,否则返回FALSE.
  32. #endif


stack.c

  1. #include "stdio.h"
  2. #include "stdlib.h"
  3. #include "common.h"
  4. #include "stack.h"
  5. /*
  6. 输入参数:*S 待处理的栈地址
  7. 返回参数:OVERFLOW 存储分配失败
  8. OK 成功
  9. 函数功能:初始化栈,构造一个空栈。
  10. */
  11. Status InitStack(SqStack *S)
  12. {
  13. S->base = (SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));
  14. if(!S->base)
  15. exit(OVERFLOW); //存储分配失败
  16. S->top = S->base; //使栈顶指针等于栈底指针
  17. S->stacksize = STACK_INIT_SIZE; //初始化栈当前可用的最大容量
  18. return OK;
  19. }
  20. /*
  21. 输入参数:*S 待处理的栈地址
  22. 返回参数:OK 操作成功
  23. OVERFLOW stack满
  24. 还可以根据实际情况定义相应的返回值
  25. 函数功能:向指定的stack输入数据,约定若输入0则结束,并将0存储stack。
  26. 注意:在stack的存储空间够用的情况下,调用该函数得到的栈顶元素都为0,若想栈顶元素不为0可以调用Push()函数。
  27. */
  28. Status StackScanf(SqStack *S)
  29. {
  30. SElemType *cap_max;
  31. cap_max = S->base + S->stacksize - 1; //减1的原因是:留一个存储单元给栈顶指针,即当stack的存储单元用完时,使栈顶指针指向存储空间的最后一个存储单元。
  32. scanf("%d",S->top);
  33. S->top++;
  34. while(*(S->top-1))
  35. {
  36. scanf("%d",S->top);
  37. S->top++;
  38. if(S->top >= cap_max)
  39. {
  40. printf("The stack is full."); //实际应用时当然还可以在这里继续为原stack扩充容量。
  41. return OVERFLOW;
  42. }
  43. }
  44. return OK;
  45. }
  46. /*
  47. 输入参数:*S 待显示的栈地址
  48. 返回参数:OK 操作成功
  49. 还可以根据实际情况定义相应的返回值
  50. 函数功能:显示指定的stack
  51. 注意:程序中调用的StackDisp()函数并未按照后进先出这一规定显示stack的,当然完全可以将其改为按后进先出的规定来显示stack的,不过我估计在实际应用中StackDisp()函数未必排得上用场。
  52. */
  53. Status StackDisp(SqStack *S)
  54. {
  55. SElemType *bottom = S->base;
  56. printf("\n*************** output start ***************\n");
  57. while(bottom<S->top)
  58. {
  59. printf("%d ",*bottom);
  60. bottom++;
  61. }
  62. printf("\n*************** output end ***************\n");
  63. return OK;
  64. }
  65. /*
  66. 输入参数:*S 待处理的栈地址
  67. 返回参数:*S所指向的stack的长度,即该stack中的元素个数
  68. 函数功能:返回指定stack的元素个数,即栈的长度
  69. */
  70. int StackLength(SqStack *S)
  71. {
  72. //可根据需要在这里添加判断S是否满足一些条件,如判断*S指向的stack是否存在等,因为栈是否存在和栈是否空有时还是有区别的。
  73. //if(!(S->top||S->top)) //判断栈是否存在,这个当然要在销毁栈时将栈顶指针和栈底指针都清为0才能在此有所判断。
  74. // return -1;
  75. return(S->top - S->base);
  76. }
  77. /*
  78. 输入参数:*S 待处理的栈地址
  79. *e 用于存储栈顶元素
  80. 返回参数:ERROR 该栈为空
  81. OK 操作成功
  82. 函数功能:若栈不空,则将S的栈顶元素传递给*e,并返回OK;否则返回ERROR.
  83. */
  84. Status GetTop(SqStack *S,SElemType *e)
  85. {
  86. if(!StackLength(S))
  87. return ERROR;
  88. else
  89. {
  90. *e = *(S->top - 1);
  91. }
  92. return OK;
  93. }
  94. /*
  95. 输入参数:*S 待处理的栈地址
  96. e 待插入的数据
  97. 返回参数:OVERFLOW stack满
  98. OK 操作成功
  99. 函数功能:插入数据e为新的栈顶元素
  100. */
  101. Status Push(SqStack *S,SElemType e)
  102. {
  103. if(StackLength(S) >= S->stacksize)
  104. {
  105. S->base = (SElemType *)realloc(S->base,(S->stacksize + STACKINCREMENT)*sizeof(SElemType));
  106. if(!S->base)
  107. exit(OVERFLOW);
  108. S->top = S->base + S->stacksize;
  109. S->stacksize += STACKINCREMENT;
  110. }
  111. *S->top++ = e;
  112. return OK;
  113. }
  114. /*
  115. 输入参数:*S 待处理的栈地址
  116. *e 待返回的栈顶元素
  117. 返回参数:ERROR 操作失败
  118. OK 操作成功
  119. 函数功能:若栈不空,则删除指定栈的栈顶元素,并用e返回其值,并返回OK;否则返回ERROR。
  120. */
  121. Status Pop(SqStack *S,SElemType *e)
  122. {
  123. if(StackLength(S) <= 0)
  124. return ERROR;
  125. *e = * --S->top;
  126. return OK;
  127. }
  128. /*
  129. 输入参数:*S 待销毁的栈地址
  130. 返回参数:OK 操作成功
  131. 还可根据需要加入别的返回值
  132. 函数功能:销毁指定栈
  133. */
  134. Status DestroyStack(SqStack *S)
  135. {
  136. free(S->base);
  137. S->base = NULL;
  138. S->top = NULL;
  139. S->stacksize = 0;
  140. return OK;
  141. }
  142. /*
  143. 输入参数:待清空的栈地址
  144. 返回参数:OK 操作成功
  145. 函数功能:清空指定栈
  146. */
  147. Status ClearStack(SqStack *S)
  148. {
  149. S->top = S->base;
  150. return OK;
  151. }
  152. /*
  153. 输入参数:*S 待处理的栈地址
  154. 返回参数:FALSE 指定的栈非空
  155. OK 指定的栈为空
  156. 函数功能:判断指定栈是否为空,若为空栈,则返回TRUE,否则返回FALSE.
  157. */
  158. Status StackEmpty(SqStack *S)
  159. {
  160. //if(!(S->top||S->top)) //判断栈是否存在,这个当然要在销毁栈时将栈顶指针和栈底指针都清为0才能在此有所判断。
  161. // return -1;
  162. if(S->top - S->base)
  163. {return FALSE;}
  164. return TRUE;
  165. }

 

main.c

  1. //>>>第3章/3.1节
  2. #include "stdio.h"
  3. #include "stdlib.h"
  4. #include "common.h" //这个头文件一定要包含在stack.h前,因为在头文件stack.h中会用到common.h头文件中的定义。
  5. #include "stack.h"
  6. int main(void)
  7. {
  8. int top_elem=0;
  9. SqStack stack;
  10. InitStack(&stack);
  11. StackScanf(&stack);
  12. StackDisp(&stack);
  13. printf("The current stack length is %d.\n",StackLength(&stack));
  14. GetTop(&stack,&top_elem);
  15. printf("The top element is %d.\n",top_elem);
  16. Push(&stack,1010);
  17. StackDisp(&stack);
  18. printf("The current stack length is %d.\n",StackLength(&stack));
  19. GetTop(&stack,&top_elem);
  20. printf("The top element is %d.\n",top_elem);
  21. Pop(&stack,&top_elem);
  22. StackDisp(&stack);
  23. printf("The current stack length is %d.\n",StackLength(&stack));
  24. GetTop(&stack,&top_elem);
  25. printf("The top element is %d.\n",top_elem);
  26. printf("~~~~~~~~~~~~~~~~\n");
  27. printf("%d\n",*stack.top); //之前的栈顶元素还存在,只不过是栈顶指针后退了一位而已。
  28. printf("~~~~~~~~~~~~~~~~\n");
  29. Push(&stack,2020);
  30. Push(&stack,3030);
  31. Push(&stack,4040);
  32. Push(&stack,5050);
  33. StackDisp(&stack);
  34. printf("The current stack length is %d.\n",StackLength(&stack));
  35. GetTop(&stack,&top_elem);
  36. printf("The top element is %d.\n",top_elem);
  37. top_elem = 0;
  38. ClearStack(&stack);
  39. printf("\nAfter clear stack:\n");
  40. StackDisp(&stack);
  41. printf("The current stack length is %d.\n",StackLength(&stack));
  42. GetTop(&stack,&top_elem);
  43. printf("The top element is %d.\n",top_elem);
  44. top_elem = 0;
  45. DestroyStack(&stack);
  46. printf("\nAfter destroy stack:\n");
  47. StackDisp(&stack);
  48. printf("The current stack length is %d.\n",StackLength(&stack));
  49. GetTop(&stack,&top_elem);
  50. printf("The top element is %d.\n",top_elem);
  51. return 0;
  52. }

 

下面这个是后来调试所加的,当然可以将两个main文件合并。

main.c

  1. //第3章/3.2节
  2. #include "stdio.h"
  3. #include "stdlib.h"
  4. #include "common.h" //这个头文件一定要包含在stack.h前,因为在头文件stack.h中会用到common.h头文件中的定义。
  5. #include "stack.h"
  6. #include "example.h"
  7. int main(void)
  8. {
  9. Conversion(1348,8);
  10. return 0;
  11. }


运算结果如下(第一个main文件):

 

 

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

闽ICP备14008679号