数据结构和算法初步.ppt

1、数据结构和算法（2学时）,数据结构和算法的基本概念 流程图和NS图 1) 让同学们知道程序设计实际上应该是数据结构和算法的设计： 首先确定数据的表示方式(结构），然后确定处理步骤（算法）； 数据的结构决定了程序的结构，算法是离不开数据结构的；同时，通过对不同算法效率分析，让大家知道算法设计的重要意义。 2）学会用流程图和NS图来描述算法。,数据结构及算法（2学时）,数据结构及算法基本概念 流程图和NS图,一. 数据结构及算法基本概念 1. 数据表示决定程序结构,编写程序设计来求解实际问题时，首先必然要将“问题域对象变为求解域对象”。,数据的表示方式确定了您程序的结构和处理步骤，例如：,编写一个

2、从一组数中找出最大数的程序。,一. 数据结构及算法基本概念,1.数据表示决定程序结构,先以3个数为例：,有的同学想，高级语言中提供了关系运算和逻辑运算（如并且、或者运算），能否这样做：,3个数我们用a、b、c表示，最大数为max: if(a=b,这样做行吗？,随着数的增加，不仅程序规模太大！而且对有些应用来说，没法确定处理步骤（例如排序）。,或者： max=a; if(b=max) max=b;,一. 数据结构及算法基本概念,要解决这个问题，我们首先要考虑：不只要表示单个的数，而且要表示数之间的关系。从逻辑上看，我们可以描述如下：。,1.数据表示决定程序结构,ai,1 i n;,在这种描述下，

3、a1是第1个元素，an是最后一个元素，除第一和最后元素外， ai的前一个元素为ai-1，后一个元素为ai+1。在该结构下处理步骤描述如下：,假设第1个数为最大数max； i的初始值为2，重复以下步骤N-1次： 如ai大于max，则max=ai,i=i+1;,一. 数据结构及算法基本概念,再看一个例子：确定某门课程各个分数的人数。,1.数据表示决定程序结构,牢记 ：数据的表示方式确定了您程序的结构和处理步骤！,一. 数据结构及算法基本概念 2. 数据结构的简单定义：,数据间是存在一定关系的。在解决实际问题时，不光要考虑单个数据本身，还需要考虑数据间的关系。,为了表示现实世界中各种复杂的关系，计算

4、机科学家们抽象出了四种最基本的关系，现实世界中各种复杂的关系可由他们或他们之间的组合来表示。,数据结构是指有关系的数据的集合。,一. 数据结构及算法基本概念 2. 常见的处理对象之间的关系,处理对象之间的关系通常可以用下面的逻辑结构进行描述：,一. 数据结构基本概念,例如：人机对弈。,在人机对弈问题中，计算机处理的对象主要是棋的“格局”，根据可能的格局选择走法。如下图：,格局之间是有关系的，但其关系通常不是线性的，因为从一个格局可以派生出许多格局，如下图：,一. 数据结构基本概念,又例如：交通查询系统。,下面是某地区交通示意图。我们要开发一个交通查询系统，能回答从甲地到乙地如何费用最省、如何中

5、转车次最少等问题。,一. 数据结构及算法基本概念,它是指解决某一类特定类型问题的一系列步骤。,3.1算法的基本概念,3. 算法,例如：求2个整数的最大公约数。,我们拿变量M、N来表示这两正整数。采用著名的欧几里德辗转相除法来解决该问题，步骤如下： 1）M除以N，得到余数R; 2）判断 R0，正确则 N 即为“最大公约数”，否则下一步； 3) 将 N 赋值给 M，将 R 赋值给 N，重做第一步。,一. 数据结构及算法基本概念,3.2算法的5个特性,3. 算法,能行性；确定性；有0或多个输出；有1或多个输出；有穷性。,一. 数据结构及算法基本概念,3. 算法,一个算法的好坏，正确是基本前提，同时主

6、要要考虑其所花的时间和所占的空间，即时间复杂度和空间复杂度。,3.3算法效率,在上面求最大公约数的例子中，大家考虑还有哪些方法，时间复杂度如何？,霍尔排序与插入排序运行时间演示比较。,货郎担问题简介。,空间复杂度的问题，大家考虑一下如何将数组倒排。,向量旋转问题算法比较。,二.流程图和NS图,二. 线性表及几个简单算法 1. 冒泡排序,1.2 过程演示（5，4，2，3，1由小到大排序）,在剩余的4个数中进行第2趟,二. 线性表及几个简单算法 1. 冒泡排序,1.2 过程演示（5，4，2，3，1由小到大排序）,在这种方法中，第i趟是将从1到的n-i+1依次比较，结果是将这n-i+1个中最大“沉入

7、”在n-i+1的位置上；,我们还可以从后面向前面比较（向上“冒泡”），如：,二. 线性表及几个简单算法 1. 冒泡排序,1.3 “冒泡”过程演示（小的向前“冒”）,其余各趟略,实际上，我们可以改进上面算法：一旦发现在某趟中，没有发生交换，则表明已经排序好。,二. 线性表及几个简单算法 1. 冒泡排序,1.4 算法分析,最好情况下比较n-1此，且不需移动位置；最坏情况下（逆序），比较和移动n(n-1)/2次；,2. 选择排序,第1步， 从n个数中选择最小（大）的数作为第1 个数；,第i (1in)从n-i+1个数中选择最小（大）的数作为第i 个数；当i从1变化到n-1后，排序完成。,第2步， 从

8、n-1个数中选择最小（大）的数作为第2个数；,二. 线性表及几个简单算法,2. 选择排序,2.1 过程演示（5，4，2，3，1由小到大排序）,在剩余的4个数中进行第2趟,实际上，我们可以改进上面算法：不需要每次比较都交换，只需要找到最小数的位置后，才交换。,二. 线性表及几个简单算法,2. 选择排序,2.2 算法分析,根据本算法的思想，该主要运算是比较2个数的大小，每趟比较完成后需要将2个数互换。请考虑该算法比较的次数和互换的次数。,比较次数：(n-1)+(n-2)+1=n(n-1)/2=O(n2)； 互换次数：最小为0，最大为n-1;运算3(n-1)次；,所以本算法的优化思想一种是考虑如何减

9、少比较次数。由于第一次比较的次数不可能减少，那么前面比较的结果能否用于后面的比较呢？答案是肯定的，请大家考虑一下8个队比赛决出前3名至少需要多少场比赛？,二. 线性表及几个简单算法,2. 选择排序,2.3 算法优化(参考）,下面我们来将9，38，26，17，8，85排序。,这实际上是在一些书中叫做锦标赛排序的算法，它除第1此比较需n-1次外，其它每次比较都只需要log2n+1次；所以其时间复杂度为O(n log2n),二. 线性表及几个简单算法,3. 顺序查找,3.1 基本思路,从第1个数开始，依次与 ai (1in)比较，如相等，则成功结束；否则表示查找失败。,二. 线性表及几个简单算法,4. 折半查找,4.1 基本思路,针对已排好顺序的表进行查找。使用2个值low和high来表示要查找值所在的区间low,hight,另外定义区间的中间位置mid=low+hight/2;low的初始值分别为1和n； 1. 首先将查找值与中间位置值进行比较，若相等则成功，转结束； 2. 否则如其大于中间值，则将 low=mid+1,hight不变; mid=low+hight/2转步骤1； 3. 如其小于中间值，则将 hight=mid-1,low不变; mid=low+hight/2,转步骤1； 4.