栈的线性储存结构与链式储存结构的实现（C语言）。

「爱情、让人受尽委屈。」 2022-01-14 16:59 169阅读 0赞

[2019独角兽企业重金招聘Python工程师标准>>> ][2019_Python_] ![hot3.png][]

顺序栈，即栈的储存结构是利用地址连续的一组储存单元依次存放栈顶到栈底的数据元素.

栈的结构：代码如下

#include<stdio.h>
    #include<stdlib.h>
    #define STACK_INIT_SIZE 100/*储存空间初始分配量*/
    #define STACKINCREMENT 10/*储存空间分配增量*/
    typedef int ElemType;
    typedef int Status;
    /*-----------------栈的顺序储存表示--------------------------*/
    typedef struct {
     ElemType *base;/*在栈构造之前和销毁之后base的值为NULL*/
     ElemType *top; /*栈顶指针*/
     int stacksize; /*当前以分配的空间，以元素为单位*/
    }SqStack;

构造一个空栈，先为栈分配初始大小，base指向分配空间，并令base==top。用stacksize来储存目前已经分配的空间，以元素的个数为单位。代码如下：

Status InitStack(SqStack *S){/*构造一个空栈*/
     S->base=(ElemType *)malloc(STACK_INIT_SIZE*sizeof(ElemType));
     if(!S->base)exit(0);//储存分配失败
     S->top=S->base;
     S->stacksize=STACK_INIT_SIZE;
     return 1;
    }

取出元素，即为出栈，首先检测栈是否为空，如果不是取出栈顶元素，栈顶指针向前移位。即向靠近栈底的一方移位。代码如下：

Status GetTop(SqStack *S,ElemType *e)
    {/*如果栈不为空，返回栈顶元素*/
     if(S->base==S->top)return 0;
     else
     {
      S->top--;
      *e=*(S->top+1);
      return 1;
     }
    }

存入元素即为压栈。首先检测是否有储存空间：如果没有则分配。代码如下：

Status Push(SqStack *S,ElemType *e)
    {/*插入元素e为新的栈顶元素*/
     if(S->top-S->base>=S->stacksize){//栈满，追加空间
      S->base=(ElemType *)realloc(S->base,(S->stacksize+STACKINCREMENT)*sizeof(ElemType));
      if(!S->base)exit(0);
      S->top=S->base+S->stacksize; 
      S->stacksize+=STACKINCREMENT;
     }
     S->top++;
     *S->top=*e;
     return 1;
    }

ealloc,malloc,calloc的区别

三个函数的申明分别是:  
void\* realloc(void\* ptr, unsigned newsize);  
void\* malloc(unsigned size);  
void\* calloc(size\_t numElements, size\_t sizeOfElement);  
都在stdlib.h函数库内  
它们的返回值都是请求系统分配的地址,如果请求失败就返回NULL

malloc用于申请一段新的地址,参数size为需要内存空间的长度,如:  
char\* p;  
p=(char\*)malloc(20);

calloc与malloc相似,参数sizeOfElement为申请地址的单位元素长度,numElements为元素个数,如:  
char\* p;  
p=(char\*)calloc(20,sizeof(char));

测试函数：

void main()
    {
     int z,i;
     SqStack S;
     InitStack(&S);/*初始化栈*/
     printf("压栈，存入数据1,2,3,4,5:\n");
     for(i=1;i<=5;i++)
     {
      Push(&S,&i);
     }
     printf("出栈，取出前两个:");
     for(i=1;i<=2;i++)
     {
      GetTop(&S,&z);
      printf("%d\t",z);
     }
     printf("\n");
     printf("压栈，存入数据11,12,13:\n");
     for(i=11;i<=13;i++)
     {
      Push(&S,&i);
     }
      printf("出栈，取出前四个:\n");
     for(i=1;i<=4;i++)
     {
      GetTop(&S,&z);
      printf("%d\t",z);
     }
      system("pause");
    }

运行结果如下：

![195838\_4mIJ\_2537692.png][195838_4mIJ_2537692.png]

\-----------------------------------------------------------------------------------------------------------------------------

栈的链式储存结构：

#include<stdio.h>
    #include<stdlib.h>
    typedef int Elemtype;
    typedef int Status;
    typedef struct Snode
    {
     Elemtype data;  /*数据域*/
     struct Snode *next; /*指针域*/
    }Snode,*LinkStack;

假设S是linkStack型的变量，s为链栈的头指针，并且始终指向链顶，即线性表的第一个元素。压栈入栈等操作代码如下：

void Init_StackL(LinkStack *S)
    {
     *S=NULL;
    }
    Status Push_L(LinkStack *S,Elemtype x)   /*将元素x插入到栈顶位置*/
    {
     LinkStack p;
     p=(LinkStack)malloc(sizeof(Snode));  /*新节点生成*/
     p->data=x;         /*向新节点赋值*/
     p->next=*S;         /*向栈顶插入新结点*/
     *S=p;
     return 1;
    }
    Status  Pop_L(LinkStack *S,Elemtype *temp_) /*删除链栈的顶元素*/
    {
     LinkStack p;
     Elemtype temp;
     if(*S==NULL) return 0;      /*对于空栈则退出*/
     temp=(*S)->data;       /*暂存栈顶元素值，以便返回*/
     p=*S;           /*使栈顶指向下一结点*/
     *S=p->next;
     free(p);          /*释放栈顶元素*/
     *temp_=temp;
     return 1;
    }

测试函数如下，与线性栈的测试数据相同，代码如下：

void main()
    {
     int i,z;
     LinkStack S;
     Init_StackL(&S);
     printf("压栈，存入数据1,2,3,4,5:\n");
     for(i=1;i<=5;i++)
     {
      Push_L(&S,i);
     }
     printf("出栈，取出前两个:");
     for(i=1;i<=2;i++)
     {
      Pop_L(&S,&z);
      printf("%d\t",z);
     }
     printf("\n");
     printf("压栈，存入数据11,12,13:\n");
     for(i=11;i<=13;i++)
     {
      Push_L(&S,i);
     }
      printf("出栈，取出前四个:\n");
     for(i=1;i<=4;i++)
     {
      Pop_L(&S,&z);
      printf("%d\t",z);
     }
      system("pause");
    }

测试结果与线性栈的结果相同，如上图测试结果。

\------------------------------------------华丽分割线----------------------------------------------------------

学习数据结果记录，栈的计数遍历等操作思路与线性表相同。如有错误欢迎指正。

转载于:https://my.oschina.net/wang520/blog/648209

[2019_Python_]: https://my.oschina.net/u/2663968/blog/3061697
[hot3.png]: /images/20220114/39c3871d0631465fa8853292903b0b67.png
[195838_4mIJ_2537692.png]: /images/20220114/a0a9062f92c54b39a52ade8fe3a6d059.png