Chinaunix首页 | 论坛 | 博客

oops

首页　| 　博文目录　| 　关于我

王贤才

  • 博客访问： 1184572
  • 博文数量： 573
  • 博客积分： 0
  • 博客等级： 民兵
  • 技术积分： 66
  • 用 户 组： 普通用户
  • 注册时间： 2016-06-28 16:21
文章分类

全部博文（573）

文章存档

2018年（3）

2016年（48）

2015年（522）

我的朋友
最近访客
推荐博文
相关博文
顺序栈

分类： C/C++

2015-12-02 14:52:49


点击(此处)折叠或打开

  1. #include <string.h>
  2. #include <stdio.h>
  3. #include <stdlib.h>

  5. #define STACK_INIT_SIZE 10 /*栈空间的初始分配量*/
  6. #define STACKINCREAMENT 5 /*栈空间的分配增量*/
  7. #define SZ_STRING 32

  9. typedef char STRING[SZ_STRING];

  11. /*定义顺序栈的结构体:描述了栈的所有要素*/
  12. typedef struct stack
  13. {
  14.     STRING * base; /*栈底指针:指向指针的指针，即指向字符串的指针*/
  15.     STRING * top; /*栈顶指针*/
  16.     int stacksize; /*记录栈的大小*/
  17. }STACK;
  18. typedef STACK * StackPtr;

  20. int InitStack(StackPtr stackptr);
  21. int StackIsEmpty(STACK stack);
  22. int Push(StackPtr stackptr, STRING string);
  23. int Pop(StackPtr stackptr, STRING string);
  24. int GetTop(STACK stack, STRING string);
  25. int PrintStack(STACK stack);
  26. int StackLen(STACK stack);
  27. int DestroyStack(StackPtr stackptr);

  29. int main(int argc, char ** argv)
  30. {
  31.     /*
  32.     顺序存储栈的特点：
  33.     1，栈空间是预先静态分配的，以后需要时，再增大存储空间
  34.     2，有栈顶指针和栈底指针
  35.     3，栈顶指针始终在栈顶元素的下一个位置上
  36.     4，栈底在地址低端，栈顶在地址高端
  37.     */
  38.     printf("顺序存储栈的实现！\n");
  39.     int stat = -2;
  40.     STRING string;
  41.     printf("sizeof(STRING)=[%d], sizeof(string)=[%d]\n", sizeof(STRING), sizeof(string));
  42.     
  43.     //STACK stack; /*定义栈元素：会自动开辟一个元素的空间*/
  44.     
  45.     StackPtr stackptr = NULL; /*定义栈指针：需要手动开辟一个空间*/
  46.     stackptr = (StackPtr)malloc(sizeof(STACK));
  47.     InitStack(stackptr);
  48.     printf("111**************************************************************\n");
  49.     PrintStack(*stackptr);
  50.     
  51.     
  52.     stat = StackIsEmpty(*stackptr);
  53.     if(stat == 1)
  54.         printf("当前栈是空栈！\n");
  55.     else if(stat == 2)
  56.         printf("当前栈是非空栈！\n");
  57.     
  58.     memset(string, 0, sizeof(string));
  59.     strcpy(string, "AAA");
  60.     Push(stackptr, string);
  61.     memset(string, 0, sizeof(string));
  62.     strcpy(string, "BBB");
  63.     Push(stackptr, string);
  64.     memset(string, 0, sizeof(string));
  65.     strcpy(string, "CCC");
  66.     Push(stackptr, string);
  67.     memset(string, 0, sizeof(string));
  68.     strcpy(string, "DDD");
  69.     Push(stackptr, string);
  70.     memset(string, 0, sizeof(string));
  71.     strcpy(string, "EEE");
  72.     Push(stackptr, string);
  73.     memset(string, 0, sizeof(string));
  74.     strcpy(string, "FFF");
  75.     Push(stackptr, string);
  76.     memset(string, 0, sizeof(string));
  77.     strcpy(string, "GGG");
  78.     Push(stackptr, string);
  79.     memset(string, 0, sizeof(string));
  80.     strcpy(string, "HHH");
  81.     Push(stackptr, string);
  82.     memset(string, 0, sizeof(string));
  83.     strcpy(string, "III");
  84.     Push(stackptr, string);
  85.     memset(string, 0, sizeof(string));
  86.     strcpy(string, "JJJ");
  87.     Push(stackptr, string);
  88.     
  89.     stat = StackIsEmpty(*stackptr);
  90.     if(stat == 1)
  91.         printf("当前栈是空栈！\n");
  92.     else if(stat == 2)
  93.         printf("当前栈是非空栈！\n");
  94.     printf("222**************************************************************\n");
  95.     PrintStack(*stackptr);
  96.     memset(string, 0, sizeof(string));
  97.     strcpy(string, "KKK");
  98.     Push(stackptr, string);
  99.     memset(string, 0, sizeof(string));
  100.     strcpy(string, "LLL");
  101.     Push(stackptr, string);
  102.     memset(string, 0, sizeof(string));
  103.     strcpy(string, "MMM");
  104.     Push(stackptr, string);
  105.     memset(string, 0, sizeof(string));
  106.     strcpy(string, "NNN");
  107.     Push(stackptr, string);
  108.     memset(string, 0, sizeof(string));
  109.     strcpy(string, "OOO");
  110.     Push(stackptr, string);
  111.     printf("333**************************************************************\n");
  112.     PrintStack(*stackptr);
  113.     memset(string, 0, sizeof(string));
  114.     strcpy(string, "PPP");
  115.     Push(stackptr, string);
  116.     printf("444**************************************************************\n");
  117.     PrintStack(*stackptr);
  118.     
  119.     memset(string, 0, sizeof(string));
  120.     Pop(stackptr, string);
  121.     printf("string1=[%s]\n", string);
  122.     printf("555**************************************************************\n");
  123.     PrintStack(*stackptr);
  124.     memset(string, 0, sizeof(string));
  125.     Pop(stackptr, string);
  126.     printf("string2=[%s]\n", string);
  127.     printf("666**************************************************************\n");
  128.     PrintStack(*stackptr);
  129.     
  130.     GetTop(*stackptr, string);
  131.     printf("取得元素=[%s]\n", string);
  132.     printf("777**************************************************************\n");
  133.     PrintStack(*stackptr);
  134.     
  135.     memset(string, 0, sizeof(string));
  136.     Pop(stackptr, string);
  137.     memset(string, 0, sizeof(string));
  138.     Pop(stackptr, string);
  139.     memset(string, 0, sizeof(string));
  140.     Pop(stackptr, string);
  141.     memset(string, 0, sizeof(string));
  142.     Pop(stackptr, string);
  143.     memset(string, 0, sizeof(string));
  144.     Pop(stackptr, string);
  145.     memset(string, 0, sizeof(string));
  146.     Pop(stackptr, string);
  147.     memset(string, 0, sizeof(string));
  148.     Pop(stackptr, string);
  149.     memset(string, 0, sizeof(string));
  150.     Pop(stackptr, string);
  151.     memset(string, 0, sizeof(string));
  152.     Pop(stackptr, string);
  153.     memset(string, 0, sizeof(string));
  154.     Pop(stackptr, string);
  155.     memset(string, 0, sizeof(string));
  156.     Pop(stackptr, string);
  157.     memset(string, 0, sizeof(string));
  158.     Pop(stackptr, string);
  159.     memset(string, 0, sizeof(string));
  160.     Pop(stackptr, string);
  161.     memset(string, 0, sizeof(string));
  162.     Pop(stackptr, string);
  163.     memset(string, 0, sizeof(string));
  164.     Pop(stackptr, string);
  165.     printf("888**************************************************************\n");
  166.     DestroyStack(stackptr);
  167.     
  168.     return 0;
  169. }

  171. /*功能：栈的初始化*/
  172. int InitStack(StackPtr stackptr)
  173. {
  174.     stackptr->base = (STRING * )malloc(STACK_INIT_SIZE * sizeof(STRING));
  175.     /*stack-> 等价于 (*stack).*/
  176.     /*栈底指针指向开辟的空间的地址低端,开辟的空间的地址类型是：eletype*/
  177.     if(stackptr->base == NULL)
  178.     {
  179.         printf("malloc失败，退出程序\n");
  180.         exit(-1);
  181.     }
  182.     stackptr->top = stackptr->base; /*栈顶指针也指向地址低端，表明是空栈*/
  183.     stackptr->stacksize = STACK_INIT_SIZE; /*记录栈的容量，不是栈中元素个数*/
  184.     
  185.     return 0;
  186. }

  188. /*功能：判断栈是否为空 1:空栈，2：非空栈*/
  189. int StackIsEmpty(STACK stack)
  190. {
  191.     //栈顶和栈底相同，即可判断为空
  192.     if(stack.top == stack.base)
  193.         return 1;
  194.     else
  195.         return 2;
  196. }

  198. /*功能：入栈操作*/
  199. int Push(StackPtr stackptr, STRING string)
  200. {
  201.     /*要先判断栈是否已满*/
  202.     if((stackptr->top - stackptr->base) >= stackptr->stacksize)
  203.     {
  204.         /*top指针已经指向栈空间的最高地址的外面了。表示栈中元素已满：即“上溢”，则追加存储空间*/
  205.         stackptr->base = (STRING *)realloc(stackptr->base, (stackptr->stacksize + STACKINCREAMENT) * sizeof(STRING));
  206.         if(stackptr->base == NULL)
  207.         {
  208.             printf("realloc失败，退出程序\n");
  209.             exit(-1);
  210.         }
  211.         stackptr->top = stackptr->base + stackptr->stacksize; /*当前栈顶指针=栈底指针+栈的原来的容量*/
  212.         stackptr->stacksize = stackptr->stacksize + STACKINCREAMENT; /*栈的容量已经改变*/
  213.     }
  214.     //*(stackptr->top) = ele; //元素e入栈
  215.     strcpy(*(stackptr->top), string);
  216.     stackptr->top = (stackptr->top)++; //保证:栈顶指针始终在栈顶元素的下一个位置
  217.     
  218.     /*
  219.     *((*stackptr).top) = ele;
  220.     (*stackptr).top = (*stackptr).top + 1;
  221.     */
  222.     printf("入栈一个元素=[%s],栈空间大小=[%d],栈中元素个数=[%d]\n", string, stackptr->stacksize, StackLen(*stackptr));
  223.     return 0;
  224. }

  226. /*功能：出栈操作*/
  227. int Pop(StackPtr stackptr, STRING string)
  228. {
  229.     /*先判断是否是空栈*/
  230.     if(stackptr->top == stackptr->base)
  231.     {
  232.         printf("栈为空，无元素可出栈！\n");
  233.         return -1;
  234.     }
  235.     stackptr->top = stackptr->top -1;
  236.     //*ele = *(stackptr->top);
  237.     strcpy(string, *(stackptr->top));
  238.     printf("出栈一个元素=[%s],栈空间大小=[%d],栈中剩余元素个数=[%d]\n", string, stackptr->stacksize, StackLen(*stackptr));
  239.     return 0;
  240. }

  242. /*功能：取栈顶元素*/
  243. int GetTop(STACK stack, STRING string)
  244. {
  245.     /*先判断是否是空栈*/
  246.     if(stack.top == stack.base)
  247.     {
  248.         printf("栈为空，无栈顶元素可取！\n");
  249.         return -1;
  250.     }
  251.     stack.top = stack.top -1; /*只是取栈顶元素，不可移动栈顶指针*/
  252.     //*ele = *(stack.top);
  253.     strcpy(string, *(stack.top));
  254.     printf("当前栈顶元素=[%s]!\n", string);
  255.     return 0;
  256. }

  258. /*功能：打印栈中的所有元素*/
  259. int PrintStack(STACK stack)
  260. {
  261.     printf("栈空间大小=[%d],栈中元素个数=[%d]\n", stack.stacksize, StackLen(stack));
  262.     /*先判断是否是空栈*/
  263.     if(stack.top == stack.base)
  264.     {
  265.         printf("栈为空,无需打印栈中元素!\n");
  266.         return -1;
  267.     }
  268.     int num = 0;
  269.     stack.top = stack.top -1;
  270.     printf("从栈顶开始：\n");
  271.     while(stack.top != stack.base)
  272.     {
  273.         num++;
  274.         printf("(第%02d个元素)=[%s]\n", num, *(stack.top));
  275.         (stack.top)--;
  276.     }
  277.     if(stack.top == stack.base) /*说明已经指向栈底了*/
  278.     {
  279.         num++;
  280.         printf("(第%02d个元素)=[%s]\n", num, *(stack.top));
  281.     }
  282.         
  283.     return 0;
  284. }

  286. /*功能：求栈中元素的个数*/
  287. int StackLen(STACK stack)
  288. {
  289.     int num = 0;
  290.     /*先判断是否是空栈*/
  291.     if(stack.top == stack.base)
  292.     {
  293.         /*printf("栈为空!\n");*/
  294.         num = 0;
  295.         return num;
  296.     }
  297.     stack.top = stack.top -1;
  298.     while(stack.top != stack.base)
  299.     {
  300.         num++;
  301.         (stack.top)--;
  302.     }
  303.     if(stack.top == stack.base) /*说明已经指向栈底了*/
  304.     {
  305.         num++;
  306.     }
  307.     
  308.     return num;
  309. }

  311. /*功能：销毁栈*/
  312. int DestroyStack(StackPtr stackptr)
  313. {
  314.     free(stackptr->base);
  315.     stackptr->base = NULL;
  316.     stackptr->top = NULL;
  317.     stackptr->stacksize = 0;
  318.     printf("顺序栈已销毁！\n");
  319.     
  320.     return 0;
  321. }

  323. /*功能：将栈中元素清空（栈还在，不是销毁栈）*/
  324. int ClearStack(StackPtr stackptr)
  325. {
  326.     return 0;
  327. }

阅读(621) | 评论(0) | 转发(0) |
0

上一篇：链式栈

下一篇：任意数制的转换

给主人留下些什么吧！~~
关于我们 | 关于IT168 | 联系方式 | 广告合作 | 法律声明 | 免费注册

Copyright 2001-2010 ChinaUnix.net All Rights Reserved 北京皓辰网域网络信息技术有限公司. 版权所有

感谢所有关心和支持过ChinaUnix的朋友们

16024965号-6