如何用C++来编写链式结构

如何用C++来编写链式结构

学习如何用C++来编写链式结构。加强理解C++动态内存以及编写动态内存类的相关概念。

11.1　概要

在使用Python的链式结构的时候，即使你设置了一个对错误的链接对象的引用，Python也并不会去阻止你编写这样的语义错误（比如，插入节点的时候，可能会弄混​​link​​​指向下一个节点的链接，从而导致跳过了一个节点，或者把节点的​​link​​​指向它自己或更早的节点，从而导致循环链式结构）。C++环境同样也不会自动捕获这些类型的语义错误。要找到这种类型的错误的最好的办法是广泛地测试你的代码。但是，Python也还是会捕获一些C++编译器和运行时环境可能不会捕获的错误。比如，Python不允许你使用名称来访问还没有指向有效对象的引用上的数据（例如，尚未定义或者值为​​None​​​的名称）。如果名称​​node​​​引用的是​​None​​​，那么在当你尝试执行​​node.link​​​或者​​node.item​​的时候，Python解释器将会始终捕获这个问题，并且在你没有捕获这个异常的时候，产生相应的异常以及回溯执行堆栈。在C++里，如果你尝试解引用一个还没有初始化的指针或者是引用一个已经被释放的对象的指针的话，那么运行时环境将会继续尝试访问这个内存位置，从而导致获取到垃圾数据，或者是内存故障从而导致程序崩溃。这部分内容我们在前一章里已经讨论过了。

C++并不允许你直接将一种类型的指针分配给另一个不同类型的指针（比如说，如果​​x​​​是指向​​int​​​的指针而​​y​​​是指向​​double​​​的指针，那么你不能写​​y = x​​​这样的代码）。你可以使用​​reinterpret_cast​​​把一种类型的指针转换成另一种类型（它的语法类似于8.9节里讨论的​​static_cast​​​），但它并不是被用来做这件事情的，而且​​reinterpret_cast​​也并不是那么常用。C++编译器会去检查数据类型是否匹配，但C++的运行时环境则不会去检查指针实际上所指向的有效内存位置是不是包含这个类型的值。当你解引用一个没有指向有效内存位置的指针的时候，你的程序有可能会崩溃，就算这个程序可能能够继续运行，你的程序结果也并不正确，就像我们在10.5节里讨论的那样。

在本章后面你将会看到，C++里的链式结构的代码并不会比Python版本的代码长。通常来说，你都可以把Python链式结构的代码逐行转换为C++代码。但是，从头开始编写C++动态内存和链式结构的代码将会比编写Python的链式结构更困难，这是因为Python会阻止某些类型的错误的产生，从而可以更容易地查找和修复其他类型的错误。在我们讨论了C++里的链式结构的一些其他问题之后，我们将把我们的Python链式结构的一个例子翻译成C++版本。

11.2　C++链式结构的类

在Python里，我们使用了一个包含两个数据元素的​​ListNode​​​类，它们分别是数据值和对链表里下一个​​ListNode​​​的引用。我们可以在C++里使用相同的技术来保存数据元素以及指向链表里下一个节点的指针。C++版本和Python版本之间的一个显著区别是：C++的​​ListNode​​​类只能包含一种类型的元素（在我们的例子里用的是​​int​​​）。这是因为所有的C++变量都必须有一个确定的类型。我们将在第12章里学习模板相关的知识，它们将能够让我们编写一个可以容纳任何类型的​​ListNode​​​类。下面是C++的​​ListNode​​类的一个简单例子，我们将在这一节的后面部分对它进行扩展：

class ListNode {public: int item_; ListNode *link_;};

