【数据结构】线性表（四）：链表之双向循环链表

﹏ヽ暗。殇╰゛Y 2023-03-02 05:12 3阅读 0赞

### 文章目录 ###

*  双向循环链表
 *   *  一、概念
     *  二、图解
     *  三、实现源码

# 双向循环链表 #

## 一、概念 ##

> **双向循环链表**是指每个结点由三部分组成：**数据域、直接前驱结点指针、直接后继结点指针**，该链表的最后一个结点的直接后继指针指向头结点，头结点的直接前驱指针指向尾节点。

## 二、图解 ##

结点图示  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTQzNzAyMg_size_16_color_FFFFFF_t_70]

双向循环链表图示  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTQzNzAyMg_size_16_color_FFFFFF_t_70 1]

## 三、实现源码 ##

> 常量定义

typedef int ET;

--------------------

> 双向循环链表定义

typedef struct Node
    { 
    	ET data;
    	Node* next;
    	Node* prev;
    }Node;
    typedef Node* BCList;

--------------------

> 获取一个新节点

Node* CreateNode(ET val){ 
    	Node* s = (Node*)malloc(sizeof(Node));
    	assert(s != NULL);
    	s->data = val;
    	s->next = s->prev = s;
    	return s;
    }

--------------------

> 初始化一个带头结点的双向循环链表

void BCLinkedListInitial(BCList* phead){ 
    	*phead = CreateNode(-1);
    }

--------------------

> 头插法

void BCLinkedListAddFromHead(BCList* phead, ET val){ 
    	assert(phead != NULL);
    	Node* s = CreateNode(val);
    	Node* p = (*phead)->next;
    
    	s->next = p;
    	s->prev = *phead;
    	(*phead)->next = s;
    	p->prev = s;
    }

--------------------

> 尾插法

void BCLinkedListAddFromBack(BCList* phead, ET val){ 
    	assert(phead != NULL);
    	Node* s = CreateNode(val);
    	Node* p = (*phead)->prev;
    
    	(*phead)->prev = s;
    	s->next = *phead;
    	s->prev = p;
    	p->next = s;
    
    }

--------------------

> 显示数据

void BCLinkedListShowData(BCList phead){ 
    	Node* p = phead->next;
    	while (p != phead){ 
    		printf("%d ", p->data);
    		p = p->next;
    	}
    	printf("\n");
    }

--------------------

> 判断表是否为空

bool IsEmpty(BCList* phead){ 
    	if ((*phead)->prev == (*phead)){ 
    		return true;
    	}
    	return false;
    }

--------------------

> 删除尾部结点

void BCLinkedListDeleteFromBack(BCList* phead){ 
    	assert(phead != NULL);
    	if (IsEmpty(phead)){ 
    		printf("表空，无法删除！\n");
    		return;
    	}
    	Node* s = (*phead)->prev;
    
    	(*phead)->prev = s->prev;
    	s->prev->next = *phead;
    
    	free(s);
    }

--------------------

> 删除首元结点

void BCLinkedListDeleteFromHead(BCList* phead){ 
    	assert(phead != NULL);
    	if (IsEmpty(phead)){ 
    		printf("表空，无法删除！\n");
    		return;
    	}
    
    	Node* s = (*phead)->next;
    	Node* p = s->next;
    
    	(*phead)->next = p;
    	p->prev = *phead;
    
    	free(s);
    }

--------------------

> 获取尾结点

Node* BCLinkedListGetBack(BCList* phead){ 
    	assert(phead != NULL);
    	if (IsEmpty(phead)){ 
    		printf("表空，无法获得！\n");
    		return NULL;
    	}
    	return (*phead)->prev;
    }

--------------------

> 获取首元结点

Node* BCLinkedListGetHead(BCList* phead){ 
    	assert(phead != NULL);
    	if (IsEmpty(phead)){ 
    		printf("表空，无法获得！\n");
    		return NULL;
    	}
    	return (*phead)->next;
    }

--------------------

