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

《数据结构实用教程(c语言版).ppt》由会员分享，可在线阅读，更多相关《数据结构实用教程(c语言版).ppt（608页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构实用教程（C语言版）第第1章章概论概论本章主要介绍以下内容：本章主要介绍以下内容：本章主要介绍以下内容：本章主要介绍以下内容：数据结构中涉及的相关概念数据结构中涉及的相关概念数据结构中涉及的相关概念数据结构中涉及的相关概念数据结构研究的主要内容数据结构研究的主要内容数据结构研究的主要内容数据结构研究的主要内容算法的概念、描述方法以及评价标准算法的概念、描述方法以及评价标准算法的概念、描述方法以及评价标准算法的概念、描述方法以及评价标准本章目录本章目录1.11.1什么是数据结构什么是数据结构什么是数据结构什么是数据结构11.21.2算法和算法分析算法和算法分析算法和算法分析算法和算法分析

2、25.55.5哈夫曼树哈夫曼树哈夫曼树哈夫曼树51.31.3本章小结本章小结本章小结本章小结3结束结束1.1什么是数据结构什么是数据结构v1.1.1基本概念及术语基本概念及术语v1.1.2数据的逻辑结构数据的逻辑结构v1.1.3数据的存储结构数据的存储结构v1.1.4抽象数据类型抽象数据类型返回到本节目录返回到总目录返回到总目录返回到总目录返回到总目录基本概念及术语基本概念及术语在系统的学习数据结构知识之前，先了解一些相在系统的学习数据结构知识之前，先了解一些相关概念和术语。关概念和术语。1数据（数据（Data）指所有能输入到计算机中并被计算机程序处理的指所有能输入到计算机中并被计算机程序处理

3、的符号的总称。例如，整数、实数、字符、图像、符号的总称。例如，整数、实数、字符、图像、声音等都是数据。声音等都是数据。2数据元素（数据元素（DataElement）数据元素（也称为结点）是数据的基本单位，在数据元素（也称为结点）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处计算机程序中通常作为一个整体进行考虑和处理。一个数据元素可以由若干个数据项组成。理。一个数据元素可以由若干个数据项组成。数据项是数据处理中不可分割的最小单位。数据项是数据处理中不可分割的最小单位。返回到本节目录3数据结构（数据结构（DataStructure）是相互之间存在一种或多种特定关系的数据元是相互之间存

4、在一种或多种特定关系的数据元素的集合。这些数据元素不是孤立存在的，素的集合。这些数据元素不是孤立存在的，而是有着某种关系，这种关系称为结构。而是有着某种关系，这种关系称为结构。数据结构一般包括以下三个方面内容：数据结构一般包括以下三个方面内容：（1）数据元素之间的逻辑关系，也称数据的）数据元素之间的逻辑关系，也称数据的逻辑结构。逻辑结构。（2）数据元素及其关系在计算机存储器内的）数据元素及其关系在计算机存储器内的表示，称为数据的存储结构。表示，称为数据的存储结构。（3）数据的运算，即对数据施加的操作。）数据的运算，即对数据施加的操作。返回到本节目录基本概念及术语基本概念及术语数据结构定义：按某

5、种逻辑关系组织起来的一批数据，数据结构定义：按某种逻辑关系组织起来的一批数据，按一定的映像方式把它存放在计算机存储器中，并按一定的映像方式把它存放在计算机存储器中，并在这些数据上定义了一个运算的集合，就叫做数据在这些数据上定义了一个运算的集合，就叫做数据结构。结构。简言之，数据结构简言之，数据结构=逻辑结构逻辑结构+存储结构存储结构+运算集合运算集合。4数据类型数据类型(DataType)数据类型是一组性质相同的值集合以及定义在这个值数据类型是一组性质相同的值集合以及定义在这个值集合上的一组操作的总称。集合上的一组操作的总称。如在高级语言中，整型类型的取值范围为：如在高级语言中，整型类型的取值

6、范围为：-32768+32767，运算符集合为加、减、乘、除、取模，运算符集合为加、减、乘、除、取模，即即+、-、*、/、%。返回到本节目录基本概念及术语基本概念及术语返回到本节目录基本概念及术语基本概念及术语1.1.2数据的逻辑结构数据的逻辑结构1定义定义数据的逻辑结构是指数据元素之间逻辑关系描数据的逻辑结构是指数据元素之间逻辑关系描述。可以用一个二元组表示，其形式化描述述。可以用一个二元组表示，其形式化描述为：为：Data_Structure=（D，R）其中其中D是数据元素的有限集合，是数据元素的有限集合，R是是D上关系的上关系的有限集合。数据的逻辑结构是从逻辑关系上有限集合。数据的逻辑结

