Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате
Форум программистов > C/C++: Для новичков > Сортировка методом пузырька


Автор: marina12 28.4.2013, 22:12
Здравствуйте! 
Есть код программы,которая сортирует строки методом пузырька 
Код C 

Код
#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 

void bubble_sort(char *array[], int size) 

char *temp; 
int i, j; 

for (i = 0; i < size; i++) 
for (j=0; j < size; j++) 
if (strcmp(array, array[j]) < 0) 

temp = array; 
array = array[j]; 
array[j] = temp; 



void main(void) 

char *values[] = {"AAA", "CCC", "BBB", "EEE", "DDD"}; 
int i; 

bubble_sort(values, 5); 

for (i = 0; i < 5; i++) 
printf("%s ", values ); 


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

Модератор: Не забываем пользоваться кнопочкой "код"

Автор: fish9370 29.4.2013, 09:56
покажи код с открытием файла, и покажи, что не получается с указателями, опиши общую идею как собираешься делать..
если ты не халявщица тебе помогут

Автор: marina12 29.4.2013, 14:30
Открытие файла:
fin=fopen("Input.txt","r");
    if(fin==NULL) 
        fprintf(stderr,"oshibka otkrutiya faila dlya chteniya\n");

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

Автор: Guinness 29.4.2013, 14:42
А чтение, где? И может уже более полный код выложим? По кускам не очень понятно, как Вы собираетесь решать Вашу задачу.

Автор: math64 29.4.2013, 15:41
Поскольку длина файла неизвестна, можете запоминать строки в структуре:
Код

struct ListItem {
  const char* value;
  struct ListItem* next;
};

struct List {
  struct ListItem* first;
  struct ListItem* last;
  int count;
};

struct ListItem * addItemLast(struct List* list, const char* value);
void printList(struct List* list);
const char** listToArray(struct List* list);

После считывания число строк будет известно, и список можно будет преобразовать в массив,
а можно сортировать "на лету", добавляя новую запись не в конец списка, в нужное место в списке.

Автор: fish9370 29.4.2013, 16:38
Цитата(marina12 @  29.4.2013,  14:30 Найти цитируемый пост)
А насчёт указателей думала создать массивы строк и указателей,присвоить адрес строки нужному указателю и в функции сортировки работать уже с указателями. В массиве строк я и запуталась..массив строк это массив из массивов,получается здесь используем указатель на указатель?


идея правильная, но прежде чем приступать к реализации необходимо прояснить несколько вопросов:

1) формат файла (что будет являться разделителем, перенос строки или запятая, возможно запятая и перенос строки: предлагаю перенос строки, для упрощения)
2) хранение данных (где данные будут храниться, самое простое - считать весь файл в строковую переменную, и произвести разделение строки на элементы (split))


Автор: feodorv 29.4.2013, 17:37
Цитата(math64 @  29.4.2013,  16:41 Найти цитируемый пост)
можете запоминать строки в структуре

Какая-то структура просто напрашивается, но...
Цитата(marina12 @  28.4.2013,  23:12 Найти цитируемый пост)
только без использования вектора и структур


По-моему, самое тупое решение - 2 раза прочитать файл. Первый - чтобы выяснить число строк (и аллокировать массив строк соответствующего размера), второй - чтобы непосредственно загружать строки из файла в массив строк. Конечно, при этом нужна осторожность (например, файл между первым чтением и вторым может измениться). 

Такое тупое решение не будет оптимальным, и будет корректно работать только с "настоящими" файлами. Но зато оно позволит существенно упростить код:
Код

unsigned int mSize, mCount, i;
char line[256];
FILE *fin=fopen("Input.txt","r");
char **values = NULL;

if( fin == NULL ) 
{
  fprintf( stderr, "oshibka otkrutiya faila dlya chteniya\n");
  exit( -1 );
}

mSize = 0;
while( fgets( line, sizeof(line), fin) != NULL ) mSize++;
if( mSize == 0 )
{
  fprintf( stderr, "pustoi fail\n");
  fclose( fin );
  exit( -1 );
}

if( (values = (char **) malloc( mSize * sizeof(char *) )) == NULL )
{
  fprintf( stderr, "net pamjati...\n");
  fclose( fin );
  exit( -1 );
}

rewind( fin );
mCount = 0;
while( fgets( line, sizeof(line), fin) != NULL )
  if( mCount < mSize )
  {
    if( (values[mCount] = strdup( line )) == NULL )
      fprintf( stderr, "Nu nikakoj pamjati ne hvataet na vash fail!\n");
    else
      mCount++;
  }

fclose( fin );
bubble_sort( values, mCount); 

for( i = 0; i < mCount; i++) printf( "%d: %s", i, values[i]); 


ЗЫ Посмотрите внимательно:
Цитата(marina12 @  28.4.2013,  23:12 Найти цитируемый пост)
void bubble_sort(char *array[], int size) 

char *temp; 
int i, j; 

