1

在设计将缩小的动态数组时，有什么方法可以跟踪使用次数最多的索引，以及当该索引的持有对象被删除时，找到新的最高使用索引。

现在我可以想出一个简单int last_used的方法，然后将维护这个变量的成本收取到func_delete必须检查它是否删除最高的值，如果是，检查每个较小的值以寻找非空值。（数组将始终为空初始化）

if(last_index == deleted_index){

    while(last_index >0 && array[--last_index] != NULL)

    // if the array is now only half full, I realloc 
}

还有其他聪明的方法吗？

4

1 回答 1

1

对我来说看起来不错，但从逻辑上讲，如果函数总是删除最高的项目，那么在较小的索引处func_delete不应该有任何值。NULL所以这应该这样做：

if(last_index == deleted_index && array[last_index] != NULL) {
    //delete last item
    free(array[last_index]);
    //set to NULL and decrement
    array[last_index--] = NULL;
}

编辑：

根据您的评论，我了解您要做什么，我认为您可以只跟踪插入函数中使用的最高索引：

void array_insert(array , element e, int index) 
{
    if (index > arr->highest_index) {
       arr->highest_index = index;
    }
    //insert element
}

当你删除时，你检查索引是否是最高的。就像您正在做的那样，不要认为有更好的方法可以做到这一点，而不会使事情进一步复杂化，例如，您可以保留另一个排序的索引列表，这样当您删除最高索引时，您会找到下一个恒定的时间，但就像我说的，它使事情复杂化。但是，我认为另一种数据结构可能更有用，例如链表，在随机删除节点时效率更高，但在随机插入节点时效率更高。

于 2012-11-09T07:15:28.293 回答