C++语言程序设计

8.5.2 链表的遍历和查找
下面我们看一个简单的链表操作函数Length()，该函数计算链表中结点的个数。
//给定链表的头指针，计算并返回链表结点的个数
int Length(node* head)
{
node* current = head;
int count = 0;
while (current != NULL) {
count++;
current = current->next;
}
return count;
}
计算链表结点个数时，该函数使用了循环语句，这也是对链表操作中常用的方法。上面的函数是用while循环语句，也可以用下面的for循环语句替代：
for (current = head; current != NULL; current = current->next)
{ … }
Length()函数有下面几个特点：
（1） current是一个局部指针变量，它最初与head指向相同的结点。当函数返回后，它被自动释放，但链表结点依然在堆内存中。
（2） 能够适应空链表的情形，此时current=head=NULL，循环体中的语句不会执行。
（3） 循环体中的语句"current = current->next;"，使局部指针current移向链表的下一个结点。当到达最后一个结点时，执行 "current = current->next; "语句后，current为NULL。
下面的程序是调用Length()函数的实例，先调用BuildOneTwoThree()函数创建链表，然后调用Length()函数计算链表结点的个数：
void LengthTest()
{
node* myList = BuildOneTwoThree();
int len = Length(myList);
// len的结果为3
}
我们可以用与Length()函数类似的方法查找链表中的某一个结点。
//给定链表的头指针和待查结点数据，返回查到的结点的指针
node* Find(node* head，int data)
{
node* current = head;
while (current!=NULL)
if(current->data == data) break;
else current = current->next;
return current;
}
Find()函数的功能是：输入链表头结点head和待查结点数据data，如果某一个结点的数据与data相等，则返回该结点的指针；如果查完每一个结点也没有找到数据与data相等的结点，则返回空指针。
需要注意的是：Find函数也可以写成下面的形式。
//给定链表的头指针和待查结点数据，返回查到的结点的指针
node* Find(node* head，int data)
{
node* current = head;
while (current!=NULL&& current->data == data)
current = current->next;
return current;
}
但把while的条件"current!=NULL&& current->data == data"写成" current->data == data &&current!=NULL"的形式，则Find函数可能会出现运行错误。这是因为：如果链表的最后一个结点，仍然不是要找的结点，则到下一次循环时current为NULL，再进行条件判断时，前者current!=NULL为真，而不再作current->data == data的判断，循环便结束；而后者在作current->data == data判断时就会导致程序崩溃。