Добавление записи в начале связанного списка в C - PullRequest
Новая
       46

Добавление записи в начале связанного списка в C

0 голосов
/ 30 марта 2020

Welp Я, наконец, достиг указателей после очень долгого времени. Я понимаю, что мои программы приобретут элегантность и силу. К сожалению, моего понимания, похоже, не хватает. Я работаю над программированием Кочана в C 4-м издании, и это упражнение 10.3. Я должен добавить запись в начало связанного списка, однако то, что я думаю, должно работать, не работает. 

#include <stdbool.h>

struct entry
  {
      int      value;
      struct entry *next;
  };
                        //n0_1              list_pointer
void insertEntry(struct entry *what, struct entry *where)
{
    what->next = where->next;
    where->next = what;
}

int main (void)
{

struct entry n1, n2, n3, n4, n5,n0_1, n2_3, n3_4, n4_5;

struct entry *list_pointer = &n1;

  n1.value = 100;
  n2.value = 200;
  n3.value = 300;
  n4.value = 400;
  n5.value = 500;

  n1.next = &n2;
  n2.next = &n3;
  n3.next = &n4;
  n4.next = &n5;
  n5.next = (struct entry*)0;

  n0_1.value = 50;
  n2_3.value = 250;
  n3_4.value = 350;
  n4_5.value = 450;

  insertEntry(&n0_1, list_pointer);
  insertEntry(&n3_4, &n3);
  insertEntry(&n4_5, &n4);


  while (list_pointer != (struct entry *)0){
    printf("%i\n", list_pointer->value);
    list_pointer = list_pointer->next;

  }


  return 0;
}

Так что я разбиваю то, что происходит следующим образом - 

n0_1.next = List_pointer.next    //ok n0_1.next points to whatever the list pointer was.  
list_pointer.next = n0_1     //doesn't that make list pointer point to n0_1?

Любое руководство будет оценено, спасибо заранее. Естественно, я буду чувствовать себя идиотом, когда увижу, что я делаю неправильно.

Ответы [ 4 ]

1 голос
/ 30 марта 2020

С показанной функцией insertEntry вы ничего не можете вставить до исходного указателя списка. В таком случае указатель на заголовок списка должен измениться, т. Е. Само значение list_pointer должно измениться, а не значение list_pointer.next; Вы можете использовать два подхода:

(1) пусть заголовок списка всегда будет одинаковым (и игнорировать его value); первым фактическим элементом будет тот, на который указывает head.next.

(2) изменить запись вставки так, чтобы она могла изменить значение where (передав указатель на этот указатель).

Approach (1): 

struct entry n1, n2, n3, n4, n5,n0_1, n2_3, n3_4, n4_5;
n1.value = 100;
...
struct entry list_pointer;
list_pointer.next = &n1;
...
struct entry* iterator = list_pointer.next;
while (iterator != NULL){
    printf("%i\n", iterator->value);
    iterator = iterator->next;
}

Подход (2) 

void insertBefore(struct entry *what, struct entry **head)
{
    what->next = (*head);  // let what.next point to the former head
    *head = &what;  // let the head-pointer point to the new head
}

insertEntry(&n0_1, &list_pointer);
...
struct entry* iterator = list_pointer;
while (iterator != NULL){
    printf("%i\n", iterator->value);
    iterator = iterator->next;
}
1 голос
/ 30 марта 2020

Давайте сделаем шаг назад.

Таким образом, у нас есть n1 в качестве первого узла, а list_pointer указывает на этот первый узел.

При вставке узла X в начале списка вы хотите, чтобы X.next указывал на то, на что указывает list_pointer. Итак, 

X.next = list_pointer

И этот узел X теперь становится вашим начальным узлом. 

list_pointer = X
0 голосов
/ 01 апреля 2020

Оооочень давно я боролся с этой чертовой штукой. Вот что у меня есть, что выглядит довольно хорошо для меня. Где я заблудился, как это не противоречит ответам выше? List_ptr работает так, как я изначально полагал. 

#include <stdio.h>
#include <stdbool.h>


struct entry
  {
      int      value;
      struct entry *next;
  };

void insertEntry(struct entry *what, struct entry *where)
{
    what->next = where->next;
    where->next = what;
}

void printEntries(struct entry initial)
{
     while (initial.next != NULL){
        printf("%i   \n", initial.next->value);
        initial.next = initial.next->next;
}
printf("\n");
}

int main (void)
{
  struct entry nx2, n0, n1, n2, n3, nx;

  struct entry *list_ptr;

  list_ptr = &n0;

  n1.value = 100;
  n2.value = 200;
  n3.value = 300;

  nx.value = 77;
  nx2.value = 15;

  n0.next = &n1;
  n1.next = &n2;
  n2.next = &n3;
  n3.next = NULL;

    printEntries(*list_ptr);
    insertEntry(&nx, list_ptr);
    printEntries(*list_ptr);
    insertEntry(&nx2, &n2);
    printEntries(n0);



  return 0;
}
0 голосов
/ 30 марта 2020

Вы не можете использовать такой вызов, как этот 

insertEntry(&n3_4, &n3);

, чтобы вставить узел перед узлом n3, потому что в этом случае вам нужно изменить элемент данных next узла n2 указывает на узел n3. Но функция не имеет никакой информации об узле n2, поскольку у вас есть односвязный список.

Даже для вызова 

insertEntry(&n0_1, list_pointer);

, где указанный узел указателем list_pointer не имеет В предыдущем узле функция написана неправильно. По крайней мере, он должен быть определен как 

struct entry * insertEntry(struct entry *what, struct entry *where)
{
    what->next = where;
    where = what;

    return where;
}

и назван как 

list_pointer = insertEntry(&n0_1, list_pointer);

Вы можете написать функцию, которая вставляет новый узел после данного узла. Например 

struct entry * insertEntry(struct entry *what, struct entry *where)
{
    if ( where == NULL )
    {
        what->next = where;
        where = what;
    }
    else
    {
        what->next = where->next;
        where->next = what;
    }

    return where;
}
...