算法基础和数据结构基础.ppt

1、第14讲 算法基础和数据结构基础,计算机基础科学系 2007.08,第7章 计算机软件技术,计算机基础科学系,主要教学内容,计算机基础科学系,学习目标,计算机基础科学系,重点与难点,算法的概念、特征与设计原则，算法的描述与常用算法的实现思想为本讲的重点；数据结构的基本知识为本讲的难点。,计算机基础科学系,1.算法基础,计算机基础科学系,算法的特征,算法中的每个步骤都能在有限时间内完成。,算法中的所有运算都是基本的，都可以通过基本运算有限次实现之。,算法的每一种运算有确定的意义，执行何种动作无二义性，目的明确。,1.1 算法的概念,计算机基础科学系,1.1 算法的概念,算法执行时间的增长率和 f

2、(n) 的增长率相同，记作：T(n) = O(f(n) （a）x:=x+1 （b）for i:=1 to n do x:=x+1 （c） for j:=1 to n do for k:=1 to n do x:=x+1 基本操作: 加法操作 时间复杂度: （a）O(1) （b）O(n) （c）O(n2),算法的复杂度,计算机基础科学系,算法设计的原则,当输入的数据非法时，算法应当恰当地作出反映或进行相应处理。,程序对于精心选择的、典型、苛刻且带有刁难性的几组输入数据能够得出满足要求的结果。,计算机基础科学系,1.2算法的三种基本结构,分支结构包括简单分支与选择分支结构。选择分支结构可以根据设定

3、的条件，判断应该选择哪一条分支来执行。,顺序结构是指按程序语句行的编写顺序，逐条执行。,循环结构是指按照一定的条件反复执行某一或某些处理步骤的结构。 有两种循环语句：一种是先判断条件再执行循环体的结构称为当型循环结构；另一种是先执行循环体后判断条件的结构称为直到型循环结构。,计算机基础科学系,1.2算法的三种基本结构,输入/输出框,处理框,条件框,起止框,计算机基础科学系,1.2算法的三种基本结构,图1 算法c=a+b的流程图,计算机基础科学系,1.2算法的三种基本结构,图2 简单分支,图3 选择分支,图4 把两个数由大到小输出的算法描述,例：,计算机基础科学系,1.2算法的三种基本结构,图5

4、 当型循环,图6 计算1+3+5+7+.+99的当型循环,例：,计算机基础科学系,1.2算法的三种基本结构,图7 直到型循环,图8 计算1+3+5+7+.+99的直到型循环,例：,计算机基础科学系,1.3常见算法介绍,i=1，a(1)=23，a(4)=823，j=4；a(1)与a(4)交换。,i=2，a(2)=78，a(3)=4578，j=3； a(4)=2345，k=4； a(2)与a(4)交换。,i=4，a(4)=78, a(5)=4578，j=5；a(4)与a(5)交换。,i=5，a(5)=78, a(6)=5678，j=6；a(3)与a(5)交换。,i=3，a(3)=45, a(5)=

5、3245，j=5；a(3)与a(5)交换。,选择排序,1.排序算法,计算机基础科学系,1.3常见算法介绍,第一步：从最后一个数开始与前面的数比较5632,328,位置不变；845,两者交换位置；878，交换位置，823，交换位置。得出最小值为8。,其它同理。,冒泡排序,计算机基础科学系,1.3常见算法介绍,（3）插入排序 插入排序是最常用的排序技术之一，经常在扑克牌游戏中使用。游戏人员将每张拿到的牌插入到手中合适的位置，以便手中的牌以一定的顺序排列。,计算机基础科学系,1.3常见算法介绍,2.查找算法,顺序查找,计算机基础科学系,1.3常见算法介绍,折半查找,计算机基础科学系,1.3常见算法介

6、绍,3.递归算法,计算机基础科学系,2.数据结构基础,数据,数据元素,数据项,数据结构是在整个计算机科学与技术领域上被广泛使用的术语，它被用来反映一个数据的内部构成，即一个数据由哪些成分数据构成，以什么方式构成，呈什么结构。数据结构有逻辑结构和物理结构之分。逻辑上的数据结构反映成分数据之间的逻辑关系，而物理上的数据结构反映成分数据在计算机内部的存储安排，它是数据结构的实现形式。数据结构作为一门学科，研究的内容主要包括数据的逻辑结构、数据的物理存储结构及对数据的操作（或算法）三个方面。,计算机基础科学系,2.1线性列表,线性表是一个含有n0个结点（数据元素）的有限序列，其中的结点，有且仅有一个开

7、始结点和一个终端结点，其他结点有且仅有一个前驱和一个后继结点。,线性表可分为广义线性表与限制线性表。 广义线性表：可以在任何位置插入与删除数据； 限制线性表：只能在列表两端增加与删除数据，如堆栈，队列,计算机基础科学系,2.2堆栈,图10 出栈操作,栈的操作有很多，基本操作有： 入栈，出栈和空三种。,图9 入栈操作,堆栈是一种执行“后进先出”算法的数据结构。,计算机基础科学系,2.3队列,队列只允许在数据表的前端进行删除操作，而在数据列表的后端进行插入操作。,图11 计算机队列,计算机基础科学系,2.3队列,队列的操作也很多，基本操作有：入列、出列和空三种,图12 入列操作,图13 出列操作,

8、计算机基础科学系,2.4树,树的基本概念,二叉树,根结点,父结点,子结点,叶子结点,兄弟,结点的度,树的高（深）度,计算机基础科学系,2.4树,A: 是根结点,同时是B、C、D结点的父结点或双亲结点 B: 是E、F的父结点，E、F是B的子结点或孩子结点 J、K、L、F、G、I：是叶子节点,B的子孙为 E、F、J、K,B,C,D互为兄弟,结点A的层次：1 结点L的层次：4,树的高度： 4,计算机基础科学系,2.4树,树的种类有很多，如无序树、有序树、二叉树和完全二叉树等。 1、二叉树的概念 二叉树是每个结点最多有两个子树的有序树，这两个子树分别称为左子树和右子树，而每一棵子树又是二叉树。 2、二

9、叉树的特点 每个结点至多只有二棵子树，二叉树的子树有左、右之分，且其次序不能颠倒,二叉树的五种基本形态,计算机基础科学系,2.4树,3.二叉树的性质 性质1：二叉树的第i层上至多有2 i-1（i 1）个结点。 证明：根据二叉树的特点，结论是显然的。（用归纳法证明）。,性质2：深度为H的二叉树中至多2H-1个结点。,性质3：具有n个结点的二叉树的最小高度H为log2n+1。,计算机基础科学系,2.4树,(1)前序遍历 (NLR) (2)中序遍历 (LNR) (3)后序遍历 (LRN),访问根结点 按照前序遍历顺序访问根结点的左子树按照前序遍历顺序访问根结点的右子树,按中序遍历顺序访问根结点的左子树 访问根结点 按中序遍历顺序访问根结点的右子树,按后序遍历顺序访问根结点的左子树 按后序遍历顺序访问根结点的右子树 访问根结点,（4）二叉树的遍历,计算机基础科学系,2.4树,前序遍历(根左右)：,中序遍历(左根右) ：,后序遍历(左右根) ：,A B C D E F,C B D A E F,C D B F E A