登录/注册
张三
2681
占位
0
占位
0
浏览量
占位
粉丝
占位
关注
第五话·数据结构必看之·栈 真的这么简单?
张三
2021-12-07 09:55:43 2021-12-07
54
0

🌕写在前面 🍊博客主页:kikoking的江湖背景 🎉欢迎关注🔎点赞👍收藏⭐️留言📝 🌟本文由 kikokingzz 原创,CSDN首发! 📆首发时间:🌹2021年12月06日🌹 🆕最新更新时间:🎄2021年12月06日🎄 ✉️坚持和努力一定能换来诗与远方! 🙏作者水平很有限,如果发现错误,请留言轰炸哦!万分感谢感谢感谢! 前文简介: 第一话·彻底搞清数据结构中的·逻辑结构&存储结构 第二话·彻底搞懂数据结构之·算法复杂度 第三话·408必看顺序表之·人生不是“顺序表” 第四话·数据结构必看之·单链表就这?

 目录

🔥1.栈的逻辑结构

🍊1.1 线性表

🍊1.2 栈的数学性质

✅例题1·卡特兰数

🔥2.栈的物理结构

🍊2.1 栈的顺序存储结构

🍓顺序栈的优点

🍊2.2共享栈

🍓共享栈的优点

🍊2.3 栈的链式存储结构

🍓链栈的优点

🔥3.用单链表实现链栈的一系列操作

🍊3.1链栈的定义

🍊3.2初始化

🍓选择带哨兵位头结点的单链表

🍊3.3判空操作

🍊3.4销毁

🍊3.5进栈

🍊3.6出栈

🍊3.7读栈顶元素

🔥4.用动态数组实现顺序栈的一系列操作

🍊4.1顺序栈的定义

🍊4.2初始化

🍊4.3判空操作

🍊4.4销毁

🍊4.5进栈

🍊4.6出栈

🍊4.7读栈顶元素

🔥栈的应用1·括号匹配

 ✅思路

🖥算法演示

🍓代码实现

🔥栈的应用2·中缀表达式求值

🍊中缀表达式转后缀表达式方法

🍊后缀表达式求值的计算机实现

🍊中缀表达式转后缀表达式的机器计算

🌟中缀表达式求值

✅普通法——将上述两种方法按次序进行

✅深度结合法 

🍊中缀表达式转前缀表达式方法​

🍓前缀表达式的机器计算

🐉:老样子,学习一种数据结构要按照怎么样的顺序学习呀? L:要从它的逻辑结构-->物理结构(存储结构)-->执行的操作来进行分析

✨✨✨我是分割线✨✨✨

🔥1.栈的逻辑结构 🍊1.1 线性表 栈(Stack)是只允许一端进行插入或删除操作的线性表 🍊1.2 栈的数学性质 常常以选择题形式考察,出栈顺序是否合法 ✅例题1·卡特兰数 列举检验:

✨✨✨我是分割线✨✨✨

🔥2.栈的物理结构 🍊2.1 栈的顺序存储结构 采用顺序存储的栈称为顺序栈,它利用一组地址连续的存储单元存放自栈底到栈顶的数据元素,同时附设一个指针(top)指示当前栈顶元素的位置。 🍓顺序栈的优点 1.偶尔增容,偶尔增一下,而链栈每次都要申请结点 2.插入数据相比链栈更高效 🍊2.2共享栈 🍓共享栈的优点 1.节省存储空间 2.降低发生上溢的可能 🍊2.3 栈的链式存储结构 ·采用链式存储的栈称为链栈 🍓链栈的优点 1.便于多个栈共享共享存储空间和提高效率 2.不存在栈满上溢的情况 3.和顺序栈相比,它可以动态地分配存储空间,方便扩容

 

✨✨✨我是分割线✨✨✨

🔥3.用单链表实现链栈的一系列操作 🍊3.1链栈的定义 typedef int ElemType;

typedef struct LStackNode //定义一个结构体类型的结点

{
ElemType x; //数据域
struct LStackNode* next; //指针域
}LS; //用LS代替LStackNode结点 🍊3.2初始化 🍓选择带哨兵位头结点的单链表 ·原因:可见,用单链表实现入栈、出栈基本上都是对应于头插和头删,为了方便起见,采用带哨兵位的头结点的单链表! void LStackInit()
{
LS* phead = (LS*)malloc(sizeof(LS));//申请一个哨兵位的头结点
phead->next = NULL; //初始化时,哨兵位头结点指向NULL
phead->data = 0;//哨兵位头结点的数据域为0
} 🍊3.3判空操作 int LStackEmpty(LS* phead)//判空
{
assert(phead);
return phead->next == NULL ? 1 : 0;
//如果phead指向空,则说明链栈为空
} 🍊3.4销毁 void LStackDestroy(LS* phead)//销毁
{
assert(phead);
LS* cur = phead->next;
while (cur)
{
LS* next = cur->next;
free(cur);
cur = next;
}
phead->next = NULL;
} 🍊3.5进栈 void LStackPush(LS* phead ,ElemType x)
{
assert(phead);
LS* newnode= (LS*)malloc(sizeof(LS));//动态申请一个新结点
newnode->data = x;//新结点的数据域放x
newnode->next = phead->next;
phead->next = newnode;
} 🍊3.6出栈 void LStackPop(LS* phead)
{
assert(phead);
LS* cur = phead->next;
if (cur)//如果哨兵位头结点后面有结点
{
LS* next = cur->next;
free(cur);
phead->next = next;
}
return;
} 🍊3.7读栈顶元素 ElemType LStack(LS* phead)
{
assert(phead);
assert(!LStackEmpty(phead));//栈非空才可以向下进行
return (phead->next)->data;
}

