内容发布更新时间 : 2024/5/3 21:16:53星期一 下面是文章的全部内容请认真阅读。

只要你有能力去做的事就一定要去做，不要给自己留下任何遗憾，人生最重要的不是所站的位置，而是所朝的方向。

二级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）线性链表

线性表的链式存储结构称为线性链表