算法与数据结构公共基础.ppt

《算法与数据结构公共基础.ppt》由会员分享，可在线阅读，更多相关《算法与数据结构公共基础.ppt（12页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、细细雨雨双双飞艳飞艳数据：凡是能被计算机识别、存取和加工处数据：凡是能被计算机识别、存取和加工处理的符号、字符、图形、图像、声音、视频理的符号、字符、图形、图像、声音、视频信号、程序等一切信息。信号、程序等一切信息。结构：数据之间的逻辑关系。结构：数据之间的逻辑关系。数据结构指相互有关联的数据元素的集合。数据结构指相互有关联的数据元素的集合。数据、数据元素之间的关系：数据元素是数数据、数据元素之间的关系：数据元素是数据的基本单位据的基本单位数据的逻辑结构：数据的逻辑结构是指数据数据的逻辑结构：数据的逻辑结构是指数据元素之间的逻辑关系，与数据的存储无关，元素之间的逻辑关系，与数据的存储无关，是独

2、立于计算机的。是独立于计算机的。数据的逻辑结构可分成数据的逻辑结构可分成2类：线性结构、非线类：线性结构、非线性结构性结构线性逻辑结构又称为线性表，栈和队列都是线性逻辑结构又称为线性表，栈和队列都是特殊的线性表。特殊的线性表。树型结构和图都属于非线性结构。树型结构和图都属于非线性结构。数据的存储结构又称为物理结构，是指数据数据的存储结构又称为物理结构，是指数据元素及其关系在计算机内存中的表示，即数元素及其关系在计算机内存中的表示，即数据的逻辑结构在计算机存储空间中的存放形据的逻辑结构在计算机存储空间中的存放形式。式。数据的存储结构可分为哪数据的存储结构可分为哪4类？类？顺序结构、链式结构、索引

3、结构、散列结构顺序结构、链式结构、索引结构、散列结构顺序结构、链式结构、索引结构、散列结构顺序结构、链式结构、索引结构、散列结构数据的存储结构与逻辑结构的关系？数据的存储结构与逻辑结构的关系？同一逻辑结构可以采用不同的存储结构同一逻辑结构可以采用不同的存储结构同一逻辑结构可以采用不同的存储结构同一逻辑结构可以采用不同的存储结构线性表必须满足的线性表必须满足的3个条件：个条件：有且只有一个根节点有且只有一个根节点有且只有一个根节点有且只有一个根节点a1a1，它无前件；，它无前件；，它无前件；，它无前件；有且只有一个终点有且只有一个终点有且只有一个终点有且只有一个终点anan，它无后件；，它无后件

4、；，它无后件；，它无后件；除了起点和终点，其余结点只有一个前件，也只除了起点和终点，其余结点只有一个前件，也只除了起点和终点，其余结点只有一个前件，也只除了起点和终点，其余结点只有一个前件，也只有一个后件。有一个后件。有一个后件。有一个后件。线性表的长度：线性表的长度：线性表的长度：线性表的长度：结点个数结点个数结点个数结点个数n n称为线性表的长度，当称为线性表的长度，当称为线性表的长度，当称为线性表的长度，当n=0n=0时，称为空表。时，称为空表。时，称为空表。时，称为空表。顺序表顺序表顺序表顺序表线性表的顺序存储结构线性表的顺序存储结构线性表的顺序存储结构线性表的顺序存储结构 特点：特点

5、：特点：特点：1 1、所有元素所占的存储空间是连续的、所有元素所占的存储空间是连续的、所有元素所占的存储空间是连续的、所有元素所占的存储空间是连续的 2 2、各元素在存储空间中是按逻辑顺序存放、各元素在存储空间中是按逻辑顺序存放、各元素在存储空间中是按逻辑顺序存放、各元素在存储空间中是按逻辑顺序存放的的的的线性链表线性链表线性链表线性链表线性表的链式存储结构线性表的链式存储结构线性表的链式存储结构线性表的链式存储结构特点：指针域指向前一个或后一个数据元素，体现特点：指针域指向前一个或后一个数据元素，体现特点：指针域指向前一个或后一个数据元素，体现特点：指针域指向前一个或后一个数据元素，体现各数

6、据元素的逻辑顺序各数据元素的逻辑顺序各数据元素的逻辑顺序各数据元素的逻辑顺序循环队列是队列的一种顺序存储结构形式，在队列循环队列是队列的一种顺序存储结构形式，在队列循环队列是队列的一种顺序存储结构形式，在队列循环队列是队列的一种顺序存储结构形式，在队列最后一个位置已被使用，而第一个位置空闲的情况最后一个位置已被使用，而第一个位置空闲的情况最后一个位置已被使用，而第一个位置空闲的情况最后一个位置已被使用，而第一个位置空闲的情况下，仍然能进行入队操作。下，仍然能进行入队操作。下，仍然能进行入队操作。下，仍然能进行入队操作。循环队列循环队列循环队列循环队列3 3种基本运算：种基本运算：种基本运算：种

