数据结构之单链表、双向链表和循环链表

快来打我* 2022-12-14 13:33 249阅读 0赞

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

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

# 单链表 #

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

//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)

//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;
    }

# 双向链表 #

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

//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

//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;
    }

# 循环链表 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1b2xhaWh1YTIwMTg_size_16_color_FFFFFF_t_70_pic_center 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1b2xhaWh1YTIwMTg_size_16_color_FFFFFF_t_70_pic_center 2]  
循环链表可以是单向的也可以是双向的。区分一个链表是不是循环链表只要看它有没有尾部元素即可。  
在循环链表中，最后一个元素指向头元素，而不是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

#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;
    }

[20201021104756256.png_pic_center]: /images/20221123/5ca69a9d238f4d78946d6bfefa682e75.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1b2xhaWh1YTIwMTg_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/b63c5d9c23c046a7bbaa627cb3bf4917.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1b2xhaWh1YTIwMTg_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221123/e6b7ec8331544a4d9b4d3754cb5560a8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1b2xhaWh1YTIwMTg_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221123/224df89efbb24a65a0f0170c4fbbc632.png