2lab_124

/*  Напишите функцию упорядочения линейного самоадресуемого списка  с помощью рекурсивного алгоритма слияния.
    В качестве данных в списке используйте случайные числа из интервала от -999 до 999.
    Рекомендуемые значения длины списка n: 10, 100, 1000, 10000, 100000, 1000000.
    Проведите проверку упорядоченности с помощью функции с параметрами.
    Задание 4 является бонусным.
*/

#include <iostream>
#include <conio.h>
#include <time.h>

using namespace std;

#define maxn 100

int a[maxn];

struct Node
{
    int num;
    Node *next;
};



Node *add_to_list(Node *lnode, int num) //добавление в список
{
    Node *newel = new Node, *l = lnode;

    newel->num = num;
    newel->next = NULL;

    if(!lnode)
        return newel;

    while(l->next)
        l = l->next;

    l->next = newel;

    return lnode;
}

void del_list(Node *lnode) //удаление списка
{
    Node *p_s = lnode;
    Node *p_tmp = p_s;

    while(p_s)
    {
        p_s = p_s->next;
        delete p_tmp;
        p_tmp = p_s;
    }
}

void test(int *a, int n)
{
    for (int i=1; i<n; ++i)
    {
        if (a[i-1]>a[i])
        {
            printf("The list is not sorted. ");
            system("pause");
            exit(0);
        }
    }
}

void merge (int l, int r, Node *lnode)
{
    int i=0;

    for(; lnode; ++i, lnode = lnode->next)
    {
        a[i]=lnode->num;
    }

    if (r == l)
        return;

    if (r - l == 1)
    {
        if (a[r] < a[l])
            swap(a[r], a[l]);
        return;
    }

    int m = (r + l) / 2;
    merge(l, m, lnode);
    merge(m + 1, r, lnode);

    int b[maxn]; //массив для записи минимальных элементов из левой и правой части
    int xl = l; //левая часть
    int xr = m + 1; //правая часть
    int cur = 0;

    while (r - l + 1 != cur)
    {
        if (xl > m)
            b[cur++] = a[xr++];
        else if (xr > r)
            b[cur++] = a[xl++];
        else if (a[xl] > a[xr])
            b[cur++] = a[xr++];
        else b[cur++] = a[xl++];
    }

    for (int i = 0; i < cur; i++)
        a[i + l] = b[i];
}

int main()
{
    Node *lnode = NULL;
    int buff, n;

    cout << "Enter the value of n: ";
    cin >> n;

    srand(time(0));
    printf("Source list: ");
    for (int i = 0; i < n; i++)
    {
        buff=rand()%100;
        lnode=add_to_list(lnode, buff);
        cout << buff << " ";
    }
    putchar('\n');

    merge(0, n - 1, lnode);

    test(a,n);

    for(int i=0; i<n; ++i, lnode = lnode->next)
    {
        lnode=add_to_list(lnode, a[i]);
    }

    printf("Ordered list: ");
    for(; lnode;  lnode = lnode->next)
    {
        printf("%d ",lnode->num);
    }

    del_list(lnode);

    getch();
    return 0;
}