sort.c

ReverseSort程序描述： 本程序包括：线性链表的逆序(从尾到头排序),链表正常排序(按.num项从大到小排序)

/* 文件 Sort.c
 * 功能：排序实现文件
 * Author : xinglanting
 * Date : 2005-11-10
 */

#include "Sort.h"

unsigned nNode = 0; //链表个数初始化

/*
 * 功能描述：链表创建
 * 返回值：返回链表头指针
 */
SList *CreateList()
{
	SList *head = NULL; //链表头指针
	SList *p1 = NULL, *p2 = NULL;

	p1 = (SList *)malloc(sizeof(SList));
	if (p1 == NULL)
		return NULL;

	head = p1;
	p2 = p1;

	printf("please input a number: \n");
	scanf("%d",&p1->num);

	if (p1->num < 0.1)
		return NULL;

	nNode ++;
	while (1)
	{
		p1 = (SList *)malloc(sizeof(SList));
		if (p1 == NULL)
			return head;

		scanf("%d",&p1->num);
		if (p1->num < 0.01)  //小于等于0时退出循环
			break;

		p2->Next = p1;
		p2 = p1;

		nNode ++;
	}
	p2->Next = NULL;
	printf("\nlist node number: %d",nNode);
	printf("\n");
 
	return head;
}

/*
 * 功能描述：链表逆序排列
 * 返回值：返回链表头指针
 */
SList *ReverSort(SList *head)
{
	SList *p1 = NULL,*p2 = NULL; //指向旧的链表
	SList *p0 = NULL; //指向新的链表

	if (nNode <= 1) //如果节点小于等于1个
		return head;

	p1 = p2 = head;
	p0 = p2;

	if (nNode == 2)  //如果节点就2个
	{
		p2 = p2->Next;
		p0->Next = NULL;
		p2->Next = p0;
		p0 = p2;

		return p0;
	}
	else if (p0 == head) //如果节点大于2个
	{
		p2 = p2->Next;		
		p1 = p2->Next;
		p0->Next = NULL;
	}

	while ((p2->Next != NULL) && (p1->Next != NULL))
	{
		p2->Next = p0;
		p0 = p2;
		p2 = p1;
		p1 = p1->Next;
	}

	p2->Next = p0;   //最后两个节点赋给新节点
	p0 = p2;
	p1->Next = p0;
	p0 = p1;

	return p0;
}

/*
 * 功能描述：链表排序(按.num由大到小的顺序排列)
 * 返回值：返回链表头指针
 */
SList *Sort(SList *head)
{
	SList *p1 = NULL,*p2 = NULL; //指向旧的链表
	SList *p0 = NULL; //指向新的链表
	unsigned int i,j;

	if (nNode <= 1) //如果节点小于等于1个
		return head;

	p0 = p2 = head;

	for (i = 0; i < nNode - 1; i++) //如果节点>=2个
	{
		p1 = p2 = head;
		p0 = head;
		p1 = p0->Next;

		for (j = 0; j < nNode - i - 1; j++)
		{
			if (j == 0)  //链头的处理
			{
				if (p1->num > p0->num)
				{
					if (p1->Next == NULL) ////如果节点==2个
					{
						p1->Next = p0;
						p0->Next = NULL;
						head = p1;
					}
					else //////如果节点>2个
					{
						p0->Next = p1->Next;
						p1->Next = p0;
						p2 = p1;
						p1 = p0->Next;
						head = p2;
					}
				}
				else
				{
					p0 = p1;
					p1 = p1->Next;
				}
			}
			else  //不是链头的处理
			{
				if (p1->Next != NULL) //不是链头,链尾的处理
				{
					if (p1->num > p0->num)
					{
						p2->Next = p1;
						p0->Next = p1->Next;
						p1->Next = p0;

						p2 = p1;
						p1 = p0->Next;
					}
					else
					{
						p2 = p0;
						p0 = p1;
						p1 = p1->Next;
					}
				}
				else //链尾的处理
				{
					if (p1->num > p0->num)
					{
						p2->Next = p1;
						p1->Next = p0;
						p0->Next = NULL;
					}				
				}
			}
		}
	}

	return head;
}

/*
 * 功能描述：链表显示
 * 返回值：无
 */
void Output(SList *head)
{
	SList *p = NULL;
	unsigned int i;

	if (head == NULL)
		return ;

	p = head;

	printf("All list are : \n");

	for (i = 0; i < nNode; i++)
	{
		printf("%d ",p->num);
		p = p->Next;
	}
	printf("\n");

	return;
}