对于初学者来说，一个容易犯的简单错误是会忘记在​​link_​​​实例变量前面加上代表指针的星号。你的C++编译器会要求一定要加上这个星号，是因为你在​​ListNode​​​的定义里又包含了​​ListNode​​​。而因为每一个​​ListNode​​​都包含一个​​ListNode​​​作为其数据成员，所以在本质上这也就是一种无限递归，会让​​ListNode​​​消耗掉无穷无尽的内存。我们在前面提到过，因为指针需要存储某个类型的对象的地址，而不是实际对象，所以指向任何数据类型的指针在32位系统上都需要4字节。也就是说，除了需要存储的数据所需要的类型相关的内存大小之外，​​ListNode​​还需要额外的4字节来存储这个指针。

#ifndef _LISTNODE_H#define _LISTNODE_H#include class ListNode { friend class LList;public: ListNode(int item = 0, ListNode* link = NULL);private: int item_; ListNode *link_;};inline ListNode::ListNode(int item, ListNode *link){ item_ = item; link_ = link;}#endif // _LISTNODE_H

​​ListNode​​​的构造函数将能够让我们使用零个、一个或者是两个参数来调用构造函数。我们为​​int​​​类型的参数提供了默认值零，这样我们就可以得到一个不需要任何参数的默认构造函数。​​link​​​参数的默认值是​​NULL​​​。和Python的​​None​​​值的判断结果为​​false​​​一样，​​NULL​​​值（其实也就是零）的判断结果也是​​false​​​，所以我们可以通过它来检查尚未初始化或者是无效的指针。因此，我们可以编写像是​​if (node != NULL)​​​或者它的简写版本​​if (node)​​​这样的代码来检查有效指针，因为​​NULL​​​会被判断为​​false​​​，而对于任何有效指针地址的判断结果则会是​​true​​​。我们在Python的章节里讨论过了在代码里使用​​is​​​运算符的链式结构，比如说：​​if node is not None​​​是在Python里执行这种判断的最好方法。但是在C++里并没有​​is​​​运算符，因此我们会使用​​if (node)​​​或​​if (node != NULL)​​​来进行判断。就C++的性能而言，这两个语句并没有任何的区别。为了方便阅读，一些程序员会更喜欢写成​​if (node != NULL)​​​，但是大多数程序员都会使用简写​​if (node)​​。

由于构造函数只有两行，因此我们把它定义成了内联函数，从而避免函数调用的额外开销。可以看到，我们遵循了在实例变量名称后添加下划线的约定。这样做除了有下划线这部分不同，实例变量和形参使用的是相同的名称。

回想一下10.2节的​​Rational​​​类的例子。在那个例子里，我们不能解引用指针，而且由于优先级问题，也不能使用没有括号的点运算符。那个时候我们提到了常见的用法是使用​​->​​。但是，像下面这个例子展示的那样，有两种正确的方法都可以完成这一功能：

ListNode *node;node = new ListNode(2); // item parameter is requirednode->item_ = 3; // this is correct*node.item_ = 3; // this is not correct(*node).item_ = 3; // this is correct

11.3　C++链表

#ifndef _LLIST_H#define _LLIST_H#include "ListNode.h"class LList {public: LList(); LList(const LList& source); ~LList(); LList& operator=(const LList& source); int size() { return size_; } void append(const ItemType &x); void insert(int i, const ItemType &x); ItemType pop(int i=-1); ItemType& operator[](int position);private: // methods void copy(const LList &source); void dealloc(); ListNode* _find(int position); ItemType _delete(int position); // data elements ListNode *head_; int size_;};#endif // _LLIST_H

我们的​​ListNode​​​和​​LList​​​类的一个缺点是它们只能使用一种数据类型（在我们的例子里是整数）。到目前为止，我们将渐进式地改进这一点，并且会使用C/C++的关键字​​typedef​​​。这个关键字能够让我们定义新的类型名称。在下面的例子里，我们创建了一个叫作​​ItemType​​​的类型，它现在是​​int​​​的同义词。接下来，我们可以更新我们的​​ListNode​​​和​​LList​​​类，从而在和列表里存储的值相应的位置使用​​ItemType​​​类型而不是​​int​​​类型。可以看到，我们并没有把所有​​int​​​类型出现的地方都改成​​ItemType​​​类型。因为，不管是什么数据类型，​​LList​​​的大小都是一个整数。现在，如果我们想要创建一个可以包含不同类型的​​LList​​​的话，比如说​​double​​​或者是​​Rational​​​，我们只需要修改ListNode.h文件里的那个​​typedef​​行就行了（如果它不是内置类型的话，还需要包含相对应的头文件）。