7、基本运算：入队、出队、读取数据元素入队、出队、读取数据元素入队、出队、读取数据元素入队、出队、读取数据元素链式存储结构方式的特点：链式存储结构方式的特点：链式存储结构方式的特点：链式存储结构方式的特点：结点的储存不一定连续结点的储存不一定连续结点的储存不一定连续结点的储存不一定连续各结点之间的存储顺序与数据元素的逻辑关系可各结点之间的存储顺序与数据元素的逻辑关系可各结点之间的存储顺序与数据元素的逻辑关系可各结点之间的存储顺序与数据元素的逻辑关系可以不一致以不一致以不一致以不一致链式存储适合于线性结构也适合于非线性结构链式存储适合于线性结构也适合于非线性结构链式存储适合于线性结构也适合于非线性结

8、构链式存储适合于线性结构也适合于非线性结构线性链表的基本运算：查找、插入、删除线性链表的基本运算：查找、插入、删除线性链表的基本运算：查找、插入、删除线性链表的基本运算：查找、插入、删除树：一种简单的非线性结构，所有元素之间具有明树：一种简单的非线性结构，所有元素之间具有明树：一种简单的非线性结构，所有元素之间具有明树：一种简单的非线性结构，所有元素之间具有明显的层次特性。显的层次特性。显的层次特性。显的层次特性。树的相关概念：在树结构中，每一个结点只有一个树的相关概念：在树结构中，每一个结点只有一个树的相关概念：在树结构中，每一个结点只有一个树的相关概念：在树结构中，每一个结点只有一个前件（

9、驱），称为父结点，没有前件（驱）的结点前件（驱），称为父结点，没有前件（驱）的结点前件（驱），称为父结点，没有前件（驱）的结点前件（驱），称为父结点，没有前件（驱）的结点只有一个，称为树的根结点，简称树的根。每一个只有一个，称为树的根结点，简称树的根。每一个只有一个，称为树的根结点，简称树的根。每一个只有一个，称为树的根结点，简称树的根。每一个结点可以有多个后件（继），称为该结点的子结点。结点可以有多个后件（继），称为该结点的子结点。结点可以有多个后件（继），称为该结点的子结点。结点可以有多个后件（继），称为该结点的子结点。没有后件（继）的结点称为叶子结点。没有后件（继）的结点称为叶子结点。没

10、有后件（继）的结点称为叶子结点。没有后件（继）的结点称为叶子结点。树的深度：一个结点所拥有的后件（继）树的深度：一个结点所拥有的后件（继）的个数称为该结点的度，所有结点中最大的个数称为该结点的度，所有结点中最大的度称为树的度。树的最大层次称为树的的度称为树的度。树的最大层次称为树的深度。深度。二叉树的特点：二叉树的特点：（1）非空二叉树只有一个根结点；）非空二叉树只有一个根结点；（2）每一个结点最多有两棵子树，且分）每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。别称为该结点的左子树与右子树。满二叉树：每一层结点数达到最大满二叉树：每一层结点数达到最大满二叉树：每一层结点数达到最大

11、满二叉树：每一层结点数达到最大 完全叉树：除最后一层外，其余每一层结点数达到最大，最完全叉树：除最后一层外，其余每一层结点数达到最大，最完全叉树：除最后一层外，其余每一层结点数达到最大，最完全叉树：除最后一层外，其余每一层结点数达到最大，最后一层结点或满，或右边连续缺少若干结点。后一层结点或满，或右边连续缺少若干结点。后一层结点或满，或右边连续缺少若干结点。后一层结点或满，或右边连续缺少若干结点。性质性质性质性质1 1：满二叉树的第：满二叉树的第：满二叉树的第：满二叉树的第i i层上有层上有层上有层上有2 i-12 i-1个结点，二叉树的第个结点，二叉树的第个结点，二叉树的第个结点，二叉树的第

12、i i层层层层 上至多有上至多有上至多有上至多有2 i-12 i-1（i i 1 1）个结点；）个结点；）个结点；）个结点；性质性质性质性质2 2：深度为：深度为：深度为：深度为h h的满二叉树共有的满二叉树共有的满二叉树共有的满二叉树共有2 h-12 h-1个结点，深度为个结点，深度为个结点，深度为个结点，深度为h h的二的二的二的二叉树中至多含有叉树中至多含有叉树中至多含有叉树中至多含有2 h-12 h-1个结点个结点个结点个结点 性质性质性质性质3 3：若在任意一棵二叉树中，有：若在任意一棵二叉树中，有：若在任意一棵二叉树中，有：若在任意一棵二叉树中，有n0n0个叶子结点，有个叶子结点，

