(新手学习中)以下是一个关于归并排序的函数。一开始cnt初始化为0(本来应该是plo),然后奇怪的事发生了:在调试时cnt的值开始随意的变化(以下各图均是运行一步的结果)。求大神解答原因。
如果你的代码没有修改某个变量,但是它无故变动,那么就说明你的数组访问有越界的行为。
你把代码放上来,我可以帮你调试看看。
一开始写的是这样的
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define random(x) (rand()%x)
#define std 3
#define lim 10000
void ScanfArray(int *a,int n);
void RandomArray(int *a,int n);
void PrintfArray(int *a,int n);
void MergeSort(int *a,int n,int *p);
void MSort(int *a,int *tmp,int lo,int hi,int *p);
void Merge(int *a,int *tmp,int plo,int phi,int hi,int *p);
int main()
{
int num;
int cnt=0;
int *p=&cnt;
printf("MSort\n");
RandomArray(a,num);
printf("原始数据:\n");
PrintfArray(a,num);
MergeSort(a,num,p);
printf("有序数据:\n");
PrintfArray(a,num);
printf("cnt=%d\n\n",*p);
return 0;
}
void RandomArray(int *a,int n)
{
int i;
srand((unsigned)time(NULL));
printf("下面随机生成1~%d的数据\n",lim);
for(i = 0;i < n;i++)
{
a[i]=random(lim);
}
}
void PrintfArray(int *a,int n)
{
int i;
for(i = 0;i < n;i++)
{
printf("a[%d] = %d\t",i,a[i]);
}
printf("\n");
}
void MergeSort(int *a,int n,int *p)
{
int *tmp;
tmp = (int*)malloc(n*sizeof(int));
if(tmp)
{
MSort(a,tmp,0,n-1,p);
free(tmp);
}
}
void MSort(int *a,int *tmp,int lo,int hi,int *p)
{
int mi;
if(hi>lo)
{
mi = (hi+lo)/2;
MSort(a,tmp,lo,mi,p);
MSort(a,tmp,mi+1,hi,p);
Merge(a,tmp,lo,mi+1,hi,p);
}
}
void Merge(int *a,int *tmp,int plo,int phi,int hi,int *p)
{
int i = plo,j = phi,_hi=hi;
int count=0; /*一开始写错的地方,应该改成plo*/
while(i <= phi-1 && j <= hi)
{
if(a[i] < a[j])
{
tmp[count++] = a[i++];
}
else if(a[i] > a[j])
{
tmp[count++] = a[j++];
}
else
{
tmp[count++] = a[i++];
tmp[count++] = a[j++];
}
(*p)++;
}
while(i <= phi-1)
{
tmp[count++] = a[i++];
(*p)++;
}
while(j <= hi)
{
tmp[count++] = a[j++];
(*p)++;
}
for(i = 0;i < hi-plo+1;i++)
{
a[_hi] = tmp[_hi];
(_hi)--;
(*p)++;
}
}
后来改了下Merge函数,又重启了几次,突然好了。
下面是改过的Merge函数
void Merge(int *a,int *tmp,int plo,int phi,int hi,int *p)
{
int i = plo,j = phi,_hi=hi;
int count=plo;
while(i <= phi-1 && j <= hi)
{
if(a[i] < a[j])
{
tmp[count] = a[i];
count++;
i++;
}
else if(a[i] > a[j])
{
tmp[count] = a[j];
count++;
j++;
}
else
{
tmp[count] = a[i];
tmp[count+1] = a[j];
count+=2;
i++;
j++;
}
(*p)++;
}
while(i <= phi-1)
{
tmp[count] = a[i];
count++;
i++;
(*p)++;
}
while(j <= hi)
{
tmp[count] = a[j];
count++;
j++;
(*p)++;
}
for(i = 0;i < hi-plo+1;i++)
{
a[_hi] = tmp[_hi];
(_hi)--;
(*p)++;
}
}
你在调用函数,还在递归,cnt的值当然会变了