C語言實(shí)現(xiàn)無頭單鏈表詳解
更新時(shí)間：2022年02月14日 15:09:59 作者：考拉愛睡覺鴨~
大家好，本篇文章主要講的是C語言實(shí)現(xiàn)無頭單鏈表詳解，感興趣的同學(xué)趕快來看一看吧，對你有幫助的話記得收藏一下
再封裝的方式，用 c++ 的思想做無頭鏈表
鏈表的結(jié)構(gòu)體描述(節(jié)點(diǎn))
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int DataType;
//節(jié)點(diǎn)
typedef struct Node
{
DataType data;
struct Node* next;
}NODE,*LPNODE;再定義一個(gè)結(jié)構(gòu)體(鏈表)
通過記錄頭節(jié)點(diǎn)和尾節(jié)點(diǎn)的方式去描述鏈表
typedef struct list
{
LPNODE frontNode; //頭節(jié)點(diǎn)
LPNODE backNode; //尾節(jié)點(diǎn)
int curSize; //當(dāng)前節(jié)點(diǎn)個(gè)數(shù)
}LIST,*LPLIST;斷言處理 & 判空處理
如果 list 為空，會引發(fā)中斷(申請內(nèi)存可能失敗)
防御性編程，如果申請內(nèi)存失敗，操作無效，NULL 里面沒有 frontNode，backNode，curSize，存在安全隱患C6011：取消對 NULL 指針"list"的引用
如果申請內(nèi)存失敗，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為空 引發(fā)中斷
assert(list);
//if(list == NULL)
//return NULL; //可以替換
list->frontNode = NULL;
list->backNode = NULL;
list->curSize = 0;
return list;
}
//abort() has been called line 25創(chuàng)建鏈表
描述鏈表最初的狀態(tài)
LPLIST createList()
{
LPLIST list = (LPLIST)malloc(sizeof(LIST)); //用結(jié)構(gòu)體變量去描述 做動(dòng)態(tài)內(nèi)存申請
assert(list);
list->frontNode = NULL; //鏈表剛開始是空的 頭尾節(jié)點(diǎn)指向空
list->backNode = NULL;
list->curSize = 0; //當(dāng)前元素個(gè)數(shù)為0
return list;
}創(chuàng)建節(jié)點(diǎn)
LPNODE createNode(int data)
{
LPNODE newNode = (LPNODE)malloc(sizeof(NODE));
assert(newNode);
//初始化數(shù)據(jù)
newNode->data = data;
newNode->next = NULL;
return newNode;
}頭插法
插入一個(gè)節(jié)點(diǎn)，節(jié)點(diǎn)插在原表頭前面，表頭會改變，在1(表頭)前面插入666(數(shù)據(jù))
把新節(jié)點(diǎn)的 next 指針指向原來的表頭
把原來表頭指針從原來的位置挪到新節(jié)點(diǎn)的位置
//插入的鏈表 插入的數(shù)據(jù)
void push_front(LPLIST list,int data)
{
LPNODE newNode = createNode(data); //創(chuàng)建新節(jié)點(diǎn)
newNode->next = list->frontNode;
list->frontNode = newNode;
//護(hù)頭也要護(hù)尾
if (list->curSize == 0) //只有一個(gè)節(jié)點(diǎn) 鏈表為空尾節(jié)點(diǎn)也是指向新節(jié)點(diǎn)
list->backNode = newNode; //把尾節(jié)點(diǎn)置為新節(jié)點(diǎn)
list->curSize++;
}
//測試代碼
LPLIST list = createList();
push_front(list, 1);
push_front(list, 2); //2 1
printList(list); 打印鏈表
從第1個(gè)節(jié)點(diǎn)開始打印
void printList(LPLIST list)
{
LPNODE pmove = list->frontNode;
while (pmove != NULL) //不為空打印數(shù)據(jù)
{
printf("%d\t", pmove->data);
pmove = pmove->next;
}
printf("\n");
}尾插法
不需要找尾巴，因?yàn)橛涗浟宋舶偷奈恢?/p>
//插入的鏈表 插入的數(shù)據(jù)
void push_back(LPLIST list, int data)
{
LPNODE newNode = createNode(data); //創(chuàng)建新節(jié)點(diǎn)
if (list->curSize == 0)
{
list->frontNode = newNode; //只有1個(gè)節(jié)點(diǎn)的情況 表頭也是指向新節(jié)點(diǎn)
//list->backNode = newNode; //表尾指向新節(jié)點(diǎn)
}
else
{
list->backNode->next = newNode; //把原來鏈表的尾節(jié)點(diǎn)的next指針置為新節(jié)點(diǎn)
//list->backNode = newNode; //原來的表尾挪到新節(jié)點(diǎn)的位置
}
list->backNode = newNode; //相同代碼
list->curSize++;
}
//測試代碼
push_back(list, 666);
push_back(list, 999); //2 1 666 999
printList(list);指定位置插入
根據(jù)指定數(shù)據(jù)做插入，插在指定位置(數(shù)據(jù))前面，不需要考慮表尾(尾插)
分改變表頭、不改變表頭兩種情況：指定數(shù)據(jù)，數(shù)據(jù)可能插在表頭前面(頭節(jié)點(diǎn)的數(shù)據(jù)==指定數(shù)據(jù))
前驅(qū)節(jié)點(diǎn)的 next 指針指向新節(jié)點(diǎn)，新節(jié)點(diǎn)的 next 指針指向當(dāng)前節(jié)點(diǎn)
void push_appoin(LPLIST list, int posData, int data)
{
if (list == NULL || list->curSize == 0) //為空無法做插入
{
printf("無法插入鏈表為空!\n");
return;
}
//其他情況可以插入
if (list->frontNode->data == posData) //頭節(jié)點(diǎn)的數(shù)據(jù)==指定數(shù)據(jù)
{
push_front(list, data); //會改變表頭 用頭插法插入
return;
}
//正常插入的情況
LPNODE preNode = list->frontNode; //定義一個(gè)前驅(qū)節(jié)點(diǎn)指向第1個(gè)節(jié)點(diǎn)
LPNODE curNode = list->frontNode->next; //定義一個(gè)當(dāng)前節(jié)點(diǎn)指向第1個(gè)節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)
//當(dāng)前節(jié)點(diǎn)!=NULL && 當(dāng)前節(jié)點(diǎn)的數(shù)據(jù)!=指定數(shù)據(jù)
while (curNode != NULL && curNode->data != posData) //并排往下走
{
preNode = curNode; //前1個(gè)節(jié)點(diǎn)走到當(dāng)前節(jié)點(diǎn)的位置
curNode = preNode->next; //當(dāng)前節(jié)點(diǎn)走到原來位置的下一個(gè)
}
//分析查找結(jié)果做插入
if (curNode == NULL) //沒找到無法做插入
{
printf("沒有找到指定位置，無法插入！\n");
}
else
{
LPNODE newNode = createNode(data); //創(chuàng)建新節(jié)點(diǎn)
preNode->next = newNode; //連接
newNode->next = curNode;
list->curSize++;
}
}
//測試代碼
push_appoin(list, 666, 888);
printList(list); //2 1 888 666 999頭刪法
只有一個(gè)節(jié)點(diǎn)的情況：表尾也要改變(表尾指向了一段刪除的內(nèi)存)，表尾也要置為空
void pop_front(LPLIST list)
{
if (list == NULL || list->curSize == 0) //判空處理
{
printf("鏈表為空，無法刪除!\n");
return;
}
LPNODE nextNode = list->frontNode->next; //頭節(jié)點(diǎn)的下一個(gè)--->第2個(gè)節(jié)點(diǎn)
free(list->frontNode); //直接刪除表頭
list->frontNode = nextNode; //把原來的表頭節(jié)點(diǎn)置為下一個(gè)節(jié)點(diǎn)
if (list->curSize == 1) //只有1個(gè)節(jié)點(diǎn)的情況
{
list->backNode = NULL; //表尾也要置為空
}
list->curSize--;
}
//測試代碼
pop_front(list);
pop_front(list);
pop_front(list);
pop_front(list);
printList(list); //999尾刪法
要找到表尾的上一個(gè)節(jié)點(diǎn)
//要?jiǎng)h除的鏈表
void pop_back(LPLIST list)
{
if (list == NULL || list->curSize == 0)
{
printf("鏈表為空，無法刪除!\n");
return;
}
//從第1個(gè)節(jié)點(diǎn)開始找 做移動(dòng)
LPNODE preNode = list->frontNode; //頭節(jié)點(diǎn)
LPNODE backNode = list->frontNode; //頭節(jié)點(diǎn)的下一個(gè)
while (backNode->next != NULL)
{
preNode = backNode; //并排往下走
backNode = preNode->next;
}
free(backNode);
if (list->curSize == 1) //只有一個(gè)節(jié)點(diǎn)的情況
{
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) //頭節(jié)點(diǎn)的數(shù)據(jù)==指定數(shù)據(jù)
{
pop_front(list); //頭刪法
return;
}
if (list->backNode->data == posData) //尾節(jié)點(diǎn)的數(shù)據(jù)==指定數(shù)據(jù)
{
pop_back(list); //尾刪法
return;
}
//中間的某個(gè)情況
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查找鏈表
//要查找的鏈表 要查找的數(shù)據(jù)
LPNODE searchlist(LPLIST list, int posData)
{
if (list == NULL) //list為空 返回NULL無法做刪除
return NULL;
LPNODE pmove = list->frontNode; //定義一個(gè)移動(dòng)的節(jié)點(diǎn)
while (pmove != NULL && pmove->data != posData)
{
pmove = pmove->next; //數(shù)據(jù)!=指定數(shù)據(jù)一直往下走
}
return pmove; //退出循環(huán)直接返回
}刪除所有指定相同的元素
void pop_all(LPLIST list, int posData)
{
while (searchlist(list, posData) != NULL) //!=NULL說明里面有指定數(shù)據(jù)
{
pop_appoin(list, posData); //持續(xù)做刪除
}
}
//測試代碼
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總結(jié)
到此這篇關(guān)于C語言實(shí)現(xiàn)無頭單鏈表詳解的文章就介紹到這了,更多相關(guān)C語言無頭單鏈表內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
C語言中全局?jǐn)?shù)組和局部數(shù)組的問題
今天同學(xué)遇到一個(gè)在C語言中全局?jǐn)?shù)組和局部數(shù)組的問題，卡了許久，我也沒有第一時(shí)間看出問題，現(xiàn)在把問題梳理一下，并給出解決方案,需要的朋友可以參考下2012-12-12
大家好，本篇文章主要講的是C++中引用和const關(guān)鍵字介紹，感興趣的同學(xué)趕快來看一看吧，對你有幫助的話記得收藏一下2022-02-02
C語言實(shí)現(xiàn)簡單員工工資管理系統(tǒng)
這篇文章主要為大家詳細(xì)介紹了C語言實(shí)現(xiàn)簡單員工工資管理系統(tǒng)，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2022-03-03
C++實(shí)現(xiàn)簡單的通訊錄管理系統(tǒng)
這篇文章主要為大家詳細(xì)介紹了C++實(shí)現(xiàn)簡單的通訊錄管理系統(tǒng)，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2022-06-06
C語言自定義類型超詳細(xì)梳理之結(jié)構(gòu)體 枚舉 聯(lián)合體
今天我們來學(xué)習(xí)一下自定義類型，自定義類型包括結(jié)構(gòu)體、枚舉、聯(lián)合體，小編覺得挺不錯(cuò)的，現(xiàn)在就分享給大家，也給大家做個(gè)參考2022-03-03
C++中可以接受任意多個(gè)參數(shù)的函數(shù)定義方法(詳解)
下面小編就為大家?guī)硪黄狢++中可以接受任意多個(gè)參數(shù)的函數(shù)定義方法(詳解)。小編覺得挺不錯(cuò)的，現(xiàn)在就分享給大家，也給大家做個(gè)參考。一起跟隨小編過來看看吧2016-10-10
這篇文章主要介紹了C語言編程中的布爾bool數(shù)據(jù)類型,bool并不是需要通過C++才能使用的,需要的朋友可以參考下2015-11-11
C++示例分析內(nèi)聯(lián)函數(shù)與引用變量及函數(shù)重載的使用
為了消除函數(shù)調(diào)用的時(shí)空開銷，C++ 提供一種提高效率的方法，即在編譯時(shí)將函數(shù)調(diào)用處用函數(shù)體替換，類似于C語言中的宏展開。這種在函數(shù)調(diào)用處直接嵌入函數(shù)體的函數(shù)稱為內(nèi)聯(lián)函數(shù)（Inline Function），又稱內(nèi)嵌函數(shù)或者內(nèi)置函數(shù)2022-08-08
C/C++中關(guān)于std::string的compare陷阱示例詳解
這篇文章主要給大家介紹了關(guān)于C/C++中關(guān)于std::string的compare陷阱的相關(guān)資料，文中先對C/C++中的std::string進(jìn)行了簡單的介紹，通過示例代碼介紹的非常詳細(xì)，需要的朋友可以參考借鑒，下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧。2017-11-11
c++語言中虛函數(shù)實(shí)現(xiàn)多態(tài)的原理詳解
這篇文章主要給大家介紹了關(guān)于c++語言中虛函數(shù)實(shí)現(xiàn)多態(tài)的原理的相關(guān)資料，文中通過示例代碼介紹的非常詳細(xì)，對大家學(xué)習(xí)或者使用c++語言具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面來一起學(xué)習(xí)學(xué)習(xí)吧2019-05-05