改造一个双向循环链表，使右链域保持原来的顺序，而左链域从小到大顺序排列。

本题在之前发布过，但发现方法略有复杂。本次将更新一下最简单的思想方法 。点击查看原题出处

思想：

1. 改进：不需要对每个结点的左链域进行置空初始化，因为最后还是会重新赋值。只需要对头结点 L 初始化： L->prior = L；
2. 原方法：每次选出最小元素，采用尾插法排序，较为繁琐，而且指针变量太多。新方法：每次选出最大元素，进行头插法。这样代码更为简洁，同样可以实现从小到大排列

附上全部代码（运行结果）

//.h文件
#ifndef _LINKLIST_H_
#define _LINKLIST_H_

#include <iostream>
#include <fstream>
using namespace std;

#define OK 1
#define ERROR 0

typedef int Status;
typedef int ELEMTYPE;


typedef struct LNode
{
	ELEMTYPE data;  //数据域
	bool flag;  //标志位  判断是否选中为最大元素
	struct LNode *prior; //前驱
	struct LNode *next; //后继
}LNode,*LinkList;

Status initLinkList(LinkList &L) //初始化链表
{
	L = (LNode *)malloc(sizeof(LNode));
	if (!L)
	{
		cout << "空间不足\n";
		return ERROR;
	}
	L->prior = L->next = L;
}

Status CreateLinkList(LinkList &L)  //尾插法建表 读文件
{
	fstream file;
	file.open("data.txt",ios::in);
	if (!file)
	{
		cout<<"打开文件失败\n";
		return ERROR;
	}
	LNode *rear = L;
	while (!file.eof())
	{
		LNode *p = (LNode *)malloc(sizeof(LNode));
		file >> p->data;
		p->flag = false;
		p->next = L;
		L->prior = p;
		p->prior = rear;
		rear->next = p;
		rear = p;
	}
	return OK;
}

int getLength(LinkList L) //获取链表长度
{
	LNode *p = L->next;
	int n = 0;
	while(p != L)
	{
		p = p->next;
		n++;
	}
	return n;
}

void Upgrade_1(LinkList &L)  //左链域从小到大
{
	L->prior = L;   //让左链域初始化
	LNode *p,*q;
	for (int i = 1; i <= getLength(L); i++)  //右链域循环 每次找出一个最大元素
	{	
		p = L->next;
		ELEMTYPE max = -99999; //足够小
		while (p != L)
		{	
			if (p->data > max && p->flag == false)
			{
				max = p->data;
				q = p;
			}
			p = p->next;
		}
		q->flag = true;  //若最大元素被选中 则标记true 不再参与下轮比较
		q->prior = L->prior; //头插法 倒序排列 实现从小到大排列
		L->prior = q;
	}
}

void Upgrade_2(LinkList &L) //左链域从大到小
{
	L->prior = L;   //让左链域初始化
	LNode *p,*q;
	for (int i = 1; i <= getLength(L); i++)  //右链域循环 每次找出一个最小元素
	{	
		p = L->next;
		ELEMTYPE min = 99999; //足够小
		while (p != L)
		{	
			if (p->data < min && p->flag == false)
			{
				min = p->data;
				q = p;
			}
			p = p->next;
		}
		q->flag = true;  //若最大元素被选中 则标记true 不再参与下轮比较
		q->prior = L->prior; //头插法 倒序排列 实现从大到小排列
		L->prior = q;
	}
}

void visitRlink(LinkList L)  //右链域遍历
{
	LNode *p = L->next;
	while (p != L)
	{
		cout << p->data << " ";
		p = p->next;
	}
	cout << endl;
}

void visitLlink(LinkList L) //左链域遍历
{
	LNode *p = L->prior;
	while (p != L)
	{
		cout << p->data << " ";
		p = p->prior;
	}
	cout << endl;
}
#endif

//.cpp文件
#include "stdafx.h"
#include "LinkList.h"

int _tmain(int argc, _TCHAR* argv[])
{
	LinkList L;  //双循环链表
	initLinkList(L); //初始化链表
	CreateLinkList(L);  //建表
	Upgrade_1(L); 
	cout << "右链域（正常顺序）：";
	visitRlink(L);
	cout << "左链域（从小到大）：";
	visitLlink(L);
	initLinkList(L);
	CreateLinkList(L);
	Upgrade_2(L);
	cout << "左链域（从大到小）：";
	visitLlink(L);
	return 0;
}

运行结果