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("%d\n", get(0, list));// 3
printf("%d\n", set(0, 6, list));// 3
printList(list);// 6 2 1
printf("%d\n", contains(6, list));// 1
printf("%d\n", isEmpty(list));// 0
clear(list);
printf("%d\n", size(list));// 0
return 0;
}
经过测试 结果发现可以正确运行
