数据结构--绪论.ppt

数 据 结 构 数据结构的前期课程主要有程序设计语言，学好这门课，可以加深对程序设计的理解，有助于进一步提高程序设计能力，并为计算机专业后续课程，如数据库操作系统编译原理，软件工程等课程奠定良好的基础。 教材：数据结构（ C语言版） 严蔚敏,吴伟民 清华大学出版社 数据结构题集（ C语言版） 严蔚敏,吴伟民 清华大学出版社 本课程的教学目标 内容安排 (48授课+24实验) 第一章 绪论 【学习内容】 基本概念 集合、线性结构、树和图的表示 算法评价 时间复杂度、空间复杂度 重点: 了解数据结构的逻辑结构、存储结构、数据的运算三方面的概念及相互关系 难点: 算法复杂度的分析方法 掌握：用C语言描述的方法，能用C语言编写程序 第一节 DS概论 例1 书目自动检索系统 例2 人机对奕问题 例3 多叉路口交通灯管理问题 1.2 数据结构课程的地位 介于数学、计算机硬件和计算机软件三者之间的一门核心课程 第二节 数据结构研究的内容和方法 2.1 基本概念 【数据】(Data)是对信息的一种符号表示。能被计算机输入、存储、处理和输出的一切信息 【数据元素】(Data Element)是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。它是数据整体中相对独立的单位,也称节点（node）或记录（record） 【数据项】一个数据元素可由若干个数据项组成。数据项是数据的不可分割的最小单位,也称域(field)。 【数据对象】(Data Object)是性质相同的数据元素的集合。是数据的一个子集。 【数据记录】组织数据的基本单位 【数据结构】(Data Structure)数据及其相互之间的关系 2.1 基本概念 【逻辑结构】数据之间的相互联系，通常分为四类基本结构： 集合结构: 结构中的数据元素除了同属于一种类型外，别无其它关系。 线性结构: 结构中的数据元素之间存在一对一的关系。 树结构: 结构中的数据元素之间存在一对多的关系。 图(或网状)结构: 结构中的数据元素之间存在多对多的关系。 【存储结构/物理结构】一种数据结构在存储器中的存储方式顺序、链接 2.2 数据的逻辑结构 用 二元组描述数据结构 Data_Structure =（D,R）其中： D是数据元素的有限集； R是在D上关系的有限集，即R是有限个关系的集合。 2.2.1 集合结构 数据结构: SET =（D,R） D = { 01,02,03,04,05,06,07,08,09,10 } R = { } 2.2.2 线性结构 数据结构 LINEARITY =（K,R） K = { 01,02,03,04,05,06,07,08,09,10 } R = { 05,01,01,03,03,08,08,02,  02,07,07,04,04,06,06,09, 09,10 } 数据元素之间的联系：1:1 2.2.3 树结构 数据结构 TREE =（K,R） K = { 01,02,03,04,05,06,07,08,09,10 } R = { 01,02,01,03,01,04,02,05, 02,06,03,07,03,08,03,09, 04,10 } 数据元素之间的联系：1:N 2.2.4 图结构 一种数据结构 GRAPH =（K,R） K = {01,02,03,04,05,06,07,08,09,10,} R = {01,02,02,01,01,04,04,01, 02,03,03,02,02,06,06,02, 02,07,07,02,03,07,07,03, 04,06,06,04,05,07,07,05 } 数据元素之间的联系：M:N 2.2.4 图结构 2.3 数据的存储（物理）结构 数据的存储（物理）结构—数据的逻辑结构在计算机存储器中的实现 存储结构分为： 顺序存储结构——借助元素在存储器中的相对位置来表示数据元素间的逻辑关系 链式存储结构——借助指示元素存储地址的指针表示数据元素间的逻辑关系 2.3 数据的存储（物理）结构 数据的逻辑结构与存储结构密切相关 算法设计 逻辑结构 算法实现 存储结构 2.4 数据的运算 数据的操作是定义在逻辑结构上的，而操作的具体 实现是在存储结构上进行的。基本的数据操作主要 有以下几种： 查找 在数据结构中寻找满足某个特定条件的数据元素（的位置或值） 插入 在数据结构中增加新的数据元素 删除 删去数据结构中指定的数据元素 更新