VPF::Восходящая сортировка связных списков слиянием.

VAAKAraceGUM

Дата 13.2.2012, 22:07 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 9
Регистрация: 13.2.2012

Репутация: нет
Всего: нет

Здравствуйте, мне дали задание сделать восходящую сортировку связного списка слиянием .
Собственно моя программа (создание двусвязного списка, добавление элемента в любое место, удаление из любого места, печать ) выглядит так :

Код


#include <stdio.h>
#include <stdlib.h>
#include <conio.h>

struct stack
{
    int val;
    struct stack * next;
    struct stack * prev;
};

struct stack * root;
struct stack * last;

int add_val (int where, int pos, int kol);
int del_val (int pos, int kol);
void print_stack (unsigned int num);

int main ()
{
    root = (struct stack *) malloc (sizeof (struct stack));
    last = root;

    int count = 0;
    int pos;
    int choise_where;
    char choise;
    
    while (choise != 'q')
    {
        printf ("\nКоманды:\n");
        printf ("\"a\" - добавление элемента в список;\n");
        printf ("\"d\" - удаление элемента из списка;\n");
        printf ("\"q\" - выход;\n");
        printf ("Ваш выбор: ");
        scanf (" %c", &choise);
        
        if (choise == 'a')
        {
            printf ("\nУкажите, как добавить: \n");
            printf ("1) создать новый элемент\n");
            printf ("2) после элемента\n");
            printf ("3) перед элементом\n");
            printf ("4) вместо элемента\n");
            printf ("Ваш выбор: ");
            scanf (" %d", &choise_where);
            
            if (choise_where < 1 || choise_where > 4)
            {
                printf ("Нет такого варианта!\n");
                continue;
            }
            if (choise_where != 1)
            {
                printf ("Позиция (номер элемента): ");
                scanf (" %d", &pos);
            }
            count = add_val (choise_where, pos, count);
            print_stack (count);
        }
        else if (choise == 'd')
        {
            printf ("Позиция, откуда удалить: ");
            scanf (" %d", &pos);
            count = del_val (pos, count);
            print_stack (count);
        }
        else if (choise == 'q') return 0;
        else printf ("Нет такого варианта!\n");
    }
    return 0;
}

int add_val (int where, int pos, int kol)
{
    int value, iter;
    struct stack *ptr_one, *ptr_two;
    struct stack *nov = (struct stack*) malloc (sizeof (struct stack));
    
    printf ("Значение (целое число): ");
    scanf (" %d", &value);

    ptr_one = root;
    if (where == 1)
    {
        last->val = value;
        last->next = nov;
        nov->prev = last;
        last = last->next;
        return ++kol;
    }

    
    if (pos > kol || pos < 1)
    {
        printf ("Ошибка, нет %d-ого элемента!\n", pos);
        return kol;
    }
    for (iter = 1; iter < pos; iter++)
        ptr_one = ptr_one->next;

    if (where == 2)
    {
        nov->val = value;
        ptr_two = ptr_one->next;
        ptr_one->next = nov;
        nov->prev = ptr_one;
        nov->next = ptr_two;
        ptr_two->prev = nov;
        return ++kol;
    }

    if (where == 3)
    {
        nov->val = value;
        if (pos == 1) root->prev = (struct stack*) malloc (sizeof (struct stack));
        ptr_two = ptr_one->prev;
        ptr_one->prev = nov;
        nov->next = ptr_one;
        nov->prev = ptr_two;
        ptr_two->next = nov;
        if (pos == 1) root = nov;
        return ++kol;
    }

    if (where == 4)
        ptr_one->val = value;
        
    return kol;
}

int del_val (int pos, int kol)
{
    int iter;
    struct stack *ptr;
    ptr = root;
    if (pos > kol || pos < 1)
    {
        printf ("Ошибка, нет %d-ого элемента!\n", pos);
        return kol;
    }
    for (iter = 1; iter < pos; iter++)
        ptr = ptr->next;

    if (pos == 1)
    {
        root = root->next;
        free (root->prev);
    }
    else if (pos == kol)
    {
        last = last->prev;
        free (last->next);
    }    
    else
    {
        (ptr->prev)->next = ptr->next;
        (ptr->next)->prev = ptr->prev;
        free (ptr);
    }
    return --kol;
}

void print_stack (unsigned int num)
{
    int go;
    if (num == 0)
    {
        printf ("\nСПИСОК ПУСТ!\n");
        return;
    }
    printf ("\nСПИСОК: ");
    struct stack* out = root;

    for (go = 0; go < num; go++)
        {
        printf ("%d ", out->val);
        out = out->next;
        }
    printf ("\n");
}

