Сортировка слиянием для критики связанных списков в C

От: Из: Общие

Я ранее реализовал сортировку слиянием для массивов, поэтому после исправления моего кода для сортировки слиянием на основе массивов я теперь реализовал сортировку слиянием для базовой структуры данных односвязного списка, которая содержит только указатель на данные и указатель на следующий «Узел». Я попытался воспользоваться советом, данным в предыдущем посте (/ q / 260010), чтобы помочь мне на этот раз. Есть три вещи, которые я не изменил ни в моем текущем, ни в предыдущем коде; позвольте мне объяснить мои рассуждения:

  1. Замедление Объявление и инициализация переменных делаются отдельно, так как я использую C90, по привычке.
  2. Я привык использовать <stdint.h> заголовок для написания всего моего кода с использованием типов фиксированной ширины, поэтому я обычно использую его для таких функций, как merge_sort чтобы он оставался неизменным на разных платформах. В то время как код пользователя написан с использованием «int», «short», «char», чтобы имитировать некое подобие пользовательского кода.
  3. Я научился использовать пробел для программирования вместо табуляции, и нам сказали сделать 3 пробела, сколько места вы рекомендуете 2, 3, 4 или X?

Любые советы о том, как улучшить мой код, помогут; Надеюсь, эта реализация намного лучше, поскольку я читал онлайн и был проинформирован, что сортировка слиянием обычно предпочтительнее для связанного списка и больших наборов данных.

TL; DR — посоветуйте, пожалуйста, как улучшить мою реализацию сортировки слиянием для версии связанного списка. А сколько пробелов вы используете для отступов?

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

struct Node{
   void *data;
   struct Node* next;
};

/*triple ref pointer are really cool as you don't need two pointers*/
int32_t split_list(struct Node *current, struct Node **front, struct Node **middle)
{
   uint32_t length, length_of_middle;
   struct Node *current_temp = current;
   struct Node **triple_ref = &current;

   if(current == NULL)
   {
      *front = *middle = NULL;
      return -1;
   }

   *front = current;
   *middle = current;
   length = length_of_middle = 0;

   while(current_temp != NULL)
   {
      current_temp = current_temp->next;
      length++;
   }

   while(length_of_middle < length / 2)
   {
      triple_ref = &((*triple_ref)->next);
      length_of_middle++;
   }

   *middle = *triple_ref;
   *triple_ref = NULL;

   return 0;
}

int32_t merge_sort(struct Node **head, int compare(const void *, const void *))
{
   struct Node *front, *middle;
   struct Node temp;
   struct Node *current = &temp;

   if(head == NULL)
   {
      return -1;
   }
   else if((*head)->next == NULL)
   {
      return 0;
   }

   split_list(*head, &front, &middle);

   merge_sort(&front, compare);
   merge_sort(&middle, compare);

   while(front != NULL && middle != NULL)
   {
      if(compare(front, middle) <= 0)
      {
         current->next = front;
         front = front->next;
         current = current->next;
      }
      else
      {
         current->next = middle;
         middle = middle->next;
         current = current->next;
      }
   }

   if(front != NULL)
   {
      while(front != NULL)
      {
         current->next = front;
         front = front->next;
         current = current->next;
      }
   }
   else
   {
      while(middle != NULL)
      {
         current->next = middle;
         middle = middle->next;
         current = current->next;
      }
   }

   *head = temp.next;
   return 0;
}


/*user code*/

int compare(const void *ptr1, const void *ptr2)
{
   const struct Node *node1, *node2;
   node1 = ptr1;
   node2 = ptr2;

   return *(int *)(node1->data) - *(int *)(node2->data);
}

void print_list(const struct Node *node)
{
   printf("n");
   while(node != NULL)
   {
      printf("%d ", *(int *)(node->data));
      node = node->next;
   }
   printf("n");
}

int32_t push_list(struct Node **head, void *val, const size_t size_of_element)
{
   struct Node *node;

   if(head == NULL)
   {
      return -1;
   }

   node = malloc(sizeof(*node));
   if(node == NULL)
   {
      return -1;
   }

   /*copy data*/
   node->data = malloc(size_of_element);
   if(node->data == NULL)
   {
      free(node);
      return -1;
   }
   memcpy(node->data, val, size_of_element);
   node->next = NULL;

   /*insertion*/
   if(*head != NULL)
   {
      struct Node *current;
      current = *head;
      while(current->next != NULL)
      {
         current = current->next;
      }
      current->next = node;
      return 0;
   }

   *head = node;
   return 0;
}