​​typedef​​​语句并不允许我们在同一个程序里去存储不同的类型。因此，在一个程序里的每个​​ListNode​​​都必须使用我们用​​typedef​​​命令所指定的那个类型。也就是说，因为程序中只能包含有一个名为​​LList​​​的类和一个名为​​ListNode​​​的类，所以一个程序只能有一个类型的​​LList​​​。我们也可以复制这部分代码并创建一批像​​ListNodeInt​​​/​​LListInt​​​以及​​ListNodeDouble​​​/​​LListDouble​​​这样的类，并且修改每个文件里的​​typedef​​​行，这样也就可以在一个程序里简单重用现有的代码来实现不同的功能了。在第12章，我们将讨论模板，模板将能够让我们在一个程序里，在不需要为每一种类型都复制一个类文件的情况下，包含不同类型的列表。在这里，使用​​typedef​​​语句可以让我们在之后更容易地将这个程序转换成基于模板的版本。下面的代码是包含​​typedef​​​版本的​​ListNode​​​和​​LList​​类头文件：

// ListNode.h#ifndef _LISTNODE_H#define _LISTNODE_H#include typedef int ItemType;class ListNode { friend class LList;public: ListNode(ItemType item, ListNode* link = NULL);private: ItemType item_; ListNode *link_;};inline ListNode::ListNode(ItemType item, ListNode *link){ item_ = item; link_ = link;}#endif // _LISTNODE_H// LList.h#ifndef _LLIST_H#define _LLIST_H#include "ListNode.h"class LList {public: LList(); LList(const LList & source); ~LList(); LList& operator=(const LList& source); int size() { return size_; } void append(ItemType x); void insert(size_t i, ItemType x); ItemType pop(int i=-1); ItemType& operator[](size_t position);private: // methods void copy(const LList&source); void dealloc(); ListNode* _find(size_t position); ItemType _delete(size_t position); // data elements ListNode *head_; int size_;};#endif // _LLIST_H

构造函数的作用是初始化实例变量。我们将对指针变量使用​​NULL​​​值来表示它没有指向任何有效节点。因为我们只有两个实例变量来初始化​​LList​​类，所以默认构造函数会非常简单：

def __init__(self): self.head = None self.size = 0// LList.cpp#include "LList.h"LList::LList(){ head_ = NULL; size_ = 0;}

除了很明显的语法差异之外，​​_find​​方法的代码是基本相同的：

def _find(self, position): node = self.head for i in range(position): node = node.link return nodeListNode* LList::_find(size_t position){ ListNode *node = head_; size_t i; for (i = 0; i < position; i++) { node = node->link_; } return node;}

​​_delete​​​方法会有一些差异，这是因为我们需要从列表里删除一个元素。在C++的版本里，我们必须要使用​​delete​​​语句来释放与需要删除的​​ListNode​​实例相应的内存：

def _delete(self, position): if position == 0: item = self.head.item self.head = self.head.link else: node = self._find(position - 1) item = node.link.item node.link = node.link.link self.size -= 1 return itemItemTypeLList::_delete(size_t position){ ListNode *node, *dnode; ItemType item; if (position == 0) { dnode = head_; head_ = head_->link_; item = dnode->item_; delete dnode; } else { node = _find(position - 1); if (node != NULL) { dnode = node->link_; node->link_ = dnode->link_; item = dnode->item_; delete dnode; } } size_ -= 1; return item;}

