零零总总搜索了一些关于链栈的资料,了解了链栈的基本操作,一直觉得别人写的代码或多或少存在一些问题,所以打算自己写一篇关于链栈的文章,也算是对所学知识的梳理和巩固了。
首先说明本文使用C语言进行链栈的基本操作,链栈是无头结点的。这里补充说明一下,无头结点的意思是,链栈的头结点是存储数据的,有头结点的是头结点不存储数据的,不了解的小伙伴可以先去学习一下单链表的内容。
之所以在这里说明,是因为我看过不少文章写的链栈是带头结点,有的还分不清到底有没有头结点,导致我在学习的时候浪费了不少时间,废话不多说,以下进入正题。
链栈的基本操作包括以下几点:
a. 栈的初始化
b. 栈的判空
c. 入栈
d. 出栈
e. 读栈顶元素
f. 遍历栈
g. 销毁栈
定义一个结构体,用来构造链栈。
typedef struct StackNode{
int data;//数据域,用来存放数据
StackNode *next;//指针域,用来指向栈顶的下一个元素
}LinkStack;
LinkStack *LS;//定义一个LinkStack类型的指针
一、初始化栈
链栈初始化首先要构造一个空栈,先创建一个头结点,然后让该头结点的指针指向空,这里使用传参的方式初始化栈。
void StackInit(LinkStack* &S)//这里传入的参数是一个指针
{ //要对传入的参数进行赋值操作,需要加一个取址符
S = NULL;//直接让S指向空,不能在这里像下面注释的代码一样分配空间,否则无法完成判空操作
/*S = (LinkStack *)malloc(sizeof(LinkStack *));
if(S == NULL)
{
printf("Malloc Error!!!\n");
return false;
}
S->next = NULL;
return true;*/
}
二、栈的判空
直接判断栈顶的地址是否为空
bool StackIsEmpty(LinkStack* S)
{
if(S == NULL)
return true;
return false;
}
三、入栈
入栈需要判断是否为空,若为空栈,第一个入栈元素为栈顶,没有下一元素,指向下一个元素的指针为空。
bool Stack_Push(LinkStack* &S,int PushData)
{
if(S == NULL)//若栈为空
{
S = (LinkStack *)malloc(sizeof(LinkStack));
if(S == NULL)
{
printf("Malloc Error!!!\n");
return false;
}
S->data = PushData;//给头结点赋值
S->next = NULL;//没有下一个元素,指向空
return true;
}
//栈不为空
LinkStack *NewNode = (LinkStack)malloc(sizeof(LinkStack));
if(NewNode == NULL)
{
printf("Malloc Error!!!\n");
return false;
}
NewNode->data = S->data;//用新节点存储当前栈顶元素,包括指针
NewNode->next = S->next;//让NewNode成为当前栈顶
S->next = NewNode;//S的下一个元素为NewNode,S成为新的栈顶(S仍为栈顶)
S->data = PushData;//记录入栈元素
return true;
}
四、出栈
出栈即为删除栈顶
bool Stack_Pop(LinkStack* &S,int &PopData)//PopData用于记录出栈元素
{
if(S == NULL)//栈为空
{
printf("Stack Is Empty!!!\n");
return false;
}
if(S->next == NULL)//最后一个元素
{
PopData = S->data;
free(S);//释放空间
S = NULL;//防止成为野指针
return true;
}
PopData = S->data;//通过PopData获取出栈(栈顶)数据
/* 此处为写错部分的代码
LinkStack *TempNode = S->next;//出栈需要释放栈顶,需要定义一个临时变量
S->next = TempNode->next;//栈顶元素出栈,下一个元素成为新的栈顶
S->data = TempNode->data;
*/
LinkStack *TempNode = S;//出栈需要释放栈顶,需要定义一个临时变量,存放旧栈顶的地址和指针域
//此时TempNode为栈顶,其指向的下一个栈元素应为新的栈顶
S = TempNode->next;//栈顶元素出栈,下一个元素成为新的栈顶
S->data = TempNode->next->data;
free(TempNode);//释放旧栈顶空间
TempNode = NULL;//防止成为野指针
return true;
}
五、读取栈顶元素
读取栈顶元素不同于出栈,只需要读取栈顶元素,不需要释放栈顶空间
bool Stack_Read(LinkStack* S,int &PopData)//PopData用于记录出栈元素
{
if(S == NULL)//栈为空,没有元素可读,返回false
{
printf("Stack Is Empty!!!\n");
return false;
}
PopData = S->data;
return;
}
六、遍历栈
这里直接打印栈的所有元素,从栈顶到栈底
//遍历栈
void Stack_Traverse(LinkStack* S)
{
if(S == NULL)//栈为空
{
printf("Stack Is Empty!!!\n");
return;
}
if(S->next == NULL)//只有一个元素
{
printf("StackTop to StackBottom: %d\n",S->data);
return;
}
LinkStack *p,*q;
p = S;//p为q是上一个元素
q = p->next;//q为p的下一个元素
printf("StackTop to StackBottom: ");
while(q->next != NULL)
{
printf("%d ",p->data);
p = p->next;
q = p->next;
}
printf("%d %d\n",p->data,q->data);
}
七、销毁栈
void Stack_Destroy(LinkStack* &S)
{
LinkStack *p = NULL;
while(S != NULL)
{
P = S;
S = S->next;
free(p);
}
p = NULL;
S = NULL;
}
需要注意的是,在释放栈空间之后,需要将相应的指针指向空,否则将会成为野指针,并且书写也不规范。学习数据结构的过程中我查阅了许多资料,发现许多博客的代码存在这样的问题,这让有那么一点强迫症的我看的很不舒服,所以就打算自己写。文章来源:https://www.toymoban.com/news/detail-450129.html
本文是我第一次写、第一次发表的文章,内容很少,也很简洁,代码完全是在网页敲出来,就看着伪代码敲,有什么不对的请给位看官批评指正,谢谢!文章来源地址https://www.toymoban.com/news/detail-450129.html
到了这里,关于【数据结构】链栈的基本操作(C语言)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!