Что такое Связанный список курсоров? [C ++] - PullRequest
4 голосов
/ 07 апреля 2010

Мой профессор предоставил мне файл с именем CursorList.cpp, который реализует «Связанный список курсоров».Проблема в том, что я понятия не имею, что это такое!

Может ли кто-нибудь дать мне суть этого?

Ответы [ 4 ]

1 голос
/ 07 апреля 2010

Я думаю, что это связанный список , который дополнительно содержит указатель на «текущий» элемент, например, для итерации по списку.

Если вы хотите убедиться, что именно ваш профессор имеет в виду, посмотрите на файл .cpp и выясните, что там реализовано.

1 голос
/ 23 декабря 2014

CursorList - это версия массива связанного списка. По сути, у вас есть массив узлов списка, но вместо каждого узла, содержащего указатель на следующий элемент в связанном списке, каждый элемент узла в массиве содержит индекс для следующего элемента узла. Так, например, если бы мы хотели сохранить 5, 3, 2, 11, 9 в связанном списке, у нас было бы 5 -> 3 -> 2 -> 11 -> 9 -> NULL. Вставка не является проблемой, так как мы просто меняем последний указатель, чтобы он указывал на вставленный узел, а для вставленного узла указываем NULL. Удаление то же самое, мы просто перенастраиваем указатели. Однако необходимость всегда динамически выделять (используя malloc или new) память для нового узла может быть проблематичной.

Если мы должны были сохранить в CursorList, мы сначала объявляем максимальный размер массива, а затем заполняем его. Поэтому мы говорим listNode cursorList[10], где мы объявляем объект listNode следующим образом:

class listNode {
    public:
        listNode() {
            data = -1;
            next = NULL;
        }
        listNode(int inputData, &listNode inputNext) {
            data = inputData;
            next = inputNext;
        }
    private:
        int data;
        listNode* next;
};

поэтому после заполнения массива объектами listNode у нас будет что-то похожее на это: CursorList after insertions

Теперь, если мы хотим удалить 5, все, что нам нужно сделать, это обновить индекс next. Итак, мы остались с этим: CursorList with 5 removed

Возникает вопрос, как мы узнаем, на что нужно установить индекс next 5? Что ж, вот тут и появляется Freelist (упомянутый в ответе @Justin Ethier). Freelist содержит индексы, которые все еще свободны в массиве. Таким образом, при создании CursorList, Freelist имеет 0-9. Поскольку объекты listNode назначаются элементам массива, Freelist удаляет эти индексы. Когда число удаляется (например, в примере с 5 выше), индекс добавляется обратно во Фрилист. Если мы хотим добавить число в CursorList, мы просто обновляем индексы next для соответствующих элементов.

1 голос
/ 07 апреля 2010

Согласно это , вот немного фона в связанном списке курсора:

  • некоторые языки не поддерживают указатели
  • вместо этого используйте массивы объектов
  • начать с Freelist
  • выделять место из списка Freelist при необходимости
  • удалить: изменить указатели, добавить в Freelist

Так что в основном это связанный список, который реализован без использования указателей. Может быть, эта реализация должна быть «проще» для понимания?

0 голосов
/ 17 сентября 2017

В реализации курсора мы сами строим пул хранения, сохраняя наши неиспользуемые узлы в связанном списке, хранящемся в массиве.

В C и C ++ пул хранения управляется набором библиотечных функцийпредоставлено языком.В начале выполнения из операционной системы получается достаточно большой пул хранения.Когда программа запрашивает новый узел, хранилище получается из пула с помощью функции языковой библиотеки.Если в пуле недостаточно места, библиотека запрашивает дополнительное пространство пула у операционной системы.Когда память освобождается программой, функция языковой библиотеки возвращает ее в пул хранения.Реализация курсора обычно получает фиксированный объем памяти из системы в виде массива и предоставляет функции, аналогичные new и delete, для прикладной программы, использующей

...