数据结构及算法二级培训.ppt

数据结构与算法 第1章 绪论 1.1 什么是数据结构 1.2 基本概念和术语 1.3 抽象数据类型的表示与实现 1.4 算法与算法分析 1.1 什么是数据结构 一、计算机解决问题的一般过程。 1、建立数学模型。 2、根据数学模型，设计算法。 3、编写程序，调试直至问题的最终解决。 二、数值问题与非数值问题。 数值问题就是我们平时所说的计算问题，如已知圆的半径，要求圆的面积。非数值问题就是问题中涉及的对象不能用数来表达的那些问题。 1）数值问题 例1 已知：游泳池的长length和宽wide，求面积area。分析：问题涉及的对象：游泳池的长length 宽wide，面积area；对象之间的关系：area=length?wide； 2）非数值问题 例 2 已知研究生选课情况，安排课程考试的日程。 研究生选课情况表 分析：◆ 问题涉及的对象：课程； ◆ 课程之间的关系：同一个研究生选修的不能按排在同一时间内考试； 课程及课程之间的关系可用如下所示的图表示： 课程考试安排问题转化为图的着色问题 用尽可能少的颜色为该图的每个顶点着色，使相邻的顶点着上不同的颜色； 每一种颜色代表一个考试时间，着上相同颜色的顶点是可以按排在同一时间考试的课程； 设G表示课程关系图，集合V包含图G中所有尚未着色的顶点，NEW表示可以用新颜色着色的顶点集合。 I=1；WHILE V 非空 DO 置 NEW 为空集合； FOR 每个 v ?V DO IF v 与NEW 中所有的结点间都没有边  从 V 中去掉v；将 v 加入NEW ； （第I天考试课程为NEW中顶点所对应的课程） 以某种形式输出NEW中顶点所对应的课程； I=I+1； 通过对上个问题的分析，在这个问题的分析解决的过程中我们遇到了以下几个问题： 1、如何表示节点以及它们之间的关系（相邻接） 2、在计算机中如何存储。 3、相应的操作如何描述。（染色过程） 3）数值问题与非数值问题的比较 数值问题 已知游泳池的长length, 和宽wide,求面积area。 （1）问题涉及的对象：length, wide,area 是实数 可用数值表示 ； （2）对象之间的关系 ：area=length?wide 可用方程或 函数表示 ； （3）数据存储：可用程序设计语言中的实型变量存储； （4）问题求解：用某种计算方法求解； 已知研究生选课情况，安排课程考试的日程。 1）问题涉及的对象：课程 可用课程名表示,不能用数值表示 2）对象之间的关系： 同一研究生选修的课程不能安排在同一 时间考试，同一研究生选修的课程之间有某种“冲突”关系 ——课程之间的这种关系不能用方程或函数表示 3）数据及数据之间的关系如何存储？ 4）如何求解 ？ 非数值数据之间的结构关系，如何表示，如何存储，如何处理的问题。 数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及他们之间关系和操作等的学科。 1.2 基本概念和术语 1、数据：一切能够输入到计算机中并被计算机程序处理的信息，包括文字、表格、图象等，都称为数据。例如，一个个人书库管理程序所要处理的数据可能是一张如表1-1所示的表格。 2．数据元素 数据元素（也叫节点），它是组成数据的基本单位。在程序中通常作为一个整体进行考虑和处理。例如，在表1-1所示的个人书库中，为了便于处理，把其中的每一行（代表一本书）作为一个基本单位来考虑，故该数据由10个结点构成。 一般情况下，一个结点中含有若干个字段（也叫数据项）。例如，在表1-1所示的表格数据中，每个结点都有登录号、书号、书名、作者、出版社和价格等六个字段构成。字段是构成数据的最小单位。 3、数据对象：是性质相同的数据元素的集合，是数据的一个子集。例如， 整数数据对象的集合N={0，±1，±2，……} ， 字母数据对象的集合C={‘A’,’B’,……’Z’}。 4、数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。 数据元素之间的相互关系称为结构。 根据数据结构之间关系，