Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > C/C++: Общие вопросы > сортировка многопутевым слиянием

Автор: Domain 24.12.2011, 12:03

Всем привет. Есть задача. В  ООН  имеется  полный  перечень  всех  стран,  который  включает  в  себя:  название,
континент,  столицу,  площадь,  численность  населения,  государственный  строй.  Вывести  названия  и
столицы  государств  в  порядке  убывания  плотности  населения.  Применить  многопутевое  двухфазное
естественное сбалансированное слиянеие. Написал следующий код.

#include <iostream>
#include <fstream>
#include <conio.h>
#include <stdlib.h>
#include <stdio.h>
#include <memory.h>
using namespace std;
/* двухфазная сортировка, параметр - имя файла*/
typedef struct item
{
    int key;
};
int vnsort1(char *ff); // фаза разделения серий
int vnsort2(char *a); // фаза слияния

int vnsort1( char *ff )
{
    FILE *A,*B,*C; /* файловые переменные */
    /* файлы "B", "C" в функциях - временные */
    item *a1,*a2; /* для чтения из исходного файла */
    item *pb,*pc; /* признаки записи в файлы разделения */
    a1 = new item;
    a2 = new item;
    pb = new item;
    pc = new item;
    a1->key = 0;
    a2->key = 0;
    pb->key = 0;
    pc->key = 0;

    int p; /* p=1 - признак достижения конца исходного файла */
    while(1)  /* цикл 1, цикл повторения фаз разделения и слияния */
        /* Подготовительные операции */
    {
        if ((A=fopen(ff,"r")) == NULL)
        {
            printf("\n Файл %s не открывается",ff);
            getch();
            return -1;
        }
        if ((B=fopen("B","w")) == NULL)
        {
            printf("\n Файл B не открывается");
            getch();
            return -1;
        }
        if ((C=fopen("C","w")) == NULL)
        {
            printf("\n Файл C не открывается");
            getch();
            return -1;
        }
        p = 0;
        pb->key = 0;
        pc->key = 0;

        if(fread(a1, sizeof (item),1, A) == NULL)
        {
            printf("\n Сортируемый файл - пустой");
            getch();
            return -1;
        }
        else
        {
            fwrite(&a1,sizeof(item),  1, B);
            //fprintf(B, " %d", a1);
            pb->key=1;
        }
        while(1) /* цикл 2, цикл формирования серий в файлах В и С */
        {
            while (1) /* цикл 3, цикл формирования серии в файле В */
            {

                if(fread(a2, sizeof (item),1, A) == NULL)
                {
                    p=1;
                    break; /* выход из цикла 3 */
                }
                else
                {
                    if (a2->key >= a1->key)  /* запишем в серию в файле В */
                    {

                        fwrite(&a2,sizeof(item),  1, B);
                        a1->key=a2->key;
                        pb->key=1;
                        continue;
                    }
                    else /* запишем первую запись новой серии в файле С */
                    {
                        fwrite(&a2,sizeof(item),  1, C);
                        a1->key=a2->key;
                        pc->key=1;
                        break; /* выход из цикла 3 */
                    }
                }
            }
            if (p)
                break;  /* выход из цикла 2 */
            while (1) /* цикл 4, формирование серии в файле С */
            {

                if(fread(a2, sizeof (item),1, A) == NULL)
                {
                    p=1;
                    break; /* выход из цикла 4 */
                }
                else
                {
                    if (a2->key >= a1->key)  /* запишем в серию в файле С */
                    {
                        fwrite(&a2,sizeof(item),  1, C);
                        a1->key=a2->key;
                        pc->key=1;
                        continue;
                    }
                    else
                    {
                        fwrite(&a2,sizeof(item),  1, B);

                        a1->key=a2->key;
                        pb->key=1;
                        break; /* выход из цикла 4 */
                    }
                }
            }
            if (p)
                break; /* выход из цикла 2 */
        }
        fclose(A);
        fclose(B);
        fclose©;
        if (pb->key && pc->key)  /* исходный файл записан в оба файла разделения */
            vnsort2(ff);  /* вызов функции слияния */
        else
        {
            /* Удаление вспомогательных файлов */
            remove("B");
            remove("C");
            return 0;  /* конец сортировки */
        }
    }
}

