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数组

回答

相关问题