数据结构 （二版）.pptVIP

数据结构 （第二版） 第一章 绪论 1.1 学习数据结构的意义及要求 1.2 数据结构的主要内容 1.3 基本术语 1.4 算法描述及分析 1.1 学习数据结构的意义及要求 一. 意义 1. 算法和数据结构是计算机科学的两大支柱 1.1 学习数据结构的意义及要求 2. 数据结构是程序设计的基础 Program=Algorithms+Data Structure 数据结构是设计OS、DBMS、编译等系统程序和各种应用程序 的重要基础 1.1 学习数据结构的意义及要求 3. 数据结构是计算机专业的一门综合性专业基础课，是一门理论与实际紧密结合的基础课。 是计算机专业本科生必修学位课程 是计算机研究生入学考试必考科目 是软件人员水平考试内容 1.1 学习数据结构的意义及要求 4. 数据结构与计算机科学技术其他相关领域的关系 1.1 学习数据结构的意义及要求 二. 要求 1. 掌握各类基本数据结构类型 和相应的存储结构 2. 提高阅读 和编写算法 的能力 3. 能针对给定问题，选择相适应的数据结构， 并能设计和分析算法 1.2 数据结构的主要内容 例1： 99080-33202670610054510102780618748 1.2 数据结构的主要内容 例2: 电话号码簿 (a1，b1) (a2，b2)…(an，bn) 其中： ai为某人姓名，bi为该人的电话号码。 要求：设计一个算法，给定一个姓名时， 能查出此人的电话号码。 1.2 数据结构的主要内容 例3：大学学生管理机构 学校 　　　　一系　　．．．八系　．．． 　　　　　　　一年级　二年级　三年级　四年级　 　　　　　　　１班　．．．８班 　　　　　　　　张三．．．李四 1.2 数据结构的主要内容 例４：图书目录管理 设每个书目含：书名，作者，登录号，分类，出版年月 对图书目录常有如下操作： 查找：某书在书库中是否存在？ 插入：购进新书时的登录； 删除：报废或丢失的书，需从目录中去掉； 1.2 数据结构的主要内容 综上所述： 《DS》主要研究内容： 数据的各种逻辑结构和物理结构，以及它们之间的相应关系； 对每种结构定义相适应的各种运算； 设计出相应的算法； 分析算法的效率。 数据结构与问题求解 1. 在计算机中建立一个与实际问题有比较密切对应关系的模型； 2. 计算机内部的数据 表示了需要被处理的实际对象，包括其内在的性质和关系； 3. 处理这些数据的程序 则模拟对象领域中的实际过程； 4. 将计算机程序的运行结果 在实际领域中给予解释，便得到实际问题的解。 问题求解例子--五叉路口交通管理系统设计 交叉路口图式模型 将一种通行方向用一个结点表示(椭圆)； 在不能同时行驶的结点间画一条连线； 求解方法（求着色问题的近似解） 1. 选出未着色的结点，并用该新颜色上色； 2. 寻找仍未着色的结点，如果某结点与新颜色结点没有边相连，则将该结点用该颜色上色。 1.３ 基本术语 数据（Data)：所有能被计算机处理的符号的集合。 数据元素（Data Element）：是数据这个集合中的一个个体。 设给定数据集合为： 　D={d1，d2，．．．，dn} 则di属于D，并称di为数据元素。 数据项（Data Item）：数据元素常常还可分为若干个数据项，数据项是数据具有意义的最小单位。 1.３ 基本术语 数据对象（Data Object）: 具有相同特性的数据元素的集合。 例如：数据集合D={0，1，…，A，B，…，Z} 则：数据对象正整数N＝｛ 0，1，…｝ 　　数据对象字母C＝｛ A，B，…，Z ｝ 数据元素是数据的一个个体， 数据对象是数据的一个子集。 基本概念和术语 集合 线性结构 树型结构 图型结构 1.３ 基本术语 数据结构（Data Structure）：是带有结构的数据元素的集合。 　所谓结构就是数据元素之间的关系，即描述数据元素之间的运算及运算规则。 　用集合的形式描述，数据结构是一个二元组： 　DS=(D，R)　　 其中：D是数据元素的集合，R是D上关系的集合。 简言之，数据元素和其相互关系称为数据结构 基本概念和术语 基本概念和术语 1.３ 基本术语 逻辑结构（Logical Structure）： 指数据元素之间的结构关系。 物理结构（Physical Structure）： 指数据结构在机内的表示，也称为存储结构。 基本概念和术语 1.４ 算法描述和算法分析 一．算法（Algorithm） １．算法概念：算法是一个有限的指令集， 遵循指令流可以完成特定的功能。 1.４ 算法描述和算法分析 ３．算法与程序的区别 算法 是解决问题的一种方法或一个过程，考