原创 C++学习日志 -- 六、 关于链表

链表是利用结构指针连接起来的结构变量，每一个结构变量就称为链表的结点（英文名字为node）。与数组相似，链表也可以用来存储一系列的数据，它也是电脑存储数据的基本结构之一。即然链表与数组相似那就存在着区别了，简单的说链表比数组更灵活一些，数据只能分配连续的空间，而链表可以在程序运行时根据实际需要一个个分配堆内在空间，并且用它的指针把这一系列的空间串连起来，这样的好处就是可以利用指针对整个链表进行管理控制。下面写个小程序学习一下链表：

/*

 * Copyright (c) 2011,深圳XXXX有限公司

 * All rights reserved. T-INDENT: 15pt" class=MsoListParagraph> * 文件名称：main.c

 * 文件标识：lesson9-4-main.cpp

 * 摘    要：学习链表

 * 

 * 当前版本：1.1

 * 作    者：懒猫爱飞

 * 完成日期：2011年7月26日

 *

 * 取代版本：无

 * 原作者  ：

 * 完成日期：

*/

 

#include <iostream.h>

 

struct node       // 定义结点结构类型

{

  char dat;     // 用于存放字符数据

  node *next;   // 用于指向下一个结点（后继结点）              

};

 

node *Creat(void);         // 创建链表函数，返回表头

void ShowList(node *head); // 遍历链表的函数，参数为表头

 

/*

 * 函数名称：int main()

 * 函数功能：主函数，调度功能

 * 入口参数：无

 * 出口参数：无

 * 备    注：无

*/

int main()

{

  node *head = NULL;

 

  head = Creat(); // 以head为表头创建一个链表

  ShowList(head); // 遍历链表

 

  return 0;

}

/*

 * 函数名称：node *Creat(void)

 * 函数功能：创建链表函数，返回表头

 * 入口参数：无

 * 出口参数：无

 * 备    注：无

*/

node *Creat()

{

  node *head = NULL; // 表头指针，初始化时没有指向任何结点所以为空

  node *pEnd = head; // 表尾指针，初始化时指向表头

  node *pS = NULL;   // 创建新结点时使用的指针

  char temp = 0;     // 用于存放键盘输入的字符

 

  cout << "Please input a String end with # " << endl;

  do{

    cin >> temp;

    if(temp != '#')   // 如果输入的字符不是"#",则建立新的结点

    {

       pS = new node;   // 创建新的结点

       pS->dat = temp;  // 新结点的数据为temp

       pS->next = NULL; // 新结点成为表尾，所以next为空

       if(head == NULL)

       {

             head = pS;    // 如果表头还没有结点，则表头指针指向这个新结点

       }

       else

       {

             pEnd->next = pS; // 否则将这个新结点连接到表尾

       }

 

       pEnd = pS; // 这个结点成为了新的表尾

 

    }

 

  }while(temp != '#'); // 一旦输入的“#”则跳出循环

 

  return head;

}      

/*

 * 函数名称：void ShowList(node *head)

 * 函数功能：遍历链表

 * 入口参数：node *head -- 表头指针

 * 出口参数：无

 * 备    注：无

*/

void ShowList(node *head)

{

  node *pRead = head; // 访问指针一开始指向表头

  cout << "The data of the link list are: " << endl;

 

  while(pRead != NULL)       // 在没有到达表尾时

  {

       cout << pRead->dat;    // 输出当前结点的数据

       pRead = pRead->next;   // 访问指针向后移动

  }

  cout << endl;

 

}

链表的内存是动态分布的，虽然每次只分配一个结构变量（结点），但却少不了指向这个结构变量的指针，如果任何一个分配给我们的结构变量失去了指向它的指针，那么这个内存空间将无法释放，这样就会导致内存泄漏，由于指针维系着各结点之间的关系，指针的丢失会造成结点之间的断开，这样就是导致整个链表被破坏。上面一小段程序只是测试之用，准确的说它不是一个完好的程序，因为没有把内存释放掉。有个链表，就有可能要对链表中的数据进行查询，下成写段小程序进行链表的查询：

/*

 * 函数名称：void ShowList(node *head)

 * 函数功能：链表的查询

 * 入口参数：node *head -- 表头

 *           char KeyWord -- 查询的关键字

 * 出口参数：无

 * 备    注：无

*/

node *Search(node *head,char KeyWord)

{

  node *pRead = head;

  while(pRead != NULL) // 采用与遍历类似的方法，当访问指针没有到达表尾之后

  {

       if(pRead->dat == KeyWord)  // 如果当前结点的值与所查询的值相符

       {

             return pRead;          // 返回当前指针

       }

       pRead = pRead->next;       // 如果不符，则指向下一个节点

  }

  return NULL;                   // 如果没查找到，则返回指针

}

会查询数据，但要从该数据处插入新的数据怎么办，当然那就需要一个插入链表的函数，所以插入函数，就需在先将链表断开，然后将新数据插入后再链接起来。下面写一下插入函数：

