VPF::Алгоритмы сортировки - Форум программистов

MJBuster

Дата 8.9.2012, 17:09 (ссылка)

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

Загрузка ...

Новичок

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

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

Здесь сортировка заданной информации методом подсчёта и сбалансированным N-ленточным слиянием.
Помогите пожалуйста найти в коде, где происходит разбиение строк на ленты и для чего нужен и как используется массив s[4].
Код на Си.

Код


#include <stdio.h>
#include <conio.h>
#include <locale.h>
#include <stdlib.h>
#include <math.h>
void main()
{
    setlocale(LC_ALL, "Russian");
    int i,j,k,r,kolvo_strok=0, kolvo_sym=0,q,*Vsp,d,p, s[4];
    char **Mass, ch, **Mass_new;
    printf("Введите количество строк, такое, что kоличество/4=целому числу: ");
    scanf("%d", &kolvo_strok);
    printf("Введите количество символов в строке:");
    scanf("%d", &kolvo_sym);
    Mass=(char **)malloc(kolvo_strok*sizeof(char));
    for(i=0;i<kolvo_strok;i++)
        Mass[i]=(char *)malloc(kolvo_sym*sizeof(char));
    Mass_new=(char **)malloc(kolvo_strok*sizeof(char));
    for(i=0;i<kolvo_strok;i++)
        Mass_new[i]=(char *)malloc(kolvo_sym*sizeof(char));
    if(!Mass_new)
    {
        printf("Ошибка 0: память не выделена!");
        getch();
        exit(1);
    }
    if(!Mass)
    {
        printf("Ошибка 1: память не выделена!");
        getch();
        exit(1);
    }
    Vsp=(int *)malloc(kolvo_strok*sizeof(int));
    if(!Vsp)
    {
        printf("Ошибка 2: память не выделена!");
        getch();
        exit(1);
    }
    for(i=0;i<kolvo_strok;i++)
    {
    re:    printf("\nВведите %d символов английского алфавита %d-й строки: ",kolvo_sym,i+1);//ввод массива
        for(j=0;j<kolvo_sym;j++)
        {
            ch=getch();
            printf("%c",ch);
            if((ch>=65)&&(ch<=122))
                Mass[i][j]=ch;
            else
            {
                printf("\nНеправильный ввод, повторите:");
                goto re;
            }
        }
    }
    for(r=1;r<=4;r++)//сортировка четырех частей массива по отдельности
    {
        for(i=((r-1)*kolvo_strok/4);i<(r*kolvo_strok/4);i++)/*определение упорядоченных позиций в файлах*/
        {
            k=0;
            for(j=((r-1)*kolvo_strok/4);j<(r*kolvo_strok/4);j++)
                if(Mass[i][0]>Mass[j][0])
                    k++;
            Vsp[i]=k;
        }
        p=0;
        k=0;
        for(i=((r-1)*kolvo_strok/4);i<(r*kolvo_strok/4);i++)//перестановка
        {
            for(j=((r-1)*kolvo_strok/4);j<(r*kolvo_strok/4);j++)
                if(Vsp[j]==p)
                    d=j;
                p++;
            for(q=0;q<kolvo_sym;q++)
            {
                ch=Mass[d][q];
                Mass[d][q]=Mass[i][q];
                Mass[i][q]=ch;
            }
            k=Vsp[i];
            Vsp[i]=Vsp[d];
            Vsp[d]=k;
        }
    }
    /*теперь мы получили массив, каждая из четырех частей которого упорядочена методом подсчета, теперь надо упорядочить весь массив, для этого используется способ слияния лент*/
    for(i=0;i<4;i++)//инициализация счетчиков
        s[i]=i*kolvo_strok/4;
    k=0;
    for(i=0;i<kolvo_strok;i++)//сортировка слинием лент
    {
        ch='z';
        for(j=0;j<4;j++)//поиск наименьшего элемента
            if((s[j]!=-1)&&(ch>=Mass[s[j]][0]))
            {
                ch=Mass[s[j]][0];
                d=j;
            }
        for(j=0;j<kolvo_sym;j++)
            Mass_new[k][j]=Mass[s[d]][j];//присвоение строки новому массиву
        k++;
        s[d]=s[d]+1;//увеличивание счетчика
        if(s[d]==(d*kolvo_strok/4)+kolvo_strok/4)//если счетчик достиг предела
            s[d]=-1;
    }
    for(i=0;i<kolvo_strok;i++)//вывод
    {
        printf("\n");
        for(j=0;j<kolvo_sym;j++)
            printf("%c",Mass_new[i][j]);
    }
    getch();
}

NadezdaT

Дата 8.9.2012, 19:00 (ссылка)

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

Загрузка ...

Крылья

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

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

это на счет s[4]:

Код


/*теперь мы получили массив, каждая из четырех частей которого упорядочена методом подсчета, теперь надо упорядочить весь массив, для этого используется способ слияния лент*/
    for(i=0;i<4;i++)//инициализация счетчиков
        s[i]=i*kolvo_strok/4;

MJBuster

Дата 8.9.2012, 21:08 (ссылка)

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

Загрузка ...

Новичок

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

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

А немного по подробнее на счёт этого можно?
Буду очень благодарен)

NadezdaT

Дата 25.9.2012, 18:29 (ссылка)

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

Загрузка ...

Крылья

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

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

s - массив из 4 элементов
i - заведено для того чтоб считывать опр эл-ты
получается что этот массив делает:
s[0] = 0*kolvo_strok/4;
s[1] = 1*kolvo_strok/4;
s[2] = 2*kolvo_strok/4;
s[3] = 3*kolvo_strok/4;

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