链表入门指南

下载演示项目 - 7 Kb

什么是链表？

链表本质上是一个以列表形式存储的对象集合。在某些方面，它可以与数组相提并论，但其存储列表的方法却大相径庭，因此链表在优缺点方面与数组有所不同。Microsoft Foundation Classes (或 MFC) 中已经提供了一个已编程的链表供您使用。这是一个很好的列表实现，因此我将介绍如何使用它。但在此之前，我将先讨论链表的工作原理、其优点和缺点。

它是如何工作的？

链表是围绕指针的概念工作的，因此最好对该主题已有扎实的了解。基本原理是，对于您想要存储在列表中的每个元素，您都需要附加一个或两个额外的变量。这些变量指向列表中相邻的元素，特别是下一个元素，通常还有前一个元素。下面是以图示形式显示的列表结构，其中显示了附加了“下一个”和“上一个”指针的元素

正如该图所示，从列表中的每个元素，我们可以获得指向下一个和上一个元素的指针。我们还可以识别列表的开始和结束，因为 pPrev 或 pNext 元素将为 NULL (0)。

通过操作pNext 和 pPrev 值，可以轻松地添加、删除和遍历元素。这种布局为我们提供了以下优势

• 可以快速地从头到尾遍历列表
• 可以快速地在开始和结束处添加元素（或节点，它们通常这样称呼）。
• 可以快速地在任何位置插入元素。

然而，主要缺点是，由于您只能从一个节点移到下一个或上一个节点，因此查找特定元素可能耗时，因为这需要搜索整个列表。

现在您已经了解了链表的基本工作原理，接下来我将向您展示如何使用 MFC 中内置的列表功能。

使用 CList 类

CList 类提供了一个链接列表的实现，该实现非常适合大多数任务，并且可以在需要时进行自定义。与 MFC 中的许多类不同，CList 是一个模板类，这使得它可以处理您想要列出的任何内容，包括整数、字符串、类等。让我们创建一个整数列表

CList<int, int> MyListOfNumbers;

现在，<int, int> 部分告诉编译器您想要创建一个什么类型的列表。第一个模板参数（第一个 int）告诉编译器我们想要一个 int 列表，第二个告诉编译器我们想要将元素作为 int 传递给 CList。通常，这两个参数将相同，除非您希望传递和接收数据的引用。如果我们想创建一个 CString 列表，可以使用以下代码，这可以避免不必要的复制

CList<CString, CString&> MyListOfStrings;

对于 CString 来说，这不会有太大区别，但大多数其他类或类型都会从中受益。列表类还可以存储对象的指针，如本例所示

CList<CMyObject *, CMyObject *> MyListOfObjects;

所有这些示例都设置了列表，并准备好存储元素。那么我们如何开始向列表中添加元素呢？在本文中，我将使用整数列表作为示例。

添加元素

添加元素非常简单，有两种方法：在列表开头添加元素，以及在列表末尾添加元素。首先，我将演示如何在列表开头放置一个元素。为此，我们使用 AddHead 函数，该函数接受一个参数：您想添加的元素。与 CList 类中的所有函数一样，您必须使用在创建列表时指定的相同类型的元素，或者，如果是类，则必须使用该类派生的任何类型。虽然不推荐，但您可以使用 void * 列表存储几乎任何内容，它可以存储指向任何类型变量的指针。

总之，假设我们有一个数字 15，我们想将其添加到数字列表的开头

ListOfNumbers.AddHead(15);

是不是很简单？如果您想将数字 15 添加到列表末尾，方法几乎相同

ListOfNumbers.AddTail(15);

现在我们将数据放入列表中，如何遍历它并检索信息？请继续阅读。

遍历列表

遍历列表的最佳方法是使用 while 循环。CList 类使用一种称为 POSITION 的变量类型来存储您在列表中的位置。不必担心此变量的详细信息，只需知道它随时存储我们在列表中的位置，并且还可以用于标记列表中的特定点。实际上，POSITION 变量就是 MFC 如何将 pNext 和 pPrev 变量添加到您的数据中的。

要获取列表中第一个元素的 `POSITION`，我们使用 GetHeadPosition() 函数。这可以如下使用

POSITION pos = MyList.GetHeadPosition();

要获取列表中最后一个元素的 `POSITION`，我们使用 GetTailPosition() 函数，如下所示

POSITION pos = MyList.GetTailPosition(); 

如您所见，这两个函数都不带参数，并返回一个 POSITION 变量。现在我们有了 `POSITION` 变量，可以将其传递给 GetNext 和 GetPrev 函数。这些函数都接受一个 POSITION，返回它指向的元素，并将 POSITION 变量设置为下一个或上一个元素。如果您使用 GetNext 函数并且处于列表末尾，或者使用 GetPrev 函数并且处于列表开头，您的 POSITION 变量将设置为 NULL，以告知您无法继续遍历，因为您已到达列表末尾。这很方便，因为它意味着我们可以说“只要 POSITION 不是 NULL，就继续遍历列表”。在实际代码中，可以这样做

