时间戳

首页 > 解决方案 > 使用数组上的链表排序索引列表

c++ - 使用数组上的链表排序索引列表

问题描述

我有一个项目使用数组上的单链表来实现排序索引列表。当我尝试执行添加功能时，我遇到了一些问题。这就是我的构造函数的样子：

SortedIndexedList::SortedIndexedList(Relation r) {
    this->cap = 10;
    this->elems = new TComp[this->cap];
    this->next = new TComp[this->cap];
    this->head = -1;
    for (int i = 0; i < this->cap - 1; i++)
        this->next[i] = i + 1;
    this->next[this->cap] = -1;
    this->firstEmpty = 0;
    this->size_elems = 0;
    this->rel = r;
}

这是我的添加功能：

void SortedIndexedList::add(TComp e) {
    if (this->size() == this->cap)
        this->resize();
    if (this->size() == 0)
    {
        int newPosition = this->firstEmpty;
        this->elems[newPosition] = e;
        this->firstEmpty = this->next[this->firstEmpty];
        this->next[newPosition] = this->head;
        this->head = newPosition;
    }
    else
    {
        int current = this->head;
        int currentPosition = 0;
        while (current != -1 && currentPosition < this->size() && rel(this->elems[current], e))
        {
            current = this->next[current];
            currentPosition++;
        }
        if (current != -1)
        {
            int nextPos = this->firstEmpty;
            this->firstEmpty = this->next[firstEmpty];
            this->elems[current] = e;
            this->next[nextPos] = this->next[current];
            this->next[current] = nextPos;
        }
    }
    this->size_elems++;
}

我想确保它有效，我尝试添加 1，然后是 2，然后是 3，并在每一行上打印元素，但不会添加 I 2 和 3（关系为 <=）。有人可以帮我吗？我无法弄清楚我做错了什么。

标签： c++listsortingdata-structures

解决方案

我认为您在初始化next数组时跳过了索引：

for (int i = 0; i < this->cap - 1; i++)
        this->next[i] = i + 1;
this->next[this->cap] = -1;

您将this->cap - 2在 for 循环 ( i < this->cap - 1) 中上升，因此this->cap - 1永远不会被赋予值。

推荐阅读