数据结构实用教程(c语言版)

《数据结构实用教程(c语言版)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构实用教程（C语言版）第1章概论本章主要介绍以下内容：数据结构中涉及的相关概念数据结构研究的主要内容算法的概念、描述方法以及评价标准本章目录1.1什么是数据结构11.2算法和算法分析25.5哈夫曼树51.3本章小结3结束1.1什么是数据结构1.1.1基本概念及术语1.1.2数据的逻辑结构1.1.3数据的存储结构1.1.4抽象数据类型返回到本节目录返回到总目录1.1.1基本概念及术语在系统的学习数据结构知识之前，先了解一些相关概念和术语。1．数据（Data）指所有能输入到计算机中并被计算机程序处理的符号的总称。例

2、如，整数、实数、字符、图像、声音等都是数据。2．数据元素（DataElement）数据元素（也称为结点）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。一个数据元素可以由若干个数据项组成。数据项是数据处理中不可分割的最小单位。返回到本节目录3．数据结构（DataStructure）是相互之间存在一种或多种特定关系的数据元素的集合。这些数据元素不是孤立存在的，而是有着某种关系，这种关系称为结构。数据结构一般包括以下三个方面内容：（1）数据元素之间的逻辑关系，也称数据的逻辑结构。（2）数据元素及其关系在计

3、算机存储器内的表示，称为数据的存储结构。（3）数据的运算，即对数据施加的操作。返回到本节目录1.1.1基本概念及术语数据结构定义：按某种逻辑关系组织起来的一批数据，按一定的映像方式把它存放在计算机存储器中，并在这些数据上定义了一个运算的集合，就叫做数据结构。简言之，数据结构={逻辑结构+存储结构+运算集合}。4．数据类型(DataType)数据类型是一组性质相同的值集合以及定义在这个值集合上的一组操作的总称。如在高级语言中，整型类型的取值范围为：-32768～+32767，运算符集合为加、减、乘、除、取模，即+、-、

4、*、/、%。返回到本节目录1.1.1基本概念及术语5．数据类型(DataType)高级语言中的数据类型分为两大类：（1）原子类型其值是不可分解的。如C语言中的标准类型（整型、实型、字符型）。（2）结构类型其值是由若干成分按某种结构组成的，因此是可以分解的。如C语言中的的构造类型（结构体、共用体、枚举等类型）。返回到本节目录1.1.1基本概念及术语1.1.2数据的逻辑结构1．定义数据的逻辑结构是指数据元素之间逻辑关系描述。可以用一个二元组表示，其形式化描述为：Data_Structure=（D，R）其中D是数据元素的有

5、限集合，R是D上关系的有限集合。数据的逻辑结构是从逻辑关系上描述数据，与数据的存储无关，是独立于计算机的。返回到本节目录2．数据的逻辑结构的分类根据数据元素之间的逻辑关系的不同特性，分为下列四类基本结构，如图1-1所示。（a）集合结构（b）线性结构（c）树型结构（d）图形结构图1-1数据结构的四种基本逻辑结构返回到本节目录1.1.2数据的逻辑结构（1）集合结构中的数据元素之间除了“同属于一个集合”的关系外，别无其他关系，这是一种最简单的数据结构。（2）线性结构结构中的数据元素之间存在着“一对一”的关系。【例1.1】学

6、籍档案管理假设一个学籍档案管理系统应包含如表1-1所示的学生信息。返回到本节目录1.1.2数据的逻辑结构特点：表中的每一行是一个数据元素（或记录、结点），它由学号、姓名、性别及出生年月等数据项组成。表中数据元素之间是一种先后关系，对于表中任一结点，与它相邻且在它前面的结点（称为直接前驱）最多只有一个；与表中任一结点相邻且在其后的结点（称为直接后继）也最多只有一个。我们将这种关系称为“线性结构”。返回到本节目录1.1.2数据的逻辑结构（3）树型结构结构中的数据元素之间存在着“一对多”的关系。【例1.2】人机对弈人与计算

7、机进行对弈的部分图如图1-2为所示。图1-2人机对弈图返回到本节目录1.1.2数据的逻辑结构特点：图中将每一个棋盘看作一个数据元素，则数据元素之间的关系要比表1-1要复杂许多。图中数据元素之间是一对多关系，即一个数据元素向上和一个数据元素相连（称为双亲结点），向下和多个数据元素相连（称为孩子结点）。我们将这种关系称为“树型结构”。4）图形结构或网状结构结构中的任意数据元素之间都可以有关系，元素之间存在着“多对多”的关系。返回到本节目录1.1.2数据的逻辑结构（【例1.3】制定教学计划在制定教学计划时，需要考虑各门课程

8、的开设顺序。有些课程需要先导先修课程，有些课程则不需要，而有些课程又是其他课程的先导先修课程。比如，计算机专业课程的开设情况如表1-2所示。返回到本节目录1.1.2数据的逻辑结构教学计划的关系图如图1-3所示。图1-3教学计划关系图特点：图中数据元素存在着多对多的任意关系。一个结点可能有多个直接前驱和直接后继。返回到本节目录1.1.2数据的逻辑