POSITION pos = MyIntList.GetHeadPosition();

while (pos)
{
	int Number = MyIntList.GetNext(pos);
	// do something with the number

}

// end of the list has been reached, so control continues to here.

因此，继续我们的数字主题，我们可以将链表中所有元素相加，如下所示

POSITION pos = MyIntList.GetHeadPosition();
int Total;

while (pos)
{
	int Number = MyIntList.GetNext(pos);
	Total = Total + Number;
}

// use the CString class to make a string using the number, a bit like printf:

CString Str;
Str.Format(“Total of the numbers = %d”, Total);
AfxMessageBox(Str);

我们还可以使用 GetHead 和 GetTail 函数来获取列表的头部和尾部。这些函数返回列表头部或尾部的实际元素，而不是代表它们的 POSITION，其用法如下所示

FirstNumber = MyIntList.GetHead();
LastNumber = MyIntList.GetTail();

FirstNumber = MyIntList.GetHead();
LastNumber = MyIntList.GetTail();

获取元素的最后一种方法是使用 GetAt 函数。这与 GetNext 和 GetPrev 函数类似，但它获取指定位置的项，而不会更改传递给它的 POSITION 变量。换句话说，它用于在不改变 `POSITION` 的情况下获取给定位置的元素。其用法如下

// MyBookmark is a POSITION variable kept from earilier:

int Number = MyIntList.GetAt(MyBookmark);

查找位置

有时您需要列表中某个项的 POSITION 变量。我们可以反转过程，通过给定元素本身来查找该项的 POSITION，使用 Find 函数。此函数接受一个元素和一个要开始的 POSITION，并返回您传入的元素的 POSITION。传递给函数的 POSITION（startAfter 变量）用于告诉列表从哪里开始搜索元素，因此，如果存在多个同名元素，您可以告诉列表从列表中的特定距离开始搜索。这意味着您可以跳过几个元素，只获取您想要的那个。如果您只想从列表开头开始搜索，可以将 `startAfter` 值设置为 NULL，或者根本不传递它。

以下是 Find 函数的示例

POSITION MyBookmark = MyIntList.Find(15);

现在，假设您想在列表中查找数字 15 的第二个出现。您可以将 MyBookmark 位置作为 `startAfter` 值传递给 Find 函数，如下所示

POSITION SecondFifteen = MyIntList.Find(15, MyBookmark);

这将返回列表中数字 15 的**第二个**出现。这个系统运行得很好，但是如果您想查找列表中的第五个元素，而不知道它的 POSITION 或值，该怎么办？简单的解决方案是使用 FindIndex 函数。它根据索引返回元素的 `POSITION`。但是，需要注意的是，此索引是从零开始的，这意味着计算机将列表中的第一个元素计为元素 0，而不是 1。因此，如果您想查找列表中的第十个元素，则必须将 9 作为索引传递给 FindIndex 函数。

以下是使用 FindIndex 函数的示例

POSITION pos = MyIntList.FindIndex(3);

这会找到列表中的**第四个**元素——再次体现了零基索引。

插入元素

可以在列表的任何给定位置插入元素。CList 类为此提供了两个函数：InsertBefore 函数和 InsertAfter 函数。这些函数接受一个 POSITION 作为参数，以及要在该位置之前或之后添加的元素。如果您试图使列表保持排序状态，这可能很有用，但您必须小心将新元素传递给正确的函数。

这两个函数都将已存在元素的 POSITION 作为参数，然后是要添加的元素。POSITION 值可以来自 GetHeadPosition、GetTailPosition、GetNext、GetPrev、Find 或 FindIndex 函数中的任何一个。回到我们的数字列表示例，假设您想将一个新数字 (15) 添加到列表中的第三个元素。方法如下

MyIntList.InsertBefore(MyIntList.FindIndex(2), 15);
// ~ OR ~

MyIntList.InsertAfter(MyIntList.FindIndex(1), 15);

不要忘记 FindIndex 函数中的零基索引——这就是为什么在调用此函数时，我们需要将元素编号 3 称为元素 2，将元素编号 2 称为元素 1。

删除元素

一旦我们将元素放入列表中，稍后可能需要删除它们。这尤其必要，如果您有一个指针列表，因为在程序结束之前需要删除它们。CList 类非常充分地支持这一点，提供了四个有助于从列表中删除元素的函数。

最显而易见的删除函数是 RemoveHead 和 RemoveTail。它们的作用正如其名称所示；它们删除列表的头部或尾部节点。这些函数有用之处在于它们实际上会返回元素，因此如果您愿意，可以在从列表中删除元素的同时获取该元素。以下是一个释放指针列表所占用的所有内存的示例

while (!MyPointerList.IsEmpty())
	delete MyPointerList.RemoveHead();

