导图社区 栈和队列
这是一篇关于栈和队列的思维导图
编辑于2022-03-07 20:34:51栈
栈的定义
栈的定义
主要内容
栈和队列主要内容
顺序栈和链栈的实现
顺序栈的实现
顺序栈的定义
顺序栈的定义
此处需要注意top不指向具体数据元素,而是为下面指向数据元素做准备
顺序栈的代码
头文件设置
返回状态量的定义
返回状态量定义
主要函数设置
栈的初始化
顺序栈的初始化
栈的摧毁
栈的摧毁
栈的清空
栈的清空
入栈函数
入栈函数
这里要质疑*ps->top和ps->top的区别,一个是地址一个是数值
出栈函数
出栈函数
栈长度反馈
栈长度值的反馈
栈空判断函数
栈空判断函数
栈的用法
栈的用法
此处需要清楚->优先级要大于*
栈的增容函数
栈的增容
注意这里自己在编程时忘了把realloc里面的ps改成ps->base,因此编程未通过,这里表面realloc的用法掌握不够,后续要进一步加强
链栈的实现
链栈的插入示意图
链栈的出入示意图
链栈头文件
链栈头文件
链栈函数
链栈初始化
链栈初始化
链栈创建节点
入栈函数
带头节点入栈示意图
入栈函数
出栈函数
带头节点出栈函数
获取栈顶的值
取栈顶的值
这里要注意需要关注的值的那一方是否为空
清空栈的值
清空栈
判断栈是否为空函数
空栈判断函数
摧毁栈函数
摧毁栈函数
链栈的实现过程
链栈的实现过程
链栈的具体应用
典型应用举例
典型应用举例
进制转换
进制转换原理
进制转换原理
进制转换函数1
进制转换代码1
进制转换代码2
两者构成进制转换代码
数字转换成字符串函数2
原理详解
数字转换位字符串函数详解
宏定义
宏定义
代码
代码1
代码2
实现方式
改进方案
括号匹配检查
原理分析
括号匹配原理
匹配过程图示表示
括号匹配代码
改进方式
行编辑程序
行编辑原理
行编辑原理
栈存图示
行编辑代码
行编辑代码
exit(EXIT_FAILURE)表示没有成功执行一个程序,这里表示程序终止
备注:EOF表示end of file的意思在C标准库中,像getchar这样的数据读取函数返回一个与符号(宏)EOF相等的值来指明文件结束的情况发生,EOF的真实值与不同的平台有关(但通常是-1,比如在glibc中),并且不等于任何有效的字符代码。块读取函数返回读取的字节数,如果它小于要求读取的字节数,就会出现一个文件结束符。在C语言中,或更精确地说成C标准函数库中表示文件结束符(endoffile)。在while循环中以EOF作为文件结束标志,这种以EOF作为文件结束标志的文件,必须是文本文件。在文本文件中,数据都是以字符的ASCII代码值的形式存放。我们知道,ASCII代码值的范围是0~255,不可能出现-1,因此可以用EOF作为文件结束标志。(该程序可以通过ctrl+C来实现)
保存文件及改进
保存文件
改进
fputc(‘a’,filename)是将a写入到filename中去
实现过程
实现过程
企业级链表
企业级链表的结构
企业级链表结构
C语言补漏:->和.的区别:在于
入栈和出栈示意图
入栈示意图
入栈示意图(注意top与val先后问题)
出栈示意图
出栈示意图(注意top与val先后问题)
栈和队列
队列
队列定义
队列的定义
队列的链式结构
链式结构存储方式
链式结构存储方式
队列的链式结构
队列栈节点及栈的结构
创建一个队列
队列初始化
入队操作
入队操作
操作代码
出队列操作
出队列操作
出队列操作代码
清除队列操作
清除队列
验证
验证操作
队列的顺序结构
顺序队列结构
队列顺序定义
头文件定义
头文件定义
初始化循环队列
初始化循环队列
入队列与出队操作
入队列与出队操作
判空及判满操作
判空与判满操作
打印队列
打印队列
获取头节点、清空与摧毁队列
获取头节点、清空与摧毁队列
排序
选择排序
图示原理及代码
图示原理
选择排序代码
插入排序
图示原理及代码
图示原理
插入排序代码
冒泡排序
图示原理及代码
图示原理
冒泡排序代码
希尔排序
图示原理及代码
图示原理
1
代码
代码
解析:希尔排序其实就是改进的插入排序,通过改变插入排序跨步长度来使其排序变快,像一般的排序是0(N^2),这里通过改进可以小于它,一般情况是0(NlogN)的大小
快速排序
图示原理及代码
基本思想
基本思想图示
快速排序图示
1
2
代码演示
代码演示
快速排序时间复杂度为o(nlogn),但缺点和希尔排序一样,由于是分组排序的,所以排序时间不稳定
归并排序
原理
总结:其实归并排序是利用分治的思想,将大的化为小的,而后一一解决以后再将其进行统一合并得到的。因此这里有两种方法,一是递归一是迭代
递归法
迭代法
主题