Блог

Я выполняю упражнение со связанным списком, в котором мне нужно удалить некоторые узлы в соответствии с условием. Условие — «удалить узлы, в которых хранятся данные, меньшие или равные ‘avg».

Я должен рассмотреть три случая: — удаление головного узла — удаление узла в середине — удаление последнего узла

Я использовал три указателя, но, похоже, это не работает. Что я делаю не так? Я случайно пропустил некоторые указатели? Заранее благодарю вас!

 void checkAvg(int avg, struct list* head_node){

   struct list* prev;
   struct list* curr;
   struct list* next;

   prev = head;
   curr = prev->link;
   next = curr->link;

   while (curr!=NULL) {
      if (prev->data <= avg) {
          head = curr;
      }

      if (curr->data <= avg) {
          prev->link = curr->link;
      }

      if (next->data <= avg) {
          curr->link = next->link;
      } 

      prev = prev->link;
      curr = curr->link;
      next = next->link;

   }

}
  

Редактировать:
Извините, как вы сказали мне, я не был конкретен. Программа должна это сделать:
1) Прочитать связанный список
2) Сгенерировать среднее значение прочитанных значений (сумма значений / количество значений)
3) удалить из списка узлы, данные которых <= равны среднему
Освободите память этих узлов.
Что касается части free (), у меня возникли некоторые трудности с этим, поэтому я подумал, что сначала мне нужно научиться правильно использовать указатели. Как вы, возможно, заметили, я не очень хорош в этом, я новичок.

Спасибо всем, кто ответил, я проверяю ответы прямо сейчас

Если в вашем связанном списке нет какого-либо контрольного головного узла (а я настоятельно рекомендую, чтобы этого не было, поскольку NULL это чертовски подходящее значение для указания «Я пуст»), обход удаления не является явно сложным. Места в вашем коде, где вы, кажется, сбиваетесь с пути, следующие:

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

Вы можете использовать значения указателя, или вы можете использовать сами фактические указатели (по адресу). Я предпочитаю последнее. В любом случае указатель на головной узел должен быть передан по-address, чтобы разрешить потенциальную модификацию переменной вызывающего объекта (как и все остальное в C), или функция может вернуть потенциально новый адрес головного узла. Я предпочитаю первый из этих методов, поскольку он оставляет вам возможность использовать возвращаемое значение функции для передачи состояний ошибки вашему вызывающему. Вы не делаете этого прямо сейчас, но вы должны (подсказка).

 void checkAvg(int avg, struct list** pp)
{
    while (*pp)
    {
        if ((*pp)->data <= avg)
        {
            struct list *victim = *pp;
            *pp = victim->link;
            free(victim);
        }
        else
        {   // advance to address of next "link" pointer
            pp = amp;(*pp)->link;
        }
    }
}
  

Стоит отметить, что это может быть значительно проще, если список поддерживается в отсортированном порядке возрастания. Если это так, вся checkAvg функция становится существенно проще. Вы можете выйти из цикла, как только обнаружите значение, которое больше не соответствует вашему условию:

 void checkAvg(int avg, struct list** pp)
{
    while (*pp amp;amp; (*pp)->data <= avg)
    {
        struct list *victim = *pp;
        *pp = victim->link;
        free(victim)
    }
}
  

В любом случае функция вызывается путем передачи верхнего указателя на стороне вызывающего объекта по адресу:

 struct list *head = NULL;

//... populate list....

checkAvg(value, amp;head);
  

Как это работает

Связанный список — это просто то, что выглядит следующим образом:

           --------      --------      --------
head ---> | link | ---> | link | ---> | link | ---> NULL
          | val1 |      | val2 |      | val3 |
          --------      --------      --------
  

Используя опубликованные методы, при обходе списка используется указатель на указатель, который выполняет что-то вроде этого:

 pp --:
     :        --------      --------      --------
    head ---> | link | ---> | link | ---> | link | ---> NULL
              | val1 |      | val2 |      | val3 |
              --------      --------      --------
  

pp указывает на указатель; не узел. Изначально pp содержит адрес head указателя (был передан в by-address в качестве параметра).

Итак, что произойдет, если первый узел соответствует вашим критериям? В конечном счете, это результат

 pp --:
     :        --------      --------
    head ---> | link | ---> | link | ---> NULL
              | val2 |      | val3 |
              --------      --------

             --------
 victim ---> | link |
             | val1 |
             --------
  

