頭結點
頭結點
頭結點的數據域可以不存儲任何信息，頭結點的指針域存儲指向第一個結點的指針（即第一個元素結點的存儲位置）。頭結點的作用是使所有鏈表（包括空表）的頭指針非空，並使對單鏈表的插入、刪除操作不需要區分是否為空表或是否在第一個位置進行，從而與其他位置的插入、刪除操作一致。
建立單鏈表的常用方法有兩種。下面以順序存儲為例來敘述。
(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; i1;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
{ s = (Snode *)malloc(sizeof(Snode));
s->data = a[i];
r->next = s;
r = s;
}
r-> next = NULL;
}
1、防止單鏈表是空的而設的，當鏈表為空的時候，帶頭結點的頭指針就指向頭結點。如果當鏈表為空的時候，頭結點的指針域的數值為NULL。
2、是為了方便單鏈表的特殊操作，插入在表頭或者刪除第一個結點，這樣就保持了單鏈表操作的統一性。
3、單鏈表加上頭結點之後，無論單鏈表是否為空，頭指針始終指向頭結點，因此空表和非空表的處理也統一了，方便了單鏈表的操作，也減少了程序的複雜性和出現bug的機會。
基本信息
- 中文名
- 頭結點
- 外文名
- head node
目錄