頭結點

頭結點

數據結構中,在單鍊表的第一個結點之前附設一個結點,它沒有直接前驅,稱之為頭結點。

簡介

頭結點的數據域可以不存儲任何信息,頭結點的指針域存儲指向第一個結點的指針(即第一個元素結點的存儲位置)。頭結點的作用是使所有鍊表(包括空表)的頭指針非空,並使對單鍊表的插入、刪除操作不需要區分是否為空表或是否在第一個位置進行,從而與其他位置的插入、刪除操作一致。

常用方法

建立單鍊表的常用方法有兩種。下面以順序存儲為例來敘述。

(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++中使用引用&);而帶頭結點的單鍊表不需改變頭指針的值,函式參數表中頭結點使用指針變數即可,對初學者更易接受。

相關詞條

熱門詞條

聯絡我們