目錄

零.必備知識

0.1 一級指針 && 二級指針

0.2 雙鏈表節(jié)點(diǎn)的成員列表

? ? ? ? a. 數(shù)據(jù)

? ? ? ? b. 后驅(qū)指針

? ? ? ? c. 前驅(qū)指針

0.3 動態(tài)內(nèi)存空間的開辟

一. 雙鏈表的實(shí)現(xiàn)與銷毀

? ? ? ? 1.1 節(jié)點(diǎn)的定義

????????1.2 雙向鏈表的初始化 && 創(chuàng)建新節(jié)點(diǎn)

????????1.3 尾插?

? ? ? ? 1.4 頭插?

? ? ? ? 1.5 尾刪?

? ? ? ? 1.6 頭刪

? ? ? ? 1.7 在指定位置之后插入數(shù)據(jù)?

? ? ? ? 1.8 刪除指定位置的數(shù)據(jù)?

? ? ? ? 1.9 銷毀雙鏈表

?二.雙鏈表源碼

List.h

List.c

零.必備知識

0.1 一級指針 && 二級指針

0.2 雙鏈表節(jié)點(diǎn)的成員列表

? ? ? ? a. 數(shù)據(jù)

? ? ? ? b. 后驅(qū)指針

? ? ? ? c. 前驅(qū)指針

0.3 動態(tài)內(nèi)存空間的開辟

一. 雙鏈表的實(shí)現(xiàn)與銷毀

此次實(shí)現(xiàn)的鏈表是帶頭雙向循環(huán)鏈表.如圖:

? ? ? ? 1.1 節(jié)點(diǎn)的定義

后驅(qū)節(jié)點(diǎn)指向?qū)懸粋€節(jié)點(diǎn).

前驅(qū)節(jié)點(diǎn)指向前一個節(jié)點(diǎn).

????????1.2 雙向鏈表的初始化 && 創(chuàng)建新節(jié)點(diǎn)

初始化是指:創(chuàng)建了一個哨兵節(jié)點(diǎn).

這個哨兵節(jié)點(diǎn)的作用是:避免雙向鏈表死循環(huán).

?

????????1.3 尾插?

貫穿本文的核心要點(diǎn)是:先修改新節(jié)點(diǎn)中前驅(qū),后驅(qū)指針的指向.再修改其余節(jié)點(diǎn)前驅(qū),后驅(qū)指針的指向.

? ? ? ? 1.4 頭插?

?

? ? ? ? 1.5 尾刪?

尾刪和接下來的頭刪,都是可以創(chuàng)建一個臨時指針來指向要刪除的節(jié)點(diǎn).

這樣看以來更直觀,更重要的是方便進(jìn)行空間的釋放.

?

? ? ? ? 1.6 頭刪

?

?

? ? ? ? 1.7 在指定位置之后插入數(shù)據(jù)?

在指定位置之后插入數(shù)據(jù):可以先實(shí)現(xiàn)一個查找函數(shù),來自己指定pos.

?

? ? ? ? 1.8 刪除指定位置的數(shù)據(jù)?

?

? ? ? ? 1.9 銷毀雙鏈表

?注意:此處傳入的是一級指針,并沒有真正的修改phead(哨兵位/頭節(jié)點(diǎn))中的值,如果要真正的銷毀雙鏈表,需要傳入二級指針.

那么為什么我傳的是一級指針呢?? 答案:保持傳入?yún)?shù)的一致性.

?文章來源地址http://www.zghlxwxcb.cn/news/detail-854886.html

?二.雙鏈表源碼

List.h

#define  _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

// 單個節(jié)點(diǎn)的定義
typedef int LTDateType;
typedef struct List
{
	LTDateType date;
	struct List* next; // 后驅(qū)節(jié)點(diǎn)
	struct List* prev; // 前驅(qū)節(jié)點(diǎn)
}List;
// 節(jié)點(diǎn)的創(chuàng)建
List* LTBuyNode(LTDateType x);
// 雙向鏈表的初始化
List* LTInit();
// 雙向鏈表的展示
void LTPrint(List* phead);
// 尾插-頭插
void LTPushBack(List* phead, LTDateType x);
void LTPushFront(List* phead, LTDateType x);
// 尾刪-頭刪
void LTPopBack(List* phead);
void LTPopFront(List* phead);
// 查找指定數(shù)據(jù)
List* LTFind(List* phead, LTDateType x);
// 在指定位置之后插入數(shù)據(jù)
void LTInsertAfter(List* pos, LTDateType x);
// 刪除指定位置的數(shù)據(jù)
void LTErase(List* phead, List* pos);
// 銷毀雙鏈表
void LTDestroy(List* phead);

