数据结构的基本概念和术语课件

1、数据结构,课程类别：专业选修 学时、学分数：48学时3学分 考核方式与要求：考查,课程介绍,重要性,章节介绍,绪论 4 线性表 6 栈和队列 6 串 1 数组和广义表 1 树和二叉树 9 图 9 查找 6 内部排序 6,数据结构,逻辑结构,物理结构,线性结构,树形结构,图状结构,集合,顺序实现,链式实现,操作，算法,5数组和广义表,4串,3栈和队列,2线性表,7图,6树和二叉树,主要内容,10排序,9查找,几点要求,上课请关机 不迟到，不旷课 准备笔记本 机房禁止玩游戏，上网，吃东西,第一章 绪 论,学习目的：掌握数据结构的基本概念和术语。,重点难点：数据结构的基本概念。,1.1 什么是数据结

2、构,1.2 基本概念和术语,教学内容,1.1 什么是数据结构,IT 计算机科学家 pascal语言的创始人Niklaus Wirth（尼古拉斯沃斯 ）教授在1976年出版了一本书：“Algorithms + Data Structures = Programs” 说明了算法和数据结构是进行程序设计的两大要素。,1.计算机是怎么解决问题的？,很多数值计算问题的数学模型通常可用一组线性或非线性的代数方程组或微分方程组来描述： 如：结构静力分析计算-线性代数方程组，全球天气预报-环流模式方程,抽象模型,设计算法,调试测试,编码,得出结果,如今计算机所处理的是大量的非数值计算的程序设计问题：,例1 *

3、数据库管理系统,例2 计算机对弈：,数学模型：表格和数据库,数学模型： 树形结构,例3 交叉路口的红绿灯管理。如今十字路口横竖两个方向都有三个红绿灯，分别控制左拐、直行和右拐，那么如何控制这些红绿灯既使交通不堵塞，又使流量最大呢？,数学模型： 图状结构,例4 煤气管道的铺设问题。如下图：需为城市的各小区之间铺设煤气管道，对 n 个小区只需铺设 n-1 条管线，由于地理环境不同等因素使各条管线所需投资不同(如图上所标识)，如何使投资成本最低？,数学模型： 图状结构,综合各种程序设计问题，抽取它具体的物理含义，就可以得到两类数学模型： 和数值计算相关的数学模型：（非）线性代数方程，常微分方程-计算

4、数学 非数值计算问题的数学模型：数学模型的表示和求解方法-数据结构 由以上几个例子可见，描述这类非数值计算问题的数学模型不再是数学方程，而是诸如表、树、图之类的数据结构。,2.什么是数据结构?,数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作的学科。 要使计算机能够更有效地进行这些非数值性处理，就必须弄清楚这些操作对象的特点，在计算机中的表示方式以及各个操作的具体实现手段。这些就是数据结构这门课程研究的主要内容。,是所有能被输入到计算机中，且能被计算机处理的所有符号(数字、字符等)的集合，它是计算机操作对象的总称，是计算机处理的信息的载体，是信息的某种特定的

5、符号表示形式。 数据是个集合，如果用集合的表示方法来写的话，就是： 数据=x|x是计算机操作的对象,是数据(集合)中的一个“个体”，在计算机中通常作为一个整体进行考虑和处理，是数据结构中讨论的“基本单位”，但不是“最小单位”。,1、数据,2、数据元素,1.2 基本概念和术语,数据元素分类 一类是不可分割的“原子”型数据元素，如：整数“5”，字符 “N” 等 一类是由多个款项构成的数据元素，其中每个款项被称为一个“数据项”。 例如描述一个学生的信息的数据元素可由下列6个数据项组成。 数据项是数据结构中讨论的“最小单位”。 数据元素是数据项的集合。,是性质相同的数据元素的集合，它是数据的一个子集。

6、如：整数数据对象 N = 0, 1, 2, 字母字符数据对象C= A,B,Z 在同一个数学模型中的数据元素必然具有相同特性。,3、数据对象,4、数据结构,1）概念：是相互之间存在一种或多种特定关系的数据元素的集合，即带“结构”的数据元素的集合。 “结构”即指数据元素之间存在的约束关系。 数据结构是一堆数据元素和这些数据元素之间的关系的总和。,例5 一个12位数的十进制数可以用3个4位的十进制数表示： 3214，6587，9345-a1(3214),a2(6587),a3(9345) a1,a2,a3之间存在“次序”关系, ， 意为 x 和 y 之间存在“x领先于y”的次序关系。 a1a2a3