и узел жертвы в конечном итоге отбрасывается (ссылка жертвы фактически все еще ссылается на второй узел, но в этом контексте бессмысленна после того, как произойдет отсоединение.

Итак, что, если второй узел был тем, который требовал удаления (т. Е. Мы пропустили первый узел). Это становится немного сложнее:

          pp -----:
                 :
              ---:----      --------
    head ---> | link | ---> | link | ---> NULL
              | val1 |      | val3 |
              --------      --------
             --------
 victim ---> | link |
             | val2 |
             --------
  

Что это пытается показать (по общему признанию плохо), так это то, что pp указатель на указатель всегда содержит адрес указателя, который мы можем изменять. Если нам не нужно изменять этот указатель, мы меняем адрес, хранящийся в, pp чтобы указать на следующий link указатель в списке (полученный через pp = amp;(*pp)->link

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

Но несмотря ни на что, pp всегда сохраняется адрес указателя, который указывает на узел, с которым мы работаем.. Изначально этот адрес является адресом head указателя вызывающего объекта.

ОК. Я могу только надеяться, что это прояснит ситуацию. Некоторая отладка с printf("pp=%p, *pp=%pn", pp, *pp) в цикле делает то, что на самом деле происходит, наиболее познавательным. Прохождение алгоритмов вручную в отладчике было бы очень информативным.

Это намного проще, чем вы думаете.

Вы просматриваете и изменяете связанный список, поэтому настройте текущий и предыдущий.

 void checkAvg(int avg, struct list** head_node){ //when calling, use checkAvg(avg, amp;head_node);
    struct list* prev = NULL; 
    struct list* curr = *head_node; 
  

Начиная с заголовка…

 while(curr != NULL){ 
    if(curr->data <= avg){
         if(prev == NULL){
             *head_node = curr->next; //updates the head node
         } else {
             prev->next = curr->next; //removes the unwanted node
         }
    }
    curr = curr->next;
}
  

Вам действительно не нужен специальный конечный регистр, потому что цикл while завершается, когда curr равен нулю; для последнего элемента в списке curr-> next имеет значение NULL, поэтому, когда он будет установлен, цикл завершится. Вам также не нужно проверять, пуст ли список, потому что цикл завершится, если он curr == NULL и вы сначала назначите заголовок curr .

Я хочу немного рекурсивной магии сегодня вечером

 Node* deleteBad(Node *head, int(*pred)(int)) {
    if (head == NULL) {
        return NULL;
    }
    if (pred(head->value)) {
        head->next = deleteBad(head->next, pred);
        return head;
    }
    else {
        Node *next = head->next;
        free(head);
        return deleteBad(next, pred);
    }
}
  

И аккумуляторы

 void deleteBad2(Node *head, int(*pred)(int), Node *out) {
    if (head) {
        if (pred(head->value)) {
            out->next = head;
            deleteBad2(head->next, pred, out->next);
        } else {
            out->next = head->next;
            deleteBad2(head->next, pred, out);
        }
    } 
}
  

И для тех, кому не нравится версия, оптимизированная для рекурсии

 void deleteBad3(Node *head, int(*pred)(int), Node *out) {
begin:
    if (head) {
        if (pred(head->value)) {
            out->next = head;
            out = out->next;
            head = head->next;
            goto begin;
        }
        else {
            out->next = head->next;
            head = head->next;
            goto begin;
        }
    }
}
  

и если кому-то не нравятся gotos

 void deleteBad3nogoto(Node *head, int(*pred)(int), Node *out) {
    while (1) {
        if (head) {
            if (pred(head->value)) {
                out->next = head;
                out = out->next;
                head = head->next;

            }
            else {
                out->next = head->next;
                head = head->next;

            }
        }
        else {
            break;
        }
    }
}
  

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

 void checkAvg(int avg, struct list* head_node){

   struct list* prev;
   struct list* curr;


   while (head!=NULL) {
      if (head->data <= avg) {
          head = head->link;
      } else {
         break;
      }
   }

   prev = head;
   curr = prev->link;

   while (curr!=NULL) {

      if (curr->data <= avg) {
          prev->link = curr->link;

      }
      prev = prev->link;
      curr = prev->link;
   }
}
  

Вместо того, чтобы проверять данные prev, curr и next, просто проверьте наличие одних данных в цикле.
Вам также необходимо вернуть новый заголовок в случае его изменения.
Я бы предложил что-то подобное (проверено):

 #include <stdio.h>
#include <malloc.h>

typedef struct list_ {
  struct list_ *link;
  int data;
} list;

list* RemoveElementsBelow(int avg, list* head_node) {
  while (head_node != NULL amp;amp; head_node->data <= avg) {
    // Remove the first.
    list* new_head = head_node->link;
    free(head_node);
    head_node = new_head;
  }
  if (head_node == NULL) {
    return NULL;
  }

  list* prev;
  list* curr;

  prev = head_node;
  curr = prev->link;

  while (curr != NULL) {
    if (curr->data <= avg) {
      prev->link = curr->link;  // Will be NULL at the end of the list.
      free(curr);
      curr = prev->link;
    } else {
      prev = curr;
      curr = curr->link;
    }
  }
  return head_node;
}

list* AddToHead(int value, list* head_node) {
  list* new_node = malloc(sizeof(list));
  new_node->link = head_node;
  new_node->data = value;
  return new_node;
}

list* PrintAndDeleteList(list* head_node) {
  while (head_node != NULL) {
    list* new_head = head_node->link;
    printf("%d ", head_node->data);
    free(head_node);
    head_node = new_head;
  }
  printf("n");
}
int main(int argc, char **argv) {
  list* my_list = NULL;
  int i;
  int sum = 0;
  for (i = 1; i < argc;   i) {
    int value = atoi(argv[i]);
    sum  = value;
    my_list = AddToHead(value, my_list);
  }
  if (argc == 1) {
    return 1;
  }
  int avg = sum / (argc - 1);
  printf("Average value: %dn", avg);

  my_list = RemoveElementsBelow(avg, my_list);

  PrintAndDeleteList(my_list);
  return 0;
}
  

Скомпилированный:

 gcc -o test test.c
  

Проверено:
./тест 10 20 30 40 50
Среднее значение: 30
50 40
./тест 50 40 30 20 10
Среднее значение: 30
40 50