数据结构概论.pptVIP

数据结构与算法 ---第一讲 北方民族大学 计算机科学与工程学院 王伦津 目录 1.1 数据结构中的术语 1.2 数据结构研究的内容 1.3 数据逻辑结构的分类 1.4 数据存储结构的分类 1.5 数据结构访问接口 1.6 抽象数据类型和数据结构 1.7 数据结构的学习方法 为什么要研究数据结构 计算机应用系统=计算机系统+网络+应用软件+ 数据 计算机系统=硬件+软件 软件=程序+文档 程序=数据结构+算法 掌握数据结构可以使数据组织规范，为设计算法提供数据基础，提高编程效率，提高代码复用 什么是数据结构 数据元素之间的关系称为数据结构。 简单说数据结构是研究数据的存储、数据之间的关系和对数据实现各种操作的一门学科。 怎样学习数据结构 1、听课、读书：掌握常规的数据组织方法，以及每种组织形式下基本操作的实现思路 2、熟悉一种算法语言，上机实现，加深理解 3、思考与分析（包括课堂与课下交流）：提高抽象与分解能力 * * 数据结构概论 本讲主要知识点： 数据结构的基本概念，包括数据、数据元素、抽象数据元素、数据的逻辑结构、数据的存储结构、数据的操作类型、数据类型和抽象数据类型的概念 基本要求：掌握数据结构的概念及其相关术语、了解数据逻辑结构和存储结构的分类； 第一讲：数据结构概论 1.1 数据结构中的术语 （1）数据：数据是描述客观事物的信息的符号化，是计算机系统可加工处理的对象 （2）数据类型：一个值的集合和定义在这个值集上的一组操作的总称。 （3） 数据元素、数据项：能独立、完整地描述问题世界中的实体的最小数据单位称为数据元素（也称记录）。构成数据元素的不可分割的数据单位，称为数据项。 （4）数据对象：同类数据元素的集合称为数据对象。 （5）数据结构：数据元素之间的关系称为结构。进一步地，称相互之间存在着一定关系的数据元素的集合及定义在其上的基本操作（运算）为数据结构。为了与后面要介绍的存储结构区别，有时也强调地称数据结构为数据的逻辑结构。 1.2 数据结构研究的内容 信息中的各个数据元素并不是孤立存在的，它们之间存在着线性关系和非线性关系结构。 使用计算机解题时，需要分析具体问题得到数学模型，数学模型需要选定适当的数据结构来描述，有了确定的数据结构才能设计算法，编制程序并调试，最后得到最终答案。 数据的逻辑结构和存储结构是密不可分的两个方面，逻辑结构是数据的约束关系，存储结构是数据的组织关系，设计算法重点考虑数据逻辑结构。在实现算法时，重点解决数据的存储问题。 数据之间既要考虑存储，又要考虑数据单位之间的关系，在确定了存储结构后，根据存储的结构再来确定相应操作的实现方法。 简单说数据结构是研究数据的存储、数据之间的关系和对数据实现各种操作的一门学科。 数据结构的定义可以记作： Data-Structure=（D，R） 其中D是数据元素的有限集合，R是D上的关系。 一般情况下，“关系”是指数据元素之间存在的逻辑关系，也称为数据的逻辑结构。数据在计算机内的存储表示（或映象）称为数据的存储结构或物理结构。 逻辑结构体现的是数据元素之间的逻辑关系，换句话说就是从操作对象中抽象出来的数学模型，因此又称为抽象结构，通常习惯说的数据结构一般就是指的逻辑结构。 讨论数据结构的目的是为了在计算机中实现对数据的操作，因此还需要研究数据的存储结构。 存储结构是数据在计算机内的表示（映象），又称物理结构。它包括数据元素的表示和关系的表示。 总之，数据结构所要研究的主要内容简单归纳为以下三个方面： ⑴ 研究数据元素之间的客观联系（逻辑结构）； ⑵ 研究数据在计算机内部的存储方法（存储结构）； ⑶ 研究如何在数据的各种结构（逻辑的和物理的）上实施有效的操作或处理（算法）。 所以数据结构是一门抽象地研究数据之间的关系的学科。 1.3 数据逻辑结构的分类 1 集合 如果数据结构中，数据元素之间不考虑关系问题（无前驱/后继之分），则称这种结构为集合。 在集合中，各元素是“平等”的，它们的共同关系是：都属于同一个集合。 这种结构的典型实例是一个班中的同学或一组相同型号规格的产品 2 线性结构 如果数据结构中，数据元素之间只存在前后顺序关系（每个元素都有唯一前趋和后继，第一个元素可以没有前驱，最后一个可以没有后继），则称这种结构为线性结构。 线性结构是一种最常见的数据结构。线性表、栈、队列、串等均为线性结构。 下图表示的数据结构可表示为： DS=(D, S) D={d1, d2, …, dn} 数据集合 S={ r }