7、构是从逻辑关系上描述数据，与数据的存储无关，是独立于计描述数据，与数据的存储无关，是独立于计算机的。算机的。返回到本节目录2数据的逻辑结构的分类数据的逻辑结构的分类根据数据元素之间的逻辑关系的不同特性，分根据数据元素之间的逻辑关系的不同特性，分为下列四类基本结构，如图为下列四类基本结构，如图1-1所示。所示。（a）集合结构）集合结构（b）线性结构）线性结构（c）树型结构）树型结构（d）图形结构）图形结构图图1-1数据结构的四种基本逻辑结构数据结构的四种基本逻辑结构返回到本节目录1.1.2数据的逻辑结构数据的逻辑结构（1）集合）集合结构中的数据元素之间除了结构中的数据元素之间除了“同属于一个集合

8、同属于一个集合”的关系外，别无其他关系，这是一种最简的关系外，别无其他关系，这是一种最简单的数据结构。单的数据结构。（2）线性结构）线性结构结构中的数据元素之间存在着结构中的数据元素之间存在着“一对一一对一”的关的关系。系。【例例1.1】学籍档案管理学籍档案管理假设一个学籍档案管理系统应包含如表假设一个学籍档案管理系统应包含如表1-1所所示的学生信息。示的学生信息。返回到本节目录1.1.2数据的逻辑结构数据的逻辑结构特点：特点：表中的每一行是一个数据元素（或记录、结点），它表中的每一行是一个数据元素（或记录、结点），它由学号、姓名、性别及出生年月等数据项组成。由学号、姓名、性别及出生年月等数据

9、项组成。表中数据元素之间是一种先后关系，对于表中任一结表中数据元素之间是一种先后关系，对于表中任一结点，与它相邻且在它前面的结点（称为直接前驱）点，与它相邻且在它前面的结点（称为直接前驱）最多只有一个；与表中任一结点相邻且在其后的结最多只有一个；与表中任一结点相邻且在其后的结点（称为直接后继）也最多只有一个。我们将这种点（称为直接后继）也最多只有一个。我们将这种关系称为关系称为“线性结构线性结构”。返回到本节目录1.1.2数据的逻辑结构数据的逻辑结构（3）树型结构）树型结构结构中的数据元素之间存在着结构中的数据元素之间存在着“一对多一对多”的关的关系。系。【例例1.2】人机对弈人机对弈人与计算

10、机进行对弈的部分图如图人与计算机进行对弈的部分图如图1-2为所示。为所示。图图1-2人机对弈图人机对弈图返回到本节目录1.1.2数据的逻辑结构数据的逻辑结构特点：特点：图中将每一个棋盘看作一个数据元素，则数据图中将每一个棋盘看作一个数据元素，则数据元素之间的关系要比表元素之间的关系要比表1-1要复杂许多。要复杂许多。图中数据元素之间是一对多关系，即一个数据图中数据元素之间是一对多关系，即一个数据元素向上和一个数据元素相连（称为双亲结元素向上和一个数据元素相连（称为双亲结点），向下和多个数据元素相连（称为孩子点），向下和多个数据元素相连（称为孩子结点）。我们将这种关系称为结点）。我们将这种关系称

11、为“树型结构树型结构”。4）图形结构或网状结构）图形结构或网状结构结构中的任意数据元素之间都可以有关系，元结构中的任意数据元素之间都可以有关系，元素之间存在着素之间存在着“多对多多对多”的关系。的关系。返回到本节目录1.1.2数据的逻辑结构数据的逻辑结构返回到本节目录1.1.2数据的逻辑结构数据的逻辑结构教学计划的关系图如图教学计划的关系图如图1-3所示。所示。图图1-3教学计划关系图教学计划关系图特点：特点：图中数据元素存在着多对多的任意关系。一个图中数据元素存在着多对多的任意关系。一个结点可能有多个直接前驱和直接后继。结点可能有多个直接前驱和直接后继。返回到本节目录1.1.2数据的逻辑结构

12、数据的逻辑结构1.1.3数据的存储结构数据的存储结构数据在计算机中的存储表示称为数据的存储结数据在计算机中的存储表示称为数据的存储结构，也称为物理结构。数据的存储结构是逻构，也称为物理结构。数据的存储结构是逻辑结构在计算机存储器中的实现。本书将介辑结构在计算机存储器中的实现。本书将介绍常用的两种基本的存储结构：顺序存储结绍常用的两种基本的存储结构：顺序存储结构和链式存储结构。构和链式存储结构。数据的逻辑结构和存储结构的关系是：存储结数据的逻辑结构和存储结构的关系是：存储结构是逻辑关系的映像与元素本身映像，是数构是逻辑关系的映像与元素本身映像，是数据结构的实现；逻辑结构是数据结构的抽象。据结构的

