栈链的C语言实现

出栈与入栈是栈的最主要操作，当无法预见栈所需大小时，需要采用栈链的方式。一、栈链结点在栈链中，不需要像单链表一样需要头结点。栈链的结构如下图所示根据该结构，用C语言定义为：typedef char SElemTypetypedef 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）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--;四、测试程序#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 ",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（"栈链内容为： "）;
PrintStackLink（&myStack）; //出栈
while（！StackEmpty（&myStack））
{
Pop（&myStack,&outch）;
printf（"弹出内容为：%c ",outch）;
}
PrintStackLink（&myStack）;
while（1）;
return ;
}相关阅读：C语言变长数组之剖析 http://www.linuxidc.com/Linux/2013-07/86997.htmC语言需要注意的问题 http://www.linuxidc.com/Linux/2013-05/84301.htmC语言位域的使用及其注意点 http://www.linuxidc.com/Linux/2013-07/87027.htm