как работает эта рекурсивная функция?объединить сортировать два односвязных списков - PullRequest
Новая
       13

как работает эта рекурсивная функция?объединить сортировать два односвязных списков

0 голосов
/ 02 января 2019

Я нашел эту рекурсивную функцию в C ++ на geeksforgeeks.org, чтобы объединить и отсортировать два односвязных списка, я использовал netbeans для отладки этого кода, но все же я не могу получить четкое представление о функции этого кода.также я видел подобный код stackoverflow, но без объяснения того, как он работает.Мой вопрос об идее, стоящей за этим, и о том, как она работает, когда достаточное объяснение здесь также поможет другим с тем же вопросом.

отладил код на NetBeans, чтобы понять рабочий процесс кода 

//Merges two given lists in-place. This function 
// mainly compares head nodes and calls mergeUtil() 

Node *merge(Node *h1, Node *h2) 
 { 
if (!h1) 
    return h2; 
if (!h2) 
    return h1; 

// start with the linked list 
// whose head data is the least 
if (h1->data < h2->data) 
{ 
    h1->next = merge(h1->next, h2); 
    return h1; 
} 
else
{ 
    h2->next = merge(h1, h2->next); 
    return h2; 
 } 
}

эта функция должна возвращать один отсортированный связанный список

Ответы [ 2 ]

0 голосов
/ 02 января 2019

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

  • {13, 24, 74}
  • {34, 72, 95}

Обратите внимание, что оба они отсортированы, так какэто требование алгоритма :

Учитывая два отсортированных списка, объедините их, чтобы получить объединенный отсортированный список

Я скомпилировалСледуйте, как это получается:

  • Стрелка - это порядок выполнения
  • Каждая строка представляет собой кадр стека.В частности, строка слева перед рекурсивным вызовом для merge, а справа - ее результат после.

Execution order

Обратите также внимание на следующее:

  • На каждой стрелке слева меньший элемент изначало узлов исчезает
  • на обратном пути, этот меньший элемент получает отсортированный порядок элементов на другой стороне.В самом конце мы возвращаем список, который только что получил другой, в отсортированном виде, а именно: {13, 24, 34, 72, 74, 95}
0 голосов
/ 02 января 2019

Я добавил комментарии к коду.Я также изменил if с <на <= в случае, если это использовалось для сортировки слиянием, где, если h1-> data == h2-> data, вы бы сначала хотели h1 для стабильности.Имейте в виду, что два списка уже отсортированы, эта функция просто объединяет их.

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

// initial input parameters, h1 and h2 each point to already sorted lists
Node *merge(Node *h1, Node *h2) 
{
    if (!h1)                                // if h1 empty
        return h2;                          //  return h2
    if (!h2)                                // if h2 empty
        return h1;                          //  return h1

    if (h1->data <= h2->data)               // if h1->data <= h2->data
    {
        h1->next = merge(h1->next, h2);     //  h1->next = smaller of {h1->next, h2}
        return h1;                          //  return h1
    }
    else                                    // else h1->data > h2->data
    {
        h2->next = merge(h1, h2->next);     //  h2->next = smaller of {h1, h2->next}
        return h2;                          //  return h2
    }
}
...