当前位置:网站首页>2.(1)栈的链式存储、链栈的操作(图解、注释、代码)
2.(1)栈的链式存储、链栈的操作(图解、注释、代码)
2022-07-31 05:26:00 【爱打羽毛球的程序员】
本人坚持更新C语言和数据结构知识,可以收藏+关注随时了解
目录
1.结构体定义
栈的链式存储主要是用到了两个结构体
一个结构体存放栈顶指针和栈底指针
之所以这样,是因为栈属于一个操作受限的线性表,对栈的操作只能在栈顶执行
一个结构体是存放结点
结点包括数据域和指针域,类似于链表
typedef struct Node //结点
{
int data;
struct Node *pNext;
} Node, *PNODE;
// Node<=>struct Node
// PNODE <=>struct Node *
typedef struct Stack //存放栈顶指针和栈底指针
{
PNODE pTop; // pTop指向的数据类型为struct Node
PNODE pBottom;
} STACK, *PSTACK;
//Stack<=>struct Stack
//PSTACK<=>struct Stack*
2.初始化一个链栈
2.1图解过程
(1)我们创建存放栈顶栈底指针的结构体(也就是栈的结构体),并动态创建一个结点,作为栈底,栈底的指针域为空
(2)初始状态下,栈顶指针(S.top)和栈底指针(S.bottom)都指向栈底
2.2代码
void initStack(PSTACK pS)
{
pS->pTop = (PNODE)malloc(sizeof(Node)); //动态生成一个结点,使得pTop指针指向它,pTop保存这个结点第一个字节的地址
if (NULL == pS->pTop)
{
printf("dynamic memory is failed to allocate,procedure is over!\n");
exit(-1);
}
else
{
pS->pBottom = pS->pTop; //让pBottom和pTop指向同一个结点
pS->pBottom->pNext = NULL; // pS->pTop->pNext = NULL;令栈底的指针域为空
}
}
3.压栈
栈的操作只能在栈顶进行,所以重点是移动栈顶指针的位置,让S.Ptop指向栈顶元素
3.1图解过程
(1)动态生成一个结点pNew
(2)pNew指向栈底,栈顶指针指向pNew
(3)以此类推
3.2代码
void pushStack(PSTACK pS, int val)
{
PNODE pNew = (PNODE)malloc(sizeof(Node));
pNew->data = val;
pNew->pNext = pS->pTop; // pS->pTop不能改成pS->pBottom
pS->pTop = pNew; // pTop指向pNew
}
4.出栈
4.1.图解过程
出栈是压栈的逆过程,只需要将S.pTop指针下移,然后释放被删除节点的内存就可以
4.2代码
/把pS所指向的栈出栈一次,并把出栈的元素存入pVal形参所指向的变量中
bool pop(PSTACK pS, int *pVal)
{
if (empty(pS))
return false;
else
{
PNODE r = pS->pTop;
*pVal = r->data;
pS->pTop = pS->pTop->pNext; // ps->pTop=r->pNext
free(r);
r = NULL;
return true;
}
}
5.栈的判空
栈空的条件为,栈顶指针和栈底指针指向同一个存储单元
bool empty(PSTACK pS)
{
if (pS->pBottom == pS->pTop)
{
return true;
}
else
{
return false;
}
}
6.栈的遍历
6.1图解过程
1.定义一个结构体指针指向栈顶,和S.pTop指向同一个位置
2.每读取一个元素就将p下移一次,直到p指向的节点的指针域为NULL
6.2代码
void traverse(PSTACK pS)
{
PNODE p;
p = pS->pTop;
cout << "stack's datas are:" << endl;
while (p->pNext != NULL)
{
cout << p->data << endl;
p = p->pNext;
}
}
边栏推荐
猜你喜欢
随机推荐
性能测试概述
Skywalking安装部署
网盘程序 ZFile安装
routeros KVM安装LEDE 20191030最新版应用
Some derivation formulas for machine learning backpropagation
【云原生】-Docker安装部署分布式数据库 OceanBase
emby,jellyfin,kodi系列
Oracle入门 13 - Linux文件目录类命令
alert弹框处理,div块处理,上传文件
What is float?What is document flow?Several ways and principles of clearing floats?What is BFC, how to trigger BFC, the role of BFC
Project exercise - memorandum (add, delete, modify, check)
新瓶陈酒 --- 矩阵快速幂
银河麒麟高级服务器v10 sp1 手动加载Raid卡驱动
JDBC的使用
项目-log4j2排查问题
在级联选择器,根据不会重复的字段,来获取当前的对象
闭包,装饰器,类方法,静态方法,委托属性
11.0 堆参数调优入门之堆参数调整
简单计算器,单层循环输出乘法表,字符串方法的使用,格式化输出
浅析瀑布流布局原理及实现方式