C語言數據結構之單鏈表的實現
一.為什麼使用鏈表
在學習鏈表以前,我們存儲數據用的方式就是數組。使用數組的好處就是便於查找數據,但缺點也很明顯。
使用前需聲明數組的長度,一旦聲明長度就不能更改
插入和刪除操作需要移動大量的數組元素,效率慢
隻能存儲一種類型的數據.
為瞭解決上述的問題,我們就可以使用鏈表來存儲數據。
二.鏈表的概念
概念:鏈表是一種物理存儲結構上非連續、非順序的存儲結構,數據元素的邏輯順序是通過鏈表中的指針鏈接次序實現的
三.鏈表的實現
3.1 創建鏈表前須知
結點:鏈表中每一個元素稱為“結點”,每個結點都應包括兩個部分:一為用戶需要用的實際數據;二為下一個結點的地址,
頭結點:在單鏈表的第一個結點之前附設一個結點,這個節點不存儲數據,稱之為頭結點
3.2 定義結構體
#include <stdio.h> #include <stdlib.h> #include <assert.h> typedef int SLDateType; //鏈表中存儲的數據類型,可換成其他 typedef struct SListNode { SLDateType date; struct SListNode* next; //指向下一個節點的指針 }SListNode;
3.3 申請一個節點
SListNode* BuyListNode(SLDateType x) { SListNode* newNode = (SListNode*)malloc(sizeof(SListNode)); if (NULL == newNode) { printf("malloc error\n"); //內存開辟失敗 exit(-1); } else { newNode->date = x; // 給新節點賦值 newNode->next = NULL; } return newNode; }
3.4 鏈表的頭插
void SListPushFront(SListNode** pphead/*要改動頭指針,所以要傳遞二級指針*/, SLDateType x) { SListNode* newNode = BuyListNode(x); //申請節點 newNode->next = *pphead; *pphead = newNode; }
3.5 鏈表的尾插
void SListPushBack(SListNode** pphead, SLDateType x) { SListNode* newNode = BuyListNode(x); if (*pphead == NULL) //若頭指針為空,則鏈表為空鏈表,直接將新節點接到頭指針後 { *pphead = newNode; } else { SListNode* tail = *pphead; while (tail->next != NULL) //找鏈表的尾部 { tail = tail->next; } tail->next = newNode;//將新節點接到尾部 } }
3.6 鏈表的尾刪
void SListPopBack(SListNode** pphead) { assert(pphead); if (*pphead == NULL)//鏈表為空,則不進行任何操作 { return; } else if ((*pphead)->next == NULL) //鏈表隻有一個節點 { free(*pphead); *pphead = NULL; } else//其餘情況 { SListNode* tail = *pphead; //鏈表的尾部節點 SListNode* pre = NULL;//鏈表尾的前一個節點 while (tail->next != NULL)//找尾 { pre = tail; tail = tail->next; } pre->next = tail->next; //將尾節點的指針域賦值給前一個節點的指針域 free(tail); } }
3.7 鏈表的頭刪
void SListPopFront(SListNode** pphead) { assert(pphead); if (*pphead == NULL) //鏈表為空什麼也不做 { return; } else { SListNode* head = *pphead;//記錄原本的第一個節點 *pphead = head->next; //讓頭指針指向第二個節點 free(head);//釋放第一個節點 } }
3.8 尋找某節點
SListNode* SListFind(SListNode* phead, SLDateType x) { SListNode* cur = phead; while (cur != NULL) { if (cur->date == x) //找到則返回該節點 { return cur; } cur = cur->next; } return NULL; //未找到則返回空 }
3.9 在指定節點前插入節點
void SListInsert(SListNode** pphead, SListNode* pos/*要插入的位置*/, SLDateType x) { assert(pphead); assert(pos); if (*pphead == pos) { SListPushFront(pphead, x); } else { SListNode* cur = *pphead; //當前所指向的位置 SListNode* pre = NULL; //前一個節點 while (cur != pos) { pre = cur; cur = cur->next; } SListNode* newNode = BuyListNode(x); pre->next = newNode; newNode->next = cur; } }
3.10 刪除指定節點前的節點
void SListErase(SListNode** pphead, SListNode* pos/*要插入的位置*/) { assert(pphead); assert(pos); if (*pphead == pos) { SListPopFront(pphead); } else { SListNode* cur = *pphead; SListNode* pre = *pphead; while (cur != pos) { pre = cur; cur = cur->next; } pre->next = cur->next; free(cur); } }
3.11 鏈表的銷毀
void SListDestory(SListNode** pphead) { if (*pphead == NULL) { return; } else { while (*pphead != NULL) { SListNode* cur = *pphead; *pphead = cur->next; free(cur); } } }
到此這篇關於C語言數據結構之單鏈表的實現的文章就介紹到這瞭,更多相關C語言 單鏈表內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet!