您现在的位置： Linux教程網 >> UnixLinux > >> Linux編程 >> Linux編程

棧鏈的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)

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\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 ;
}

Linux編程