-
頭結點
鎖定
- 中文名
- 頭結點
- 外文名
- 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、是為了方便單鏈表的特殊操作,插入在表頭或者刪除第一個結點.這樣就保持了單鏈表操作的統一性!
4、對單鏈表的多數操作應明確對哪個結點以及該結點的前驅。不帶頭結點的鏈表對首元結點、中間結點分別處理等；而帶頭結點的鏈表因為有頭結點，首元結點、中間結點的操作相同,從而減少分支，使算法變得簡單，流程清晰。對單鏈表進行插入、刪除操作時，如果在首元結點之前插入或刪除的是首元結點，不帶頭結點的單鏈表需改變頭指針的值，在TurboC算法的函數形參表中頭指針一般使用指針的指針(在C++中使用引用&)；而帶頭結點的單鏈表不需改變頭指針的值，函數參數表中頭結點使用指針變量即可，對初學者更易接受。
