devbox
你好赵伟
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

数据结构之单链表、双向链表和循环链表_循环单链及循环双链的适用场景

作者：你好赵伟 | 2024-07-16 01:01:51

赞

踩

循环单链及循环双链的适用场景

链表是一种最为基础的数据结构，需要动态开辟空间，在执行删除或插入操作时效率高。主要分类有：

  • 单链表
  • 双向链表
  • 循环链表
    链表的应用场景：（不需要预先知道数据规模；适应于频繁的删除插入操作。），如：
    内存管理：内存管理是操作系统中一项重要的任务，操作系统必须决定如何为系统中运行的进程分配和回收存储空间。链表能够用来跟踪可分配的内存片段信息。
    其他的数据结构：栈、队列、集合、哈希表和图都要依赖于链表。

单链表

简称链表，由各个数据成员通过一个指针彼此链接起来而组成。每个元素包括两部分：数据成员和一个称为next的指针。只能以一个方向进行遍历，从头到尾。
在这里插入图片描述

//list.h
#pragma once
#ifndef LIST_H
#define LIST_H
#endif // !LIST_H

#include<stdlib.h>

//定义链表元素的结构
typedef struct ListElmt_ {
	void * data;
	struct ListElmt_ *next;
} ListElmt;

//定义链表的结构
typedef struct List_ {
	//size表示链表元素的个数
	int size;
	//match并不是由链表本身使用，而是由从链表数据结构派生而来的新类型所使用。
	int(*match)(const void *key1, const void *key2);
	//destroy是封装之后传递给list_init的析构函数
	void(*destroy)(void *data);
	//指向头结点的指针
	ListElmt *head;
	//指向尾结点的指针
	ListElmt *tail;
}List;

//公共接口
//初始化
void list_init(List *list, void(*destroy)(void *data));
//销毁
void list_destroy(List *list);

//如果插入元素成功则返回0，否则返回-1
/*
在list指定的链表中element后面插入一个新元素，如果element为空，说明链表为空，新元素插入链表头部
新元素包含一个指向data的指针，只要该元素在链表中，data所引用的内存空间要保持合法
*/
int list_ins_next(List *list, ListElmt *element, const void* data);
/*移除element后的一个元素，data指向已移除中存储的元素
如果element为NULL，则移除头结点*/
int list_rem_next(List* list, ListElmt * element, void **data);

//int list_size(const List* list);
//
返回指向链表中头元素的指针
//ListElmt * list_head(const List *list);
返回指向链表尾元素的指针
//ListElmt * list_tail(const List *list);
判断是否头结点,尾结点
//int list_is_head(const ListElmt *element);
//int list_is_tail(const ListElmt *element);
//
返回节点中保存的数据
//void *list_data(const List *element);

#define list_size(list) ((list)->size)
#define list_head(list) ((list)->head)
#define list_tail(list) ((list)->tail)
#define list_is_head(list,element) ((element) == (list)->head?1:0)
#define list_is_tail(element) ((element)->next == NULL ? 1:0)
#define list_data(element) ((element)->data)
#define list_next(element) ((element)->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
//list.c
#include<stdlib.h>
#include<string.h>
#include"list.h"
//初始化链表
void list_init(List *list, void(*destroy)(void *data)) {
	list->size = 0;
	list->destroy = destroy;
	list->head = NULL;
	list->tail = NULL;
	return;
}
//销毁链表
void list_destroy(List *list) {
	void * data;
	//移除每个元素
	while (list_size(list) > 0)
	{
		if (list_rem_next(list, NULL, (void **)&data) == 0 && list->destroy != NULL) {
			//调用一个用户分配的函数来释放动态分配的内存
			list->destroy(data);
		}
	}
	//现在无操作被允许，但是要对这个结构进行清零操作，作为预防措施
	memset(list, 0, sizeof(List));
	return;

}

//移除element之后的一个元素
int list_rem_next(List *list, ListElmt *element, void **data) {
	ListElmt *old_element;

	//如果链表为空，则直接返回-1；
	if (list_size(list) == 0) {
		return -1;
	}
	//如果element为空，删除头结点
	if (element == NULL) {
		*data = list->head->data;
		old_element = list->head;
		list->head = list->head->next;

		if (list_size(list) == 1) {
			list->tail = NULL;
		}
	}
	else
	{
		//需要删除的元素在头结点之外

		//如果删除的元素为空，则直接返回
		if (element->next == NULL) {
			return -1;
		}

		*data = element->next->data;
		old_element = element->next;
		element->next = element->next->next;

		//如果删除外element后的节点后，element之后没节点了，说明element成了尾结点
		if (element->next == NULL) {
			list->tail = element;
		}
	}

	//old_element是需要删除的节点,释放他的内存
	free(old_element);

	//调整list的size
	list->size--;
	return 0;
}

