Chinaunix首页 | 论坛 | 博客
  • 博客访问: 35663
  • 博文数量: 24
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 246
  • 用 户 组: 普通用户
  • 注册时间: 2016-02-14 20:13
  • 认证徽章:
文章分类

全部博文(24)

文章存档

2017年(5)

2016年(19)

我的朋友

分类: C/C++

2016-02-26 22:34:51


  1. /*
  2.  * 根据郝斌老师视频整理
  3.  * 编译环境:
  4.  * guo@linux:~$ gcc --version
  5.  * gcc (Ubuntu 4.8.4-2ubuntu1~14.04.1) 4.8.4
  6.  */
  7. #include <stdio.h>
  8. #include <malloc.h>
  9. #include <stdlib.h>

  10. #define FALSE 0
  11. #define TRUE 1

  12. typedef struct Node
  13. {
  14.     int data;
  15.     struct Node *pNext;
  16. }NODE, *PNODE;

  17. typedef struct Stack
  18. {
  19.     PNODE pTop;
  20.     PNODE pBottom;
  21. }STACK, *PSTACK;

  22. /**********************声明**********************************/
  23. /*初始化栈*/
  24. void InitStack(PSTACK );
  25. /*压栈*/
  26. void PushStack(PSTACK , int );
  27. /*遍历*/
  28. void TraverseStack(PSTACK );
  29. /*判断栈是否为空*/
  30. int IsEmpty(PSTACK );
  31. /*出栈*/
  32. int PopStack(PSTACK ,int *);
  33. /*清空栈*/
  34. void ClearStack(PSTACK );


  1. /*
  2.  * 函数名称:InitStack。
  3.  * 输入参数:pStack栈变量的地址。
  4.  * 输出参数:无。
  5.  * 函数说明:新建一个栈。栈的特点是"先入后出"
  6.  */
  7. void InitStack(PSTACK pStack)
  8. {
  9.     /*申请一块内存,将内存地址赋值给栈变量所指向的pTop成员*/
  10.     pStack->pTop = (PNODE)malloc(sizeof(NODE));
  11.     if (NULL == pStack->pTop)
  12.     {
  13.         printf("动态分配内存失败!\n");
  14.         exit(-1);
  15.     }
  16.     pStack->pBottom = pStack->pTop;
  17.     pStack->pBottom->pNext = NULL;

  18.     return;
  19. }


  1. /*
  2.  * 函数名称:PushStack。
  3.  * 输入参数:pStack栈变量的地址;val压栈的值。
  4.  * 输出参数:无。
  5.  * 函数说明:将一个元素压入栈中。
  6.  */
  7. void PushStack(PSTACK pStack, int val)
  8. {
  9.     PNODE pNew = (PNODE)malloc(sizeof(NODE));
  10.     if (NULL == pNew)
  11.     {
  12.         printf("动态分配内存失败!\n");
  13.         exit(-1);
  14.     }
  15.     
  16.     pNew->data = val;
  17.     pNew->pNext = pStack->pTop;
  18.     pStack->pTop = pNew;

  19.     return;
  20. }

  21. /*
  22.  * 函数名称:TraverseStack。
  23.  * 输入参数:pStack栈变量的地址。
  24.  * 输出参数:无。
  25.  * 函数说明:将一个栈遍历输出。
  26.  */
  27. void TraverseStack(PSTACK pStack)
  28. {
  29.     PNODE p = pStack->pTop;

  30.     if (pStack->pTop == pStack->pBottom)
  31.     {
  32.         printf("栈为空!\n");
  33.     }
  34.     else
  35.     {
  36.         while (p != pStack->pBottom)
  37.         {
  38.             printf("%d ",p->data);
  39.             p = p->pNext;
  40.         }
  41.         printf("\n");
  42.     }

  43.     return;
  44. }

  45. /*
  46.  * 函数名称:IsEmpty。
  47.  * 输入参数:pStack栈变量的地址。
  48.  * 输出参数:如果栈为空返回TRUE;否则返回FALSE。
  49.  * 函数说明:判断栈是否为空。
  50.  */
  51. int IsEmpty(PSTACK pStack)
  52. {
  53.     if (pStack->pTop == pStack->pBottom)
  54.         return TRUE;
  55.     else
  56.         return FALSE;
  57. }


  58. /*
  59.  * 函数名称:PopStack。
  60.  * 输入参数:pStack栈变量的地址;pVal保存出栈的值。
  61.  * 输出参数:出栈成功返回TRUE;否则返回FALSE。
  62.  * 函数说明:出栈。
  63.  */
  64. int PopStack(PSTACK pStack,int *pVal)
  65. {
  66.     if ( IsEmpty(pStack) )
  67.     {
  68.         return FALSE;
  69.     }
  70.     else
  71.     {
  72.         PNODE r = pStack->pTop;
  73.         *pVal = r->data;
  74.         pStack->pTop = r->pNext;
  75.         free(r);
  76.         r = NULL;
  77.         return TRUE;
  78.     }
  79. }

  80. /*
  81.  * 函数名称:ClearStack。
  82.  * 输入参数:pStack栈变量的地址。
  83.  * 输出参数:无。
  84.  * 函数说明:清空栈。
  85.  */
  86. void ClearStack(PSTACK pStack)
  87. {
  88.     if ( IsEmpty(pStack) )
  89.     {
  90.         return ;
  91.     }
  92.     else
  93.     {
  94.         PNODE p = pStack->pTop;
  95.         PNODE q = NULL;
  96.         while (p != pStack->pBottom)
  97.         {
  98.             q = p->pNext;
  99.             free(p);
  100.             p = q;
  101.         }
  102.     }
  103.     pStack->pTop = pStack->pBottom;
  104. }

  105. int main(void)
  106. {
  107.     STACK Stack;
  108.     int val;

  109.     InitStack(&Stack);
  110.     PushStack(&Stack, 1);
  111.     PushStack(&Stack, 2);
  112.     PushStack(&Stack, 3);
  113.     PushStack(&Stack, 4);
  114.     PushStack(&Stack, 5);
  115.     PushStack(&Stack, 6);
  116.     PushStack(&Stack, 7);
  117.     PushStack(&Stack, 8);
  118.     TraverseStack(&Stack);

  119.     if ( PopStack(&Stack, &val) )
  120.     {
  121.         printf("出栈的元素是%d\n", val);
  122.     }
  123.     else
  124.     {
  125.         printf("出栈失败!\n");
  126.     }
  127.     printf("出栈后遍历:\n");
  128.     TraverseStack(&Stack);

  129.     if ( PopStack(&Stack, &val) )
  130.     {
  131.         printf("出栈的元素是%d\n", val);
  132.     }
  133.     else
  134.     {
  135.         printf("出栈失败!\n");
  136.     }
  137.     printf("出栈后遍历:\n");
  138.     TraverseStack(&Stack);

  139.     ClearStack(&Stack);
  140.     printf("清空后遍历:\n");
  141.     TraverseStack(&Stack);

  142.     return 0;
  143. }



阅读(344) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~
评论热议
请登录后评论。

登录 注册