1.版本一
由于节点之间的连接变多 所以我们最好提前将前驱节点和后继节点用变量保存下来 以免等下在进行节点之间的指向时出错文章来源:https://www.toymoban.com/news/detail-795717.html
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
// 节点类
typedef struct Node {
// 数据域
int data;
// 指针域
struct Node* next;
struct Node* pre;
}Node;// 别名
// 初始化链表
Node* initList() {
Node* list = (Node*)malloc(sizeof(Node));
list->data = 0;
list->next = NULL;
list->pre = NULL;
return list;
}
// 头插法
void headInsert(int data, Node* list) {
Node* node = (Node*)malloc(sizeof(Node));
Node* pre = list;
Node* next = list->next;
node->data = data;
pre->next = node;
node->pre = pre;
node->next = next;
if (list->data != 0) {
next->pre = node;
}
// 更新链表长度
list->data++;
}
// 尾插法
void tailInsert(int data, Node* list) {
// 为待插入节点分配内存
Node* node = (Node*)malloc(sizeof(Node));
// 获取待插入节点的前驱节点 前驱节点其实就是原来的尾节点
Node* pre = list->next;
while (pre->next) {
pre = pre->next;
}
Node* next = pre->next;
node->data = data;
pre->next = node;
node->pre = pre;
node->next = next;
// 更新链表长度
list->data++;
}
// 删除方法
bool delete(int data, Node* list) {
// 我们需要做的是删除指定节点值对应的第一个节点
Node* cur = list->next;
while (cur) {
// 如果一旦遇到符合指定节点值的节点的话 那么就执行相关操作
if (cur->data == data) {
// 需要先考虑头删、尾删和中间删以及删除之后链表为空四种情况 总结之后 我们可以发现尾删和删除之后链表为空同属一种情况 都是只需要设置一条线即可 即前驱指向后继 但是其他情况需要设置两条线 即前驱指向后继 后继指向前驱
cur->pre->next = cur->next;
if (cur->next) {
cur->next->pre = cur->pre;
}
free(cur);
list->data--;
return true;
}
cur = cur->next;
}
return false;
}
// 打印链表方法
void printList(Node* list) {
Node* cur = list->next;
while (cur) {
printf("%d ", cur->data);
cur = cur->next;
}
printf("\n");
}
int main() {
Node* list = initList();
headInsert(1, list);
headInsert(2, list);
headInsert(3, list);
tailInsert(4, list);
tailInsert(5, list);
printList(list);// 3 2 1 4 5
if (delete(5, list) == true) {
printf("删除成功\n");
}
else {
printf("删除失败\n");
}
printList(list);// 2 1 4 5
}
2.版本二(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->pre = NULL;
list->next = NULL;
return list;
}
// 索引越界的处理
void outOfBounds(int index) {
printf("索引为%d 索引越界了\n", 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* cur = (Node*)malloc(sizeof(Node));
// 获取待插入节点的前驱节点 如果是头插的话 那么就需要特殊处理了
Node* pre = index == 0 ? list : node(index - 1, list);
// 获取待插入节点的后继节点
Node* next = pre->next;
cur->data = data;
// 四种情况都要设置三条线
pre->next = cur;
cur->pre = pre;
cur->next = next;
if (next)
next->pre = cur;
// 无论执行的是哪一种情况 都需要更新链表长度
list->data++;
}
// 删除方法
int delete(int index, Node* list) {
// 我们需要将问题分成三种情况去讨论 一种情况是中间删除 一种情况是尾删 一种情况是头删 如果是中间删除的话 那么我们需要操作的指针有两条 分别是前驱节点的后继节点还有后继节点的前驱节点 如果是尾删的话 那么就需要操作一条 即前驱节点指向后继节点 如果是头删的话 那么需要操作两条 同中间删除一样 如果是删除之后链表为空的话 那么就归结到尾删的情况中去考虑即可 并且复用尾删的代码
Node* cur = node(index, list);
// 我们保存一下待删除节点的节点值
int delete = cur->data;
// 通过待删除节点获取到他的前驱节点以及后继节点
Node* pre = cur->pre;
Node* next = cur->next;
pre->next = next;
if (next)
next->pre = pre;
// 我们还要去释放一下cur的内存 同时也解决了从cur指出的两条指针
free(cur);
// 更新一下链表的长度
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;
}
// 清空链表之后链表长度为0
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;
while (cur) {
printf("%d ", cur->data);
cur = cur->next;
}
printf("\n");
}
// 定义一个主函数
int main() {
// 创建一个链表
Node* list = initList();
// 头部添加 尾部添加
add(0, 1, list);// 1
add(0, 2, list);// 2 1
add(0, 3, list);// 3 2 1
add(0, 4, list);// 4 3 2 1
add(size(list), 5, list);// 4 3 2 1 5
// 打印链表
printList(list);// 4 3 2 1 5
// 头部删除 尾部删除
delete(0, list);// 3 2 1 5
delete(size(list) - 1, list);// 3 2 1
// 打印链表
printList(list);// 3 2 1
// 获取头部元素
printf("%d\n", get(0, list));// 3
// 重置头部元素
printf("%d\n", set(0, 4, list));// 3
// 打印链表
printList(list);// 4 2 1
printf("%d\n", contains(4, list));// true
printf("%d\n", isEmpty(list));// false
// 清空链表
clear(list);
printf("%d\n", size(list));// 0
return 0;
}
测试结果显示 这个代码符合预期文章来源地址https://www.toymoban.com/news/detail-795717.html
到了这里,关于C语言实现双向链表的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!