C語言中單鏈表的基本操作(創(chuàng)建、銷毀、增刪查改等)
更新時間：2023年02月05日 10:20:16 作者：安河橋畔
這篇文章主要介紹了C語言中單鏈表的基本操作(創(chuàng)建、銷毀、增刪查改等)，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教
鏈表分類
鏈表主要有下面三種分類方法：
- 單向或者雙向
- 帶頭或者不帶頭
- 循環(huán)或者非循環(huán)綜合來看鏈表有八種類型，本文主要針對的是不帶頭節(jié)點的非循環(huán)單鏈表。
單鏈表的介紹
typedef struct SListNode
{
DataType data;//數(shù)據(jù)域
struct SListNode *next;//結(jié)構(gòu)體指針，指向下一個節(jié)點
}SListNode;//類型別名
如圖
鏈表的每一個節(jié)點由數(shù)據(jù)域和指針域構(gòu)成，數(shù)據(jù)域存放數(shù)據(jù)，指針域中的指針指向下一個節(jié)點。
plist表示鏈表的指針，指向鏈表的第一個節(jié)點，最后一個節(jié)點的指針為空。
單鏈表的基本操作
創(chuàng)建
創(chuàng)建單鏈表有幾點需注意：
- 鏈表與順序表的區(qū)別是，順序表是物理空間上連續(xù)的，而鏈表只在邏輯上連續(xù)，所以鏈表申請空間時是使用一個申請一個，順序表則是一次申請一段空間，空間不足時進行擴容。
- 如果在棧上申請空間，在函數(shù)調(diào)用結(jié)束后會釋放，所以需要在堆區(qū)申請空間。
- 每次申請一個節(jié)點都要存入數(shù)據(jù)，所以鏈表總是滿的，而順序表則可能有一段空間沒有利用。
- 函數(shù)的返回值是指向節(jié)點的結(jié)構(gòu)體類型的指針
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)
{
//改變指針指向，參數(shù)傳二級指針
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é)點
- 遍歷找到最后一個節(jié)點的前驅(qū)結(jié)點prev
- 令prev的next指向NULL
- 釋放原來最后一個節(jié)點申請的空間
注意事項：
- 區(qū)分鏈表為空、單個結(jié)點、多個結(jié)點各種情況
- 不能找到最后一個節(jié)點并將其置空，而是要找到其前驅(qū)節(jié)點，斷開與最后一個節(jié)點的連接
- 刪除節(jié)點后要釋放空間，避免內(nèi)存泄漏
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)結(jié)束時cur指向最后一個節(jié)點
}
//cur= NULL;//這里不能寫cur=NULL,需要找到cur的前一個節(jié)點，將其next置空\
否則前一個結(jié)點的next依然指向原來的最后一個節(jié)點
prev->next = NULL;//prev成為最后一個節(jié)點
free(cur);//釋放原來最后一個節(jié)點的空間
}
頭刪
頭刪的操作步驟：
- 保存第一個節(jié)點的指針信息
- 令*pplist指向第二個節(jié)點
- 釋放原來的第一個節(jié)點的空間
同樣的，頭刪也要注意保存原來第一個節(jié)點的位置，否則*pplist指向改變后，原來的第一個節(jié)點就找不到了，會無法釋放空間造成內(nèi)存泄漏。
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
頭文件包含，函數(shù)聲明，定義結(jié)構(gòu)體
#pragma once
#include<stdio.h>
#include<Windows.h>
#include<assert.h>
#include<assert.h>
typedef int DataType;
typedef struct SListNode
{
DataType data;//數(shù)據(jù)域
struct SListNode *next;//結(jié)構(gòu)體指針，指向下一個節(jié)點
}SListNode;//類型別名
//函數(shù)聲明
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
各操作函數(shù)的具體實現(xiàn)
#include"work.h"
//鏈表與順序表的區(qū)別是，順序表是物理空間上連續(xù)的
//而鏈表只在邏輯上連續(xù)，所以鏈表申請空間時是使用一個申請一個
//順序表則是一次申請一段空間
SListNode* BuySListNode(DataType x)
{
//若在棧申請內(nèi)存函數(shù)調(diào)用結(jié)束后會釋放，所以使用動態(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)
{
//改變指針指向，參數(shù)傳二級指針
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)結(jié)束時cur指向最后一個節(jié)點
}
//cur= NULL;//這里不能寫cur=NULL,需要找到cur的前一個節(jié)點，將其next置空\
否則前一個結(jié)點的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é)構(gòu)體指針
//尾插法插入五個節(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;
}
總結(jié)
以上為個人經(jīng)驗，希望能給大家一個參考，也希望大家多多支持腳本之家。
相關文章
這篇文章主要通過一些示例為大家詳細介紹一下C語言中的線程信號控制，文中的示例代碼講解詳細，對我們深入了解C語言有一定的幫助，感興趣的可以學習一下2023-02-02
下面小編就為大家?guī)硪黄獪\談C++阻止類被實例化詳解。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2021-09-09
程序調(diào)???的編程技巧稱為遞歸 recursion）函數(shù)??調(diào)???就是遞歸，你也可以理解成是?種嵌套結(jié)構(gòu)，但遞歸分為倆部分，第?是“遞”，進?嵌套結(jié)構(gòu)。第?是”歸“，最終會?步?步返回。第?次接觸遞歸都會很懵，慢慢理解這個過程就明?了2022-06-06
本文給大家簡單介紹了下C語言中的條件判斷語句的語法和用法示例，非常簡潔實用，有需要的小伙伴可以參考下2017-10-10
Qt中實現(xiàn)自定義信號與槽函數(shù)，信號用于發(fā)送并觸發(fā)槽函數(shù)，槽函數(shù)則是具體的功能實現(xiàn)，本文就詳細的介紹一下如何使用，感興趣的可以了解一下2021-11-11
這篇文章主要為大家詳細介紹了C語言中的動態(tài)內(nèi)存分配，文中的示例代碼講解詳細，對我們學習C語言有一定的幫助，需要的可以參考一下2022-06-06
命名空間是C++中用來避免命名沖突的一種機制,本文主要介紹了C++ 命名空間避免命名沖突的實現(xiàn),具有一定的參考價值,感興趣的可以了解一下2024-03-03
這篇文章主要介紹了C語言模擬實現(xiàn)atoi函數(shù)的實例詳解的相關資料,atoi函數(shù)，主要功能是將一個字符串轉(zhuǎn)變?yōu)檎麛?shù)，這里就實現(xiàn)這樣的函數(shù)，需要的朋友可以參考下2017-08-08
本文給大家介紹的是C++多線程編程，由于C++本身沒有多線程機制，在windows下我們使用調(diào)用SDK win32 api來實現(xiàn)，示例都很簡單，講解的也很詳細，推薦給大家2021-09-09
C++獲取類的成員函數(shù)的函數(shù)指針詳解及實例代碼
這篇文章主要介紹了C++獲取類的成員函數(shù)的函數(shù)指針詳解及實例代碼的相關資料,需要的朋友可以參考下2017-02-02