作者：曾平,喻丹丹,方颖,李春葆,蒋林
出版社：清华大学出版社
格式: AZW3, DOCX, EPUB, MOBI, PDF, TXT
数据结构简明教程(第2版)-微课版试读：
前言
用计算机求解实际问题时，必然涉及数据组织及数据处理，这些正是“数据结构”课程的主要学习内容。“数据结构”课程在计算机科学中是一门综合性的专业基础课。在计算机科学中，数据结构内容不仅作为一般程序设计的必备知识，而且是设计编译程序、操作系统、数据库系统及其他系统程序和大型应用程序的重要基础。“数据结构”课程主要的学习内容有：数据的逻辑结构描述，即表示求解问题中的数据和数据元素之间的逻辑关系；数据的存储结构设计，即将数据逻辑结构在计算机内存中表示出来；运算算法设计，即实现求解问题的功能，如设计插入、删除、修改、查询和排序算法等。
很多学习“数据结构”课程的学生都感觉数据结构比较抽象，算法理解比较困难，这很大程度上是由于没有领会数据结构的特点。首先，一个学习计算机专业的学生必须具有某种计算机语言编程能力，能够将求解问题的思路转换成计算机可以执行的程序代码，会编写基本的程序就像一个小学生识字和掌握基本的词汇一样重要；其次，必须掌握用计算机求解问题的三个层次，即提取求解问题中数据的逻辑结构、设计相应的存储结构和在存储结构上实现求解问题的算法。在设计一个算法时，先要充分理解相关的存储结构，试想一下，一个图的邻接表存储结构还没有弄清楚，如何设计一个图的遍历算法呢？所以在写算法时脑海里要准确地呈现数据的存储结构，这样才会下笔有“神”，流畅地写出正确的代码，如同小学生在掌握相当量的词汇和写作技巧后才会写出高质量的作文。
本书是作者针对数据结构课程的特点，在总结自己长期教学经验的基础上编写的。本书的“简明”性主要体现在以下两个方面。
一是内容上的简明性。本书的内容基本涵盖了最新全国计算机专业联考大纲（2018年）数据结构部分的知识点，讲授上省去了一些难度较大的应用和扩展内容，如表达式求值和迷宫问题、串的KMP算法和广义表等。
二是写作上的简明性。作者在写作时遵循“简洁如iPhone”的风格，主要体现为知识点、知识结构和算法表述简明清晰。
本书的主要特色如下。● 力求实现从C/C++语言程序设计到数据结构算法设计的无缝对接，对算法设计中用到的一些C/C++语言难点如指针、引用类型等，结合算法设计的特点予以充分的讲述。实际上，算法描述中除了引用类型属于C++，其他均采用C语言的基本语法。● 通过通俗易懂的示例简单明了地讲解数据结构解决问题的一般性思路，如一些综合性示例统一从问题描述、设计存储结构、设计基本运算算法、设计主程序和程序运行结果几方面来讲解，突出数据结构求解问题的三个层次。● 采用大量图示描述算法设计的思路，如求最小生成树的Prim算法、求图中最短路径的Dijkstra算法和各种内排序算法中都通过直观的图示，不仅描述这些算法的设计思路，而且讲解这些算法为什么这样设计的精髓。● 注重算法设计的简洁和易懂特性，同一种算法可以有多种设计方法，本书中尽可能采用简单的设计方法，如二叉排序树查找、删除等都用非递归算法来实现。● 力求归纳数据结构算法设计的通用性方法，如单链表算法设计、递归算法设计、二叉树的算法设计和图算法设计等，都相应地总结出通用求解的方法，读者只要灵活运用这些通用方法，便可以举一反三自己设计求解较复杂问题的算法。● 书中提供了大量的练习题和上机实验题，各类练习题401道，各类上机实验题118道，便于读者练习和实训。● 书中所有算法都用C/C++语言编写并上机调试，并配套有较完整的教学资源（含教学PPT和所有算法和示例源程序），读者可以从清华大学出版社网站http://www.tup.edu.cn免费下载。对于学习计算机专业的学生，直接阅读程序代码可能比看“伪码”更简明。● 本书配套有《数据结构简明教程学习与上机实验指导》（李春葆等，清华大学出版社，2018），涵盖所有练习题和上机实验题的参考答案。● 本书配套有全部知识点的教学视频，视频采用微课碎片化形式组织（含141个小视频，累计25小时），读者通过扫描二维码即可观看相关视频讲解。
全书分为9章，第1章为概论，介绍数据结构的基本概念，特别强调了基本算法设计和分析的方法；第2章为线性表，介绍线性表的概念、两种存储结构即顺序表和链表，线性表基本运算的实现算法以及线性表的应用；第3章为栈和队列，介绍这两种特殊线性表的概念、存储结构和相关应用；第4章为串，介绍串的概念、串的两种存储结构和应用；第5章为数组和稀疏矩阵，介绍数组的概念、几种特殊矩阵的压缩方法、稀疏矩阵的定义和压缩存储结构；第6章为树和二叉树，介绍树的概念和性质，二叉树的概念，二叉树的两种主要存储结构，二叉树各种运算算法设计，哈夫曼树和哈夫曼编码，特别突出了二叉树递归算法设计方法；第7章为图，介绍图的概念、图的两种主要的存储结构、图遍历算法以及图的各类应用；第8章为查找，介绍各种查找算法的实现过程；第9章为排序，介绍各种主要的内排序算法设计方法和基本的外排序过程。附录A给出了书中部分算法清单，附录B给出了全国计算机专业数据结构2017年研究生联考大纲。
本书适合作为计算机及相关专业本、专科生“数据结构”课程的教材，也适合于各类计算机考试人员参考。
本书的编写得到湖北省教改项目“计算机科学与技术专业课程体系改革”的资助，清华大学出版社给予了大力支持，许多授课教师和同学提出建设性意见，编者在此一并表示衷心感谢。
由于水平所限，尽管编者不遗余力，书中仍可能存在疏漏和不足之处，欢迎读者联系并批评指正。编 者2018年10月第1章 概论
计算机的主要功能是数据运算，这些数据绝不是杂乱无章的，而是有着某种内在联系。只有分清楚数据的联系，合理地组织数据，才能对它们进行有效的运算。合理地组织数据、高效率地实施数据运算，正是数据结构课程的目的。本章简要介绍有关数据结构的基本概念和算法分析方法。1.1 数据结构概述1.1.1 什么是数据结构
计算机数据运算的一般过程如图1.1所示。数据是信息的载体，能够被计算机识别、存储和加工处理，数据包括文字、表格、图像等。例如，某个班的全部学生记录、a~z的字母集合、1~1000的所有素数等都是数据。信息是数据的内涵，即数据所表达的意义，例如，通过统计后产生某课程的平均分85，这里85是数据，表示某课程平均分的信息。图1.1 数据运算的过程
数据的基本单位是数据元素（有时称为元素、结点或记录等），通常把数据元素作为一个整体进行处理。例如，一个班的学生数据包括张三、李四等数据元素。
数据对象是具有相同类型的数据元素的集合，因为所有数据元素类型相同时处理起来更加方便，所以在数据结构中除特别指定外数据通常都是数据对象。
有时一个数据元素可以由若干个数据项（也可称为字段、域、属性）组成。数据项是具有独立意义的不可分割的最小标识单位。例如，在1~100的整数数据中，10就是一个数据元素；又比如在一个学生表中，一个学生记录可称为一个数据元素，而这个元素中的某一字段（如姓名）就是一个数据项。【例1.1】组成数据的基本单位是________。A．数据项B．数据类型C．数据元素D．数据变量
解：数据是由数据元素组成的，数据元素是数据的基本单位。本题答案为C。
数据结构是相互之间存在一种或多种特定关系的数据元素的集合，如图1.2所示。这些数据元素不是孤立存在的，而是有着某种关系，这种关系构成了某种结构。在现实中，数据元素之间的关系多种多样，在“数据结构”课程中主要讨论数据元素之间的相邻关系。图1.2 数据结构由数据和结构组成
归纳起来，数据结构一般包括以下三个方面的内容。（1）数据元素之间的逻辑关系。所有元素的逻辑关系构成了数据逻辑结构。数据的逻辑结构是从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。因此，数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。（2）数据元素（有时简称为元素）及其逻辑关系在计算机存储器内的表示，构成了数据存储结构。数据存储结构是逻辑结构用计算机语言实现的（也称为映像），它是依赖于计算机语言的。一般只在高级语言的层次上讨论存储结构。（3）数据运算，即对数据施加的操作。数据运算的定义（指定运算的功能描述）是基于逻辑结构的，每种逻辑结构都有一组相应的运算。例如，最常用的运算有检索、插入、删除、更新、排序等；而数据运算的实现是基于存储结构的，通常是采用某种计算机语言实现的。
例如，一个学生成绩表Score如表1.1所示，它由多个学生成绩记录（即数据元素）组成，每个元素又包括多个数据项，其中，学号数据项是关键字，即学号唯一标识一个学生记录，现要求计算所有学生的平均分。表1.1 一个学生成绩表Score
在这个求解问题中，表1.1给出了数据的逻辑结构，其数据运算是求所有学生的平均分。为了实现这个功能，先要设计对应的存储结构，即把Score表存放到计算机内存中，然后设计出实现求平均分的算法。
这里包含的学生成绩表逻辑结构，对应的存储结构设计和求平均分运算的实现都是数据结构所涉及的内容。1.1.2 逻辑结构
数据元素之间的逻辑关系的整体称为数据的逻辑结构。现实中，数据元素的逻辑关系千变万化，而数据结构课程中讨论的逻辑关系主要是指数据元素之间的相邻关系，如果两个数据元素是相邻的，说明它们之间是有关系的，否则它们之间没有关系。实际上，这种相邻关系处理方法很容易推广到其他复杂关系的处理。
根据数据元素之间逻辑关系的不同特性，分为下列4类基本结构。（1）集合：包含的所有数据元素同属于一个集合（数据元素之间没有关系，集合是一种最松散的逻辑结构）。（2）线性结构：包含的数据元素之间存在一对一的关系。（3）树状结构：包含的数据元素之间存在一对多的关系。（4）图形结构：包含的数据元素之间存在多对多的关系。也称为网状结构。
数据的逻辑结构可以采用多种方式描述，二元组是一种既常用也十分通用的数据逻辑结构表示方式。二元组表示如下。 S=(D,R) D={d|1≤i≤n}i R={r|1≤j≤m}j
其中，D是数据元素的有限集合，即D是由有限个数据元素所构成的集合，R是D上的关系的有限集合，即R是由有限个关系r（1≤j≤jm）所构成的集合，而每个关系都是指D→D的关系。
每个关系r用序偶集合来表示，一个序偶表示两个元素之间的相j邻关系，用尖括号表示有向关系，如
设r是一个D到D的关系，r∈R，若元素d∈D，d′∈D，且
例如，表1.1数据的逻辑结构是怎么样的呢？从该表中可以看出，学号为201201的元素为开始元素（没有前驱元素），学号为201204的元素为终端元素（没有后继元素）。除此之外，所有元素都只有一个前驱元素和一个后继元素，如学号为201205的学生记录的唯一前驱元素为学号为201201的学生记录，唯一后继元素为学号为201206的学生记录。由此可知，这个表的逻辑结构为线性结构。
实际上，Score表本身就完整地描述了该数据的逻辑结构，也可以用如下二元组表示其逻辑结构（用学号表示相应的元素）。 Score=(D,R) D={201201,201202,201204,201205,201206} R={r} //这里只有一个逻辑关系，一些复杂的数据结构中可以有多个逻辑关系 r={<201201,201205>,<201205,201206>,<201206,201202>,<201202,201204>}
数据逻辑结构的呈现形式称为数据的逻辑表示，除二元组外，数据逻辑结构还可以用相应的关系图来表示，称为逻辑结构图。【例1.2】设数据的逻辑结构如下： B=(D,R)1 D={1,2,3,4,5,6,7,8,9} R={r} r={<1,2>,<1,3>,<3,4>,<3,5>,<4,6>,<4,7>,<5,8>,<7,9>}
试画出对应的逻辑结构图，并指出哪些是开始结点，哪些是终端结点，说明是何种数据结构。
解：B对应的逻辑结构图如图1.3所示。其中，1是开始结点，12、6、8、9是终端结点，除开始结点外，每个结点有唯一的前驱结点，除终端结点外，每个结点有一个或多个后继结点，所以它是一种树状结构。【例1.3】设数据的逻辑结构如下： B=(D,R)2 D={1,2,3,4,5,6} R={r} r={<1,2>,<2,4>,<1,3>,<3,4>,<3,5>,<3,6>,<5,6>}
试画出对应的逻辑结构图，说明是何种数据结构。
解：B对应的逻辑结构图如图1.4所示，其中每个结点都有零个2或多个前驱结点，每个结点都有零个或多个后继结点，所以它是一种图形结构。的逻辑结构图B图1.3 1的逻辑结构图B图1.4 21.1.3 存储结构
数据逻辑结构在计算机存储器中的表示称为数据的存储结构（或存储表示），也称为物理结构。通常情况下，同一种逻辑结构可以设计多种存储结构，在不同的存储结构中，实现同一种运算的算法可能不同。
逻辑结构、存储结构和运算三者之间的关系如图1.5所示。
把数据对象存储到计算机中时，通常要求既要存储各数据元素，又要存储数据元素之间的逻辑关系。在实际应用中，数据的存储方法是灵活多样的，可根据问题规模（通常是指元素个数的多少）和运算种类等因素适当选择。下面简要介绍主要的几种存储结构。图1.5 逻辑结构、存储结构和运算之间的关系
1．顺序存储结构
顺序存储结构是采用一组连续的存储单元存放所有的数据元素，而且逻辑上相邻的元素的存储单元也相邻。也就是说，元素之间的逻辑关系由存储单元地址间的关系隐含表示，即顺序存储结构将数据的逻辑结构直接映射到存储结构。
对于前面的逻辑结构Score，假设每个元素占用30B，且从100号单元开始由低地址向高地址方向存储，对应的顺序存储结构如图1.6所示。图1.6 Score对应的顺序存储结构
顺序存储结构的主要优点是节省存储空间。因为分配给数据的存储单元全用于存放元素值，元素之间逻辑关系的表示没有占用额外的存储空间。用这种方法来存储线性结构的数据元素时，可实现对各数据元素的随机存取（所谓随机存取是指给定某元素的逻辑序号，能在常量时间内查找到对应的元素值）。
这是因为线性结构中每个数据元素对应一个序号（开始元素的序号为1，它的后继元素的序号为2……），序号为i的元素a，其存储地i址如下：LOC（a）=p+（i—1）×ki其中，k是每个元素所占的单元数，p是第一个元素所占单元的首地址。
顺序存储结构的主要缺点是不便于修改，在对元素进行插入、删除运算时，可能要移动一系列的元素。
2．链式存储结构
顺序存储结构要求所有的元素在内存中相邻存放，因而需占用一片连续的存储空间；而链式存储结构不是这样，每个结点单独存储，无须占用一整块存储空间，但为了表示结点之间的关系，给每个结点附加指针字段，用于存放相邻结点的存储地址。
对于前面的逻辑结构Score，在设计其链式存储结构时，每个结点存放一个学生成绩记录，每个结点附加一个“下一个结点地址”即后继指针域，用于存放后继结点的首地址，则可得到如图1.7所示的Score的链式存储表示，head作为第一个结点的地址来标识整个链式存储结构。从图中可以看出，每个结点由两部分组成，一部分用于存放结点的数据，另一部分用于存放后继结点的首地址。图1.7 Score对应的链式存储结构
为了更清楚地反映链式存储结构，可采用更直观的图示来表示，如Score的链式存储结构可用如图1.8所示的方式表示。如要查找某学号的结点，需从head所指结点开始比较，在没有找到时依次沿后继指针域继续找下去。图1.8 Score链式存储结构示意图
链式存储结构的主要优点是便于修改，在进行插入、删除运算时，仅需修改结点的指针域，不必移动结点。
与顺序存储结构相比，链式存储结构的主要缺点是存储空间的利用率较低，因为分配给数据元素的存储单元中有一部分被用来存放结点之间的逻辑关系了。另外，由于逻辑上相邻的结点在存储器中不一定相邻，因此，在用这种方法存储的线性结构中不能对结点进行随机存取。
3．索引存储结构
索引存储结构是在存储数据（称为主数据表）的同时，还建立附加的索引表。索引表中的每一项称为索引项，索引项的一般形式如下： （关键字，对应地址）
在索引表中，所有关键字有序排列（如递增），每个关键字的对应地址为该关键字的记录在数据表中的存储地址。
如图1.9所示的是Score对应的一种索引存储结构。在进行关键字（如学号）查找时，先在索引表中快速查找（因为索引表中按关键字有序排列，可以采用二分查找）到相应的关键字，然后通过对应地址在数据表中找到该记录的数据。
索引存储结构的优点是查找效率高，其缺点是需要建立索引表，从而增加了时间和空间开销。图1.9 Score对应的索引存储结构
4．哈希（散列）存储结构
哈希存储结构根据元素的关键字来确定其存储地址。具体做法是：以元素的关键字为自变量，通过某个哈希函数H（key）（或散列函数）计算出对应的函数值，再把该函数值当作该元素的存储地址。
对于前面的逻辑结构Score，假设哈希表长度m=6（存储单元的地址为0~5），记录个数n=5，以学号作为自变量，选用哈希函数如下：h（学号）=学号—201201
对于每个学生记录，计算的存储地址如下。
于是得到如图1.10所示的哈希存储结构（其中2地址单元空闲）。如果要查找学号为id的学生记录，只需要求出h（id），以它为地址在该哈希表中直接找到该学号的学生记录。图1.10 Score对应的哈希存储结构
哈希存储结构的优点是查找速度快，只要给出待查找结点的关键字，就有可能立即计算出对应记录的存储地址。
与前三种存储方法不同的是，哈希存储方法只存储数据元素本身，不存储数据元素之间的逻辑关系。哈希存储结构一般只用于要求对数据能够进行快速查找、插入的场合。采用哈希存储的关键是要选择一个好的哈希函数和处理“冲突”的办法。1.1.4 数据运算
数据运算就是施加于数据的操作。数据运算包括运算定义和运算实现两部分，前者描述运算的功能，是抽象的，后者是在存储结构上设计对应运算的实现算法，是具体的。这种将运算定义和运算实现相互分离的做法即软件工程的思想，更加便于软件开发。
在数据结构中，运算实现与数据存储结构密切相关，选用好的存储结构可以提高运算实现的效率。1.1.5 数据结构、数据类型和抽象数据类型
1．数据结构
数据结构是指带结构的数据元素的集合。一个数据结构包含数据逻辑结构、存储结构和数据运算三个方面。
2．数据类型
数据类型是高级程序设计语言中的一个基本概念，它和数据结构的概念密切相关。一方面，在程序设计语言中，每一个数据都属于某种数据类型。数据类型显式或隐含地规定了数据的取值范围、存储方式以及允许进行的运算。例如，在32位系统中，C语言的short int（短整型）数据类型隐含取值范围为—32 768~32 767，其运算有+、—、∗、/、%等。因此可以认为，数据类型是在程序设计语言中已经实现了的数据结构。另一方面，在程序设计过程中，当需要引入某种新的数据结构时，必须借助编程语言所提供的数据类型来描述数据的存储结构。
下面总结C/C++语言中常用的数据类型。
1）C/C++语言的基本数据类型
C/C++语言中的基本数据类型有int型、float型；double型和char型。int型可以有三个修饰符：short（短整数）、long（长整数）和unsigned（无符号整数）。
数据类型用于定义变量，如有定义语句：int n=10；在执行该语句时系统自动为变量n分配一个固定长度（如4B）的内存空间，如图1.11所示，程序员通过变量名n对这个内存空间进行存取操作（内存分成许多单元，每个单元都有一个地址，可以通过地址来对指定的单元进行操作，但这样做对于程序员来说十分麻烦，而通过变量名来操作内存单元非常方便），当超出作用范围时系统自动释放其内存空间，所以称之为自动变量。
2）C/C++语言的指针类型
C/C++语言允许直接对存放变量的地址进行操作。例如有以下定义： int i, ∗ p;其中，i是整型变量，p是指针变量（它用于存放某个整型变量的地址）。表达式&i表示变量i的地址，将p指向整型变量i的运算为：p=&i。
对于指针变量p，表达式∗p是取p所指变量的值，例如： int i=2, ∗ p=&i printf(＂%d\n＂,∗ p);
上述语句执行后，其内存结构如图1.12所示，通过表达式∗p输出变量i的值即2。n分配存储空间图1.11 为变量p指向整型变量i图1.12 指针变量
可以使用malloc（）函数为一个指针变量分配一片连续的空间（称为动态空间分配）。例如：
上述代码先定义字符指针变量p（此时它没有指向有效的字符数据，即p中的地址值没有意义），使用malloc（）函数为其分配长度为10个字符的空间，将该空间的首地址赋给p（尽管程序员不知道这个地址是多少，但p的值已经有意义了），再将字符串＂China＂放到这个空间中，如图1.13所示。p指向的是首字符'C'，所以第一个printf语句输出的∗p即字符'C'，而第二个printf语句输出的是整个字符串即＂China＂。
p变量是自动变量，当超出范围时，系统会自动释放它的空间，但p所指向的空间（用malloc函数分配的空间）是不能被系统自动释放的，所以必须显式用free（p）语句来释放p所指向的空间，这称为销毁，即垃圾回收。如果不做销毁操作，p所指向的内存空间在程序执行完毕仍被占用，这样可能很快造成内存消耗完，称为内存泄漏。所以本书后几章中介绍的每种数据结构都包含创建和销毁基本运算。p分配指向的空间图1.13 为指针变量
3）C/C++语言的数组类型
数组是同一数据类型的一组数据的有限序列。数组分为一维数组和多维数组。数组名标识一个数组，下标指示一个数组元素在该数组中的位置。
数组下标的最小值称为下界，在C语言中总是为0。数组下标的最大值称为上界，在C语言中数组上界为数组长度减1。例如，inta[10]语句定义了包含10个整数的数组a，其数组元素是a[0]~a[9]。
4）C/C++语言中的结构体类型
结构体是由一组称为结构体成员的数据项组成的，每个结构体成员都有自己的标识符，也称为数据成员域。例如，以下声明了一个teacher结构体类型：
结构体类型是用于定义结构体变量的，当定义一个结构体类型的变量时，系统按照结构体类型声明为对应的变量分配存储空间。例如，定义一个结构体变量t： struct teacher t;
t变量在内存中的存放方式如图1.14所示，引用no成员的方式是t.no，引用name成员的方式是t. name，引用age成员的方式是t.age，所有成员相邻存放，t变量所分配的内存空间大小为所有成员占用的内存空间之和。
可以使用结构体类型teacher定义其他变量，有以下代码：图1.14 结构体变量在内存中的存放方式
其执行结果如下。 1，陈华，34 5，王强，48
5）C/C++语言中的共用体类型
共用体用于把不同的数据成员组织为一个整体，它们在内存中共享一段存储单元，但不同成员以不同的方式被解释。例如，声明一个共用体类型tag如下：
共用体类型是用于定义共用体变量的，当定义一个共用体类型的变量时，系统按照共用体类型声明为对应的变量分配存储空间。例如，定义一个共用体变量u： union tag u;图1.15 共用体变量在内存中的存放方式
u变量在内存中的存放方式如图1.15所示，引用n成员的方式是u.n，引用ch成员的ch[0]元素的方式是u.ch[0]，所有成员共享相同的内存空间，u变量所分配的内存空间大小为所有成员占用的成员空间的最大值。
可以使用共用体类型tag定义其他变量，有以下代码：
通过赋值后，在共用体变量u的成员n的两个字节中，高位为65（0x41），低位为66 （0x42），分别对应u.ch[1]和u.ch[0]成员，所以printf输出为A和B两个字符（字符'A'的ASCII为十六进制数41，字符'B'的ASCII为十六进制数42）。
6）C语言中的自定义类型
C/C++语言中允许使用typedef关键字为一个数据类型指定一个别名，例如： typedef char ElemType;
该语句将char类型与ElemType等同起来。这样做有两个好处，一是方便程序调试，例如，将上述语句改为typedef int ElemType，则程序中所有ElemType都改为int类型了；二是可以简化代码，例如：
这样，StudType等同于学生结构体类型，可以使用该类型名定义变量： StudType s1,s2;等同于： struct student s1,s2;
3．抽象数据类型
在数据结构中，抽象数据类型（Abstract Data Type，ADT）是指一个数学模型以及定义在此数学模型上的一组操作。抽象数据类型需要通过固有数据类型（高级编程语言中已实现的数据类型）来实现。对一个抽象数据类型进行定义时，必须给出抽象数据类型名称和包含的运算名称及其功能描述。一旦定义了一个抽象数据类型并具体实现，程序设计中就可以像使用基本数据类型那样，十分方便地使用该抽象数据类型。
从数据结构的角度看，一个求解问题可以通过抽象数据类型来描述，也就是说，抽象数据类型对一个求解问题从逻辑上进行了准确的定义，所以抽象数据类型由数据逻辑结构和运算定义两部分组成。从中看出，抽象数据类型是面向用户的，而抽象数据类型的实现是面向程序员的。【例1.4】定义单个集合的抽象数据类型ASet，其中所有元素为正整数，包含创建一个集合、输出一个集合和判断一个元素是否为集合中元素的基本运算。
在此基础上再定义两个集合运算的抽象数据类型BSet，包含集合的并集、差集和交集运算。
解：抽象数据类型ASet的定义如下：
抽象数据类型BSet的定义如下：
通过上述两个抽象数据类型的定义，就将求解问题描述清楚了，下一步就是用C/C++等语言具体实现其功能。1.2 算法和算法分析1.2.1 算法及其描述
1．算法的特性
一个运算实现是通过算法来表述的，算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每条指令表示一个或多个操作。算法设计应满足以下几条目标。（1）正确性：要求算法能够正确地执行预先规定的功能和性能要求。这是最重要也是最基本的标准。（2）可使用性：要求算法能够很方便地使用。这个特性也叫作用户友好性。（3）可读性：算法应该易于人的理解，也就是可读性好。为了达到这个要求，算法的逻辑必须是清晰的、简单的和结构化的。（4）健壮性：要求算法具有很好的容错性，即提供异常处理，能够对不合理的数据进行检查。不经常出现异常中断或死机现象。（5）高效率与低存储量需求：通常算法的效率主要指算法的执行时间。对于同一个问题如果有多种算法可以求解，执行时间短的算法效率高。算法存储量指的是算法执行过程中所需的最大存储空间。效率和低存储量这两者都与问题的规模有关。【例1.5】即使输入非法数据，算法也能适当地做出反应或进行处理，不会产生预料不到的运行结果，这种算法好坏的评价因素称为________。A．正确性B．易读性C．健壮性D．时空性
解：一个算法对于非法数据输入不会产生预料不到的运行结果，称为算法的健壮性。本题答案为C。
算法具有以下5个重要特性。（1）有限性（或有穷性）：一个算法必须总是（对任何合法的输入值）在执行有限步之后结束，且每一步都可在有限时间内完成。（2）确定性：算法中每一条指令必须有确切的含义，不会产生二义性。（3）可行性：算法中每一条运算都必须是足够基本的，就是说它们原则上都能精确地执行，甚至人们仅用笔和纸做有限次运算就能完成。（4）输入性：一个算法有零个或多个输入。大多数算法中输入参数是必要的，但对于较简单的算法，如计算1+2的值，不需要任何输入参数，因此算法的输入可以是零个。（5）输出性：一个算法有一个或多个输出。算法用于某种数据处理，如果没有输出，这样的算法是没有意义的，这些输出是同输入有着某些特定关系的量。
说明：算法和程序是有区别的，程序是指使用某种计算机语言对一个算法的具体实现，即具体要怎么做，而算法侧重于对解决问题的方法描述，即要做什么。算法必须满足有限性，而程序不一定满足有限性，如Windows操作系统在用户没有退出、硬件不出现故障以及不断电的条件下理论上可以无限时运行，所以严格讲算法和程序是两个不同的概念。当然算法也可以直接用计算机程序来描述，这样算法和程序就是一回事了，本书就采用这种方式。【例1.6】有下列两段描述：
这两段描述均不能满足算法的特性，试问它们违反了算法的哪些特性？
解：①这是一个死循环，违反了算法的有限性特性。②出现除零错误，违反了算法的可行性特性。
2．算法的描述
描述算法的方式很多，有的采用类Pascal语言，有的采用自然语言伪码。本书采用C/C++语言来描述算法的实现过程，通常用C/C++函数来描述算法。
以设计求1+2+…+n值的算法为例说明C/C++语言描述算法的一般形式，该算法如图1.16所示。图1.16 算法描述的一般形式
通常用函数的返回值表示算法能否正确执行，有时当算法只有一个返回值或者返回值可以区分算法是否正确执行时，用函数返回值来表示算法的执行结果，另外还可以带有形参表示算法的输入输出。任何算法（用函数描述）都是被调用的（在C/C++语言中除main函数外任何一个函数都会被其他函数调用，如何一个函数不被调用，这样的函数是没有意义的）。在C语言中调用函数时只有从实参到形参的单向值传递，执行函数时若改变了形参而对应的实参不会同步改变。例如，设计以下主函数调用图1.16中的Sum1函数。 void main() { int a=10,b=0; if(Sum1(a,b))printf(＂%d\n＂,b); else printf(＂参数错误\n＂); }
执行时发现输出结果为0。这是因为b对应的形参为s（在内存中b和s存放在不同的位置），Sum1函数执行后s=55，但s并没有回传给b，b的值仍然为0。在C语言中可以用传指针方式来实现形参的回
试读结束[说明：试读内容隐藏了图片]