List.c

#define  _CRT_SECURE_NO_WARNINGS
#include "List.h"
// 節(jié)點(diǎn)的創(chuàng)建
List* LTBuyNode(LTDateType x)
{
	List* newNode = (List*)malloc(sizeof(List));
	if (newNode == NULL) { // 創(chuàng)建失敗
		perror("malloc fail!");
		exit(1);
	}
	newNode->date = x;
	newNode->next = NULL;
	newNode->prev = NULL;
	return newNode;
}
// 雙向鏈表的初始化
List* LTInit()
{
	List* newNode = LTBuyNode(-1);
	newNode->next = newNode;
	newNode->prev = newNode;
	return newNode;
}
// 雙向鏈表的展示
void LTPrint(List* phead)
{
	assert(phead);
	List* pcur = phead->next;
	while (pcur != phead) {
		printf("%d->", pcur->date);
		pcur = pcur->next;
	}
	printf("\n");
}
// 尾插
void LTPushBack(List* phead, LTDateType x)
{
	assert(phead);
	// 創(chuàng)建新節(jié)點(diǎn)
	List* newNode = LTBuyNode(x);
	// 先更改新節(jié)點(diǎn)的前驅(qū)后驅(qū)指針
	newNode->next = phead;
	newNode->prev = phead->prev;

	// 更改其余節(jié)點(diǎn)的前驅(qū)后驅(qū)指針
	phead->prev->next = newNode;
	phead->prev = newNode;
}
// 頭插
void LTPushFront(List* phead, LTDateType x)
{
	assert(phead);
	List* newNode = LTBuyNode(x);
	// 更改newNode的前驅(qū)后驅(qū)指針
	newNode->next = phead->next;
	newNode->prev = phead;

	// 更改其余節(jié)點(diǎn)的指針指向
	phead->next->prev = newNode;
	phead->next = newNode;
}
// 尾刪
void LTPopBack(List* phead)
{
	assert(phead);
	List* pcur = phead->prev;
	// 更改要刪除的節(jié)點(diǎn)的前一個節(jié)點(diǎn)的指針指向
	pcur->prev->next = phead;
	
	// 更改哨兵位的指針指向
	phead->prev = pcur->prev;
	
	// 釋放尾節(jié)點(diǎn)
	free(pcur);
	pcur = NULL;
}
// 頭刪
void LTPopFront(List* phead)
{
	assert(phead);
	List* pcur = phead->next;
	
	phead->next = pcur->next;
	pcur->next->prev = phead;

	// 銷毀pcur節(jié)點(diǎn)
	free(pcur);
	pcur = NULL;
}
// 查找指定數(shù)據(jù)
List* LTFind(List* phead, LTDateType x)
{
	assert(phead);
	List* pcur = phead->next;
	while (pcur != phead) {
		if (pcur->date == x) {
			printf("找到了!\n");
			return pcur;
		}
		pcur = pcur->next;
	}
	printf("沒有找到!\n");
	return NULL;
}
// 在指定位置之后插入數(shù)據(jù)
void LTInsertAfter(List* pos, LTDateType x)
{
	assert(pos);
	List* newNode = LTBuyNode(x);

	// 修改新節(jié)點(diǎn)的指向
	newNode->next = pos->next;
	newNode->prev = pos;

	// 修改其余節(jié)點(diǎn)的指向
	pos->next->prev = newNode;
	pos->next = newNode;
}
// 刪除指定位置的數(shù)據(jù)
void LTErase(List* phead, List* pos)
{
	assert(phead && pos);

	pos->next->prev = pos->prev;
	pos->prev->next = pos->next;

	// 銷毀pos節(jié)點(diǎn)
	free(pos);
	pos = NULL;
}
// 銷毀雙鏈表
void LTDestroy(List* phead)
{
	assert(phead);
	List* pcur = phead->next;
	while (pcur != phead) {
		List* prev = pcur;
		pcur = pcur->next;
		// 銷毀 pcur的前一個節(jié)點(diǎn)
		free(prev);
		prev = NULL;
	}
	// 銷毀哨兵位
	free(phead);
	phead = NULL; // 但是沒有真正的改變哨兵位, 因?yàn)閭鞯氖且患壷羔?	              // 如果要真正的改變 phead的值,則需要傳遞二級指針
}

到了這里，關(guān)于[C語言][數(shù)據(jù)結(jié)構(gòu)][鏈表] 雙鏈表的從零實(shí)現(xiàn)!的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！