13、有个叶子结点，有个叶子结点，有n2n2个个个个度为度为度为度为2 2的结点，则：的结点，则：的结点，则：的结点，则：n0=n2+1n0=n2+1；性质性质性质性质4:4:具有具有具有具有n n个结点的完全二叉树的深度为个结点的完全二叉树的深度为个结点的完全二叉树的深度为个结点的完全二叉树的深度为log2n+1,log2n+1,具有具有具有具有n n个结点的任意二叉树，其深度个结点的任意二叉树，其深度个结点的任意二叉树，其深度个结点的任意二叉树，其深度 至少为至少为至少为至少为 log2n+1log2n+1；其中；其中；其中；其中log2nlog2n表示取表示取表示取表示取log2nlog2n的

14、整数部分的整数部分的整数部分的整数部分 性质性质性质性质5 5：完全二叉树按层序（从根结点开始编号为完全二叉树按层序（从根结点开始编号为完全二叉树按层序（从根结点开始编号为完全二叉树按层序（从根结点开始编号为1 1，每层，每层，每层，每层从左到右）编号，某一结点编号为从左到右）编号，某一结点编号为从左到右）编号，某一结点编号为从左到右）编号，某一结点编号为k k，它若有左孩子结点，它若有左孩子结点，它若有左孩子结点，它若有左孩子结点，左孩子结点编号为左孩子结点编号为左孩子结点编号为左孩子结点编号为2k2k，它若有右孩子结点，右孩子结点编号，它若有右孩子结点，右孩子结点编号，它若有右孩子结点，右

15、孩子结点编号，它若有右孩子结点，右孩子结点编号为为为为2k+12k+1。由性质由性质由性质由性质5 5可推出：若完全二叉树有可推出：若完全二叉树有可推出：若完全二叉树有可推出：若完全二叉树有n n个结点，那该二个结点，那该二个结点，那该二个结点，那该二叉树有叉树有叉树有叉树有n-n/2n-n/2个叶子结点，其中个叶子结点，其中个叶子结点，其中个叶子结点，其中n/2n/2表示对表示对表示对表示对n/2n/2取取取取不大于不大于不大于不大于n/2n/2的最大整数。的最大整数。的最大整数。的最大整数。先序遍历先序遍历先序遍历先序遍历(D L R):(D L R):访问根结点，按先序遍历左子树，按先序

16、遍历右访问根结点，按先序遍历左子树，按先序遍历右访问根结点，按先序遍历左子树，按先序遍历右访问根结点，按先序遍历左子树，按先序遍历右子树。子树。子树。子树。中序遍历中序遍历中序遍历中序遍历(L D R):(L D R):按中序遍历左子树，访问根结点，按中序遍历右按中序遍历左子树，访问根结点，按中序遍历右按中序遍历左子树，访问根结点，按中序遍历右按中序遍历左子树，访问根结点，按中序遍历右子树。子树。子树。子树。后序遍历后序遍历后序遍历后序遍历(L R D):(L R D):按后序遍历左子树，按后序遍历右子树，访问根按后序遍历左子树，按后序遍历右子树，访问根按后序遍历左子树，按后序遍历右子树，访问

17、根按后序遍历左子树，按后序遍历右子树，访问根结结结结顺序表插入：顺序表插入：顺序表插入：顺序表插入：最好情况最好情况最好情况最好情况0 0，最坏情况，最坏情况，最坏情况，最坏情况n n，平均情况，平均情况，平均情况，平均情况n/2n/2顺序表删除：顺序表删除：顺序表删除：顺序表删除：最好情况最好情况最好情况最好情况0 0，最坏情况，最坏情况，最坏情况，最坏情况n-1,n-1,平均情况平均情况平均情况平均情况（n-1)/2n-1)/2顺序查找：顺序查找：顺序查找：顺序查找：最好情况最好情况最好情况最好情况1 1，最坏情况，最坏情况，最坏情况，最坏情况n n，平均情况，平均情况，平均情况，平均情况

18、（n+1)/2n+1)/2二分查找二分查找二分查找二分查找 :最好情况最好情况最好情况最好情况1 1，最坏情况，最坏情况，最坏情况，最坏情况log2nlog2n次次次次 堆排序的复杂度：堆排序的复杂度：堆排序的复杂度：堆排序的复杂度：nlog2n nlog2n 其余排序方法的运算次数：其余排序方法的运算次数：其余排序方法的运算次数：其余排序方法的运算次数：n(n-1)/2 n(n-1)/2 顺序查找的特点：顺序查找的特点：顺序查找的特点：顺序查找的特点：查找效率相对较低查找效率相对较低查找效率相对较低查找效率相对较低 适合无序线性表和有序的线性链表进行查找适合无序线性表和有序的线性链表进行查找适合无序线性表和有序的线性链表进行查找适合无序线性表和有序的线性链表进行查找二分法查找的特点：适合于顺序存储的有二分法查找的特点：适合于顺序存储的有序表序表；查找效率比顺序查找高；最坏情况查找效率比顺序查找高；最坏情况查询次数：查询次数：log2n次次