/*

 * 函数名称：void Insert(node *head,char KeyWord,char newdata)

 * 函数功能：插入新数据

 * 入口参数：node *head -- 表头

 *           char KeyWord -- 查询的关键字

 *           char newdata -- 新插入的数据

 * 出口参数：无

 * 备    注：无

*/

void Insert(node *head,char KeyWord,char newdata)

{

  node *newnode = new node; // 新建结点

 

  newnode->dat = newdata;   // newdata是新结点的数据

  node *pGuard = Search(head,KeyWord); // pGuard 是插入结点前的位置指针

 

  if((head == NULL)||(pGuard == NULL))  // 如果链表中没有结点或找不到关键字结点

  {

       newnode->next = head; // 连链表

       head = newnode;       // 断开链表

  }

    else

  {

       newnode->next = pGuard->next;

       pGuard->next = newnode;

  }

}

关于插入节点的功能分析:

1、必须知道对哪个链表进行操作，所以表头指针head必须知道

2、为了确定插入位置，插入位置前的结点打针pGuard必须知道

3、需要用一个newnode指针来接受新建的指针

4、如果插入的位置是表头，由于操作的是表头指针而不是一个结点，所以要特殊处理

5、插入结点的过程中，始终要保持所有的结点都在我们的控制范围之内，保证链表的完整性。为了达到这一点要求，就需要采用先连后断的方式，先把新结点和它的后继结点连接起来，再把插入之前的结点与后继结点断开，并与新结点连结。

删除链表

与插入数据类似，数组为了保持其顺序存储特性，在删除某个数据时，其后数据都要依次前移。而链表中结点的删除只要对结点周围小范围的操作就可以了。与建立链表类似，删除链表需要分析以下问题：

1、因为要知道是对哪个链表操作，所以要知道表头

2、需要建立一个链表指针指向待删除指针的前身指针

3、由于对待删除结点作内在释放，所以需要有一个指针指向待删除指针

4、如果待删除结点为头结点，则要操作表头，就要做特殊处理

5、在删除链表的过程中，仍然要始终保持所有的结点都在控制范围内，保证链表的完整性

6、如果链表没有结点或找不到待删除结点，则应给出提示信息

下面写个小程序测试一下：

 /*

 * 函数名称：void Delete(node* &head,char KeyWord) 

 * 函数功能：删除数据

 * 入口参数：node *head -- 表头

 *           char KeyWord -- 要删除的关键字

 * 出口参数：无

 * 备    注：无

*/

void Delete(node* &head,char KeyWord) 

{

  if(head != NULL) // 如果链表没有结点，就直接输出提示

  {

       node *p;

       node *pGuard = head;      // 初始化pGuard指针

       if(head ->dat == KeyWord)

       {

             p = head;             // 头结点是待删除的结点

             head = head->next;    // 先连接

             delete p;             // 再断开

             cout << "The delete node is : " << KeyWord << endl;

             return ;

       }

       else

       {

             while(pGuard->next != NULL)     // 当pGuard没有达到队尾时

             {

                  if(pGuard->dat == KeyWord)  // 如果pGuard的结点符合关键字

                  {

                        p = pGuard->next;       // pGuard后继结点是待删除结点

                        p->next = pGuard->next; // 先连

                        delete p;               // 后断

                        cout << "The delete node is : " << KeyWord << endl;

                        return;

                  }

                  pGuard = pGuard->next;       // pGuard指针后移

             }

       }

  }

  cout << "The keyword node is not found or the link list is empty!" << endl; // 输出提示信息

} 

清除链表

链表的结点是动态分布的，如果在程序结束之前不释放内存，就会造成内存泄漏，所以一定要写一个清除链表的函数，想写清除函数，必须知道要清的是哪个链表，也即知道表头，所以也要用一个指针指向待删除的结点，当然清除链表仍然需要先连后断，即把表头指向头结点的后继，再删除结点。清除函数如下：

/*

 * 函数名称：void Destory(node * &head)

 * 函数功能：清除列表        

 * 入口参数：node *head -- 表头

 * 出口参数：无

 * 备    注：无

*/

void Destory(node * &head)

{

  node *p;

  while(head != NULL) // 当还有头结点存在时

  {

       p = head;       // 头结点是待删除的结点

       head = head->next; // 先连

       delete head;       // 后断

  }

  cout << "This list has been deleted!" << endl;

}     

关于链表的学习总结：

1、链表与数组类似可以用来存储数据

2、数组存储不需要指针，存储空间相对较小，使用数组下标能很快找到第n个元素

3、数组存储的缺点是存储空间灵活性小，容易造成存储空间浪费，另外插入删除元素相对麻烦

4、链表存储相对灵活，不会浪费，插入删除结点不影响前后结点

5、各结点需要指针来连接前后结点，无法很快定位元素。

 

嗯，好了，该去洗碗了，等下接着学习^_^

哦，最后再吼一下懒猫的口号：

 

每天进步一点点，开心多一点^_^