void free_list(struct Node *head)
{
   struct Node *temp;
   while(head != NULL)
   {
      temp = head;
      head = head->next;
      free(temp->data);
      free(temp);
   }
}

int main(void)
{
   struct Node *head;
   struct Node *front, *middle;
   int i;

   i = 10;
   /* i = 666;*/

   /*add values*/
   head = front = middle = NULL;
   for(; i > -1; i--)
   {
      push_list(&head, &i, sizeof(i));
   }
   i = 10;
   push_list(&head, &i, sizeof(i));
   i = -1;
   push_list(&head, &i, sizeof(i));

   /*print sort print*/
   print_list(head);
   merge_sort(&head, &compare);
   print_list(head);

   free_list(head);
   return 0;
}

2 ответа
2

Я научился использовать пробел для программирования вместо табуляции, и нам сказали сделать 3 пробела, сколько места вы рекомендуете 2, 3, 4 или X?
А сколько места вы используете при программировании?

Это проблема стиля, и лучше всего следовать стандарту кодирования вашей группы, который, по-видимому, равен 3. Я использую 2.

Хорошая среда кодирования позволяет вам быстро изменить отступ всего файла с помощью параметра настройки и вызова этого автоматического форматирования.

Если вы вручную редактируете правильный отступ, вы неэффективны. Используйте автоформатер.

Замедление ….

Эй, замедлять есть 😉. Вы имели в виду Декларация?

Пространство имен

Скорее, чем

struct Node{
int32_t split_list()
int32_t merge_sort()
void print_list()
int32_t push_list()
void free_list()

Рассмотрите единообразное именование

struct DList {
int32_t DList_split()
int32_t DList_merge_sort()
void DList_print()
int32_t DList_push()
void DList_free()

Сформировать DList.h заголовочный файл и отделите свой DList функции в DList.c файл.

Слабое сравнение

*(int *)(node1->data) - *(int *)(node2->data) рискует UB и неверным результатом, когда вычитание приводит к переполнению.

Вместо:

int i1 = *(int *)(node1->data);
int i2 = *(int *)(node2->data);
return (i1 > i2) - (i1 < i2);

int против. int32_t против ….

Я не вижу смысла в использовании int32_t здесь. Рекомендуем переделать код на size_t для типа, который относится к индексированию массивов и int/bool для простого флага успеха.

Незначительный: () не требуется

Вопрос стиля:

// node = malloc(sizeof(*node));
node = malloc(sizeof *node);

  • Извините, я исправил опечатку в вопросе, испортил ваш каламбур …

    — Тоби Спейт

  • Понятно. Мне нужно изменить имя моей функции для связанного списка, чтобы он был более согласованным! Кстати Хороший каламбур, мне нужно притормозить.

    — Дней

  • Никаких голых петель. Каждый цикл представляет собой важный алгоритм и как таковой заслуживает названия. Например, петли в split_list действительно

      uint32_t list_length(struct Node *);

    а также

      struct Node * advance(struct Node *, uint32_t);

  • split_list немного сложнее, чем необходимо. Дело в том, что front становится current известно заранее. Неужели нам нужно его сдавать?

    Точно не вижу причин для triple_ref быть ** (Кстати, название действительно сбивает с толку — почему тройной?).

    Все, что сказал, считайте

      struct Node * split_list(struct Node * current)
  {
      if (current == NULL) {
          return MULL;
      }
      uint32_t half_length = list_length(current) / 2;
      struct Node * pre_middle = advance(current, half_length);
      struct Node * middle = pre_middle->next;
      pre_middle->next = 0;
      return middle;
  }

  • Я не вижу причин для merge_sort чтобы вернуть целое число. В любом случае это значение никогда не проверяется. Гораздо естественнее вернуться head:

      struct Node * merge_sort(struct Node * head, int compare(const void *, const void *));

  • Необъединенные остатки списков перебирать не нужно. Они уже хороши, а нас не волнует current больше.

      if (front != NULL) {
      current->next = front;
  } else {
      current->next = middle;
  }

  • current = current->next выполняется в обоих if а также else ветви слияния. Поднимите это.

  • Причина, по которой я использую «triple_ref» в качестве имени, связана с этим видео. youtube.com/… пользователя Computerphile. И это плохо, так как это больше концепция по сравнению с фактическим указателем тройной ссылки.

    — Дней


Похожие записи:

  1. Простая консольная шахматная игра C ++
  2. Критика слияния в C
  3. односвязный список кода Python
  4. Программа для записи санации объекта
  5. Критика реализации C ArrayList

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *