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