作者：圣才电子书
出版社：圣才电子书
格式: AZW3, DOCX, EPUB, MOBI, PDF, TXT
李春葆《数据结构教程》（C＋＋语言描述）笔记和课后习题详解试读：
第1章 绪 论
1.1 复习笔记
一、数据结构
1．概述（1）计算机对具体问题的处理
在用计算机解决一个具体的问题时，大致需要经过以下几个步骤：
①分析问题，确定数据模型。
②设计相应的算法。
③编写程序，运行并调试程序，直至得到正确的结果。（2）数据的含义
①数据是描述客观事物的数、字符以及所有能输入到计算机中并被计算机程序处理的符号的集合。从计算机的角度看，数据是所有能被输入到计算机中，且能被计算机处理的符号的集合。它是计算机操作的对象的总称，也是计算机所处理信息的某种特定的符号表示形式。
②数据元素是组成数据的、有一定意义的基本单位，在计算机中通常作为整体处理，有些情况下数据元素也称为元素、结点、记录等。一个数据元素可以由若干个数据项组成。数据项是具有独立含义的数据的最小单位，也称为域。
③数据对象是性质相同的有限个数据元素的集合，它是数据的一个子集。
默认情况下，数据结构中的数据指的都是数据对象。（3）数据结构的定义
数据结构是指所有数据元素以及数据元素之间的关系，可以看作是相互之间存在特定关系的数据元素的集合，因此，可时把数据结构看成是带结构的数据元素的集合。数据结构包括以下几个方面：
①数据元素之间的逻辑关系，即数据的逻辑结构，它是数据结构在用户面前呈现的形式。
数据的逻辑结构是从逻辑关系（主要指数据元素的相邻关系）上描述数据的，它与数据的存储无关，是独立于计算机的。因此，数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。
②数据元素及其关系在计算机存储器中的存储方式，即数据的存储结构，也称为数据的物理结构。
数据的存储结构是逻辑结构用计算机语言的实现或在计算机中的表示（也称为映像），也是指逻辑结构在计算机中的存储方式，它是依赖于计算机语言的。一般情况下，只在高级语言（如C、C++、Java语言）的层次上讨论存储结构。
③施加在该数据上的操作，即数据的运算。
数据的运算是定义在数据的逻辑结构之上的，每种逻辑结构都有一组相应的运算。最常用的运算有检索、插入、删除、更新、排序等。数据的运算最终需要在对应的存储结构上用算法实现。
因此，数据结构是一门讨论“描述现实世界实体的数学模型（通常为非数值计算）及其之上的运算在计算机中如何表示和实现”的学科。
2．数据的逻辑结构
讨论数据结构的目的是为了用计算机求解问题，分析并弄清数据的逻辑结构是求解问题的基础。
数据的逻辑结构是用户根据需要建立起来的数据组织形式，它反映数据元素之间的逻辑关系而不是物理关系，是独立于计算机的。
数据的逻辑结构有4种，包括线性结构、树形结构、图形结构以及集合中的数据元素没有任何相邻关系。
通常采用二元组表示数据的逻辑结构。一个二元组如下：B=（D，R）其中，B是一种数据结构，D是数据元素的集合，在D上数据元素之间可能存在多种关系，R是所有关系的集合。
3．数据的存储结构（1）存储实现的基本目标
建立数据的机内表示包括数据元素的存储和数据元素之间关系的存储。数据的存储结构应正确地反映数据元素之间的逻辑关系，即在设计某种逻辑结构对应的存储结构时，不仅要存储所有的数据元素，还要存储数据元素之间的关系。所以，将数据的存储结构称为逻辑结构的映像，将设计数据的存储结构称为从逻辑结构到存储器的映射，如图1-1所示。图1-1 存储结构是逻辑结构在内存中的映像
归纳起来，数据的逻辑结构是面向问题的，而存储结构是面向计算机的，其基本目标是将数据及其逻辑关系存储到计算机的内存中。（2）4种常用的存储结构类型
①顺序存储结构
a．定义
顺序存储结构是把逻辑上相邻的结点存储在物理位置上相邻的存储单元中，结点之间的逻辑关系由存储单元的邻接关系来体现，由此得到的存储表示称为顺序存储结构。通常，顺序存储结构是借助计算机程序设计语言（如C／C++、Java语言等）的数组来描述的。
b．优点
顺序存储方法的优点是节省存储空间，因为分配给数据的存储单元全部用于存放结点的数据，结点之间的逻辑关系没有占用额外的存储空间。采用这种方法，可实现对结点的随机存取，即每个结点对应一个序号，由该序号可直接计算出结点的存储地址。
c．缺点
顺序存储方法的主要缺点是不便于修改，对结点进行插入、删除运算时，可能要移动一系列的结点。
②链式存储结构
a．定义
链式存储结构不要求逻辑上相邻的结点在物理位置上也相邻，结点间的逻辑关系用附加的指针域来表示，由此得到的存储表示称为链式存储结构。通常，链式存储结构要借助计算机程序设计语言（如C／C++）的指针来描述。
b．优点
链式存储方法的主要优点是便于修改，在进行插入、删除运算时，仅需修改相应结点的指针域即可，不必移动结点。
c．缺点
与顺序存储方法相比，链式存储方法的主要缺点是存储空间的利用率较低，因为分配给数据的存储单元有一部分被用来存储结点之间的逻辑关系。另外，由于逻辑上相邻的结点在存储空间中不一定相邻，所以不能对结点进行随机存取。
③索引存储结构
a．定义
索引存储结构通常在存储结点信息的同时，还建立附加的索引表。索引表中的每一项称为索引项，索引项的一般形式是（关键字，地址），关键字唯一标识一个结点，索引表按关键字有序排序，地址作为指向结点的指针。这种带有索引表的存储结构可以大大提高数据查找的速度。
b．优点
当线性结构采用索引存储方法后，可以对结点进行随机访问。在进行插入、删除运算时，只需移动存储在索引表中对应结点的存储地址即可，不必移动存放在结点表中结点的数据，所以仍保持较高的数据修改运算效率。
c．缺点
索引存储方法的缺点是增加了索引表，降低了存储空间的利用率。
④哈希存储结构
a．定义
哈希（或散列）存储结构的基本思想是根据结点的关键字通过哈希（或散列）函数直接计算出一个值，并将这个值作为该结点的存储地址。
b．优点
哈希存储方法的优点是查找速度快，只要给出待查结点的关键字，就可以立即计算出该结点的存储地址。与前3种存储方法不同的是，哈希存储方法只存储结点的数据，不存储结点之间的逻辑关系。
c．缺点
哈希存储方法一般只适合要求对数据能够进行快速查找和插入的场合。
上述4种基本存储结构，既可以单独使用，也可以组合使用。同一种逻辑结构采用不同的存储方法，可以得到不同的存储结构。
4．数据的运算
将数据存放在计算机中的目的是为了实现一种或多种运算。运算包括功能描述（或运算功能）和功能实现（或运算实现），前者是基于逻辑结构的，是用户定义的，是抽象的；后者是基于存储结构的，是程序员用计算机语言或伪码表示的，是详细的过程，其核心是设计实现某一运算功能的处理步骤，即算法设计。
归纳起来，对于一种数据结构，其逻辑结构是唯一的（尽管逻辑结构的表示形式有多种），但它可能对应多种存储结构，并且在不同的存储结构中，同一运算的实现过程可能不同。
5．数据结构和数据类型（1）数据结构和数据类型的差别
数据类型是一组性质相同的值的集合和定义在此集合上的一组操作的总称。数据结构是指计算机处理的数据元素的组织形式和相互关系，而数据类型是某种程序设计语言中已实现的数据结构。在程序设计语言提供的数据类型的支持下，可以根据从问题中抽象出来的各种数据模型，逐步构造出描述这些数据模型的各种新的数据结构。（2）抽象数据类型
①抽象数据类型的概念
抽象数据类型（Abstract Data Type，ADT）指用户进行软件系统设计时从问题的数学模型中抽象出来的逻辑数据结构和逻辑数据结构上的运算，不考虑计算机的具体存储结构和运算的具体实现算法。
抽象数据类型中的数据对象和数据运算的声明与数据对象的表示和数据运算的实现相互分离，又称抽象模型。
②“抽象”的含义“抽象”意味着应该从与实现方法无关的角度研究数据结构，只关心数据结构做什么，而不是如何实现。在程序中使用数据结构之前，必须提供实现方法，还要关心运算的执行效率。
③抽象数据类型的定义
一个具体问题的抽象数据类型的定义通常采用简洁、严谨的文字描述，一般包括数据对象（即数据元素的集合）、数据关系和基本运算3个方面的内容。抽象数据类型可用（D，S， P）三元组表示，其中，D是数据对象，S是D上的关系集，P是D中数据运算的基本运算集。其基本格式如下：
ADT抽象数据类型名
{
数据对象：数据对象的声明
数据关系：数据关系的声明
基本运算：基本运算的声明
}ADT抽象数据类型名
基本运算的声明格式如下：
基本运算名（参数表）：运算功能描述（3）数据抽象和数据封装
抽象数据类型有两个重要特征，即数据抽象和数据封装。
数据抽象，是指用ADT描述程序处理的实体时，强调的是其本质的特征、所能完成的功能以及它和外部用户的接口（即外界使用它的方法）；
数据封装，是指将实体的外部特性和其内部实现细节分离，并且对外部用户隐藏其内部实现细节。抽象数据类型需要通过固有数据类型（高级编程语言中已实现的数据类型，如C++中的类）来实现。
二、算法及其描述
1．概述（1）算法的概念
数据元素之间的关系有逻辑关系和物理关系，对应的运算有逻辑结构上的运算（抽象运算）和具体存储结构上的运算（运算实现）。确切地说，算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示计算机的一个或多个操作。（2）算法的特性
算法具有以下5个重要的特性（如图1-2所示）。图1-2 算法的概念
①有穷性：指算法在执行有限的步骤之后自动结束，而不会出现无限循环，并且每一个步骤在可接受的时间内完成。
②确定性：对于每种情况下执行的操作在算法中都有确定的含义，不会出现二义性，并且在任何条件下，算法都只有一条执行路径。
③可行性：算法的每条指令都是基本可执行的，也指借助纸、笔或计算机可以完成。
④输入性：算法有零个或多个输入。大多数算法中输入参数是必要的，但对于较简单的算法，如计算1+2的值，不需要任何输入参数，因此算法的输入可以是零个。
⑤输出性：算法至少有一个或多个输出。算法用于某种数据处理，如果没有输出，这样的算法是没有意义的，这些输出是和输入有着某些特定关系的量。（3）算法和程序的区别
①程序是指使用某种计算机语言对一个算法的具体实现，即具体要怎么做；算法侧重于对解决问题的方法描述，即要做什么。
②算法必须满足有穷性，而程序不一定满足有穷性，如Windows操作系统在用户没有退出、硬件不出现故障以及不断电的条件下理论上可以无限时运行。算法的有穷性意味着不是所有的计算机程序都是算法，所以严格上讲算法和程序是两个不同的概念。
2．算法描述（1）C++的数据类型
①C++语言中的基本数据类型
a．基本数据类型
int型、float型、double型和char型。int型可以有3个修饰符，即short（短整数）、long（长整数）和unsigned（无符号整数）。
b．数据类型的作用
数据类型用于定义变量，如有定义语句“int n=10；”，在执行该语句时系统自动为变量n分配一个固定长度（如两个字节）的内存空间，如图1-3所示。程序员通过变量名n对这个内存空间进行存取操作。图1-3 为变量n分配存储空间
②C++语言中的指针类型
a. 地址操作
C++语言允许直接对存放变量的地址进行操作。如有以下定义：int i，* p；
其中，i是整型变量，p是指针变量（它用于存放某个整型变量的地址）。表达式＆i表示变量i的地址，将p指向整型变量i的运算为p=＆i。
对于指针变量p，表达式*p是取p所指变量的值，如：
上述语句执行后，其内存结构如图1-4所示，结果是通过*p输出变量i的值，即2。图1-4 指针变量p指向整型变量
b．内存动态管理
C++提供了new和delete运算符用于实现内存动态管理，其中，new用于为一个指针变量分配一片连续的空间，delete用于释放通过new分配的空间。如：
上述代码先定义字符指针变量p，使用new为其分配长度为10个字符的空间，并将该空间的首地址赋给p，再将字符串“China”放到这个空间中，如图1-5所示。所以，第1个printf语句输出的是首地址的字符，即“C”，第2个printf语句输出的是整个字符串，即“China”。图1-5 为指针变量p分配指向的空间
p变量是自动变量，当超出范围时，系统会自动释放它的空间，用delete[]p语句来释放p所指向的空间，这称之为销毁，即垃圾回收。如果不做销毁，p所分配的内存空间在程序执行完毕后仍被占用，这样可能很快地消耗完内存，称之为内存泄露。
说明：如果用new分配单个数据空间，可用delete释放；如果用new分配一个含有多个元素的数组空间，可用delete[]释放，其中，方括号的作用是通知编译器要释放数组中的所有元素（若是对象数组，delete[]根据由new[]创建的对象数调用相同数目的析构函数。否则delete只释放该指针所指的单个数组元素，其后的数组元素没有被释放）。
③C++语言中的数组类型
a．定义
数组是同一类型的一组有序数据的集合，有一维数组和多维数组两种类型,数组名称识一个数组，下标指示一个数组元素在该数组中的位置。
数组下标的最小值称为下界，在C语言中它总是为0。数组下标的最大值称为上界，在 C语言中数组上界为数组定义值减1。
b．数组初始化
在定义数组时可以同时进行初始化，初始化值的个数可以小于或等于数组定义的元素个数，但不可以多于元素个数（否则会导致语法错误），对于不足部分的数组元素，系统自动以0值填充。如果在初始化数组的语句中忽略了数组大小，则数组元素个数是指初始化值的个数。下面一维数组的初始化形式是合法的：
和一维数组一样，二维数组也能在定义时初始化。下面定义几个二维数组并进行初始化：
④C++语言中的结构体类型
结构体是由一组被称为结构体成员（或数据域）的数据项组成的，每个结构体成员都有自己的标识符。例如定义一个teacher结构体类型：
⑤C++语言中的共用体类型
共用体是把不同的成员组织为一个整体，它们在内存中共享一段存储单元，但不同成员以不同的方式被解释。例如，定义一个共用体类型tag：
定义一个共用体变量u：
union tag u；
u变量在内存中的存放方式如图1-6所示，引用n成员的方式是u．n，引用ch成员的ch[0]元素的方式是u.ch[0]，所有成员共享相同的内存空间，u变量所分配的内存空间大小为所有成员占用的成员空间的最大值。图1-6 共用体变量在内存中的存放方式
用户可以使用共用体类型tag定义其他变量，如：
通过赋值后，在共用体变量u的成员n的两个字节中，高位为64，低位为65，分别对应u.ch[1]和u.ch[0]成员，所以printf输出A和B两个字符（字符'A'的ASCII码为十六进制数41，字符'B'的ASCII码为十六进制数42）。（2）C++中的类设计
①类的定义格式和类对象的声明
a．类的定义格式
类的定义包括声明部分和实现部分，声明部分用来说明该类所包含数据成员的成员函数，实现部分是成员函数的具体实现。类的一般定义格式如下：
注意：在类声明中最后面的右大括号后面的分号“；”是语法的一部分，因此，漏写该分号会产生一个语法错误。
其中，“class”是定义类的关键字，“类名’’是一个标识符，用于唯一标识一个类。
b．类的成员
类的成员包含数据成员和成员函数两种，C++提供了3种访问成员的权限：
第一，public（公有成员）：该类的对外界面，允许外界通过该类对象访问；
第二，private（私有成员）：该类的私有部分，只有该类的成员函数可以访问；
第三，protected（保护成员）：具有私有性，但允许该派生类的成员函数访问。
c．类的声明
第一，在默认情况下，一个类中所有的成员都是私有的。
第二，一旦给出了成员访问限定符（如public：），它后面的成员都具有这个成员访问权限（如后面的成员均为公有的），直到出现另一个成员访问限定符或类声明结束为止。
第三，一旦声明了一个类，就可以用它作为数据类型来定义类对象（简称为对象）。在C++中，类对象又称类变量或者类实例。定义类对象的格式如下：类名 对象名表；
d．类的成员函数
类的成员函数用于实现某种操作。通常，把类的声明和类的实现分开，也可以在类声明体中直接实现成员函数，这样做的成员函数属内联（inline）函数。C++编译器在遇到调用内联函数的地方会用函数体中的代码来替换函数的调用，其优点是节省函数调用带来的参数传递、运行栈的进栈与出栈等开销，从而提高运行速度，缺点是增加了代码长度。通常，采用成员函数来实现算法。在定义成员函数时需要指定访问权限、返回值、函数名字以及函数的形参。函数的返回值表示算法能否正确执行，当算法只有一个返回值或者返回值可以区分算法是否正确执行时，用函数返回来表示算法的执行结果，还可以带有形参表示算法的输入／输出。成员函数的形参放在括号中，当有多个形参时需要用逗号分隔，空括号表示函数没有任何形参。
如图1-7所示为在某个类中定义了一个求n！的成员函数fun，当n>0时求出正确的结果并返回true，否则返回false。图1-7 成员函数fun的定义
成员函数可以向调用方返回某一个特定的值。如果函数的返回类型不是void，则该函数可以用return语句来返回值，return还可以用来停止函数的执行。
②构造函数和析构函数
在C++类中有两种特殊的成员函数，即构造函数和析构函数。
a．构造函数
类的构造函数用来初始化类的数据成员，当类对象创建时，构造函数就会自动地执行。
构造函数的特点是，构造函数的名字与类的名字相同；构造函数一定具有public访问权限；构造函数尽管是一个函数，但没有任何类型，即它既不属于返回值函数也不属于void函数；类可以有多个构造函数，此时它们的参数各不相同。
b．析构函数
对象是类的实例，即类的变量，当生存期结束时，系统会自动调用析构函数来做一些清理工作，与构造函数的功能正好相反。
析构函数的特点是，析构函数的名字是“～”加上类的名字（中间没有空格）；析构函数在类对象销毁时自动执行；析构函数一定具有public访问权限；一个类只能有一个析构函数，而且析构函数没有参数；和构造函数一样，析构函数也没有任何类型，即它既不属于返回值函数也不属于void函数，它们不能像其他函数那样被调用。
在数据结构中，通常用构造函数来实现数据结构的初始化操作。析构函数用于实现数据结构的销毁操作。
③成员函数的参数传递
成员函数中的参数是保证不同成员函数间互动的重要“桥梁”，方便用户对数据进行操作。在C++中，成员函数的参数主要有值参数和引用参数两种类型。
a．值参数值参数不含任何修饰符，当利用值参向成员函数传递参数时，编译系统给实参的值做一份副本，并且将此副本传递给该成员函数，被调用的成员函数不会修改内存中实参的值，所以使用值参可以保证实际值的安全性，此时只是实参到形参的单向值传递。
b．引用参数
在形参的参数名前加上“＆”符声明的参数属于引用参数。引用参数本身并不创建新的存储空间，而是和实参一起共享相同的存储空间，所以对形参的修改会影响原来实参的值，可以理解为此时实参和形参是双向值传递。
c．说明
由于在函数调用时引用形参不另外分配存储空间，而是和实参共享存储空间，所以当函数间传递较大的数据时，在没有副作用的情况下尽可能采用引用参数，以节省存储空间。（3）C++中的友元设计
①友元的作用
友元提供了不同类或对象的成员函数之间、类的成员函数与一般函数之间进行数据共享的机制。即通过友元，一个普通函数或者类的成员函数可以访问到封装于某一类中的数据。
②友元函数
a．定义
如果友元是一般函数或类的成员函数，则称之为友元函数。
b．声明
第一，声明格式
为了使一个函数成为类的友元函数，必须在类中进行声明。声明友元函数的方式是在类中用关键词friend声明该函数，其一般格式如下：
friend函数类型 友元函数名（参数表）；
第二，声明位置
友元函数的声明位置可在类的任何地方，既可在public区，也可在protected区，意义完全一样。友元函数的定义既可以放在类的外部，也可以放在类的内部，通常与类的成员函数定义放在一起。
如以下程序的MyClass类中声明了一个友元函数add，在该函数中可以直接访问MyClass类对象的私有数据成员n：
第三，特点
友元函数可以是一个普通的函数，也可以是其他类的成员函数，但它一定不是本类的成员函数；
通常，成员函数只可以访问一个类的私有和保护成员，但友元函数可以访问多个类的私有和保护成员；
友元函数可以绕过成员函数，直接访问类的私有和保护成员，这样就避免了调用成员函数相关的开销；
如果没有友元功能，一个函数要想访问某个类的私有和保护成员，只能将这个成员设置为公共的，这样一来，用户就可以访问该类中的所有成员，从而破坏了信息的隐藏性；
由于友元函数不是本类的成员函数，其定义和调用方式与普通函数一样，在调用友元函数时不需要使用“．”运算符，在定义时也不需要使用类前缀；
友元函数并不是类的成员函数，它不带有this指针，所以必须用对象名或对象的引用作为友元函数的形参，并在函数体中使用运算符“．”来访问对象的成员；
由于友元函数可以使用类中的所有成员，破坏了数据的安全性，所以用户使用友元函数时必须谨慎，不要通过友元函数对数据成员进行危险的操作。
③友元类
如果友元是一个类，则称之为友元类，此时友元类的所有成员函数都成为友元函数。和友元函数一样，类也可以声明为另一个类的友元，这时它成为友元类。若B类为A类的友元类，则B类的所有成员函数都是A类的友元函数，都可以访问A类的私有和保护成员。友元类的一般语法格式如下：
通过友元类声明，友元类的成员函数可以通过对象名直接访问到隐藏的数据，从而达到高效协调工作的目的。在较为复杂的问题中实现不同类之间的数据共享，使用友元类是很必要的选择。（4）C++中的运算符重载设计
①运算符重载的定义
运算符重载是指用同一个运算符完成不同的运算功能。在C++中，运算符重载可以完成两个对象的复杂运算（如两个复数的算术运算等）。
②运算符重载的实现
运算符重载是通过运算符重载函数来实现的，当C++编译系统遇到重载运算符时，如遇到复数加法表达式“c1-c2”中的减号运算符“-”时，会自动调用“-”运算符的重载函数完成c1和c2这两个复数对象的减法运算，而不是执行普通整数或实数的减法运算。
实现类的运算符重载有两种形式，即重载为类的成员函数和重载为类的友元函数。将运算符重载函数作为类的成员函数的格式如下：
函数类型operator重载运算符（形参表）
{
函数体；
}
将运算符重载函数作为类的友元函数的格式如下：
friend函数类型operator重载运算符（形参表）
{
函数体，
}
其中，“函数类型”指出重载运算符的返回值类型；operator是定义运算符重载函数的关键词；“重载运算符”指出要重载的运算符名字，可以是C++中可重载的运算符；“形参表”指出重载运算符所需要的参数及其类型。对于运算符重载为友元函数的情况，还要在函数类型声明之前使用friend关键词来说明。
③两种实现方法的区别
用户从中可以看到，实现同样的重载运算符功能，采用友元函数方式要比采用成员函数方式多一个形参。如一元运算符重载，成员函数方式不带形参，而友元函数方式带一个形参；二元运算符重载，成员函数方式带一个形参，而友元函数方式带两个形参。（5）C++中的对象复制设计
①this指针
a．定义
this是一个隐含于每个类的成员函数的特殊指针，该指针是一个指向正在被某个成员函数操作的对象的指针。
b．调用成员函数
当一个对象调用成员函数时，编译程序先将对象的地址赋给this指针，即当调用成员函数时，this被初始化为被调用的成员函数所在的类实例，即对象的地址，然后调用成员函数，每次成员函数存取数据成员时，隐含使用this指针。通常，不显式使用this指针。
this指针是C++实现封装的一种机制，它将对象和该对象调用的成员函数连接在一起，在外部看来，每个对象都拥有自己的成员函数。
②对象的浅复制与深复制
a．对象的浅复制
当两个对象之间进行复制时，若复制完成后，它们还共享某些资源（内存空间），其中一个对象的销毁会影响另一个对象，这种对象之间的复制称为对象的浅复制。C++中采用赋值运算符进行对象复制时默认的是浅复制。
b．对象的深复制
当两个对象之间进行复制时，若复制完成后，它们不会共享任何资源（内存空间），其中一个对象的销毁不会影响另一个对象，这种对象之间的复制称为深复制。（6）C++中的模板设计
①定义
模板（template）用于把函数或类要处理的数据类型参数化，表现为参数的多态性。模板用于表达逻辑结构相同、具体数据元素类型不同的数据对象的通用行为，从而使程序可以从逻辑功能上抽象，把被处理的对象（数据）类型作为参数传递。
②模板机制分类
C++提供了两种模板机制，即函数模板和类模板（又称类属类）。模板中的类型参数也称为类属参数。
a．函数模板
第一，定义
函数模板是对一组函数的描述，它不是一个真实的函数，编译系统并不对其产生任何执行代码。当编译系统在程序中发现有与函数模板中相匹配的函数调用时，便生成一个重载函数，该重载函数的函数体与函数模板的函数体相同，该重载函数是指模板函数。
第二，声明
声明函数模板的一般格式如下：
template类型形参表
返回类型 函数名（形参表）
{
函数体；
}
其中，“类型形参表”可以包含基本数据类型，也可以包含类类型。类型形参需要加前缀“class"或“typename”。关键词class或typename在这里的意思是“跟随类型形参”。
如果类型形参多于一个，则每个类型形参都要使用class或typename。“形参表”中的参数必须是唯一的，而且在函数定义（包括形参定义）中至少出现一次。另外，在template语句和函数模板声明之间不允许有其他语句。
b．类模板
第一，定义
类模板使用户可以为类定义一种模式，使得类中的某些数据成员、成员函数的参数和返回值能取任意数据类型。类模板用于实现类所需数据的类型参数化。类模板在表示数据结构（如数组、二叉树和图等）时显得特别重要，这些数据结构的表示和算法不受所包含元素类型的影响。
定义类模板的一般格式如下：
其中，“类型形参表”与函数模板中的意义一样。在后面的成员函数定义中，“类型名表”是类型形参的使用。“类型形参表”中的形参要加上“class”或“typename”关键词。类型形参可以是C++中的任何基本类型或用户定义类型。对于在形参表中定义的每个类型，必须使用关键词class或typename。如果类型形参多于一个，则每个形参都要使用关键词class或typename。
同样，类模板不能直接使用，必须先实例化为相应的模板类，再定义该模板类的对象，之后才能使用，如图1-8所示。图1-8 类模板、模板类和类对象之间的关系
第二，模板类的创建格式
在定义类模板之后，创建模板类的一般格式如下：
类模板名 <类型实参表> 对象表；
其中，“类型实参表”应与该类模板中的“类型形参表”相匹配。“对象表”是定义该模板类的一个或多个对象。
③说明
数据结构的实现通常用类模板来描述，这是由于数据结构关注的是数据元素、其关系的保存方法以及基于这些关系的运算的实现方法，而数据元素可以是任意类型。使用类模板来描述，可以避免对于具体数据元素类型的依赖。
三、算法分析
1．算法设计的目标
算法设计应满足以下几个目标：（1）正确性：要求算法能够正确地执行预先规定的功能和性能要求。（2）可使用性：要求算法能够很方便地使用，这个特性又称用户友好性。（3）可读性：算法应该易于人理解，即可读性好。为了达到这个目标，算法的逻辑必须是清晰的、简单的和结构化的。（4）健壮性：要求算法具有很好的容错性，即提供异常处理，能够对不合理的数据进行检查，不经常出现异常中断或死机现象。（5）高效率与低存储量需求：通常算法的效率主要指算法的执行时间。对于同一个问题，如果有多种算法可以求解，执行时间短的算法效率高。算法存储量指的是算法执行过程中所需的最大存储空间。高效率和低存储量都与问题的规模有关。
2．算法的时间效率分析（1）评价算法效率的方法
求解同一问题不同算法的时间效率不同。通常有两种衡量算法效率的方法，即事后统计法和事前分析估算法。前者存在的缺点是必须执行程序，并且存在其他因素掩盖算法本质。所以，以下均采用事前分析估算法来分析算法效率。（2）算法的运行时间
①影响计算机运行时间因素
一个算法用高级语言实现后，在计算机上运行时所消耗的时间与很多因素有关。仅考虑算法本身的效率高低，可以认为一个特定算法的“运行工作量”的大小只依赖于问题的规模（通常用整数量n表示）。
②控制结构和原操作
一个算法是由控制结构（顺序、分支和循环3种）和原操作（指固有数据类型的操作）构成的，算法的运行时间取决于两者的综合效果。
为了便于比较求解同一问题的不同算法，通常的做法是，从算法中选取一种对于所讨论问题来说是原操作的基本语句，算法执行时间大致是这种基本语句的执行时间与其运算次数（一个语句的运行次数称为该语句的频度）的乘积。被视为算法基本语句的语句一般是最深层循环内的语句。执行基本语句的次数越少，其运行时间也就越少；反之，其运行时间也就越多。即一个算法的执行时间可以看成是其中基本语句的执行次数。
③ “O”的形式定义
一个算法的执行基本语句的次数T（n）是问题规模n的某个函数f（n），记作：
T（n）=O（f（n））
记号“O”读作“大O”（是Order的简写，意指数量级），它表示随问题规模n的增大算法执行时间的增长率和f（n）的增长率相同。
若f（n）是正整数n的一个函数，则T（n）=O（f（n））表示存在一个正的常数C和n，使得当n≥n时都满足T（n）≤cf（n），即只00求出T（n）的最高阶，忽略其低阶项和常系数，得到T（n）的近似度量，这样既可简化T（n）的计算，又能比较客观地反映出当n很大时算法的时间性能，又称渐进表示法。如：22T（n）=3n-5n+100= O（n）
④不同数量级下的时间复杂度
在一个没有循环的算法中，基本语句执行次数与问题规模n无关，记作O（1），又称常数阶。在一个只有一重循环的算法中，基本语句执行次数与问题规模n的增长呈线性增大关系，记作O（n），又称线22性阶。其余常用的还有平方阶O（n）、立方阶O（n）、对数阶 nO（1ogn）、指数阶O（2）等。各种不同数量级对应的值存在着以2下关系：
说明：在通常情况下，在分析算法的时间复杂度时除非特别指定，总是分析算法最坏情况下的时间复杂度。
3．算法的存储空间分析
一个算法的存储空间包括形参所占空间和临时变量所占空间。在对算法进行存储空间分析时，只考察临时变量所占空间。
如图1-9所示，其中，临时空间为变量i、maxi占用的空间。图1-9 一个算法的临时空间
所以，空间复杂度是对一个算法在运行过程中临时占用的存储空间大小的量度，一般也作为问题规模n的函数，以数量级形式给出，记作：S（n）=O（g（n））
若所需临时空间相对于输入数据量来说是常数，则称此算法为原地工作或就地工作。若所需临时空间依赖于特定的输入，则通常按最坏情况来考虑。
因为形参的空间会在调用该算法的算法中考虑，所以算法占用的空间只考虑临时空间，而不必考虑形参的空间。
四、数据结构的目标
1．抽象数据类型
从数据结构的角度看，一个求解问题可以通过抽象数据类型的方法来描述，即抽象数据类型对一个求解问题从逻辑上进行了准确的定义，所以抽象数据类型由数据的逻辑结构和抽象运算两部分组成。
在用计算机解决问题时，首先要设计其存储结构，然后在存储结构上设计实现抽象运算的算法。而一种数据的逻辑结构可以映射成多种存储结构，抽象运算在不同的存储结构上实现可能对应多种算法，而且在同一种存储结构上实现也可能有多种算法，因此需要明确的标准来评价算法的好坏。
2．算法的评价标准
算法的评价标准是指算法占用计算机资源的多少，占用计算机资源越多的算法越不好，反之，占用计算机资源越少的算法越好。这是通过算法的时间复杂度和空间复杂度分析来完成的。设计好的算法的过程如图1-10所示。图1-10 设计好的算法的过程
在采用C++面向对象的程序设计语言实现抽象数据类型时，通常将一个抽象数据类型设计成一个C++类，如图1-11所示。在该图中，采用类的数据成员表示数据的存储结构，将抽象运算通过类的公有成员函数实现。图1-11 用C++类实现抽象数据类型
从该图可以看到，算法设计分为3个步骤，即通过抽象数据类型进行问题定义、设计存储结构和设计算法，这3个步骤并不是独立的。其中，设计存储结构是关键的一步，在选择存储结构时需要考虑其对算法的影响。存储结构对算法的影响两个方面。（1）存储结构的存储能力
如果存储结构的存储能力强、存储的信息多，设计算法会很方便；反之，对于过于简单的存储结构，就要设计一套比较复杂的算法。在这一点上,经常体现出时间与空间的矛盾，存储能力往往和所使用的空间大小成正比。（2）存储结构应与所选择的算法相适应
存储结构是实现算法的基础，也会影响算法的设计，其选择要充分考虑算法的各种操作，应与算法的操作相适应。
学习数据结构时，不仅要学会设计存储结构，还需要掌握基本的算法分析能力，能够熟练判别“好”算法和“坏”算法。
3．数据结构的目标
数据结构的目标就是针对求解问题设计好的算法。
1.2 课后习题详解
一、单项选择题（1）计算机所处理的数据一般具备某种内在联系，这是指______。
A．数据和数据之间存在某种关系
B．元素和元素之间存在某种关系
C．元素内部具有某种结构
D．数据项和数据项之间存在某种关系【答案】B【解析】数据是计算机操作对象的总称，数据元素是计算机处理数据的基本单位，因此数据之间的内在联系指的应该是数据元素和数据元素之间的关系。（2）在数据结构中，与所使用计算机无关的是数据的______结构。
A．逻辑
B．存储
C．逻辑和存储
D．物理【答案】A【解析】数据的逻辑结构是从逻辑关系上描述数据的，它与数据的存储无关，是独立于计算机的。而数据的存储结构是指数据元素及其关系在计算机存储器中的存储方式，也称为数据的物理结构，与计算机有关。（3）数据结构在计算机中的表示称为数据的______。
A．存储结构
B．抽象数据类型
C．顺序结构
D．逻辑结构【答案】A【解析】数据的存储结构是逻辑结构用计算机语言的实现或在计算机中的表示。（4）在计算机中存储数据时，通常不仅要存储各数据元素的值，还要存储______。
A．数据的处理方法
B．数据元素的类型
C．数据元素之间的关系
D．数据的存储方法【答案】C【解析】存储实现的基本目标是建立数据的机内表示，其包括两个部分，即数据元素的存储和数据元素之间关系的存储。（5）在计算机的存储器中表示数据时，逻辑上相邻的两个元素对应的物理地址也是相邻的，这种存储结构称为______。
A．逻辑结构
B．顺序存储结构
C．链式存储结构
D．以上都正确【答案】B【解析】顺序存储结构是把逻辑上相邻的结点存储在物理位置上相邻的存储单元中，结点之间的逻辑关系由存储单元的邻接关系来体现，由此得到的存储表示称为顺序存储结构。所以答案B项正确；逻辑结构是独立于计算机的与存储结构相平行的概念，并不是存储结构的一种，A项错误；中链式存储结构不要求逻辑上相邻的结点在物理位置上也相邻，结点同的逻辑关系用附加的指针域来表示，C项错误。（6）当数据采用链式存储结构时，要求______。
A．每个结点占用一片连续的存储区域
B．所有结点占用一片连续的存储区域
C．结点的最后一个数据域是指针类型
D．每个结点有多少个后继就设多少个指针域【答案】A【解析】数据采用链式存储结构时，各个结点之间不要求采用连续的存储空间，而是用指针记录下一个结点的位置，B项错误；但是每个结点内部所用的存储空间必须是连续的，A项正确；结点的最后一个数据域存放的不是指针类型，C项错误；每个结点除后继结点外还可能有前驱结点，指针域的个数应该为这两者的总和。（7）以下关于算法的说法正确的是______。
A．算法最终必须由计算机程序实现
B．算法等同于程序
C．算法的可行性是指指令不能有二义性
D．以上都是错误的【答案】D【解析】算法具有可行性，指借助纸、笔或计算机可以完成，不一定通过计算机程序实现，因此A、C项不正确。指令不能有二义性是算法的确定性。程序是某种计算机语言对一个算法的具体实现，同时也不一定具有算法有穷性的特性，依次算法不等同于程序，B项错误。（8）算法的时间复杂度与______有关。
A．问题规模
B．计算机硬件性能
C．编译程序质量
D．程序设计语言【答案】A【解析】程序的运行时间与四个选项中的问题规模，计算机硬件性能，编译程序质量，程序设计语言都有关系，撇开与计算机硬件软件相关的因素，算法的时间复杂度只依赖于问题规模。（9）算法的主要任务之一是分析______。
A．算法是否具有较好的可读性
B．算法中是否存在语法错误
C．算法的功能是否符合设计要求
D．算法的执行时间和问题规模之间的关系【答案】D【解析】算法的时间复杂度是衡量算法好坏的重要标准，因此分析算法的执行时间与问题规模之间的关系是算法的主要任务之一。2（10）某算法的时间复杂度为O（n），表明该算法的______。2
A．问题规模是n2
B．执行时间等于n2
C．执行时间与n成正比2
D．问题规模与n成正比【答案】C【解析】本题考点在于对O含义的理解。O（f（n））,表示随问题规模n的增大算法执行时间的增长率和f（n）的增长率相同。在本题中即2表示算法执行时间的增长率与n增长率相同，即二者成正比，因此答案为C项。
二、问答题（1）简述数据与数据元素的关系与区别。
答：凡是能被计算机存储、加工的对象统称为数据，数据是一个集合；数据元素是数据的基本单位，是数据的一个元素。
数据元素与数据之间的关系是元素与集合之间的关系。（2）简述数据结构与数据类型的区别。
答：数据类型是一组性质相同的值的集合和定义在此集合上的一组操作的总称，是指计算机处理的数据元素的组织形式和相互关系，而数据类型是某种程序设计语言中已实现的数据结构。在程序设计语言提供的数据类型的支持下，可以根据从问题中抽象出来的各种数据模型，逐步构造出描述这些数据模型的各种新的数据结构。（3）试举一个例子，说明对于相同的逻辑结构，采用同一种运算在不同的存储方式下实现，其运算算法的效率是不同的。
答：对于顺序表和单链表两种数据结构：其逻辑结构都是线性表，而存储结构分别为顺序存储与链式存储。在顺序表上进行插入操作，需要移动待插入元素之后的数据，平均次数为n/2（n为数据元素个数）；而在链表上进行插入操作，则仅仅需要把待插入元素的节点连接进链表的相应位置而无需移动数据元素，插入运算的效率比顺序存储要好。从这个例子可以看出即使有相同的逻辑结构，同一运算在不同存储方式下的运算效率也是会有所不同的。2（4）一个算法的执行频度为（3n+2nlogn+4n-7）／（10n），其2时间复杂度是多少？
答：O（n）2【解析】该算法的执行频度为（3n+2nlogn+4n-7）／（10n）=0.3n2+0.2logn+0.4-0.7/n，算法整体的时间复杂度时只考虑各部分之中时2间复杂度中最高者，由不同数量级的时间复杂度对应值的关系可知，O(n)的值最大，因此本题答案为O（n）。3（5）某算法的时间复杂度为O（n），当n=5时执行时间为50s，那么当n=15时，其执行时间是多少？
答：400s。33【解析】O（n）表示算法执行的时间与n的规模成正比，设33n=15时其执行时间为t,则有50/ 5=t/ 15,解得t=400s。（6）分析以下算法的时间复杂度。
答：T(n)=n/2－1=O(n)。【解析】本题中的原操作为内层循环中的k++,和i+=2，其执行次数即为循环次数，由程序可知，循环次数应为n/2，所以本题的时间复杂度为应该与n/2成正比，为O(n)。（7）分析以下算法的时间复杂度。2
答：O(nlogn)。5【解析】算法时间复杂度与原操作，即最内层函数执行次数有关。在本题的算法中，最内层函数为k=5*k，这一操作执行了logn次，在此52内层循环外嵌套了两层循环，执行的次数为n。所以总的执行次数为22nlogn，即算法的时间复杂度为0(nlogn)。55（8）有以下递归函数fact（n），分析其时间复杂度。
答：O(n)。【解析】分析此递归函数的功能可知此函数为对n求阶乘n!的函数，当n大于1时，n的值减1，同时结果会在原来运算基础上乘以将(n-1)代入函数后返回的值，因此递归的次数一共为n次，所以此函数的时间复杂度为O(n)。
第2章 线性表
2.1 复习笔记
一、线性表
1．线性表的定义
线性表是具有相同特性的数据元素的一个有限序列。
2．线性表的特征
线性表的特征有：（1）所有数据元素的类型相同；（2）线性表是由有限个数据元素构成的；（3）线性表中的数据元素是与位置有关的，通常从1开始编号，每个数据元素有唯一的序号，这一点表明线性表不同于集合；（4）线性表中的数据元素可以重复出现，而集合中的数据元素不会重复出现。
3．线性表的逻辑结构（1）逻辑结构表示
线性表的逻辑结构一般表示为（a，a，…，a，a，…，12ii+1a），用图形表示逻辑结构如图2-1所示。n图2-1 线性表的逻辑结构示意图
其中，用n（n≥0）表示线性表的长度（即线性表中数据元素的个数）。当n=0时，表示线性表是一个空表，不包含任何数据元素。（2）线性表的逻辑特征
对于至少含有一个数据元素的线性表，除开始元素α（又称首元1素）没有前趋元素外，其他每个元素α（2≤i≤n）有且仅有一个前趋元i素α；除终端元素α（又称尾元素）没有后继元素外，其他元素i-1nα（1≤i≤n-1）有且仅有一个后继元素α。即在线性表中，每个元素ii+1至多只有一个前趋元素并且至多只有一个后继元素。
4．线性表的抽象数据类型
线性表的抽象数据类型描述线性表的抽象数据类型描述如下：
二、线性表的顺序存储结构
1．线性表的顺序存储结构—顺序表（1）定义
线性表的顺序存储结构是把线性表中的所有元素按照其逻辑顺序依次存储到从计算机存储器中指定存储位置开始的一块连续的存储空间中。线性表的顺序存储结构称为顺序表。（2）实现
①具体实现方法
采用C++语言中的一维数组data来实现顺序表，并设定该数组的长度为常量MaxSize，图2-2所示为将长度为n的线性表存放在data数组中。图2-2 长度为n的线性表存放在顺序表中
②说明
数组的长度是指存放线性表的存储空间的长度，存储分配后这个量一般是不变的，而线性表的长度是指线性表中的数据元素的个数，随着线性表的插入和删除操作而发生变化，但在任何时刻都不能大于数组的长度MaxSize。由于线性表的长度小于可以数组data的长度，此时该数组中有一部分是空闲的，所以设计一个变量length表示顺序表的长度，即顺序表data数组中实际数据元素的个数。
线性表中的元素a（1≤i≤n）的逻辑序号为i，在对应顺序表中该i元素的物理序号为i-1。算法形参中的序号i通常指逻辑序号。（3）类模板的声明
①具体声明方法
采用一个类模板SqListClass
试读结束[说明：试读内容隐藏了图片]