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

数据结构实用教程（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．数据元素（DataElement）数据元素（也称为结点）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。一个数据元素可以由若干个数据项组成。数据项是数据处理中不可分割的最小单位。返回到本节目录3．数据结构（DataStructure）是相互之间存在一种或多种特定关系的数据元素的集合。这些数据元素不是孤立存在的，而是有着某种关系，这种关系称为结构。数据结构一般包括以下三个方面内容：（1）数据元素之间的逻辑关系，也称数据的逻辑结构。（2）数据元素及其关系在计算机存储器内的表示，称为数据的存储结构。（3）数据的运算，即对数据施加的操作。返回到本节目录1.1.1基本概念及术语数据结构定义：按某种逻辑关系组织起来的一批数据，按一定的映像方式把它存放在计算机存储器中，并在这些数据上定义了一个运算的集合，就叫做数据结构。简言之，数据结构={逻辑结构+存储结构+运算集合}。4．数据类型(DataType)数据类型是一组性质相同的值集合以及定义在这个值集合上的一组操作的总称。如在高级语言中，整型类型的取值范围为：-32768～+32767，运算符集合为加、减、乘、除、取模，即+、-、*、/、%。返回到本节目录1.1.1基本概念及术语5．数据类型(DataType)高级语言中的数据类型分为两大类：（1）原子类型其值是不可分解的。如C语言中的标准类型（整型、实型、字符型）。（2）结构类型其值是由若干成分按某种结构组成的，因此是可以分解的。如C语言中的的构造类型（结构体、共用体、枚举等类型）。返回到本节目录1.1.1基本概念及术语1.1.2数据的逻辑结构1．定义数据的逻辑结构是指数据元素之间逻辑关系描述。可以用一个二元组表示，其形式化描述为：Data_Structure=（D，R）其中D是数据元素的有限集合，R是D上关系的有限集合。数据的逻辑结构是从逻辑关系上描述数据，与数据的存储无关，是独立于计算机的。返回到本节目录2．数据的逻辑结构的分类根据数据元素之间的逻辑关系的不同特性，分为下列四类基本结构，如图1-1所示。（a）集合结构（b）线性结构（c）树型结构（d）图形结构图1-1数据结构的四种基本逻辑结构返回到本节目录1.1.2数据的逻辑结构（1）集合结构中的数据元素之间除了“同属于一个集合”的关系外，别无其他关系，这是一种最简单的数据结构。（2）线性结构结构中的数据元素之间存在着“一对一”的关系。【例1.1】学籍档案管理假设一个学籍档案管理系统应包含如表1-1所示的学生信息。返回到本节目录1.1.2数据的逻辑结构特点：表中的每一行是一个数据元素（或记录、结点），它由学号、姓名、性别及出生年月等数据项组成。表中数据元素之间是一种先后关系，对于表中任一结点，与它相邻且在它前面的结点（称为直接前驱）最多只有一个；与表中任一结点相邻且在其后的结点（称为直接后继）也最多只有一个。我们将这种关系称为“线性结构”。返回到本节目录1.1.2数据的逻辑结构（3）树型结构结构中的数据元素之间存在着“一对多”的关系。【例1.2】人机对弈人与计算机进行对弈的部分图如图1-2为所示。图1-2人机对弈图返回到本节目录1.1.2数据的逻辑结构特点：图中将每一个棋盘看作一个数据元素，则数据元素之间的关系要比表1-1要复杂许多。图中数据元素之间是一对多关系，即一个数据元素向上和一个数据元素相连（称为双亲结点），向下和多个数据元素相连（称为孩子结点）。我们将这种关系称为“树型结构”。4）图形结构或网状结构结构中的任意数据元素之间都可以有关系，元素之间存在着“多对多”的关系。返回到本节目录1.1.2数据的逻辑结构（【例1.3】制定教学计划在制定教学计划时，需要考虑各门课程的开设顺序。有些课程需要先导先修课程，有些课程则不需要，而有些课程又是其他课程的先导先修课程。比如，计算机专业课程的开设情况如表1-2所示。返回到本节目录1.1.2数据的逻辑结构教学计划的关系图如图1-3所示。图1-3教学计划关系图特点：图中数据元素存在着多对多的任意关系。一个结点可能有多个直接前驱和直接后继。C1C3C4C8C5C6C7C9C2返回到本节目录1.1.2数据的逻辑结构1.1.3数据的存储结构数据在计算机中的存储表示称为数据的存储结构，也称为物理结构。数据的存储结构是逻辑结构在计算机存储器中的实现。本书将介绍常用的两种基本的存储结构：顺序存储结构和链式存储结构。数据的逻辑结构和存储结构的关系是：存储结构是逻辑关系的映像与元素本身映像，是数据结构的实现；逻辑结构是数据结构的抽象。返回到本节目录1.顺序存储结构顺序存储结构：借助元素在存储器中的相对位置来表示数据元素间的逻辑关系。【例1.4】对于表1-1提出的学生信息登记表进行存储，假定每个元素占用50个存储单元，数据从1000号单元开始由低地址向高地址存放，对应的顺序存储结构如表1-3所示。返回到本节目录1.1.3数据的存储结构顺序存储结构的主要特点：可实现对各数据元素的随机访问。这是因为只要知道存储的首地址以及每个数据元素所占的存储单元，就可以计算出各数据元素的存储地址。不利于修改，在对数据元素进行插入、删除运算时可能要移动一系列的数据元素。返回到本节目录1.1.3数据的存储结构2.链式存储结构链式存储结构：借助指示元素存储地址的指针表示数据元素间的逻辑关系。【例1.5】对于表1-1学生信息登记表进行链式存储时，在每个数据元素后方附加一个指向“下一个结点地址”的指针字段，用于存放后继数据元素的存储地址，每个数据元素的地址是随机的，可以不连续。对应的链式存储结构见表1-4所示。返回到本节目录1.1.3数据的存储结构链式存储结构的主要特点：利于修改，在对数据元素进行插入、删除运算时，仅需修改数据元素的指针字段值，而不必移动数据元素。由于逻辑上相邻的数据元素在存储位置中不一定相邻，因此，链式存储结构不能对数据元素进行随机访问。返回到本节目录1.1.3数据的存储结构1.1.4抽象数据类型1．抽象数据类型的定义抽象数据类型（AbstractDataType，简称ADT）是指一个数学模型以及定义在该模型上的一组操作。2．抽象数据类型的表示抽象数据类型实际上就是对该数据结构的定义。因为它定义了一个数据的逻辑结构以及在此结构上的一组算法。可以用一个三元组表示：ADT=（Ｄ，Ｓ，Ｐ）其中，D是数据对象，S是D上的关系集，P是对D的基本操作集。返回到本节目录抽象数据类型通常是指由用户定义，用以表示应用问题的数据类型，抽象数据类型由基本的数据类型组成，并包括一组相关的服务（或称操作）。抽象数据类型有些类似于pascal语言中的记录（record）类型和c语言中的构造（struct）类型，但它增加了相关的服务。3．ADT的两个重要特征（1）数据抽象用ADT描述程序处理的实体时，强调的是其本质的特征、其所能完成的功能以及它和外部用户的接口（即外界使用它的方法）。（2）数据封装将实体的外部特性和其内部实现细节分离，并且对外部用户隐藏其内部实现细节。返回到本节目录1.1.4抽象数据类型1.2算法和算法分析1.2.1算法的概念1.2.2算法分析1.2.3相关C语言知识回顾返回到总目录1.2.1算法的概念1．算法的定义瑞士著名的计算机科学家N.Wirth所提出的著名公式“程序=算法+数据结构”，所谓算法，就是为解决特定问题而采取的步骤和方法。2．算法的特性一个算法应该具有下列特性：（1）有穷性：一个算法必须（对任何合法的输入值）在执行有限步之后结束。（2）确定性：算法中的每一条指令必须有确切的含义，不会产生二义性。返回到本节目录（3）可行性：算法中描述的操作都可以通过执行有限次基本操作来实现。（4）输入：一个算法有零个或多个输入。（5）输出：一个算法必有一个或多个输出。3．算法的评价要设计一个好的算法通常需要考虑以下几方面的要求：（1）正确性：要求算法能够正确地执行预先规定的功能，并达到所期望的性能要求。（2）可读性：为了便于理解、测试和修改算法，算法应该具有良好的可读性。返回到本节目录1.2.1算法的概念（3）健壮性：当输入非法的数据时，算法应能恰当地做出反应或进行相应处理，而不是产生莫名奇妙的输出结果。并且处理出错的方法不应是中断程序的执行，而是返回一个表示错误或错误性质的值，以便在更高的抽象层次上进行处理。（4）高效性：对同一个问题，执行时间越短，算法的效率越高。（5）低存储量：完成相同的功能，执行算法所占用的存储空间应尽可能的少。返回到本节目录1.2.1算法的概念4．算法的描述为了表示一个算法，可以用多种不同的方法，常用的有自然语言、传统流程图、结构化流程图、N-S流程图等表示。本书采用C的描述语言实现对各种数据结构及算法的操作描述，算法是以函数形式描述，描述如下：类型标识符函数名(形式参数表)/*算法说明*/{语句序列}返回到本节目录1.2.1算法的概念1.2.2算法分析在算法满足正确性的前提下，如何评价不同算法的优劣呢？通常主要考虑算法的时间复杂度和空间复杂度这两方面。一般情况下，鉴于运算空间（内存）较为充足，所以把算法的时间复杂度作为重点分析。1.时间复杂度（TimeComplexity）一个算法所需的运算时间通常与所解决问题的规模大小有关。问题规模是一个和输入有关的量，用n表示问题规模的量，把算法运行所需的时间T表示为n的函数，记为T(n)。不同的T(n)算法，当n增长时，运算时间增长的快慢很不相同。一个算法所需的执行时间就是该算法中所有语句执行次数之和。当n逐渐增大时T(n)的极限情况，一般简称为时间复杂度。返回到本节目录当讨论一个程序的运行时间时，注重的不是T(n)的具体值，而是它的增长率。T(n)的增长率与算法中数据的输入规模紧密相关，而数据输入规模往往用算法中的某个变量的函数来表示，通常是f(n)。随着数据输入规模的增大，f(n)的增长率与T(n)的增长率相近，因此T(n)同f(n)在数量级上是一致的。记作：T(n)=O(f(n))其中，大写字母O为Order(数量级)的字头，f(n)为函数形式，如T(n)=O(n2)。返回到本节目录1.2.2算法分析注意，当T(n)为多项式时，可只取其最高次幂项并省略其系数，其它的次幂项及系数均略去不写。一般地，对于足够大的n，常用的时间复杂性存在以下顺序：O(1)O(log2n)O(n)O(nlog2n)O(n2)O(n3)O(2n)算法时间复杂度的数量级越大，表示该算法的效率越低，反之越高。例如O(1)为常数数量级,，即算法的时间复杂性与输入规模n无关。返回到本节目录1.2.2算法分析【例1.6】分析以下算法的时间复杂度。x=0;y=0;for(k=1;k=n;k++)x++;（1）执行n次for(i=1;i=n;i++)for(j=1;j=n;j++)y++;（2）执行n2次解：T(n)=n+n2T(n)=O(n2)上述算法中的基本运算是语句（2），其执行频率为n2。则T(n)=n2=O(n2)返回到本节目录1.2.2算法分析【例1.7】分析以下算法的时间复杂度。i=1;while(i=n)i=2*i;(1)执行f(n)次解：设语句（1）执行次数是f(n)，则2f(n)≤n得到T(n)=O(log2n)返回到本节目录1.2.2算法分析【例1.8】求两个矩阵相乘的函数的时间复杂度。voi