for (i = 0; i < size; i++) 
for (j=0; j < size; j++) 
if (strcmp(array[ i ], array[j]) < 0) 

temp = array[ i ]
array[ i ] = array[j]; 
array[j] = temp; 



Автор: fish9370 29.4.2013, 17:56
Цитата(feodorv @  29.4.2013,  17:37 Найти цитируемый пост)
По-моему, самое тупое решение - 2 раза прочитать файл


тогда можно проще и надежнее:

1) выяснить размер файла,
2) выделить память под весь файл + 1
3) произвести над ним split, получив масив строк
4) вызвать функцию сортировки


Автор: feodorv 29.4.2013, 18:05
Цитата(fish9370 @  29.4.2013,  18:56 Найти цитируемый пост)
1) выяснить размер файла,
2) выделить память под весь файл + 1
3) произвести над ним split, получив масив строк

Вот под это всё так и тянет структуру завести  smile 
Но, честно, не думаю, что выйдет проще...

Автор: fish9370 29.4.2013, 18:15


Цитата(feodorv @  29.4.2013,  18:05 Найти цитируемый пост)

Вот под это всё так и тянет структуру завести 
Но, честно, не думаю, что выйдет проще...


можно без структур обойтись в упрощенном варианте, 
тут вся загвоздка в разделении, но такую функцию я как раз тут и приводил..

Автор: marina12 29.4.2013, 21:39
Всем большое спасибо!
Посмотрите пожалуйста теперь, в правильном ли месте выделена память под массивы, а то компилятор на это жалуется, но сортирует вроде бы правильно...
Код


#include "stdafx.h"
#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 
void bubble_sort(char *array[], int size) 

    char *temp; int i,j; 
    for(i=0;i-size;i++) 
        for(j=0;j-size;j++) 
            if(strcmp(array[ i ],array[j]) < 0) 
                temp=array[ i ],
                array[ i ]=array[j],
                array[j]=temp; 

int main(void) 

    char *m,**v,t=0,p; 
    int j,s=0,k,l; 
    FILE* fin; 
    fin=fopen("Input.txt","rb");
    if(fin==NULL) 
        fprintf(stderr,"oshibka otkrutiya faila dlya chteniya\n");
    while (!feof(in)) 
        p=t,
        t=fgetc(in),
        s++; 
    fclose (fin);
    if(p!=10) 
        s+=2; 
    m=(char*)malloc(s);
     fin=fopen("input.txt", "rb"); 
    for(j=0;j < s-1;m[j++]=fgetc(in)); 
    fclose(fin);
    for(m[s-3]=13,m[s-2]=10,m[s-1]=k=j=0;j < s;) 
        if(m[j++]==13) 
            k++; 
    v=(char**)malloc(k); 
    for(v[0]=&m[0],m[s-3]=0,l=j=1;l-k;j++) 
        if(m[j]==13) 
            m[j]=0,
            v[l++]=&m[j+2]; 
bubble_sort(v, 5); 
for(j=0;j-5;j++) 
    printf("%s\n",v[j]); 

free(m); 
free(v); 
return 0; 
}

Автор: fish9370 29.4.2013, 22:52
какой страшный код

Автор: Guinness 30.4.2013, 08:34
Это, конечно, круто. Я даже вскрылся пару раз.
Сразу хочу сказать, не хочу обидеть, все мы поначалу ошибались, просто пытаюсь дать советы как лучше исправить, чтобы код был читабельным. 
Дайте переменным нормальные имена, не однобуквенные.
Код

while (!feof(in)) 
        p=t,
        t=fgetc(in),
        s++; 

Здесь видимо нужно использовать fin. Плюс, зачем этот цикл, когда есть чудесные функции fseek и ftell http://www.cplusplus.com/reference/cstdio/ftell/
Код

if(p!=10) 
        s+=2; 

Во-первых, если сравниваете char, то лучше пишите, что это за символ,  а не код из таблицы ascii. Во-вторых, зачем это сравнение? Просто добавьте к размеру файла единицу для '\0'. Все остальное должно считаться.
Код

 for(j=0;j < s-1;m[j++]=fgetc(in));

Вот не нужно так писать. Зачем? Что Вы хотели этим сэкономить? Вроде понятно, что делает этот код, но читабельность падает. И не бойтесь ставить фигурные скобки.
Код

for(j = 0;j < s-1; j++){
    m[j] = fgetc(in);
}

Код

 for(m[s-3]=13,m[s-2]=10,m[s-1]=k=j=0;j < s;) 
        if(m[j++]==13) 
            k++; 

Зачем Вам такой блок инициализации? Вам нужно было только последний символ установить как '\0', остальное должно считываться из файла. Опять же j++ лучше вынести в объявление цикла(не помню как по умному называется). Допустим здесь мы подсчитали количство строк в буфере - это у нас число k. Тогда, что Вы хотели сказать этой строчкой:
Код

v=(char**)malloc(k);

