2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Qsort
Сообщение30.11.2013, 20:59 


20/10/12
235
Добрый вечер, уважаемые участники форума! Возможно я уже всех достал со своей записной книжкой, но все таки :D
Работает уже все, что я хотел, но qsort сортирует данные как-то не так. Укажите, где не так, пожалуйста. Собственно код, полистать.
код: [ скачать ] [ спрятать ]
Используется синтаксис C++
#include <stdio.h>
#include <ctype.h>
#include <string.h>
#define SIZE 200
#define BUFF 10000
#define MODBUFFER 10
/*Записная книга*/
int modecorrect(char *str); /*Прототипы*/ /*Проверка упр. строки*/
void getdata(unsigned char *field, FILE *file); /*Получение данных формы*/
unsigned int fillStruct(FILE *file, struct person bigArray[], unsigned int arraySize);
int qsort(struct person *left, int allnumber, int (*compare)(void *A, void *B));
int compare(char p[], char q[]);
/*заполнение структуры из файла*/
struct person{                            /*Структура записи*/
  unsigned char name[12];
  unsigned char surname[12];
  unsigned char number[20];
};
int main(void)
{
FILE *MyBook;
size_t i, count; //for structure
unsigned int Size = 200;
struct person NewData;
struct person Contacts[SIZE]; /*Массив структур*/
unsigned char *out = malloc(BUFF * sizeof(unsigned char));
/*указатель в файле при выводе и сортировке*/
unsigned char *pname    = NewData.name;     /*используются в первичном заполнении*/      
unsigned char *psurname = NewData.surname;
unsigned char *pnumber  = NewData.number;
unsigned char *mode     = malloc(MODBUFFER * sizeof(unsigned char)); /* Read or Add */
unsigned char *answer   = malloc( 4 * sizeof(unsigned char));        /* YES / NO */
printf("MyBook 1.0\nEnglish language is used(!) \nChoose your mode:");
while(1){ //// !!!!!Начало общего зацикливания
printf("\nInput \"Read\" or \"Add\"\n");
gets(mode);
printf("\n");
if(!strcmp(mode,"Add")) /*Режим добавления*/
{
if((MyBook = fopen("MyBook.txt", "a+")) == NULL)//
printf("Writing MyBook.txt error");

printf("Please, input new data\nto stop press <Enter>\n");
while(1){//////////////////
printf("Name: ");
 getdata(pname, MyBook);
if(!strcmp(pname, ""))
 break;
fprintf(MyBook, " ");

printf("Surname: ");
 getdata(psurname, MyBook);
fprintf(MyBook, " ");

printf("Number: ");
 getdata(pnumber, MyBook);
fprintf(MyBook, "\n");
}//////////////////////////
fclose(MyBook);
}
/* Режим чтения и сортировки */
if(!strcmp(mode,"Read"))
{
if((MyBook = fopen("MyBook.txt", "r")) == NULL)
printf("Reading MyBook.txt error");
do{
 fscanf(MyBook, "%c" , out);
 putchar(*out);
}while(!feof(MyBook));
do{
 printf("\n Alphabet sort? Input \"Yes\" or \"No\" ");
 gets(answer);
}while(strcmp(answer, "Yes") && strcmp(answer, "No"));

if(!strcmp(answer, "Yes"))
{
        rewind(MyBook);
    count = fillStruct(MyBook, Contacts, SIZE);
        //--------------------------------Q_SORT------------------------------------------//
    qsort(Contacts, count , compare);
        //--------------------------------------------------------------------------------//
        for (i = 0; i < count; ++i)                // вывод отсортированной структуры
         printf("%s %s %s\n", Contacts[i].name, Contacts[i].surname, Contacts[i].number );
}
fclose(MyBook);
}
} ////!!!!
return 0;
}
/////////////////////////////////////////////////////////////////////////
int modecorrect(char *str)  /* small functions */
{
if(!strcmp(str, "Add") || !strcmp(str, "Read"))
 return 1;
return 0;
}
/////////////////////////////////////////////////////////////////////////
void getdata(unsigned char *field, FILE *file)
{
gets(field), fputs(field, file);
}
////////////////////// Сортировка по алфавиту  //////////////////////////
int qsort(struct person *left, int allnumber, int (*compare)(void *A, void *B))
{
        struct person *last, *right = left + allnumber - 1, *i;
        if (left >= right)
          return 1;
        if (!swap(left, left + (right-left)/2))
          return 0;

        last = left;
        for (i = left + 1; i <= right; ++i)
        {      
          if (compare(i, left))
                if (!swap(++last, i))
                  return 0;
        }
        if (!swap(left, last))
          return 0;

        qsort(left, last-left, compare);
        qsort(last+1, right-last, compare);
        return 1;
}
//........................................................//
int swap (struct person * A, struct person * B ) //меняет местами указатели на структурные переменные
{
  struct person *temp;
  if ((temp = (struct person *) malloc(sizeof(struct person))) == NULL)
        return 0;
  *temp = *A;
  *A = *B;
  *B = *temp;

  free(temp);  
  return 1;
}
/////////////////////// Заполнение массива структур //////////////////////
unsigned int fillStruct(FILE *file, struct person bigArray[], unsigned int arraySize)
{
    unsigned int index = 0;
    while((index < arraySize) && !feof(file))
        {
        fscanf(file,"%11s %11s %19s\n", bigArray[index].name, bigArray[index].surname, bigArray[index].number);
                ++index;
    }
    return index;
}
///////////////////////////Сравнение////////////////////////////// WORK
int compare(struct person *p, struct person *q)    //(p<q)? Сравнение двух строк
{
  return strcoll(p->name, q->name);
}
 