//在element之后插入一个元素
int list_ins_next(List *list, ListElmt *element, const void *data) {
	ListElmt * new_element;
	//为该元素分配内存
	new_element = (ListElmt*)malloc(sizeof(ListElmt));
	//如果未分配到内存
	if (new_element == NULL) return -1;

	//需要强制转换，const类型不能转给非const类型
	new_element->data =(void *) data;

	//如果element为空，则把new_element作为头结点
	if (element == NULL) {
		//如果是个空链表
		if (list_size(list) == 0) {
			list->tail = new_element;
		}
		new_element->next = list->head;
		list->head = new_element;
	}
	else
	{
		//如果element为尾结点
		if (element->next == NULL) {
			list->tail = new_element;
		}
		
		new_element->next = element->next;
		element->next = new_element;
	}

	list->size++;
	return 0;
}

  • 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
  • 105
  • 106
  • 107
  • 108

双向链表

链表元素由两个指针链接。每个元素有三部分组成：除了数据成员和next指针外，还有包含一个指向前一个元素的指针prev。为了标识头和尾，将第一个元素的prev指针和最后一个元素的next指针置为NULL。它可以从头到尾，也可以从尾到头遍历整个链表。
在这里插入图片描述

//dlist.h
#pragma once
#ifndef DLIST_H
#define DLIST_H

#include<stdlib.h>
typedef struct DListElmt_ {
	void *data;
	struct DListElmt_ *prev;
	struct DListElmt_ *next;
} DListElmt;
typedef struct DList_ {
	int size;
	int(*match)(const void *key1, const void *key2);
	void(*destroy)(void *data);
	DListElmt *head;
	DListElmt *tail;
} DList;
//公共接口
void dlist_init(DList * list, void(*destroy)(void *data));
void dlist_destroy(DList *list);
int dlist_ins_next(DList *list, DListElmt * element, const void *data);
int dlist_ins_prev(DList *list, DListElmt * element, const void *data);
int dlist_remove(DList *list, DListElmt *element, void **data);

#define dlist_size(list) ((list)->size)
#define dlist_head(list) ((list)->head)
#define dlist_tail(list) ((list)->tail)
#define dlist_is_head(element) ((element)->prev == NULL ? 1:0)
#define dlist_is_tail(element) ((element)->next == NULL ? 1:0)
#define dlist_data(element) ((element)->data)
#define dlist_next(element) ((element)->next)
#define dlist_prev(element) ((element)->prev)
#endif // !DLIST_H


  • 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
//dlist.c
#include<stdlib.h>
#include<string.h>
#include"dlist.h"

void dlist_init(DList *list, void(*destroy)(void *data)) {
	list->size = 0;
	list->destroy = destroy;
	list->head = NULL;
	list->tail = NULL;
	return;
}

