作出一個合併排序幾乎完全相同的僞代碼作業

我一直在做一個合併排序，到目前爲止，我認爲一切工作，除了我必須比較右和左數組的部分。幫幫我！（這是一個家庭作業，所以它必須是幾乎等同於這個僞代碼：作出一個合併排序幾乎完全相同的僞代碼作業

/*MERGESORT(A, p, r)] 
    if p < r 
     q = (p+r)/2 
     MERGESORT(A,p,q) 
     MERGESORT(A,q + 1, r) 
     MERGE(A,p,q,r) 

MERGE(A,p,q,r) 
    n1 = q - p + 1 
    n2 = r - q 
    let L[1...n1 + 1] and R[1...n2 + 1] be new arrays 
    for i = 1 to n1 
     L[i] = A[p + i - 1] 
    for j = 1 to n2 
     R[j] = A[q + j] 
    L[n1 + 1] = INFINITY 
    R[n2 + 1] = INFINITY 
    i = 1 
    j = 1 
    for k = p to r 
     if L[i] <= R[j] 
      A[k] = L[i] 
      i = i + 1 
     else 
      A[k] = R[j] 
      j = j + 1*/

這些都是合併排序功能。注：忽略整數類型，它什麼都不做還

void CensusData::mergeSort(int type) { 
    if(type == 0) //STOPPED FOR DEBUGGING 
     MERGE_SORT(type, 0, data.size() - 1); 
} 

void CensusData::MERGE_SORT(int type, int p, int r){ 
    //int q; 
    //cout << "data size " << data.size() << endl; 
    std::cout << "MERGE_SORT START ///("<< p << ", " << r << ")" <<std::endl; 
    if(p < r) 
    { 
     int q = (p + r)/2; 
     MERGE_SORT(type, p, q); 
     MERGE_SORT(type, q + 1, r); 
     MERGE(type, p, q ,r); 
    } 
} 

void CensusData::MERGE(int type, int p, int q, int r){ 
    if(type == 0) 
    { 
     std::cout << "MERGING WITH: (" << p << ", "<< q <<", " << r<< ")"<< std::endl; 
     //int n1; 
     //int n2; 
     int n1 = q - p + 1; 
     int n2 = r - q; 
     cout << "N1: " << n1 <<" N2:" << n2 << endl; 
     Record* L[n1 + 1]; 
     Record* R[n2 + 1]; 
     L[n1 + 1] = NULL; 
     R[n2 + 1] = NULL; 
     for(int i = 0; i < n1; i++) 
     { 
      //if (L[i] == NULL) 
       //continue; 
      cout << "P, I: " << p <<", "<< i<< endl; 
      cout << "filling array L: " << data[p + i]->population << endl; 
      L[i] = data[p + i]; 
      cout<< L[i]->population << endl; 
     } 
     //cout << "J: " << j << endl; 
     for(int j = 0; j < n2; j++) 
     { 
      //if(R[j] == NULL) 
       //continue; 
      cout << "filling array R: " << data[q + j + 1]->population<<endl; 
      R[j] = data[q + j + 1]; 
      cout << R[j]->population << endl; 
     } 
     //THIS IS WHERE I THINK THE PROBLEMS ARE OCCURING FROM VVVVVVVVVVV 
     int i = 0; 
     int j = 0; 
     for(int k = p; k <= r; k++) 
     { 
      if(L[i]->population < R[j]->population) 
      { 
       cout << "TRUE" << endl; 
       data[k] = L[i]; 
       i = i + 1; 
      } 
      else if (L[i]->population > R[j]->population) 
      { 
       cout << "FALSE" << endl; 
       data[k] = R[j]; 
       j = j + 1; 
      } 
     } 
      /*std::vector<Record*>::iterator it = data.begin(); 
    while (it != data.end()) { 
     std::cout << *(*it)->city << ", " 
       << *(*it)->state << ", " 
       << (*it)->population << std::endl; 
     it++;}*/ 

    } 
}

輸入:::

Vina, California, 237 
San Francisco, California, 812826 
Santa Fe, New Mexico, 68642

輸出:::

Vina, California, 237 
Santa Fe, New Mexico, 68642 

Program received signal SIGSEGV, Segmentation fault. 
0x00445cf7 in std::basic_ostream<char, std::char_traits<char> >& std::operator<< <char, std::char_traits<char>, std::allocator<char> >(std::basic_ostream<char, std::char_traits<char> >&, std::basic_string<char, std::char_traits<char>, std::allocator<char> > const&)() 
    at /usr/lib/gcc/i686-pc-cygwin/3.4.4/include/c++/iostream:77 
77  static ios_base::Init __ioinit;

從10

輸入例2 :::

Vina, California, 237 
San Francisco, California, 812826 
Santa Fe, New Mexico, 68642 
Roseville, California, 1293 
New York, New York, 283822 
pieland, Conneticut, 283822

輸出::::

Program received signal SIGSEGV, Segmentation fault. 
0x004031ae in CensusData::MERGE (this=0x28aa40, type=0, p=0, q=2, r=5) 
    at CensusDataSorts.cpp:105 
105     if(L[i]->population < R[j]->population)

來源

2013-10-11 Ryan Mann

這些陳述是錯誤的（越界數組訪問）

L[n1 + 1] = NULL; 
    R[n2 + 1] = NULL;

我想你的意思可能是

L[n1] = NULL; 
    R[n2] = NULL;

因爲在僞代碼數組中，從1開始，但在您的代碼數組中開始一個零。我預計這種差異將成爲你大部分問題的原因。

另一個問題是，您使用NULL來表示僞代碼調用INFINITY，但是當您進行比較時，您不檢查NULL。

所以

 if(L[i]->population < R[j]->population)

成爲

 if ((L[i] != NULL && R[j] != NULL && L[i]->population < R[j]->population) || 
      (L[i] == NULL && R[j] != NULL))

下一個if語句

 else if ((L[i] != NULL && R[j] != NULL && L[i]->population > R[j]->population) || 
      (L[i] != NULL && R[j] == NULL))

來源

2013-10-11 09:06:05 john

我這樣做，和類似的變化，現在的輸入示例2輸出::: 237，1293， 68642，然後seg故障。 –

關於如何在if和if語句中實現它的任何指針，我一直盯着這個代碼幾個小時，真的很難想象。 –

我補充說，如果和改變，如果其他只是一個ELSE，現在沒有輸出，它在這裏seg故障：編程接收到的信號SIGSEGV，分段故障。 0x0040304e在CensusData :: MERGE（this = 0x28aa40，type = 0，p = 0，q = 1，r = 2） at CensusDataSorts.cpp：87 87 cout <<「fill array L：」<< data [ p + i] - > population << endl; –

作出一個合併排序幾乎完全相同的僞代碼作業

回答

相關問題