Chinaunix首页 | 论坛 | 博客

oops

首页　| 　博文目录　| 　关于我

王贤才

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

全部博文（573）

文章存档

2018年（3）

2016年（48）

2015年（522）

我的朋友
最近访客
推荐博文
相关博文
链式栈

分类： C/C++

2015-12-02 14:51:51


点击(此处)折叠或打开

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

  5. #define SZ_STRING 32

  7. typedef char STRING[SZ_STRING];

  9. /*链式栈存储结构：栈元素节点的定义*/
  10. /*好处：栈结点元素的成员可以方便扩充*/
  11. typedef struct stack
  12. {
  13.     STRING string;
  14.     struct stack * next;
  15. }STACKNODE;

  17. typedef STACKNODE * StackNodePtr;

  19. /*栈的要素的定义*/
  20. typedef struct linkstack
  21. {
  22.     StackNodePtr top; /*栈顶指针：始终指向链表头节点*/
  23.     StackNodePtr base; /*栈底指针*/
  24. }LINKSTACK;

  26. int InitSatck(LINKSTACK * linkstack);
  27. int StackIsEmpty(LINKSTACK linkstack);
  28. int CreatStackNode(StackNodePtr * stacknodeptr, STRING string);
  29. int Push(LINKSTACK * linkstack, STRING string);
  30. int Pop(LINKSTACK * linkstack, STRING string);
  31. int StackLen(LINKSTACK linkstack);
  32. int PrintSatck(LINKSTACK linkstack);
  33. int GetStackHead(LINKSTACK linkstack, STRING string);
  34. int DestroyStack(LINKSTACK * linkstack);

  36. int main(int argc, char ** argv)
  37. {
  38.     /*
  39.     链式存储栈的特点：
  40.     1，栈空间是动态分配的，每一个栈的节点都包括真实的数据域和指针域
  41.     2，栈顶指针:指向链表的空头节点,空头节点的下一个元素就是栈顶元素
  42.     3，栈底指针：指向链表的最后一个节点
  43.     3，栈顶元素始终是头节点的下一个元素
  44.     4，栈底元素始终是链表的最后一个元素
  45.     */
  46.     printf("链式存储栈的实现！\n");
  47.     
  48.     LINKSTACK linkstack;
  49.     InitSatck(&linkstack);
  50.     
  51.     int flag = -1;
  52.     flag = StackIsEmpty(linkstack);
  53.     if(flag == 1)
  54.         printf("是空栈！\n");
  55.     else if(flag == 2)
  56.         printf("是非空栈！\n");
  57.     
  58.     Push(&linkstack, "AAA");
  59.     
  60.     flag = StackIsEmpty(linkstack);
  61.     if(flag == 1)
  62.         printf("是空栈！\n");
  63.     else if(flag == 2)
  64.         printf("是非空栈！\n");
  65.         
  66.     Push(&linkstack, "BBB");
  67.     Push(&linkstack, "CCC");
  68.     Push(&linkstack, "DDD");
  69.     Push(&linkstack, "EEE");
  70.     Push(&linkstack, "FFF");
  71.     Push(&linkstack, "GGG");
  72.     
  73.     PrintSatck(linkstack);
  74.     
  75.     STRING string;
  76.     memset(string, 0, sizeof(STRING));
  77.     Pop(&linkstack, string);
  78.     printf("出栈元素1=[%s]\n", string);
  79.     memset(string, 0, sizeof(STRING));
  80.     Pop(&linkstack, string);
  81.     printf("出栈元素2=[%s]\n", string);
  82.     PrintSatck(linkstack);
  83.     
  84.     memset(string, 0, sizeof(STRING));
  85.     Pop(&linkstack, string);
  86.     memset(string, 0, sizeof(STRING));
  87.     GetStackHead(linkstack, string);
  88.     printf("取得栈顶元素1=[%s]\n", string);
  89.     memset(string, 0, sizeof(STRING));
  90.     Pop(&linkstack, string);
  91.     memset(string, 0, sizeof(STRING));
  92.     GetStackHead(linkstack, string);
  93.     printf("取得栈顶元素2=[%s]\n", string);
  94.     //DestroyStack(&linkstack);
  95.     //DestroyStack(&linkstack);
  96.     //DestroyStack(&linkstack);
  97.     //PrintSatck(linkstack);
  98.     memset(string, 0, sizeof(STRING));
  99.     Pop(&linkstack, string);
  100.     memset(string, 0, sizeof(STRING));
  101.     Pop(&linkstack, string);
  102.     memset(string, 0, sizeof(STRING));
  103.     Pop(&linkstack, string);
  104.     memset(string, 0, sizeof(STRING));
  105.     Pop(&linkstack, string);
  106.     memset(string, 0, sizeof(STRING));
  107.     Pop(&linkstack, string);
  108.     
  109.     PrintSatck(linkstack);
  110.     
  111.     return 0;
  112. }

  114. /*功能：判断链式栈是否为空,1：空， 2：非空*/
  115. int StackIsEmpty(LINKSTACK linkstack)
  116. {
  117.     if(linkstack.top == linkstack.base)
  118.         return 1;
  119.     else
  120.         return 2;
  121. }

  123. /*功能；初始化链栈，即创建空表头（空表头不是栈顶元素）*/
  124. int InitSatck(LINKSTACK * linkstack)
  125. {
  126.     linkstack->base = (StackNodePtr)malloc(sizeof(STACKNODE));
  127.     if(linkstack->base == NULL)
  128.     {
  129.         printf("InitSatck malloc err!\n");
  130.         exit(-1);
  131.     }
  132.     linkstack->top = linkstack->base; /*栈顶指针始终指向空头节点*/
  133.     memset(linkstack->base->string, 0 , sizeof(STRING)); /*空头*/
  134.     linkstack->base->next = NULL;
  135.     
  136.     return 0;
  137. }

  139. /*功能：创建一个栈节点*/
  140. int CreatStackNode(StackNodePtr * stacknodeptr, STRING string)
  141. {
  142.     *stacknodeptr = (StackNodePtr)malloc(sizeof(STACKNODE));
  143.     if(*stacknodeptr == NULL)
  144.     {
  145.         printf("CreatStackNode malloc失败\n");
  146.         exit(-1);
  147.     }
  148.     memset((*stacknodeptr)->string, 0 , sizeof(STRING));
  149.     strcpy((*stacknodeptr)->string, string);
  150.     (*stacknodeptr)->next = NULL;
  151.     return 0;
  152. }

  154. /*功能：求链栈中元素的个数*/
  155. int StackLen(LINKSTACK linkstack)
  156. {
  157.     int len = 0;
  158.     StackNodePtr p = NULL;
  159.     p = linkstack.top;
  160.     if(p == NULL)
  161.     {
  162.         //printf("链式栈不存在，或者已经销毁！\n");
  163.         return len;
  164.     }
  165.     while(p->next != NULL)
  166.     {
  167.         len++;
  168.         p = p->next;
  169.     }
  170.     return len;
  171. }

  173. /*功能：入栈操作：从栈顶加入元素*/
  174. int Push(LINKSTACK * linkstack, STRING string)
  175. {
  176.     StackNodePtr stacknodeptr = NULL;
  177.     CreatStackNode(&stacknodeptr, string);
  178.     
  179.     /*新插入的栈节点，在空表头之后，作为新的栈顶元素*/
  180.     if(StackIsEmpty(*linkstack) == 1) /*空栈*/
  181.     {
  182.         linkstack->base = stacknodeptr;
  183.     }

  185.     stacknodeptr->next = linkstack->top->next; /*新元素连接到第一个元素之后*/
  186.     linkstack->top->next = stacknodeptr; /*空头指向新连接的元素*/
  187.     
  188.     printf("入栈一个元素=[%s],链栈中元素个数=[%d]\n", stacknodeptr->string, StackLen(*linkstack));
  189.     
  190.     return 0;
  191. }

  193. /*功能：出栈操作:栈顶元素删除*/
  194. int Pop(LINKSTACK * linkstack, STRING string)
  195. {
  196.     if(StackIsEmpty(*linkstack) == 1) /*空栈*/
  197.     {
  198.         printf("栈为空，无元素可出栈！\n");
  199.         return -1;
  200.     }
  201.     /*将栈顶元素出栈，栈顶元素即是空表头之后的第一个节点元素*/
  202.     StackNodePtr stempnodeptr = linkstack->top->next; /*指向第一个节点元素*/
  203.     if(linkstack->top->next == linkstack->base) /*当栈中只有一个栈底元素时*/
  204.     {
  205.         linkstack->base = linkstack->top;
  206.     }
  207.     linkstack->top->next = linkstack->top->next->next;
  208.     
  209.     strcpy(string, stempnodeptr->string);
  210.     printf("出栈一个元素=[%s],链栈中剩余元素个数=[%d]\n", stempnodeptr->string, StackLen(*linkstack));
  211.     free(stempnodeptr);
  212.     stempnodeptr == NULL;
  213.     
  214.     return 0;
  215. }

  217. /*功能：打印栈中所有元素*/
  218. int PrintSatck(LINKSTACK linkstack)
  219. {
  220.     int num = 0;
  221.     
  222.     if(StackIsEmpty(linkstack) == 1) /*空栈*/
  223.     {
  224.         printf("栈为空，无需打印！\n");
  225.         return 1;
  226.     }
  227.     printf("链式栈中元素个数=[%d]\n", StackLen(linkstack));
  228.     
  229.     StackNodePtr p = NULL;
  230.     p = linkstack.top;
  231.     printf("从链表头，即栈顶开始：\n");
  232.     while(p->next != NULL)
  233.     {
  234.         num++;
  235.         p = p->next;
  236.         printf("(第%02d个元素)=[%s]\n", num, p->string);    
  237.     }

  239.     return 0;
  240. }

  242. /*功能：取得栈顶元素*/
  243. int GetStackHead(LINKSTACK linkstack, STRING string)
  244. {
  245.     if(linkstack.top == linkstack.base)
  246.     {
  247.         printf("栈为空，无栈顶元素可取！\n");
  248.         return -1;
  249.     }
  250.     strcpy(string, linkstack.top->next->string);
  251.     
  252.     return 0;
  253. }

  255. /*功能：销毁栈链表*/
  256. int DestroyStack(LINKSTACK * linkstack)
  257. {
  258.     StackNodePtr p = NULL;
  259.     StackNodePtr q = NULL;
  260.     p = linkstack->top;
  261.     q = linkstack->top;
  262.     if(p == NULL)
  263.     {
  264.         printf("链式队列不存在，或者已经销毁！\n");
  265.         return 0;
  266.     }
  267.     while(q->next != NULL)
  268.     {
  269.         p = q->next;
  270.         free(q);
  271.         q = p;
  272.     }
  273.     free(p);
  274.     p = NULL;
  275.     q = NULL;
  276.     linkstack->top = NULL;
  277.     linkstack->base = NULL;
  278.     
  279.     printf("链式栈已销毁！\n");
  280.     
  281.     return 0;
  282. }

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

上一篇：顺序队列

下一篇：顺序栈

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

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

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

16024965号-6