这就是我想要做的。
存在3个数组,即cost [] node1 []和node2 []。
这些整体对应于具有node1 [i],node2 [i]和cost [i]的图的边,该边指定了从顶点node1 [i]到node2 [i]的边的权重为cost [i] 。

我正在尝试根据权重对这些边缘进行排序,即使用merge-sort对cost []数组进行排序。但是,无论何时,只要更改cost []数组中的条目,我都还想更改node1和node2数组中的相应条目,因为甚至必须修改图的节点。也就是说,如果node1 [] = 1,2,3和node2 [] = 2,3,1 cost [] = {7 4 8},则在对成本数组进行排序之后,node1和node2应该看起来像node1 [] = 2,1 ,3 node2 [] = 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和cost数组的全部都是0。有人能告诉我为什么会这样吗?谢谢!

最佳答案

您可能已经忘记照顾i++操作的副作用了。那个地方根本不需要副作用,不要那样做。

关于c - 合并排序,奇怪的行为,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/13967422/

10-13 07:37