计算机算法设计及分析.doc

<<计算机算法设计与分析>>
课程报告

问题陈述:
对所给元素存储于数组中和存储于链表中两中情况,写出自然合并排序算法.
解题思路:
将待排序元素分成大小大相同的两个集合,分别对两个集合进行排序,,再进行子数组的合并排序.
程序代码:
#include <>
const int N=100;
void ScanTarget(int target[], int n, int head[], int tail[]);
int CountHead(int head[]);
void MergeSort(int a[], int head[], int tail[], int m);
void MergePass(int x[], int y[], int s, int a[], int b[], int m);
void Merge(int c[], int d[], int l, int m, int r);
void main()
{
char a;
do
{
int target[N],head[N],tail[N];
int i=0,n,m;
for(; i<N; i++)
{
head[i]=-1;
tail[i]=-1;
}
cout<<"请输入要排序的总数:"<<endl;
cin>>n;
cout<<"请输入要排序的数列:" <<endl;
for(i=0; i<n; i++)
cin>>target[i];
ScanTarget(target,n,head,tail);
m=CountHead(head);
MergeSort(target,head,tail,m);
cout<<"排序后:"<<endl;
for(i=0; i<n; i++)
cout<<target[i]<<" ";
cout<<endl;
cout<<"是否继续(y/n):"<<endl;
cin>>a;
}
while(a!='n' && a!='N');
}
void ScanTarget(int target[], int n, int head[], int tail[])//扫描待排数组;
{
int i,j=0,k=0;
head[k]=0;
k++;
for(i=1;i<n;i++)
{
if(target[i-1]>target[i])
{
tail[j++]=i-1;
head[k++]=i;
}
}
tail[j]=n-1;
}
int CountHead(int head[])//求长度;
{
int i(0);
while(head[i]!=-1)
{
i++;
}
return i;
}
void MergeSort(int a[], int head[], int tail[], int m)
{
int b[N];
int s=1;
while(s<m)
{
MergePass(a,b,s,head,tail,m);
s+=s;
MergePass(b,a,s,head,tail,m);
s+=s;
}
}
void MergePass(int x[], int y[], int s, int a[], int b[], int m)
{
int i=0;
while(i <= m-2*s)
{
Merge(x,y,a[i],b[i+s-1],b[i+2*s-1]);
i=i+2*s;
}
if(i+s < m)
{
Merge(x,y,a[i],b[i+s-1],b[m-1]);
}
else
{
for(int j=i; j<m; j++)
for(int k=a[j]; k<=b[j]; k++)
y[k]=x[k];
}
}
void Merge(int c[], int d[], int l, int m, int r)
{
int i,j,k;
i=l;
j=m+1;
k=l;
while((i<=m) && (j<=r))
{
if( c[i] <= c[j] )
d[k++]=c[i++];
else d[k++]=c[j++];
}
if( i>m )
{
for(int q=j; q<=