常用数据结构及其存储

常用数据结构及其存储第一页，共二十七页，2022年，8月28日[主要内容]21.1算法21.2数据结构的基本概念21.3线性表21.4栈与队列21.5树与二叉树第二页，共二十七页，2022年，8月28日21.1算法

定义：是对特定问题求解步骤的一种描述。或者说，是为求解某问题的方法和步骤。

特征：有穷性确定性有效性零个或多个输入一个或多个输出第三页，共二十七页，2022年，8月28日例如：一元二次方程求根算法。键盘输入系数送到a,b,c中start计算出两个根放在x1、x2中显示x1、x2中存放的数据end第四页，共二十七页，2022年，8月28日算法复杂度评价一个算法优劣的主要标准是：算法的执行效率与存储需求

算法的效率：指的是时间复杂度（TimeComplexity）

存储需求：指的是空间复杂度（SpaceComplexity）

一般情况下，算法中的基本操作重复操作执行的次数是问题规模n的某个函数f(n)，算法的时间复杂度记做：T(n)=O(f(n))第五页，共二十七页，2022年，8月28日21.2数据结构的基本概念数据与数据结构

数据:

是描述客观事物的数、字符以及所有能输入到计算机中并被计算机程序加工处理的符号的集合。

数据元素:

是数据的基本元素，即数据集合中的个体。

数据项:

具有独立意义的最小数据单位。

数据对象:

具有相同特性的数据元素的集合，是数据的子集。

数据结构:互相之间存在着一种或多种关系的数据元素的集合。

第六页，共二十七页，2022年，8月28日数据的逻辑结构

集合线性结构树形结构图状或网状结构第七页，共二十七页，2022年，8月28日数据的存储结构一、顺序存储结构主要特点：所有元素所占的存储空间是连续的；各个元素在存储空间中是按逻辑顺序依次存放的；元素可随机存取，但插入、删除运算不便，会引起大量结点的移动。第八页，共二十七页，2022年，8月28日二、链式存储结构主要特点：存储数据结构的存储空间可以不连续；各结点的存储顺序与元素之间的逻辑关系可以不一致，元素之间的逻辑关系由指针域来确定；插入、删除操作灵活方便，不必移动结点，只要改变结点中的指针值即可。

第九页，共二十七页，2022年，8月28日数据的运算

检索：在数据结构里查找满足一定条件的结点

插入：往数据结构里增加新的结点

删除：把指定的结点从数据结构里去掉

更新：修改指定结点的一个或多个域的值

排序：保持线性结构的结点序列里结点数不变，将结点按某种指定的顺序重新排列第十页，共二十七页，2022年，8月28日21.3线性表线性表是最常用的一种数据结构。线性表的逻辑结构是n个数据元素的有限序列。

（a1，a2，…，an）

顺序表：指用顺序存储结构存储的线性表。

链表：用链式存储结构存储的线性表。

栈和队列：是对线性表的插入、删除运算可以发生的位置加以限制的两种特殊的线性表。第十一页，共二十七页，2022年，8月28日顺序表

各种高级语言里的一维数组就是用顺序方式存储的线性表，因此常用一维数组称呼顺序表。若顺序表中结点个数为n，则：

插入一个结点平均需要移动之结点个数为

n/2，算法的时间复杂度是O(n)；

删除一个结点平均需移动结点个数为

（n-1）/2，算法的时间复杂度是O(n)。第十二页，共二十七页，2022年，8月28日链表

线性链表（单链表）：删除算法的时间复杂度为O(n)，其主要执行时间是搜索删除位置。

循环链表：指链表的最后一个结点的指针值指向第一个结点，整个链表形成一个环（如下图）。…结点1结点2结点n第十三页，共二十七页，2022年，8月28日21.4栈和队列栈：是一种特殊的线性表，是限定仅在表尾进行插入和删除运算的线性表，表尾称为栈顶（top），表头称为栈底（bottom）。表中无元素即空栈。栈中有元素a1,a2,…,an，如下页图所示，称a1为栈底元素。新元素进栈要置于an之上，删除或退栈先对an进行，即“后进先出”（LIFO）的操作原则;

