数据结构导论知识点演示教学.pdfVIP

数据结构导论知识点 第一章 概论 数据结构： 是相互之间存在一种或多种关系的数据元素的集合。 和该集合中数据元素之 间的关系组成。数据结构包括数据的逻辑结构、数据的存储结构和数据的基本运算。 简单地说， 数据结构是计算机组织数据和存储数据的方式。 更进一步地说， 数据结构是 指一组相互之间存在一种或多种特定关系的数据的组织方式和它们在计算机内的存储方式， 以及定义在该组数据上的操作。 合理的数据结构可降低程序设计的复杂性， 提高程序执行的 效率。 1.1 引言 计算机解决一个具体问题时，一般需要经过以下几个步骤： ①从具体的问题抽象出一个适当的数学模型； ②设计一个求解该数学模型的算法； ③用某种计算机语言编写实现该算法的程序，调试和运行程序直至最终得到问题的解 答。 数据的逻辑结构： 数据和数据的组织方式称为数据的逻辑结构。 为了能用计算机加工处 理，逻辑结构还必须转换为能被计算机存储的存储结构。 1976 年瑞士计算机科学家尼克劳斯·维尔特提出公式：算法 +数据结构 =程序。该公式 简洁的描述了数据结构和程序之间关系。 1.2 基本概念和术语 1.2.1 数据、数据元素和数据项 数据：所有被计算机存储、处理的对象。 数据元素：简称元素（又称为结点） ，数据的基本单位，在程序中作为一个整体而加以 考虑和处理。 数据元素是运算的基本单位， 通常具有完整确定的实际意义。 数据元素由数据 项组成。 数据项： 在数据库中数据项又称为字段或域， 是数据的不可分割的最小标识单位， 组成 数据元素。 关系： 数据、 数据元素和数据项实际上反映了数据组织的三个层次， 数据可由若干个数 据元素组成，而数据元素又可由若干个数据项组成。 表格（逻辑结构） ，行 =记录 =数据元素，列 =数据项。 1.2.2 数据的逻辑结构 数据的逻辑结构：是指数据元素之间的逻辑关系。 逻辑关系：是指数据元素之间的关联方式或邻接关系。 逻辑结构示意图中的小圆圈称为结点，一个结点代表一个数据元素（记录） 。 根据数据元素之间关系的不同特性， 通常有集合、 线性结构、 树形结构和图结构四类基 本逻辑结构，反映了四类基本的数据组织形式。 四类基本逻辑结构： ①集合：集合中任何两个结点之间都没有邻接关系，组织形式松散。 ②线性结构：线性结构中结点按逻辑关系依次排列形成一条“链” ，结点之间一个一个 依次相邻接。 ③树形结构：树形结构具有分支、层次特性， 其形态有点像自然界中的树， 上层的结点 可以和下层多个结点相邻接，但下层结点只能和上层的一个结点相邻接。 ④图结构：图结构最复杂，任何两个结点都可以邻接。 数据的逻辑结构与存储无关，独立与计算机。 1.2.3 数据的存储结构 数据的逻辑结构在计算机中的实现称为数据的存储结构（或物理结构） 。 一个存储结构包括两个部分：①存储数据元素。②数据元素之间的关联方式。 表示数据元素之间的关联方式主要有： ①顺序存储方式： 是指所有存储结点存放在一个连续的存储区里。 利用结点在存储器中 的相对位置来表示数据元素之间的逻辑关系。 （使用数组，内存地址连续） ②链式存储方式： 是指每个存储结点除了含有一个数据元素外， 还包含指针， 每个指针 指向一个与本结点有逻辑关系的结点，用