计算机二级c语言数据结构与算法思维导图
本思维导图主要介绍计算机二级c语言数据结构与算法
树图思维导图提供 计算机二级c语言数据结构与算法 在线思维导图免费制作，点击“编辑”按钮，可对 计算机二级c语言数据结构与算法 进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：9ffa0e6441344953b6f15e88d8dfbc41
思维导图大纲
计算机二级c语言数据结构与算法思维导图模板大纲
算法
算法的概念
是指解题方案的准确而完整的描述
算法的基本特征：
可行性、确定性、有穷性(有限的时间)、拥有足够的情报
算法的复杂度：
时间复杂度和空间复杂度
(1)时间复杂度：
算法所需要的计算工作量（算法所执行的基本运算次数）
(2)空间复杂度：
执行这个算法所需要的内存空间
数据结构的基本概念
数据结构研究的三个问题
(1)逻辑结构：
指反应数据元素之间逻辑关系的数据结构
(2)存储结构（物理结构）：
数据的逻辑结构在计算机存储空间中的存放形式。
(3)对各种数据结构进行的运算
数据结构定义：
是指带有结构的数据元素的集合。所谓结构就是指数据元素之间的前后件关系。
在数据结构中，没有前件的结点称为根结点，没有后件的结点为终端结点（也叫叶子结点）。
空的数据结构：
一个元素都没有的数据结构。
数据结构的种类：
线性结构：
有且只有一个根结点，每一个结点最多有一个前件，也最多有一个后件。
非线性结构：
如果一个数据结构不是线性结构，则称之为非线性结构。
线性表及其顺序存储
线性表是最简单、最常用的一种线性结构。
非空线性表的结构特征：
(1)有且只有一个根结点，无前件
(2)有且只有一个终端（叶子）结点，无后件
(3)除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。
在线性表中结点的个数n称为线性表的长度，当n=0时，称为空表。
线性表顺序存储结构的基本特点：
(1)所有元素所占的存储空间是连续的
(2)各元素在存储空间中是按逻辑顺序依次存放的
在长度为n的顺序存储的线性表中，当在任何位置上插入或删除一个元素概率都相等时，插入或删除一个元素所需移动元素的平均个数是为n/2。
栈和队列
栈：限定在一端进行插入与删除的线性表。
栈的结构特点： 先进后出 或 后进先出
栈的基本运算：
入栈运算、退栈运算、读栈顶元素
(1)上溢：当栈空间已满，不能再入栈时，称为“上溢”。
(2)下溢：当栈空间已空，不能再出栈时，称为“下溢”。
队列：
允许在一端进行插入、而在另一端进行删除的线性表
队列的结构特点： 先进先出 或 后进后出
循环队列：
将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间。
循环队列中元素个数：(分两种情况)
(1)队尾指针>队头指针： 元素个数 = 队尾指针 - 队头指针
(2)队尾指针<队头指针： 元素个数 = 队尾指针 + 队列容量 – 队头指针
线性链表
线性表的链式存储结构称为线性链表。
在链式存储结构中，每个数据结点由两部分组成：
一部分存放数据元素的值，称为数据域；
另一部分存放下一结点的存储地址，称为指针域。
在链式存储结构中，存储数据结构的存储空间可以不连续，各数据结点的存储顺序与数据元素的逻辑关系可以不一致，而数据元素之间的逻辑关系是由指针域来确定的。
线性链表的优点：
在线性链表中插入或删除一个元素时，不需要移动元素的位置，只需改变指针的指向就行了。
循环链表的优点：
只要指出表中任何一个结点的位置，就可以从它出发访问到表中其他所有的结点，而线性单链表做不到这一点。
树与二叉树
树是一种简单的非线性结构。
树的基本术语：
父结点；根结点；子结点；叶子结点；结点的度；树的度；树的深度根结点在第1层。叶子结点没有子树。
二叉树：
只有一个根结点，每一个结点最多有2颗子树，且分别叫做左子树和右子树。
二叉树的基本性质：
(1)在二叉树的第k层上，最多有2k-1（k>=1）个结点
(2)深度为m的二叉树最多有2m-1个结点
(3)度为0的结点（叶子结点）是比度为2的结点多一个
(4)具有n个结点的二叉树，其深度至少为[log2n]+1
当完全二叉树总结点n为偶数时，叶子节点的个数为：n/2
当完全二叉树总结点n为奇数时，叶子节点的个数为：(n+1)/2
二叉树的遍历：
前序遍历（根-左-右）；中序遍历（左-根-右）；后序遍历（左-右-根）
查找技术
顺序查找：
最坏情况下，需比较n次。
二分法查找：
最坏情况下，需比较loag2n次。
排序技术
交换类排序：
（1）冒泡排序法：n(n-1)/2（最坏情况下）
（2）快速排序法：n(n-1)/2（最坏情况下） O(nlog2n)（平均情况下）
插入类排序：
（1）简单插入排序法：n(n-1)/2（最坏情况下）
（2）希尔排序法：O(n1. 5)（最坏情况下）
选择类排序：
（1）简单选择法：n(n-1)/2（最坏情况下）
（2）堆排序法： O(nlog2n) （最坏情况下）
相关思维导图模板
树图思维导图提供 计算机考试c语言知识点结构体 在线思维导图免费制作，点击“编辑”按钮，可对 计算机考试c语言知识点结构体 进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：352b1d3fd705a601054a8eaca9bc2d99
树图思维导图提供 计算机二级c语言知识点实型数据 在线思维导图免费制作，点击“编辑”按钮，可对 计算机二级c语言知识点实型数据 进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：3bb1f0337f38eaaaf140ed9487c800a4
沪公网安备 31011502019485号
上海工商