数据结构：第1章 绪论.ppt

Return 主要教学内容： 1.1 本课程的研究对象； 1.2 数据结构的有关基本概念； 1.3 数据结构的分类及表示； 1.4 算法及算法分析（算法评价） 1.1 本课程研究的问题 计算机的发展 软件 硬件 应用领域 数据处理的种类和能力 数据 数值数据 非数值数据 数 (整数,实数) 字符 字符串 文字 图形 图象 声音 数据：客观对象的符号表示 数学中的整数、实数， 课程名，地名、书名 程序 原始数据结果数据 数值问题与非数值问题 1）数值问题 例1 已知：游泳池的长len和宽wide，求面积area 设计 求解问题的方法 编程 main ( ) int len, wide ,area ; scanf (“%d %d%n”, area=len*wide ; printf (“area=%d”,area); 1.1 本课程研究的问题 建模型： 问题涉及的对象：游泳池的长len 宽wide，面积area； 对象之间的关系：area=lenwide 学号 姓名 性别 出生日期 籍贯 入学成绩 所在班级 00201 杨润生 男 82/06/01 广州 561 00计算机2 00102 石磊 男 83/12/21 汕头 512 00计算机1 00202 李梅 女 83/02/23 阳江 532 00计算机2 00301 马耀先 男 82/07/12 广州 509 00计算机3 2）非数值问题 例 2 已知某级学生情况 , 要求分班按入学成绩排列顺序。 1.1 本课程研究的问题 在这类文档管理的数学模型中, 计算机处理的对象之间通常存在着一种最简 单的线性关系 , 这类数学模型称为线性模型。 1.1 本课程研究的问题 例 3 迷宫问题。在迷宫中，每走到一处，接下来可走 的通路有三条。计算机处理的这类对象之间通常不存 在线性关系。若把从迷宫入口处到出口的过程中所有 可能的通路都画出，则可得一棵“树” 入口 出口 城市间交通网问题 1.1 本课程研究的问题 数据结构的研究问题： 非数值数据之间的结构关系， 及如何表示，如何存储，如何处理。 本课程讨论的问题： 应用中常用的几种数据间的结构关系， 及如何表示,如何存储，如何处理。 12 数据结构的有关概念 数据：客观对象的符号表示。 例如：学号，姓名，班名都是数据。 数据元素：数据的基本单位。相当于“记录”,在计算机程序中通常作为 一个整体考虑和处理 数据项: 相当于记录的“域”, 是数据的不可分割的最小单位,如学号 数据对象：性质相同的数据元素的集合. 例如: 所有班名相同的记录集合 数据结构：是相互间存在关系的数据元素集合。 1.2 数据结构的有关概念 对每种数据结构，主要讨论如下两方面的问题： 1） 数据的逻辑结构，数据结构的基本操作； 2） 数据的存储结构，数据结构基本操作的实现； 数据的逻辑结构： 数据之间的结构关系，是具体关系的抽象。 12 数据结构的有关概念 数据结构的基本操作： 指对数据结构的加工处理 数据的存储结构 (物理结构)： 数据结构在计算机内存中的表示 数据结构基本操作的实现： 基本操作在计算机上的实现（方法) 某班学生基本情况登记表，记录了每个学生的学号 姓名 专业 政 治 面貌 ，表中的记录是按学生的学号顺序排列的。 学号 姓名 专业 政治面藐 001 王洪 计算机 党员 002 孙文 计算机 团员 003 谢军 计算机 团员 004 李辉 计算机 团员 005 沈祥福 计算机 党员 006 余斌 计算机 团员 007 巩力 计算机 团员 008 孔令辉 计算机 团员 学生基本情况登记表的图示 001003002004006005008007 学生间学号顺序关系 是一种线性结构关系 例 一 常用的数据结构 1） 集合 2） 线性结构 3） 树结构 4） 图结构 5）其它复杂结构 1.3 数据结构的分类及表示 家族的族谱 假设某家族有10个成员A， B， C， D， E， F， G， H，I， J，他们之 间的血缘关系可以用如下图表示。 J I A CBD HGFE 13 数据结构的分类及表示 例 二数据结构的表示 图示表示 图示表示是由顶点和边构成的图，其中顶点表示数据 ，边表示数据之 间的结构关系； 001003002004006005008007 学生基本情况表的图示表示 J I A CBD HGFE 家族树的图示表示 13 数据结构的分类及表示 学生基本情况表的二元组表示（D，S） 二元组表示 二元组表示是用一个二元组（D，S）表示数据结构， 其中 D 是数据元素 集合，S 是 D 上关系的集合。 D = 001，002，003，004，005，006，007，008 S = R R= , , 家族树的二元组表示（D，S） D = A，B，C，D，E，F，G，H，I，J S = R R = A,B, 13 数据结构的分类及表示 J I A CBD HGFE 001003002004006005008007 14 算法与算法分析 1.4 算法与算法分析 一 算法的概念 算法是求解问题的操作序列 算法的基本特征： 1）输入：0个或多个输入； 2）输出：1个或多个输出； 3）有穷性：算法必须在有限步内结束； 4）确定性：组成算法的操作必须清晰无二义性。 5）可行性：组成算法的操作必须能够在计算机上实现。 求两个正整数 m，n 中的最大数MAX的算法 （1）若 m n 则 m