在链表中使用头结点与尾指针

版权声明：本文为博主原创文章，未经博主允许不得转载。

1 头结点

首先，不要被以下三个词组弄混了：

链表头：数据内容为第一个元素的结点。

头指针：指向头结点元素的指针。

头结点：数据内容无效，其指针是头指针。

一句话描述为：头指针是指向头结点的指针，头结点是指向链表头的结点。

对于一个链表来说，头指针是一定存在的，是访问链表的入口，如果没有头指针则无法对其进行访问；链表头对于非空表来说是一定存在的，非空表则不存在。

注意到，如果说我们不引入头结点的话，将出现操作不统一的问题:

1、对于元素访问的或者结点的引用不统一。假设pHead是头指针，pNode是指向其他链表结点的指针。此时头指针指向链表头。

2、对于空表与非空表的判定操作不统一。假设pHead是头指针，pNode是指向其他链表结点的指针。此时头指针指向链表头。

[cpp] view%20plain copy print?pHead == NULL; //对于空表的判定  pNode->next == NULL; //对于非空表是否访问到末尾的判定  头结点的引入可以很好地解决这两个问题。首先来看看带头结点的三种链表形式。

单链表：

双链表：

循环双链表（循环单链表类同）

访问形式统一为：

[cpp] view plain copy print?p->next->Element; //统一后的元素访问  p->next == NULL; //统一后的末尾判定  个人来讲，倾向于在链表中引入头结点。虽然多出了一块儿存储空间，但是相对于大链表来说，这个空间是微不足道的。好处是使所有的操作保持一致性代码的编写也更为简单。

引申：在队列的数据结构中，%20一种实现方法是队列的头指针（或者标号）为对头的前一个位置。这种方式也可以看作为头结点的一种扩展方式。

2%20尾指针

另外一种链表的技巧是使用尾指针。

尾指针是相对于头指针而言的，形式与头指针相同，内容只想链表的最后一个节点。

通常，链表的插入语删除操作都是在链表头或者链表尾进行。如果只保存一个头指针的话，要在链表尾操作时必须先遍历整个表，增加了时间复杂度，如果能再保存一个尾指针，则可以立即找到链表尾，时间复杂度降为O(1)。

在单向循环链表中，时常值保存一个尾指针，因为尾指针的下一个节点即是头结点。这样便可以方便地在首尾进行操作。

最后，提供一个带头结点和尾指针的单链表插入实现参考代码。

[cpp] view plain copy print?#include <stdio.h>  #include <stdlib.h>    #define ElementType int    struct ListNode  {      ElementType Element;      struct ListNode *Next;  };    typedef struct  {      struct ListNode *Head;      struct ListNode *Tail;  } List, *pList;    int InsertTail( ElementType X, pList L ) //尾部插入元素  {      struct ListNode *newP;        if ( (newP = malloc(sizeof(struct ListNode))) == NULL )      {          perror("OUT OF SPACE!");          return -1;      }        newP->Element = X;      newP->Next = NULL;        L->Tail->Next = newP;      L->Tail = newP;        if ( L->Head->Next == NULL)      {          L->Head->Next = L->Tail;      }        return 0;  }    int InsertHead( ElementType X, pList L ) //头部插入元素  {      struct ListNode *newP;        if ( (newP = malloc(sizeof(struct ListNode))) == NULL )      {          perror("OUT OF SPACE!");          return -1;      }        newP->Element = X;      newP->Next = L->Head->Next;      L->Head->Next = newP;        return 0;  }          int main()  {      pList L;        if ( (L = malloc(sizeof(List))) == NULL )      {          perror("OUT OF SPACE!");          return -1;      }        if ( (L->Head = malloc(sizeof(struct ListNode))) == NULL )      {          perror("OUT OF SPACE!");          return -1;      }        L->Head->Next = NULL; //初始化      L->Tail = L->Head;            InsertTail( 10, L );      InsertTail( 11, L );      InsertTail( 12, L ); //三次尾部插入      InsertHead( 13, L );      InsertHead( 14, L ); //两次头部插入      InsertTail( 15, L );      InsertTail( 16, L ); //两次尾部插入        while( L->Head->Next != NULL ) //遍历输出      {          printf("%d ", L->Head->Next->Element);          L->Head = L->Head->Next;      }        puts("");        return 0;  }  

运行结果：

[cpp] view%20plain copy print?jimmy@MyPet:~/code/learnc$ make  gcc -Wall -g -o test test.c -std=c99  jimmy@MyPet:~/code/learnc$ ./test   14 13 10 11 12 15 16  

（完）

转载：http://blog.csdn.net/jmy5945hh/article/details/7574857