一、算法的基本概念 二、数据结构 三、栈和队列 四、排序方法 五、二叉树

Presentation on theme: "一、算法的基本概念 二、数据结构 三、栈和队列 四、排序方法 五、二叉树"— Presentation transcript:

1 一、算法的基本概念 二、数据结构 三、栈和队列 四、排序方法 五、二叉树
基本数据结构与算法 一、算法的基本概念 二、数据结构 三、栈和队列 四、排序方法 五、二叉树

2 一、算法的基本概念 算法是解决某个特定问题的一种方法或一个过程。 2.算法具有以下五个特性： 1.算法的基本定义:
（1）有穷性 一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。 （2）确定性 算法中每一条指令必须有确切的含义。不存在二义性。且算法只有一个入口和一个出口。 （3）可行性 一个算法是可行的。即算法描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。 (4）输入 一个算法有零个或多个输入，这些输入取自于某个特定的对象集合。 (5）输出 一个算法有一个或多个输出，这些输出是同输入有着某些特定关系的量。

3 1.时间复杂度与空间复杂度是不相关的。 2.算法的效率与问题的规模和数据存贮结构有关
3.一个算法的评价主要从时间复杂度和空间复杂度来考虑 (1)时间复杂度：执行算法所需要的计算工作 量，用基本运算的执行次数来度量。 (2)空间复杂度:执行算法的内存空间。 注意 注意 1.时间复杂度与空间复杂度是不相关的。 2.算法的效率与问题的规模和数据存贮结构有关 1.时间复杂度与空间复杂度是不相关的。 2.算法的效率与问题的规模和数据存贮结构有关

4 二、数据结构 数据结构：就是相互之间存在一种或多种特定关系的数据元素的集合。 数据结构主要指逻辑结构和物理结构（存储结构） 线性表 栈
数据的逻辑结构 数据的存储结构 线性结构 非线性结构 顺序存储 链式存储 线性表 栈 队 树形结构 图形结构

5 1.数据之间的相互关系称为逻辑结构。 通常分为四类基本结构： （1）集合 结构中的数据元素除了同属于一种类型外，别无其它关系。 （2）线性结构 结构中的数据元素之间存在一对一的关系。 （3）树型结构 结构中的数据元素之间存在一对多的关系。 （4）图状结构或网状结构 结构中的数据元素之间存在多对多的关系

6 注意 2.数据结构在计算机中的表示称为数据的物理结构，又称为存储结构 通常分为两类基本结构：
（1）顺序存储结构:用数据元素在存储器中的相对位置来表示数据元素之间的逻辑关系。 （2）链式存储结构：在每一个数据元素中增加一个存放地址的指针，用此指针来表示数据元素之间的逻辑关系。 注意 逻辑结构和物理结构是描述数据结构的密不可分的两个方面。任何一个算法的设计取决于选定的逻辑结构，而算法的实现取决于依赖的存储结构

7 三、栈和队列 1.栈的定义和特点 栈和队列是两种特殊的线性表，是操作受限的线性表，仅在表的一端进行插入或删除操作。
定义：限定仅在表尾进行插入或删除操作的线性表，表尾—栈顶，表头—栈底，不含元素的栈称空栈 入栈(压栈):栈的插入操作 出栈(弹栈):删除操作 特点：先进后出（FILO）或后进先出（LIFO）

8 栈的示意图： 入栈 入栈 入栈 入栈 入栈 入栈 入栈 出栈 栈顶 图3.1栈的示意图 图3.1栈的示意图 图3.1栈的示意图
an an an an an an an an 栈s=(a1,a2,……,an) 栈s=(a1,a2,……,an) 栈s=(a1,a2,……,an) 栈s=(a1,a2,……,an) … 入栈顺序： a1,a2,……,an 入栈顺序： a1,a2,……,an 入栈顺序： a1,a2,……,an a2 a2 a2 a2 a2 a2 a2 a2 a2 出栈顺序： an,an-1,……,a1 栈底 栈底 栈底 栈底 栈底 栈底 a1

9 题1：假设数据1,2,3顺序入栈，入栈时可以随时出栈，问出栈序列有几种？
题2：设一个栈的输入序列为1、2、3、4，则借助栈所得到的输出序列不可能是（ ）。 A. 1、2、3、 B. 4、3、2、1 C. 1、3、4、 D. 4、1、2、3 总结： 栈是限定仅能在表尾一端进行插入、 删除操作的线性表； 2 栈的元素具有后进先出的特点；

10 特点： 2.队列的定义和特点 定义：队列特殊性在于限定插入在线性表的一端进行，删除在线性表的另外一端进行。
出队 front rear 通常我们将插入端称为队尾，用一个“队尾指针”指 示；而删除端被称为队头，用一个“队头指针”指示。 先进先出（First In First Out），简称为 FIFO线性表。 特点：

11 队列总结： 1.队列是限定仅能在表尾一端进行插入，表头一端删除操作的线性表； 2.队列中的元素具有先进先出的特点 3.循环队列 题：某循环队列的容量为50 ，头指针Front=5（指向队头元素的前一位置），尾指针rear=29（指向队尾元素），该循环队列共有_____元素

12 四、各种排序方法的综合比较 稳定 排序方法 平均时间 最坏情况 最好情况 辅助空间 稳定性 直接插入 折半插入 希尔排序 不稳定 冒泡排序
快速排序 简单选择 堆排序 归并排序 基数排序 O(n) O(n ) / O(nlog2n) O(n2 ) O(nlog2n ) O(d(n+rd) ) O(n2 ) O(n4/3 ) O(nlog2n) O(nlog2n ) O(d(n+rd) ) O(n2 ) O(nlog2n ) O(d(n+rd) ) / O(1) O(log2n) O(n) O(n+rd)

13 五、二叉树 二叉树是一类重要的非线性数据结构，是以分支关系定义的层次结构。 1.基本概念：
结点的度：树中每个结点具有的子树数或者后继结点数称为该结点的度（Degree）。度数为0的结点，即没有子树的结点叫终端结点或叶子结点。一棵树中各个结点度数的最大值叫做这个树的度。 结点的层次(level)——从根结点算起，根为第一层，它的孩子为第二层……

14 树的深度：树是一种层次结构，树中结点的层次（Level）是从根结点算起的。根结点为第一层，其儿子结点为第二层。其余各结点的层数逐层由上而下计算。一棵树中结点的最大层数叫做此树的深度或高度。
2.二叉树的定义及性质： 定义：一个二叉树是n个结点的有限集（n≥0），此集合或者是空集（n=0），或者是由一个根结点及两棵互不相交的、分别称为左子树和右子树的二叉树组成。 由上述定义可知，二叉树可以是空集，其根可以有空的左子树或右子树，或者左、右子树皆为空。 一般地，二叉树有五种基本形态

15 ○ 性质2：深度为k的二叉树至多有____个结点(k1) (a) A (b ) (c (d C (e
二叉树的性质与结论: 性质1：在二叉树的第i层(i  1)上至多有____个结点 性质2：深度为k的二叉树至多有____个结点(k1)

16 性质3：任意一棵二叉树T，如果其叶结点数为n0，度为2的结点数为n2，则_________
两种特殊的二叉树： 1.满二叉树：如果一个二叉树中，除最下一层的各结点度数为0以外，其它各层结点的度数均等于2，则此二叉树为满二叉树。 2.完全二叉树：如果一个二叉树各层都是“满”的，只是最下面一层从右边起连续缺n个结点，这种二叉树叫做完全二叉树。 n0=n2+1

17 题1.某二叉树中有N个度为2的结点，则二叉树的叶子结点是多少？
题2.一棵二叉树中共有70个叶子结点，80个度为1的结点，则该二叉树的总结点数？

18 二叉树的遍历 二叉树的遍历(Traversal)是指按一定的规律访问二叉树的每个结点，且每个结点只被访问一次的过程。 对二叉树的遍历过程实际上是将非线性结构的二叉树中的结点排列成一个线性序列的过程。

19 一个非空的二叉树由根结点及左、右子树这三个基本部分组成，因此若能依次遍历这三部分，便是遍历了整个二叉树。
在任一给定结点上，可以按某种次序执行三个操作：访问结点本身，遍历该结点左子树，遍历该结点右子树，操作排列次序： ① 左、根、右；③ 根、左、右；⑤ 左右根； ② 右、根、左；④ 根、右、左；⑥ 右、左、根； 由于实际问题一般都是要求左子树较右子树先遍历，故只采用其中①、③、⑤三种遍历次序，分别称为中序遍历、先序遍历和后序遍历。

20 先序遍历：先访问根结点，然后分别先序遍历左子树、右子树
中序遍历：先中序遍历左子树，然后访问根结点，最后中序遍历右子树 后序遍历：先后序遍历左右子树，然后访问根结点 按层次遍历：从上到下从，左到右访问各节点。

21 题1. 中序遍历序列：H，D，I，B，E，A，F，C，G。 先序遍历序列：A，B，D，H，I，E，C，F，G。 后序遍历序列：H，I，D，E，B，F，G，C，A。 题2.已知一棵二叉树 先序序列KAFGIBEDHJC和中序序列AGFKEDBHJIC 写出后序序列 题3.已知一颗二叉树 后序序列FBCGIEJDAH和中序序列BFGCHIEADJ 写出先序序列。

22 题2.后序遍历：GFADEJHBCIK 题3.前序遍历：HGBFCAEIDJ K A I B C D E F G H J A B C D E