13、实现；逻辑结构是数据结构的抽象。返回到本节目录1.顺序存储结构顺序存储结构顺序存储结构：借助元素在存储器中的相对位顺序存储结构：借助元素在存储器中的相对位置来表示数据元素间的逻辑关系。置来表示数据元素间的逻辑关系。【例例1.4】对于表对于表1-1提出的学生信息登记表提出的学生信息登记表进行存储，假定每个元素占用进行存储，假定每个元素占用50个存储单元，个存储单元，数据从数据从1000号单元开始由低地址向高地址号单元开始由低地址向高地址存放，对应的顺序存储结构如表存放，对应的顺序存储结构如表1-3所示。所示。返回到本节目录1.1.3数据的存储结构数据的存储结构顺序存储结构的主要特点：顺序存储结构

14、的主要特点：v可实现对各数据元素的随机访问。这是因为可实现对各数据元素的随机访问。这是因为只要知道存储的首地址以及每个数据元素所只要知道存储的首地址以及每个数据元素所占的存储单元，就可以计算出各数据元素的占的存储单元，就可以计算出各数据元素的存储地址。存储地址。v不利于修改，在对数据元素进行插入、删除不利于修改，在对数据元素进行插入、删除运算时可能要移动一系列的数据元素。运算时可能要移动一系列的数据元素。返回到本节目录1.1.3数据的存储结构数据的存储结构2.链式存储结构链式存储结构链式存储结构：借助指示元素存储地址的指针链式存储结构：借助指示元素存储地址的指针表示数据元素间的逻辑关系。表示数

15、据元素间的逻辑关系。【例例1.5】对于表对于表1-1学生信息登记表进行链学生信息登记表进行链式存储时，在每个数据元素后方附加一个指式存储时，在每个数据元素后方附加一个指向向“下一个结点地址下一个结点地址”的指针字段，用于存的指针字段，用于存放后继数据元素的存储地址，每个数据元素放后继数据元素的存储地址，每个数据元素的地址是随机的，可以不连续。对应的链式的地址是随机的，可以不连续。对应的链式存储结构见表存储结构见表1-4所示。所示。返回到本节目录1.1.3数据的存储结构数据的存储结构链式存储结构的主要特点：链式存储结构的主要特点：v利于修改，在对数据元素进行插入、删除运利于修改，在对数据元素进行

16、插入、删除运算时，仅需修改数据元素的指针字段值，而算时，仅需修改数据元素的指针字段值，而不必移动数据元素。不必移动数据元素。v由于逻辑上相邻的数据元素在存储位置中不由于逻辑上相邻的数据元素在存储位置中不一定相邻，因此，链式存储结构不能对数据一定相邻，因此，链式存储结构不能对数据元素进行随机访问。元素进行随机访问。返回到本节目录1.1.3数据的存储结构数据的存储结构1.1.4抽象数据类型抽象数据类型1抽象数据类型的定义抽象数据类型的定义抽象数据类型（抽象数据类型（AbstractDataType，简，简称称ADT）是指一个数学模型以及定义在该模）是指一个数学模型以及定义在该模型上的一组操作。型上

17、的一组操作。2抽象数据类型的表示抽象数据类型的表示抽象数据类型实际上就是对该数据结构的定义。抽象数据类型实际上就是对该数据结构的定义。因为它定义了一个数据的逻辑结构以及在此因为它定义了一个数据的逻辑结构以及在此结构上的一组算法。可以用一个三元组表示：结构上的一组算法。可以用一个三元组表示：ADT=（，）（，）其中，其中，D是数据对象，是数据对象，S是是D上的关系集，上的关系集，P是是对对D的基本操作集。的基本操作集。返回到本节目录抽象数据类型通常是指由用户定义，用以表示应用问抽象数据类型通常是指由用户定义，用以表示应用问题的数据类型，抽象数据类型由基本的数据类型组题的数据类型，抽象数据类型由基

18、本的数据类型组成，并包括一组相关的服务（或称操作）。成，并包括一组相关的服务（或称操作）。抽象数据类型有些类似于抽象数据类型有些类似于pascal语言中的记录语言中的记录（record）类型和）类型和c语言中的构造（语言中的构造（struct）类型，）类型，但它增加了相关的服务。但它增加了相关的服务。3ADT的两个重要特征的两个重要特征（1）数据抽象用）数据抽象用ADT描述程序处理的实体时，强调描述程序处理的实体时，强调的是其本质的特征、其所能完成的功能以及它和外的是其本质的特征、其所能完成的功能以及它和外部用户的接口（即外界使用它的方法）。部用户的接口（即外界使用它的方法）。（2）数据封装将

