[数据结构与算法]C语言双向循环链表

一、介绍

在C语言中，链表分为单向链表和双向链表，单向链表只能朝一个方向遍历，中间的一个节点只能由上一个节点推出，只能往前推，无法往后推，关于单向链表的介绍可以点击单向链表介绍。
这次介绍双向链表，既然叫双向就说明可以往两个方向进行遍历，可以利用中间的一个节点推出下一个节点和上一个节点，所以在定义一个双向链表节点的时候，除了要保存数据和下一个节点的地址，还得保存上一个节点的地址，定义如下：

typedef struct NODE{
	int data;//要保存的数据
	struct NODE *next;//下一节点地址
	struct NODE *prev;//上一节点地址
}*NODE;

在此基础上，如果让头结点的prev指向尾结点，让尾结点的next指向头结点，那么就构成了双向循环链表，如图示：

二、创建双向循环链表

思路：先创建一个节点，并且让该节点的next和prev都指向自己，让他自己跟自己循环，再依次加入新节时，这时只需改变头结点的prev和尾结点的next以及新节点的next和prev即可。
如图示：

示例代码：

    NODE node = GetNewNode();//获取新节点
	//先让他自己循环
	node->next = node;
	node->prev = node;
	int data;
	scanf("%d",&data);
	getchar();
	node->data = data;
	while(1){
		if(scanf("%d",&data)==1){
			getchar();
			NODE new = GetNewNode();
			new->data = data;
			InsertNode(node,new);
			ShowNode(node);
		}
		else
			break;
	}

注：在这里定义的规则是输入非数字就停止创建新节点。
给出GetNewNode函数代码：

NODE GetNewNode(){
	NODE new = malloc(sizeof(struct NODE));
	if(new==NULL){
		perror("获取内存失败！");
		exit(1);
	}else
	return new;
}

给出InsertNode函数代码：

//正向插入节点
void InsertNode(NODE node,NODE new){
	NODE temp = node;
	while(node->next != temp){//判断是否到达尾结点
		node = node->next;
	}
	node->next = new;
	new->prev = node;
	new->next = temp;
	temp->prev = new;
}

给出ShowNode函数代码：

void ShowNode(NODE node){
	NODE temp = node;
	printf("正向遍历双向循环链表：");
	while(node->next!=temp){//判断是否到达尾结点
		printf("%d\t",node->data);
		node = node->next;
	}
	printf("%d\t\n",node->data);//输出尾结点数据
}

三、排序插入

排序插入即按从小到大排列链表，创建新链表后寻找合适位置再插入，使得链表始终是按从小到大排列的。实现原理和单向链表排序插入类似，只是要多改变两个指针的指向，我的实现方法中把情况分为三类：
①插入的是第二个节点，直接插在头结点后面，如果头结点比新节点大，那么两个节点交换数据；
②中间节点，遍历链表找到两个连续节点一个节点比新节点小另一个节点比新节点大，插在中间；
③找不到比新节点大的节点，那么是最后一个节点，直接插在末尾。
如图示：

示例代码：

//按从小到大顺序插入
int SortInsertNode(NODE node,NODE new){
	NODE temp = node;
	if(node->next == node){//代表只有一个节点,就插到第一个节点后面
		node->next = new;
		new->prev = node;
		node->prev = new;
		new->next = node;
		if(new->data<=node->data){//如果新节点小于旧节点，则两个交换值
			int data = node->data;
			node->data = new->data;
			new->data = data;
		}
		return 1;//结束函数运行
	}else{//如果不是第一个节点
		while(node->next != temp){//开始遍历
			if(node->data<=new->data&&node->next->data>new->data){//判断某个节点是否小于新节点且该节点的下一个节点大于新节点
				//插在中间
				new->next = node->next;
				node->next->prev = new;
				node->next = new;
				new->prev = node;
				return 1;//结束运行
			}
		   node = node->next;
	    }
	}
	//能运行到这里说明新节点是最大的节点，直接插到最后
	node->next = new;
	new->prev = node;
	new->next = temp;
	temp->prev = new;
	return 1;
}

注：return无实际用途，仅仅为了结束函数运行。

四、应用

看到一道题目：
创建一个空的双向循环链表。将自然数作为链表节点里面的数据，并将若干个自然数插入链表。比如依次插入从1到10个自然数: 1，2，3，4，5，6，7、8，9，10然后通过某些操作，将其重新排列成1，3，5，7，9，10，8，6，4，2，即奇数升序偶数降序，并在屏幕上打印出来。
从中可以发现规律：奇数顺序不变，越小的偶数越扔后面，所以思路就来了：
从后往前遍历，如果遇到奇数则不变，如果遇到偶数，将节点断开插到链表末尾。
如图示：

示例代码：
注释较多，不再做解释。

