数据结构与(C 语言描述) .ppt

数据结构（C++语言描述） 教学演示文稿 数据结构课程要研究的主要问题： 现实世界中的实际问题必须经过抽象，得出反映实际事物本质的数据表示后，才能被计算机处理。 如何用计算机所能接受的形式来描述这些数据，如何将这些数据以及它们之间的关系存储在计算机中，以及如何用有效的方法去处理这些数据，是数据结构课程要研究的主要内容。 2.1 基本概念 2.1.1 数据、数据元素、数据对象 2.1.2 数据结构 2.1.1 数据、数据元素、数据对象 数据 (data) 是对客观事物的符号表示，是对现实世界的事物采用计算机能够识别、存储和处理的形式进行描述的符号的集合。 例如：科学计算软件处理的是数值数据；文字处理软件处理的是字符数据；多媒体软件处理的是图象、声音等多媒体数据。 数据元素 (data element) 是数据的基本单位，也称结点，在一个计算机程序中通常作为一个整体进行考虑和处理。数据元素也称结点。 2.1.1 数据、数据元素、数据对象 一个数据元素可以由若干个数据项 (data item) 组成。数据项包括两种：初等项（是数据不可分割的最小单位）、组合项（由若干个数据项组成）。 在数据库语言中，数据项称为“字段”，而数据元素称为“记录”。 数据对象 (data object) 是性质相同的数据元素的集合，是数据的一个子集。例如整数对象、实数对象、字符对象等。 2.1.2 数据结构 从数学意义上讲，数据结构是指数据的组织形式，由数据对象及该对象中数据元素之间的关系组成。数据结构可描述为一个二元组 Data-Structure=（D，R） 其中：D是数据对象，为数据元素的有限集；R是该对象中数据元素之间关系的有限集。 这种意义上的数据结构称为数据的逻辑结构。除此之外，要将数据放在计算机内进行处理，还将涉及数据的存储结构。 2.1.2 数据结构 涉及到计算机的数据结构概念，至今尚未有一个公认的标准定义，但一般认为应包括以下三个方面： （1）数据元素与数据元素之间的逻辑关系，也称为数据的逻辑结构，它独立于计算机； （2）数据元素与数据元素之间的关系在计算机中的存储表示，也称为数据的存储结构或物理结构，它依赖于计算机； （3）数据的运算，即对数据施加的操作。 2.2 数据结构的分类：逻辑结构 如果一个数据结构中的两个结点k、k’之间存在的关系可用有序对 k, k’表示，则称 k’是 k的后继，k是k’的前驱，k和k’互为相邻结点。如果k没有后继，则k称为终端结点。如果k没有前驱，则称k为开始结点。如果k既不是终端结点，也不是开始结点，则称k为内部结点。 数据的逻辑结构分为线性结构和非线性结构两大类。非线性结构又分为树型结构和图状结构。 线性结构 线性结构有且仅有一个开始结点和一个终端结点，并且所有的结点最多只有一个前驱和一个后继。线性表是典型的线性结构。 线性表 一个学校所有学生的各种特征可用以下表格来记录： 学号 姓名 性别 出生年月 系 班级 … 030401 张三 男 1985.1 计算机 0304 … 030402 李四 女 1984.12 计算机 0304 … 030403 王五 男 1984.6 计算机 0304 … 030404 赵六 男 1985.4 计算机 0304 … … … … … … … … 该表为一个数据结构，其中列称为“字段”，行称为“记录”，记录之间有一对一的线性关系，称为“线性结构”。 树状结构 树状结构中，一个结点最多只有一个前驱，而可以有多个后继。它是最重要的非线性结构。 一个学校的组织机构可用以下数据结构来表示： 该数据结构的“结点”具有一对多的逻辑关系，就象一棵倒挂的树，故称为“树状结构”。 图状结构 图状结构中，对结点的前驱和后继的个数没有限制，结点之间的关系是任意的。它是最一般的非线性结构。 在 n 个城市间建立通信网络，要求在任意两个城市之间都有直接或间接的通信线路，该通信线路可用以下图形来表示： 如果每个城市为一个结点，则结点之间的逻辑结构称为 “图状结构”，它是一种多对多的数据结构。 2.2 数据结构的分类：存储结构 数据的存储结构（又称物理结构）取决于四种基本的存储方法：顺序存储、链接存储、索引存储、散列存储。 顺序存储是把逻辑上相邻的结点存储在物理位置相邻的存储单元里。结点之间的逻辑关系用存储单元的邻接关系来体现。 链接存储对逻辑上相邻的结点不要求在存储的物理位置上相邻，结点之间的逻辑关系由附加的指针来表示。 索引存储是在存储结点数据的同时，还建