19、实体的外部特性和其内部实现细节分）数据封装将实体的外部特性和其内部实现细节分离，并且对外部用户隐藏其内部实现细节。离，并且对外部用户隐藏其内部实现细节。返回到本节目录1.1.4抽象数据类型抽象数据类型1.2算法和算法分析算法和算法分析v1.2.1算法的概念算法的概念v1.2.2算法分析算法分析v1.2.3相关相关C语言知识回顾语言知识回顾返回到总目录返回到总目录返回到总目录返回到总目录1.2.1算法的概念算法的概念1算法的定义算法的定义瑞士著名的计算机科学家瑞士著名的计算机科学家N.Wirth所提出的著所提出的著名公式名公式“程序程序=算法算法+数据结构数据结构”，所谓算，所谓算法，就是为解决

20、特定问题而采取的步骤和方法，就是为解决特定问题而采取的步骤和方法。法。2算法的特性算法的特性一个算法应该具有下列特性：一个算法应该具有下列特性：（1）有穷性：一个算法必须（对任何合法的）有穷性：一个算法必须（对任何合法的输入值）在执行有限步之后结束。输入值）在执行有限步之后结束。（2）确定性：算法中的每一条指令必须有确）确定性：算法中的每一条指令必须有确切的含义，不会产生二义性。切的含义，不会产生二义性。返回到本节目录（3）可行性：算法中描述的操作都可以通过）可行性：算法中描述的操作都可以通过执行有限次基本操作来实现。执行有限次基本操作来实现。（4）输入：一个算法有零个或多个输入。）输入：一个

21、算法有零个或多个输入。（5）输出：一个算法必有一个或多个输出。）输出：一个算法必有一个或多个输出。3算法的评价算法的评价要设计一个好的算法通常需要考虑以下几方面要设计一个好的算法通常需要考虑以下几方面的要求：的要求：（1）正确性：要求算法能够正确地执行预先）正确性：要求算法能够正确地执行预先规定的功能，并达到所期望的性能要求。规定的功能，并达到所期望的性能要求。（2）可读性：为了便于理解、测试和修改算）可读性：为了便于理解、测试和修改算法，算法应该具有良好的可读性。法，算法应该具有良好的可读性。返回到本节目录1.2.1算法的概念算法的概念（3）健壮性：当输入非法的数据时，算法应）健壮性：当输入

22、非法的数据时，算法应能恰当地做出反应或进行相应处理，而不是能恰当地做出反应或进行相应处理，而不是产生莫名奇妙的输出结果。并且处理出错的产生莫名奇妙的输出结果。并且处理出错的方法不应是中断程序的执行，而是返回一个方法不应是中断程序的执行，而是返回一个表示错误或错误性质的值，以便在更高的抽表示错误或错误性质的值，以便在更高的抽象层次上进行处理。象层次上进行处理。（4）高效性：对同一个问题，执行时间越短，）高效性：对同一个问题，执行时间越短，算法的效率越高。算法的效率越高。（5）低存储量：完成相同的功能，执行算法）低存储量：完成相同的功能，执行算法所占用的存储空间应尽可能的少。所占用的存储空间应尽可

23、能的少。返回到本节目录1.2.1算法的概念算法的概念4算法的描述算法的描述为了表示一个算法，可以用多种不同的方法，为了表示一个算法，可以用多种不同的方法，常用的有自然语言、传统流程图、结构化流常用的有自然语言、传统流程图、结构化流程图、程图、N-S流程图等表示。本书采用流程图等表示。本书采用C的描的描述语言实现对各种数据结构及算法的操作描述语言实现对各种数据结构及算法的操作描述，算法是以函数形式描述，描述如下：述，算法是以函数形式描述，描述如下：类类型型标识标识符符函数名函数名(形式参数表形式参数表)/*算法算法说说明明*/语语句序列句序列返回到本节目录1.2.1算法的概念算法的概念1.2.2

24、算法分析算法分析在算法满足正确性的前提下，如何评价不同算法的优在算法满足正确性的前提下，如何评价不同算法的优劣呢？通常主要考虑算法的时间复杂度和空间复杂劣呢？通常主要考虑算法的时间复杂度和空间复杂度这两方面。一般情况下，鉴于运算空间（内存）度这两方面。一般情况下，鉴于运算空间（内存）较为充足，所以把算法的时间复杂度作为重点分析。较为充足，所以把算法的时间复杂度作为重点分析。1.时间复杂度（时间复杂度（TimeComplexity）一个算法所需的运算时间通常与所解决问题的规模大一个算法所需的运算时间通常与所解决问题的规模大小有关。问题规模是一个和输入有关的量，用小有关。问题规模是一个和输入有关的

