Что такое квадратический связанный список?

I can't be sure, but it sounds a bit like a skip list.

Even if that's not what it is, you might find skip lists handy. (To the best of my knowledge they are unidirectional, however.)

I don't know if this is exactly a "quad-linked list", but it sounds like something like this:

struct Person {
    // Normal doubly-linked list.
    Customer *nextCustomer;
    Customer *prevCustomer;

    std::string firstName;

    Customer *nextByFirstName;
    Customer *prevByFirstName;

    std::string lastName;

    Customer *nextByLastName;
    Customer *prevByLastName;
};

That is: you maintain several orderings through your collection. You can easily navigate in firstName order, or in lastName order. It's expensive to keep the links up to date, but it makes navigation quite quick.

Of course, this could be something completely different.

Мое чтение таково, что список с четырьмя связями - это тот, который можно просмотреть (назад или вперед) в O (n) двумя различными способами, то есть отсортировать по FieldX или FieldY:

(а) создание первого и второго наборов указателей ссылок, при этом первый набор указателей ссылок указывает на элементы-преемники множества связанные записи, когда записи заказано относительно фиксированного идентификатора поле и второй набор ссылок указатели указывают на предшественника элементы набора связанных записей когда записи упорядочены с относительно поля с фиксированным идентификатором;

(b) генерируют третий и четвертый наборы указателей ссылок, при этом третий набор указателей ссылок указывает на элементы-преемники множества связанные записи, когда записи упорядочено относительно переменной Поле идентификатора и четвертый набор ссылок указатели указывают на предшественника элементы набора связанных записей когда записи упорядочены с respect to the variable ID field;

So if you had a quad linked list of employees you could store it sorted by name AND sorted by age, and enumerate either in O(n).

Одним из источников патента является этот . По-видимому, существует две претензии, вторая из которых более близка к актуальности:

Реализованный на компьютере способ организации и поиска набора связанных записей, в котором каждая запись включает в себя:

i) поле фиксированного идентификатора; и

ii) поле идентификатора переменной;

(f) при поиске конкретной записи со ссылкой на ее поле идентификатора переменной проводят двоичный поиск второго набора указателей поля для определения начального указателя и окончательного указателя, определяющего диапазон, в котором находится конкретная запись ;

(g) изучение путем линейного поиска полей идентификатора переменной в пределах диапазона, определенного на шаге (f), для определения местоположения конкретной записи.

Когда вы работаете с патентным гоблендом, я думаю, это означает примерно то же самое. как наличие двух списков пропусков (один для прямого поиска, один для обратного поиска) на каждом из двух ключей (следовательно, всего 4 списка и имя 'quad-list'). Я не думаю, что это очень хороший патент - он выглядит очевидным применением пропуска списков к набору данных, где у вас есть два ключа для поиска.

выполнение двоичного поиска второго набора указателей поля для определения начального указателя и окончательного указателя, определяющего диапазон, в котором находится конкретная запись;

(g) проверка путем линейного поиска полей идентификатора переменной в этом диапазоне определяется на шаге (f), чтобы найти конкретную запись.

Когда вы работаете с патентным справочником, я думаю, это означает примерно то же самое, что иметь два списка пропусков (один для поиска вперед, один для поиска назад) на каждом из двух ключи (следовательно, всего 4 списка и название 'quad-list'). Я не думаю, что это очень хороший патент - он выглядит очевидным применением пропуска списков к набору данных, где у вас есть два ключа для поиска.

выполнение двоичного поиска второго набора указателей поля для определения начального указателя и окончательного указателя, определяющего диапазон, в котором находится конкретная запись;

(g) проверка путем линейного поиска полей идентификатора переменной в этом диапазоне определяется на шаге (f), чтобы найти конкретную запись.

Когда вы работаете с патентным справочником, я думаю, это означает примерно то же самое, что иметь два списка пропусков (один для поиска вперед, один для поиска назад) на каждом из двух ключи (следовательно, всего 4 списка и название 'quad-list'). Я не думаю, что это очень хороший патент - он выглядит очевидным применением пропуска списков к набору данных, где у вас есть два ключа для поиска.

поля идентификатора переменной в пределах диапазона, определенного на шаге (f) для определения местоположения конкретной записи.

Когда вы работаете с патентным справочником, я думаю, это означает примерно то же самое, что наличие двух списков пропуска (один для прямого поиска, один для поиск в обратном направлении) по каждому из двух ключей (следовательно, всего 4 списка и имя 'quad-list'). Я не думаю, что это очень хороший патент - он выглядит очевидным применением пропуска списков к набору данных, где у вас есть два ключа для поиска.

поля идентификатора переменной в пределах диапазона, определенного на шаге (f) для определения местоположения конкретной записи.

Когда вы работаете с патентным справочником, я думаю, это означает примерно то же самое, что наличие двух списков пропуска (один для прямого поиска, один для поиск в обратном направлении) по каждому из двух ключей (следовательно, всего 4 списка и имя 'quad-list'). Я не думаю, что это очень хороший патент - он выглядит очевидным применением пропуска списков к набору данных, где у вас есть два ключа для поиска.

The description isn't particularly good, but as best I can gather, it sounds like a less-efficient skip list.