您当前的位置:首页 > 计算机 > 编程开发 > VC/VC++

链表的创建和遍历

时间:01-10来源:作者:点击数:

上一节,我们介绍了链表的概念。在这一节,我们将介绍如何用程序来实现一个链表。在具体实现之前,我们先要明确一下我们有哪些任务:

  1. 能够创建一个具有若干个结点的链表。
  2. 能够访问到链表中的每一个结点,即输出每个结点的数据。这种操作称为遍历。
  3. 能够根据数据查找到结点所在的位置。
  4. 能够在链表的任意位置插入一个结点。
  5. 能够在链表的任意位置删除一个结点。
  6. 能够在程序结束前清除整个链表,释放内存空间。

我们知道链表也是动态分配的,虽然每次只分配一个结构变量(结点),但却少不了指向这个结构变量的指针。如果任何一个分配给我们的结构变量失去了指向它的指针,那么这个内存空间将无法释放,就造成了内存泄漏。由于指针还维系着各结点之间关系,指针的丢失造成了结点之间断开,整个链表就此被破坏。

所以,我们要保证每个结点都在我们的控制之内,即我们能够通过各种手段,利用指针访问到链表的任一个结点。这也是我们在所有对链表的操作过程中始终要注意的一点。

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

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

做完了这些分析,我们可以开始着手写这个程序了:(程序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函数创建链表的过程。

程序中showList函数的主要工作有:

①初始化访问指针。

②如果访问指针不为空,则输出当前结点的数据,否则函数结束。

③访问指针向后移动,并重复第二项工作。

注意,虽然上述程序可以运行,但是它没有将内存释放,严格意义上来说,它是一个不完整的程序。

方便获取更多学习、工作、生活信息请关注本站微信公众号城东书院 微信服务号城东书院 微信订阅号
上一篇:链表的查询 下一篇:什么是链表
推荐内容
相关内容
栏目更新
栏目热门