链栈基本操作.doc

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

#define OK 0
#define ERROR 1
int MAX_SIZE = 20;

// 顺序栈的表示方法
typedef struct {
int* pData; // top=-1表示栈为空, top范围-1~MAX_SIZE
int top; //top=MAX_SIZE-1表示栈满
}SeqStack;

SeqStack* InitList(SeqStack* L)
{
if (NULL==L)
{
L=(SeqStack*)malloc(sizeof(SeqStack)); //为L开辟空间
}

if (!L)
{
printf("初始化失败！\n"); //开辟失败输出的提示
return NULL;
}

L->pData=(int*)malloc(MAX_SIZE*sizeof(int)); //为栈开辟空间
if(!L->pData)
{
free(L); //如果开辟失败释放L的空间
printf("初始化失败！\n");
return NULL;
}
L->top=-1; //栈为空
return L;
}

// 顺序栈的销毁
int DestroyList(SeqStack* L)
{
if(L->pData)
{
free(L->pData); //释放栈的空间
L->pData=NULL;
}
L->top=-1; //栈置空
return 1;
}

// 获取栈顶元素
int GetTop(SeqStack* L)
{
if(-1==L->top)
{
printf("栈已空!\n"); //如果L->pData等于-1则栈是空的
exit(1);
}
return L->pData[L->top]; //返回栈顶元素
}

// 出栈操作
int Pop(SeqStack* L)
{
if(-1==L->top)
{
printf("栈已空!\n"); //如果L->pData等于-1则栈是空的
exit(1);
}
return L->pData[L->top--]; //返回栈顶元素，栈顶减1
}

// 入栈操作
int Push(SeqStack *L, int x)
{
if(!L->pData || L->top>=MAX_SIZE-1)
{
printf("顺序栈不存在或是栈已满, 不能插入!"); //如果栈顶等于栈元素最大个数，则栈已满
return ERROR;
}
L->top++; //栈顶加1
*(L->pData+L->top)=x; //要入栈的元素放入栈顶
return OK;
}

// 输出某个数据
void PrintDataType(int x)
{
printf("%d", x); //输出传过来的元素
printf("\n");
}

// 输出顺序栈中的每个元素
void PrintList(SeqStack* L)
{
int k=0;
if(!L->pData)
{
printf("顺序栈不存在!\n"); //如果L->pData为0，则栈不存在
return;
}
if(-1==L->top)
{
printf("顺序栈是空的!\n"); //如果栈顶为-1 ，则栈为空
return;
}
printf("栈中的元素有:\n");
for(k=0; k<=L->top; k++)
{
PrintDataType(L->pData[k]); //调用PrintDataType()函数，输出栈中的的值
}
}

// 置空栈
int SetEmpty(SeqStack* L)
{
if(!L->pData)
{
return ERROR;
}
L->top=-1; //站定赋值-1，栈置空
return OK;
}

// 求栈中元素个数
int GetCnt(SeqStack* L)
{
if(L->pData)
{
return L->top+1;
}
return -1; // 顺序栈没有分配内存时, 返回-1
}

// 判断是否为空: 1为空, 0为非空
int IsEmpty(SeqStack* L)
{
if(!L->pData)
{
printf("顺序栈不存在!\n");
}
return -1==L->top;
}

// 判断是否为满: 1为满, 0为不满
int IsFull(SeqStack* L)
{
if(!L->pData)
{
printf("顺序栈不存在!\n");
}
return MAX_SIZE==L->top+1;
}

void main()
{
SeqStack* L=NULL;
L=InitList(L); // 初始化顺序栈
PrintList(L); // 打印顺序栈
printf("插入三个元素后");
Push(L, 10); // 把元素10入栈
Push(L, 12); // 把元素12入栈
Push(L, 14); // 把元素14入栈

PrintList(L); // 打印顺序栈
printf("栈顶元素为:");
PrintDataType(GetTop(L));
printf("岀栈元素为:");
PrintDataType(Pop(L));
PrintList(L); // 打印顺序栈
printf("栈顶元素为:");
PrintDataType(GetTop(L));

if(IsEmpty(L)){
printf("顺序栈是空的\n");
}else{
printf("顺序栈是非空的\n");
}
printf("置空栈后");
SetEmpty(L); // 把顺序栈置空

PrintList(L); // 打印顺序栈
DestroyList(L); // 不要忘了
printf("栈已销毁！\n");
PrintList(L); // 打印顺序栈
if (NULL!=L)
free(L);
}

- 6 -