一.前言
嗨嗨嗨,大家好久不见!前面我们已经通过数组实现数据的增删查改、单链表实现数据的增删查改,现在让我们尝试一下使用双链表实现数据的增删查改吧!
二.正文
如同往常一样,对于稍微大点的项目来说,我们使用多文件操作更好一些。
List.h
#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
typedef int DataType;
struct ListNode
{DataType data;struct ListNode* prev;struct ListNode* next;
};
typedef struct ListNode ListNode;
void ListInit(ListNode** pphead);//双向链表初始化
void ListDestroy(ListNode* phead);//双向链表销毁
void ListPrint(ListNode* phead);//双向链表打印
void ListPushBack(ListNode* phead, DataType x);//双向链表尾部插入节点
void ListPushFront(ListNode* phead, DataType x);//双向链表第一个有效节点前插入节点(即哨兵位的后一个节点为第一个有效节点)
void ListPopBack(ListNode* phead);//双向链表删除尾部节点
void ListPopFront(ListNode* phead);//双向链表删除第一个有效节点
void ListInsert(ListNode* pos, DataType x);//双向链表指定位置之后插入节点
void ListErase(ListNode* pos);//双向链表指定位置之后删除节点
ListNode* ListFind(ListNode* phead, DataType x);//查找目标节点
我们首先定义了这个项目的头文件,并把其他函数实现过程中可能使用的头文件包含在List.h中,这样就可以方便代码的维护,并且减少冗余的代码。
这是我们的双向链表结构体的定义:
struct ListNode
{DataType data;struct ListNode* prev;struct ListNode* next;
};
和单链表区分的话,那就是单链表定义的结构体中没有指向前一个节点的prev。
下面是我们在实现整个项目中,各种功能的罗列,就类似于书的目录一样。
void ListInit(ListNode** pphead);//双向链表初始化
void ListDestroy(ListNode* phead);//双向链表销毁
void ListPrint(ListNode* phead);//双向链表打印
void ListPushBack(ListNode* phead, DataType x);//双向链表尾部插入节点
void ListPushFront(ListNode* phead, DataType x);//双向链表第一个有效节点前插入节点(即哨兵位的后一个节点为第一个有效节点)
void ListPopBack(ListNode* phead);//双向链表删除尾部节点
void ListPopFront(ListNode* phead);//双向链表删除第一个有效节点
void ListInsert(ListNode* pos, DataType x);//双向链表指定位置之后插入节点
void ListErase(ListNode* pos);//双向链表指定位置之后删除节点
ListNode* ListFind(ListNode* phead, DataType x);//查找目标节点
List.c
#include"List.h"
ListNode* ListBuyNode(DataType x)
{ListNode* node = (ListNode*)malloc(sizeof(ListNode));if (node == NULL){perror("malloc fail!");return NULL;}node->next = node;//值得注意的是在创造新节点的时候,双向链表和单链表不同的是,单链表的next要指向NULLnode->prev = node;//而双向链表需要前后指针,即prev和next都要指向自己,构成循环。node->data = x;return node;
}
void ListInit(ListNode** pphead)
{*pphead = ListBuyNode(0);
}
void ListPushBack(ListNode* phead,DataType x)
{assert(phead);//双向链表的哨兵位phead不可能为NULL,如果phead都是NULL了,那么这个链表就不是双向链表。ListNode* newnode = ListBuyNode(x);newnode->next = phead;newnode->prev = phead->prev;phead->prev-> next = newnode;phead->prev = newnode;
}
void ListPrint(ListNode* phead)
{ListNode* pcur = phead->next;while (pcur != phead){printf("%d->", pcur->data);pcur = pcur->next;}printf("\n");
}
void ListPushFront(ListNode* phead,DataType x)
{assert(phead);ListNode* newnode = ListBuyNode(x);newnode->next = phead->next;newnode->prev = phead;phead->next->prev = newnode;phead->next = newnode;
}
void ListPopBack(ListNode* phead)
{assert(phead && phead->next != phead);ListNode* del = phead->prev;del->prev->next = phead;phead->prev = del->prev;free(del);del = NULL;
}
void ListPopFront(ListNode* phead)
{assert(phead&&phead->next!=phead);ListNode* del = phead->next;phead->next = del->next;del->next->prev = phead;free(del);del = NULL;
}
ListNode* ListFind(ListNode* phead,DataType x)
{ListNode* pcur = phead->next;while (pcur != phead){if (pcur->data == x){return pcur;}pcur = pcur->next;}return NULL;
}
void ListInsert(ListNode* pos,DataType x)
{ListNode* newnode = ListBuyNode(x);newnode->prev = pos;newnode->next = pos->next;pos->prev = newnode;pos->next = newnode;
}
void ListErase(ListNode* pos)
{pos->prev->next = pos->next;pos->next->prev = pos->prev;free(pos);pos = NULL;
}
void ListDestroy(ListNode* phead)//值得注意的是因为这里我们传的的是一级指针,
//所以在这里phead的改变,不会影响实参plist的改变,因此在主函数中我们需要主动让plist=NULL。
//在这里我们也可以传二级指针ListNode** pphead,这样*pphead的改变就可以影响实参plist的改变了。
{ListNode* pcur = phead;ListNode* next = pcur->next;while (pcur != phead){free(pcur);pcur = next;next = next->next;}free(phead);
}
上面的代码中,个别函数有些地方的关键点我有注释,有兴趣的小伙伴可以看一下。
test.c
#include"List.h"
//void test1()//测试双向链表初始化和创造节点
//{
// ListNode* plist = NULL;
// ListInit(&plist);
//}
//void test2()//测试双向链表尾插节点以及双向链表的打印
//{
// ListNode* plist = NULL;
// ListInit(&plist);
// ListPushBack(plist, 1);
// ListPushBack(plist, 2);
// ListPushBack(plist, 3);
// ListPushBack(plist, 4);
// ListPrint(plist);
//}
//void test3()//测试打印双向链表
//{
// ListNode* plist = NULL;
// ListInit(&plist);
// ListPushFront(plist, 1);
// ListPushFront(plist, 2);
// ListPushFront(plist, 3);
// ListPushFront(plist, 4);
// ListPrint(plist);
//}
//void test4()//测试尾删
//{
// ListNode* plist = NULL;
// ListInit(&plist);
// ListPushBack(plist, 1);
// ListPushBack(plist, 2);
// ListPushBack(plist, 3);
// ListPushBack(plist, 4);
// ListPopBack(plist);//删一次
// ListPopBack(plist);//删两次
// ListPopBack(plist);//三次
// ListPopBack(plist);//四次,下一次再删除会报错
// ListPrint(plist);
//}
//void test5()//测试头删
//{
// ListNode* plist = NULL;
// ListInit(&plist);
// ListPushBack(plist, 1);
// ListPushBack(plist, 2);
// ListPushBack(plist, 3);
// ListPushBack(plist, 4);
// ListPrint(plist);
// ListPopFront(plist);//删一次
// ListPrint(plist);
// ListPopFront(plist);//2
// ListPrint(plist);
// ListPopFront(plist);//3
// ListPrint(plist);
// ListPopFront(plist);//4,下一次再删除会报错
// ListPrint(plist);
//}
//void test6()//测试查找目标数据节点、指定节点之后插入数据、删除指定节点
//{
// ListNode* plist = NULL;
// ListInit(&plist);
// ListPushBack(plist, 1);
// ListPushBack(plist, 2);
// ListPushBack(plist, 3);
// ListPushBack(plist, 4);
// ListNode* find = ListFind(plist, 1);
// if (find == NULL)
// printf("没找到\n");
// else
// printf("找到了,地址是%p\n", find);
// ListErase(find);
// ListPrint(plist);
//}
void test7()//链表的销毁
{ListNode* plist = NULL;ListInit(&plist);ListPushBack(plist, 1);ListPushBack(plist, 2);ListPushBack(plist, 3);ListPushBack(plist, 4);ListPrint(plist);ListDestroy(plist);ListPrint(plist);plist = NULL;
}
int main()
{//test1();//测试双向链表初始化和创造节点//test2();//测试双向链表尾插节点以及双向链表的打印//test3();//测试打印双向链表//test4();//测试尾删//test5();//测试头删//test6();//测试查找目标数据节点、指定节点之后插入数据、删除指定节点test7();//链表的销毁return 0;
}
上面的代码,是我在测试函数功能是否正常所写的代码。小伙伴们看看就行。
三.结言
关于如何通过双向链表实现数据的增删查改就讲到这里了,帅哥美女们,我们下次再见,拜拜。