C语言实现链式栈(不带头结点)
文章目录
前言
继上一篇文章C语言实现顺序栈实现顺序栈之后，这次来实现一下链式栈。由于栈的特性是只在一端进行操作，所以我认为使用不带头结点的方式实现会比较简单，并且不浪费头结点这个空间。
实现的功能
- 初始化栈
- 入栈
- 出栈
- 获取栈顶元素
主界面截图
栈的定义
每个结点需要有数据域和指针域。我定义了一个全局变量length来查看栈中的元素个数。
typedef int ElemType;//给数据类型取别名,此次存的是int类型，如果要存为其他类型只需要修改此处一次
int length = 0;//定义一个全局变量表示栈中实际存储的元素个数
//-------结构体定义部分------ //
typedef struct mystack{
ElemType data; //数据域
struct mystack *next;//指向栈顶元素的指针
}MyStack;
//-------结构体定义部分------ //
栈的初始化
由于采用不带头结点的方式，初始化时只需要将头结点的指针置空。
//栈的初始化(不带头结点)
bool InitStack(MyStack *S)
{
S->next = NULL;//先把指针域置空
return true;
}
入栈
元素入栈时需要区分两种情况：
① 入栈前栈为空，即要将第一个元素入栈，此时只需要新申请一个结点保存入栈的元素，然后把头指针指向这个新结点(S->next = p)，并且让这个结点的指针指向NULL(p->next = NULL)。
② 入栈时栈中已有元素，这时同样需要新申请结点保存新入栈的元素，并且需要先将新结点的指针指向原来头指针指向的结点(p->next = S->next)，然后再让头指针指向新结点(S->next = p)。
//入栈
bool Push(MyStack *S,ElemType e)
{
length++;//栈中元素个数+1
//1.申请一个内存空间保存新结点
MyStack *p = (MyStack *)malloc(sizeof(MyStack));
//2.把值放入结点的数据域
p->data = e;
//对第一个入栈的元素做特殊处理
if(length==1)
{
S->next = p;
p->next = NULL;
}
else
{
p->next = S->next;
S->next = p;
}
return true;
}
出栈
出栈时需要判断栈是否为空。出栈只需要将头指针指向栈顶元素的下一个元素即可。
//出栈
bool Pop(MyStack *S)
{
if(S->next==NULL)
return false;
MyStack *q = S->next;
S->next = q->next;
length--;//栈中元素个数-1
return true;
}
获取栈顶元素
获取栈顶元素同样需要判断栈是否为空。如果不为空，则头指针指向的元素即为栈顶元素。
//获取当前栈顶元素
bool GetTop(MyStack *S,int *x)
{
if(S->next==NULL)//如果栈空
return false;
else
*x = (S->next)->data;
return true;
}
获取栈长
获取栈长我这里直接打印结果，当然也可以用一个值返回。
//获取栈长
bool GetLen(MyStack *S)
{
printf("当前栈中元素的个数为:%d\n",length);
return true;
}
全部代码
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h> //根据C99标准,C语言使用bool类型需要添加这个头文件
typedef int ElemType;//给数据类型取别名,此次存的是int类型，如果要存为其他类型只需要修改此处一次
int length = 0;//定义一个全局变量表示栈中实际存储的元素个数
//-------结构体定义部分------ //
typedef struct mystack{
ElemType data; //数据域
struct mystack *next;//指向栈顶元素的指针
}MyStack;
//-------结构体定义部分------ //
//-------函数声明部分------ //
void MainMenu();
bool InitStack(MyStack *S);//栈的初始化
bool Push(MyStack *S,ElemType e);//将元素e压入栈
bool Pop(MyStack *S);//出栈
bool GetTop(MyStack *S,int *x);//获取当前栈顶元素
bool GetLen(MyStack *S);//获取栈长，并且直接打印在屏幕上
//-------函数声明部分------ //
int main()
{
int ch;//选择操作指令
int element;//入栈的元素
int x;//获取出栈的元素
MyStack S;
InitStack(&S);//初始化一个栈
while(1)
{
MainMenu();
printf("请输入您要执行的操作:");
scanf("%d",&ch);
switch(ch)
{
case 0: printf("感谢使用，已退出！"); exit(0); break;
case 1: printf("请输入您要入栈的元素:\n");
scanf("%d",&element);
if(Push(&S,element))
printf("入栈成功！\n");
else
printf("入栈失败！栈已满！\n");
break;
case 2:
if(Pop(&S))
printf("出栈成功！\n");
else
printf("出栈失败！栈已空！\n");
break;
case 3:
if(GetTop(&S,&x))
printf("获取栈顶成功！当前栈顶元素为:%d\n",x);
else
printf("获取栈顶失败！栈已空！\n");
break;
case 4: GetLen(&S); break;
default: printf("您输入的操作指令有误！请重新输入！");
}
}
return 0;
}
//主菜单，显示
void MainMenu()
{
printf("\n\n\n");
printf("\t *************链式栈的实现************\n\n");
printf("\t ------- 0.退出 \n\n");
printf("\t ------- 1.将数据入栈\n\n");
printf("\t ------- 2.执行一次出栈操作\n\n");
printf("\t ------- 3.获取当前栈顶元素\n\n");
printf("\t ------- 4.输出栈中元素的个数\n\n");
printf("\t *************************************\n");
}
//栈的初始化(不带头结点)
bool InitStack(MyStack *S)
{
S->next = NULL;//先把指针域置空
return true;
}
//入栈
bool Push(MyStack *S,ElemType e)
{
length++;//栈中元素个数+1
//1.申请一个内存空间保存新结点
MyStack *p = (MyStack *)malloc(sizeof(MyStack));
//2.把值放入结点的数据域
p->data = e;
//对第一个入栈的元素做特殊处理
if(length==1)
{
S->next = p;
p->next = NULL;
}
else
{
p->next = S->next;
S->next = p;
}
return true;
}
//出栈
bool Pop(MyStack *S)
{
if(S->next==NULL)
return false;
MyStack *q = S->next;
S->next = q->next;
length--;//栈中元素个数-1
return true;
}
//获取当前栈顶元素
bool GetTop(MyStack *S,int *x)
{
if(S->next==NULL)//如果栈空
return false;
else
*x = (S->next)->data;
return true;
}
//获取栈长
bool GetLen(MyStack *S)
{
printf("当前栈中元素的个数为:%d\n",length);
return true;
}