文档介绍：第 1 章数据结构与算法
算法
:是指解题方案的准确而完整的描述
:可行性、确定性、有穷性(有限的时间)、拥有足够的情报
:时间复杂度和空间复杂度
(1)时间复杂度:算法所需要的计算工作量(算法所执行的基本运算次数)
(2)空间复杂度:执行这个算法所需要的内存空间
数据结构的基本概念
(1)逻辑结构:指反应数据元素之间逻辑关系的数据结构
(2)存储结构(物理结构):数据的逻辑结构在计算机存储空间中的存放形式。
(3)对各种数据结构进行的运算
:是指带有结构的数据元素的集合。所谓结构就是指数据元素之间的前后件关系。
在数据结构中,没有前件的结点称为根结点,没有后件的结点为终端结点(也叫叶子结点)。
:一个元素都没有的数据结构。
:线性结构与非线性结构。
¬ 线性结构:有且只有一个根结点,每一个结点最多有一个前件,也最多有一个后件。
¬ 非线性结构:如果一个数据结构不是线性结构,则称之为非线性结构。
线性表及其顺序存储
、最常用的一种线性结构。
:
(1)有且只有一个根结点,无前件
(2)有且只有一个终端(叶子)结点,无后件
(3)除根结点与终端结点外,其他所有结点有且只有一个前件,也有且只有一个后件。
在线性表中结点的个数 n 称为线性表的长度,当 n=0 时,称为空表。
:
(1)所有元素所占的存储空间是连续的
(2)各元素在存储空间中是按逻辑顺序依次存放的
n 的顺序存储的线性表中,当在任何位置上插入或删除一个元素概率都相等时,插入或删除一个元素所需移动元素的平均个
数是为 n/2。
栈和队列
:限定在一端进行插入与删除的线性表。
: 先进后出或后进先出
:入栈运算、退栈运算、读栈顶元素
(1)上溢:当栈空间已满,不能再入栈时,称为“上溢”。
(2)下溢:当栈空间已空,不能再出栈时,称为“下溢”。
:允许在一端进行插入、而在另一端进行删除的线性表
: 先进先出或后进后出
:将队列存储空间的最后一个位置绕到第一个位置,形成逻辑上的环状空间。
:(分两种情况)
(1)队尾指针>队头指针: 元素个数= 队尾指针- 队头指针
(2)队尾指针<队头指针: 元素个数= 队尾指针+ 队列容量–队头指针
线性链表
。
,每个数据结点由两部分组成:一部分存放数据元素的值,称为数据域;另一部分存放下一结点的存储地址,称为
指针域。
,存储数据结构的存储空间可以不连续,各数据结点的存储顺序与数据元素的逻辑关系可以不一致,而数据元素之
间的逻辑关系是由指针域来确定的。
:在线性链表中插入或删除一个元素时,不需要移动元素的位置,只需改变指针的指向就行了。
:只要指出表中任何一个