Как реализовать логику указателя prev в двусвязном списке - PullRequest
Новая
       2

Как реализовать логику указателя prev в двусвязном списке

1 голос
/ 18 ноября 2011

Мне нужна помощь с реализацией логической части prev указателя в двусвязном списке.

По сути, я нахожусь в процессе создания связанного списка, который в данный момент является односвязным. Я добавил необходимый структурный узел * prev; к моей структуре, так что я могу иметь как следующие указатели, так и предыдущие указатели в каждом узле в списке. Но теперь я врезался в стену и действительно не знаю, как реализовать указатель * prev в моем коде.

Я не ищу точных решений, просто толчок в правильном направлении. 

typedef struct L { 
    char val;
    struct L *next;
    struct L *prev;
} List;

List *insertList(char val, List *t1 );
List *createList(void);

int main(void) {
    List *z = createList();
    while ( z != NULL ) {
        printf("%c", z->val);
        z = z->next;
    }
    return 0;
}

List *createList(void) {
    List *h = NULL;
    char c;
    do { 
        c =(char)getchar();
        h = insertList(c, h);
    }while(c != '.');
    return h;
}

List *insertList( char val, List *t1) {
    List *t = calloc(1, sizeof( List ));
    t->val = val;
    t->next = t1;
    return t;
}

Ответы [ 3 ]

0 голосов
/ 18 ноября 2011

insertList должно быть: 

List *insertList( char val, List *t1) {
  List *t = calloc(1, sizeof( List ));
  t->val = val;
  t->next = t1;
  // Set the previous pointer
  if (t1 != NULL)
     t1->prev = t;  
  return t;
}

Однако есть проблема с этой реализацией. Предположим, вы звоните: 

List* t1 = insertList('a', NULL)
List* t2 = insertList('b', t1)
List* t3 = insertList('c', t2)

Теперь у вас есть список 

c->b->a->NULL

Если вы сейчас позвоните 

List *t4 = insertList('d', t1)

Тогда ваш «список» будет 

c->b-
     \
   d->a->NULL

Вы видите проблему здесь. Это не связанный список . Если вы просто вставляете элементы в начале списка, ваша реализация в порядке. В другом случае вам следует пересмотреть способ вставки предметов.

Также не забывайте, что вы должны где-то хранить узел head .

Вы должны просмотреть связанный список Статья Википедии и этот связанные списки в руководстве по C / C ++

0 голосов
/ 22 апреля 2017

Вы реализуете insert @, начинаете сохранять сложность O (1).

Для двусвязного списка вам нужно добавить еще один указатель 'prev' на узел и убедиться, что указатель на предыдущий узел в списке. Это должно быть сделано во время вставки узла. Следовательно, код вставки выглядит примерно так: 

List *insertList( char val, List *t1) {
    List *t = calloc(1, sizeof( List ));
    t->val = val;
    t->next = t1;

    //For all nodes except the first insert, point the previous node
    if (t1 != NULL) {
       t1->prev = t;
    }
    return t;
}

Полагаю, это должно вывести вас на следующий уровень.

0 голосов
/ 18 ноября 2011

После вызова insertList (внутри функции createList) устанавливаются прямые ссылки, все, что вам нужно, это обратные ссылки.

Для этого после вызова insertList вам нужночтобы проверить, если h->next равно NULL, а если нет, установите h->next->prev на h.Вы также можете сделать то же самое в самом insertList, проверив, является ли t1 значением NULL, а если нет, установив t1->prev в t.

...