Здесь Вы выделили k байт, v указывает - честно говоря, затрудняюсь даже сказать куда. Вы же хотите в выделенной памяти хранить указатели на начало строк в буфере, так? А где Вы будете хранить размер каждой строки? Надеюсь здесь меня поправят более опытные форумчане. Я же просто перестал понимать как у Вас это работает без ошибок. Если не ошибаюсь размер указателя равен int. И тут вроде бы нужно сделать как-то так:
Код

v=(char**)malloc( sizeof(*v) * k); // вроде как выделяем массив указателей на чар

Если не прав, надеюсь поправят. 

Код

bubble_sort(v, 5); 
for(j=0;j-5;j++) 
    printf("%s\n",v[j]);

Откуда взято число 5? j-5 смотрится очень стремно, j < 5 - это конечно мейнстрим, а мы не ищем легких путей, но лучше все же писать именно так.

Автор: fish9370 30.4.2013, 11:54
спасибо Guinness, надеюсь твои слова будут услышаны

я тут набросал свое видение решения данной задачи, модификация приветствуется:


Код

/*
 *
 * \section copyright Copyright and author
 *
 * Copyright (C) 2008 - 2013, fish9370.
 *
 * \author Oleg Shteinliht <fish9370@fpg.ru>
 *
 */

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h> /* for bool type */
#include <getopt.h>
#include <string.h>
#include <limits.h> /* for LINE_MAX constant */

#define PROGNAME "test program"
#define PROGVERSION "0.0.0.1"

#define V_SIZE 256
char *buffv[V_SIZE];
#define BUFF_SIZE 4096
char buff_1[BUFF_SIZE];
char buff_2[BUFF_SIZE];

#define FILENAME "array.txt"

void va2str(char *str, size_t size, char *fmt, char **buffv) {
        int pos = 0;
        while (*buffv && pos < size)
                pos += snprintf(str + pos, size - pos, fmt, *buffv++);

        str[pos] = '\0';
}

void str_sort_1(char *buffv[], int size, bool asc)
{
        int i, j, imin;
        char *tmp;
        for (i = 0; i < size - 1; i++) {
                for (imin = i, j = i + 1; j < size; j++)
                        if (asc) {
                                if (strcmp(buffv[j], buffv[imin]) < 0)
                                        imin = j;
                        } else
                                if (strcmp(buffv[j], buffv[imin]) > 0)
                                        imin = j;
                tmp = buffv[i];
                buffv[i] = buffv[imin];
                buffv[imin] = tmp;
        }
}

int readfile(char *buff, int buff_size, char *buffv[], int arr_size, const char *filename)
{
        char line[LINE_MAX];
        FILE *f = fopen(filename, "r");
        if (f == NULL)
                return -1;

        int n = 0, offset = 0, len;
        while (fgets(line, sizeof(line), f)) {
                if (n == arr_size - 1 || offset + 1 >= buff_size)
                        break;

                if ((len = strlen(line)) <= 1)
                        continue;

                if (line[len - 1] == '\n')
                        line[len - 1] = '\0';

                buffv[n++] = buff + offset;

                strncpy(buff + offset, line, buff_size - offset - 1);
                offset += len;
                buff[offset + 1] = '\0';
        }

        buffv[n] = NULL;

        fclose(f);
        return n;
}

void usage(const char * const name)
{
        printf("usage:\n%s [options]\n", name);
        printf("options:\n");
        printf("  --help\t\t\tThis help.\n");
        printf("  -V, --version \t\tPrint program version.\n");

        printf("\nreport bugs to <fish9370@fpg.ru>\n");
}

int main(int argc, char *argv[])
{

        static struct option long_options[] = {
                {"help", 0, 0, '?'},
                {"version", 0, 0, 'V'},
                {0, 0, 0, 0}
        };

        int c, index = 0;
        while ((c = getopt_long(argc, argv, "hV", long_options, &index)) != -1) {
                switch (c) {
                case ':':
                        printf("Option -%c requires an operand\n", optopt);
                        usage(argv[0]);
                        goto exit;

                case 'V':
                        printf("%s %s\n", PROGNAME, PROGVERSION);
                        printf("Copyright (C) 2013 ");
                        printf("fish9370\n");
                        printf("This is free software; see the source for copying conditions.  There is NO\n");
                        printf("warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.\n\n");
                        goto exit;

                case '?':
                        /*printf("Unrecognized option: -%c\n", optopt);*/
                        usage(argv[0]);
                        goto exit;
                }

        }

        int n;
        if ((n = readfile(buff_1, BUFF_SIZE, buffv, V_SIZE, FILENAME)) > 0) {
                str_sort_1(buffv, n, true);

                va2str(buff_2, sizeof(buff_2), "%s ", buffv);
                printf("%s\n", buff_2);
        } else
                printf("error opening file\n");

exit:
        return 0;
}



сборка
Код

gcc -Wall -g ./v2.c -o v2



файл array.txt
Код


aaa
123
bbb
432
abc



тестирование
Код

#./v2
123 432 aaa abc bbb


PS прошу прощения за копирайт, но возможно это кому-то будет полезно

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)