25、量，用n表表示问题规模的量，把算法运行所需的时间示问题规模的量，把算法运行所需的时间T表示为表示为n的函数，记为的函数，记为T(n)。不同的。不同的T(n)算法，当算法，当n增长时，增长时，运算时间增长的快慢很不相同。一个算法所需的执运算时间增长的快慢很不相同。一个算法所需的执行时间就是该算法中所有语句执行次数之和。当行时间就是该算法中所有语句执行次数之和。当n逐逐渐增大时渐增大时T(n)的极限情况，一般简称为时间复杂度。的极限情况，一般简称为时间复杂度。返回到本节目录当讨论一个程序的运行时间时，注重的不是当讨论一个程序的运行时间时，注重的不是T(n)的具体值，而是它的增长率。的具体值，而是它

26、的增长率。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算法分

27、析算法分析返回到本节目录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;(

28、1)执行执行f(n)次次解：设语句（解：设语句（1）执行次数是）执行次数是f(n)，则，则2f(n)n得到得到T(n)=O(log2n)返回到本节目录1.2.2算法分析算法分析【例例1.8】求两个矩阵相乘的函数的时间复杂度。求两个矩阵相乘的函数的时间复杂度。voidmult(inta,intb,intc)/*以二维数组存储矩阵元素，以二维数组存储矩阵元素，c为为a和和b的乘积的乘积*/for(i=1;i=n;+i)(1)执行执行n次次for(j=1;j=n;+j)(2)执行执行n2次次ci,j=0;for(k=1;k成员名成员名等价于：等价于：(*指针名指针名).成员名成员名等价于：结构体变量

29、名等价于：结构体变量名.成员名成员名在本书中，在程序内大量使用结构体类型的指在本书中，在程序内大量使用结构体类型的指针，所以大都采用第一种写法。针，所以大都采用第一种写法。返回到本节目录1.2.3相关相关C语言知识回顾语言知识回顾（4）用）用typedef定义类型定义类型除了可以直接使用除了可以直接使用C提供的标准类型名和自己提供的标准类型名和自己声明的结构体类型外，还可以用声明的结构体类型外，还可以用typedef声声明新的类型名来代替已有的类型名。其基本明新的类型名来代替已有的类型名。其基本定义格式如下：定义格式如下：【格式格式】typedef原类型名原类型名新类型名新类型名;其中，其中，

30、typedef为关键字，表示重定义。原类为关键字，表示重定义。原类型名是型名是C语言提供的任语言提供的任意意一种数据类型，可一种数据类型，可以是简单数据类型，也可以是构造数据类型。以是简单数据类型，也可以是构造数据类型。新类型名为原类型名的一个别名。使用新类新类型名为原类型名的一个别名。使用新类型名就像使用原类型名那样定义变量。型名就像使用原类型名那样定义变量。返回到本节目录1.2.3相关相关C语言知识回顾语言知识回顾2动态存储分配函数动态存储分配函数C语言提供了动态分配函数来实现动态存储分配。最常语言提供了动态分配函数来实现动态存储分配。最常用的动态存储分配函数有以下两个。用的动态存储分配函

31、数有以下两个。（1）分配内存空间函数）分配内存空间函数malloc()【格式格式】(类型名类型名*)malloc(要分配的内存字节数要分配的内存字节数size)【功能功能】在内存中分配一个长度为在内存中分配一个长度为size的连续存储空的连续存储空间，返回值是新分配存储空间的首地址，若内存不间，返回值是新分配存储空间的首地址，若内存不足，则返回足，则返回NULL。其中，类型名表示把该存储空。其中，类型名表示把该存储空间用于何种数据类型。（类型名间用于何种数据类型。（类型名*）表示把）表示把malloc函数返回值强制转换为该类型指针。函数返回值强制转换为该类型指针。返回到本节目录1.2.3相关相

32、关C语言知识回顾语言知识回顾（2）释放内存空间函数）释放内存空间函数free()【格式格式】free(指向要释放单元的指针名指向要释放单元的指针名)【功能功能】释放该指针所指的一块存储空间，该释放该指针所指的一块存储空间，该空间系统可另作它用。注意这个指针所指的空间系统可另作它用。注意这个指针所指的空间必须是由空间必须是由malloc()函数和函数和calloc()函函数分配的才行。数分配的才行。free函数无返回值。例如：函数无返回值。例如：int*pt;pt=(int*)malloc(sizeof(int);free(pt);程序段表示释放程序段表示释放pt指向的存储空间。指向的存储空间。

33、返回到本节目录1.2.3相关相关C语言知识回顾语言知识回顾3函数的定义与调用函数的定义与调用在本书中，绝大多数的算法都是编写成在本书中，绝大多数的算法都是编写成C语言的函数，语言的函数，这些函数需要通过编写相应的主函数才能被执行。这些函数需要通过编写相应的主函数才能被执行。（1）函数的定义）函数的定义函数的定义如下：函数的定义如下：【格式格式】函数函数类类型型函数名（形参表）函数名（形参表）内部内部变变量定量定义义函数主体函数主体语语句句返回返回语语句句返回到本节目录1.2.3相关相关C语言知识回顾语言知识回顾（2）函数的调用）函数的调用【格式格式】函数类型函数类型函数名（实参表）函数名（实参

34、表）;【说明说明】1实参表中各参数应与形参表中各参数类型实参表中各参数应与形参表中各参数类型及个数相符。及个数相符。2在调用函数时，表达式应与该函数的类型在调用函数时，表达式应与该函数的类型相符，如果该函数有返回值时，在调用时要相符，如果该函数有返回值时，在调用时要将该函数的返回值赋给相同类型的变量。将该函数的返回值赋给相同类型的变量。返回到本节目录1.2.3相关相关C语言知识回顾语言知识回顾4TurboC2.0中的汉字显示中的汉字显示在在TurboC2.0中，如果想输入和显示汉字，中，如果想输入和显示汉字，需要使用需要使用UCDOS汉字系统。但现在的汉字系统。但现在的Windows操作系统不

35、支持操作系统不支持UCDOS汉字系汉字系统的统的16位显示。下面介绍一种能在位显示。下面介绍一种能在WindowsXP系统环境下，在系统环境下，在TurboC2.0中使用中使用UCDOS的汉字系统的方法。的汉字系统的方法。返回到本节目录1.2.3相关相关C语言知识回顾语言知识回顾（1）将）将UCDOS的核心文件进行兼容性设置的核心文件进行兼容性设置（有的机器可省略这步，直接执行（有的机器可省略这步，直接执行（2）。）。点点“开始开始”菜单菜单-“所有程序所有程序”-“附件附件”-“程序兼容性向导程序兼容性向导”-“我想手动定位程序我想手动定位程序”-“浏览浏览”-win98-256色，色，64

36、0X480-程序工程序工作正确吗？选作正确吗？选“是，设置此程序为一直使用是，设置此程序为一直使用兼容性设置。兼容性设置。”完成。有的完成。有的UCDOS版本的版本的核心文件是核心文件是knlvga.exe，也要照此进行兼，也要照此进行兼容性设置。容性设置。返回到本节目录1.2.3相关相关C语言知识回顾语言知识回顾（2）运行）运行UCDOS系统文件的方法。系统文件的方法。进入到命令提示符（进入到命令提示符（MS-DOS状态）（状态）（“开开始始”-“程序程序”-“附件附件”-“命令提示符命令提示符”）切换到）切换到UCDOS目录。（带下划线文字目录。（带下划线文字为输入的命令信息，为输入的命令

37、信息，“”表示回车键。假表示回车键。假设设UCDOS文件夹在文件夹在C盘根目录内，可输入盘根目录内，可输入如下命令：）如下命令：）C:DocumentsandSettingscd（回到（回到C盘根目录下）盘根目录下）C:cdUcdos（进入（进入UCDOS的目录）的目录）返回到本节目录1.2.3相关相关C语言知识回顾语言知识回顾这时不要运行这时不要运行UCDOS.BAT，分别一项一项，分别一项一项命令运行。如：命令运行。如：C:UDOS C:UDOS C:UDOS C:UDOS C:UDOS（五笔输入，如不（五笔输入，如不用五笔可省略此步）用五笔可省略此步）（注：可直接输入命令名，如输入（注：

38、可直接输入命令名，如输入“rd16”，省略扩展名，省略扩展名“.com”）返回到本节目录1.2.3相关相关C语言知识回顾语言知识回顾就可以顺利进入就可以顺利进入ucdos。然后，退出。然后，退出UCDOS目录，再进入目录，再进入tc目录运行目录运行tc.exe文件就可以文件就可以在在TurboC2.0中顺利的输入和显示汉字了。中顺利的输入和显示汉字了。如：如：C:UDOScd C:cdtc（假定（假定TurboC2.0的文的文件夹名称为件夹名称为TC）C:TCtc.exe(可直接输入可直接输入tc 即可即可)即可进行即可进行TurboC2.0输入并运行输入并运行C语言源程语言源程序了。序了。返

39、回到本节目录1.2.3相关相关C语言知识回顾语言知识回顾（3）常用的）常用的TurboC2.0快捷键快捷键Alt+F：文件菜单：文件菜单Load打开文件打开文件Save保存保存Writeto另存为另存为Quit退出退出Alt+R：运行菜单：运行菜单Run（或（或Ctrl+F9）运行程序运行程序UserScreen(或或Alt+F5)查看运行结果查看运行结果Alt+E：编辑（显示光标，有时调试有错时可：编辑（显示光标，有时调试有错时可将光标重新显示在编辑区）将光标重新显示在编辑区）F9：编译系统查错：编译系统查错返回到本节目录1.2.3相关相关C语言知识回顾语言知识回顾（4）更改汉字输入法）更改

40、汉字输入法Alt+F1区位区位Alt+F2全拼全拼Alt+F3双拼双拼Alt+F5五笔（必须在五笔（必须在UCDOS中输入中输入wb命命令才能用此项）令才能用此项）Alt+F6英文英文单次按右单次按右shift键键可显示或隐藏中文输入法可显示或隐藏中文输入法返回到本节目录1.2.3相关相关C语言知识回顾语言知识回顾1.3本章小结本章小结本章主要介绍了有关数据结构的以下几方面：本章主要介绍了有关数据结构的以下几方面：（1）数据结构主要研究数据的逻辑结构、存）数据结构主要研究数据的逻辑结构、存储结构和运算方法。储结构和运算方法。（2）数据的逻辑结构包括：集合、线性结构、）数据的逻辑结构包括：集合、

41、线性结构、树型结构、图形结构四种基本类型。树型结构、图形结构四种基本类型。（3）数据的存储结构包括：顺序存储结构和）数据的存储结构包括：顺序存储结构和链式存储结构。链式存储结构。（4）算法是对特定问题求解步骤的一种描述，）算法是对特定问题求解步骤的一种描述，是指令的有限序列。算法具有：有穷性、确是指令的有限序列。算法具有：有穷性、确定性、正确性、输入、输出等特性。定性、正确性、输入、输出等特性。（5）算法的时间复杂度与空间复杂度。）算法的时间复杂度与空间复杂度。返回到总目录返回到总目录返回到总目录返回到总目录 数据结构实用教程（C语言版）中国水利水电出版社第第2章章线性表线性表本章主要介绍下列

42、内容本章主要介绍下列内容本章主要介绍下列内容本章主要介绍下列内容线性表的定义和基本操作线性表的定义和基本操作线性表的定义和基本操作线性表的定义和基本操作线性表的顺序存储结构线性表的顺序存储结构线性表的顺序存储结构线性表的顺序存储结构线性表的链式存储结构线性表的链式存储结构线性表的链式存储结构线性表的链式存储结构线性表的应用举例线性表的应用举例线性表的应用举例线性表的应用举例本章目录本章目录2.12.1线性表的基本概念线性表的基本概念线性表的基本概念线性表的基本概念12.22.2顺序表顺序表顺序表顺序表22.32.3链表链表链表链表32.42.4线性表的应用举例线性表的应用举例线性表的应用举例线

43、性表的应用举例42.52.5本章小结本章小结本章小结本章小结5结束2.1 2.1 线性表的基本概念线性表的基本概念v2.1.1线性表的定义线性表的定义v2.1.2线性表的基本操作线性表的基本操作返回到总目录 线性表的定义线性表的定义1.线性表的定义线性表的定义线性表是具有相同数据类型的线性表是具有相同数据类型的n（n=0）个）个数据元素的有限序列，通常记为：数据元素的有限序列，通常记为：（a1，a2，ai-1，ai，ai+1，an）其中其中n为表长，当为表长，当n=0时称为空表。时称为空表。在线性表中相邻元素之间存在着顺序关系。如在线性表中相邻元素之间存在着顺序关系。如对于元素对于元素ai而言

44、，而言，ai-1称为称为ai的直接前驱，的直接前驱，ai+1称为称为ai的直接后继。的直接后继。返回到本节目录2.线性表的特点线性表的特点（1）有且仅有一个开始结点（）有且仅有一个开始结点（a1），它没有），它没有直接前驱；直接前驱；（2）有且仅有一个终端结点（）有且仅有一个终端结点（an），它没有），它没有直接后继；直接后继；（3）除了开始结点和终端结点以外，其余的）除了开始结点和终端结点以外，其余的结点都有且仅有一个直接前驱和一个直接后结点都有且仅有一个直接前驱和一个直接后继。继。线性表的定义线性表的定义返回到本节目录 线性表的基本操作线性表的基本操作数据结构的运算是定义在逻辑结构层次上的

45、，数据结构的运算是定义在逻辑结构层次上的，而运算的具体实现是建立在存储结构上的。而运算的具体实现是建立在存储结构上的。下面定义的线性表的基本操作仅是定义在逻下面定义的线性表的基本操作仅是定义在逻辑结构上的，每一个操作的具体实现只有在辑结构上的，每一个操作的具体实现只有在确定了线性表的存储结构之后才能完成。确定了线性表的存储结构之后才能完成。线性表的基本操作有：线性表的基本操作有：（1）初始化线性表）初始化线性表InitList(L)。其作用是建立一个空表其作用是建立一个空表L（即建立线性表的构（即建立线性表的构架，但不包含任何数据元素）。架，但不包含任何数据元素）。返回到本节目录 线性表的基本

46、操作线性表的基本操作返回到本节目录（5）插入操作）插入操作InsElem(L,i,x)。其作用是在线性表。其作用是在线性表L的的第第i个位置上插入一个值为个位置上插入一个值为x的新元素，使线性表的新元素，使线性表L由由（a1，a2，ai-1，ai，ai+1，an）变为（）变为（a1，a2，ai-1，x，ai，ai+1，an）。其中）。其中1iGetLength(L)+1。（6）删除操作）删除操作DelElem(L,i,x)。其作用是删除线性表。其作用是删除线性表L的第的第i个位置的数据元素并用个位置的数据元素并用x将其存储，使线性表将其存储，使线性表L由由（a1，a2，ai-1，ai，ai+1

47、，an）变为（）变为（a1，a2，ai-1，ai+1，an）。其中）。其中1iGetLength(L)。（7）输出元素值）输出元素值DispList(L)。其作用是依次扫描线性。其作用是依次扫描线性表表L，并输出各元素的值。，并输出各元素的值。线性表的基本操作线性表的基本操作返回到本节目录2.2顺序表顺序表v2.2.1顺序表顺序表v2.2.2顺序表的基本操作实现顺序表的基本操作实现返回到总目录1.顺序表的定义顺序表的定义数据结构在内存中的表示通常有两种形式，即顺序存数据结构在内存中的表示通常有两种形式，即顺序存储表示和链式存储表示。线性表的顺序存储表示又储表示和链式存储表示。线性表的顺序存储表

48、示又称为顺序表。线性表的顺序存储是指用一组地址连称为顺序表。线性表的顺序存储是指用一组地址连续的存储单元依次存储线性表的数据元素，我们把续的存储单元依次存储线性表的数据元素，我们把用这种存储形式存储的线性表称为顺序表。用这种存储形式存储的线性表称为顺序表。假设顺序表假设顺序表(a1，a2，ai-1，ai，ai+1，an)，每，每个数据元素占用个数据元素占用d个存储单元，则元素个存储单元，则元素ai的存储位置的存储位置为：为：Loc(ai)=Loc(a1)+(i-1)d1in2.2.1顺序表顺序表返回到本节目录其中，其中，Loc(a1)是顺序表第一个元素是顺序表第一个元素a1的存储位置，的存储位

49、置，通称为顺序表的起始地址。顺序存储结构示意图如通称为顺序表的起始地址。顺序存储结构示意图如图图2-1所示。所示。顺序表的存储特点：顺序表的存储特点：（1）顺序表的逻辑顺序和物理顺序是一致的。）顺序表的逻辑顺序和物理顺序是一致的。（2）顺序表中任意一个数据元素都可以随机存取，所）顺序表中任意一个数据元素都可以随机存取，所以顺序表是一种随机存取的存储结构。以顺序表是一种随机存取的存储结构。2.2.1顺序表顺序表返回到本节目录2.顺序表的类型定义顺序表的类型定义#defineMAXLEN100/*定义常量定义常量MAXLEN为为100表示存表示存储空间总量储空间总量*/#defineOK/*定义常量定义常量OK为为1表示成功表示成功*/#defineERROR0/*定义常量定义常量ERROR为为0表示失败表示失败*/#defineOVER-1/*定义常量定义常量OVER为为-1表示结束表示结束*/typedefintElemType;/*定义定义ElemType为为int类型类型*/typedefstruct/*顺序表存储类型顺序表存储类型*/ElemTypedataMAXLEN;/*存放线性表的数组存放线性表的数组*/intLength;/*Length是顺序表的长度是顺序表的长度*/SeqList;2.2.1顺序表顺序表返回到本节目录2.2.2顺序表的基本操作实现顺序表的基本操作