✨✨✨我是分割线✨✨✨

🔥4.用动态数组实现顺序栈的一系列操作 🍊4.1顺序栈的定义 typedef int STDataType;

typedef struct Stack //这是一个动态数组Stack
{
STDataType* a;//指针a指向数组的首元素地址
int top;//栈顶
int capacity;//栈的容量
}ST;//用ST来简便代替struct Stack 🍊4.2初始化 void StackInit(ST* pst)
{
assert(pst);//断言结构体不为空
pst->a = (STDataType*)malloc(sizeof(STDataType) * 4);
//动态申请存放4个元素的空间
//好处是之后扩容可以直接扩容
pst->top = 0;//指向栈顶元素的top指向0
pst->capacity = 4;//栈的容量为4
} 🍊4.3判空操作 🍊4.4销毁 void StackDestroy(ST* pst)//销毁栈
{
assert(pst);//结构体不为空才往下进行
free(pst->a);//销毁栈
pst->a = NULL;//将原本指向栈底的指针置空
pst->capacity = pst->top = 0;//栈的容量和top的值都置0
} 🍊4.5进栈 void StackPush(ST* pst, STDataType x)
{
assert(pst);
if (pst->top == pst->capacity)//判断是否需要增容
{
STDataType* tmp = (STDataType*)realloc(pst->a,sizeof(STDataType) * pst->capacity * 2);//用tmp指向新申请的一片空间
if (tmp == NULL)
{
printf("realloc fail\n");//增容失败
exit(-1);//结束整个程序
}
pst->a = tmp;//栈底指针a指向新空间
pst->capacity = 2;//栈的容量扩增两倍
}
pst->a[pst->top] = x;//在top指向的位置插入元素
pst->top++;//top指向下一个可以插入的位置
} 🍊4.6出栈 void StackPop(ST
pst)//出栈操作
{
assert(pst);
assert(!StackEmpty(pst));//如果栈为空就不进行下去了
pst->top--;//将指向栈顶的top减1
} 🍊4.7读栈顶元素 STDataType StackTop(ST* pst)
{
assert(pst);
assert(!StackEmpty(pst));//如果为空就不进行下去了
return pst->a[pst->top - 1];//返回一个栈顶元素
//因为top一直指向下一个元素插入的位置,所以当前栈顶元素的位置应当是top-1
}

✨✨✨我是分割线✨✨✨

🔥栈的应用1·括号匹配 20. 有效的括号https://leetcode-cn.com/problems/valid-parentheses/ ✅思路 1.每出现一个右括号,就消耗一个左括号 2.遇到左括号就入栈 3.遇到右括号,就“消耗”一个左括号 🖥算法演示 ✅正常模式: ❌错误模式: 由于C语言的库不够完整,因此下面所使用到的栈,调用了上面预先建立的顺序栈的程序 🍓代码实现 bool isValid(char * s){

ST st;
StackInit(&st);//记得要初始化它
while(*s)
{
//左括号入栈
//右括号找最近的左括号匹配
if(*s=='['||*s=='('||*s=='{')
{
StackPush(&st,*s);
++s;//继续判断下一个题目给的括号
}
else
{
if(StackEmpty(&st))//栈为空,说明没有前括号
{
StackDestroy(&st);//记得要先销毁再return
return false;
}
char top=StackTop(&st);//读取栈顶元素
//如果不匹配就return false
if((top=='['&&*s!=']')
||(top=='('&&*s!=')')
||(top=='{'&&*s!='}'))
{
StackDestroy(&st);//记得要先销毁
return false;
}
else
{
StackPop(&st);//将栈顶元素出栈
++s;//继续判断下一个题目给的括号
}
}
}

bool ret = StackEmpty(&st);//判断此时栈是否空
//如果栈不空,说明有多余的左括号没有得到匹配
StackDestroy(&st);//记得要销毁
return ret;//最后栈空返回true,不空返回false

}

✨✨✨我是分割线✨✨✨

🔥栈的应用2·中缀表达式求值 前情须知: 上述中括号就是界限符,界限符同时也限制的运算的先后次序,计算机如何识别界限符是很难的,这时候,一个波兰数学家提出:可以不同界限符也能无歧义地表达 🍊中缀表达式转后缀表达式方法 🍊后缀表达式求值的计算机实现 🍊中缀表达式转后缀表达式的机器计算 🌟中缀表达式求值 ✅普通法——将上述两种方法按次序进行 Step1.将中缀表达式转换为后缀表达式 Step2.使用后缀表达式计算 ✅深度结合法 ·使用两个栈来进行 🍊中缀表达式转前缀表达式方法 🍓前缀表达式的机器计算

原文: https://blog.csdn.net/qq_54151955/article/details/121708312

暂无评论