概念：双向链表是每个结点除后继指针外还有一个前驱指针。和单链表类同，双向链表也有带头结点结构和不带头结点结构两种，带头结点的双向链表更为常用；另外，双向链表也可以有循环和非循环两种结构，循环结构的双向链表更为常用。
头文件.h
ps:头文件中函数声明里面的参数和定义的时候写的必须一致,否则就会报错
长这样的报错可以检查一下参数还是函数名写错了,大小写啥的都看一下
#pragma once
typedef int DataType;
typedef struct DListNode
{
struct DListNode* next;
struct DListNode* prev;
DataType data;
}DLNode;
// 创建返回链表的头结点.
DLNode* ListCreate();
int ListSize(DLNode* head);
int ListEmpty(DLNode* head);
// 双向链表销毁
void ListDestory(DLNode** plist);
// 双向链表打印
void ListPrint(DLNode* head);
// 双向链表尾插
void ListPushBack(DLNode* head, DataType x);
// 双向链表尾删
void ListPopBack(DLNode* head);
// 双向链表头插
void ListPushFront(DLNode* head, DataType x);
// 双向链表头删
void ListPopFront(DLNode* head);
// 双向链表查找
DLNode* ListFind(DLNode* plist, DataType x);
// 双向链表在pos的前面进行插入
void ListInsert(DLNode* pos, DataType x);
// 双向链表删除pos位置的节点
void ListErase(DLNode* pos);
///
void TestDList();
源代码.c
#include"DList.h"
#include<stdio.h>
#include<assert.h>
#include<malloc.h>
//动态申请节点,储存值为data
DLNode* buyDListNode(DataType data)
{
DLNode* node = (DLNode*)malloc(sizeof(DLNode));
if (node == NULL)
{
assert(0);
return NULL;
}
node->data = data;
node->next = NULL;
node->prev = NULL;
return node;
}
// 创建链表的头结点
DLNode* ListCreate()
{
DLNode* head = buyDListNode(0);
head->next = head;
head->prev = head;
return head;
}
//链表元素个数
int ListSize(DLNode* head)
{
assert(head);
DLNode* cur = head->next;
int size = 0;
while (cur!=head)
{
size++;
cur = cur->next;
}
return size;
}
//判空
int ListEmpty(DLNode* head)
{
assert(head);
if (head->next == head)
{
return 0;
}
else
{
return 1;
}
}
// 双向链表销毁
void ListDestory(DLNode** plist)
{
assert(plist);
DLNode* cur = *plist;
while ((cur->next)!=*plist)
{
DLNode* nodedel = cur->next;
free(cur);
cur = nodedel;
}
free(*plist);
*plist = NULL;
}
// 双向链表打印
void ListPrint(DLNode* head)
{
assert(head);
DLNode* cur = head->next;
while (cur != head)
{
printf("---->%d", cur->data);
cur = cur->next;
}
printf("\n");
}
// 双向链表尾插
void ListPushBack(DLNode* head, DataType x)
{
assert(head);
DLNode* node = buyDListNode(x);
node->next = head;
node->prev = head->prev;
head->prev->next = node;
head->prev = node;
//也可以ListInsert(head, x);
}
// 双向链表尾删
void ListPopBack(DLNode* head)
{
if (ListEmpty(head))
{
return;
}
assert(head);
DLNode* nodedel = head->prev;
head->prev->next = head;
head->prev = head->prev->prev;
free(nodedel);
//也可以ListErase(plist->prev);
}
// 双向链表头插
void ListPushFront(DLNode* head, DataType x)
{
DLNode* node = buyDListNode(x);
node->next = head->next;
node->prev = head;
head->next->prev = node;
head->next = node;
//ListInsert(plist->next, x);
}
// 双向链表头删
void ListPopFront(DLNode* head)
{
assert(head);
if (ListEmpty(head))
{
return;
}
DLNode* nodedel = head->next;
head->next = nodedel->next;
nodedel->next->prev = head;
free(nodedel);
//ListErase(plist->next);
}
// 双向链表查找
DLNode* ListFind(DLNode* plist, DataType x)
{
assert(plist);
DLNode* cur = plist->next;
while (cur != plist)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}
// 双向链表在pos的前面进行插入
void ListInsert(DLNode* pos, DataType x)
{
if (pos == NULL)
{
return;
}
DLNode* node = buyDListNode(x);
pos->prev->next = node;
node->prev = pos->prev;
node->next = pos;
pos->prev = node;
}
// 双向链表删除pos位置的节点
void ListErase(DLNode* pos)
{
if (pos == NULL){
return;
}
pos->prev->next = pos->next;
pos->next->prev = pos->prev;
free(pos);
}
void TestDList()
{
DLNode* head= ListCreate();
ListPushBack(head, 1);//尾插
ListPushBack(head, 2);
ListPushBack(head, 3);
ListPushBack(head, 4);
ListPushBack(head, 5);
ListPrint(head);//打印,期待效果12345
ListPushFront(head, 0);//头插
ListPrint(head);//打印,期待效果012345
ListPopFront(head);//头删
ListPrint(head);//12345
ListInsert(ListFind(head, 3), 6);//在3前插入6
ListPrint(head);//126345
ListErase(ListFind(head, 6));//删除6
ListPrint(head);//12345
}
main.c
#include"DList.h"
#include<windows.h>
int main()
{
TestDList();
system("pause");
return 0;
}
完美!
多敲代码,慢慢熟练以后敲代码就变得很流畅很开心,越难受越要忍着难受敲,使劲敲,敲到熟练为止!!!