版權聲明：本文為博主原創文章，未經博主允許不得轉載。

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