栈的物理存储可以用顺序存储结构或链式存储结构;

栈的运算还有取栈顶元素，检查栈是否为空，清除等。第十四页，共二十七页，2022年，8月28日栈的插入和删除ABACBABAFEBAATOPTOPTOPTOPTOPTOPan…a2a1进栈出栈栈底栈结构(3)(1)(2)(5)(4)(6)栈顶第十五页，共二十七页，2022年，8月28日队列队列：是限定所有的插入都在表的一端进行，所有的删除都在表的另一端进行的线性表。进行删除的一端叫队头，进行插入的一端叫队尾，如下页图所示。在队列中，新元素总是加入到队尾，每次删除的总是对头元素，即当前“最老的”元素，这就是“先进先出”（FIFO）的操作原则。队列的物理存储可以用：顺序存储结构，也可用链式存储结构。第十六页，共二十七页，2022年，8月28日队列的示意图出队列

a1a2a3…an

入队列

队头

队尾第十七页，共二十七页，2022年，8月28日队列的插入和删除示例第十八页，共二十七页，2022年，8月28日21.5树与二叉树

树形结构是一类重要的非线性结构，树和二叉树是最常见的树形结构。

树（Tree）:是n（n≥0）个结点的有限集合。若n=0，则称为空树；否则，有且仅有一个特定的结点被称为根，当n>1时，其余结点被分成m（m>0）个互不相交的子集T1，T2，…，Tm，每个子集又是一棵树，称作这个根的子树（subtree）。

第十九页，共二十七页，2022年，8月28日树形结构的常用术语

结点的度（Degree）：一个结点的子树的个数。

树的度：树中各结点的度的最大值。

树叶（Leaf）：度为0的结点。

分支结点：度不为0的结点。

双亲（Parent）、子女（Child）：结点的各子树的根称作该结点的子女；相应的该结点称作其子女的双亲。

兄弟（Sibling）：具有相同双亲的结点互为兄弟。

结点的层数（Level）；树的深度（Depth）森林（Forest）第二十页，共二十七页，2022年，8月28日二叉树

二叉树（BinaryTree）:是n（n≥0)个结点的有限集合，这个集合或者为空集（n=0），或者由一个根结点及两棵不相交的、分别称作这个根的左子树和右子树的二叉树组成。二叉树是树的特殊情形。

二者的区别是：二叉树为有序树。第二十一页，共二十七页，2022年，8月28日

二叉树的性质：

1、在二叉树的i层上，最多有2i-1个结点（i≥1）

2、深度为k的二叉树最多有2k-1个结点(k≥1)

3、对于任意一棵二叉树，如果度为0的结点个数为n0，度为2的结点个数为n2，则n0=n2+1。

4、具有n个结点的完全二叉树的深度为[log2n]+1。其中，[log2n]是不大于log2n的最大整数。

第二十二页，共二十七页，2022年，8月28日满二叉树和完全二叉树

一棵深度为k且具有2k-1个结点的二叉树称为满二叉树（FullBinaryTree）。深度为k，有n个结点的二叉树，当且仅当其妹一个结点都与深度为k的满二叉树中编号从1到n的结点一一对应时，称为完全二叉树。第二十三页，共二十七页，2022年，8月28日二叉树的存储

二叉树的存储通常采用：链接方式。每个结点除存储结点自身的信息外再设置两个指针域Ichild和rchild，分别指向结点的左子女和右子女，当结点的某个指针为空时，则相应的指针值为空（NIL或∧

）。结点的形式为：lchilddatarchild第二十四页，共二十七页，2022年，8月28日二叉树的遍历

遍历一个树形结构是指：按一定次序系统的访问该结构中的所有结点，使每个结点恰好被访问一次。前序遍历法（NLR次序）访问根，按前序遍历左子树，按前序遍历右子树。后序遍历法（LRN次序）按后序遍历左子树，按后序遍历右子树，访问根。