Улучшение моего Mergeort для связанных списков. Как?

Question

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

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

---

Мой код уже работает. Для целей тестирования я всегда создал обратные отсортированные списки. Это все еще не хватает чего-то для таких случаев, как список ноль.

Поэтому, прежде чем публиковать код, который использует структуру:

struct list{
  int nbr;
  struct list *next_el;
};
typedef struct list LIST;
typedef LIST *z_LIST;

Я получил две функции, Мергеорта и слива. Mergeort возвращает новую главу отсортированных (под) списков и Merge возвращает головку объединенных последовательностей.

Прямо сейчас я даю Mergeort текущую главу несортированного списка и количества элементов. Затем он разрушает список рекурсивно (очевидно :)). Я не уверен, сколько сказать в следующем коде. Если что-то неясно, я отвечу и объясню как можно быстрее, но

z_LIST mergeSort ( z_LIST head, int length ) {

  int steps;
  int m = 0;
  z_LIST head1 = NULL, head2 = NULL, new_head = NULL;

if( length > 1) {

  m = (length+1)/2;


  head2 = head; 
  for(steps = 0; steps<m; steps++) {
    head2 = head2->next_el;
  }

  head1 = mergeSort(head, m);
  head2 = mergeSort(head2, length-m);

  new_head = merge(head1, head2, m, length-m);

  return new_head;

  } else {
    return head;
  }
}

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

z_LIST merge (z_LIST head1, z_LIST head2, int l1, int l2)  {

  int i,j;
  z_LIST part1 = head1, part2 = head2;
  z_LIST temp_head = NULL, head = NULL;

/*First I let it check what the head of the new list is going to 
be and thus initiating the merging process with either i=1/j=0
or i=0/j=1.*/

  if(part1->nbr < part2->nbr){
    head = part1;
    if(part1->next_el != NULL)  {
      part1 = part1->next_el;
    }
    i=1;
    j=0;
  } else {
    head = part2;
    if(part2->next_el != NULL)  { //The last element of the original list points
      part2 = part2->next_el;     //to NULL. If I would then make part2 = NULL,
    }                             //then there wouldn't be part2->nbr ->lots
    i=0;
    j=1;
  }

  temp_head = head;

  while( (i<l1) || (j<l2) ) {
    if( ((part1->nbr < part2->nbr) && i<l1)||( j>=l2 ))  {
      temp_head->next_el = part1;
      part1 = part1->next_el;
      temp_head = temp_head->next_el;
      if (j>=l2)  { //If j>=l2 then I let merge add one more item of list1
       break;       //since list 1 is already sorted and linked correctly.
      }             //Same below. Should shave off some operations/time?
      i++;
    } else {
      temp_head->next_el = part2;
      part2 = part2->next_el;
      temp_head = temp_head->next_el;
      if (i>=l1)  {
        break;
      }
      j++;
    }
  }

  return head;
}

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

Answer 1

«Нормальная» структура для фазы слияния своего рода является:

set output list to empty
while (list1 not empty && list2 not empty)
{
    if (list1->headvalue < list2->headvalue
        move head of list1 to output list
    else
        move head of list2 to output list
}
while (list1 not empty)
    move head of list1 to output list
while (list2 not empty)
    move head of list2 to output list

Работа «MOVE» включает в себя обновление указателя на следующий элемент в списке.

У вас есть несколько разная структура в вашем merge() функция.

Также актуально требует отсчета списков. Обычно вы определяете конец списка, используя либо «Далее, это NULL», либо «Далее - это голова», в зависимости от того, является ли список чисто линейным или ли он круговым списком.