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

Question

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

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

---

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

Поэтому, прежде чем разместить код на том-структуру, я использую:

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

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

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

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 

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

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

Это также обычное требование, чтобы списки учитывались. Обычно вы определяете конец списка, используя «next is null» или «next is head» в зависимости от того, является ли список чисто линейным или является ли он циклическим списком.