C++ Связанный список Сортировка, разбиение и печать вопроса

Question

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

1. написать программу, которая создает вперед связанный список по меньшей мере, 20 элементов, где каждый элемент содержит случайное целое число в диапазоне от 0 до 99. Печати списка.

2. Напишите функцию «returnMiddleList», чтобы найти средний элемент связанного списка за один проход. Распечатайте целочисленное значение этого элемента и положение этого элемента (начиная с нуля) относительно головы (где голова = 0, элемент, на который указывает голова = 1, элемент, на который указывает предыдущий = 2 , и т.д).

3. Разделите список пополам на средний элемент, чтобы создать два полностью изолированных * связанных списка почти равного размера (+/- 1) и распечатать два списка. Измените функцию returnMiddleList, чтобы выполнить это, вернув головку второго связанного списка и установив ссылку элемента, указывающего на эту главу, на нуль. Затем напечатайте две суммы целых чисел, хранящихся в элементах обоих списков.

4. Отсортируйте два списка от наименьшего до наибольшего и распечатайте их (печать на этом этапе необязательна в зависимости от выбранного подхода сортировки). Затем объедините два списка, сортируя их снова от наименьшего до наибольшего и распечатайте новый список. (Подсказка:. Вы можете разделить списки дальше и сортировать их по шкале от одного до двух списков элементов до сортировки и объединения двух первых несортированные списки Что такого рода называется?)

Я получил # 1 и # 2, но # 3 и # 4 - это то, где проблема начинается. Когда я разбиваю свой список ссылок на два списка и распечатываю отдельные списки, мой первый список ссылок выводит 9 номеров, когда он должен печатать 10 (10-е число как-то исчезает?), Но когда я делаю сумму первого списка сразу после этого число, которое исчезло, добавляется в сумму! Я не знаю, почему он исчезает, и это одна проблема. Другая проблема во втором списке: в список добавляется случайное «0», и один из чисел теряется. Моя последняя проблема связана с №4, поскольку алгоритм слияния, который я использовал, не работает (я объединяю список вместе, сортируя их, но я не использую рекурсию, потому что мы еще не узнали об этом). Любые ввод и помощь будут очень признательны! Благодаря!

#include <iostream> 
#include <stdlib.h> 
#include <time.h> 
using namespace std; 

struct nodeType { 
    int data; 
    nodeType *link; 
}; 

void populateList(nodeType *head) { 
// srand(time(NULL)); 
    nodeType *temp; 
    nodeType *current = head; 

    for (int i = 0; i < 20; i++) { 
     temp = new nodeType; 

     current->data = rand() % 100; 

     current->link = temp; 

     current = temp; 
    } 

    temp->link = NULL; 
} 

void print(nodeType *head) { 
    int i = 1; 

    while (head->link != NULL) { 
     cout << "#" << i++ << ": " << head->data << endl; 

     head = head->link; 
    } 
} 

nodeType* returnMiddleList(nodeType *head) { 
    nodeType *p1 = head, *p2 = head; 
    int count = 0; 
    int middle = 1; 

    while (p1->link->link != NULL) { 
     p1 = p1->link; 

     count++; 

     if (count % 2 == 0) { 
      p2 = p2->link; 
      middle++; 
     } 

    } 

    cout << "Middle #" << middle << ": " << p2->data << endl; 

    p1 = p2->link; 
    p2->link = NULL; 

    return p1; 
} 

void add(nodeType *head) { 
    int sum = 0; 

    while (head != NULL) { 
     sum = sum + head->data; 
     head = head->link; 
    } 

    cout << sum << endl; 
} 

void sort(nodeType *head) { 
    nodeType *temp = head; 

    while (temp != NULL) { 
     nodeType *temp2 = temp; 

     while (temp2 != NULL) { 
      if (temp->data > temp2->data) { 
       int temp3; 

       temp3 = temp->data; 
       temp->data = temp2->data; 
       temp2->data = temp3; 
      } 

      temp2 = temp2->link; 
     } 

     temp = temp->link; 
    } 
} 

nodeType* merge(nodeType* head1, nodeType* head2) { 
    nodeType *head3 = new nodeType, *current1 = head1, *current2 = head2; 

    while (current1 != NULL || current2 != NULL) { 
     if (current1 == NULL) { 
      while (current2 != NULL) { 
       //logic 
       current2 = current2->link; //dumps list 2 
       head3->data = current2->data; 
      } 
      break; 
     } 
     if (current2 == NULL) { 
      while (current1 != NULL) { 
       //Logic 
       current1 = current1->link; //dumps list 1 
       head3->data = current1->data; 
      } 
      break; 
     } 

     if (current1->data < current2->data) { 
      //logic 
      current1 = current1->link; //increments list 1 
      head3->data = current1->data; 

     } else { 
      //logic 
      current2 = current2->link; //increments list 2 
      head3->data = current2->data; 

     } 

    } 

    return head3; 
} 

int main() { 
    nodeType *head = new nodeType, *head2, *head3; 

    populateList(head); 

    print(head); 
    cout << endl; 

    head2 = returnMiddleList(head); 

    cout << endl << "List #1 Sum: "; 
    add(head); 

    cout << endl << "List #2 Sum: "; 
    add(head2); 

    sort(head); 
    cout << endl << "List #1 Sorted" << endl; 
    print(head); 

    sort(head2); 
    cout << endl << "List #2 Sorted" << endl; 
    print(head2); 

    head3 = merge(head, head2); 
    print(head3); 
} 

Answer 1

Для № 3 вам не нужен счет. Код также должен включать проверки для главы == NULL, p1 == NULL перед попыткой проверить ссылку p1->, и он должен проверить на p1-> link == NULL перед попыткой проверить ссылку p1-> link->. После добавления этих проверок, чтобы исключить счет, просто переместите p1 по два за раз: p1 = p1-> link-> link, одновременно продвигая p2: p2 = p2-> link. Когда вы дойдете до конца списка с помощью ссылки p1-> link или p1-> link->, рассмотрите p2 как указатель на последний узел первой половины списка и следуйте приведенным инструкциям о том, как разделить список.

Для # 4 подход рекурсивного разбиения списка на под-списки в целом известен как divide and conquer algorithm (wiki link). Этот подход используется для сортировки слияния сверху вниз, и хотя существуют другие подходы, которые лучше подходят (быстрее) для реализации сортировки слияния со связанными списками, я понимаю, что инструктор, вероятно, хочет, чтобы вы следовали данным подсказкам.