Соответственно, мне надо сделать эту злополучную Восходящую сортировку связного списка слиянием.Помогите плз...

borisbn

Дата 14.2.2012, 08:45 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 4875
Регистрация: 6.2.2010
Где: Ростов-на-Дону

Репутация: 22
Всего: 135

делаешь ф-цию, в которую передаёшь указатель на стартовый элемент списка. в этой функции проходишь от стартового элемента до конца списка и ищёшь минимальный элемент, затем меняешь местами стартовый и найденный минимальный элементы и вызываешь эту же функцию со стартовым элементом равным следующему за стартовым элементом. как-то так

Код


void sort_list( struct stack * start ) {
    if ( start == 0 )
        return;
    struct stack *min = start;
    struct stack *curr = start->next;
    while ( curr != 0 ) {
        if ( curr->val < min->val ) {
            min = curr;
        }
        curr = curr->next;
    }
    int temp = start->val;
    start->val = min->val;
    min->val = temp;
    sort_list( start->next );
}

--------------------

Женщины отличаются от программистов тем, что у них чары состоят из стрингов

VAAKAraceGUM

Дата 14.2.2012, 11:15 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 9
Регистрация: 13.2.2012

Репутация: нет
Всего: нет

borisbn, а ты проверял, она у тебя работает ? Просто у меня она чет ничего не делает, циклится , я вместо struct stack * start , поставил root , как корневой элемент...

Код


#include <stdio.h>
#include <stdlib.h>
#include <conio.h>

struct stack
{
    int val;
    struct stack * next;
    struct stack * prev;
};

struct stack * root;
struct stack * last;

int add_val (int where, int pos, int kol);
int del_val (int pos, int kol);
void print_stack (unsigned int num);
void sort_list(struct stack * start);

int main ()
{
    root = (struct stack *) malloc (sizeof (struct stack));
    last = root;

    int count = 0;
    int pos;
    int choise_where;
    char choise;
    
    while (choise != 'q')
    {
        printf ("\nКоманды:\n");
        printf ("\"a\" - добавление элемента в список;\n");
        printf ("\"d\" - удаление элемента из списка;\n");
        printf ("\"h\" - сортировка слиянием;\n");
        printf ("\"q\" - выход;\n");
        printf ("Ваш выбор: ");
        scanf (" %c", &choise);
        
        if (choise == 'a')
        {
            printf ("\nУкажите, как добавить: \n");
            printf ("1) создать новый элемент\n");
            printf ("2) после элемента\n");
            printf ("3) перед элементом\n");
            printf ("4) вместо элемента\n");
            printf ("Ваш выбор: ");
            scanf (" %d", &choise_where);
            
            if (choise_where < 1 || choise_where > 4)
            {
                printf ("Нет такого варианта!\n");
                continue;
            }
            if (choise_where != 1)
            {
                printf ("Позиция (номер элемента): ");
                scanf (" %d", &pos);
            }
            count = add_val (choise_where, pos, count);
            print_stack (count);
        }
        else if (choise == 'd')
        {
            printf ("Позиция, откуда удалить: ");
            scanf (" %d", &pos);
            count = del_val (pos, count);
            print_stack (count);
        }
        else if (choise == 'q') return 0;
        else if (choise == 'h')
        {
            sort_list(root);
            print_stack (count);    
        }
        else printf ("Нет такого варианта!\n");
    }
    return 0;
}

int add_val (int where, int pos, int kol)
{
    int value, iter;
    struct stack *ptr_one, *ptr_two;
    struct stack *nov = (struct stack*) malloc (sizeof (struct stack));
    
    printf ("Значение (целое число): ");
    scanf (" %d", &value);

    ptr_one = root;
    if (where == 1)
    {
        last->val = value;
        last->next = nov;
        nov->prev = last;
        last = last->next;
        return ++kol;
    }

    
    if (pos > kol || pos < 1)
    {
        printf ("Ошибка, нет %d-ого элемента!\n", pos);
        return kol;
    }
    for (iter = 1; iter < pos; iter++)
        ptr_one = ptr_one->next;

    if (where == 2)
    {
        nov->val = value;
        ptr_two = ptr_one->next;
        ptr_one->next = nov;
        nov->prev = ptr_one;
        nov->next = ptr_two;
        ptr_two->prev = nov;
        return ++kol;
    }

    if (where == 3)
    {
        nov->val = value;
        if (pos == 1) root->prev = (struct stack*) malloc (sizeof (struct stack));
        ptr_two = ptr_one->prev;
        ptr_one->prev = nov;
        nov->next = ptr_one;
        nov->prev = ptr_two;
        ptr_two->next = nov;
        if (pos == 1) root = nov;
        return ++kol;
    }

    if (where == 4)
        ptr_one->val = value;
        
    return kol;
}

