C語言實(shí)現(xiàn)無頭單鏈表詳解
更新時(shí)間：2022年02月14日 15:09:59 作者：考拉愛睡覺鴨~
大家好，本篇文章主要講的是C語言實(shí)現(xiàn)無頭單鏈表詳解，感興趣的同學(xué)趕快來看一看吧，對(duì)你有幫助的話記得收藏一下
再封裝的方式，用 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 為空，會(huì)引發(fā)中斷(申請(qǐng)內(nèi)存可能失敗)
防御性編程，如果申請(qǐng)內(nèi)存失敗，操作無效，NULL 里面沒有 frontNode，backNode，curSize，存在安全隱患C6011：取消對(duì) NULL 指針"list"的引用
如果申請(qǐng)內(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)存申請(qǐng)
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)插在原表頭前面，表頭會(huì)改變，在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++;
}
//測(cè)試代碼
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++;
}
//測(cè)試代碼
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); //會(huì)改變表頭 用頭插法插入
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++;
}
}
//測(cè)試代碼
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--;
}
//測(cè)試代碼
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--;
}
}
//測(cè)試代碼
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--;
}
}
//測(cè)試代碼
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ù)做刪除
}
}
//測(cè)試代碼
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)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
這篇文章主要為大家詳細(xì)介紹了C語言實(shí)現(xiàn)萬年歷小程序，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2019-10-10
平衡二叉樹是具有平衡屬性的有序二叉樹，本文主要介紹了C語言中的平衡二叉樹，具有一定的參考價(jià)值，需要的小伙伴可以參考閱讀2023-04-04
本篇文章介紹了，在C中實(shí)現(xiàn)矩陣乘法的一種高效的方法。需要的朋友參考下2013-05-05
這篇文章主要為大家詳細(xì)介紹了Opencv實(shí)現(xiàn)最小外接矩形和圓，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2019-05-05
這篇文章主要為大家介紹了深入的分析了C語言與C++的區(qū)別與聯(lián)系，文中通過詳細(xì)的示例進(jìn)行了對(duì)比，以便大家更容易的看懂理解，有需要的朋友可以借鑒參考下2021-11-11
剖析C++編程當(dāng)中指針作為函數(shù)參數(shù)的用法
這篇文章主要介紹了剖析C++編程當(dāng)中指針作為函數(shù)參數(shù)的用法,是C++入門學(xué)習(xí)中的基礎(chǔ)知識(shí),需要的朋友可以參考下2015-09-09
斐波那契數(shù)列 優(yōu)化矩陣求法實(shí)例
斐波那契數(shù)列 優(yōu)化矩陣求法實(shí)例，需要的朋友可以參考一下2013-03-03
構(gòu)造函數(shù)主要作用在于創(chuàng)建對(duì)象時(shí)為對(duì)象的成員屬性賦值，構(gòu)造函數(shù)由編譯器自動(dòng)調(diào)用,無須手動(dòng)調(diào)用；析構(gòu)函數(shù)主要作用在于對(duì)象銷毀前系統(tǒng)自動(dòng)調(diào)用，執(zhí)行一 些清理工作2022-07-07
C++ Boost命令行解析庫(kù)的應(yīng)用詳解
命令行解析庫(kù)是一種用于簡(jiǎn)化處理命令行參數(shù)的工具,它可以幫助開發(fā)者更方便地解析命令行參數(shù)并提供適當(dāng)?shù)膸椭畔?本文主要介紹了不同的命令行解析庫(kù)和它們?cè)贑++項(xiàng)目中的應(yīng)用,希望對(duì)大家有所幫助2023-11-11
這篇文章主要介紹了詳解C++編程中對(duì)于函數(shù)的使用,包括函數(shù)的參數(shù)和返回值以及調(diào)用等基本的知識(shí)點(diǎn),需要的朋友可以參考下2015-09-09