C語言實現無頭單鏈表詳解
再封裝的方式，用 c++ 的思想做無頭鏈表
鏈表的結構體描述(節點)
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int DataType;
//節點
typedef struct Node
{
DataType data;
struct Node* next;
}NODE,*LPNODE;
再定義一個結構體(鏈表)
通過記錄頭節點和尾節點的方式去描述鏈表
typedef struct list
{
LPNODE frontNode; //頭節點
LPNODE backNode; //尾節點
int curSize; //當前節點個數
}LIST,*LPLIST;
斷言處理 & 判空處理
如果 list 為空，會引發中斷(申請內存可能失敗)
防禦性編程，如果申請內存失敗，操作無效，NULL 裡面沒有 frontNode，backNode，curSize，存在安全隱患C6011：取消對 NULL 指針"list"的引用
如果申請內存失敗，assert()直接讓程序直接中斷，並且告訴你程序斷在哪一行
#include<assert> //斷言處理宏
#define assert(expression) (void)( \
(!!(expression)) || \
(_wassert(_CRT_WIDE(#expression), _CRT_WIDE(__FILE__), (unsigned)(__LINE__)), 0) \
)
LPLIST createList()
{
LPLIST list = (LPLIST)malloc(sizeof(LIST));
list = NULL; //list為空 引發中斷
assert(list);
//if(list == NULL)
//return NULL; //可以替換
list->frontNode = NULL;
list->backNode = NULL;
list->curSize = 0;
return list;
}
//abort() has been called line 25
創建鏈表
描述鏈表最初的狀態
LPLIST createList()
{
LPLIST list = (LPLIST)malloc(sizeof(LIST)); //用結構體變量去描述 做動態內存申請
assert(list);
list->frontNode = NULL; //鏈表剛開始是空的 頭尾節點指向空
list->backNode = NULL;
list->curSize = 0; //當前元素個數為0
return list;
}
創建節點
LPNODE createNode(int data)
{
LPNODE newNode = (LPNODE)malloc(sizeof(NODE));
assert(newNode);
//初始化數據
newNode->data = data;
newNode->next = NULL;
return newNode;
}
頭插法
插入一個節點，節點插在原表頭前面，表頭會改變，在1(表頭)前面插入666(數據)
把新節點的 next 指針指向原來的表頭
把原來表頭指針從原來的位置挪到新節點的位置
//插入的鏈表 插入的數據
void push_front(LPLIST list,int data)
{
LPNODE newNode = createNode(data); //創建新節點
newNode->next = list->frontNode;
list->frontNode = newNode;
//護頭也要護尾
if (list->curSize == 0) //隻有一個節點 鏈表為空尾節點也是指向新節點
list->backNode = newNode; //把尾節點置為新節點
list->curSize++;
}
//測試代碼
LPLIST list = createList();
push_front(list, 1);
push_front(list, 2); //2 1
printList(list);
打印鏈表
從第1個節點開始打印
void printList(LPLIST list)
{
LPNODE pmove = list->frontNode;
while (pmove != NULL) //不為空打印數據
{
printf("%d\t", pmove->data);
pmove = pmove->next;
}
printf("\n");
}
尾插法
不需要找尾巴，因為記錄瞭尾巴的位置
//插入的鏈表 插入的數據
void push_back(LPLIST list, int data)
{
LPNODE newNode = createNode(data); //創建新節點
if (list->curSize == 0)
{
list->frontNode = newNode; //隻有1個節點的情況 表頭也是指向新節點
//list->backNode = newNode; //表尾指向新節點
}
else
{
list->backNode->next = newNode; //把原來鏈表的尾節點的next指針置為新節點
//list->backNode = newNode; //原來的表尾挪到新節點的位置
}
list->backNode = newNode; //相同代碼
list->curSize++;
}
//測試代碼
push_back(list, 666);
push_back(list, 999); //2 1 666 999
printList(list);
指定位置插入
根據指定數據做插入，插在指定位置(數據)前面，不需要考慮表尾(尾插)
分改變表頭、不改變表頭兩種情況：指定數據，數據可能插在表頭前面(頭節點的數據==指定數據)
前驅節點的 next 指針指向新節點，新節點的 next 指針指向當前節點
void push_appoin(LPLIST list, int posData, int data)
{
if (list == NULL || list->curSize == 0) //為空無法做插入
{
printf("無法插入鏈表為空!\n");
return;
}
//其他情況可以插入
if (list->frontNode->data == posData) //頭節點的數據==指定數據
{
push_front(list, data); //會改變表頭 用頭插法插入
return;
}
//正常插入的情況
LPNODE preNode = list->frontNode; //定義一個前驅節點指向第1個節點
LPNODE curNode = list->frontNode->next; //定義一個當前節點指向第1個節點的下一個節點
//當前節點!=NULL && 當前節點的數據!=指定數據
while (curNode != NULL && curNode->data != posData) //並排往下走
{
preNode = curNode; //前1個節點走到當前節點的位置
curNode = preNode->next; //當前節點走到原來位置的下一個
}
//分析查找結果做插入
if (curNode == NULL) //沒找到無法做插入
{
printf("沒有找到指定位置，無法插入！\n");
}
else
{
LPNODE newNode = createNode(data); //創建新節點
preNode->next = newNode; //連接
newNode->next = curNode;
list->curSize++;
}
}
//測試代碼
push_appoin(list, 666, 888);
printList(list); //2 1 888 666 999
頭刪法
隻有一個節點的情況：表尾也要改變(表尾指向瞭一段刪除的內存)，表尾也要置為空
void pop_front(LPLIST list)
{
if (list == NULL || list->curSize == 0) //判空處理
{
printf("鏈表為空，無法刪除!\n");
return;
}
LPNODE nextNode = list->frontNode->next; //頭節點的下一個--->第2個節點
free(list->frontNode); //直接刪除表頭
list->frontNode = nextNode; //把原來的表頭節點置為下一個節點
if (list->curSize == 1) //隻有1個節點的情況
{
list->backNode = NULL; //表尾也要置為空
}
list->curSize--;
}
//測試代碼
pop_front(list);
pop_front(list);
pop_front(list);
pop_front(list);
printList(list); //999
尾刪法
要找到表尾的上一個節點
//要刪除的鏈表
void pop_back(LPLIST list)
{
if (list == NULL || list->curSize == 0)
{
printf("鏈表為空，無法刪除!\n");
return;
}
//從第1個節點開始找 做移動
LPNODE preNode = list->frontNode; //頭節點
LPNODE backNode = list->frontNode; //頭節點的下一個
while (backNode->next != NULL)
{
preNode = backNode; //並排往下走
backNode = preNode->next;
}
free(backNode);
if (list->curSize == 1) //隻有一個節點的情況
{
backNode = NULL; //釋放後置空
list->frontNode = NULL; //表頭也要置為空
list->backNode = NULL; //表尾置為空
list->curSize--;
}
else
{
backNode = NULL;
preNode->next = NULL;
list->backNode = preNode;
list->curSize--;
}
}
//測試代碼
pop_back(list);
printList(list);
指定位置刪除
void pop_appoin(LPLIST list,int posData)
{
if (list == NULL || list->curSize == 0)
{
printf("鏈表為空，無法刪除!\n");
return;
}
if (list->frontNode->data == posData) //頭節點的數據==指定數據
{
pop_front(list); //頭刪法
return;
}
if (list->backNode->data == posData) //尾節點的數據==指定數據
{
pop_back(list); //尾刪法
return;
}
//中間的某個情況
LPNODE preNode = list->frontNode; //原來的頭部
LPNODE curNode = list->frontNode->next;
while (curNode != NULL && curNode->data != posData)
{
preNode = curNode; //並排往下走
curNode = preNode->next;
}
if (curNode == NULL)
{
printf("未找到指定位置，無法刪除!\n");
}
else
{
preNode->next = curNode->next; //先連後斷
free(curNode);
curNode = NULL;
list->curSize--;
}
}
//測試代碼
pop_appoin(list, 2);
pop_appoin(list, 999);
pop_appoin(list, 888); //2 1 888 666 999
printList(list); //1 666
查找鏈表
//要查找的鏈表 要查找的數據
LPNODE searchlist(LPLIST list, int posData)
{
if (list == NULL) //list為空 返回NULL無法做刪除
return NULL;
LPNODE pmove = list->frontNode; //定義一個移動的節點
while (pmove != NULL && pmove->data != posData)
{
pmove = pmove->next; //數據!=指定數據一直往下走
}
return pmove; //退出循環直接返回
}
刪除所有指定相同的元素
void pop_all(LPLIST list, int posData)
{
while (searchlist(list, posData) != NULL) //!=NULL說明裡面有指定數據
{
pop_appoin(list, posData); //持續做刪除
}
}
//測試代碼
LPLIST test = createList();
push_back(test, 1);
push_back(test, 1);
push_back(test, 1);
push_back(test, 2);
pop_all(test, 1);
printList(test); //2
總結
到此這篇關於C語言實現無頭單鏈表詳解的文章就介紹到這瞭,更多相關C語言無頭單鏈表內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！