数据结构和算法初步.ppt

《数据结构和算法初步.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

2、。数据的表示方式确定了您程序的结构和处理步骤，例如：编写一个从一组数中找出最大数的程序。一.数据结构及算法基本概念1.数据表示决定程序结构先以3个数为例：有的同学想，高级语言中提供了关系运算和逻辑运算（如并且、或者运算），能否这样做：3个数我们用a、b、c表示，最大数为max:if(a>=b&&a>==c){max=a;}……这样做行吗？随着数的增加，不仅程序规模太大！而且对有些应用来说，没法确定处理步骤（例如排序）。或者：max=a;if(b>=max){max=b;}……一.数据结构及算法基本概念

3、要解决这个问题，我们首先要考虑：不只要表示单个的数，而且要表示数之间的关系。从逻辑上看，我们可以描述如下：。1.数据表示决定程序结构ai,1≤i≤n;在这种描述下，a1是第1个元素，an是最后一个元素，除第一和最后元素外，ai的前一个元素为ai-1，后一个元素为ai+1。在该结构下处理步骤描述如下：假设第1个数为最大数max；i的初始值为2，重复以下步骤N-1次：如ai大于max，则max=ai,i=i+1;一.数据结构及算法基本概念再看一个例子：确定某门课程各个分数的人数。1.数据表示决定程序结构牢

4、记：数据的表示方式确定了您程序的结构和处理步骤！一.数据结构及算法基本概念2.数据结构的简单定义：数据间是存在一定关系的。在解决实际问题时，不光要考虑单个数据本身，还需要考虑数据间的关系。为了表示现实世界中各种复杂的关系，计算机科学家们抽象出了四种最基本的关系，现实世界中各种复杂的关系可由他们或他们之间的组合来表示。数据结构是指有关系的数据的集合。一.数据结构及算法基本概念2.常见的处理对象之间的关系处理对象之间的关系通常可以用下面的逻辑结构进行描述：树型结构：图状结构：线性结构：集合结构：一.数据结

5、构基本概念例如：人机对弈。在人机对弈问题中，计算机处理的对象主要是棋的“格局”，根据可能的格局选择走法。如下图：格局之间是有关系的，但其关系通常不是线性的，因为从一个格局可以派生出许多格局，如下图：当前格局格局1.n格局1.1格局1.2格局1格局1.1.n格局1.1.1格局1.1.2一.数据结构基本概念又例如：交通查询系统。下面是某地区交通示意图。我们要开发一个交通查询系统，能回答从甲地到乙地如何费用最省、如何中转车次最少等问题。ACB100120一.数据结构及算法基本概念它是指解决某一类特定类型问题

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

7、复杂度和空间复杂度。3.3算法效率在上面求最大公约数的例子中，大家考虑还有哪些方法，时间复杂度如何？霍尔排序与插入排序运行时间演示比较。货郎担问题简介。空间复杂度的问题，大家考虑一下如何将数组倒排。向量旋转问题算法比较。二.流程图和NS图二.线性表及几个简单算法1.冒泡排序1.2过程演示（5，4，2，3，1由小到大排序）54231第1趟：45231425314235142315在剩余的4个数中进行第2趟……二.线性表及几个简单算法1.冒泡排序1.2过程演示（5，4，2，3，1由小到大排序）54231第

8、1趟：42315第2趟：23145第3趟：21345第4趟：12345在这种方法中，第i趟是将从1到的n-i+1依次比较，结果是将这n-i+1个中最大“沉入”在n-i+1的位置上；我们还可以从后面向前面比较（向上“冒泡”），如：二.线性表及几个简单算法1.冒泡排序1.3“冒泡”过程演示（小的向前“冒”）54231第1趟：542131与3比较541231与2比较514231与4比较154231与5比较其余各趟略……实际上，我们可以改进上面算法：一旦发现在某