如你想要拥有完美无暇的友谊，可能一辈子不到朋友。
二级C语言公共基础知识之  数据结构
考点1  算法的复杂度
1．算法的基本概念
算法的基本特征：可行性、确定性、有穷性、输入（可为0）、输出(不能为0)
2．算法复杂度  包括时间复杂度和空间复杂度
名称描述时间复杂度是指执行算法所需要的计算工作量空间复杂度是指执行这个算法所需要的内存空间考点2  逻辑结构和存储结构
1．逻辑结构
2．存储结构
考点3  线性结构和非线性结构
根据数据结构中各数据元素之间前后件关系的复杂程度
一般将数据结构分为两大类型：线性结构与非线性结构
如果一个非空的数据结构满足下列两个条件：
（1）有且只有一个根结点；
（2）每一个结点最多有一个前件
也最多有一个后件
则称该数据结构为线性结构
线性结构又称线性表
在一个线性结构中插入或删除任何一个结点后还应是线性结构
栈、队列、串等都线性结构
如果一个数据结构不是线性结构
则称之为非线性结构
数组、广义表、树和图等数据结构都是非线性结构
考点4  栈
1．栈的基本概念
栈（stack）是一种特殊的线性表
是限定只在一端进行插入与删除的线性表
在栈中
一端是封闭的
既不允许进行插入元素
也不允许删除元素；另一端是开口的
允许插入和删除元素
通常称插入、删除的这一端为栈顶
另一端为栈底
当表中没有元素时称为空栈
栈顶元素总是后被插入的元素
从而也是最先被删除的元素；栈底元素总是最先被插入的元素
从而也是最后才能被删除的元素
"先进后出"或"后进先出"
2．栈的顺序存储及其运算  栈的基本运算有三种：入栈、退栈与读栈顶元素
（1）入栈运算：入栈运算是指在栈顶位置插入一个新元素
（2）退栈运算：退栈是指取出栈顶元素并赋给一个指定的变量
（3）读栈顶元素：读栈顶元素是指将栈顶元素赋给一个指定的变量
考点5  队列
1．队列的基本概念
队列是只允许在一端进行删除
在另一端进行插入的顺序表
通常将允许删除的这一端称为队头
允许插入的这一端称为队尾
  当表中没有元素时称为空队列
队列的修改是依照先进先出的原则进行的
因此队列也称为先进先出的线性表
或者后进后出的线性表
例如：火车进遂道
最先进遂道的是火车头
最后是火车尾
而火车出遂道的时候也是火车头先出
最后出的是火车尾
若有队列：Q =（q1
q2
...
qn）
那么
q1为队头元素（排头元素）
qn为队尾元素
队列中的元素是按照q1
q2
...
qn的顺序进入的
退出队列也只能按照这个次序依次退出
即只有在q1
q2
...
qn-1 都退队之后
qn才能退出队列
因最先进入队列的元素将最先出队
所以队列具有先进先出的特性
体现"先来先服务"的原则
队头元素q1是最先被插入的元素
也是最先被删除的元素
队尾元素qn是最后被插入的元素
也是最后被删除的元素
  "先进先出"
入队运算为往队列队尾插入一个数据元素
退队运算为从队列的队头删除一个数据元素
考点6  链表
在链式存储方式中
要求每个结点由两部分组成：一部分用于存放数据元素值
称为数据域
另一部分用于存放指针
称为指针域
其中指针用于指向该结点的前一个或后一个结点（即前件或后件）
链式存储方式既可用于表示线性结构
也可用于表示非线性结构
（1）线性链表
线性表的链式存储结构称为线性链表
在某些应用中
对线性链表中的每个结点设置两个指针
一个称为左指针
用以指向其前件结点；另一个称为右指针
用以指向其后件结点
这样的表称为双向链表
在线性链表中
各数据元素结点的存储空间可以是不连续的
且各数据元素的存储顺序与逻辑顺序可以不一致
在线性链表中进行插入与删除
不需要移动链表中的元素
（2）带链的栈
栈也是线性表
也可以采用链式存储结构
带链的栈可以用来收集计算机存储空间中所有空闲的存储结点
这种带链的栈称为可利用栈
考点7  二叉树及其基本性质
1、二叉树及其基本概念
二叉树是一种很有用的非线性结构
具有以下两个特点：
①非空二叉树只有一个根结点；
②每一个结点最多有两棵子树
且分别称为该结点的左子树和右子树
在二叉树中
每一个结点的度最大为c语言的冒泡排序算法2
即所有子树（左子树或右子树）也均为二叉树
另外
二叉树中的每个结点的子树被明显地分为左子树和右子树
在二叉树中
一个结点可以只有左子树而没有右子树
也可以只有右子树而没有左子树
当一个结点既没有左子树也没有右子树时
该结点即为叶子结点
父结点（根）  在树结构中
每一个结点只有一个前件
称为父结点
没有前件的结点只有一个
称为树的根结点
简称树的根
例如
在图1-1中
结点A是树的根结点
子结点和
叶子结点  在树结构中
每一个结点可以有多个后件
称为该结点的子结点
没有后件的结点称为叶子结点
例如
在图1-1中
结点D
E
F均为叶子结点
度  在树结构中
一个结点所拥有的后件的个数称为该结点的度
所有结点中最大的度称为树的度
例如
在图1-1中
根结点A和结点B的度为2
结点C的度为1
叶子结点D
E
F的度为0
所以
该树的度为2
深度  定义一棵树的根结点所在的层次为1
其他结点所在的层次等于它的父结点所在的层次加1
树的最大层次称为树的深度
例如
在图1-1中
根结点A在第1层
结点B
C在第2层
结点D
E
F在第3层
该树的深度为3
子树  在树中
以某结点的一个子结点为根构成的树称为该结点的一棵子树
2、二叉树基本性质
二叉树具有以下几个性质：
性质1：在二叉树的第k层上
最多有2k-1（k≥1）个结点；
性质2：深度为m的二叉树最多有2m-1个结点；
性质3：在任意一棵二叉树中
度为0的结点（即叶子结点）总是比度为2的结点多一个
性质4：具有n个结点的二叉树
其深度至少为［log2n］+1
其中［log2n］表示取log2n的整数部分
3、满二叉树与完全二叉树
满二叉树是指这样的一种二叉树：除最后一层外
每一层上的所有结点都有两个子结点
在满二叉树中
每一层上的结点数都达到最大值
即在满二叉树的第k层上有2k-1个结点
且深度为m的满二叉树有2m－1个结点
完全二叉树是指这样的二叉树：除最后一层外
每一层上的结点数均达到最大值；在最后一层上只缺少右边的若干结点
对于完全二叉树来说
叶子结点只可能在层次最大的两层上出现：对于任何一个结点
若其右分支下的子孙结点的最大层次为p

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。