这就是我想要做的。有 3 个数组，cost[] node1[] 和 node2[]。这些整体对应于带有 node1[i]、node2[i] 和 cost[i] 的图的边，指定有一条边从顶点 node1[i] 到 node2[i]，边权重为 cost[i] .
我正在尝试根据它们的权重对这些边进行排序，即使用合并排序对 cost[] 数组进行排序。但是，每当我更改 cost[] 数组中的条目时，我也想更改 node1 和 node2 数组中的相应条目，因为即使是图形的节点也必须修改。即如果 node1[]=1,2,3 和 node2[]=2,3,1 cost[]={7 4 8} 那么在对成本数组进行排序之后，node1 和 node2 应该看起来像 node1[]=2,1 ,3 节点 2[]=3,2,1。和成本[]=4,7,8
这是我的代码。
#include<stdio.h>
#include<stdlib.h>
int merge_sort(int arr[],int low,int high,int node1[],int node2[])
{
int mid;
if(low<high) {
mid=(low+high)/2;
// Divide and Conquer
merge_sort(arr,low,mid,node1,node2);
merge_sort(arr,mid+1,high,node1,node2);
// Combine
merge(arr,low,mid,high,node1,node2);
}
return 0;
}
int merge(int arr[],int l,int m,int h,int node1[],int node2[])
{
int arr1[80000],arr2[80000]; // Two temporary arrays to
int arr3[70000],arr4[70000];
int arr5[70000],arr6[70000];
int n1,n2,i,j,k;
n1=m-l+1;
n2=h-m;
for(i=0; i<n1; i++)
{
arr1[i]=arr[l+i];
arr3[i]=node1[l+i];
arr5[i]=node2[l+i];
}
for(j=0; j<n2; j++)
{
arr2[j]=arr[m+j+1];
arr4[i]=node1[m+j+1];
arr6[i]=node2[m+j+1];
}
arr1[i]=99999; // To mark the end of each temporary array
arr2[j]=99999;
arr3[i]=99999;
arr4[j]=99999;
arr5[i]=99999;
arr6[j]=99999;
i=0;
j=0;
for(k=l; k<=h; k++) { //process of combining two sorted arrays
if(arr1[i]<=arr2[j])
{
arr[k]=arr1[i++];
//node1[k]=arr3[i++]; COMMENTED LINES!!!!!!!!!!!
//node2[k]=arr5[i++];
}
else
{
arr[k]=arr2[j++];
//node1[k]=arr4[j++]; COMMENTED LINES!!!!!!!!~!
//node2[k]=arr6[j++];
}
}
return(0);
}
int main(void)
{
int i,j,n,vert1,vert2,weight;
scanf("%d",&n);
int adjmat[n+1][n+1],cluster[n+1][n+1];
int *cost,*node1,*node2;
node1=malloc(sizeof(int)*1000000);
node2=malloc(sizeof(int)*1000000);
cost=malloc(sizeof(int)*1000000);
for(i=0;i<n+1;i++)
for(j=0;j<n+1;j++)
{
adjmat[i][j]=0;
cluster[i][j]=0;
}
for(i=1;i<n+1;i++)
cluster[i][0]=i;
for(i=1;i<(n+1)*(n+1);i++)
{
scanf("%d %d %d",&vert1,&vert2,&weight);
node1[i]=vert1;
node2[i]=vert2;
cost[i]=weight;
if(node1[i]==node1[i-1] && node2[i]==node2[i-1] && cost[i]==cost[i-1])
break;
// printf("%d %d %d\n",node1[i],node2[i],cost[i]);
adjmat[vert1][vert2]=weight;
adjmat[vert2][vert1]=weight;
}
printf("\n%d\n",i);
merge_sort(cost,1,124751,node1,node2);
for(j=1;j<i;j++)
printf("%d %d %d\n",node1[j],node2[j],cost[j]);
return(0);
}
每当我评论合并函数中的行时，代码都会设法对成本数组进行排序。但是，每当我取消注释这些行时，一切都等于 0。即 node1 node2 和成本数组的所有整数都是 0。谁能告诉我为什么会这样？谢谢！