int vnsort2(char *a)
{
    bool flag;
    FILE *A,*B,*C; /* файловые переменные */
    item *b1,*b2,*c1,*c2; /* для считывания данных из файлов В и С */
    b1 = new item;
    b2 = new item;
    c1 = new item;
    c2 = new item;
    b1->key = 0;
    b2->key = 0;
    c1->key = 0;
    c2->key = 0;
    int rb,rc; /* коды завершения операции считывания из файлов В и С*/
    /* Подготовительные операции */
    if ((A=fopen(a,"w")) == NULL)
    {
        printf("\n Файл %s не открывается",a);
        getch();
        return -1;
    }
    if ((B=fopen("B","r")) == NULL)
    {
        printf("\n Файл B не открывается");
        getch();
        return -1;
    }
    if ((C=fopen("C","r")) == NULL)
    {
        printf("\n Файл C не открывается");
        getch();
        return -1;
    }
    rb = fread(b2, sizeof (item),1, B);
    rc = fread(c2, sizeof (item),1, C);
    b1->key=b2->key;
    c1->key=c2->key;
    while (1)
    {
        if ( (rb > 0) && (rc <= 0) )    // файл С закончился
        {
            fwrite(&b2,sizeof(item),  1, A);

            while (fread(b2, sizeof (item),1, B))
                fwrite(&b2,sizeof(item),  1, A);
            fclose(A);
            fclose(B);
            fclose©;
            return 0;
        }
        else if ( (rb <= 0) && (rc > 0) ) // файл B закончился
        {
            fwrite(&c2,sizeof(item),  1, A);
            while (fread(c2, sizeof (item),1, C))
                fwrite(&c2,sizeof(item),  1, A);
            fclose(A);
            fclose(B);
            fclose©;
            return 0;
        }
        else if ( (rb <= 0) && (rc <= 0) ) // оба файла закончились
        {
            fclose(A);
            fclose(B);
            fclose©;
            return 0;
        }

        if ( (b2->key >= b1->key) && (c2->key >= c1->key) ) /* обе сливаемые серии не исчерпаны */
        {
            if (b2->key <= c2->key)
            {
                fwrite(&b2,sizeof(item),  1, A);
                b1->key=b2->key;
                rb = fread(b2, sizeof (item),1, B);

                continue;
            }
            else
            {
                fwrite(&c2,sizeof(item),  1, A);
                c1->key=c2->key;
                rc=fread(c2, sizeof (item),1, C);
                continue;
            }
        }

        if ( (b2->key >= b1->key) && (c2->key < c1->key) ) // серия файла C кончилась
        {
            c1->key = c2->key;
            flag = false;
            do
            {
                fwrite(&b2,sizeof(item),  1, A);

                b1->key = b2->key;
                rb=fread(b2, sizeof (item),1, B);
                if( rb <= 0 )
                {
                    flag = true;
                    break;
                }
                if( b2->key < b1->key )
                {
                    b1->key = b2->key;
                    flag = true;
                    break;
                }
                if ( flag == true )
                    break;
            }
            while(1);
            if( flag == true )
                continue;
        }
        if ( (b2->key < b1->key) && (c2->key >= c1->key) ) // серия файла B кончилась
        {
            b1->key = b2->key;
            flag = false;
            do
            {
                fwrite(&c2,sizeof(item),  1, A);

                c1->key = c2->key;
                rc=fread(c2, sizeof (item),1, C);
                if( rc <= 0 )
                {
                    flag = true;
                    break;
                }
                if( c2->key < c1->key )
                {
                    c1->key = c2->key;
                    flag = true;
                    break;
                }
                if ( flag == true )
                    break;
            }
            while (1);
            if( flag == true )
                continue;
        }

    }
}
void in()
{
    FILE * file;
    file = fopen("test.dat", "wb");
    item *items = new item[10];

    items[0].key = 10;
    items[1].key = 4;
    items[2].key = 2;

    fwrite(&items[0],sizeof(item),  1, file);
    fwrite(&items[1],sizeof(item),  1, file);
    fwrite(&items[2],sizeof(item),  1, file);

    fclose(file);
}
void out ()
{
    FILE * file;
    file = fopen("test.dat", "rb");
    item *it = new item;
    int i;
    while (i=fread(it, sizeof (item),1, file))
    {
        cout<<"\nkey: "<<it->key;
    }
    cout<<"\n";
    fclose(file);
}
int main()
{

    in();
    out();
    vnsort1("test.dat");
    out();
    cin.get();
    return 0;
}

Выполнение программы дает следующий  результат(прикрепил фото). Никак не могу понять в чем же дело. Почему выводит такие значение.