MergeSort算法與對象類

Question

我一直在試圖弄清楚這個東西在過去的幾個小時，但沒有成功。

我有幾個類用於添加數據，所以我可以顯示它們，但現在我必須實現MergeSort算法根據標題對這些數據進行排序。

我有對象CD，其中所有其他類繼承，對象CD具有屬性標題，類型char。

現在，當我的指針傳遞給我的班級我做的比較和檢查，但它不工作應該如何：

這是我對排序算法功能：

void merge(CD *a[], int, int, int); 

void merge_sort(CD *a[], int low, int high) { 
    int mid; 
    if (low < high) { 
     mid = (low + high)/2; 
     merge_sort(a, low, mid); 
     merge_sort(a,mid + 1, high); 
     merge(a, low, mid, high); 
    } 
} 

void merge(CD *a[], int low, int mid, int high) { 
    int h, i, j, k; 
    CD *b; 
    h = low; 
    i = low; 
    j = mid + 1; 


    while ((h <= mid) && (j <= high)) { 
     if (a[h]->title[100] <= a[j]->title[100]) { 
      b[i].title[100] = a[h]->title[100]; 
      h++; 
     } 
     else { 
      b[i].title[100] = a[j]->title[100]; 
      j++; 
     } 
     i++; 
    } 
    if (h > mid) { 
     for (k = j; k <= high; k++) { 
      b[i].title[100] = a[k]->title[100]; 
      i++; 
     } 
    } 
    else { 
     for (k = h; k <= mid; k++) { 
      b[i].title[100] = a[k]->title[100]; 
      i++; 
     } 
    } 
    for (k = low; k <= high; k++) 
     a[k]->title[100] = b[k].title[100]; 
} 

任何想法如何實現這樣的事情？

Answer 1

您在codepad上發佈的代碼有幾處錯誤，我會在程序註釋中指出。既然你沒有給我們定義Popular，Symphony和Opera，我會有我自己的。爲了方便起見，我將所有代碼放在一個文件中。

#pragma once 
#include <string> 
#include <iostream> 

using namespace std; 

class CD { 
public: 
    string publisher, title, location, year, empty; 
public: 
    CD() 
    { 
     publisher = ""; 
     title = ""; 
     location = ""; 
     year = ""; 
     empty = ""; 
    } 

    void virtual input() = 0; 

    void virtual output() = 0; 
}; 


class Popular : public CD 
{ 
public: 
    Popular(const string& name) 
    { 
     title = name; 
    } 
    virtual void input() 
    { 
     return; 
    } 
    virtual void output() 
    { 
     return; 
    } 
}; 

void merge(CD *a[], int, int, int); 

void merge_sort(CD *a[], int low, int high) { 
    int mid; 
    if (low < high) { 
     mid = low + (high - low)/2; //avoid overflow 
     merge_sort(a, low, mid); 
     merge_sort(a, mid + 1, high); 
     merge(a, low, mid, high); 
    } 
} 

void merge(CD *a[], int low, int mid, int high) { 

    int p1 = low; 
    int p2 = mid + 1; 
    CD ** merged = (CD**)malloc(sizeof(CD*) * (high - low + 1)); // CD *b[high] isn't illegal c++ syntax, VLA is part of C99. 
    int p = 0; 
    while(p1 < mid + 1 && p2 < high + 1) 
    { 
     if(a[p1]->title > a[p2]->title) 
     { 
      merged[p] = a[p2]; 
      p2++; 
     } 
     else 
     { 
      merged[p] = a[p1]; 
      p1++; 
     } 
     p++; 
    } 

    while(p1 < mid + 1) 
    { 
     merged[p++] = a[p1++]; 
    } 

    while(p2 < high + 1) 
     merged[p++] = a[p2++]; 

    for(int i = 0;i < (high - low + 1); i++) 
    { 
     a[low + i] = merged[i]; 
    } 

    free(merged); 
} 

int main() { 
    CD *cdptr[100]; //pointer declaration for each of our class 

    int n = 0, choose; 

    // just to test the mergesort 
    CD* c1 = new Popular("hello"); 
    CD* c2 = new Popular("world"); 
    CD* c3 = new Popular("coldplay"); 
    CD* c4 = new Popular("pink"); 

    cdptr[n++] = c1; 
    cdptr[n++] = c2; 
    cdptr[n++] = c3; 
    cdptr[n++] = c4; 

    char terminate = 'n'; // you should initialize this variable. 

    do // do-while statement which allows the user to enter data and terminate the program when he wants 
    { 
     cout << "\n1.Classical"; 
     cout << "\n2.Popular"; 
     cout << "\n3.Sort"; 
     cout << "\n4.Display"; 
     cout << "\n5.Terminate program"; 
     cout << endl << endl; 
     cout << "\nChoose category: "; 
     cin >> choose; 
     switch (choose)       //switch for the user to choose the type of input 
     { 
      //skip the case 1, 2 
      case 3: 
       merge_sort(cdptr, 0, n - 1); // element indices begin at 0. 
       break; 
      case 4: 
       if (n == 0) 
        cout << "\nNo data entered!" << endl; 
       for (int i = 0; i < n; i++) { 
        cdptr[i]->output(); 
        cout << endl; 
       } 
       break; 
      case 5: 
       cout << "\nDo you want to terminate the program? (y/n)"; 
       cin >> terminate; 
       break; 
      default: 
       cout << "\nNot recognized value!" << endl; 
     } 
    } while (terminate != 'y'); 

    for(int i = 0; i < 4; ++i) 
     cout<<cdptr[i]->title<<endl; 

    delete c1; 
    delete c2; 
    delete c3; 
    delete c4; 
    return 0; 
} 

下面是輸出：

1.Classical 
2.Popular 
3.Sort 
4.Display 
5.Terminate program 


Choose category: 3 

1.Classical 
2.Popular 
3.Sort 
4.Display 
5.Terminate program 


Choose category: 5 

Do you want to terminate the program? (y/n)y 
coldplay 
hello 
pink 
world 

Answer 2

首先，更新您的問題，以顯示merge,merge_sort和CD的真實代碼。我將引用評論中發佈的實際代碼。

你的問題可能源於你排序的標題，而不是排序基於標題。在您的代碼中，您將CD的標題分配給另一個的任何地方，都會出錯。你比較的冠軍，但你重新定位和重新排列對象本身（或在您的情況下，指向對象本身）

總之，要解決這個問題，您只需更換任何像這樣的代碼：

x->title = y->title; 

與此：

x = y; 

例如，而不是

b[i]->title = a[h]->title; 

你應該寫

b[i] = a[h]; 

順便說一句，內存分配和釋放是不是你做作爲一種事後的東西，看它是否有效與否！即使是平庸的程序員也要小心處理記憶;善良的人以純粹的愛和尊重處理記憶。