VPF::Три внешних сортировки - Форум программистов

Coderr

Дата 20.4.2008, 18:55 (ссылка)

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

Загрузка ...

Бывалый

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

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

Доброго времени суток, винградовцы!
Появилось задание, которое я никак не могу "вкурить" и написать.
Суть в том, что надо написать программу-реализацию трёх типов внешней сортировки, а именно:
1) Двухфазная сортировка простым слиянием
2) Однофазная сортировка простым слиянием
3) Сортировка естественным слиянием.

В поиске про внешнюю сортировку нашёл только в подфоруме паскаля, но там совершенно не то...
Я тут накатал приблизительное начало. Кстати сказать, прогу надо сделать под консоль. Вот, собсно, сам код:

Код


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

/*------ Begin PROTOTYPES ------*/
void AnyKey();
void PrintElement(int, int);
void Menu();
void DivideFile(int);
int PrintFile(char *);
void FileMerge();
void FillFile();
void TwoPhase(int);
void MonoPhase();
void NatureMerge();
/*------- End PROTOTYPES -------*/

/*------------------------- BEGIN OTHER FUNCTIONS --------------------------*/
void AnyKey()
{
 printf("\n\nPress any key to continue...");
 getch();
}

void PrintElement(int element, int color)
{
 textcolor(color);
 cprintf("%d ", element);
 textcolor(LIGHTGRAY);
}

void Menu()
{
 int c;

 do
  {
   clrscr();

   printf("1. Fill file\n"
      "2. 2-phase sort\n"
      "3. 1-phase sort\n"
      "4. Nature sort\n"
      "0. Exit\n");
   printf("Your choice: ");
   scanf("%d", &c);

   switch (c)
    {
     case 1: FillFile();             break;
     case 2: TwoPhase(1);            break;
     case 3: MonoPhase();            break;
     case 4: NatureMerge();          break;
    }
  }
 while (c != 0);
}
/*-------------------------- END OTHER FUNCTIONS ---------------------------*/

/*------------------------- BEGIN FILE OPERATIONS --------------------------*/
void DivideFile(int length)
{
 FILE *src;
 FILE *dest1;
 FILE *dest2;
 int tmp;
 int cnt=1;
 int f=0;

 src = fopen("source.txt", "r");
 dest1 = fopen("temp1.txt", "w");
 dest2 = fopen("temp2.txt", "w");

 fscanf(src, "%d", &tmp);
 while (tmp != EOF)
  {
   if (f == 0)
    fprintf(dest1, "%d ", tmp);
   else
    fprintf(dest2, "%d ", tmp);

   cnt++;
   if (cnt > length)
    {
     cnt = 1;
     f = !f;
    }

   fscanf(src, "%d", &tmp);
  }

 fclose(src);
 fclose(dest1);
 fclose(dest2);
}

int PrintFile(char *FileName)
{
 FILE *file;
 int f=0;
 int tmp;

 file = fopen(FileName, "r");

 fscanf(file, "%d", &tmp);
 while (tmp != EOF)
  {
   f = 1;

   printf("%d ", tmp);
   fscanf(file, "%d", &tmp);
  }

 fclose(file);

 return f;
}

void FileMerge()
{
 FILE *src;
 FILE *dest1;
 FILE *dest2;

 src = fopen("source.txt", "w");
 dest1 = fopen("temp1.txt", "r");
 dest2 = fopen("temp2.txt", "r");



 fclose(src);
 fclose(dest1);
 fclose(dest2);
}

void FillFile()
{
 FILE *file;
 int tmp;
 int i, n;

 file = fopen("source.txt", "w");

 clrscr();
 printf("Input count of elements: ");
 scanf("%d", &n);

 printf("Input elements:\n");
 for(i=0; i<n; i++)
  {
   scanf("%d", &tmp);
   fprintf(file, "%d ", tmp);
  }

 fclose(file);
}
/*-------------------------- END FILE OPERATIONS ---------------------------*/

/*----------------------------- BEGIN SORTS --------------------------------*/
void TwoPhase(int length)
{
 clrscr();

 DivideFile(length);
 printf("Part 1: ");
 PrintFile("temp1.txt");
 printf("\nPart 2: ");
 PrintFile("temp2.txt");
 printf("\n\n");

 TwoPhase(length*2);
}

void MonoPhase()
{

}

void NatureMerge()
{

}
/*------------------------------ END SORTS ---------------------------------*/

void main()
{
 Menu();
}

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

Кодинг - это стиль жизни!

Coderr

Дата 20.4.2008, 22:31 (ссылка)

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

Загрузка ...

Бывалый

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

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

Хорошо. Давайте по-порядку.
У меня возникают проблемы в этой процедуре:

Код


void DivideFile(int length)
{
 FILE *src;
 FILE *dest1;
 FILE *dest2;
 int tmp;
 int cnt=1;
 int f=0;
 src = fopen("source.txt", "r");
 dest1 = fopen("temp1.txt", "w");
 dest2 = fopen("temp2.txt", "w");
 fscanf(src, "%d", &tmp);
 while (tmp != EOF)
  {
   if (f == 0)
    fprintf(dest1, "%d ", tmp);
   else
    fprintf(dest2, "%d ", tmp);
   cnt++;
   if (cnt > length)
    {
     cnt = 1;
     f = !f;
    }
   fscanf(src, "%d", &tmp);
  }
 fclose(src);
 fclose(dest1);
 fclose(dest2);
}

Она зацикливается из-за условия while (tmp != EOF). А считываю я элементы, как видите, fscanf'ом.
Подскажите, как мне отследить конец файла в моём случае?

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

Кодинг - это стиль жизни!

Coderr

Дата 21.4.2008, 19:45 (ссылка)

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

Загрузка ...

Бывалый

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

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

Нашёл замечательную функцию feof. Теперь могу спокойно отследить конец.

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

Кодинг - это стиль жизни!

sgrey

Дата 21.4.2008, 23:11 (ссылка)

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

Загрузка ...

Опытный

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

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

http://cis.stvincent.edu/html/tutorials/sw...rt/extsort.html - тут по-моему всё что тебе надо. там есть два файлика в тексте с алгоритмами внешних сортировок

Coderr

Дата 22.4.2008, 18:51 (ссылка)

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

Загрузка ...

Бывалый

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

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

Не... Там реализован только одна сортировка, и то я не понял какая... smile

Жалко в википедии нет... :(

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

Кодинг - это стиль жизни!

Coderr

Дата 22.4.2008, 21:19 (ссылка)

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

Загрузка ...

Бывалый

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

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

О, великие ГУРУ кодинга! Поможите бедному студенту! Я горю. В четверг уже сдавать...
Я две недели мозги ломал, но так и не смог написать... smile

Гугл выдаёт одно и тоже и всё не то...
ПОМОГИТЕ!

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

Кодинг - это стиль жизни!

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