1

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

Задача состоит в том, чтобы в линейный список добавлять лишь те узлы, у которых уникально поле, то есть чтобы в списке не было повторяющихся элементов. Вот код:

    #include <stdio.h>
    #include <string.h>
    #include <stdlib.h>

    typedef struct Node {
        int val;
        struct Node *next;
    }Node_t;

    void push (Node_t **head, int newVal) // получаем на вход указатель на место в памяти, где располагается head (4)
    {
        Node_t *newNode;
        int i = 0;
        newNode = (Node_t*)malloc(sizeof(Node_t));

        newNode->val = newVal;
        newNode->next = *head;
        *head = newNode;
    }
    void find (Node_t *head, int newVal)
    {
        Node_t *cur = head; // создаём указатель на Node_t и присваиваем ему указатель head (2)
        int res = 0;
        while (cur != NULL) {
            if (cur->val == newVal)
                res = 1; // такой элемент уже есть в списке
            cur = cur->next;
        }
        cur = head;
        if (res == 0) 
            // элемент уникален
            push(&head, newVal); // передаём в функцию вставки адрес (3)        
    }
   void GoThroughList (Node_t *head)
   {
       Node_t *cur = head;
       while (cur != NULL) {
          printf("%d\n", cur->val);
          cur = cur->next;
       } 
    }
    int main()
    {
        Node_t *head; // создаём указатель на Node_t
        int values[] = {1, 2, 2}, i = 0;

        head = (Node_t*)malloc(sizeof(Node_t)); // выделяем память
        head->val = 0;
        head->next = NULL;

        for (i = 0; i < 3; i++)
            find(head, values[i]); // передаём в функцию указатель (1) head
        GoThroughList(head);
        return  0;
    }

Собственно, вопросы в коде я выделил цифрами в скобках.

(1) - не могу понять: если *head - это указатель на структуру, то что тогда такое head без * ?

(2) - непосредственно вытекает из (1).

(3) - адрес чего мы передаём в функцию добавления в начало списка?

(4) - тут я совсем запутался, так как интуитивно понимаю, что нужно передать указатель на место в памяти, где хранится "голова" списка, чтобы она не затёрлась, но так ли это?

Прочёл Кернигана и Ричи вдоль и поперёк уже на эту тему + разные статьи по динамическим структурам данным. Скорее всего, это просто затуп, но очень хочется, чтобы была полная ясность в каждой строчке кода, чтобы потом было легче работать с подобными структурами.

Собственно, поняв эти пункты, я, скорее всего, пойму и почему GoThroughList в конце выводит 0, а не 2 1 0.

Помогите, пожалуйста, разобраться.

1 ответ 1

2

Похоже, что самое главное Ваше непонимание, это разделение объявлений переменных и их непосредственного использования.

Начнем с этой строки

Node_t *head;

Эту строку иногда пишут так

Node_t* head;

И в этом ключ. В обеих случаях объявляется указатель(потому что звездочка) на Node_t с именем head. Разница только в прочтении.

Но звездочка может означать и разыменования указателя (когда в выражении пишется вот так *head) и в этом случае можно считать, что на место этой конструкции просто подставляется уже не указатель, а сам объект (структура, переменная).

А ещё звездочка - это просто умножение:)

теперь пункт 1 - head - это просто указатель. Его и передают.

*head в объявлении - это указатель. А в выражении - разыменования указателя.

Пункт 2 - cur указатель, и head - указатель. Их легко можно присвоить друг дружке. Никаких проблем.

Пункт 3. Тут чуто сложнее. В функции push у первого аргумента две звездочки - указатель на указатель, а в пункте 3 head просто указатель. И что бы обычный указатель превратить в указатель на указатель, нужно добавить &. То есть, амперсанд добавляет уровень косвености, а звездочка - убирает.

Тут возникает вопрос, а зачем нужен указатель на указатель? Все просто - если нужно переменную модифицировать (и иметь доступ к модифицированному значению после вызова функции) - передаем указатель на нее (и не важно, что при этом сама переменная указатель). Если переменную не нужно модифицировать - передаем по значению (хотя никто не мешает передавать по указателю).

Собственно в пункте 4 это и написано - передаем указатель на указатель. Да, адрес переменной это и есть указатель на эту переменную.

P.S.

  1. как всё-таки заставить в main с помощью функции GoThroughList вывести нужный список, а не просто 0?

А собственно функция рабочая, она все правильно делает. Просто head не содержит то, чего Вы ждете.

  1. с помощью & мы получаем адрес объекта, с помощью *, применив к &, получим сам объект.

только применив к указателю, а не к &.

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

find(&head, values[i]); // передаём в функцию указатель (1) head

И конечно, нужно саму функцию переписать.

void find(Node_t **head, int newVal) { // тут указатель на указатель
  Node_t *cur =
      *head; // теперь нужно head разыменовывать
  int res = 0;
  while (cur != NULL) {
    if (cur->val == newVal)
      res = 1; // такой элемент уже есть в списке
    cur = cur->next;
  }
  cur = *head; // аналогично
  if (res == 0)
    // элемент уникален
    push(head, newVal); // а тут head и так адрес.
}
3
  • Спасибо большое за столь обстоятельные ответы, но остались некоторые уточняющие вопросы: 1. как всё-таки заставить в main с помощью функции GoThroughList вывести нужный список, а не просто 0? 2. с помощью & мы получаем адрес объекта, с помощью *, применив к &, получим сам объект. Так?
    – Setplus
    21 ноя 2017 в 18:37
  • Отлично, всё заработало, спасибо! Но всё равно остался концептуальный вопрос: в КиР написано, что & - это указатель (p = &q - p указывает на q). * - ссылка по указателю.Тогда int *id; id = &x; - id хранит объект, на который он указывает. Не понял тогда Вашего второго замечания...
    – Setplus
    21 ноя 2017 в 19:03
  • Скорее всего это опечатка при переводе. Или приведите точную цитату. Если в приведённую "цытату" добавить несколько слов, то ее можно сделать более "правдоподобной".
    – KoVadim
    21 ноя 2017 в 19:17

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими условиями использования и подтверждаете, что прочитали и поняли наши политику конфиденциальности и нормы поведения.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.