我在之前一篇博客《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; }