C++抽象基類ptrs到ptrs數組

我有一個抽象基類（Comparable），它具有虛擬繼承它的Date和Time以及一個DateTime類，它繼承自Date和Time。C++抽象基類ptrs到ptrs數組

我的問題是這樣的：我的任務是動態分配一個可比較數組。

Comparable ** compArray; 
compArray = new Comparable *[n]; // where n is user specified number of elements

然後我用交替順序填充DateTimes的數組。我需要使用快速排序和bubblesort組合來排序此數組。如果長度爲泡沫< 8. Comparable ** from和Comparable **是我允許使用的唯一參數。

但我完全卡住了。在這一點上，由於它很瘋狂的隨意性，所以它不值得粘貼在我的代碼中。

任何幫助將不勝感激。我花了幾個小時試圖完成這個任務，只在我的項目中進行了排序。哪個明天早上到期。

由於提前，喬爾

編輯：

void Sort(Comparable** a); 
    void quicksort(Comparable** from, Comparable** to); 
    Comparable** partition(Comparable** from, Comparable** to); 
    void Swap(Comparable** from, Comparable** to);  
    void safeRead(istream& sin, Comparable* d, const char* prompt); 
    void printArray(ostream & sout, Comparable **a, int size);

我得到了上面我arraySort.h

我用用：int aSize = _msize(a)/sizeof(Comparable) - 1;作爲我的長度是可變的。 ..我必須計算，而不是通過它，這是一種討厭。

我主要是在解除引用**的頭痛，並在quicksort中調用它的lessThan或equals方法。一旦我明白如何做一個快速排序，它會'點擊'，我將能夠輕鬆地進行冒泡排序。

編輯：我目前有以下作爲我的冒泡排序，它根本沒有排序數組。

void Swap(Comparable** from, Comparable** to) 
    { 
    Comparable** tmp; 

    tmp = from; 
    **from = **to; 
    to = tmp; 

    } 

    void bubbleSort(Comparable** a, int size) 
    { 

    int i, j; 

     for (i=0; i<size-1; i++) 
     { 
     for (j= size - 1; j > i; j--) 
      if(a[j]->lessThan(*a[j-1])) 
      Swap(&a[j], &a[j-1]); 

     } 
    }

來源

2009-10-15 Joel Garboden

如果你的排序函數中沒有長度參數，那麼唯一可能的方法是'n'和'compArray'是全局的 - 它們是否允許爲全局的？（並且，通常你想要使用長度參數而不是使用全局變量來做愚蠢的事情，這聽起來像是可能是賦值中的錯誤......） – bdonlan

你允許使用std :: vector嗎？ – GManNickG

GMan，我的猜測是他正在做一些介紹C++的東西，他們讓他動態分配二維數組。所以不，載體可能不允許哈哈。嗯，我記得那些日子... – Polaris878

你必須有交替的日期和時間，所以你不需要創建DateTime對象，是嗎？

記住你正在排序一個inplace數組。 From和to就像STL容器的begin（）和end（）部分。

void QuickSort(Comparable** from, Comparable** to) 
{ 
    int n = to - from; 
    if (n < 8) BubbleSort(from, to); 
    else { 
     // the trick in here is remembering you have to sort in pairs 
    } 
} 

Comparable** array = new Comparable*[n]; 
for (int i = 0; i < n; i += 2) { 
    array[i] = new Date(); 
    array[i+1] = new Time(); 
} 

// sort it 
QuickSort(array, array+n);

來源

2009-10-16 01:02:06 jmucchiello

Comparable**從和Comparable**到是我允許使用的唯一參數。

這有點傻，因爲有一個尺寸參數會是一個更好的API。無論如何，一個解決方法（我不知道它是否允許）將做C做字符串的操作：比如將數組放大一個（1）元素大於分配它時需要的大小，並將其最後一個元素設置爲零（空）以標記數組的末尾（以便被調用者可以查找空指針以發現數組結束位置）。

來源

2009-10-16 00:35:21 ChrisW

我不同意，整個STL使用開始和結束指針，它做得很好。 – GManNickG

'qsort'函數有一個'size_t num'。在任何情況下，單個數組類型參數都不容易傳達'大小'或'數組末尾的位置'信息，這通常是在第二個參數中傳遞的。 – ChrisW

您應該爲您的類重載運算符「<」，以便您可以比較其中的兩個以便對它們進行排序。之後，這是一個實施bubblesort和quicksort的問題，這非常簡單（您會在google中找到大量的解釋和示例代碼）。也許我不明白究竟什麼是您的問題，因此，如果這沒有幫助，請更明確:)

來源

2009-10-16 00:48:36 AntonioMO

記住以下行：

Comparable ** compArray = new Comparable *[n];

...正在分配一個指針數組;它沒有分配任何實際的對象。因此，在分配上述數組之後要做的下一件事是將compArray中的每個指針設置爲指向一個有效的對象。（無論您是通過爲每一個設置新的值來設置它們，還是將指針設置爲指向您現有對象的指針，當然都取決於您）

假設你已經這麼做了，接下來的事情可能是想做的事就是寫一個IsLessThan（）函數，基於它們指向什麼比較兩個指針：

bool IsLessThan(const Comparable * a, const Comparable * b) {return (*a) < (*b);}

注意，上面的是指針比較本身就是不一樣！

之後的下一步就是編寫一個BubbleSort函數對數組進行排序。這可能是這樣的：

void BubbleSort(Comparable ** ptrArray, int arrayLen) 
{ 
    [... bubble sort routine would go here ...] 
}

...它可能只是反覆遍歷數組中的指針，只要找到一對是錯順序相鄰的指針（即IsLessThan（ptrArray [ i]，ptrArray [i + 1]）== false），交換指針。一旦它通過數組的整個過程而不必交換任何指針，你就知道你已經完成了，並且你可以允許函數返回。

一旦這正常工作（這將是低效的，當然，不過沒關係），最後一步是寫的快速排序程序：

void QuickSort(Comparable ** ptrArray, int arrayLen) 
{ 
    if (arrayLen < 8) BubbleSort(ptrArray, arrayLen); 
    else 
    { 
     [... quick sort routine would go here ...] 
    } 
}

我不記得了快速排序不夠好，以解決它在這裏，但希望上面的內容至少能讓你完成作業的大部分任務。

來源

2009-10-16 00:50:18

快速排序和取消引用是正在殺死我，但你的解釋是有道理的。 –

C++抽象基類ptrs到ptrs數組

回答

相關問題