我在之前一篇博客《C語言實現單鏈表（不帶頭結點）的基本操作》中具體實現了不帶頭結點的單鏈表的11種操作：如計算鏈表長度、初始化、創建鏈表、清空鏈表等等。但是在實際使用中，帶頭結點的單鏈表往往比不帶頭結點的單鏈表用的更多，使用也更為方便。因為不用單獨考慮第一個節點的情況了，第一個節點和其他後續節點的處理全都一樣了，簡化操作。這篇博客將會來實現帶頭結點的單鏈表的11種操作。
（1）定義帶頭結點單鏈表的節點類型
typedef int elemType;
typedef struct NodeList{
int element;
struct NodeList *next;
}Node;
//1.初始化帶頭結點的單鏈表
void InitialList(Node **pNode){
//個人建議每一次malloc分配內存空間後，都要進行判斷分配是否成功，也即判斷是否為空；
//此時的這個pNode就是一個頭結點；
//初始化成功後，其實相當於是一個正常的鏈表了；
*pNode = (Node *)malloc(sizeof(Node));
if (*pNode == NULL) {
printf("%s函數執行，內存分配失敗，初始化單鏈表失敗",__FUNCTION__);
}else{
(*pNode)->next = NULL;
printf("%s函數執行，帶頭結點的單鏈表初始化完成\n",__FUNCTION__);
}
}
（3）尾插法創建帶頭結點的單鏈表
//2.創建帶頭結點的單鏈表
void CreateList(Node *pNode){
/**
* 就算一開始輸入的數字小於等於0，帶頭結點的單鏈表都是會創建成功的，只是這個單鏈表為空而已，也就是裡面除了頭結點就沒有其他節點了。
*/
Node *pInsert;
Node *pMove;
pInsert = (Node *)malloc(sizeof(Node));//需要檢測分配內存是否成功 pInsert == NULL ?
memset(pInsert, 0, sizeof(Node));
pInsert->next = NULL;
scanf("%d",&(pInsert->element));
pMove = pNode;
while (pInsert->element > 0) {
pMove->next = pInsert;
pMove = pInsert;
pInsert = (Node *)malloc(sizeof(Node)); //需要檢測分配內存是否成功 pInsert == NULL ?
memset(pInsert, 0, sizeof(Node));
pInsert->next = NULL;
scanf("%d",&(pInsert->element));
}
printf("%s函數執行,帶頭結點的單鏈表創建成功\n",__FUNCTION__);
}
（4）打印帶頭結點的單鏈表
//3.打印帶頭結點的單鏈表
void PrintList(Node *pNode){
/**
* 注意這裡，如果單鏈表為空（只有一個頭結點），我也讓它打印（打印成功）。只是裡面沒有元素，打出來是空的而已,所以在控制台上就是一行空的；
*/
Node *pMove;
pMove = pNode->next;
while (pMove != NULL) {
printf("%d ",pMove->element);
pMove = pMove->next;
}
printf("\n%s函數執行，打印帶頭結點的單鏈表成功\n",__FUNCTION__);
}
//4.清除線性表中的所有元素，即釋放所有節點（除了頭結點），使之成為一個空表
void ClearList(Node *pNode){
Node *pMove;
pMove = pNode->next;
while (pMove != NULL) {
pNode->next = pMove->next;
free(pMove);
pMove = pNode->next;
}
printf("%s函數執行，清空帶頭結點的鏈表成功\n",__FUNCTION__);
}
//5.返回帶頭結點的單鏈表的長度
int SizeList(Node *pNode){
/**
* 當只有一個頭結點的時候，size = 0；頭節點不計算到鏈表長度中。
*/
int i = 0;
Node *pMove;
pMove = pNode->next;
while (pMove != NULL) {
i++;
pMove = pMove->next;
}
printf("%s函數執行，帶頭結點的單鏈表的長度為：%d\n",__FUNCTION__,i);
return i;
}
（7）判斷鏈表是否為空
//6.判斷帶頭結點的單鏈表是否為空，為空則返回1，否則返回0
int IsEmptyList(Node *pNode){
/**
* 當只有一個頭結點的時候，該鏈表就為空
*/
if (pNode->next == NULL) {
printf("%s函數執行，帶頭結點的鏈表為空\n",__FUNCTION__);
return 1;
}
printf("%s函數執行，帶頭結點的鏈表非空\n",__FUNCTION__);
return 0;
}
（8）查找鏈表某個位置元素
//7.返回單鏈表中第pos個結點中的元素，若返回-1，表示沒有找到
int GetElement(Node *pNode,int pos){
int i = 1;
Node *pMove;
pMove = pNode->next;
while (pMove != NULL) {
if (i == pos) {
printf("%s函數執行，pos=%d位置的值是%d\n",__FUNCTION__,pos,pMove->element);
return pMove->element;
}
i++;
pMove = pMove->next;
}
printf("%s函數執行，在pos=%d位置沒有找到值\n",__FUNCTION__,pos);
return -1;
}
//8.從單鏈表中查找具有給定值x的第一個元素，若查找成功則返回該結點data域的存儲地址，否則返回NULL
elemType* GetElemAddr(Node *pNode,int x){
Node *pMove;
pMove = pNode->next;
while (pMove != NULL) {
if (pMove->element == x) {
printf("%s函數執行，查找到x=%d的內存地址為:0x%x\n",__FUNCTION__,x,&(pMove->element));
return &(pMove->element);
}
pMove = pMove->next;
}
printf("%s函數執行，在帶頭結點的單鏈表中沒有找到x=%d的值，無法獲得內存地址\n",__FUNCTION__,x);
return NULL;
}
//9.把單鏈表中第pos個結點的值修改為x的值
Node* ModifyElem(Node *pNode,int pos,int x){
int i = 1;
Node *pMove;
pMove = pNode->next;
while (pMove != NULL) {
if (i == pos) {
pMove->element = x;
printf("%s函數執行，把pos=%d位置的值改為%d成功\n",__FUNCTION__,pos,x);
return pNode;
}
i++;
pMove = pMove->next;
}
printf("%s函數執行，鏈表為空或者輸入pos值非法，修改值失敗\n",__FUNCTION__);
return pNode;
}
//10.向單鏈表的表頭插入一個元素
Node *InsertHeadList(Node *pNode,int x){
Node *pInsert;
pInsert = (Node *)malloc(sizeof(Node));
memset(pInsert, 0, sizeof(Node));
pInsert->element = x;
pInsert->next = pNode->next;
pNode->next = pInsert;
printf("%s函數執行，在表頭插入元素%d成功\n",__FUNCTION__,x);
return pNode;
}
// 11.向單鏈表的末尾添加一個元素
Node *InsertTailList(Node *pNode,int x){
Node *pMove;
Node *pInsert;
pInsert = (Node *)malloc(sizeof(Node));
memset(pInsert, 0, sizeof(Node));
pInsert->element = x;
pInsert->next = NULL;
pMove = pNode;
while (pMove->next != NULL) {
pMove = pMove->next;
}
pMove->next = pInsert;
printf("%s函數執行，在表尾插入元素%d成功\n",__FUNCTION__,x);
return pNode;
}
int main(int argc, const char * argv[]) {
Node *pList;
InitialList(&pList);
CreateList(pList);
PrintList(pList);
SizeList(pList);
IsEmptyList(pList);
GetElement(pList, 3);
GetElemAddr(pList, 5);
ModifyElem(pList, 2, 111);
PrintList(pList);
InsertHeadList(pList,1234);
PrintList(pList);
SizeList(pList);
InsertTailList(pList,9999);
PrintList(pList);
SizeList(pList);
ClearList(pList);
PrintList(pList);
return 0;
}
