C语言实现双向循环链表

本文介绍: 经过测试结果发现可以正确运行。

1.mj版本的双向循环链表(虚拟头节点)

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define ELEMENT_NOT_FOUND -1
// 设置一个节点类
typedef struct Node {
	// 数据域
	int data;
	// 指针域
	struct Node* pre;
	struct Node* next;
}Node;
// 初始化链表的方法
Node* initList() {
	Node* list = (Node*)malloc(sizeof(Node));
	list->data = 0;// 记录链表长度
	list->next = NULL;
	list->pre = NULL;
	return list;
}
// 索引越界方法
void outOfBounds(int index) {
	printf("索引为%d 索引越界了", index);
}
// 边界检查方法
void rangeCheck(int index, Node* list) {
	if (index < 0 || index >= list->data)
		outOfBounds(index);
}
// 针对添加方法的边界检查方法
void rangeCheckForAdd(int index, Node* list) {
	if (index < 0 || index > list->data)
		outOfBounds(index);
}
// 根据指定索引获取节点
Node* node(int index, Node* list) {
	// 对参数索引进行边界检查
	rangeCheck(index, list);
	Node* cur = list->next;
	for (int i = 0; i < index; ++i) {
		cur = cur->next;
	}
	return cur;
}
// 添加方法
void add(int index, int data, Node* list) {
	// 对参数索引进行边界检查
	rangeCheckForAdd(index, list);
	// 为待插入节点分配内存
	Node* n = (Node*)malloc(sizeof(Node));
	n->data = data;
	// 获取待插入节点的前驱节点 但是由于添加方法中包含这多种情况 所以需要进行分类讨论 如果执行的是头插操作的话 那么前驱节点就不能通过node方法获取了
	Node* pre = index == 0 ? list : node(index - 1, list);
	// 获取待插入节点的后继节点 但是如果是针对特殊情况的话 那么后继节点就不能够通过普通方式去获取了 而是得通过特殊方式去获取
	Node* next = list->data == 0 ? n : pre->next;
	// 我们需要分成三种情况进行讨论 如果我们进行的中间插入的操作的话 那么操作的有四条线 如果我们执行的是尾插操作的话 那么我们操作的就有四条线 如果我们进行的是头插操作的话 那么我们操作的就有四条线 如果我们是往空链表执行插入操作的话 那么我们操作的主要有四条线
	pre->next = n;
	n->pre = pre;
	next->pre = n;
	n->next = next;
	// 更新链表长度
	list->data++;
}
// 删除方法
int delete(int index, Node* list) {
	// 获取指定索引处的节点
	Node* n = node(index, list);
	// 获取待删除节点的节点值
	int delete = n->data;
	// 获取待删除节点的前驱节点
	Node* pre = n->pre;
	// 获取待删除节点的后继节点 如果是特殊情况的话 那么就需要设置后继节点为空值
	Node* next = list->data == 1 ? NULL : n->next;
	// 我们需要分成三种情况进行讨论 一种是中间删除 即将前驱节点指向后继节点 一种是尾删 即将前驱节点指向后继节点 一种是头删 即将前驱节点指向后继节点 一种是删除之后链表为空 让前驱节点指向为空
	pre->next = next;
	if(next)
		next->pre = pre;
	// 反正不管执行的是那种情况 都需要更新链表长度
	list->data--;
	return delete;
}
// 获取指定节点值的位置
int indexOf(int data, Node* list) {
	Node* cur = list->next;
	for (int i = 0; i < list->data; ++i) {
		if (cur->data == data)return i;
		cur = cur->next;
	}
	return ELEMENT_NOT_FOUND;
}
// 获取指定位置处的节点值
int get(int index, Node* list) {
	return node(index, list)->data;
}
// 重置指定位置处的节点值
int set(int index, int newData, Node* list) {
	int data = node(index, list)->data;
	node(index, list)->data = newData;
	return data;
}
// 清空方法
void clear(Node* list) {
	Node* cur = list->next;
	Node* next;
	for (int i = 0; i < list->data; ++i) {
		next = cur->next;
		free(cur);
		cur = next;
	}
	list->data = 0;
}
// 判断链表中是否包含指定节点值
bool contains(int data, Node* list) {
	return indexOf(data, list) != ELEMENT_NOT_FOUND;
}
// 判断链表是否为空
bool isEmpty(Node* list) {
	return list->data == 0;
}
// 获取链表长度
int size(Node* list) {
	return list->data;
}
// 打印链表
void printList(Node* list) {
	Node* cur = list->next;
	for (int i = 0; i < list->data; ++i) {
		printf("%d ", cur->data);
		cur = cur->next;
	}
	printf("n");
}
// 定义一个主函数
int main() {
	// 创建一个链表
	Node* list = initList();
	// 对链表进行头部和尾部添加操作
	add(0, 1, list);// 1
	add(size(list), 2, list);// 1 2
	// 打印链表
	printList(list);// 1 2
	// 对链表进行删除操作
	delete(size(list) - 1, list);// 1
	// 打印链表
	printList(list);// 1
	// 接着在对链表进行添加操作
	add(0, 2, list);// 2 1
	add(0, 3, list);// 3 2 1
	// 打印链表
	printList(list);// 3 2 1
	printf("%dn", get(0, list));// 3
	printf("%dn", set(0, 6, list));// 3
	printList(list);// 6 2 1
	printf("%dn", contains(6, list));// 1
	printf("%dn", isEmpty(list));// 0
	clear(list);
	printf("%dn", size(list));// 0
	return 0;
}