C語言中單鏈表的基本操作(創(chuàng)建、銷毀、增刪查改等)
更新時間：2023年02月05日 10:20:16 作者：安河橋畔
這篇文章主要介紹了C語言中單鏈表的基本操作(創(chuàng)建、銷毀、增刪查改等)，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教
鏈表分類
鏈表主要有下面三種分類方法：
- 單向或者雙向
- 帶頭或者不帶頭
- 循環(huán)或者非循環(huán)綜合來看鏈表有八種類型，本文主要針對的是不帶頭節(jié)點的非循環(huán)單鏈表。
單鏈表的介紹
typedef struct SListNode
{
DataType data;//數據域
struct SListNode *next;//結構體指針，指向下一個節(jié)點
}SListNode;//類型別名
如圖
鏈表的每一個節(jié)點由數據域和指針域構成，數據域存放數據，指針域中的指針指向下一個節(jié)點。
plist表示鏈表的指針，指向鏈表的第一個節(jié)點，最后一個節(jié)點的指針為空。
單鏈表的基本操作
創(chuàng)建
創(chuàng)建單鏈表有幾點需注意：
- 鏈表與順序表的區(qū)別是，順序表是物理空間上連續(xù)的，而鏈表只在邏輯上連續(xù)，所以鏈表申請空間時是使用一個申請一個，順序表則是一次申請一段空間，空間不足時進行擴容。
- 如果在棧上申請空間，在函數調用結束后會釋放，所以需要在堆區(qū)申請空間。
- 每次申請一個節(jié)點都要存入數據，所以鏈表總是滿的，而順序表則可能有一段空間沒有利用。
- 函數的返回值是指向節(jié)點的結構體類型的指針
SListNode* BuySListNode(DataType x)
{
SListNode* plist = (SListNode*)malloc(sizeof(SListNode));
if (plist == NULL)
{
return NULL;//判斷是否申請成功
}
plist->data = x;
plist->next = NULL;
return plist;
}
打印
遍歷鏈表，進行打印
void SListPrint(SListNode* plist)
{
assert(plist);
SListNode* cur = plist;
while (cur)
{
printf("%d-->", cur->data);
cur = cur->next;
}
printf("NULL\n");
}
尾插
尾插的操作步驟：
- 若鏈表為空，*pplist指向新插入的節(jié)點
- 鏈表不為空則遍歷鏈表，找到最后一個節(jié)點
- 令最后一個節(jié)點的next指向新插入的節(jié)點
- 新插入的節(jié)點next指向NULL
注意事項：
- 因為插入元素要改變原鏈表中指針的指向，故傳參時要傳入二級指針。
- assert(pplist)是判斷鏈表是否存在，因為pplist是指向鏈表的指針的地址，若pplist為空，說明鏈表的地址不存在，即鏈表不存在；而如果(*pplist)為空，表示的是該鏈表是空鏈表。
void SListPushBack(SListNode** pplist, DataType x)
{
//改變指針指向，參數傳二級指針
assert(pplist);//判斷鏈表是否存在,與鏈表是否為空不同
//1.若鏈表為空，*pplist指向插入的節(jié)點
if (*pplist == NULL)
{
*pplist = BuySListNode(x);
}
else {
//2.鏈表不為空，指針移動到鏈表最后一個節(jié)點，其next指向插入的節(jié)點
SListNode* cur = *pplist;
while (cur->next)
{
cur = cur->next;//cur的next為空時，cur指向最后一個節(jié)點
}
cur->next = BuySListNode(x);
}
}
頭插
頭插操作順序：
- 申請一個新節(jié)點
- 新節(jié)點的next指向原來的第一個節(jié)點，即*pplist
- 改變*pplist指向，使其指向新增的節(jié)點
進行頭插時，要注意各個步驟的順序，如果直接令*pplist指向了新增的的節(jié)點，會導致原有的第一個節(jié)點無法找；另外，鏈表為空時的操作方法與鏈表非空時代碼可以合并，不用再分開寫各種情況。
void SListPushFront(SListNode** pplist, DataType x)
{
assert(pplist);
//if (NULL == *pplist)
//{
// //鏈表為空
// *pplist = BuySListNode(x);
//}
//else
//{
// SListNode* temp = *pplist;//temp指向鏈表原來的第一個節(jié)點
// *pplist = BuySListNode(x);//plist指向新增的節(jié)點
// (*pplist)->next = temp;//新增的節(jié)點指向原來的第一個節(jié)點
//}
//上面兩種情況代碼可以合并
SListNode* node = BuySListNode(x);//申請一個新節(jié)點
node->next = *pplist;//新增的節(jié)點的next指向原來的第一個節(jié)點
*pplist = node;//*pplist指向新增的節(jié)點
}
尾刪
尾刪步驟：
- 判斷鏈表是否為空或只有一個結點
- 遍歷找到最后一個節(jié)點的前驅結點prev
- 令prev的next指向NULL
- 釋放原來最后一個節(jié)點申請的空間
注意事項：
- 區(qū)分鏈表為空、單個結點、多個結點各種情況
- 不能找到最后一個節(jié)點并將其置空，而是要找到其前驅節(jié)點，斷開與最后一個節(jié)點的連接
- 刪除節(jié)點后要釋放空間，避免內存泄漏
void SListPopBack(SListNode** pplist)
{
assert(pplist);
//1.鏈表為空
if (NULL== *pplist)
{
return;
}
//2.鏈表只有一個元素
else if (NULL == (*pplist)->next)
{
free(*pplist);
*pplist = NULL;
}
//3.鏈表有多個元素
else
{
SListNode* prev = NULL;
SListNode* cur = *pplist;
while (cur->next)
{
prev = cur;
cur = cur->next;//循環(huán)結束時cur指向最后一個節(jié)點
}
//cur= NULL;//這里不能寫cur=NULL,需要找到cur的前一個節(jié)點，將其next置空\
否則前一個結點的next依然指向原來的最后一個節(jié)點
prev->next = NULL;//prev成為最后一個節(jié)點
free(cur);//釋放原來最后一個節(jié)點的空間
}
頭刪
頭刪的操作步驟：
- 保存第一個節(jié)點的指針信息
- 令*pplist指向第二個節(jié)點
- 釋放原來的第一個節(jié)點的空間
同樣的，頭刪也要注意保存原來第一個節(jié)點的位置，否則*pplist指向改變后，原來的第一個節(jié)點就找不到了，會無法釋放空間造成內存泄漏。
void SListPopFront(SListNode** pplist)
{
assert(pplist);
//1.單鏈表為空
if (NULL == *pplist)
{
return;
}
2.單鏈表有一個節(jié)點
//else if (NULL == (*pplist)->next)
//{
// *pplist = NULL;//刪除后鏈表為空
//}
3.單鏈表有多個節(jié)點
//else
//{
//*pplist= (*pplist)->next;
//}
//兩種情況可以合并，只有一個節(jié)點時，*pplist的next為空
else
{
SListNode* delNode = *pplist;
*pplist = delNode->next;
free(delNode);//釋放刪除節(jié)點的空間
}
}
查找
用于查找某一元素是否存在于鏈表中，若存在則返回其第一次出現(xiàn)在鏈表中的位置，不存在則返回NULL。
遍歷時注意循環(huán)條件。
SListNode* SListFind(SListNode* plist, DataType x)
{
SListNode* cur = plist;
while (cur)
{
if (cur->data == x)
{
return cur;
}
else
{
cur = cur->next;
}
}
return NULL;
}
任意位置插入
pos節(jié)點后插入的步驟：
- 申請一個新的節(jié)點
- 新增節(jié)點的next指向原pos的next
- pos的next指向新增的節(jié)點
注意事項
- 任意位置的插入操作只能在給定節(jié)點的后面插入，前面的節(jié)點無法同通過給出的節(jié)點找到。
- 要注意插入的操作順序，否則原來鏈表pos后的節(jié)點可能會找不到
void SListInsertAfter(SListNode* pos, DataType x)
{
assert(pos);//指針合法性校驗
SListNode* newNode = BuySListNode(x);
newNode->next = pos->next;
pos->next = newNode;
}
任意位置刪除
與任意位置的插入相同，只能刪除給定節(jié)點pos后面的節(jié)點
void SListDeleteAfter(SListNode* pos)
{
assert(pos);
//1.鏈表有一個節(jié)點
if (NULL == pos->next)
{
return;
}
//2.鏈表有多個節(jié)點
else
{
SListNode* temp = pos->next;
pos->next = temp->next;
free(temp);
}
}
銷毀
鏈表的銷毀，遍歷一遍，逐個釋放空間
void SListDestroy(SListNode** pplist)
{
assert(pplist);//鏈表是否存在
//1.鏈表為空
if (NULL == *pplist)
{
return;
}
else
{
SListNode* cur = NULL;
while (*pplist)
{
cur = *pplist;
*pplist = (*pplist)->next;
free(cur);
}
}
}
完整代碼
work.h
頭文件包含，函數聲明，定義結構體
#pragma once
#include<stdio.h>
#include<Windows.h>
#include<assert.h>
#include<assert.h>
typedef int DataType;
typedef struct SListNode
{
DataType data;//數據域
struct SListNode *next;//結構體指針，指向下一個節(jié)點
}SListNode;//類型別名
//函數聲明
SListNode* BuySListNode(DataType x);//節(jié)點申請
void SListPrint(SListNode* pst);//單鏈表遍歷打印
void SListPushBack(SListNode** pplist, DataType x);//單鏈表尾插
void SListPushFront(SListNode** pplist, DataType x);//單鏈表頭插
void SListPopBack(SListNode** pplist);//單鏈表尾刪
void SListPopFront(SListNode** pplist);//單鏈表頭刪
SListNode* SListFind(SListNode* plist, DataType x);//單鏈表查找
void SListInsertAfter(SListNode* pos, DataType x);//pos后位置的插入
void SListDeleteAfter(SListNode* pos);//pos后位置的刪除
void SListDestroy(SListNode** pplist);//釋放鏈表空間
work.c
各操作函數的具體實現(xiàn)
#include"work.h"
//鏈表與順序表的區(qū)別是，順序表是物理空間上連續(xù)的
//而鏈表只在邏輯上連續(xù)，所以鏈表申請空間時是使用一個申請一個
//順序表則是一次申請一段空間
SListNode* BuySListNode(DataType x)
{
//若在棧申請內存函數調用結束后會釋放，所以使用動態(tài)申請
SListNode* plist = (SListNode*)malloc(sizeof(SListNode));
if (plist == NULL)
{
return NULL;//判斷是否申請成功
}
plist->data = x;
plist->next = NULL;
return plist;
}
void SListPrint(SListNode* plist)
{
assert(plist);
SListNode* cur = plist;
while (cur)
{
printf("%d-->", cur->data);
cur = cur->next;
}
printf("NULL\n");
}
//尾插法
void SListPushBack(SListNode** pplist, DataType x)
{
//改變指針指向，參數傳二級指針
assert(pplist);//判斷鏈表是否存在,與鏈表是否為空不同
//1.若鏈表為空，*pplist指向插入的節(jié)點
if (*pplist == NULL)
{
*pplist = BuySListNode(x);
}
else {
//2.鏈表不為空，指針移動到鏈表最后一個節(jié)點，其next指向插入的節(jié)點
SListNode* cur = *pplist;
while (cur->next)
{
cur = cur->next;//cur的next為空時，cur指向最后一個節(jié)點
}
cur->next = BuySListNode(x);
}
}
//頭插法
void SListPushFront(SListNode** pplist, DataType x)
{
assert(pplist);
//if (NULL == *pplist)
//{
// //鏈表為空
// *pplist = BuySListNode(x);
//}
//else
//{
// SListNode* temp = *pplist;//temp指向鏈表原來的第一個節(jié)點
// *pplist = BuySListNode(x);//plist指向新增的節(jié)點
// (*pplist)->next = temp;//新增的節(jié)點指向原來的第一個節(jié)點
//}
//鏈表為空的情況可以和不為空合并
SListNode* node = BuySListNode(x);//申請一個新節(jié)點
node->next = *pplist;//新增的節(jié)點的next指向原來的第一個節(jié)點
*pplist = node;//*pplist指向新增的節(jié)點
}
//尾刪法？
void SListPopBack(SListNode** pplist)
{
assert(pplist);
//1.鏈表為空
if (NULL== *pplist)
{
return;
}
//2.鏈表只有一個元素
else if (NULL == (*pplist)->next)
{
free(*pplist);
*pplist = NULL;
}
//3.鏈表有多個元素
else
{
SListNode* prev = NULL;
SListNode* cur = *pplist;
while (cur->next)
{
prev = cur;
cur = cur->next;//循環(huán)結束時cur指向最后一個節(jié)點
}
//cur= NULL;//這里不能寫cur=NULL,需要找到cur的前一個節(jié)點，將其next置空\
否則前一個結點的next依然指向原來的最后一個節(jié)點
prev->next = NULL;//prev最后一個節(jié)點
free(cur);//釋放原來最后一個節(jié)點的空間
}
}
//頭刪
void SListPopFront(SListNode** pplist)
{
assert(pplist);
//1.單鏈表為空
if (NULL == *pplist)
{
return;
}
2.單鏈表有一個節(jié)點
//else if (NULL == (*pplist)->next)
//{
// *pplist = NULL;//刪除后鏈表為空
//}
3.單鏈表有多個節(jié)點
//else
//{
//*pplist= (*pplist)->next;
//}
//兩種情況可以合并，只有一個節(jié)點時，*pplist的next為空
else
{
SListNode* delNode = *pplist;
*pplist = delNode->next;
free(delNode);//釋放刪除節(jié)點的空間
}
}
//單鏈表查找
SListNode* SListFind(SListNode* plist, DataType x)
{
SListNode* cur = plist;
while (cur)
{
if (cur->data == x)
{
return cur;
}
else
{
cur = cur->next;
}
}
return NULL;
}
//任意位置的插入
//只能在pos的后面插入
void SListInsertAfter(SListNode* pos, DataType x)
{
assert(pos);//指針合法性校驗
SListNode* newNode = BuySListNode(x);
newNode->next = pos->next;
pos->next = newNode;
}
//任意位置的刪除
//只能刪除給定的pos后面的節(jié)點
void SListDeleteAfter(SListNode* pos)
{
assert(pos);
//1.鏈表有一個節(jié)點
if (NULL == pos->next)
{
return;
}
//2.鏈表有多個節(jié)點
else
{
SListNode* temp = pos->next;
pos->next = temp->next;
free(temp);
}
}
// 鏈表空間釋放
void SListDestroy(SListNode** pplist)
{
assert(pplist);//鏈表是否存在
//1.鏈表為空
if (NULL == *pplist)
{
return;
}
else
{
SListNode* cur = NULL;
while (*pplist)
{
cur = *pplist;
*pplist = (*pplist)->next;
free(cur);
}
}
}
main.c
程序入口，測試用例
#include"work.h"
void Test()
{
SListNode* node = NULL;//定義一個結構體指針
//尾插法插入五個節(jié)點
SListPushBack(&node, 1);
SListPushBack(&node, 2);
SListPushBack(&node, 3);
SListPushBack(&node, 4);
SListPushBack(&node, 5);
SListPrint(node);//遍歷打印
SListPushFront(&node, 0);//頭插一個節(jié)點
SListPrint(node);//遍歷打印
SListPopBack(&node);//尾刪最后一個節(jié)點
SListPrint(node);//遍歷打印
SListPopFront(&node);//頭刪第一個節(jié)點
SListPrint(node);//遍歷打印
printf("%p\n", SListFind(node, 4));//查找3在鏈表中的位置
printf("%p\n", SListFind(node, 99));//查找99在鏈表中的位置
SListInsertAfter(SListFind(node, 4), 99);//4后面插入一個節(jié)點99
SListPrint(node);//遍歷打印
SListDeleteAfter(SListFind(node, 4));//刪除4的下一個節(jié)點
SListPrint(node);//遍歷打印
}
int main()
{
Test();
system("pause");
return 0;
}
總結
以上為個人經驗，希望能給大家一個參考，也希望大家多多支持腳本之家。
相關文章
C++實現(xiàn)LeetCode(187.求重復的DNA序列)
這篇文章主要介紹了C++實現(xiàn)LeetCode(187.求重復的DNA序列),本篇文章通過簡要的案例,講解了該項技術的了解與使用,以下就是詳細內容,需要的朋友可以參考下2021-07-07
QML是一種描述性的腳本語言，文件格式以.qml結尾。語法格式非常像CSS（參考后文具體例子），但又支持javascript形式的編程控制。QtDesigner可以設計出·ui界面文件，但是不支持和Qt原生C++代碼的交互2022-08-08
C/C++ break和continue區(qū)別及使用方法
這篇文章主要介紹了C/C++ break和continue區(qū)別及使用方法的相關資料,需要的朋友可以參考下2017-07-07
這篇文章主要介紹了C語言實現(xiàn)的排列組合問題的通用算法、解決方法,本文使用C語言實現(xiàn)在程序中解決這個問題,需要的朋友可以參考下2014-08-08
斐波那契數列這一個大一上C語言就有的問題大家應該都不陌生,下面這篇文章主要給大家介紹了關于C語言新手練習題之求第n個斐波那契數的相關資料,文中通過圖文以及實例代碼介紹的非常詳細,需要的朋友可以參考下2022-11-11
c++中cin/cout與scanf/printf的區(qū)別比較
這篇文章主要介紹了c++中cin/cout與scanf/printf的區(qū)別比較,需要的朋友可以參考下2017-06-06
本文主要介紹了QT5?Thread線程，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2022-05-05
這篇文章主要為大家詳細介紹了C語言實現(xiàn)簡易版三子棋游戲，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-07-07
C++深入刨析優(yōu)先級隊列priority_queue的使用
最近我學習了C++中的STL庫中的優(yōu)先級隊列（priority_queue）容器適配器，對于優(yōu)先級隊列，我們不僅要會使用常用的函數接口，我們還有明白這些接口在其底層是如何實現(xiàn)的2022-08-08
本篇文章是對用C語言實現(xiàn)單鏈表的各種操作進行了詳細的分析介紹，需要的朋友參考下2013-05-05