第二章 数据结构和算法初步1.ppt

数据结构和算法（2学时） 数据结构和算法的基本概念 流程图和NS图 1) 让同学们知道程序设计实际上应该是数据结构和算法的设计： 首先确定数据的表示方式(结构），然后确定处理步骤（算法）； 数据的结构决定了程序的结构，算法是离不开数据结构的；同时，通过对不同算法效率分析，让大家知道算法设计的重要意义。 2）学会用流程图和NS图来描述算法。 数据结构及算法（2学时） 数据结构及算法基本概念 流程图和NS图 一. 数据结构及算法基本概念 1. 数据表示决定程序结构 一. 数据结构及算法基本概念 一. 数据结构及算法基本概念 一. 数据结构及算法基本概念 一. 数据结构及算法基本概念 2. 数据结构的简单定义： 一. 数据结构及算法基本概念 2. 常见的处理对象之间的关系 一. 数据结构基本概念 一. 数据结构基本概念 一. 数据结构及算法基本概念 一. 数据结构及算法基本概念 一. 数据结构及算法基本概念 二.流程图和NS图 二. 线性表及几个简单算法 1. 冒泡排序 二. 线性表及几个简单算法 1. 冒泡排序 二. 线性表及几个简单算法 1. 冒泡排序 二. 线性表及几个简单算法 1. 冒泡排序 二. 线性表及几个简单算法 二. 线性表及几个简单算法 二. 线性表及几个简单算法 二. 线性表及几个简单算法 二. 线性表及几个简单算法 二. 线性表及几个简单算法 二. 线性表及几个简单算法 * 编写程序设计来求解实际问题时，首先必然要将“问题域对象变为求解域对象”。 数据的表示方式确定了您程序的结构和处理步骤，例如： 编写一个从一组数中找出最大数的程序。 1.数据表示决定程序结构 先以3个数为例： 有的同学想，高级语言中提供了关系运算和逻辑运算（如并且、或者运算），能否这样做： 3个数我们用a、b、c表示，最大数为max: if(a=ba==c) {max=a;}…… 这样做行吗？ 随着数的增加，不仅程序规模太大！而且对有些应用来说，没法确定处理步骤（例如排序）。 或者： max=a; if(b=max) {max=b;}…… 要解决这个问题，我们首先要考虑：不只要表示单个的数，而且要表示数之间的关系。从逻辑上看，我们可以描述如下：。 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.数据表示决定程序结构 牢记 ：数据的表示方式确定了您程序的结构和处理步骤！ 数据间是存在一定关系的。在解决实际问题时，不光要考虑单个数据本身，还需要考虑数据间的关系。 为了表示现实世界中各种复杂的关系，计算机科学家们抽象出了四种最基本的关系，现实世界中各种复杂的关系可由他们或他们之间的组合来表示。 数据结构是指有关系的数据的集合。 处理对象之间的关系通常可以用下面的逻辑结构进行描述： 树型结构： 图状结构： 线性结构： 集合结构： 例如：人机对弈。 在人机对弈问题中，计算机处理的对象主要是棋的“格局”，根据可能的格局选择走法。如下图： 格局之间是有关系的，但其关系通常不是线性的，因为从一个格局可以派生出许多格局，如下图： 当前格局 格局1.n 格局1.1 格局1.2 格局1 格局1.1.n 格局1.1.1 格局1.1.2 又例如：交通查询系统。 下面是某地区交通示意图。我们要开发一个交通查询系统，能回答从甲地到乙地如何费用最省、如何中转车次最少等问题。 A C B 100 120 它是指解决某一类特定类型问题的一系列步骤。 3.1算法的基本概念 3. 算法 例如：求