显然，您可以直接删除头部或尾部而不实际获取被删除的元素，如下所示

MyList.RemoveTail();

如果我们改用 RemoveHead 函数，结果将相同。

CList 类提供的第三个函数是 RemoveAt 函数。它删除列表中给定位置的元素。如果您想删除特定元素，此函数很有用。它可以与 Find 和 FindIndex 函数结合使用，以帮助您删除特定元素。它只需将一个 POSITION 作为参数，删除元素，然后将其返回给您。其用法如下

MyIntList.RemoveAt(MyBookmarkedPosition);

如果您想删除列表中数字 15 的第一个出现，您将使用以下代码

MyIntList.RemoveAt(MyIntList.Find(15));

此函数有许多可能性。请记住，如果您有一个指针列表，当您完成使用它们后，必须释放它们占用的内存，因为 Remove 函数不会为您释放内存。

删除元素的最后一种方法是最粗暴的方法；RemoveAll 函数。它不接受任何参数，用于删除列表中的所有元素。此函数不适用于指针列表，因为您将不再有方法释放先前在列表中的元素的已分配内存。而是，请使用我上面概述的释放列表中内存的方法。

SetAt 函数

此函数可能非常有用——它用于替换给定位置的元素。它接受两个参数：要替换的 POSITION，以及要插入的新元素。其工作原理如下

MyIntList.SetAt(MyBookmarkedPosition, 23);

这将用数字 23 替换存储在 MyBookmarkedPosition 变量所持有的位置的值。下面的示例，同样基于数字列表，演示了如何将数字 15 的所有出现替换为数字 25

POSITION pos = NULL;
while (pos = MyIntList.Find(15))
	MyIntList.SetAt(pos, 25);

状态信息

准备好列表后，您可能稍后想知道列表中有多少项。有两种“状态”函数旨在提供帮助。第一个是 IsEmpty，它告诉我们列表是否包含任何信息。它返回 TRUE 或 FALSE。它可以在许多情况下使用，其中一种是确定您是否已完成释放列表中存储的信息。例如

while (!MyObjectPointerList.IsEmpty())
{
	CMyObject *head = MyObjectPointerList.RemoveHead();
	delete head;	// free the memory allocated to the element in the list

}

这可以以更简洁的形式编写为

while (!MyObjectPointersList.IsEmpty())
	delete MyObjectPointerList.RemoveHead();

第二个提供列表状态信息的函数是 GetCount 函数。它将返回一个描述列表中任何时候有多少项的值。再次回到我们的整数列表，假设它是已排序的，我们可以使用此函数来查找列表中存储的数字的中位数。中位数是在一系列数字中中间数字的数学术语，或者，如果系列有奇数个元素，则是中间两个数字的平均值。以下是一些执行此操作的代码，用于我们的列表

int nItems = MyIntList.GetCount();
int nMedian = 0;

if (nItems % 2 == 1) // if there is an odd number of items in the list

{
	nItems = (nItems + 1) / 2; // get the central item

	nMedian = MyIntList.GetAt(MyIntList.FindIndex(nItems));
}
else
{
	nItems = nItems / 2;

	// get the middle two items:

	nMedian = MyIntList.GetAt(MyIntList.FindIndex(nItems));
	nMedian = nMedian + MyIntList.GetAt(MyIntList.FindIndex(nItems + 1));

	// now average the two:

	nMedian = nMedian / 2;
}

这构成了一些有趣的代码，所以您可能想自己看看，也许在调试器中。

摘要

以下是本文涵盖内容的概述

1. 链表用于在一个地方存储任意数量的项目（元素）。
2. 链表提供快速的插入和删除功能，但随机访问速度较慢。
3. MFC CList 类是一个已为您编写好的链表系统。
4. 在 CList 类中，我们可以使用 AddHead 和 AddTail 函数在列表的开头和结尾添加元素。
5. POSITION 变量用于存储链表中的一个位置。
6. GetNext 和 GetPrev 函数允许我们遍历列表。
7. GetAt 函数返回列表中给定 POSITION 处的元素。
8. InsertBefore 和 InsertAfter 函数可用于在列表的任何给定位置插入元素。
9. Find 和 FindIndex 函数可用于在给定元素的零基索引或元素本身的情况下获取元素的 POSITION。
10. RemoveHead 和 RemoveTail 函数用于删除列表的第一个或最后一个元素。
11. RemoveAt 函数用于删除任何给定位置的元素。
12. RemoveAll 函数用于删除列表中的所有元素。
13. IsEmpty 和 GetCount 函数用于确定列表中有多少项。
14. SetAt 函数替换给定 POSITION 处的元素。

演示程序使用了一个支持 MFC 的基于控制台的应用程序。我之所以这样做，是为了避免处理窗口消息等复杂性干扰您对基本代码基础的理解。它编写时省略了 C++ 的许多特性，以强调链表和 CList 类。

链表就讲到这里！