mergesort.cpp

要求先对所输入序列进行扫描。输入序列为整形数据

// 文件名：MergeList.cpp         
// 功能： 用归并算法对链表进行排序   


#include "iostream.h"                              //输入输出流
#include <malloc.h>                                //内存管理
#define  NULL  0                                   //空指针定义
#define  MAXSIZE  100                             //结点个数最大为100
typedef int ElemType;                             //定义结点元素为整型数据 
typedef struct LNode{
	ElemType data;                               //结点数据域
	struct LNode * next;                         //指针域指向下一个结点
}LNode, * LinkList;                              //定义结点数据结构
LNode *Head[MAXSIZE];                            //设立一个数组来存储各有序子序列的头指针


void CreateList_L(LinkList &L, int n){
	//逆位序输入n个元素的值，建立带头结点的单链线性表
	LNode  * p;
	for(int i = n; i > 0; --i){
		p = (LinkList)malloc(sizeof(LNode));     //生成新结点
		cout<<"请输入第["<<n-i+1<<"]个结点元素值：";
		cin>>p->data;                            //输入元素值
		p->next = L->next;  L->next = p;         //插入到表头
	}
}//CreateList_L

void ClearList_L(LinkList &L)                    //清空链表中除头结点外的所有结点
{
	LNode *q, * p = L->next;
	q=p;
	while(p){
		q = q->next;
		free(p);
		p = q;
	}
	L->next = NULL;		
}//ClearList_L

void DivideList_L(LinkList &L)
{
	int i =1;
	LNode *q,* p = L->next;
	Head[0]=L->next;
	while(p->next!=NULL){
		if(p->data > p->next->data){
			Head[i] = p->next;  
			i++;   q=p;
			p=p->next;
			q->next=NULL;//若下一个结点数据域小于于该结点数据域，则将下个结点设为新的子列
		}
		else p = p->next;
	}
}//DivideList_L


LNode *Merge(LNode *first,LNode *second)   //对链表上的子序列进行归并
{
	LNode *last_sorted;                    //指向排好序的最后一个元素
	LNode combined;                        //声名一个哑变量，指向排好序的表
	last_sorted = &combined;               //将最后元素指针指向哑变量的地址
	while(first!=NULL && second!= NULL){   //将数据按序输入以哑变量为头结点的链表
		if(first->data <= second->data){
			last_sorted->next = first;
			last_sorted = first;
			first = first->next;
		}
		else{
			last_sorted->next = second;
			last_sorted = second;
			second = second->next;
		}
	}
	if(first == NULL)
		last_sorted->next = second;
	else
		last_sorted->next = first;
	return combined.next;
}//Merge


void Merge_Sort(LinkList &L)//初始归并段为最大有序子序列的归并排序,采用链表存储结构
{
	int i,k,n=1;
	for(i=1;i<MAXSIZE;i++)       //对子列进行计数
			if(Head[i]!=NULL)
				n++;
	while(n>1){
		n=1;
		for(i=1;i<MAXSIZE;i++)   //对子列进行计数
			if(Head[i]!=NULL)
				n++;	
		k=1;
		while(Head[k]==NULL)
			if((k+1)<MAXSIZE)k++;
		Head[0] = Merge(Head[0],Head[k]);//归并排序主体（采用非递归算法）
		Head[k] = NULL;
		n--;
	}
 	L->next = Head[0];
}//Merge_Sort


char ReadCommand()                  //读取命令操作符
{
	char cmd;
	bool waiting = true;
	cout<<"请选择一个操作符，按回车键<Enter>确认:";
	while(waiting){
		cin>>cmd;
		if(cmd=='i'||cmd=='p'||cmd=='q')//判断命令输入是否正确
			waiting=false;
		else{
			cout<<"请输入一个有效的操作符："<<endl
				<<"[i]创建一个链表"<<endl
				<<"[p]打印排序后的结果"<<endl
				<<"[q]退出该程序"<<endl;
		}
	}
	return cmd;//返回命令操作符
}


bool Interpret(char cmd,LinkList &L)                           	//解释执行操作命令cmd
{
	int n = 0;
	LNode *p;
	switch(cmd){
	case 'i':
		//创建链表并自动排序
		if(L->next!=NULL){
			ClearList_L(L);
			for(int i=0;i<MAXSIZE;i++)
			Head[i] = NULL;
		}
		while(n<1||n>MAXSIZE){
			cout<<"请输入元素个数(1--"<<MAXSIZE<<")：";
			cin>>n;
		}
		CreateList_L(L,n);
		p=L->next;
		cout<<"排序前的链表元素值为："<<endl;
		while(p){
			cout<<p->data<<",";
			p=p->next;
		}
		cout<<endl;
		DivideList_L(L);
		Merge_Sort(L);
		p=L->next;
		cout<<"排序后的链表元素值为："<<endl;
		while(p){
			cout<<p->data<<",";
			p=p->next;
		}
		cout<<endl;
		break;
	case 'p':
		//打印链表
		p=L->next;
		if(!p)cout<<"请先创建链表!!!"<<endl;
		cout<<"排序后的链表元素值为："<<endl;
		while(p){
			cout<<p->data<<",";
			p=p->next;
		}
		cout<<endl;
		break;
	case 'q':
		//退出
		cout<<"Task has been Finished!"<<endl;
		return false;
	}
	return true;
}

void Frame()                //排印演示程序界面
{
	cout<<"                  该演示程序处理的元素类型为<整型数据>"<<endl
		<<"*******************************************************************************"<<endl
		<<"                            程序执行菜单："<<endl
		<<"                         i----创建一个单链表"<<endl
		<<"                         p----打印排序后结果"<<endl
		<<"                         q----退出该演示程序"<<endl
		<<"*******************************************************************************"<<endl
		<<"请输入一个操作符： [i], [p] OR [q]"<<endl;
}


void main()	        //程序主体
{
	Frame();          //界面函数
	LNode * L1;
	for(int i=0;i<MAXSIZE;i++)      //初始化头指针数组
		Head[i] = NULL;
	L1 = (LinkList)malloc(sizeof(LNode));
	L1->next = NULL;                              //先建立一个带头结点的单链表
	while(Interpret(ReadCommand(),L1));           //执行用户输入命令
}