只要你有能力去做事就一定要去做，不要给自己留下任何遗憾，人生最重要不是所站位置，而是所朝方向。
二级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、二叉树及其基本概念
二叉树是一种很有用非线性构造
具备如下两个特点：
①非空二叉树只有一种根结点；
②每一种结点最多有两棵子树
且分别称为该结点左子树和右子树
在二叉树中
每一种结点度最大为2
即所有子树(左子树或右子树)也均为二叉树
此外
二叉树中每个结点子树被明显地分为左子树和右子树
在二叉树中
一种结点可以只有左子树而没有右子树
也可以只有右子树而没有左子树
当一种结点既没有左子树也没有右子树时
该结点即为叶子结点
父结点(根)在树构造中
每一种结点只有一种前件
称为父结点
没有前件结点只有一种
称为树根结点
简称树根
例如
在图1-1中
结点A是树根结点
子结点和
叶子结点在树构造中
每一种结点可以有各种后件
称为该结点子结点
没有后件结点称为叶子结点
例如
在图1-1中
结点D
E
F均为叶子结点
度在树构造中
一种结点所拥有后件个数称为该结点度
所有结点中最大度称为树度
例如
在