Python里其实也有一个叫作​​del​​​的语句，它可以从可访问的名称字典里删除标识符来在当前名称空间里删除名称（如果你需要回顾一下关于Python的名称字典的相关知识的话，可以参阅4.2节）。就像你知道的那样，当你删除一个名称的时候，名称所引用的对象的引用计数将会减1。当对象的引用计数减少到零的时候，Python就会释放这个对象的内存。下面这个Python版本的代码显示了​​del​​语句的用法：

def _delete(self, position): if position == 0: dnode = self.head self.head = self.head.link x = dnode.item del dnode # not necessary in Python else: node = self._find(position - 1) if node is not None: dnode = node.link node.link = dnode.link x = dnode.item del dnode # not necessary in Python self.size -= 1 return x

就像注释里说的那样，​​del​​​语句并不是必需的；但是，用了它也不会造成任何问题。除非在调用​​_delete​​​方法的函数/方法的调用链里还有另一个Python的名称引用着名称​​dnode​​​，不然的话它应该是唯一一个引用这个对象的名称。这是因为：只要没有其他的名称在引用这个对象的话，那么​​del​​​语句就会把​​ListNode​​​对象的引用计数减少到零，然后Python会释放这个对象；或者，如果不用​​del​​​语句的话，那么在函数结束并且从本地名称字典中删除​​dnode​​​名称的时候，引用计数也将被减少到零。在我们最早的Python版本里，被删除的​​ListNode​​​对象的引用计数会在语句​​self.head = self.head.link​​​或者语句​​node.link = node.link.link​​​之后减少，所以原始版本和带有​​del​​语句的新版本具有相同的最终结果。

虽然Python的​​del​​​和C++的​​delete​​​关键字在这个例子里看起来完成了相似的工作，而且工作方式非常相似，但它们原理上并不会执行相同的操作。Python的​​del​​​语句是从当前命名空间里删除一个名称，而C++的​​delete​​​语句则会释放内存。在这个例子里，我们必须要用C++的​​delete​​​语句，不然代码将会出现内存泄漏。应该注意到的一个关键概念是：​​delete​​​语句会为对象释放内存，而不管是否有其他的指针变量指向同一个对象。如果还有任何其他的指针指向这个对象的话，那么在执行​​delete​​语句之后，解引用这些指针就会产生错误。我们在10.5.3小节里已经讨论过了这个问题。

Python程序员在学习C++的时候经常犯的一个错误是：会忘记在想要分配节点的时候使用​​new​​​关键字（也就是，他们会写成​​node-> link_ = ListNode(x)​​​）。如果忘记​​new​​​语句的话，编译器将会生成错误。当你想要分配一个节点的时候，就需要使用​​new​​​语句；而当你想要释放一个节点的时候，就应该使用​​delete​​​语句。Python里的内存分配是类似的：当你想要分配节点的时候，只需要调用构造函数（例如，​​node = ListNode(x)​​​）。接下来我们可以看到，​​append​​​和​​insert​​方法在Python里和C++里是基本相同的：

def append(self, x): newNode = ListNode(x) if self.head is not None: node = self._find(self.size - 1) node.link = newNode else: self.head = newNode self.size += 1void LList::append(ItemType x){ ListNode *node, *newNode = new ListNode(x); if (head_ != NULL) { node = _find(size_ - 1); node->link_ = newNode; } else { head_ = newNode; } size_ += 1;} def insert(self, i, x): if i == 0: self.head = ListNode(x, self.head) else: node = self._find(i - 1) node.link = ListNode(x, node.link) self.size += 1void LList::insert(size_t i, ItemType x){ ListNode *node; if (i == 0) { head_ = new ListNode(x, head_); } else { node = _find(i - 1); node->link_ = new ListNode(x, node->link_); } size_ += 1;}

