数据结构 主讲:陈光喜博士 课号:032844 课时40讲课)+16(实验) 上课地点:6312(周)3314(周五 计算科学与数学系
数 据 结 构 主讲：陈光喜 博士 课号:032844 课时:40(讲课)+16(实验) 上课地点:6312 (周一) 3314 (周五) 计算科学与数学系
2003-2004(夏)9 讲;陈光喜 第一章绪论 1.1例子 1.2数据结构、基本概念和术语 1.3算法和算法分 1.3.1算法 1.32算法设计的要求 1.33算法的复杂度 1.3.4算法的描述
Chgx@gliet.edu.cn 数 据 结 构 2003-2004(夏) 主讲:陈光喜 第一章 绪 论 1.1 例子 1.2 数据结构、基本概念和术语 1.3 算法和算法分 1.3.1 算法 1.3.2 算法设计的要求 1.3.3 算法的复杂度 1.3.4 算法的描述
2003-2004(夏)9 讲陈光喜 第一章绪论 计算机是一门研究用计算机进行信息表示和处理的 科学。这里面涉及到两个问题 信息的表示信息的处理 信息的表示和组又直接关系到处理信息的程序的效 率。随着计算机的普及,信息量的增加,信息范围 的拓宽,系统程序和应用程序的规模越来越大,结 构愈加复杂。要有“好”的程序,必须分析待处理 的对象的特征及各对象之间存在的关系,这就是数 据结构这门课所要研究的问题
Chgx@gliet.edu.cn 数 据 结 构 2003-2004(夏) 主讲:陈光喜 第一章 绪 论 ⚫ 计算机是一门研究用计算机进行信息表示和处理的 科学。这里面涉及到两个问题： 信息的表示 信息的处理 信息的表示和组又直接关系到处理信息的程序的效 率。随着计算机的普及，信息量的增加，信息范围 的拓宽，系统程序和应用程序的规模越来越大，结 构愈加复杂。要有“好”的程序，必须分析待处理 的对象的特征及各对象之间存在的关系，这就是数 据结构这门课所要研究的问题
2003-2004(夏)9 讲陈光喜 1.1例子 (Niklaus Wirth) Algorithm +Data Structures=Programs 程序设计:为计算机处理问题编制一组指令集 算法:处理问颕的策略数据结构:问题的数学模型 例:有关数值让篁的程序设计问题 结构静力分析计算一线性代数方程组 数据结构主要研究的是非数值让篁程序的数据结构 1电话号码查询系统 设电话号码薄记录了人的名和电话号码,假定按如下形 式安排:(a1,b1)(a,b2).(an,b)其中a,b(i=1, 2n)分别表示某人的名字和对应的电话号码要求设计 个算法,当给定人名时,算法得到他的电话号码, 如果该电话簿中没这个人,算法指出没有
Chgx@gliet.edu.cn 数 据 结 构 2003-2004(夏) 主讲:陈光喜 ⚫ 1.1 例子 (Niklaus Wirth) Algorithm + Data Structures = Programs 程序设计: 为计算机处理问题编制一组指令集 算法: 处理问题的策略 数据结构:问题的数学模型 例: 有关数值计算的程序设计问题 结构静力分析计算 ─━ 线性代数方程组 数据结构主要研究的是非数值计算程序的数据结构 ⚫ 1 电话号码查询系统 设电话号码薄记录了人的名和电话号码，假定按如下形 式安排： (a1，b1)(a2，b2)…(an，bn) 其中ai,bi(i=1， 2…n) 分别表示某人的名字和对应的电话号码要求设计 一个算法，当给定人名时，算法得到他的电话号码， 如果该电话簿中没这个人，算法指出没有
2003-2004(夏)9 陈光喜 ●算法的设计,依赖于计算机如何存储人的名字 和对应(逻辑关系)的电话号码,即依赖于名字 和其电话号码的结构 数据的结构,直影购算法的进择和效率 ●该问题是一种数据结构问题(存储结构)。可将 名字和对应的电话号码设计成:二维数组、表 结构、向量。 数据结构还要提供每种结构类型所定义的各种 运算的算法(操作)
Chgx@gliet.edu.cn 数 据 结 构 2003-2004(夏) 主讲:陈光喜 ⚫ 算法的设计，依赖于计算机如何存储人的名字 和对应(逻辑关系)的电话号码，即依赖于名字 和其电话号码的结构。 ⚫ 数据的结构，直接影响算法的选择和效率。 ⚫ 该问题是一种数据结构问题(存储结构)。可将 名字和对应的电话号码设计成：二维数组、表 结构、向量。 数据结构还要提供每种结构类型所定义的各种 运算的算法(操作)
2003-2004(夏)9 主讲,陈光喜 2在字典里查找某个单词 算法:比较“大小” 模型:? 3计算机下五子棋 算法:下棋的规则,策略模型: 可以认为:数据结构描述现实世界实体的数学模型 非数值计算)及其上的操作在计算机中的表示和实现 (研究数据的逻辑结构物理结构以及对结构定义 相应的运算,而且确保经过运算后所得到的结果 仍然是原来的结构。)
Chgx@gliet.edu.cn 数 据 结 构 2003-2004(夏) 主讲:陈光喜 •2 在字典里查找某个单词 算法: 比较“大小” 模型: ? •3 计算机下五子棋 算法: 下棋的规则,策略 模型: ? 可以认为：数据结构描述现实世界实体的数学模型 (非数值计算)及其上的操作在计算机中的表示和实现. (研究数据的逻辑结构,物理结构以及对结构定义 相应的运算，而且确保经过运算后所得到的结果 仍然是原来的结构。)
2003-2004(夏)9 主讲,陈光喜 1.2基本概念和术语 ●数据(Daa是对信息的一种符号表示。在计算机 科学中是指所有能输入到计算机中并被计算机程 序处理的符号的总称。 ●数据元素 Data Element)是数据的基本单位,在计 算机程序中通常作为一个整体进行考虑和处理 个数据元素可由若干个数据项组成。数据项是 数据的不可分割的最小单位 ●数据对象( Data Object):是性质相同的数据元素 的集合。是数据的一个子集 ●数据结构( Data structure):是相互之间存在一种 或多种特定关系的数据元素的集合
Chgx@gliet.edu.cn 数 据 结 构 2003-2004(夏) 主讲:陈光喜 ⚫ 数据(Data):是对信息的一种符号表示。在计算机 科学中是指所有能输入到计算机中并被计算机程 序处理的符号的总称。 ⚫ 数据元素(Data Element):是数据的基本单位，在计 算机程序中通常作为一个整体进行考虑和处理。 一个数据元素可由若干个数据项组成。数据项是 数据的不可分割的最小单位。 ⚫ 数据对象(Data Object)：是性质相同的数据元素 的集合。是数据的一个子集。 ⚫ 数据结构(Data Structure)：是相互之间存在一种 或多种特定关系的数据元素的集合。 1.2 基本概念和术语
2003-2004(夏)9 讲陈光喜 数据结构主要指逻辑结构和物理结构 数据间的相互关系称为逻辑结构常分为四类基本结构 集合结构中的数据元素除同属于一种类型外,无其它关系 ●二、线性结构结构中的数据元素之间存在一对一的关系 ●三、树型结构结构中的数据元素之间存在对多的关系。 ●四、图状结构或网状结构数据元素之间存在多对多的关系 专性生
Chgx@gliet.edu.cn 数 据 结 构 2003-2004(夏) 主讲:陈光喜 ⚫ 数据结构主要指逻辑结构和物理结构 ⚫ 数据间的相互关系称为逻辑结构.常分为四类基本结构： ⚫ 一、集合 结构中的数据元素除同属于一种类型外,无其它关系。 ⚫ 二、线性结构 结构中的数据元素之间存在一对一的关系。 ⚫ 三、树型结构 结构中的数据元素之间存在一对多的关系。 ⚫ 四、图状结构或网状结构 数据元素之间存在多对多的关系
2003-2004(夏)9 讲陈光喜 ※数据结构的形式定义为:数据结构是一个二元 H Data-Structure=D,R) 其中:D是数据元素的有限集,R是D上关系的 有限集。 例复数的数据结构定义: Complex=(,R) 其中:C是含两个实数的集合{C1,C2,分 别表示复数的实部和虚部。R={P},P是定义在 集合上的一种关系{(C1,C2〉}。 ※数据结构在计算机中的表示称为数据的物理结 构,又称为存储结构
Chgx@gliet.edu.cn 数 据 结 构 2003-2004(夏) 主讲:陈光喜 数据结构的形式定义为：数据结构是一个二元 组：Data-Structure=(D，R) 其中：D是数据元素的有限集，R是D上关系的 有限集。 例 复数的数据结构定义：Complex=(C，R) 其中：C是含两个实数的集合﹛C1，C2﹜，分 别表示复数的实部和虚部。R={P}，P是定义在 集合上的一种关系{〈C1，C2〉}。 数据结构在计算机中的表示称为数据的物理结 构，又称为存储结构
2003-2004(夏)9 讲陈光喜 ●数据对象D可以是有限的,也可以是无限的。 ●数据结构不同于数据类型,也不同于数据对象,它 描述数据类型的数据对象和数据对象各元素之间的 相互关系 ●R是D上元素的关系集合。 ●数据的逻辑结构:反映数据之间逻辑关系的数据结构 ●数据结构的图形表示(略)P7
Chgx@gliet.edu.cn 数 据 结 构 2003-2004(夏) 主讲:陈光喜 ⚫ 数据对象D可以是有限的，也可以是无限的。 ⚫ 数据结构不同于数据类型，也不同于数据对象，它 描述数据类型的数据对象和数据对象各元素之间的 相互关系。 ⚫ R是D上元素的关系集合。 ⚫ 数据的逻辑结构: 反映数据之间逻辑关系的数据结构。 ⚫ 数据结构的图形表示(略) P7