7、a2a1a3,例6 可以用下述数据结构来描述2行3列的矩阵： 它是一个含6个数据元素a1,a2,a3,a4,a5,a6 的集合，且集合上存在“行关系”和“列关系”两个次序关系，其中： 行row=， 列col=，,a1 a3 a5 a2 a4 a6,a1 a2 a3 a4 a5 a6,同样的这6个数据元素组成的一维数组a1,a2,a3,a4,a5,a6的数据元素之间存在如下的次序关系: | i=1,2,5 同样的数据元素，不同的关系构成了不同的结构，因此数据结构是带结构的数据元素的集合。或者说，数据结构是相互之间存在着某种逻辑关系的数据元素的集合。,2）数据结构的形式定义,数据结构是一个二元组

8、Data_Structures = ( D,S ) 其中：D是数据元素的有限集， S是D上关系的有限集。 例7 复数的二元组定义 复数由实部和虚部构成（构成元素），两者之间存在着一种次序关系（逻辑关系）。 可以表示为： Complex=(C,R) 其中,C= c1,c2 R= 说明:表示有序数对,用图示法表示时画箭头 ( )表示无序数对,用图示法表示时画线段,数据的逻辑结构：描述数据元素之间的逻辑关 系，不依赖于具体表示，是抽象的。可归结为以下四类:,线性结构,树形结构,图/网状结构,集合结构,3）数据的“逻辑结构”,一对一,一对多,多对多,4）数据的“存储结构”, 逻辑结构在存储器中的具体实

9、现表示(映象)。故又称数据存储结构。 它包括数据元素的表示和关系的表示。,“数据元素”的映象 ？,“关系”的映象 ？,数据元素的映象方法：,用二进制位(bit)的位串表示数据元素,(321)10 = (501)8 = (101000001)2,A = (101)8 = (001000001)2,关系的映象方法：,顺序映象,借助元素在存储器中相对的位置来表示数据元素之间的关系。地址是连续的。如数组。,例8 存储复数 z=3.0-2.3i,顺序存储结构,链式映象,借助元素存储地址的指针来表示数据元素之间的关系。地址可以是离散的。 如上复数的存储,链式存储结构,当用高级程序设计语言进行编程时，通常可

10、用高级编程语言中提供的数据类型来描述存储结构。,两种存储的比较： 顺序结构:占用最少的存储空间，产生较多碎片。 非顺序：不会出现碎片，每个结点占用较多空间。,5、数据类型 数据类型是一个“值”的集合和定义在此集合上的“一组操作”的总称。 在用高级程序语言编写的程序中，必须对程序中出现的每个变量、常量或表达式，明确说明它们所属的数据类型。程序中对变量或常量说明其所属类型的作用是，对它们加上两个约束条件：一是可取值的范围，二是可进行的操作。 不同类型的变量，其所能取的值的范围不同，所能进行的操作不同。,例如，C 语言中提供的基本数据类型有:,整型 int,浮点型 float,字符型 char,空类

11、型 void,双精度型 double,实型（ C+语言）,6、抽象数据类型(Abstract Data Type 简称ADT),指一个数学模型以及定义在该模型上的一组操作。 由用户定义，用以表示应用问题的数据模型 由基本的数据类型组成, 并包括一组相关的服务（或称操作）,抽象数据类型的描述方法(P8),抽象数据类型可用（D，S，P）三元组表示。 其中：D 是数据对象； S 是 D 上的关系集； P 是对 D 的基本操作集。 格式：ADT 抽象数据类型名 数据对象：数据对象的定义 数据关系：数据关系的定义 基本操作：基本操作的定义 ADT 抽象数据类型名,其中基本操作的定义格式为: 基本操作名（

12、参数表） 初始条件：初始条件描述 操作结果：操作结果描述 赋值参数 只为操作提供输入值。 引用参数 以&打头，除可提供输入值外，还将返回操作结果。 初始条件 描述了操作执行之前数据结构和参数应满足的条件，若不满足，则操作失败，并返回相应出错信息。 操作结果 说明了操作正常完成之后，数据结构的变化状况和应返回的结果。若初始条件为空，则省略之。,例9、抽象数据类型复数的定义,ADT Complex 数据对象：D = e1,e2 | e1,e2 RealSet 数据关系：R1 = | e1是复数的实部，e2是复数的虚部 基本操作： InitComplex( &Z, v1, v2 ) 操作结果：构造复

13、数Z，其实部和虚部分别被赋以参数v1和v2的值。 DestroyComplex( &Z) 初始条件：复数已存在。 操作结果：复数Z被销毁。 GetReal( Z, &realPart ) 初始条件：复数已存在。 操作结果：用 realPart 返回复数Z的实部值。 GetImag( Z, &ImagPart ) 初始条件：复数已存在。 操作结果：用 ImagPart 返回复数Z的虚部值。 Add( z1,z2, &sum ) 初始条件：z1，z2 是复数。 操作结果：用sum返回两个复数z1，z2的和值。 ADT Complex,假设:z1和z2是上述定义的复数 则 Add(z1, z2, z3) 操作的结果 即为用户要求的结果 z3 = z1 + z2,课堂总结 主要内容：什么是数据结构、数据结构的基本概念。 重点难点：数据结构的