东南大学数据结构_Lec001讲述.pptx

第1讲 绪论 1.1 数据结构及其概念 1.2 基本概念和术语 1.3 数据类型与抽象数据类型 1.4 算法和算法分析 0 数据结构 计算机求解问题的一般步骤 编写解决实际问题的程序的一般过程： 如何用数据形式描述问题? ——即由问题抽象出一个适当的数学模型； 问题所涉及的数据量大小及数据之间的关系； 如何在计算机中存储数据及体现数据之间的关系? 处理问题时需要对数据作何种运算? 所编写的程序的性能是否良好? 上面所列举的问题基本上由数据结构这门课程来回答。 数据结构 1 数据结构的研究内容 要对所加工的对象进行逻辑组织（选择数据结构）。 如何把加工对象存储到计算机中去？ 数据运算处理 数据结构 2 分析问题，确定算法的资源限制。 确定必须支持的基本运算，度量运算所受的资源限制。 选择最接近这些资源开销的数据结构。 数据结构的几个例子 电话号码查询系统 设有一个电话号码薄，它记录了N个人的名字和其相应的电话号码，假定按如下形式安排：(a1, b1)，(a2, b2)，…(an, bn)，其中ai, bi(i=1，2…n) 分别表示某人的名字和电话号码。 本问题是一种典型的表格问题。如表1-1，数据与数据成简单的一对一的线性关系。 数据结构 3 姓名 电话号码 陈海李四锋。。。 。。。 表1-1 线性表结构 数据结构的几个例子 磁盘目录文件系统 磁盘根目录下有很多子目录及文件，每个子目录里又可以包含多个子目录及文件，但每个子目录只有一个父目录，依此类推。 本问题是一种典型的非线性关系结构：树形结构，如图1-1所示，数据与数据成一对多的关系。 数据结构 4 图1-1 树形结构 数据结构的几个例子 交通网络图 从一个地方到另外一个地方可以有多条路径； 本问题是一种典型的网状结构问题，数据与数据成多对多的关系，是一种非线性关系结构。 数据结构 5 第1讲 绪论 1.1 数据结构及其概念 1.2 基本概念和术语 1.3 数据类型与抽象数据类型 1.4 算法和算法分析 6 数据结构 基本概念和术语 数据结构的相关名词： 数据 (Data) 数据元素 (Data Element) 数据结构 (Data Structure) 数据结构 7 数据（Data） 数据是信息的载体，是描述客观事物的数、字符，以及所有能输入到计算机中并被计算机程序识别和处理的符号的集合。 数据大致分为两类： 数值性数据，包括整数、浮点数、复数等，主要用于工程和科学计算，以及商业事务处理； 非数值数据，主要包括字符和字符串，以及文字、图形、图像、语音等数据。 数据结构 8 数据元素（Data Element） 数据元素是组成数据的基本单位，是计算机程序中加工处理的基本单位，是一个数据整体中相对独立的单位。 一个数据元素可由若干个数据项（data item）组成。 数据项是对客观事物某一方面特性的数据描述。 初等项：这些数据项是在数据处理时不能再分割的最小单位。 组合项：如学生成绩，可以再划分为各门课程等更小的项。 数据结构 9 数据结构（Data Structure） 数据元素之间的相互关系称为结构。 招生考试时考生记录（按成绩排队） n个网站之间建立通信网络 考虑最小代价的网站连通性； 考虑任一网站出现故障时，整个网络仍保持畅通。 数据结构由某一数据元素的集合和该集合中数据元素之间的关系组成。其形式定义为一个二元组，记为： Data_Structure={D, R} 其中，D是某一数据元素的有限集合，R是该集合中所有数据元素之间的关系的有限集合。 数据结构 10 数据结构的分类 线性结构（linear structure） 也称为线性表，这种结构中所有数据元素都按某种次序排列在一个序列中。 非线性结构（nonlinear structure） 这种结构中各个数据元素不再保持在一个线性序列中，每个数据元素可能与零个或多个其他数据元素发生联系。 层次结构：按层次划分的数据元素的集合，指定层次上元素可以有零个或多个处于下一个层次上的直接所属元素。 —— 树形结构 群结构：所有元素之间无顺序关系。 —— 集合、图结构 数据结构 11 基本数据结构类型 常见的四类基本数据结构 ① 线性结构：结构中的数据元素之间存在一对一的关系。 ② 树形结构：结构中的数据元素之间存在一对多的关系。 ③ 集合：结构中的数据元素除了“同属于一个集合”关系外， 没有其它关系。 ④ 图结构或网状结构： 结构中的数据元素之间存在多对多的关系。 数据结构 12 图1-3 四类基本结构图 数据结构的定义举例 例：为一类科研课题小组设计一个数据结构。 假设