​​pop​​​方法会有些不同，因为在Python里，我们会通过使用默认的参数值​​None​​​来表示我们想要删除的列表里的最后一项元素。但是，因为C++没有动态类型以及​​None​​​这样的特殊值，所以我们必须要使用一个特定的整数来表示默认值。在这里，我们选择用数字​​-1​​​来表示我们将要删除最后一项。除了这个区别之外，​​pop​​​方法在两个语言里是相同的。当然，我们在这里还是忽略了测试参数​​i​​​是否在​​0​​​～​​size_ - 1​​范围内：

def pop(self, i = None): if i is None: i = self.size - 1 return self._delete(i)ItemType LList::pop(int i){ if (i == -1) { i = size_ - 1; } return _delete(i);}

为了能够像我们在使用Python序列和C++数组那样，使用方括号来访问列表的元素，我们需要使用运算符重载。下面这个例子还展示了在C++里应该使用的引用返回类型。这让我们只需要在一个方法里就可以编写出Python的​​__getitem__​​​和​​__setitem__​​​方法。在这里只包含了Python的​​__getitem__​​方法来进行比较：

def __getitem__(self, position): node = self._find(position) return node.itemItemType& LList::operator[](size_t position){ ListNode *node; node = _find(position); return node->item_;}

在下一个例子中，我们展示了这个方法的用法。如果返回类型不是引用的话，那么语句​​x = a[1]​​​是可以起作用的。但是因为没有返回引用，所以语句​​a[2] = 40​​将不能正常工作。和Python一样，赋值语句左侧的元素必须是一个可以用来存储值的地方。计算机科学里对这种地方所使用的技术术语是左值（l-value）。同时，赋值语句右侧的元素可以是变量、常量或者是表达式。返回引用相当于返回了第二个​​ListNode​​​里的​​item_​​的内存位置。当在赋值运算符的左侧使用返回的引用类型的时候，赋值语句的结果（语句右侧的表达式的值）将会被存储在由方法或者函数返回的变量的内存位置里。当在右侧使用引用返回类型或者把它作为表达式的一部分的时候，赋值语句将会使用实际数据值而不是返回的变量的内存地址。我们曾经在10.4.5小节里讨论过了返回引用的一些常见问题。

#include "LList.h"int main(){ LList a; int x; a.append(10); a.append(20); a.append(30); // both of these methods cause the operator[] method to be called x = a[1]; // returns 20 which is stored in x a[2] = 40; // changes the 30 at the last ListNode’s item to 40 return 0;}

我们现在再去看看那些需要处理链表的动态内存的其他方法。由于Python会自动地处理内存释放，因此在Python的代码里没有相应的代码来和这些方法的C++版本进行比较。复制构造函数被用来生成​​LList​​​对象的深拷贝，它需要为它正在复制的原始源​​LList​​​里的每一个现有的​​ListNode​​​实例都创建一个新的​​ListNode​​​实例。我们提到过，当按值传递这个类型的对象的时候，将会调用复制构造函数。同样地，因为我们也需要在赋值运算符里复制整个列表，所以我们会编写一个让这两个方法都可以调用的​​copy​​​方法。我们会通过遍历源列表里的所有​​ListNode​​​对象，并且在这个循环里为新列表创建一系列新的​​ListNode​​​对象，并恰当地连接​​link_​​​链接，来创建一个深拷贝。要更简单地编写这个​​copy​​​方法的话，我们还可以通过迭代所有元素并且使用​​append​​​方法将它们添加到新的​​LList​​​对象里去。但是如果没有​​tail_​​实例变量来代表列表尾部的话，这样做的效率是不高的。

我们之前说过，在Python里是不用编写赋值运算符的，这是因为Python里的赋值只会把另一个名称绑定到同一个对象上（也就是使这个名称成为对同一个对象的引用）。C++的赋值运算符则需要首先释放存储元素的现有​​ListNode​​​对象，不然的话我们的代码就会发生内存泄漏。我们将会调用​​dealloc​​​方法来释放现有的​​ListNode​​对象。下面的例子将会展现这些内容：

