数据结构绪论 PPT课件 (2).ppt

第1章 绪论 第1章 绪论 1.1 什么是数据结构 1.2 数据的逻辑结构和物理结构 1.3 算法描述 1.4 算法分析 1.5 小结 习题1 1.1 什么是数据结构 数据结构(Data Structure)包括两方面的内容：数据和结构。 最简单的数据结构的例子是一维数组。例如：要计算100个数a1 , a2 , … , a100的累加和，显然，用赋值语句sum = a1 + a2 + … +a100来描述求和的表达式是极不科学的。我们可以把这100个数以线性排列的结构组成一个一维数组A[i]。在此基础上，计算这100个数的累加和的程序段可描述为 sum = 0 ; for(i=1; i =100; i++) sum = sum + A[i]; 计算结果保存在sum中。这个程序段比sum = a1 + a2 + … + a100这样的语句要简明得多，况且在程序设计中不允许书写省略号。上面的程序段实际上包括了两方面的内容：第一是数据结构int A[100]表示的数组，第二是数组作为数据结构的形式所描述的算法，从而达到使程序设计简明、易读的目的。 要用计算机实现对学校的管理，就要经课题调查、研究，按管理的模式确定程序的数据处理模式和流程，如图1-1所示，还要确定具体部门的数据结构形式，如表1-1所示的学生成绩表。 图1-1 学校管理程序流程框图 表1-1 学生成绩表 1.2 数据的逻辑结构和物理结构 数据结构作为一门独立的课程是从1968年才开设的。而数据结构课程中的有关内容，如表处理、串处理、树结构等早已散见于计算机的其他课程，如操作系统、编译原理、表处理语言等课程中，但其内容都缺乏规范性和系统性。随着计算机科学的发展和计算机应用的普及，计算机加工、处理的对象已从早期的数值、布尔值扩展到字符串、表格、图像甚至语音等等。这些能被计算机存储、加工的对象称为数据。因此现在认为，数据包含数值和非数值两种类型。 数据通常由数据元素组成，数据元素是数据的基本单位，具有完整、确定的实际意义，在程序中作为一个整体而加以考虑和处理。如表1-1所示的学生成绩表中，每个学生的数据用学号、姓名和各门学科的成绩来表示，这些具体的数值和字符是数据元素。这些数据元素准确地表示了某个学生的学习成绩。 在很多情况下，数据元素又由数据项组成，但数据项通常不具有完整、确定的实际意义或不被当作一个整体对待。如在学生成绩表中，“学号”、“姓名”、“C语言”等内容都是数据项，所有数据项中的数据组成了数据元素。因此，每个学生的成绩是一个数据元素，成绩中的每一项都是数据元素中的数据项。 每个项目是作为成绩的一个成分出现的，但单独的项目没有完整确定的实际意义。例如，将表格中第一行的各个数据项拆开，分别地看，则“1”、“张平”、“82”……这些数据分别表示一个学号、一个学生名、C语言课程的成绩等，它们各自在学生成绩表中是一个个离散的数据，不能完整地表示某个学生的学习档案，但这些数据项的组合就构成了一个具有完整意义的某学生的学习情况。所以，在由多个数据项所构造的数据元素中，数据项不是数据元素，而每一个项目的组合则是数据元素。 但是，当有些数据元素不能再分解为数据项的组合，即该数据元素仅由一个数据项组成时，这个数据项就是该数据元素自身。 现实的世界是信息的世界。所谓信息，就是客观存在的反映，而数据就是信息的表现形式和描述，这种描述是为了能被计算机所识别、存储和处理。而这种描述一般可归结为数字、字符和各种字符的集合，如上例中的学号、姓名、成绩等。值得注意的是，我们研究的数据不是孤立的，而表现出了相互关联的特性。如某学生的姓名以及该学生的学科成绩都作为数据存在，其数据与数据之间的关系为：学生姓名与班级名对应，成绩与学科相匹配。这种数据元素之间存在的相互关系就是数据的结构。这种由设计者建立的数据之间的结构也称为数据之间的逻辑结构。 图1-2所示为四类基本逻辑结构的示意图，它们反映了四类基本的数据组织形式。图中的小圆圈称为结点。一个结点代表一个数据元素。结点之间的连线代表逻辑关系，即相应数据元素之间的邻接关系。 图1-2 四类基本逻辑结构 集合；(b) 线性结构； (c) 树形结构；(d) 图状结构 以上的各种逻辑结构就是本书中将要详细介绍的数学模型。关于逻辑结构，有以下几点需特别注意。 (1) 逻辑结构与数据元素本身的形式、类型、内容无关。 (2) 逻辑结构与数据元素的相对位置无关。 (3) 逻辑结构与所含结点个数无关。 1.3 算法描述 1.3.1 数据结构上的基本操作 本书中主要介绍各种算法，并给出部分算法对应的C语言程序。 数据结构上的基本操作主