> 获取表长度

size_t BCLinkedListGetListLength(BCList* phead){ 
    	assert(phead != NULL);
    	Node* p = (*phead)->next;
    	size_t len = 0;
    
    	while (p != (*phead)){ 
    		p = p->next;
    		len++;
    	}
    	return len;
    }

--------------------

> 清空表中数据

void BCLinkedListClear(BCList* phead){ 
    	assert(phead != NULL);
    	Node* p = (*phead)->next;
    	Node* q = (*phead)->next;
    	while (q != (*phead)){ 
    		q = q->next;
    		free(p);
    		p = q;
    	}
    	(*phead)->next = *phead;
    	(*phead)->prev = *phead;
    }

--------------------

> 摧毁表结构

void BCLinkedListDestroy(BCList* phead){ 
    	assert(phead != NULL);
    
    	Node* p = (*phead)->next;
    	Node* q = (*phead)->next;
    	(*phead)->next = NULL;
    
    	while (q != NULL){ 
    		q = q->next;
    		free(p);
    		p = q;
    	}
    	*phead = NULL;
    }

--------------------

> 按值查找

Node* BCLinkedListFindByValue(BCList* phead, ET key){ 
    	assert(phead != NULL);
    
    	Node* p = (*phead)->next;
    	while (p != (*phead) && p->data != key){ 
    		p = p->next;
    	}
    	if (p == *phead) return NULL;
    	return p;
    }

--------------------

> 按值的大小插入

void BCLinkedListInsertByValue(BCList* phead, ET val){ 
    	assert(phead != NULL);
    	Node *p = (*phead)->next;
    	while (p != *phead && p->data < val){ 
    		p = p->next;
    	}
    	if (p == *phead){ 
    		BCLinkedListAddFromBack(phead, val);
    	}
    	else{ 
    		Node* s = CreateNode(val);
    		Node* q = p->prev;
    
    		q->next = s;
    		s->next = p;
    		p->prev = s;
    		s->prev = q;
    	}
    }

--------------------

> 将表中结点按照数据升序链接

void BCLinkedListSortByData(BCList* phead){ 
    	assert(phead != NULL);
    	Node *p = (*phead)->next->next;
    	Node *q = (*phead)->next->next;
    	(*phead)->prev->next = NULL;
    	(*phead)->next->next = (*phead);
    	(*phead)->prev = (*phead)->next;
    	while (q != NULL){ 
    		q = q->next;
    		if ((*phead)->next->data > p->data){ 
    			BCLinkedListAddFromHead(phead, p->data);
    			free(p);
    		}
    		else{ 
    			Node* temp = (*phead)->next;
    			while (temp->next != (*phead) && temp->data < p->data){ 
    				temp = temp->next;
    			}
    			if (temp->next == (*phead)){ 
    				BCLinkedListAddFromBack(phead, p->data);
    				free(p);
    			}
    			else{ 
    				p->next = temp;
    				p->prev = temp->prev;
    				temp->prev->next = p;
    				temp->prev = p;
    			}
    		}
    		p = q;
    	}
    }

--------------------

> 反转链表

void BCLinkedListReverseList(BCList* phead){ 
    	assert(phead != NULL);
    	if (IsEmpty(phead))	return;
    
    	Node* p = (*phead)->prev;
    	Node* q = (*phead)->prev;
    
    	(*phead)->next->prev = NULL;	//创造循环结束条件 
    
    	//将头结点置空
    	(*phead)->next = (*phead)->prev = *phead;
    
    	while (q != NULL){ 
    		q = q->prev;
    		BCLinkedListAddFromBack(phead, p->data);
    		free(p);
    		p = q;
    	}
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTQzNzAyMg_size_16_color_FFFFFF_t_70]: /images/20230208/3dee1eb69cc74f8f803dd9d6bdd7efbe.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTQzNzAyMg_size_16_color_FFFFFF_t_70 1]: /images/20230208/f201a8187f3544de862d745c04c1d65b.png