循环双链表
目录
双向循环链表结构体初始化函数添加数据头插删除数据显示函数示例程序一(简易版本)：运行结果：示例程序二输出结果：
双向循环链表
结构图示：
结构体
typedef struct node
{
int data;
struct node* pre; //指向前驱
struct node* next; //指向后继
}NODE;
双链表是链表的一种，由节点组成，每个数据结点中都有两个指针，分别指向直接后继和直接前驱。
初始化函数
NODE * Init()
{
NODE* head = (NODE*)malloc(sizeof(NODE));
head->pre = head->next = head; //不循环双链表的head->pre=head->next=NULL;
return head;
}
添加数据
头插
void insert(NODE * head, int data)
{
//申请节点
NODE* pNew = (NODE*)malloc(sizeof(NODE));
//NODE* pNew = Init(); //和上面等效
//初始化节点
pNew->data = data;
//插入节点
#if 1//头插
pNew->pre = head; //①
pNew->next = head->next;//②
pNew->pre->next = pNew; //③
pNew->next->pre = pNew; //④
#elif 0//尾插
//插入的是head的前面
pNew->pre = head->pre;
pNew->next = head;
pNew->next->pre = pNew;
pNew->pre->next = pNew;
#else //中间插入 插入到条件节点的后面
//条件 插入到...条件 data==3
NODE *temp = head->next; //第一个结点没有数据
while (temp != head) //循环链表
{
if (temp->data == 3) //插入到q的后面
{
break;
}
temp = temp->next;
}
//插入
pNew->next = temp->next;
pNew->pre = temp;
pNew->next->pre = pNew;
pNew->pre->next = pNew;
#endif
}
删除数据
void deleteData(NODE * head, int data)
{
NODE*temp = head->next;
while (temp != head)
{
if (temp->data == data)
{
//删除数据
temp->next->pre = temp->pre; //①
temp->pre->next = temp->next; //②
free(temp);
break;
}
temp = temp->next;
}
}
显示函数
void showLinked(NODE * head)
{
NODE*temp = head->next;
int number = 1;
while (temp != head)
{
printf("%d\t%d\n", number++, temp->data);
temp = temp->next;
}
}
示例程序一(简易版本)：
#include<stdio.h>
#include<stdlib.h>
typedef struct node
{
int data;
struct node* pre; //指向前驱
struct node* next; //指向后继
}NODE;
NODE* Init(); //初始化
void insert(NODE* head, int data);
void deleteData(NODE* head, int data);
void showLinked(NODE* head);
int main()
{
NODE* head = Init();
insert(head, 1);
insert(head, 3);
insert(head, 5);
printf("---插入后---\n");
showLinked(head);
printf("---删除后---\n");
deleteData(head, 3);
showLinked(head);
getchar();
}
NODE * Init()
{
NODE* head = (NODE*)malloc(sizeof(NODE));
head->pre = head->next = head;
return head;
}
void insert(NODE * head, int data)
{
//申请节点
NODE* pNew = (NODE*)malloc(sizeof(NODE));
//初始化节点
pNew->data = data;
//插入节点
#if 0//头插
pNew->pre = head;
pNew->next = head->next;
pNew->pre->next = pNew;
pNew->next->pre = pNew;
#elif 1//尾插
//插入的是head的前面
pNew->pre = head->pre;
pNew->next = head;
pNew->next->pre = pNew;
pNew->pre->next = pNew;
#else //中间插入 插入到条件节点的后面
//条件 插入到...条件 data==3
NODE *temp = head->next; //第一个结点没有数据
while (temp != head) //循环链表
{
if (temp->data == 3) //插入到q的后面
{
break;
}
temp = temp->next;
}
//插入
pNew->next = temp->next;
pNew->pre = temp;
pNew->next->pre = pNew;
pNew->pre->next = pNew;
#endif
}
void deleteData(NODE * head, int data)
{
NODE*temp = head->next;
while (temp != head)
{
if (temp->data == data)
{
//删除数据
temp->next->pre = temp->pre;
temp->pre->next = temp->next;
free(temp);
break;
}
temp = temp->next;
}
}
void showLinked(NODE * head)
{
NODE*temp = head->next;
int number = 1;
printf("id\tdata\n");
while (temp != head)
{
printf(" %d\t %d\n", number++, temp->data);
temp = temp->next;
}
}
运行结果：
---插入后---
id data
1 1
2 3
3 5
---删除后---
id data
1 1
2 5
示例程序二
//mian.c
#include"Double_Linked.h"
int main()
{
NODE* head;
head = Init(); //初始化表头
/****准备数据****/
NODE data;
data.m_id = 1001;
data.m_score = 100;
strcpy(data.m_name, "小明");
//插入data
insert(head, data);
/****准备数据****/
data.m_id = 1002;
data.m_score = 98;
strcpy(data.m_name, "小红");
//插入data
insert(head, data);
showData(head);
printf("-----删除数据之后-----\n");
deleteData(head, 1001);
showData(head);
getchar();
}
//Double_Linked.h
#pragma once
#include<stdlib.h>
#include<string.h>
#include<stdio.h>
typedef struct node
{
int m_id;
char m_name[20];
int m_score;
struct node* pre; //指向前驱
struct node* next; //指向后继
}NODE;
NODE* Init(); //初始化
void insert(NODE* head, NODE data); //插入数据
void deleteData(NODE*head, int id); //删除数据
void showData(NODE*head);
//Double_Linked.c
#include"Double_Linked.h"
NODE * Init()
{
NODE* head = (NODE*)malloc(sizeof(NODE));
head->pre = head->next = head;
return head;
}
void insert(NODE * head, NODE data)
{
//申请节点
NODE* pNew = (NODE*)malloc(sizeof(NODE));
pNew->m_id = data.m_id;
pNew->m_score = data.m_score;
strcpy(pNew->m_name, data.m_name);
//插入节点
#if 0//头插
pNew->pre = head;
pNew->next = head->next;
pNew->pre->next = pNew;
pNew->next->pre = pNew;
#elif 1//尾插
//插入的是head的前面
pNew->pre = head->pre;
pNew->next = head;
pNew->next->pre = pNew;
pNew->pre->next = pNew;
#else //中间插入 插入到条件节点的后面
//条件 插入到...条件 m_id==3
NODE *temp = head->next; //第一个结点没有数据
while (temp != head) //循环链表
{
if (temp->m_id == 3) //插入到q的后面
{
break;
}
temp = temp->next;
}
/***如果没有找到3这个数据那么，相当于头插***/
//插入
pNew->next = temp->next;
pNew->pre = temp;
pNew->next->pre = pNew;
pNew->pre->next = pNew;
#endif
}
void deleteData(NODE * head, int id)
{
NODE*temp = head->next;
while (temp != head)
{
if (temp->m_id == id)
{
//删除数据
temp->next->pre = temp->pre;
temp->pre->next = temp->next;
free(temp);
break;
}
temp = temp->next;
}
}
void showData(NODE * head)
{
NODE*temp = head->next;
printf("id\tname\tscore\n");
while (temp != head)
{
printf("%d\t%s\t%d\n", temp->m_id, temp->m_name, temp->m_score);
temp = temp->next;
}
}
输出结果：
id name score
1001 小明 100
1002 小红 98
-----删除数据之后-----
id name score
1002 小红 98