NODE DropNode(NODE node){
	NODE first = node;//指向链表最前
	NODE q = node->prev,p;//指向链表最后，q是主指针，p是次指针
	NODE last = node->prev;//一直指向链表最后
	NODE temp = first;//最后使用
	while(q!=node){//遍历直到到达第一个节点
		if(q->data%2==0&&q!=last){//判断是否是偶数和最后一个节点，因为最后一个节点不管怎么样没必要移
			p = q;//赋值给p，不能影响主指针
			q = q->prev;//主指针向前移
			//从中断开
			p->prev->next = p->next;
			p->next->prev = p->prev;
			last->next = p;//插到最后
			p->prev = last;
			p->next = first;
			first->prev = p;
			last = p;//新插的节点成为最后的节点
		}
		else
		    q = q->prev;//主指针向前移
	}
	//判断第一个节点是否为偶数，如果是直接让第二个节点成为头结点
	if(first->data%2==0){
		temp = first->next;
	}
	return temp;//返回头结点
}

五、完整代码

//双向循环链表
#include<stdio.h>
#include<stdlib.h>
typedef struct NODE{
	int data;//要保存的数据
	struct NODE *next;//下一节点地址
	struct NODE *prev;//上一节点地址
}*NODE;
//获取新节点
NODE GetNewNode(){
	NODE new = malloc(sizeof(struct NODE));
	if(new==NULL){
		perror("获取内存失败！");
		exit(1);
	}else
	return new;
}
//正向插入节点
void InsertNode(NODE node,NODE new){
	NODE temp = node;
	while(node->next != temp){
		node = node->next;
	}
	node->next = new;
	new->prev = node;
	new->next = temp;
	temp->prev = new;
}
//按从小到大顺序插入
int SortInsertNode(NODE node,NODE new){
	NODE temp = node;
	if(node->next == node){//代表只有一个节点,就插到第一个节点后面
		node->next = new;
		new->prev = node;
		node->prev = new;
		new->next = node;
		if(new->data<=node->data){//如果新节点小于旧节点，则两个交换值
			int data = node->data;
			node->data = new->data;
			new->data = data;
		}
		return 1;//结束函数运行
	}else{//如果不是第一个节点
		while(node->next != temp){//开始遍历
			if(node->data<=new->data&&node->next->data>new->data){//判断某个节点是否小于新节点且该节点的下一个节点大于新节点
				//插在中间
				new->next = node->next;
				node->next->prev = new;
				node->next = new;
				new->prev = node;
				return 1;//结束运行
			}
		   node = node->next;
	    }
	}
	//能运行到这里说明新节点是最大的节点，直接插到最后
	node->next = new;
	new->prev = node;
	new->next = temp;
	temp->prev = new;
	return 1;
}
void ShowNode(NODE node){
	NODE temp = node;
	printf("正向遍历双向循环链表：");
	while(node->next!=temp){
		printf("%d\t",node->data);
		node = node->next;
	}
	printf("%d\t\n",node->data);
}
void ReverseShowNode(NODE node){
	NODE temp = node;
	printf("反向遍历双向循环链表：");
	while(node->prev!=temp){
		printf("%d\t",node->data);
		node = node->prev;
	}
	printf("%d\t\n",node->data);
}
NODE DropNode(NODE node){
	NODE first = node;//指向链表最前
	NODE q = node->prev,p;//指向链表最后，q是主指针，p是次指针
	NODE last = node->prev;//一直指向链表最后
	NODE temp = first;//最后使用
	while(q!=node){//遍历直到到达第一个节点
		if(q->data%2==0&&q!=last){//判断是否是偶数和最后一个节点，因为最后一个节点不管怎么样没必要移
			p = q;//赋值给p，不能影响主指针
			q = q->prev;//主指针向前移
			//从中断开
			p->prev->next = p->next;
			p->next->prev = p->prev;
			last->next = p;//插到最后
			p->prev = last;
			p->next = first;
			first->prev = p;
			last = p;//新插的节点成为最后的节点
		}
		else
		    q = q->prev;//主指针向前移
	}
	//判断第一个节点是否为偶数，如果是直接让第二个节点成为头结点
	if(first->data%2==0){
		temp = first->next;
	}
	return temp;//返回头结点
}
int main(){
	NODE node = GetNewNode();//获取新节点
	//先让他自己循环
	node->next = node;
	node->prev = node;
	int data;
	scanf("%d",&data);
	getchar();
	node->data = data;
	while(1){
		if(scanf("%d",&data)==1){
			getchar();
			NODE new = GetNewNode();
			new->data = data;
			InsertNode(node,new);//正向插入
			ShowNode(node);//输出
			ReverseShowNode(node);//反向输出
		}
		else
			break;
	}
	node = DropNode(node);//改变节点位置
	ShowNode(node);
	return 0;
}

到此结束！