习题－41.c

这些是数据结构结构的经典实现算法

//本程序只给出了算法思想
//读者可以自己完善本程序
void LinkedList_Merge_Sort2(LinkedList &L)
//初始归并段为最大有序子序列的归并排序,采用链表存储结构
{
	LNode *end[MAXSIZE]; //设立一个数组来存储各有序子序列的尾指针
	for(p=L->next->next,i=0;p;p=p->next) //求各有序子序列的尾指针
		if(!p->next||p->data>p->next->data) end[i++]=p;
		while(end[0]->next) //当不止一个子序列时进行两两归并
		{
			j=0;k=0; //j:当前子序列尾指针存储位置;k:归并后的子序列尾指针存储位置
			for(p=L->next,e2=p;p->next;p=e2) //两两归并所有子序列
			{
				e1=end[j];e2=end[j+1]; //确定两个子序列
				if(e1->next) LinkedList_Merge(L,p,e1,e2); //归并
				end[k++]=e2; //用新序列的尾指针取代原来的尾指针
				j+=2; //转到后面两个子序列
			}
		}//while
}//LinkedList_Merge_Sort2 
void LinkedList_Merge(LinkedList &L,LNode *p,LNode *e1,LNode *e2)
//对链表上的子序列进行归并,第一个子序列是从p->next到e1,第二个是从e1->next到e2
{
	q=p->next;r=e1->next;
	while(q!=e1->next&&r!=e2->next)
	{
		if(q->data<r->data)
		{
			p->next=q;p=q;
			q=q->next;
		}
		else
		{
			p->next=r;p=r;
			r=r->next;
		}
	}//while
	while(q!=e1->next)
	{
		p->next=q;p=q;
		q=q->next;
	}
	while(r!=e2->next)
	{
		p->next=r;p=r;
		r=r->next;
	}
}//LinkedList_Merge