C語言實現(xiàn)無頭單鏈表詳解
更新時間：2022年02月14日 15:09:59 作者：考拉愛睡覺鴨~
大家好，本篇文章主要講的是C語言實現(xiàn)無頭單鏈表詳解，感興趣的同學趕快來看一看吧，對你有幫助的話記得收藏一下
再封裝的方式，用 c++ 的思想做無頭鏈表
鏈表的結構體描述(節(jié)點)
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int DataType;
//節(jié)點
typedef struct Node
{
DataType data;
struct Node* next;
}NODE,*LPNODE;再定義一個結構體(鏈表)
通過記錄頭節(jié)點和尾節(jié)點的方式去描述鏈表
typedef struct list
{
LPNODE frontNode; //頭節(jié)點
LPNODE backNode; //尾節(jié)點
int curSize; //當前節(jié)點個數(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)); //用結構體變量去描述 做動態(tài)內(nèi)存申請
assert(list);
list->frontNode = NULL; //鏈表剛開始是空的 頭尾節(jié)點指向空
list->backNode = NULL;
list->curSize = 0; //當前元素個數(shù)為0
return list;
}創(chuàng)建節(jié)點
LPNODE createNode(int data)
{
LPNODE newNode = (LPNODE)malloc(sizeof(NODE));
assert(newNode);
//初始化數(shù)據(jù)
newNode->data = data;
newNode->next = NULL;
return newNode;
}頭插法
插入一個節(jié)點，節(jié)點插在原表頭前面，表頭會改變，在1(表頭)前面插入666(數(shù)據(jù))
把新節(jié)點的 next 指針指向原來的表頭
把原來表頭指針從原來的位置挪到新節(jié)點的位置
//插入的鏈表 插入的數(shù)據(jù)
void push_front(LPLIST list,int data)
{
LPNODE newNode = createNode(data); //創(chuàng)建新節(jié)點
newNode->next = list->frontNode;
list->frontNode = newNode;
//護頭也要護尾
if (list->curSize == 0) //只有一個節(jié)點 鏈表為空尾節(jié)點也是指向新節(jié)點
list->backNode = newNode; //把尾節(jié)點置為新節(jié)點
list->curSize++;
}
//測試代碼
LPLIST list = createList();
push_front(list, 1);
push_front(list, 2); //2 1
printList(list); 打印鏈表
從第1個節(jié)點開始打印
void printList(LPLIST list)
{
LPNODE pmove = list->frontNode;
while (pmove != NULL) //不為空打印數(shù)據(jù)
{
printf("%d\t", pmove->data);
pmove = pmove->next;
}
printf("\n");
}尾插法
不需要找尾巴，因為記錄了尾巴的位置
//插入的鏈表 插入的數(shù)據(jù)
void push_back(LPLIST list, int data)
{
LPNODE newNode = createNode(data); //創(chuàng)建新節(jié)點
if (list->curSize == 0)
{
list->frontNode = newNode; //只有1個節(jié)點的情況 表頭也是指向新節(jié)點
//list->backNode = newNode; //表尾指向新節(jié)點
}
else
{
list->backNode->next = newNode; //把原來鏈表的尾節(jié)點的next指針置為新節(jié)點
//list->backNode = newNode; //原來的表尾挪到新節(jié)點的位置
}
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é)點的數(shù)據(jù)==指定數(shù)據(jù))
前驅(qū)節(jié)點的 next 指針指向新節(jié)點，新節(jié)點的 next 指針指向當前節(jié)點
void push_appoin(LPLIST list, int posData, int data)
{
if (list == NULL || list->curSize == 0) //為空無法做插入
{
printf("無法插入鏈表為空!\n");
return;
}
//其他情況可以插入
if (list->frontNode->data == posData) //頭節(jié)點的數(shù)據(jù)==指定數(shù)據(jù)
{
push_front(list, data); //會改變表頭 用頭插法插入
return;
}
//正常插入的情況
LPNODE preNode = list->frontNode; //定義一個前驅(qū)節(jié)點指向第1個節(jié)點
LPNODE curNode = list->frontNode->next; //定義一個當前節(jié)點指向第1個節(jié)點的下一個節(jié)點
//當前節(jié)點!=NULL && 當前節(jié)點的數(shù)據(jù)!=指定數(shù)據(jù)
while (curNode != NULL && curNode->data != posData) //并排往下走
{
preNode = curNode; //前1個節(jié)點走到當前節(jié)點的位置
curNode = preNode->next; //當前節(jié)點走到原來位置的下一個
}
//分析查找結果做插入
if (curNode == NULL) //沒找到無法做插入
{
printf("沒有找到指定位置，無法插入！\n");
}
else
{
LPNODE newNode = createNode(data); //創(chuàng)建新節(jié)點
preNode->next = newNode; //連接
newNode->next = curNode;
list->curSize++;
}
}
//測試代碼
push_appoin(list, 666, 888);
printList(list); //2 1 888 666 999頭刪法
只有一個節(jié)點的情況：表尾也要改變(表尾指向了一段刪除的內(nèi)存)，表尾也要置為空
void pop_front(LPLIST list)
{
if (list == NULL || list->curSize == 0) //判空處理
{
printf("鏈表為空，無法刪除!\n");
return;
}
LPNODE nextNode = list->frontNode->next; //頭節(jié)點的下一個--->第2個節(jié)點
free(list->frontNode); //直接刪除表頭
list->frontNode = nextNode; //把原來的表頭節(jié)點置為下一個節(jié)點
if (list->curSize == 1) //只有1個節(jié)點的情況
{
list->backNode = NULL; //表尾也要置為空
}
list->curSize--;
}
//測試代碼
pop_front(list);
pop_front(list);
pop_front(list);
pop_front(list);
printList(list); //999尾刪法
要找到表尾的上一個節(jié)點
//要刪除的鏈表
void pop_back(LPLIST list)
{
if (list == NULL || list->curSize == 0)
{
printf("鏈表為空，無法刪除!\n");
return;
}
//從第1個節(jié)點開始找 做移動
LPNODE preNode = list->frontNode; //頭節(jié)點
LPNODE backNode = list->frontNode; //頭節(jié)點的下一個
while (backNode->next != NULL)
{
preNode = backNode; //并排往下走
backNode = preNode->next;
}
free(backNode);
if (list->curSize == 1) //只有一個節(jié)點的情況
{
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é)點的數(shù)據(jù)==指定數(shù)據(jù)
{
pop_front(list); //頭刪法
return;
}
if (list->backNode->data == posData) //尾節(jié)點的數(shù)據(jù)==指定數(shù)據(jù)
{
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查找鏈表
//要查找的鏈表 要查找的數(shù)據(jù)
LPNODE searchlist(LPLIST list, int posData)
{
if (list == NULL) //list為空 返回NULL無法做刪除
return NULL;
LPNODE pmove = list->frontNode; //定義一個移動的節(jié)點
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總結
到此這篇關于C語言實現(xiàn)無頭單鏈表詳解的文章就介紹到這了,更多相關C語言無頭單鏈表內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
這篇文章主要為大家詳細介紹了C語言實現(xiàn)萬年歷小程序，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2019-10-10
平衡二叉樹是具有平衡屬性的有序二叉樹，本文主要介紹了C語言中的平衡二叉樹，具有一定的參考價值，需要的小伙伴可以參考閱讀2023-04-04
本篇文章介紹了，在C中實現(xiàn)矩陣乘法的一種高效的方法。需要的朋友參考下2013-05-05
這篇文章主要為大家詳細介紹了Opencv實現(xiàn)最小外接矩形和圓，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2019-05-05
這篇文章主要為大家介紹了深入的分析了C語言與C++的區(qū)別與聯(lián)系，文中通過詳細的示例進行了對比，以便大家更容易的看懂理解，有需要的朋友可以借鑒參考下2021-11-11
剖析C++編程當中指針作為函數(shù)參數(shù)的用法
這篇文章主要介紹了剖析C++編程當中指針作為函數(shù)參數(shù)的用法,是C++入門學習中的基礎知識,需要的朋友可以參考下2015-09-09
斐波那契數(shù)列 優(yōu)化矩陣求法實例，需要的朋友可以參考一下2013-03-03
構造函數(shù)主要作用在于創(chuàng)建對象時為對象的成員屬性賦值，構造函數(shù)由編譯器自動調(diào)用,無須手動調(diào)用；析構函數(shù)主要作用在于對象銷毀前系統(tǒng)自動調(diào)用，執(zhí)行一 些清理工作2022-07-07
命令行解析庫是一種用于簡化處理命令行參數(shù)的工具,它可以幫助開發(fā)者更方便地解析命令行參數(shù)并提供適當?shù)膸椭畔?本文主要介紹了不同的命令行解析庫和它們在C++項目中的應用,希望對大家有所幫助2023-11-11
這篇文章主要介紹了詳解C++編程中對于函數(shù)的使用,包括函數(shù)的參數(shù)和返回值以及調(diào)用等基本的知識點,需要的朋友可以參考下2015-09-09