实现细节
辅助理解图
具体实现代码
1、对链表进行初始化
2、任意位置前的插入
3、任意位置的删除
4、头插和尾删
完整代码
头文件
具体函数
测试
实现细节1、带一个哨兵位(哨兵节点,初始节点,不存储有效数据,用来方便后期数据的存储与查找)
2、与单向链表不同的是,双向链表中每个数据节点包含两个指针,分别指向前后两个节点
3、双向链表是循环的,其尾节点后不是空指针,而是与头部的哨兵节点通过指针相连
辅助理解图 具体实现代码 1、对链表进行初始化初始化:哨兵位的前后指针均指向哨兵节点本身
void ListInit(ListNode** pphead)
{
*pphead = (ListNode*)malloc(sizeof(ListNode));
if (*pphead == NULL)
{
perror("ListInit");
exit(-1);
}
(*pphead)->date = -1;
(*pphead)->next = *pphead;
(*pphead)->prev = *pphead;
}
2、任意位置前的插入
注意:插入位置前后节点中的前后指针要进行相应的更换
void Any_insert(ListNode* pos,Listtype date)
{
ListNode* Prev = pos->prev;
//建立新节点
ListNode* NewNode = (ListNode*)malloc(sizeof(ListNode));
if (NewNode == NULL)
{
perror("Any_insert");
exit(-1);
}
NewNode->date = date;
NewNode->next = pos;
pos->prev = NewNode;
Prev->next = NewNode;
NewNode->prev = Prev;
}
3、任意位置的删除
细节点:当链表中没有数据时,就不用删除,因此需要建立一个函数进行判断
bool Determine(ListNode* pphead)
{//判断链表中有无元素
assert(pphead);
return pphead == pphead->next;
}
void Any_delet(ListNode* pos)
{
assert(!Determine(pos));
ListNode* Next = pos->next;
ListNode* Prev = pos->prev;
Next->prev = Prev;
Prev->next = Next;
free(pos);
}
4、头插和尾删
此处的插入和删除,十分方便,即:对上面的任插和任删进行套用
头插如下:
void Head_insert(ListNode* pphead, Listtype date)
{
ListNode* NewNode = (ListNode*)malloc(sizeof(ListNode));
if (NewNode == NULL)
{
perror("Head_insert");
exit(-1);
}
//单独实现
//NewNode->date = date;
//NewNode->prev = pphead;
//NewNode->next = pphead->next;
//pphead->next->prev = NewNode;
//pphead->next = NewNode;
//进行任插的复用
Any_insert(pphead->next ,date);
}
尾删如下:
void Tail_delet(ListNode* pphead)
{
assert(pphead);
//单独实现
//assert(Determine(pphead));
/*ListNode* tail = pphead->prev;
if (tail != pphead)
{
ListNode* tailprev = tail->prev;
tailprev->next = pphead;
pphead->prev = tailprev;
free(tail);
}*/
//尾删的复用
Any_delet(pphead->prev);
}
完整代码
头文件
#pragma once
#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int Listtype;
typedef struct ListNode
{
struct ListNode* prev;
Listtype date;
struct ListNode* next;
}ListNode;
void ListInit(ListNode** pphead); //链表初始化
void ListNode_ADD(ListNode* pphead, Listtype date); //尾插
void Head_insert(ListNode* pphead, Listtype date); //头插
void ListNode_Print(ListNode* pphead); //链表打印
void Tail_delet(ListNode* pphead); //尾删
bool Determine(ListNode* pphead); //判断表中有无数据
void Any_insert(ListNode* pos, Listtype date); //任插
void Any_delet(ListNode* pos); //任删
void List_Destory(ListNode* pos); //链表清空
具体函数
#define _CRT_SECURE_NO_WARNINGS 1
#include "List.h"
//链表打印
void ListNode_Print(ListNode* pphead)
{
assert(pphead);
ListNode* phead = pphead;
pphead = pphead->next;
for (; pphead != phead; pphead = pphead->next)
{
printf("%d ", pphead->date);
}
printf("\n");
}
bool Determine(ListNode* pphead)
{//判断链表中有无元素
assert(pphead);
return pphead == pphead->next;
}
//链表初始化
void ListInit(ListNode** pphead)
{
*pphead = (ListNode*)malloc(sizeof(ListNode));
if (*pphead == NULL)
{
perror("ListInit");
exit(-1);
}
(*pphead)->date = -1;
(*pphead)->next = *pphead;
(*pphead)->prev = *pphead;
}
//尾插
void ListNode_ADD(ListNode* pphead,Listtype date)
{
//ListNode* NewNode = (ListNode*)malloc(sizeof(ListNode));
//if (NewNode == NULL)
//{
//perror("ADD_malloc");
//exit(-1);
//}
//NewNode->date = date;
//NewNode->prev = pphead->prev;
//pphead->prev->next = NewNode;
//pphead->prev = NewNode;
//NewNode->next = pphead;
//任插的复用
Any_insert(pphead, date);
}
void Head_insert(ListNode* pphead, Listtype date)
{
ListNode* NewNode = (ListNode*)malloc(sizeof(ListNode));
if (NewNode == NULL)
{
perror("Head_insert");
exit(-1);
}
//NewNode->date = date;
//NewNode->prev = pphead;
//NewNode->next = pphead->next;
//pphead->next->prev = NewNode;
//pphead->next = NewNode;
//进行任插的复用
Any_insert(pphead->next ,date);
}
void Tail_delet(ListNode* pphead)
{
assert(pphead);
//assert(Determine(pphead));
/*ListNode* tail = pphead->prev;
if (tail != pphead)
{
ListNode* tailprev = tail->prev;
tailprev->next = pphead;
pphead->prev = tailprev;
free(tail);
}*/
//尾删的复用
Any_delet(pphead->prev);
}
//在任意位置前插入
void Any_insert(ListNode* pos,Listtype date)
{
ListNode* Prev = pos->prev;
ListNode* NewNode = (ListNode*)malloc(sizeof(ListNode));
if (NewNode == NULL)
{
perror("Any_insert");
exit(-1);
}
NewNode->date = date;
NewNode->next = pos;
pos->prev = NewNode;
Prev->next = NewNode;
NewNode->prev = Prev;
}
//任意位置删除
void Any_delet(ListNode* pos)
{
assert(!Determine(pos));
ListNode* Next = pos->next;
ListNode* Prev = pos->prev;
Next->prev = Prev;
Prev->next = Next;
free(pos);
}
//链表清空
void List_Destory(ListNode* pos)
{
ListNode* head = pos,*Prev = pos->prev;
for (pos = pos->prev; head != pos;pos = Prev)
{
Prev = pos->prev;
Any_delet(pos);
}
printf("\n清空完成\n");
}
测试
#define _CRT_SECURE_NO_WARNINGS 1
#include "List.h"
void ListTest(ListNode** pphead)
{
ListInit(pphead);
Head_insert(*pphead, 60);
Head_insert(*pphead, 100);
Head_insert(*pphead, 60);
Head_insert(*pphead, 50);
ListNode_Print(*pphead);
Tail_delet(*pphead);
Tail_delet(*pphead);
Tail_delet(*pphead);
ListNode_Print(*pphead);
}
int main()
{
ListNode* pphead = NULL;
ListTest(&pphead);
return 0 ;
}
以上就是详解C语言中双向循环链表的实现的详细内容,更多关于C语言双向循环链表的资料请关注易知道(ezd.cc)其它相关文章!