main.cpp

包括图、二叉树、链表

#include "List.h"
#include<time.h>
#include<stdlib.h>
int count=0;
void print(List<int>list)
{		
	    int data;
		cout<<"第"<<(count++)<<"次归并:";
		for(int i=1;i<list.size();i++)
		{
			list.retrieve(i,data);
	        cout<<data<<" ";
		}		
		cout<<endl;	
}
void Merge(List<int>&source,List<int>&dest,int low ,int mid,int high){     //把两个有序的表连在一起 
	int i,j,k;
	int key1,key2;
	i=low;j=mid+1;k=low;
	while(i<=mid&&j<=high)
	{
		source.retrieve(i,key1);
		source.retrieve(j,key2);
		if(key1<=key2) 
		{
			dest.replace(k++,key1);
			i++;
		}
		else 
		{
			dest.replace(k++,key2);
			j++;
		}			
	}	
	while (i<=mid) 
	{
		source.retrieve(i++,key1);
		dest.replace(k++,key1);
	}
	while (j<=high) 
	{
		source.retrieve(j++,key2);
		dest.replace(k++,key2);
	}			
}
void MergePass(List<int>&source,List<int>&dest,int n,int len){       //排序的分开啊!

	int i=1,j;
	int key;	
	while(i+2*len-1<=n){
		Merge(source,dest,i,i+len-1,i+2*len-1);
		i=i+2*len;
	}
	if(i+len-1<n)
		Merge(source,dest,i,i+len-1,n);
	else 
		for(j=i;j<=n;j++){
			source.retrieve(j,key);		
			dest.replace(j,key);
		}
	print(dest);
}
void MergeSort(List<int>&source,List<int>&dest,int n){      

	int len=1;	
	while(len<n){	
		MergePass(source,dest,n,len);len*=2;			
		MergePass(dest,source,n,len);len*=2;
	}	
}
void rand_seed(){                     //以系统的时间为随机数种子

	int seed=static_cast<int>(time(0));
	srand(seed);
}
int rand_int(char a,char b){                   //产生从a到b的随机数

	return a+rand()%(b-a+1);
}
void main()
{	
	List<int>source;
    List<int>dest;
	int n,data;
	rand_seed(); 
    cout<<"please input the max(n):";
	cin>>n;
    for(int i=0;i<n+1;i++)
	  source.insert(i,rand_int(1,100));	
	dest=source;
	print(source);
	MergeSort(source,dest,n);	
}