C語言學習之鏈表的實現(xiàn)詳解

更新時間：2022年11月06日 14:56:19 作者：Fug_Lee

鏈表是一種物理存儲結構上非連續(xù)、非順序的存儲結構，數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈接次序實現(xiàn)的。這篇文章主要介紹了C語言中鏈表的實現(xiàn)，需要的可以參考一下

一、鏈表的概念

鏈表是一種物理存儲結構上非連續(xù)、非順序的存儲結構，數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈接次序實現(xiàn)的

二、鏈表的結構

（1）單鏈表

（2）帶頭結點的單鏈表

（3）雙向鏈表

（4）循環(huán)單鏈表

（5）雙向循環(huán)鏈表

注釋：

（1）無頭單向非循環(huán)鏈表：結構簡單，一般不會單獨用來存數(shù)據(jù)。實際中更多是作為其他數(shù)據(jù)結構的子結構，如哈希桶、圖的鄰接表等等。

（2）帶頭雙向循環(huán)鏈表：結構最復雜，一般用在單獨存儲數(shù)據(jù)。實際中使用的鏈表數(shù)據(jù)結構，都是帶頭雙向循環(huán)鏈表。另外這個結構雖然結構復雜，但是使用代碼實現(xiàn)以后會發(fā)現(xiàn)結構會帶來很多優(yōu)勢，實現(xiàn)反而簡單了。

三、順序表和鏈表的區(qū)別和聯(lián)系

（1）順序表：

優(yōu)點：空間連續(xù)，支持隨機訪問。

缺點：中間或前面部分的插入刪除時間復雜度為O（n），并且增容代價比較大。

（2）鏈表

優(yōu)點：任意位置插入刪除時間復雜度為O(1) 2.沒有增容問題，插入一個開辟一個空間。

缺點：以節(jié)點為單位存儲，不支持隨機訪問。

四、鏈表的實現(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é)點為第一個節(jié)點
	if (plist->head == NULL)
	{
		plist->head = s;
		return;
	}
	//O(n)
	SListNode* p = plist->head;
	//查找鏈表的尾部節(jié)點
	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é)點不存在.\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é)點
	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)雙鏈表只有頭結點,操作失敗.\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)雙鏈表只有頭結點,操作失敗.\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)鏈表只有頭結點，查找失敗.\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語言學習之鏈表的實現(xiàn)詳解的詳細內容，更多關于C語言鏈表的資料請關注腳本之家其它相關文章！

您可能感興趣的文章:

C++之Boost::array用法簡介
這篇文章主要介紹了C++之Boost::array用法簡介,較為詳細的分析了Boost::array中的常見用法,并用實例的形式予以總結歸納,需要的朋友可以參考下
2014-10-10
c語言標準庫中字符轉換函數(shù)和數(shù)字轉換函數(shù)
這篇文章主要介紹了c標準庫中字符轉換函數(shù)和數(shù)字轉換函數(shù),需要的朋友可以參考下
2014-04-04
C++實現(xiàn)LeetCode(169.求大多數(shù))
這篇文章主要介紹了C++實現(xiàn)LeetCode(169.求大多數(shù)),本篇文章通過簡要的案例,講解了該項技術的了解與使用,以下就是詳細內容,需要的朋友可以參考下
2021-08-08
Visual Studio Code運行C++代碼時顯示CLOCKS_PER_SEC未定義的問題及解決方法
這篇文章主要介紹了解決Visual Studio Code運行C++代碼時顯示CLOCKS_PER_SEC未定義的問題,本文給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下
2020-04-04
C 二分查找遞歸與非遞歸的實現(xiàn)代碼
C 二分查找遞歸與非遞歸的實現(xiàn)代碼，需要的朋友可以參考一下
2013-03-03
C++ Qt開發(fā)之使用QTcpSocket實現(xiàn)TCP網(wǎng)絡通信
Qt 是一個跨平臺C++圖形界面開發(fā)庫,利用Qt可以快速開發(fā)跨平臺窗體應用程序,本文主要為大家介紹了如何運用QTcpSocket組件實現(xiàn)基于TCP的網(wǎng)絡通信功能,需要的可以參考下
2024-03-03
C語言數(shù)據(jù)結構之線性表的鏈式存儲結構
線性表是最基本、最簡單、也是最常用的一種數(shù)據(jù)結構。線性表（linear list）是數(shù)據(jù)結構的一種，一個線性表是n個具有相同特性的數(shù)據(jù)元素的有限序列，這篇文章帶你學習下線性表的鏈式存儲結構
2021-11-11
Qt實現(xiàn)簡單TCP服務器
這篇文章主要為大家詳細介紹了Qt實現(xiàn)簡單TCP服務器，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下
2022-08-08
C++中atof?函數(shù)的介紹
這篇文章主要給大家分享的是C++中atof?函數(shù)的介紹，在?stdlib.h?中?atof?函數(shù),可用于將?char?字符串轉為?float?/?double?浮點數(shù)類型，想具體了解語法的小伙伴可以參考下面文章的內容，希望對大家有所幫助
2021-11-11
C語言實現(xiàn)簡易版三子棋游戲
這篇文章主要為大家詳細介紹了C語言實現(xiàn)簡易版三子棋游戲，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下
2020-07-07