void dlist_destroy(DList *list) {
	void *data;
	while (dlist_size(list)>0)
	{
		if (dlist_remove(list, dlist_tail(list), (void **)&data) == 0 && list->destroy != NULL) {
			//调用用户自定义的函数来释放动态分配的数据data
			list->destroy(data);
		}
	}
	memset(list, 0, sizeof(list));
	return;
}
//将元素插入element之后
int dlist_ins_next(DList *list, DListElmt *element, const void *data) {
	DListElmt * new_element;

	//不可能的情况
	if (element == NULL && dlist_size(list) != 0) {
		return -1;
	}
	//为要插入的元素分配内存,内存分配失败返回-1
	if ((new_element = (DListElmt*)malloc(sizeof(DListElmt))) == NULL) {
		return -1;
	}
	new_element->data =(void *) data;

	//如果链表为空,该元素要作为头结点
	if (dlist_size(list) == 0) {
		new_element->prev = NULL;
		new_element->next = NULL;
		list->head = new_element;
		list->tail = new_element;
	}
	else {
		new_element->prev = element;
		new_element->next = element->next;
		element->next = new_element;

		//还要考虑element后为空的情况,插入之后，new_element就变成最后一个了
		if (element->next == NULL) {
			list->tail = new_element;
		}
		else {
			element->next->prev = new_element;
		}
	}
	list->size++;
	return 0;	
}
//在element之前插入
int dlist_ins_prev(DList *list, DListElmt *element, const void *data) {
	//先创建一个新元素
	DListElmt * new_element;
	if (element == NULL && dlist_size(list) == 0) {
		return -1;
	}
	//分配内存
	new_element = (DListElmt *)malloc(sizeof(DListElmt));
	if (new_element == NULL) {
		//分配内存失败
		return -1;
	}
	//将数据放入
	new_element->data = (void *)data;
	
	//如果element为NULL，说明链表为空,也可以用size==0表示,插入的元素为第一个
	if (element == NULL) {
		new_element->next = NULL;
		new_element->prev = NULL;
		list->head = new_element;
		list->tail = new_element;
	}
	else
	{
		new_element->next = element;
		new_element->prev = element->prev;
		//如果该元素是头元素，则新元素应该成为新的头元素
		if (element->prev == NULL) {
			list->head = new_element;
		}
		else {
			element->prev->next = new_element;	
		}
		element->prev = new_element;
	}
	list->size++;
	return 0;

}
//删除元素
int dlist_remove(DList *list, DListElmt * element, void ** data) {
	//如果元素为空，或者链表为空，删除失败
	if (element == NULL || dlist_size(list) == 0)
		return -1;
	*data = element->data;

	//如果该数据是头结点
	if (element->prev == NULL) {
		list->head = element->next;
		//如果链表只有一个元素
		if (element->next == NULL) {
			list->tail = NULL;
		}
		else {
			element->next->prev = NULL;
		}
	}
	else {
		element->prev->next = element->next;
		//如果这个元素是最后一个
		if (element->next == NULL) {
			list->tail = element->prev;
		}
		else {
			element->next->prev = element->prev;
		}
	}

	//释放内存
	free(element);
	list->size--;
	return 0;
}

  • 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
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115
  • 116
  • 117
  • 118
  • 119
  • 120
  • 121
  • 122
  • 123
  • 124
  • 125
  • 126
  • 127
  • 128
  • 129
  • 130
  • 131
  • 132
  • 133
  • 134
  • 135
  • 136

循环链表

在这里插入图片描述
在这里插入图片描述
循环链表可以是单向的也可以是双向的。区分一个链表是不是循环链表只要看它有没有尾部元素即可。
在循环链表中，最后一个元素指向头元素，而不是NULL；如果是双向的循环链表，它的头元素的prev要指向最后一个元素，而不是NULL。

//clist.h
#pragma once
#ifndef CLIST_H
#define CLIST_H
#include<stdlib.h>
typedef struct CListElmt_ {
	void *data;
	struct CListElmt_ *next;
} CListElmt;
typedef struct Clist_ {
	int size;
	int(*match)(const void *key1, const void *key2);
	void(*destroy)(void *data);
	CListElmt *head;
} CList;

//公共接口
void clist_init(CList *list, void(*destroy)(void *data));
void clist_destroy(CList *list);
int clist_ins_next(CList *list, CListElmt *element, const void *data);
int clist_rem_next(CList *list, CListElmt *element, void **data);

#define clist_size(list) ((list)->size)
#define clist_head(list) ((list)->head)
#define clist_data(element) ((element)->data)
#define clist_next(element) ((element)->next)
#endif // !CLIST_H


  • 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
#include<stdlib.h>
#include<string.h>
#include"clist.h"

void clist_init(CList *list, void(*destroy)(void *data)) {
	list->size = 0;
	list->head = NULL;
	list->destroy = destroy;
	return;
}
void clist_destroy(CList *list) {
	void *data;
	while (clist_size(list)>0)
	{
		if (clist_rem_next(list, list->head, (void **)&data) == 0 && list->destroy !=NULL) {
			list->destroy(data);
		}
	}
	memset(list, 0, sizeof(CList));
	return;
}
int clist_ins_next(CList *list, CListElmt *element, const void*data) {
	CListElmt * new_element;
	if ((new_element = (CListElmt *)malloc(sizeof(CListElmt))) == NULL) {
		return -1;
	}
	new_element->data = (void *)data;
	//如果链表为空
	if (clist_size(list) == 0) {
		list->head = new_element;
		list->head->next = new_element;
	}
	else {
		new_element->next = element->next;
		element->next = new_element;
	}
	list->size++;
	return 0;
}
int clist_rem_next(CList *list, CListElmt *element, void ** data) {
	CListElmt * old_element;
	if (clist_size(list) == 0) {
		return -1;
	}
	//如果只有一个元素
	if (clist_size(list) == 1) {
		list->head = NULL;
		old_element = element;
	}
	else {
		old_element = element;
		element->next = element->next->next;
		if (old_element == clist_head(list)) {
			list->head = old_element->next;
		}
	}

	free(old_element);
	list->size--;
	return 0;
}

  • 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
声明：本文内容由网友自发贡献，转载请注明出处：【wpsshop博客】
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号