Как я могу написать функцию сортировки слиянием, которая принимает LinkedList & в качестве ввода в C ++? - PullRequest
Новая
       68

Как я могу написать функцию сортировки слиянием, которая принимает LinkedList & в качестве ввода в C ++?

0 голосов
/ 10 апреля 2020

Вот объявление моего LinkedList: 

struct LinkedList {
LinkedListNode *head, *tail;
LinkedList() { head = tail = NULL; }
~LinkedList() {
    Clear();
} //end-~LinkedList

void Clear() {
    while (head) {
        LinkedListNode* p = head;
        head = head->next;
        delete p;
    } //end-while

    head = tail = NULL;
} //end-Clear

void Append(int key) {
    LinkedListNode* node = new LinkedListNode(key);
    if (tail == NULL) head = tail = node;
    else {
        tail->next = node;
        tail = node;
    } //end-else
} //end-Append
};

Вот тело функции, которое мне нужно реализовать как этот формат в C ++: 

void MergeSort(LinkedList& list){ //I need to make merge sort with LinkedList }

Вот код, который тестирует мой алгоритмы сортировки, но сортировка слиянием не работает (кстати, я не могу изменить сторону теста). 

#define N 1024*32
int A[N];  
typedef void (*SortingFunction)(LinkedList &);

float Test(SortingFunction F, char *msg){
  int B[] = {4, 2, 5, 7, 8, 1, 10, 9, 15, 34, 6, 17, 66, 55, 44, 33};

  LinkedList list;
  for (int i = 0; i < sizeof(B) / sizeof(int); i++) {
      list.Append(B[i]);
  } //end-for

  // Use the sorting algorithm
  F(list);

  printf("Using %s to sort %d numbers...\n", msg, 16);

  // Check the result
  LinkedListNode* p = list.head;
  int S[] = { 1, 2, 4, 5, 6, 7, 8, 9, 10, 15, 17, 33, 34, 44, 55, 66 };
  for (int i = 0; i < sizeof(S) / sizeof(int); i++) {
      if (S[i] != p->key) return 0;
      p = p->next;
  } // end-for

  list.Clear();
  srand((unsigned int)time(NULL));
  int i;
  int min = INT_MAX;
  int max = 0;
  for (i=0; i<100;i++){
      int number = rand();
      list.Append(number);

      if (number<min) min=number;
      else if (number>max) max=number;
  } //end-for

  printf("Using %s to sort %d numbers...", msg, N);
  time_t t1 = time(NULL);
  F(list);
  time_t t2 = time(NULL);
  printf("took %I64d seconds\n", t2-t1);

  // Check the result
  if (list.head->key!=min || list.tail->key!=max) return 0;

  LinkedListNode* q = list.head;
  p = q->next;
  while (p){
    if (q->key > p->key) return 0;
    q = p;
    p = p->next;
  } //end-for

  return 100;
} //end-Test

/****************************************************
 * Main function
 ****************************************************/
int main(){
  float grade = 0;
  printf("======================= TEST4 =======================\n");
  grade += Test(MergeSort, "MergeSort");
  return 0;
} //end-main

Вот код, который я написал для сортировки слиянием, но он не работает, я думаю, что проблема в функции прототип. Все примеры, которые я видел из inte rnet, используют указатель узла в качестве параметра функции. Но по моему я должен передать ссылку как LinkedList &. Я пробовал некоторые коды, но не смог добиться результата. Кроме того, вот код, который я пробовал, но не получил результата. 

void MergeSort(LinkedList& list){
    LinkedListNode* myhead = list.head;
    mergeSorting(myhead);

} //end-MergeSort
void mergeSorting(LinkedListNode*& head) {
    if (head->next != NULL)             
    {
        LinkedListNode* head1;
        LinkedListNode* head2 = head;
        int len = getLength(head);
        for (int i = 0; i < len / 2; i++)
        {
            head1 = head2;
            head2 = head2->next;
        }
        head1->next = NULL; 
        head1 = head;
        mergeSorting(head1);
        mergeSorting(head2);
        head = merge(head1, head2);
    }
}
int getLength(LinkedListNode* head) {
    LinkedListNode* cur = head;
    int i = 0;
    for (; cur != NULL; cur = cur->next) {
        i++;
    }
    return i;
}
LinkedListNode* merge(LinkedListNode*& head1, LinkedListNode*& head2) {
    LinkedListNode* newHead;
    if (head1 == NULL) return head2;
    else if (head2 == NULL) return head1;
    if (head1->key < head2->key) {
        newHead = head1;
        newHead->next = merge(head1->next, head2);
    }
    else {
        newHead = head2;
        newHead->next = merge(head1, head2->next);
    }
    return newHead;
}

Ответы [ 2 ]

2 голосов
/ 10 апреля 2020

Код требует немного другого подхода. mergeSorting должен взять указатель на узел в качестве входного параметра и вернуть указатель на узел. Последние 3 строки должны выглядеть примерно так: 

        head1 = mergeSorting(head1);
        head2 = mergeSorting(head2);
        return merge(head1, head2);

Затем для вызывающего кода: 

void MergeSort(LinkedList& list){
    list.head = mergeSorting(list.head);
}

Предполагается, что вам разрешено выполнять поиск в Интернете по примеру алгоритмов, снизу вверх сортировка слиянием для связанных списков выполняется быстрее, но она не основана на логике c, используемой для сортировки слиянием снизу вверх для массивов. Если интересно, статья в вики имеет пример псевдокода:

https://en.wikipedia.org/wiki/Merge_sort#Bottom -up_implementation_using_lists

1 голос
/ 10 апреля 2020

Вы склонны использовать ссылки в местах, где они создают путаницу.

MergeSort следует просто взять указатель на первый узел списка и вернуть указатель на первый узел отсортированного списка.

merge должен просто взять 2 указателя на начальные узлы отсортированного списка и вернуть указатель на первый узел объединенного отсортированного списка.

Вот измененная версия: 

void MergeSort(LinkedList& list) {
    LinkedListNode *cur = list.head = mergeSorting(list.head);
    if (cur) {
        while (cur->next)
            cur = cur->next;
    }
    list.tail = cur;
}
LinkedListNode *mergeSorting(LinkedListNode *head) {
    if (head->next != NULL) {
        LinkedListNode *head1;
        LinkedListNode *head2;
        LinkedListNode *prev = head;
        LinkedListNode *cur = head;
        int half = getLength(head) / 2;
        for (int i = 0; i < half; i++) {
            prev = cur;
            cur = cur->next;
        }
        prev->next = NULL; 
        head1 = mergeSorting(head);
        head2 = mergeSorting(cur);
        head = merge(head1, head2);
    }
    return head;
}
int getLength(const LinkedListNode *head) {
    const LinkedListNode* cur = head;
    int i = 0;
    for (; cur != NULL; cur = cur->next) {
        i++;
    }
    return i;
}
LinkedListNode *merge(LinkedListNode *head1, LinkedListNode *head2) {
    LinkedListNode *newHead;
    if (head1 == NULL)
        return head2;
    if (head2 == NULL)
        return head1;
    if (head1->key <= head2->key) {
        newHead = head1;
        newHead->next = merge(head1->next, head2);
    } else {
        newHead = head2;
        newHead->next = merge(head1, head2->next);
    }
    return newHead;
}
...