Chinaunix首页 | 论坛 | 博客
  • 博客访问: 3233661
  • 博文数量: 367
  • 博客积分: 9916
  • 博客等级: 中将
  • 技术积分: 7199
  • 用 户 组: 普通用户
  • 注册时间: 2011-05-29 23:27
个人简介

简单!

文章分类

全部博文(367)

文章存档

2013年(51)

2012年(269)

2011年(47)

分类: C/C++

2013-07-15 11:34:40

栈(Stack)是限制在表的一端进行插入和删除运算的线性表。通常称插入、删除的这一端为栈顶(Top),另一端称为栈底(Bottom)。当表中没有元素时称为空栈。栈为后进先出(Last In First Out)的线性表,简称为LIFO表。栈的修改是按后进先出的原则进行。每次删除(退栈)的总是当前栈中"最新"的元素,即最后插入(进栈)的元素,而最先插入的是被放在栈的底部,要到最后才能删除。


一、栈链结点

出栈与入栈是栈的最主要操作,当无法预见栈所需大小时,需要采用链的方式。在链中,不需要像单链表一样需要头结点。链的结构如下图所示:

根据该结构,用C语言定义为:

  1. typedef char SElemType

  2. typedef struct StackNode
  3. {
  4.     SElemType data;//根据实际需要定义数据类型
  5.     struct StackNode *next;
  6. }StackNode,*LinkStackPtr;

  7. typedef struct LinkStack
  8. {
  9.     LinkStackPtr top;//指向栈链顶部
  10.     int count;//用以判断栈是否为空,可初始化为0
  11. }LinkStack;


二、进栈

能够进栈的前提是已成功建立栈空间,即成功调用malloc函数。进栈操作的过程如下图所示。进栈函数所需的参数主要是指向栈顶的指针和入栈内容,因此可定义为:

int Push(LinkStack *pS,SElemType e)

Step1:开辟内存,将需要入栈的元素压入栈:

LinkStackPtr s=(LinkStackPtr)malloc(sizeof(StackNode));

s->data = e;

Step2:更改指针

(1)新结点的*next指向原来栈顶:s->next = pS->top;

(2)栈链新的top指针指向新建立的结点:pS->top = s;

Step3:更改栈状态(累计入栈元素个数)

pS->count++;

三、出栈

出栈之前需要判断当前栈的状态,如果栈元素个数为零,则显然是空栈,无法进行出栈操作。出栈操作函数同样需要两个参数,一是指向栈链的指针,二是弹出的栈元素,因此定义为:

int Pop(LinkStackPtr *pS,SElemType *e)//之所以是*e,是为了在函数结束后可以取得该弹出元素

出栈操作过程如下图所示:

出栈过程:

Step1:获取弹出元素:*e = pS->top->data;

Step2:top指针指向栈顶:p = pS->top ;pS->top = p->next;//LinkStackPtr p;

Step3:释放结点:free(p);

Step4:更改栈状态

pS->count--;

四、测试程序

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

  4. typedef char SElemType;

  5. typedef struct StackNode {
  6.     SElemType data;
  7.     struct StackNode *next;
  8. } StackNode, *LinkStackPtr;

  9. typedef struct LinkStack {
  10.     LinkStackPtr top;
  11.     int count;
  12. } LinkStack;

  13. void InitialStack(LinkStack * L)
  14. {
  15.     L->top = NULL;
  16.     L->count = 0;
  17.     
  18.     return;
  19. }

  20. int StackEmpty(LinkStack * pS)
  21. {
  22.     return (!pS->count);
  23. }

  24. int Push(LinkStack * pS, SElemType e)
  25. {
  26.     LinkStackPtr s = (LinkStackPtr) malloc(sizeof(StackNode));
  27.     if(s == NULL) {
  28.         printf("no enough memory!\n");
  29.         return -1;
  30.     }
  31.     s->data = e;
  32.     s->next = pS->top;
  33.     pS->top = s;
  34.     pS->count++;
  35.     
  36.     return 0;
  37. }

  38. int Pop(LinkStack * pS, SElemType * e)
  39. {
  40.     LinkStackPtr p = NULL;
  41.     
  42.     if (StackEmpty(pS)) {
  43.         printf("stack is empty!\n");
  44.         return 0;
  45.     }

  46.     *e = pS->top->data;
  47.     p = pS->top;
  48.     pS->top = p->next;
  49.     free(p);
  50.     pS->count--;
  51.     
  52.     return 0;
  53. }

  54. void PrintStackLink(LinkStack * pS)
  55. {
  56.     int i;
  57.     LinkStackPtr L = NULL;
  58.     
  59.     L = pS->top;
  60.     if (StackEmpty(pS)) {
  61.         printf("stack is empty!\n");
  62.         return;
  63.     }

  64.     for (i = 0; i < (pS->count); i++) {
  65.         printf("%c\n", L->data);
  66.         L = L->next;
  67.     }
  68.     
  69.     return;
  70. }

  71. int main(int argc, char **argv)
  72. {
  73.     char getch;
  74.     char outch;
  75.     LinkStack myStack;
  76.     
  77.     InitialStack(&myStack);
  78.     
  79.     printf("请输入压入栈的数据(char型),输入#结束:\n");
  80.     scanf("%c", &getch);
  81.     while (getch != '#') {
  82.         Push(&myStack, getch);
  83.         scanf("%c", &getch);
  84.     }
  85.     printf("栈链内容为:\n");
  86.     PrintStackLink(&myStack);

  87.     while (!StackEmpty(&myStack)) {
  88.         Pop(&myStack, &outch);
  89.         printf("弹出内容为:%c\n", outch);
  90.     }
  91.     PrintStackLink(&myStack);

  92.     return 0;
  93. }
阅读(1337) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~
评论热议
请登录后评论。

登录 注册