C++教程:链表的创建和遍历

2020-05-23 14:26:50

字体：大中小

来源：转载

供稿：网友

接下来，我们把链表的创建和遍历分析得更加具体化：

由于第一个结点也是动态分配的，因此一个链表始终要有一个指针指向它的表头，否则我们将无法找到这个链表。我们把这个表头指针称为head。
在创建一个多结点的链表时，新的结点总是连接在原链表的尾部的，所以我们必须要有一个指针始终指向链表的尾结点，方便我们操作。我们把这个表尾指针称为pEnd。
每个结点都是动态分配的，每分配好一个结点会返回一个指针。由于head和pEnd已经有了各自的岗位，我们还需要一个指针来接受刚分配好的新结点。我们把这个创建结点的指针称为pS。
在遍历的过程中，需要有一个指针能够灵活动作，指向链表中的任何一个结点，以读取各结点的数据。我们把这个访问指针称为pRead。
我们把创建链表和遍历各自写为一个函数，方便修改和维护。

做完了这些分析，我们可以开始着手写这个程序了：（程序9.6.1）
#include "iostream.h"
struct node//定义结点结构类型
{
char data;//用于存放字符数据
node *next;//用于指向下一个结点（后继结点）
};
node * create();//创建链表的函数，返回表头
void showList(node *head);//遍历链表的函数，参数为表头
int main()
{
node *head;
head=create();//以head为表头创建一个链表
showList(head);//遍历以head为表头的链表
return 0;
}
node * create()
{
node *head=NULL;//表头指针，一开始没有任何结点，所以为NULL
node *pEnd=head;//表为指针，一开始没有任何结点，所以指向表头
node *pS;//创建新结点时使用的指针
char temp;//用于存放从键盘输入的字符
cout <<"Please input a string end with '#':" <<endl;
do//循环至少运行一次
{
cin >>temp;
if (temp!='#')//如果输入的字符不是结尾符#，则建立新结点
{
pS=new node;//创建新结点
pS->data=temp;//新结点的数据为temp
pS->next=NULL;//新结点将成为表尾，所以next为NULL
if (head==NULL)//如果链表还没有任何结点存在
{
head=pS;//则表头指针指向这个新结点
}
else//否则
{
pEnd->next=pS;//把这个新结点连接在表尾
}
pEnd=pS;//这个新结点成为了新的表尾
}
}
while (temp!='#');//一旦输入了结尾符，则跳出循环
return head;//返回表头指针
}
void showList(node *head)
{
node *pRead=head;//访问指针一开始指向表头
cout <<"The data of the link list are:" <<endl;
while (pRead!=NULL)//当访问指针存在时（即没有达到表尾之后）
{
cout <<pRead->data;//输出当前访问结点的数据
pRead=pRead->next;//访问指针向后移动
}
cout <<endl;
}
运行结果：
Please input a string end with '#':
Tomato#
The data of the link list are:
Tomato

这个程序的功能是把输入的字符串保存到链表中，然后把它输出。从程序中我们可以看出，create函数的主要工作有：
①做好表头表尾等指针的初始化。
②反复测试输入的数据是否有效，如果有效则新建结点，并做好该结点的赋值工作。将新建结点与原来的链表连接，如果原链表没有结点，则与表头连接。
③返回表头指针。
下图9.6.1给出了create函数创建链表的过程。