计算机软件技术之算法基础和数据结构基础

1、第第14讲讲 算法基础和数据结构基础算法基础和数据结构基础计算机基础科学系2007.08第7章 计算机软件技术湖南涉外经济学院返回主要教学内容主要教学内容算法基础1数据结构基础2小 结3计算机基础科学系湖南涉外经济学院返回学习目标学习目标1 了解算法的基本概念；掌握算法的三种基本结构；了解常见算法。 2 掌握数据的逻辑结构、物理存储结构的基本概念。3 掌握线性列表、堆栈、队列的基本操作；掌握树和二叉树的概念；掌握二叉树的特点、性质和遍历方案。计算机基础科学系湖南涉外经济学院返回重点与难点重点与难点 算法的概念、特征与设计原则，算法的描述与常用算法的实现思想为本讲的重点；数据结构的基本知识为本讲

2、的难点。计算机基础科学系湖南涉外经济学院返回1.算法基础算法基础算法是指解决问题的方法和步骤，是对解决某一问题方案的准确描述。算法算法Algorithm 如 ： 求 圆 的 面 积 问 题（s=r2 ） ，把这个问题交给计算机来处理，过程为先输入圆的半径，然后按面积计算公式计算，最后输出计算结果。描述如下：1.输入圆的半径2.计算圆的面积；s=r2；3.输出圆的面积s；上述这种解决问题的方法就是一个算法。计算机基础科学系湖南涉外经济学院返回有穷性有输入有输出确定性可行性算法中的每个步骤都能在有限时间内完成。算法中的所有运算都是基本的，都可以通过基本运算有限次实现之。算法的每一种运算有确定的确定

3、的意义，执行何种动作无二义无二义性性，目的明确。1.1 算法的概念算法的概念计算机基础科学系湖南涉外经济学院返回1.1 算法的概念算法的概念时间复杂度时间复杂度是指算法需要消耗的时间资源。 空间复杂度是指算法需要消耗的空间资源。 算法执行时间的增长率和 f(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) 计算机基础科学系湖南涉外经济学院返回正确性高效

4、率与低存储量需求可读性健壮性当输入的数据非法时，算法应当恰当地作出反映或进行相应处理。程序对于精心选择的、典型、苛刻且带有刁难性的几组输入数据能够得出满足要求的结果。计算机基础科学系湖南涉外经济学院返回1.2算法的三种基本结构算法的三种基本结构分支结构分支结构包括简单分支与选择分支结构。选择分支结构可以根据设定的条件，判断应该选择哪一条分支来执行。顺序结构顺序结构是指按程序语句行的编写顺序，逐条执行。循环结构循环结构是指按照一定的条件反复执行某一或某些处理步骤的结构。有两种循环语句：一种是先判断条件再执行循环体的结构称为当型循环结构；另一种是先执行循环体后判断条件的结构称为直到型循环结构。顺序

5、分支循环计算机基础科学系湖南涉外经济学院返回1.2算法的三种基本结构算法的三种基本结构输入/输出框处理框条件框起止框圆角矩形用于算法的起止平行四边形用于描述算法的输入与输出矩形用于算法数据的处理棱形框用于算法的判断有向箭头用于算法的流程指标计算机基础科学系湖南涉外经济学院返回1.2算法的三种基本结构算法的三种基本结构图1 算法c=a+b的流程图输入a、b的值开始c=a+b结束输出c 的值顺序计算机基础科学系湖南涉外经济学院返回1.2算法的三种基本结构算法的三种基本结构图2 简单分支图3 选择分支条件语句组1否是条件语句组1是否语句组2分支图4 把两个数由大到小输出的算法描述输出a、b是否ab吗

6、？输入a、b的值开始结束输出b、a例：计算机基础科学系湖南涉外经济学院返回1.2算法的三种基本结构算法的三种基本结构是条件循环体否图5 当型循环是否i99？S=0i=1S=S+ii=i+2开始结束输出S图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)=

7、78, a(6)=5678，j=6；a(3)与a(5)交换。i=3，a(3)=45, a(5)=3232,328,位置不变；845,两者交换位置；878，交换位置，823，交换位置。得出最小值为8。其它同理。冒泡排序计算机基础科学系湖南涉外经济学院返回1.3常见算法介绍常见算法介绍（3）插入排序 插入排序是最常用的排序技术之一，经常在扑克牌游戏中使用。游戏人员将每张拿到的牌插入到手中合适的位置，以便手中的牌以一定的顺序排列。计算机基础科学系湖南涉外经济学院返回1.3常见算法介绍常见算法介绍2.查找算法顺序查找计算机基础科学系湖南涉外经济学院返回1.3常见算法介绍常见算法介绍折半查找计算机基础科

8、学系湖南涉外经济学院返回1.3常见算法介绍常见算法介绍3.递归算法计算机基础科学系湖南涉外经济学院返回2.数据结构基础数据结构基础数据数据数据元素数据元素数据项数据项 数据结构是在整个计算机科学与技术领域上被广泛使用的术语，它被用来反映一个数据的内部构成，即一个数据由哪些成分数据构成，以什么方式构成，呈什么结构。数据结构有逻辑结构和物理结构之分。逻辑上的数据结构反映成分数据之间的逻辑关系，而物理上的数据结构反映成分数据在计算机内部的存储安排，它是数据结构的实现形式。数据结构作为一门学科，研究的内容主要包括数据的逻辑结构、数据的物理存储结构及对数据的操作（或算法）三个方面。计算机基础科学系湖南涉

9、外经济学院返回2.1线性列表线性列表线性表是一个含有n0个结点（数据元素）的有限序列，其中的结点，有且仅有一个开始结点和一个终端结点，其他结点有且仅有一个前驱和一个后继结点。线性表可分为广义线性表与限制线性表。广义线性表：可以在任何位置插入与删除数据；限制线性表：只能在列表两端增加与删除数据，如堆栈，队列计算机基础科学系湖南涉外经济学院返回2.2堆栈堆栈图10 出栈操作栈的操作有很多，基本操作有：栈的操作有很多，基本操作有：入栈，出栈和空三种。入栈，出栈和空三种。图9 入栈操作堆栈堆栈是一种执行是一种执行“后进先出后进先出”算法的数据结构。算法的数据结构。计算机基础科学系湖南涉外经济学院返回2

10、.3队列队列队列队列只允许在数据表的前端进行删除操作，而在数据列表的后端进行插入操只允许在数据表的前端进行删除操作，而在数据列表的后端进行插入操作。作。图11 计算机队列计算机基础科学系湖南涉外经济学院返回2.3队列队列队列的操作也很多，基本操作有：入列、出列和空三种队列的操作也很多，基本操作有：入列、出列和空三种图12 入列操作图13 出列操作计算机基础科学系湖南涉外经济学院返回2.4树树树的基本概念树的基本概念二叉树二叉树根结点根结点父结点父结点子结点子结点叶子结点叶子结点兄弟兄弟结点的度结点的度树的高（深）度树的高（深）度计算机基础科学系湖南涉外经济学院返回2.4树树ABCDEFGHIJ

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

12、点至多只有二棵子树，二叉树的子树有左、右之分，且其次序不能颠倒v二叉树的五种基本形态 空二叉树 仅有根结点 右子树为空 左子树为空左右子树均非空计算机基础科学系湖南涉外经济学院返回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树树前序遍历前序遍历(根左右根左右)：中序遍历中序遍历(左根右左根右) ：后序遍历后序遍历