C語言學(xué)習(xí)之鏈表的實現(xiàn)詳解
更新時間：2022年11月06日 14:56:19 作者：Fug_Lee
鏈表是一種物理存儲結(jié)構(gòu)上非連續(xù)、非順序的存儲結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈接次序?qū)崿F(xiàn)的。這篇文章主要介紹了C語言中鏈表的實現(xiàn)，需要的可以參考一下
一、鏈表的概念
鏈表是一種物理存儲結(jié)構(gòu)上非連續(xù)、非順序的存儲結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈接次序?qū)崿F(xiàn)的
二、鏈表的結(jié)構(gòu)
（1）單鏈表
（2）帶頭結(jié)點(diǎn)的單鏈表
（3）雙向鏈表
（4）循環(huán)單鏈表
（5）雙向循環(huán)鏈表
注釋：
（1）無頭單向非循環(huán)鏈表：結(jié)構(gòu)簡單，一般不會單獨(dú)用來存數(shù)據(jù)。實際中更多是作為其他數(shù)據(jù)結(jié)構(gòu)的子結(jié)構(gòu)，如哈希桶、圖的鄰接表等等。
（2）帶頭雙向循環(huán)鏈表：結(jié)構(gòu)最復(fù)雜，一般用在單獨(dú)存儲數(shù)據(jù)。實際中使用的鏈表數(shù)據(jù)結(jié)構(gòu)，都是帶頭雙向循環(huán)鏈表。另外這個結(jié)構(gòu)雖然結(jié)構(gòu)復(fù)雜，但是使用代碼實現(xiàn)以后會發(fā)現(xiàn)結(jié)構(gòu)會帶來很多優(yōu)勢，實現(xiàn)反而簡單了。
三、順序表和鏈表的區(qū)別和聯(lián)系
（1）順序表：
優(yōu)點(diǎn)： 空間連續(xù)，支持隨機(jī)訪問。
缺點(diǎn)： 中間或前面部分的插入刪除時間復(fù)雜度為O（n），并且增容代價比較大。
（2）鏈表
優(yōu)點(diǎn)： 任意位置插入刪除時間復(fù)雜度為O(1) 2.沒有增容問題，插入一個開辟一個空間。
缺點(diǎn)： 以節(jié)點(diǎn)為單位存儲，不支持隨機(jī)訪問。
四、鏈表的實現(xiàn)
（1）單鏈表的增刪查找等操作
#pragma once
#include"common.h"
typedef struct SListNode
{
ElemType data;
struct SListNode* next;
}SListNode;
typedef struct SList
{
SListNode* head;
}SList;
///
///
//單鏈表的函數(shù)接口聲明
void SListInit(SList* plist);
static SListNode* _Buynode(ElemType x);
void SListPushBack(SList* plist, ElemType item);//1
void SListPushFront(SList* plist, ElemType item);//2
void SListShow(SList* plist);//3
void SListPopBack(SList* plist);//4
void SListPopFront(SList* plist);//5
void SListInsertVal(SList* plist, ElemType val);//7
void SqListDeleteByVal(SList* plist, ElemType val);//9
SListNode* SListFind(SList* plist, ElemType key);//10
size_t SListLength(SList* plist);//11
void SListSort(SList* plist);//13
void SListReverse(SList* plist);//14
void SListClear(SList* plist);//15
void SListDestroy(SList* plist);
///
///
//單鏈表的函數(shù)接口實現(xiàn)
void SListInit(SList* plist)
{
plist->head = NULL;
}
static SListNode* _Buynode(ElemType x)
{
SListNode* s = (SListNode*)malloc(sizeof(SListNode));
assert(s != NULL);
s->data = x;
s->next = NULL;
return s;
}
//1
void SListPushBack(SList* plist, ElemType item)
{
assert(plist != NULL);
SListNode* s = _Buynode(item);
//插入的節(jié)點(diǎn)為第一個節(jié)點(diǎn)
if (plist->head == NULL)
{
plist->head = s;
return;
}
//O(n)
SListNode* p = plist->head;
//查找鏈表的尾部節(jié)點(diǎn)
while (p->next != NULL)
{
p = p->next;
}
p->next = s;
}
//2
void SListPushFront(SList* plist, ElemType item)
{
assert(plist != NULL);
SListNode* s = _Buynode(item);
s->next = plist->head;
plist->head = s;
}
//3
void SListShow(SList* plist)
{
assert(plist != NULL);
SListNode* p = plist->head;
while (p != NULL)
{
printf("%d-->", p->data);
p = p->next;
}
printf("Over.\n");
}
//4
void SListPopBack(SList* plist)
{
assert(plist != NULL);
SListNode* p = plist->head;
if (plist->head == NULL)
{
printf("單鏈表為空，輸出失敗!\n");
return;
}
if (p->next == NULL)
{
plist->head = NULL;
return;
}
SListNode* prev = NULL;
while (p->next != NULL)
{
prev = p;
p = p->next;
}
prev->next = NULL;
free(p);
}
//5
void SListPopFront(SList* plist)
{
assert(plist != NULL);
SListNode* p = plist->head;
if (plist->head == NULL)
{
printf("單鏈表為空，輸出失敗!\n");
return;
}
plist->head = p->next;
free(p);
}
//6
//7
void SListInsertVal(SList* plist, ElemType val)
{
assert(plist != NULL);
SListNode* prev = NULL;
SListNode* p = plist->head;
SListNode* s = _Buynode(val);
while (p != NULL && val > p->data)
{
prev = p;
p = p->next;
}
if (prev == NULL)
{
s->next = p;
plist->head = s;
}
else
{
s->next = prev->next;
prev->next = s;
}
}
//10
SListNode* SListFind(SList* plist, ElemType key)
{
assert(plist != NULL);
SListNode* p = plist->head;
while (p != NULL && p->data != key)
p = p->next;
return p;
}
//9
void SqListDeleteByVal(SList* plist, ElemType val)
{
assert(plist != NULL);
SListNode* prev = NULL;
SListNode* p = SListFind(plist, val);
if (p == NULL)
{
printf("要刪除的節(jié)點(diǎn)不存在.\n");
return;
}
if (p == plist->head)
plist->head = p->next;
else
{
prev = plist->head;
while (prev->next != p)
prev = prev->next;
//刪除
prev->next = p->next;
}
free(p);
}
//11
size_t SListLength(SList* plist)
{
assert(plist != NULL);
size_t len = 0;
SListNode* p = plist->head;
while (p != NULL)
{
len++;
p = p->next;
}
return len;
}
//13
void SListSort(SList* plist)
{
assert(plist != NULL);
SListNode* p = plist->head->next;
SListNode* q, * t, * prev = NULL;
plist->head->next = NULL; //斷開鏈表
t = plist->head;
while (p != NULL)
{
q = p->next;
while (t != NULL && p->data > t->data)
{
prev = t;
t = t->next;
}
if (prev == NULL)
{
p->next = plist->head;
plist->head = p;
}
else //if(prev->next!=NULL)
{
p->next = prev->next;
prev->next = p;
}
p = q;
t = plist->head;
}
}
//14
void SListReverse(SList* plist)
{
assert(plist != NULL);
SListNode* p = plist->head->next;
SListNode* q;
if (p->next == NULL)
return;
//斷開第一個節(jié)點(diǎn)
plist->head->next = NULL;
while (p != NULL)
{
q = p->next;
p->next = plist->head;
plist->head = p;
p = q;
}
}
//15
void SListClear(SList* plist)
{
assert(plist != NULL);
SListNode* p = plist->head;
while (p != NULL)
{
plist->head = p->next;
free(p);
p = plist->head;
}
}
void SListDestroy(SList* plist)
{
SListClear(plist);
plist->head = NULL;
}
```c
（2）帶頭的雙循環(huán)鏈表的實現(xiàn)
#pragma once
#include"common.h"
/
//帶頭的雙循環(huán)鏈表
typedef struct DCListNode
{
ElemType data;
struct DCListNode* next;
struct DCListNode* prev;
}DCListNode;
typedef struct DCList
{
DCListNode* head;
}DCList;
static DCListNode* _Buydnode(ElemType x);
void DCListInit(DCList* plist);
void DCListDestroy(DCList* plist);
void DCListPushBack(DCList* plist, ElemType x);//1
void DCListPushFront(DCList* plist, ElemType x);//2
void DCListShow(DCList* plist);//3
void DCListPopBack(DCList* plist);//4
void DCListPopFront(DCList* plist);//5
void DCListInsertByVal(DCList* plist, ElemType val);//7
void DCListDeleteByVal(DCList* plist, ElemType val);//9
size_t DCListLength(DCList* plist);//11
void DCListSort(DCList* plist);//13
void DCListReverse(DCList* plist);//14
void DCListClear(DCList* plist);//15
DCListNode* DCListFind(DCList* plist, ElemType key);//10
static DCListNode* _Buydnode(ElemType x)
{
DCListNode* s = (DCListNode*)malloc(sizeof(DCListNode));
assert(s != NULL);
s->data = x;
s->next = s->prev = s;
return s;
}
void DCListInit(DCList* plist)
{
plist->head = _Buydnode(0);
}
//1
void DCListPushBack(DCList* plist, ElemType x)
{
assert(plist != NULL);
DCListNode* s = _Buydnode(x);
s->prev = plist->head->prev;
s->prev->next = s;
s->next = plist->head;
plist->head->prev = s;
}
//2
void DCListPushFront(DCList* plist, ElemType x)
{
assert(plist != NULL);
DCListNode* s = _Buydnode(x);
s->next = plist->head->next;
s->next->prev = s;
plist->head->next = s;
s->prev = plist->head;
}
//3
void DCListShow(DCList* plist)
{
assert(plist != NULL);
DCListNode* p = plist->head->next;
while (p != plist->head)
{
printf("%d->", p->data);
p = p->next;
}
printf("Over.\n");
}
//4
void DCListPopBack(DCList* plist)
{
assert(plist != NULL);
DCListNode* p = plist->head->prev;
if (plist->head->next == plist->head)
//if(p == plist->head)
{
printf("循環(huán)雙鏈表只有頭結(jié)點(diǎn),操作失敗.\n");
return;
}
plist->head->prev = p->prev;
p->prev->next = plist->head;
free(p);
}
//5
void DCListPopFront(DCList* plist)
{
assert(plist != NULL);
DCListNode* p = plist->head->next;
if (p == plist->head)
{
printf("循環(huán)雙鏈表只有頭結(jié)點(diǎn),操作失敗.\n");
return;
}
plist->head->next = p->next;
p->next->prev = plist->head;
free(p);
}
//7
void DCListInsertByVal(DCList* plist, ElemType val)
{
assert(plist != NULL);
DCListNode* p = plist->head->next;
while (p != plist->head && p->data < val)
{
p = p->next;
}
DCListNode* s = _Buydnode(val);
s->next = p;
s->prev = p->prev;
p->prev->next = s;
p->prev = s;
}
//9
void DCListDeleteByVal(DCList* plist, ElemType val)
{
assert(plist != NULL);
DCListNode* p = DCListFind(plist, val);
if (p == NULL)
return;
p->next->prev = p->prev;
p->prev->next = p->next;
free(p);
}
//10
DCListNode* DCListFind(DCList* plist, ElemType key)
{
assert(plist != NULL);
DCListNode* p = plist->head->next;
if (p == plist->head)
{
printf("雙循環(huán)鏈表只有頭結(jié)點(diǎn)，查找失敗.\n");
return 0;
}
while (p != plist->head && p->data != key)
{
p = p->next;
}
if (p != plist->head)
return p;
return NULL;
}
//11
size_t DCListLength(DCList* plist)
{
assert(plist != NULL);
size_t len = 0;
DCListNode* p = plist->head->next;
while (p != plist->head)
{
len++;
p = p->next;
}
return len;
}
//13
void DCListSort(DCList* plist)
{
assert(plist != NULL);
DCListNode* p = plist->head->next;
DCListNode* q = p->next;
//斷開鏈表
p->next = plist->head;
plist->head->prev = p;
while (q != plist->head)
{
p = q;
q = q->next;
//尋找p插入的位置
DCListNode* t = plist->head->next;
while (t != plist->head && t->data < p->data)
t = t->next;
p->next = t;
p->prev = t->prev;
p->next->prev = p;
p->prev->next = p;
p = q;
}
}
//14
void DCListReverse(DCList* plist)
{
assert(plist != NULL);
DCListNode* p = plist->head->next;
DCListNode* q = p->next;
//斷開鏈表
p->next = plist->head;
plist->head->prev = p;
while (q != plist->head)
{
p = q;
q = q->next;
p->next = plist->head->next;
p->prev = plist->head;
p->next->prev = p;
p->prev->next = p; //plist->head->next = p;
}
}
//15
void DCListClear(DCList* plist)
{
assert(plist != NULL);
DCListNode* p = plist->head->next;
while (p != plist->head)
{
p->next->prev = p->prev;
p->prev->next = p->next;
free(p);
p = plist->head->next;
}
}
void DCListDestroy(DCList* plist)
{
DCListClear(plist);
free(plist->head);
plist->head = NULL;
}
以上就是C語言學(xué)習(xí)之鏈表的實現(xiàn)詳解的詳細(xì)內(nèi)容，更多關(guān)于C語言鏈表的資料請關(guān)注腳本之家其它相關(guān)文章！
相關(guān)文章
這篇文章主要介紹了C語言實現(xiàn)牛頓迭代法解方程詳解的相關(guān)資料,需要的朋友可以參考下2017-03-03
C語言使用ffmpeg實現(xiàn)單線程異步的視頻播放器
這篇文章主要為大家詳細(xì)介紹了C語言如何使用ffmpeg實現(xiàn)單線程異步的視頻播放器功能，文中的示例代碼講解詳細(xì)，感興趣的小伙伴可以嘗試一下2022-12-12
C++相較于Java，Python 并沒有提供的字符串分割的函數(shù)split，因此需要自己進(jìn)行編寫，本文主要介紹了C++如何切割String對象的方法，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2022-05-05
這篇文章主要介紹了C++無符號整數(shù)溢出探究,本文主要探討C/C++中無符號整數(shù)超過范圍后的計算問題，本文給大家介紹的非常詳細(xì)，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值，需要的朋友可以參考下2022-06-06
這篇文章主要為大家介紹了switch語句，switch語句是我們常見會用到的結(jié)構(gòu)，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪2022-06-06
這篇文章主要為大家詳細(xì)介紹了C++設(shè)計模式之享元模式Flyweight，具有一定的參考價值，感興趣的小伙伴們可以參考一下2018-04-04
這篇文章主要為大家詳細(xì)介紹了C語言實現(xiàn)火車票管理系統(tǒng)，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-03-03
詳解C/C++ Linux出錯處理函數(shù)(strerror與perror)的使用
我們知道，系統(tǒng)函數(shù)調(diào)用不能保證每次都成功，必須進(jìn)行出錯處理，這樣一方面可以保證程序邏輯正常，另一方面可以迅速得到故障信息。本文主要為大家介紹兩個出錯處理函數(shù)(strerror、perror)的使用，需要的可以參考一下2023-01-01
本文詳細(xì)介紹了如何使用C語言編寫一個簡單的TCP服務(wù)器,包括創(chuàng)建套接字、綁定IP和端口、監(jiān)聽連接請求、接受客戶端連接、數(shù)據(jù)接收與發(fā)送以及關(guān)閉套接字等步驟,最后通過一個簡單的示例展示了TCP服務(wù)器的基本實現(xiàn)過程2024-10-10
c 調(diào)用python出現(xiàn)異常的原因分析
本篇文章是對使用c語言調(diào)用python出現(xiàn)異常的原因進(jìn)行了詳細(xì)的分析介紹，需要的朋友參考下2013-05-05