LList::LList(const LList& source){ copy(source);}void LList::copy(const LList &source){ ListNode *snode, *node; snode = source.head_; if (snode) { node = head_ = new ListNode(snode->item_); snode = snode->link_; } else { head_ = NULL; } while (snode) { node->link_ = new ListNode(snode->item_); node = node->link_; snode = snode->link_; } size_ = source.size_;}LList & LList::operator=(const LList& source){ if (this != &source) { dealloc(); copy(source); } return *this;}

类的析构函数需要释放掉当前列表里的每个​​ListNode​​​对象，这是因为这些对象是还没有被释放掉的​​ListNode​​​实例。这样做能够确保每当​​LList​​​对象被释放的时候，任何动态分配的内存都会被释放。提醒一下，析构函数会在非指针实例超出作用域，或者是对指向​​LList​​​对象的指针调用了​​delete​​​语句之后，被自动调用。由于我们也会在赋值运算符里去释放​​ListNode​​​实例，因此我们会用一个​​dealloc​​​方法来包含这些逻辑，并让赋值运算符和析构函数都去调用它。我们可以通过重复地调用​​pop​​​方法或者是使用​​_delete​​​方法来为我们的​​dealloc​​​方法编写代码，因为它们都会从列表里一次删除一个元素。但考虑到效率因素，我们将直接实现相关的逻辑。代码将会遍历每一个​​ListNode​​​并且使用​​delete​​​语句来释放它的内存。要注意的是，在释放当前​​ListNode​​​之前，我们必须前进到下一个​​ListNode​​​里去。因为一旦我们释放了一个​​ListNode​​，我们就再也不能去访问它了，也就会导致我们没有办法找到下一个节点。因为我们在执行列表操作的时候，会经常需要访问当前节点和这个节点之前的那个节点，所以通过两个指针来跟踪——一个用于当前节点，一个用于前一个节点——是单链式结构里常见的使用技术：

LList::~LList(){ dealloc();}void LList::dealloc(){ ListNode *node, *dnode; node = head_; while (node) { dnode = node; node = node->link_; delete dnode; }}

当你查看这些方法的代码的时候，你可能会想要知道我们是如何确定每个​​new​​​语句都有一个相应的​​delete​​​语句，从而释放掉由​​new​​​语句分配的​​ListNode​​​对象的内存的。我们将会使用下面这个简单的程序来讨论它。在阅读下面这段代码之后的段落前，先尝试看你能不能去确定这段代码一共执行了多少个​​new​​​和​​delete​​语句，以及它们分别是在什么时候被执行的：

#include "LList.h"int main(){ LList b, c; int x; b.append(1); b.append(2); b.append(3); c.append(4); c.append(5); c = b; x = b.pop();}

每个变量都会调用一次构造函数，但这不会执行任何​​new​​​或​​delete​​​语句。对​​append​​​方法的5次调用将会导致执行5次​​new​​​语句。​​c = b​​​语句会执行两次​​delete​​​语句，这是因为​​operator=​​​会调用​​dealloc​​​方法，而且实例​​c​​​会删除掉包含​​4​​​和​​5​​​的​​ListNode​​​对象。然后这一步会调用​​copy​​​方法来执行3个​​new​​​语句，所以到目前为止，我们一共有6个​​ListNode​​​对象：变量​​b​​​有3个​​ListNode​​​对象，包含数字​​1​​​、​​2​​​和​​3​​​；变量​​c​​​也有3个​​ListNode​​​对象，包含​​1​​​、​​2​​​和​​3​​​。语句​​x = b.pop()​​​会执行​​delete​​​语句来释放​​LList​​​的对象​​b​​​里包含​​3​​​的​​ListNode​​​对象。当函数结束的时候，​​LList​​​的析构函数会自动被调用两次：一次是给变量​​b​​​的，一次是给变量​​c​​​的。当调用​​b​​​的析构函数的时候，它会调用​​dealloc​​​方法来删除包含​​1​​​和​​2​​​的​​ListNode​​​对象。当调用​​c​​​的析构函数的时候，它会删除包含​​1​​​、​​2​​​和​​3​​​的3个​​ListNode​​对象。

