当前位置:   article > 正文

双向循环链表(图文讲解)_循环双链表

循环双链表

双向循环链表

请添加图片描述

请添加图片描述

结构体
typedef struct node
{
	int data;
	struct node* pre;	//指向前驱
	struct node* next;	//指向后继
}NODE;
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6

双链表是链表的一种,由节点组成,每个数据结点中都有两个指针,分别指向直接后继和直接前驱。

初始化函数
NODE * Init()
{
	NODE* head = (NODE*)malloc(sizeof(NODE));
	head->pre = head->next = head;	//双链表的head->pre=head->next=NULL;
	return head;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
添加数据
头插

请添加图片描述

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
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
删除数据

请添加图片描述


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;
	}
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
显示函数
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;
	}
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
示例程序一(简易版本):
#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;
	}
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
运行结果:
---插入后---
id      data
 1       1
 2       3
 3       5
---删除后---
id      data
 1       1
 2       5
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
示例程序二
//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();
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
//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);
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
//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;
	}
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77

输出结果:


id      name    score
1001    小明    100
1002    小红    98
-----删除数据之后-----
id      name    score
1002    小红    98
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/笔触狂放9/article/detail/655470
推荐阅读
相关标签
  

闽ICP备14008679号