Слияние в односвязном списке C ++ - PullRequest
Новая
       16

Слияние в односвязном списке C ++

0 голосов
/ 29 апреля 2011

Я ищу какой-то простой способ узнать и понять сортировку слиянием на них. Я посмотрел в Интернете, и было обнаружено, что сортировка слиянием действительно хорош для односвязных списков, но я не могу понять, как это сделать. Это сайты, которые я нашел: Wikipedia Merge sort и Специально связанные списки

Я не уверен, какой код дать вам. У меня просто есть это в моем заголовочном файле, и я новичок в этом , поэтому я очень простой. Заранее спасибо за помощь:) 

class Node
{
public:
    int data;
    Node* next;
    Node()
    {
        next = NULL;
        data = 0;
    }
};

class SLLIntStorage
{
public:
    Node* head;
    Node* current;
    Node* tail;

    void Read(istream&);
    void Write(ostream&);
    void setReadSort(bool);
    void sortOwn();
    void print();

    bool _sortRead;
    int numberOfInts;

    SLLIntStorage(const SLLIntStorage& copying)
    {

    }

    SLLIntStorage(void);
    ~SLLIntStorage(void);
};

1 Ответ

2 голосов
/ 29 апреля 2011

Если вы посмотрите на этот абзац из википедии

Концептуально сортировка слиянием работает как следует

  1. Если список имеет длину 0 или 1, то он уже отсортирован. В противном случае:
  2. Разделите несортированный список на два подсписка размером примерно в половину.
  3. Сортировка каждого подсписка рекурсивно путем повторного применения сортировки слиянием.
  4. Объединение двух подсписков обратно в один отсортированный список.

Это довольно кратко говорит вам, что вам нужно делать и какие операции вам нужны. предложения 2 и 4 - это операции, которые вы должны уметь выполнять Split() и Merge(). Разделение может быть реализовано в вашем Node классе как 

// Split: removes half of the list and returns a pointer to it
Node* Node::Split()
{
}

аналогично Merge может быть реализовано как 

// Merge: insert elements from source in order
Node::Merge(Node* source)
{
}

в целом 1, 2, 3, 4 описывают, что вам нужно сделать, чтобы выполнить фактическую сортировку, реализуйте эти шаги по порядку в функции сортировки, используя операции списка Merge и Split.

Это только один способ, которым Merge и Split может выглядеть, как их реализация будет зависеть от вашего стиля, требований, знания c ++ и различных других факторов. (Я уверен, что вы найдете некоторые другие решения в ответах). Вам, вероятно, также понадобится Node::Append(Node* val) или что-то подобное в качестве основного оператора. Выглядит не так, как будто вам понадобится Node::Remove(Node* val), но это также не помешает реализовать это.

...