图11.1所示的图形向我们展示了上面那个例子在两个时间点的执行情况。上面部分展示的是语句​​c = b​​​之前的情况，下面部分则显示了在程序结束之后的情况。在这里我们用从​​1 000​​​开始的内存地址来作为堆栈动态变量，同时动态堆从​​2 000​​​开始。我们使用的内存地址可以是在内存里的任何位置。从这个例子可以看到，我们在​​operator=​​​方法里调用了​​dealloc​​方法去释放了一些内存之后，又重用了一些内存地址。就像之前提到过的那样，实际使用的内存地址会有所不同，内存地址可能会在被释放之后立即被重复使用，也可能并不会被立即使用。

图11.1　​​LList​​例子的图形表示

在什么时候指针会调用析构函数？作为对这个问题的提醒，我们将通过下面这个例子来讨论析构函数是在什么时候被调用的：

LList* f(){ LList b; LList *c; b.append(1); c = new LList; c->append(2); return c; // the function returns a pointer to an LList instance // destructor is automatically called for b when the function ends}int main(){ LList *p; p = f(); p->append(3); delete p; // delete statement causes destructor to be called}

变量​​b​​​的析构函数会在函数​​f​​​的末尾被调用，这是因为​​b​​​只是一个局部变量，它的生命周期在函数完成执行的时候就结束了。这也代表着，包含值​​1​​​的​​ListNode​​​对象也会被释放。变量​​c​​​在函数​​f​​​的末尾的时候超出了作用域，但是由于它是一个指针变量，因此只会释放存储​​LList​​​对象地址的这4字节。包含值​​2​​​的​​ListNode​​​的​​LList​​​对象将会继续存在。而且，当函数结束的时候，并不会为变量​​c​​​调用析构函数。如果我们想在函数​​f​​​里调用析构函数的话，就需要在函数的代码体里添加语句​​delete c​​​来强制执行它。函数​​f​​​将会返回由​​c = new LList​​​语句创建的​​LList​​​对象。然后​​main​​​函数会把整数​​3​​​添加到这个列表里去。而当执行​​delete p​​​语句的时候，就会调用​​LList​​​的析构函数。这个时候，就会把由函数​​f​​​里的​​c = new LList​​​语句所创建的​​LList​​​对象释放掉。析构函数也同时会释放它所包含的两个​​ListNode​​​对象。当函数完成之后，指针​​p​​的4字节也将会被自动释放，所有的本地堆栈动态变量的字节也是同样的操作。

11.4　C++链接的动态内存错误

我们在10.5节里讨论过关于动态内存的相关问题，也同样适用于使用动态内存的链式结构，因此再去看一看这部分内容是一个很好的主意。如果你有一个​​ListNode​​​变量​​*node​​​的话，你需要记得​​node->item_​​​和​​node->link_​​​都是解引用指针。因此，如果​​node​​​没有保存一个关于​​ListNode​​​的有效地址的话，那么这些语句都是不正确的，可能会导致程序崩溃或者是产生不正确的结果。如果我们在链接​​ListNode​​​实例的时候错误地更新了​​link_​​​实例变量的话，那么我们就会丢失掉对列表的一部分的访问权限。下面这段代码是一个把我们的​​insert​​方法改成这种错误的例子：

// this code is incorrectvoid LList::insert(size_t i, ItemType x){ ListNode *node; if (i == 0) { head_ = new ListNode(x, head_); } else { node = _find(i - 1); node->link_ = new ListNode(x); // incorrect } size_ += 1;}

基于这段代码，新创建的​​ListNode​​​实例的​​link_​​​实例变量将会被设置为​​NULL​​，因为这是构造函数第二个参数的默认值。而这就会无法访问在新插入的节点之后的那些元素，也就是断开了我们的列表。在C++里，我们将没办法再去访问列表的一部分从而会导致内存泄漏，因此完整地测试C++代码，确保没有内存错误是非常重要的。而在Python里，类似的代码会断开我们的列表，但并不会有内存泄漏，这是因为Python使用了引用计数来进行自己的内存释放管理。

11.5　小结

这一章我们介绍了如何使用指针和动态内存在C++里实现链式结构的相关问题。我们在这里总结了一些重要部分。

11.6　练习

1．判断题

（4）要创建​​LList​​​的副本，我们必须为它所包含的每个​​ListNode​​实例都创建一个单独的副本。（　　）

（5）​​ListNode​​​的​​item_​​实例变量可以是一个指针。（　　）

2．选择题

（1）列表的链式实现（　　）。

a．总是需要比这个列表的数组版本更多的内存

b．总是需要比这个列表的数组版本更少的内存

c．可能需要比列表的数组版本更少的内存，取决于具体的数据类型（两者都存储相同的数据类型的情况下）

d．可能需要比列表的数组版本更多的内存，取决于具体的数据类型（两者都存储相同的数据类型的情况下）

（2）具有n个元素的​​LList​​​的​​copy​​方法的时间复杂度是（　　）。

a．Θ (1)

b．Θ (log2n)

c．Θ (n)

d．Θ (n2)

（3）具有n个元素的​​LList​​的复制方法在最好情况下的时间复杂度是（　　）。

a．Θ (1)

b．Θ (log2n)

c．Θ (n)

d．Θ (n2)

（4）具有n个元素的​​LList​​的析构函数的时间复杂度是（　　）。

a．Θ (1)

b．Θ (log2n)

c．Θ (n)

d．Θ (n2)

（5）具有n个元素的​​LList​​的析构函数在最好情况下的时间复杂度是（　　）。

a．Θ (1)

b．Θ (log2n)

c．Θ (n)

d．Θ (n2)

3．简答题

（1）在第10章里的动态数组​​List​​​类对于有​​n​​个整数的列表来说需要多少的内存？

（2）这一章里的​​LList​​​类对于有​​n​​个整数的列表来说需要多少的内存？

（3）如果需要一个存储整数的列表的话，应该如何确定程序是应该使用动态数组实现的​​List​​​类还是链式实现的​​LList​​类？

（4）如果​​ListNode​​​的​​item_​​实例变量是指向动态分配的内存的指针，那么会有哪些潜在的问题？

（5）为什么在类里面包含一个指向它自己的类型的实例的指针是合法的，但包含自己的类型的实例就是非法的（换句话说，为什么​​ListNode​​​类可以包含一个指向​​ListNode​​​的指针，但不能包含一个​​ListNode​​的实例）？

4．编程练习

（1）通过添加​​tail_​​实例变量和一个外部迭代器类来完成列表的链式实现。之后编写代码来测试所有的列表的方法。这里并没有自动迭代，因此你需要编写一个外部迭代器，从而能够让下面这样的代码调用它：

LList l;LListIterator li;int x;li.init(l);while (li.next(x)) { cout << x << endl;}

（2）编写这样一个列表的链式实现，其中每个列表的节点元素都同时包含着指向列表里的上一个和下一个元素的指针。

（3）C++也支持继承。继承的基本语法是：

class CursorLList : public LList {};

如果要在C++里使用继承的话，那么你还需要学习许多各种各样的知识。但是对于这个练习来说，你只需要知道在派生类的构造函数被执行之前会自动调用基类的构造函数。当派生类的析构函数完成之后，将自动调用基类的析构函数。按照4.6.2小节里的描述用C++来创建一个派生出来的游标列表以及游标类。

（4）用C++实现一个基于节点的二叉搜索树。为这个类提供复制构造函数、赋值运算符以及析构函数。

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。