int del_val (int pos, int kol)
{
    int iter;
    struct stack *ptr;
    ptr = root;
    if (pos > kol || pos < 1)
    {
        printf ("Ошибка, нет %d-ого элемента!\n", pos);
        return kol;
    }
    for (iter = 1; iter < pos; iter++)
        ptr = ptr->next;

    if (pos == 1)
    {
        root = root->next;
        free (root->prev);
    }
    else if (pos == kol)
    {
        last = last->prev;
        free (last->next);
    }    
    else
    {
        (ptr->prev)->next = ptr->next;
        (ptr->next)->prev = ptr->prev;
        free (ptr);
    }
    return --kol;
}

void print_stack (unsigned int num)
{
    int go;
    if (num == 0)
    {
        printf ("\nСПИСОК ПУСТ!\n");
        return;
    }
    printf ("\nСПИСОК: ");
    struct stack* out = root;

    for (go = 0; go < num; go++)
        {
         printf ("%d ", out->val);
         out = out->next;
        }
    printf ("\n");
}

void sort_list( struct stack * start ) 
{
    if ( start == 0 )
        return;
    struct stack *min = start;
    struct stack *curr = start->next;
    while ( curr != 0 ) {
        if ( curr->val < min->val ) 
        {
            min = curr;
        }
        curr = curr->next;
    }
    int temp = start->val;
    start->val = min->val;
    min->val = temp;
    sort_list( start->next );
}

borisbn

Дата 14.2.2012, 11:24 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 4875
Регистрация: 6.2.2010
Где: Ростов-на-Дону

Репутация: 22
Всего: 135

Цитата(VAAKAraceGUM @ 14.2.2012, 11:15

)

а ты проверял, она у тебя работает ?

эту почётную обязанность я возложил на тебя smile

я вообще-то тебе текстом всё объяснил, а код привёл просто так - для пояснения сказанного

А виснет она потому, что я предполагал, что твой в твоём листе, как в честном контейнере, next последнего элемента равен 0 (или NULL - как угодно). можешь исправить сравнение с 0-м в моём коде на сравнение с last

Добавлено через 1 минуту и 59 секунд
не. неправильно будет сравнивать с last - самый последний элемент не отработает. лучше занули next у последнего элемента. а раз уж у тебя двунаправленный список, то и prev у первого элемента неплохо было бы занулить

--------------------

Женщины отличаются от программистов тем, что у них чары состоят из стрингов

VAAKAraceGUM

Дата 15.2.2012, 01:53 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 9
Регистрация: 13.2.2012

Репутация: нет
Всего: нет

В общем в итоге я прозрел и сделал другой рекурсивный алгоритм :

Код


void sort_pom(int mas[], int lb, int split, int ub) //функция слияния файлов
{
    // текущая позиция чтения из первой последовательности mas[lb]...mas[split]
  int pos1 = lb;
    // текущая позиция чтения из второй последовательности mas[split+1]...mas[ub]
  int pos2 = split+1;
    // текущая позиция записи в temp
  int pos3 = 0;
  int temp[ub+1];
  // идет слияние, пока есть хоть один элемент в каждой последовательности
  while (pos1 <= split && pos2 <= ub) 
  {
    if (mas[pos1] < mas[pos2])
      temp[pos3++] = mas[pos1++];
    else
      temp[pos3++] = mas[pos2++];
  }
  // одна последовательность закончилась - копировать остаток другой в конец буфера
  while (pos2 <= ub)   // пока вторая последовательность непуста 
    temp[pos3++] = mas[pos2++];
  while (pos1 <= split)  // пока первая последовательность непуста
    temp[pos3++] = mas[pos1++];
  // скопировать буфер temp в mas[lb]...mas[ub]
  for (pos3 = 0; pos3 < ub-lb+1; pos3++)
    mas[lb+pos3] = temp[pos3];     
}

void sort_spisok( int mas[] , int lb, int ub) 
{
    int split, i;                         // индекс, по которому делим массив

    if (lb < ub) 
    {               
       split = (lb + ub)/2;
       sort_spisok(mas, lb, split);       // сортировать левую половину 
       sort_spisok(mas, split+1, ub);     // сортировать правую половину 
       sort_pom(mas, lb, split, ub);      // слить результаты в общий массив
    }
}

А потом просто восстановил список из массива...

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C/C++: Общие вопросы \| Следующая тема »