VPF::Сортировка методом пузырька - Форум программистов

marina12

Дата 28.4.2013, 22:12 (ссылка)

(голосов:1)

Загрузка ...

Новичок

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

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

Здравствуйте!
Есть код программы,которая сортирует строки методом пузырька
Код 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)(только без использования вектора и структур). С открытием файла все понятно, а вот дальше я начала путаться в указателях...

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

Это сообщение отредактировал(а) bsa - 1.5.2013, 15:11

fish9370

Дата 29.4.2013, 09:56 (ссылка)

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

Загрузка ...

Опытный

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

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

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

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

undefined

marina12

Дата 29.4.2013, 14:30 (ссылка)

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

Загрузка ...

Новичок

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

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

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

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

Guinness

Дата 29.4.2013, 14:42 (ссылка)

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

Загрузка ...

Опытный

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

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

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

math64

Дата 29.4.2013, 15:41 (ссылка)

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

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 2505
Регистрация: 12.4.2007

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

Поскольку длина файла неизвестна, можете запоминать строки в структуре:

Код


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 (ссылка)

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

Загрузка ...

Опытный

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

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

Цитата(marina12 @ 29.4.2013, 14:30

)

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

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

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

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

undefined

feodorv

Дата 29.4.2013, 17:37 (ссылка)

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

Загрузка ...

Эксперт

Профиль
Группа: Комодератор
Сообщений: 2214
Регистрация: 30.7.2011

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

Цитата(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;
}
}

Это сообщение отредактировал(а) feodorv - 29.4.2013, 17:41

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

Напильник, велосипед, грабли и костыли - основные инструменты программиста...

fish9370

Дата 29.4.2013, 17:56 (ссылка)

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

Загрузка ...

Опытный

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

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

Цитата(feodorv @ 29.4.2013, 17:37

)

По-моему, самое тупое решение - 2 раза прочитать файл

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

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

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

undefined

feodorv

Дата 29.4.2013, 18:05 (ссылка)

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

Загрузка ...

Эксперт

Профиль
Группа: Комодератор
Сообщений: 2214
Регистрация: 30.7.2011

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

Цитата(fish9370 @ 29.4.2013, 18:56

)

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

Вот под это всё так и тянет структуру завести smile

Но, честно, не думаю, что выйдет проще...

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

Напильник, велосипед, грабли и костыли - основные инструменты программиста...

fish9370

Дата 29.4.2013, 18:15 (ссылка)

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

Загрузка ...

Опытный

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

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

Цитата(feodorv @ 29.4.2013, 18:05

)

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

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

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

undefined

marina12

Дата 29.4.2013, 21:39 (ссылка)

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

Загрузка ...

Новичок

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

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

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

Код



#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; 
}

Это сообщение отредактировал(а) marina12 - 29.4.2013, 21:40

fish9370

Дата 29.4.2013, 22:52 (ссылка)

(голосов:1)

Загрузка ...

Опытный

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

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

какой страшный код

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

undefined

Guinness

Дата 30.4.2013, 08:34 (ссылка)

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

Загрузка ...

Опытный

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

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

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

Код


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 - это конечно мейнстрим, а мы не ищем легких путей, но лучше все же писать именно так.

Это сообщение отредактировал(а) Guinness - 30.4.2013, 08:35

fish9370

Дата 30.4.2013, 11:54 (ссылка)

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

Загрузка ...

Опытный

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

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

спасибо Guinness, надеюсь твои слова будут услышаны

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

Код


/*
 *
 * \section copyright Copyright and author
 *
 * Copyright (C) 2008 - 2013, fish9370.
 *
 * \author Oleg Shteinliht <[email protected]>
 *
 */

#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 <[email protected]>\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 прошу прощения за копирайт, но возможно это кому-то будет полезно

Это сообщение отредактировал(а) fish9370 - 30.4.2013, 12:34

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

undefined

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