栈链的C语言实现

出栈与入栈是栈的最主要操作,当无法预见栈所需大小时,需要采用栈链的方式。

一、栈链结点

在栈链中,不需要像单链表一样需要头结点。栈链的结构如下图所示

栈链的C语言实现

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

typedef char SElemType

typedef struct StackNode

{

SElemType data;//根据实际需要定义数据类型

struct StackNode *next;

}StackNode,*LinkStackPtr;

typedef struct LinkStack

{

LinkStackPtr top;//指向栈链顶部

int count;//用以判断是否栈为空,可初始化为0

}LinkStack;

二、进栈操作

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

int Push(LinkStack *pS,SElemType e)

栈链的C语言实现

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,是为了在函数结束后可以取得该弹出元素

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

栈链的C语言实现

出栈过程:

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

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

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

Step4:更改栈状态

pS->count--;

四、测试程序

#include <stdio.h>
#include <stdlib.h>

typedef char SElemType ;

typedef struct StackNode
{
 SElemType data;
 struct StackNode *next;
}StackNode,*LinkStackPtr;

typedef struct LinkStack
{
 LinkStackPtr top;
 int count;
}LinkStack;

//栈指针初始化
void InitialStack(LinkStack *L)
{
 L->top=NULL;
 L->count=0;
 return;
}
//栈状态
int StackEmpty(LinkStack *pS)
{
 if(!pS->count)//若为空,则返回1
  return 1;
 else
  return 0;//若非空,则返回0;
}
//压栈操作
int Push(LinkStack *pS,SElemType e)
{
 //一般情况下,不存在栈满情况
 LinkStackPtr s=(LinkStackPtr)malloc(sizeof(StackNode));
 s->data = e;
 s->next = pS->top;

 pS->top=s;
 pS->count++;
 return 0;
}

//出栈操作
int Pop(LinkStack *pS,SElemType *e)
{
 LinkStackPtr p;
 if(StackEmpty(pS))
  {
   printf("栈为空!");
      return 0;
    }

 *e=pS->top->data;

 p = pS->top;
 pS->top = p->next;
 free(p);
 pS->count--;
 return 0;
}
//打印栈链
void PrintStackLink(LinkStack *pS)
{
 LinkStackPtr L;
 int i;
 //i = pS->count;
 L = pS->top;
 if(pS->count == 0)
 {
  printf("栈为空!");
  return;

 }
 for(i=0;i<(pS->count);i++)
 {
  printf("%c\n",L->data);
    L = L->next;
 }
 return ;
}
void main()
{
 //测试
 char getch;
 char outch;
 LinkStack myStack;
 InitialStack(&myStack);
 //压栈
 printf("请输入压入栈的数据(char型),输入#结束");
 scanf("%c",&getch);
 while(getch!='#')
 {
  Push(&myStack,getch);
  scanf("%c",&getch);
 }
 printf("栈链内容为:\n");
 PrintStackLink(&myStack);

 //出栈
 while(!StackEmpty(&myStack))
 {
  Pop(&myStack,&outch);
  printf("弹出内容为:%c\n",outch);
 }
 PrintStackLink(&myStack);
 while(1);
 return ;
}

相关阅读:

相关推荐