Mergesort, 이상한 행동

Question

내가 뭘하려는거야. cost [] node1 [] 및 node2 []의 배열이 3 개 있습니다. 이들 엔트리는 edge1 [i], node2 [i] 및 cost [i]를 갖는 그래프의 에지에 대응하고, 에지 가중치가 cost [i] 인 에지가 노드 2 [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 노드 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으로 동일하게됩니다. 즉 노드 1 노드 2의 모든 엔트리와 비용 배열은 0입니다. 아무도 왜 이런 일이 발생하는지 말할 수 있습니까? 감사!

Answer 1

아마도 i++ 작업의 부작용을 잊어 버렸을 것입니다. 그 곳에서 부작용으로 일할 필요가 전혀 없습니다. 그렇게하지 마십시오.