Сортировка слиянием

Тема в разделе "Общие вопросы по С и С++", создана пользователем Charley2, 21 ноя 2010.

Статус темы:
Закрыта.
  1. Charley2

    Charley2 Гость

    Код (Text):
    #pragma hdrstop

    #include <tchar.h>
    #include <iostream.h>
    #include <conio.h>
    #include <windows.h>
    #include <stdlib.h>
    #include <stdio.h>

    //---------------------------------------------------------------------------

    #pragma argsused

    class Element {
    public:
    int data;
    Element *next;
    Element *prev;
    };

    class list {
    Element *top;
    int MaxCount;
    public:
    int count;
    list()
    {
    MaxCount=0;
    count=0;
    top=NULL;
    }
    int IsEmpty ()
    {
    if (top==NULL)
    {
    return true;
    }
    else
    return false;
    }
    int pop()
    {
    if(!IsEmpty())
    {
    int element;
    element=top->data;
    MaxCount--;
    top=top->next;
    return element;
    } else
    return NULL;
    }

    void push(int i)
    {
    Element *link = new Element;
    link->data=i;
    link->next=top;
    top=link;
    MaxCount++;
    }

    void show()
    {
    Element *tmp = top;
    while (tmp)
    {
    cout << tmp->data << " ";
    tmp=tmp->next;
    }
    }

    void mergeSort(list part)
    {
    list right_mas;
    list left_mas;
    int max=MaxCount;
    int element;
    if (max>=2)
    {
    for (int i=max; i>0; i--)
    {
    if (i>max/2)
    {
    element=pop();
    right_mas.push(element);
    } else
    {
    element=pop();
    left_mas.push(element);
    }
    }
    mergeSort(right_mas);
    mergeSort(left_mas);
    //merge(top, stakan.top);
    }
    show();
    cout << "\n";
    }
    };

    int main()
    {    for (int i=0; i<10; i++)
    {
    a=rand()%100;
    t2.push(a);
    }
    t2.mergeSort(t2);
    getch();
    return 0;
    }
    Метод mergeSort делит связный список на списки до тех пор пока в списках останется только один элемент. Вызов t2.mergeSort(t2) должен показать по идее содержимое всех списков, состоящих из одного элемента, но он ничего не показывает. Почему?
     
  2. lazybiz

    lazybiz Well-Known Member
    C\C++ Team

    Регистрация:
    3 ноя 2010
    Сообщения:
    1.344
    Симпатии:
    0
    Charley2
    Как ты думаешь, тебя скоро забанят?
     
  3. Charley2

    Charley2 Гость

    Просто завалы в универе, сам понимаешь нервничаю :facepalm:
     
  4. lazybiz

    lazybiz Well-Known Member
    C\C++ Team

    Регистрация:
    3 ноя 2010
    Сообщения:
    1.344
    Симпатии:
    0
    Потому что при вызове show(), top == NULL.
     
  5. Charley2

    Charley2 Гость

    Понял, ошибку исправил
     
  6. lazybiz

    lazybiz Well-Known Member
    C\C++ Team

    Регистрация:
    3 ноя 2010
    Сообщения:
    1.344
    Симпатии:
    0
    И что получилось? Все заработало?
     
  7. Charley2

    Charley2 Гость

    Сортировка слиянием, если кому интересно.
    Долго мучился, но решение мне подсказали
    Код (Text):
    #pragma hdrstop
    #include <tchar.h>
    #include <iostream>
    #include <fstream>
    #include <windows.h>
    #include <conio.h>
    #include <stdlib.h>
    #include <stdio.h>

    #pragma argsused
    using namespace std;

    template <typename T>
    class Element {
    public:
    T data;
    Element *next;
    Element *prev;
    };


    template <typename T>
    class list {
    Element<T> *top;
    int MaxCount;
    bool metka;
    public:
    list()
    {
    MaxCount=0;
    top=NULL;
    }

    bool IsEmpty ()
    {
    if (top==NULL)
    {
    return true;
    }
    else
    return false;
    }

    void push(T i)
    {
    Element<T> *link = new Element<T>;
    link->data=i;
    link->next=top;
    top=link;
    MaxCount++;
    }

    T pop()
    {
    if(!IsEmpty())
    {
    T element;
    element=top->data;
    MaxCount--;
    top=top->next;
    return element;
    } else
    return NULL;
    }

    void show()
    {
    Element<T> *tmp = top;
    while (tmp)
    {
    cout    << tmp->data << " ";
    tmp=tmp->next;
    }
    }

    list<T> mergeSort(list<T>& stack)
    {
    int max=stack.MaxCount;
    stack.metka=true;
    list<T> central_mas;
    for (int i=max/2; i>0; i--)
    {
    central_mas.push(stack.pop());
    }
    if (stack.MaxCount>1) stack=stack.mergeSort(stack); //это мне подсказали
    if (central_mas.MaxCount>1) central_mas=central_mas.mergeSort(central_mas); //это мне подсказали
    list<T> buffer;
    T left_element;
    T right_element;
    while (stack.IsEmpty()==false && central_mas.IsEmpty()==false)
    {
    left_element=stack.pop();
    right_element=central_mas.pop();
    if (left_element >= right_element)
    {
    buffer.push(left_element);
    central_mas.push(right_element);
    } else
    {
    stack.push(left_element);
    buffer.push(right_element);
    }
    }
    while (stack.IsEmpty()==false)
    {
    buffer.push(stack.pop());
    }
    while (central_mas.IsEmpty()==false)
    {
    buffer.push(central_mas.pop());
    }
    while (buffer.IsEmpty()==false)
    {
    stack.push(buffer.pop());
    }
    return stack;
    }

    ~list()
    {
    if (metka==false)
    {
    while (top!=NULL)
    {
    Element<T> *tmp=top;
    top=top->next;
    delete tmp;
    }
    }
    }
    };
    на 50000 элементах сортировка работает за 0,7 с.
     
Загрузка...
Похожие Темы - Сортировка слиянием
  1. MahovIV
    Ответов:
    7
    Просмотров:
    2.037
  2. vera2014
    Ответов:
    0
    Просмотров:
    1.076
  3. Liori
    Ответов:
    2
    Просмотров:
    1.008
  4. FCDK
    Ответов:
    0
    Просмотров:
    1.267
  5. ленарано
    Ответов:
    1
    Просмотров:
    1.106
Статус темы:
Закрыта.

Поделиться этой страницей