[C语言][数据结构][链表] 双链表的从零实现!

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

// 单个节点的定义
typedef int LTDateType;
typedef struct List
{
	LTDateType date;
	struct List* next; // 后驱节点
	struct List* prev; // 前驱节点
}List;
// 节点的创建
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);
// 查找指定数据
List* LTFind(List* phead, LTDateType x);
// 在指定位置之后插入数据
void LTInsertAfter(List* pos, LTDateType x);
// 删除指定位置的数据
void LTErase(List* phead, List* pos);
// 销毁双链表
void LTDestroy(List* phead);

List.c

#define  _CRT_SECURE_NO_WARNINGS
#include "List.h"
// 节点的创建
List* LTBuyNode(LTDateType x)
{
	List* newNode = (List*)malloc(sizeof(List));
	if (newNode == NULL) { // 创建失败
		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);
	// 创建新节点
	List* newNode = LTBuyNode(x);
	// 先更改新节点的前驱后驱指针
	newNode->next = phead;
	newNode->prev = phead->prev;

	// 更改其余节点的前驱后驱指针
	phead->prev->next = newNode;
	phead->prev = newNode;
}
// 头插
void LTPushFront(List* phead, LTDateType x)
{
	assert(phead);
	List* newNode = LTBuyNode(x);
	// 更改newNode的前驱后驱指针
	newNode->next = phead->next;
	newNode->prev = phead;

	// 更改其余节点的指针指向
	phead->next->prev = newNode;
	phead->next = newNode;
}
// 尾删
void LTPopBack(List* phead)
{
	assert(phead);
	List* pcur = phead->prev;
	// 更改要删除的节点的前一个节点的指针指向
	pcur->prev->next = phead;
	
	// 更改哨兵位的指针指向
	phead->prev = pcur->prev;
	
	// 释放尾节点
	free(pcur);
	pcur = NULL;
}
// 头删
void LTPopFront(List* phead)
{
	assert(phead);
	List* pcur = phead->next;
	
	phead->next = pcur->next;
	pcur->next->prev = phead;

	// 销毁pcur节点
	free(pcur);
	pcur = NULL;
}
// 查找指定数据
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;
}
// 在指定位置之后插入数据
void LTInsertAfter(List* pos, LTDateType x)
{
	assert(pos);
	List* newNode = LTBuyNode(x);

	// 修改新节点的指向
	newNode->next = pos->next;
	newNode->prev = pos;

	// 修改其余节点的指向
	pos->next->prev = newNode;
	pos->next = newNode;
}
// 删除指定位置的数据
void LTErase(List* phead, List* pos)
{
	assert(phead && pos);

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

	// 销毁pos节点
	free(pos);
	pos = NULL;
}
// 销毁双链表
void LTDestroy(List* phead)
{
	assert(phead);
	List* pcur = phead->next;
	while (pcur != phead) {
		List* prev = pcur;
		pcur = pcur->next;
		// 销毁 pcur的前一个节点
		free(prev);
		prev = NULL;
	}
	// 销毁哨兵位
	free(phead);
	phead = NULL; // 但是没有真正的改变哨兵位, 因为传的是一级指针
	              // 如果要真正的改变 phead的值,则需要传递二级指针
}

NMBG22

[C语言][数据结构][链表] 双链表的从零实现!

零.必备知识

一. 双链表的实现与销毁

1.1 节点的定义

1.2 双向链表的初始化 && 创建新节点

1.3 尾插

1.4 头插

1.5 尾删

1.6 头删

1.7 在指定位置之后插入数据

1.8 删除指定位置的数据

1.9 销毁双链表

二.双链表源码

List.h

List.c