Сам Qsort и compare(ну и swap заодно):
Код:
int swap (struct person * A, struct person * B ) //меняет местами указатели на структурные переменные
{
  struct person *temp;
  if ((temp = (struct person *) malloc(sizeof(struct person))) == NULL)
        return 0;
  *temp = *A;
  *A = *B;
  *B = *temp;

  free(temp); 
  return 1;
}

int qsort(struct person *left, int allnumber, int (*compare)(void *A, void *B))
{
        struct person *last, *right = left + allnumber - 1, *i;
        if (left >= right)
          return 1;
        if (!swap(left, left + (right-left)/2))
          return 0;

        last = left;
        for (i = left + 1; i <= right; ++i)
        {       
          if (compare(i, left))
                if (!swap(++last, i))
                  return 0;
        }
        if (!swap(left, last))
          return 0;

        qsort(left, last-left, compare);
        qsort(last+1, right-last, compare);
        return 1;
}

int compare(struct person *p, struct person *q)    //(p<q)? Сравнение двух строк
{
  return strcoll(p->name, q->name);
}


Работа идет с массивом структур, сортироваться должно в алфавитном порядке. Записи берутся из файла.
PS В идеале должно сортировать по любому полю записи, поэтому я заморочился с указателем на функцию.

 Профиль  
                  
 
 Re: Qsort
Сообщение01.12.2013, 01:25 


24/05/09

2054
А там, где примерно "не так", вставьте printf с сомнительными переменными. И вы увидите, как минимум, ошибка до "printf" или после . Это называется "отладка" Сложно?

 Профиль  
                  
 
 Re: Qsort
Сообщение01.12.2013, 05:17 
Заслуженный участник


09/09/10
3729
Alexu007 в сообщении #794755 писал(а):
Это называется "отладка"

"Трассировка". Программа нашпиговывается printf'ами/fprintf'ами/еще каким выводом на каждый чих, затем запускается, валится, после чего программист вдумчиво читает протокол трассировки (trace log), сопоставляя его с исходным кодом. Нестареющая техника.

 Профиль  
                  
 
 Re: Qsort
Сообщение01.12.2013, 07:22 
Заслуженный участник


04/05/09
4589
Код:
          if (compare(i, left))

Как вы думаете, что проверяет это условие?

Ну и вообще, программа называется qsort, подразумевая алгоритм quicksort - быстрая сортировка, а реализовано непонятно что.

 Профиль  
                  
 
 Re: Qsort
Сообщение01.12.2013, 10:09 


24/05/09

2054
Joker_vD в сообщении #794787 писал(а):
"Трассировка". Программа нашпиговывается printf'ами/fprintf'ами/еще каким выводом на каждый чих, затем запускается, валится, после чего программист вдумчиво читает протокол трассировки (trace log), сопоставляя его с исходным кодом. Нестареющая техника.

printf() в комплекте с getch() - тогда программа останавливается и выдаёт порцию данных. Можна спокойно подумать. Ну и не всю программу ессно нашпиговывать (всю то зачем???), а проблемные по мнению программиста места. Как-то с встроенными отладчиками у меня сразу не заладилось...

(Оффтоп)

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

 Профиль  
                  
 
 Re: Qsort
Сообщение01.12.2013, 18:53 
Заслуженный участник


09/09/10
3729

(Оффтоп)

Alexu007 в сообщении #794814 писал(а):
printf() в комплекте с getch() - тогда программа останавливается и выдаёт порцию данных. Можна спокойно подумать.

Пока вы не начинаете отлаживать сетевые программы. Если вы вынуждены общаться с кем-то, у кого внутри жестко закодированы 30–60-секундные таймауты, паузы во время выполнения практически неотличимы от hangup(...); exit(0);.

 Профиль  
                  
 
 Re: Qsort
Сообщение01.12.2013, 22:15 


05/09/12
2587

(Оффтоп)

А еще забавнее применять трассировку (в народе - отладочную печать) при отладке систем реального времени. Там система может просто не успевать передать нужное количество символов за ограниченный временной интервал и свалиться, не успев начать следующую итерацию.

 Профиль  
                  
 
 Re: Qsort
Сообщение02.12.2013, 00:15 
Заслуженный участник


09/09/10
3729

(Оффтоп)

Ну, системы реального времени — это по-хорошему вообще отдельная история и дисциплина программирования. Ни один высокоуровневый язык, строго говоря, не гарантирует, что при компиляции в программу не будут в произвольных местах вставлены sleep(1000); — "время выполнения" вообще лежит вне их семантики.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 8 ] 

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group