[工学]算法基础1数据结构基础

《[工学]算法基础1数据结构基础》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

2、案的准确描述。算法Algorithm如：求圆的面积问题（s=πr2），把这个问题交给计算机来处理，过程为先输入圆的半径，然后按面积计算公式计算，最后输出计算结果。描述如下：1.输入圆的半径2.计算圆的面积；s=πr2；3.输出圆的面积s；上述这种解决问题的方法就是一个算法。计算机基础科学系算法的特征有穷性有输入有输出确定性可行性算法中的每个步骤都能在有限时间内完成。算法中的所有运算都是基本的，都可以通过基本运算有限次实现之。算法的每一种运算有确定的意义，执行何种动作无二义性，目的明确。1.1算法的概念计算机基础科学系1.1算法的概念时间复杂度是指算法需要消耗的时

3、间资源。空间复杂度是指算法需要消耗的空间资源。算法执行时间的增长率和f(n)的增长率相同，记作：T(n)=O(f(n))（a）x:=x+1（b）fori:=1tondox:=x+1（c）forj:=1tondofork:=1tondox:=x+1基本操作:加法操作时间复杂度:（a）O(1)（b）O(n)（c）O(n2)算法的复杂度计算机基础科学系算法设计的原则正确性高效率与低存储量需求可读性健壮性当输入的数据非法时，算法应当恰当地作出反映或进行相应处理。程序对于精心选择的、典型、苛刻且带有刁难性的几组输入数据能够得出满足要求的结果。计算机基础科学系1.2算法的三

4、种基本结构分支结构包括简单分支与选择分支结构。选择分支结构可以根据设定的条件，判断应该选择哪一条分支来执行。顺序结构是指按程序语句行的编写顺序，逐条执行。循环结构是指按照一定的条件反复执行某一或某些处理步骤的结构。有两种循环语句：一种是先判断条件再执行循环体的结构称为当型循环结构；另一种是先执行循环体后判断条件的结构称为直到型循环结构。顺序分支循环计算机基础科学系1.2算法的三种基本结构输入/输出框处理框条件框起止框圆角矩形用于算法的起止平行四边形用于描述算法的输入与输出矩形用于算法数据的处理棱形框用于算法的判断有向箭头用于算法的流程指标计算机基础科学系1.2算

5、法的三种基本结构图1算法c=a+b的流程图输入a、b的值开始c=a+b结束输出c的值顺序计算机基础科学系1.2算法的三种基本结构图2简单分支图3选择分支条件语句组1否是条件语句组1是否语句组2分支图4把两个数由大到小输出的算法描述输出a、b是否a>b吗？输入a、b的值开始结束输出b、a例：计算机基础科学系1.2算法的三种基本结构是条件循环体否图5当型循环是否i<=99S=0i=1S=S+ii=i+2输出S开始结束图6计算1+3+5+7+...+99的当型循环循环例：计算机基础科学系1.2算法的三种基本结构图7直到型循环否条件循环体是否是i>99？S=0i=1S=

6、S+ii=i+2开始结束输出S图8计算1+3+5+7+...+99的直到型循环循环例：计算机基础科学系1.3常见算法介绍i=1，a(1)=23，a(4)=8<23，j=4；a(1)与a(4)交换。i=2，a(2)=78，a(3)=45<78，j=3；a(4)=23<45，k=4；a(2)与a(4)交换。i=4，a(4)=78,a(5)=45<78，j=5；a(4)与a(5)交换。i=5，a(5)=78,a(6)=56<78，j=6；a(3)与a(5)交换。i=3，a(3)=45,a(5)=32<45，j=5；a(3)与a(5)交换。⑴选择排序1.排序算法计算机基

7、础科学系1.3常见算法介绍第一步：从最后一个数开始与前面的数比较56>32,32>8,位置不变；8<45,两者交换位置；8<78，交换位置，8<23，交换位置。得出最小值为8。其它同理。⑵冒泡排序计算机基础科学系1.3常见算法介绍（3）插入排序插入排序是最常用的排序技术之一，经常在扑克牌游戏中使用。游戏人员将每张拿到的牌插入到手中合适的位置，以便手中的牌以一定的顺序排列。计算机基础科学系1.3常见算法介绍2.查找算法⑴顺序查找计算机基础科学系1.3常见算法介绍⑵折半查找计算机基础科学系1.3常见算法介绍3.递归算法计算机基础科学系2.数据结构基础数据数据元素数据

8、项数据结构是在整个计算机