數據結構中，在單鍊表的第一個結點之前附設一個結點，它沒有直接前驅，稱之為頭結點。
基本介紹
- 中文名：頭結點
- 外文名：head node
簡介,常用方法,作用,
簡介
頭結點的數據域可以不存儲任何信息，頭結點的指針域存儲指向第一個結點的指針（即第一個元素結點的存儲位置）。頭結點的作用是使所有鍊表（包括空表）的頭指針非空，並使對單鍊表的插入、刪除操作不需要區分是否為空表或是否在第一個位置進行，從而與其他位置的插入、刪除操作一致。
常用方法
建立單鍊表的常用方法有兩種。下面以順序存儲為例來敘述。
(1) 頭插法建表
該方法從一個空表開始，讀取數組a中的字元，生成新結點，將讀取的數據存放到新結點的數據域中，然後將新結點插入到當前鍊表的表頭上，直到結束為止。算法如下：
void CreateListF(Snode *&L, ElemType a[], int n)
{ Snode *s; int i;
L = (Snode *) malloc(sizeof(Snode));
L->next = NULL;
for (i=0; i<n;i++)/*改成for (i=n; i>1;i--)可讓節點次序與原數組元素順序相同。
{ s = (Snode *)malloc(sizeof(Snode));
s->data = a[i];
s->next = L->next;
L->next = s;
}
}
(2) 尾插法建表
頭插法建立鍊表雖然算法簡單，但生成的鍊表中結點的次序和原數組元素的順序相反，若希望兩者次序一致，可採用尾插法。該方法是將新結點插到當前鍊表的表尾上，為此必須增加一個尾指針r,使其始終指向當前鍊表的尾結點。算法如下：
void CreateListR(Snode *&L, ElemType a[], int n)
{ Snode *s, *r; int i;
L = (Snode *) malloc(sizeof(Snode));
L->next = NULL;
r = L;
for (i=0; i<n;i++)
{ s = (Snode *)malloc(sizeof(Snode));
s->data = a[i];
r->next = s;
r = s;
}
r-> next = NULL;
}
作用
頭結點是鍊表裡面第一個結點，他的數據域可以不存放任何信息（有時候也會存放鍊表的長度等等信息），他的指針區域存放的是鍊表中第一個數據元素的結點（就是傳說中的首元結點）存放的地址。
1、防止單鍊表是空的而設的.當鍊表為空的時候,帶頭結點的頭指針就指向頭結點.如果當鍊表為空的時候,頭結點的指針域的數值為NULL.
2、是為了方便單鍊表的特殊操作,插入在表頭或者刪除第一個結點.這樣就保持了單鍊表操作的統一性!
3、單鍊表加上頭結點之後，無論單鍊表是否為空，頭指針始終指向頭結點，因此空表和非空表的處理也統一了，方便了單鍊表的操作，也減少了程式的複雜性和出現bug的機會。
4、對單鍊表的多數操作應明確對哪個結點以及該結點的前驅。不帶頭結點的鍊表對首元結點、中間結點分別處理等；而帶頭結點的鍊表因為有頭結點，首元結點、中間結點的操作相同,從而減少分支，使算法變得簡單，流程清晰。對單鍊表進行插入、刪除操作時，如果在首元結點之前插入或刪除的是首元結點，不帶頭結點的單鍊表需改變頭指針的值，在TurboC算法的函式形參表中頭指針一般使用指針的指針(在C++中使用引用&)；而帶頭結點的單鍊表不需改變頭指針的值，函式參數表中頭結點使用指針變數即可，對初學者更易接受。
