Круговой двусвязный список с узлом заголовка - PullRequest
Новая
       58

Круговой двусвязный список с узлом заголовка

1 голос
/ 21 апреля 2020

Я должен реализовать Циклический список с двойной связью с узлом заголовка в C ++.

Мой профессор дал мне этот алгоритм, но я не могу понять, как его использовать.

enter image description here

Где и как я должен использовать предшествовать, следовать и выходить?

Внутри precede есть буква «P», которую я не понимаю, откуда она взялась, То же самое касается r в методе follow и p и r в методе out, но я подумал, что это может быть просто new E2*, поэтому я создал это 

class E2 {

public:
    E2* prev;
    E2* next;
    int key;

    E2() {
        prev = this;
        next = this;


    };


};

void precede(E2* q, E2* r) {

    //insert (*q) before (*r)

    E2* p = new E2();
    p = r->prev;
    q->prev = p;
    q->next = r;
    p->next = r->prev = q;



}

void follow(E2* p, E2* q) {

    E2* r = new E2();

    r = p->next;
    q->prev = p;
    q->next = r;
    p->next = r->prev = q;


}

void out(E2* q) {

    E2* r = new E2();
    E2* p = new E2();

    p = q->prev;
    r = q->next;
    p->next = r;
    r->prev = p;
    q->prev = q->next = this;
}

В методе out «это» дает мне ошибку, которая говорит: 'this' may only be used inside a nonstatic member function

1 Ответ

1 голос
/ 21 апреля 2020

В предыдущем методе:
p - временная переменная. Он используется для именования любого узла перед R. Представьте себе двусвязный список, содержащий 2 узла, A и R. Предыдущий метод вставит узел Q перед R. Следующие шаги:

  1. Отметить узел, предшествующий R как р. Таким образом, A помечен как р. Теперь мы вставим Q между p и R.
  2. Сделайте p в качестве предыдущего Q и R в качестве следующего узла Q. Следующим из p по-прежнему является R. Аналогично, предыдущим из R по-прежнему является p. Мы изменим это на следующем шаге.
  3. Пометить Q как следующий из p и предыдущий из R.

Вы можете использовать тот же лог c, чтобы понять следующую функцию.

В удалении method, p и r - предыдущий и следующий узлы q. Здесь нам нужно создать двойную связь между ними (т.е. пометить r как следующий из p и p как предыдущий из r). Это удалит узел q.

Надеюсь, это поможет.

...