数据结构与算法 ----C/C++
学习数据结构的目的:针对不同的情况使用不同数据结构,去解决不同的问题
一、线性表
线性表一般有几个函数/(宏定义):
- 初始化线性表 List_Init()/List_Create()
- 返回第K元素的数据值 List_getElementData()
- 返回线性表长度 List_getLength()
- 插入一个元素到线性表 List_insertData()
- 删除指定为序第i个元素 List_deleteData()
提示 : 在编写这些操作函数前(宏定义)首先要检验形参的合法性,如果是动态内存分配空间失败,应该退出,避免程序异常。
1、利用数组的连续存储空间顺序存放线性表的各个元素的优势如下:
- 物理上存储空间连续、相对节省内存空间。
- 访问速度快,用数组方式访问元素更加快,只需要知道索引即可。
- 插入/或删除元素不方便,其他后面的元素也要向后移动,删除元素后,其他后面的元素也要向前移动。
- 需要预先控制数组长度。
2、利用链表实现数据存储
- 生成节点相对耗费时间,动态内存函数调用
- 访问某一个位置数据需要遍历方式,相对较慢
- 方便插入和删除数据、不需要移动数据的元素,只需要修改“链表节点”。
- 容易出现内存碎片,这种情况单片机比较容易出现
- 内存空间不连续,消耗更多一点(只是一点点而已)
- 不需要预先控制长度,长度根据内存容量决定
链表种类
1、单链表
优势:动态内存分配比双向链表少一个指针,那么分配内存相对较少。
2、双向链表
优势:容易获取尾部最后一个节点,适用于FIFO类型的数据结构,FIFO的节点个数根据内存容量决定(应该限制一下,避免内存分配满了,导致程序没有可用内存而挂掉)。
链表实际应用场景:FreeRTOS系统上的任务、线程运行队列、连续上送数据。
二、堆栈
堆栈:可以用链式(Top是链表头)、数组等方式实现堆栈
1、数据出口和入口是同一个
2、数据入栈和出栈特点:先进后出(FILO)
3、需要两个指针分别指向栈顶和栈底的元素
一般有几个操作集/(宏定义):
- 初始化空堆栈、并设置长度位stackMaxSize Stack_Init()/Stack_Create()
- 判断堆栈S是否已经满了 Stack_isFull()
- 将数据入栈 ,加入栈顶元素 Stack_pushData()
- 将数据出栈 ,返回栈顶元素 Stack_popData()
- 判断堆栈是否为空 Stack_isEmpty()
堆栈表达式求值:中缀表达式 -->> 后缀表达式
2+9/3-5 -->> 2 9 3/ + 5 -
当表达式中出现有 ( ) 括号或者 [ ] 中括号时候
算法思路:
(1)初始化一个栈大小为Stack_maxSize
(2)若是出现右括号,则栈中元素不断出栈并进行运算,直至出栈元素为左括号
(3)若果是左括号的话,则压入栈中
(4)若是所有元素都出栈还是匹配不到(左、右)括号
应用场景:Android 软件界面的APP、微信界面、小程序、门禁人机交互界面、一些进入/返回界面操作能够体现出来
三、队列
队列:顺序存储(数组)/链式存储(链表),受约束的线性表
- 插入与删除操作:加入元素只能在一端,删除元素只能在另一端
- 先进先出(先来先服务)(FIFO)
- 两个指针指向队列头(font)和尾部(rear)
操作集:
1、创建队列 Queue_Create()
2、加入队列 Queue_addElement()
3、删除队列 Queue_delElement()
4、判断队列是否满了 Queue_isFull()
5、判断队列是否为空 Queue_isEmty()
数据结构应用实例:Window消息机制、发送数据的缓冲区、事件发生消息机制、多半用于通信的消息机制。
四、查找
在某些数据类型中经常要经行查找的操作
查找:根据某个给定关键字K,从集合R中找出关键字与K相同的记录
静态查找:集合的记录固定不变
- 没有插入与删除、只有查找
动态查找:集合的记录动态变化 - 除了查找、集合有插入和删除
顺序查找:
1、查找出固定元素后退出
2、查找不出来,到了数组边界时候退出
3、建立一个//哨兵//,就是第一个元素赋值是自己要找的元素。
- 如果返回值是第一个,没找到元素
- 返回值不是第一个,找到元素并返回位置
二分查找:
1、要求n个数据的集合,必须有序排列(有序比如:从小到大 )
查找范围:
3 22 243 244 255 266 455 677 744 844
1 2 3 4 5 6 7 8 9 10
取中间值,进行比较,当两个指针分别是左边的和右边的相反位置时候,找不到
五、树
1、结点的度(Degree):结点的子树个数
2、树的度:树的所有结点中最大的度数
3、叶结点:度为0的结点
4、父结点:
5、子结点:
6、兄弟结点:具有同一父结点的各结点彼此时兄弟结点
7、路径和长度:
…
二叉树
- 树中所有结点的度不大于2的树
- 一个二叉树第i层最大结点数有2的i-1次方,i≥1
- 深度为K的二叉树有最大结点总数为:2的K次方 减1,K≥1
二叉树操作集:
1、判断二叉树是否为空 Tree_IsEmpty()
2、遍历,按某顺序访问每个结点 Tree_goTraversal()
3、创建一个二叉树 Tree_goCreateBinTree()
特殊二叉树:斜二叉树、完全二叉树、完美二叉树、满二叉树
常用的遍历方法有:
void PreOrderTraversal() 先序遍历 – 根、左子树、右子树
void InOrderTraversal() 中序遍历 – 左子树、根、右子树
void PostOrderTraversal() 后序遍历 – 左子树、右子树、根
void LevelOrderTraversal() 层次遍 历 – 从上到下、从左到右
二叉树的存储结构
1、顺序存储结构(数组)
利用数组存储完全二叉树(仅限于完全二叉树,可以补齐成一个完全二叉树)
- 非根结点的父节点的序号是[ i / 2 ]
- 结点的左孩子结点的序号是[ 2i ]
- 结点的右孩子结点的序号是[ 2i + 1 ]
2、链表存储
更新未完…
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)