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

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

Форум программистов > C/C++: Для новичков > Сортировка строк по алфавиту. Структуры.

Автор: Kruger2 14.7.2011, 16:48

Известная задача, в интернете есть много вариантов, но я не могу нормально реализовать сортировку по алфавиту.
Вот условие:

1.    Описать структуру с именем ТRAIN, содержащую следующие поля:
•    NAZN - название пункта назначения;
•    NUMR - номер поезда;
•    ТIМЕ - время отправления.
2.    Написать программу, выполняющую следующие действия:
•    ввод с клавиатуры данных в массив RASР, состоящий из восьми элемен¬тов типа ТRAIN; записи должны быть размещены в алфавитном порядке по названиям пунктов назначения;
•    вывод на экран информации о поездах, отправляющихся после введенного с клавиатуры времени;
•    если таких поездов нет, выдать на дисплей соответствующее сообщение.

Вот задача:

Код


#include <stdio.h>
#include <string.h>
struct TRAIN{
       char NAZN[20];
       unsigned NUMR;
       char TIME[6];
       } RASP[8],T;
       
main()
{
  int i, j, k=0; 
  unsigned Num; 
  char Name[20];

/*Ввод и считывание информации*/
   for(i=0; i<8; i++)
   {
    printf("\nName of the place? "); 
    scanf("%s", &RASP[i].NAZN); 
     
     if(strlen(RASP [i].NAZN)==0)
          break;
   
    printf("Train number? ");
    scanf("%u",&RASP[i].NUMR);
    
    printf("Departure time? "); 
    scanf("%s",&RASP[i].TIME);
    
     k++;
     };
     
     /*Тут должна быть сортировка. Тут и нужна помощь:)*/
   
       /*Вывод результатов*/
        printf("\nTrains:\n"); 
         for(i=0; i<k; i++)
         printf("%-19s - #%3u - %7s\n",RASP[i].NAZN,RASP[i].NUMR,RASP[i].TIME);
        while(1)
        {
           printf("\nTrain number for seach (0 for exit)? "); 
           scanf("%u",&Num); 
           j=0; 
           
            if(!Num)
           break;
           
             for(i=0;i<k;i++)
           if(Num==RASP[i].NUMR)
             {
             printf("\nName of the place: %s \nTrain number: %u \nDeparture time: %s\n\n", 
                     RASP[i].NAZN,RASP[i].NUMR,RASP[i].TIME);
             j=1;
             }; 
             
            
     if(!j)
       printf("No such train!\n"); 
 getchar();}
}

Каким образом создать сортировку? Допустим будут строки:

London
Astana
Moscow
Kiev

Надо раскидать их по алфавиту, от а к z.

Если рассматривать как двумерный массив, то мне необходимо сравнивать первый элемент 1ой строки с первым элементов 2ой , если он больше, то поднять вверх всю строку и т.д. Но у меня массив NAZN(название города) объявлен как одномерный. У меня вообще нет тут двумерного массива, что бы попробовать пузырьковою конструкцию типа:

Код


for(i=0; i<k; i++)
   for(j=0; j<k; j++)
if (matrix[0][j] < matrix [0] [j+1])
 t=matrix[0][j]
matrix[0][j+1]=matrix [0][j]
matrix [0][j+1]=t

Или в этом случае я зафиксировал вообще нулевой элемент и надо вот так? Но всё равно у меня нет двухмерного массива и я не могу сравнивать именно нулевой элемент каждой строки ((

Код


for(i=0; i<k; i++)
   for(j=0; j<k; j++)
if (matrix[0][j] < matrix [0] [j+1])
 t=matrix[j]
matrix[j+1]=matrix [j]
matrix [j+1]=t

Автор: boostcoder 14.7.2011, 16:53

юзай std::vector и std::sort smile

Автор: Kruger2 14.7.2011, 16:54

boostcoder,
Находил такие примеры, но я как бы не должен их ещё знать на этой стадии, хотя в общих чертах понимаю как работают они smile

Добавлено через 1 минуту и 18 секунд
Хотя нет, вектор не знаю вообще)

Автор: boostcoder 14.7.2011, 16:59

используй http://www.cplusplus.com/reference/clibrary/cstdlib/qsort/. это Си-функция для сортировки.

Автор: Kruger2 14.7.2011, 17:01

Да, только по программе эта задача идет перед функциями и тем более перед указателями smile

Неужели нет вариантов? как отсортировать например по номеру поезда я знаю, а по алфавиту как?)

Автор: boostcoder 14.7.2011, 17:14

Цитата(Kruger2 @ 14.7.2011, 17:01

)

Неужели нет вариантов?

вариантов куча. но это руками все писать придется...

Автор: Kruger2 14.7.2011, 17:15

Тут сортировка происходит в зависимости от номера поезда:

Код


 for(i=0; i<k; i++)
      for(j=0; j<k-i-1; j++)
        if(RASP[i].NUMBER < RASP[j].NUMBER) 
        {
           T= RASP[j];
          RASP[j] = RASP[j+1];
          RASP[j+1]=T;
        }

33
22
44
11

Не совсем понимаю каким образом тут происходит сортировка. Получается, i=строки, j= столбцы? Тогда каким образом строка сравнивается со столбцом О_о

Добавлено через 27 секунд
boostcoder,
Пичалька smile

Автор: borisbn 14.7.2011, 17:57

Kruger2, в твоём одномерном массиве нет ни столбцов ни строк. Есть просто индекс.
Для лучшего понимания распечатай каждый шаг алгоритма (все переменные):

Код


 for(i=0; i<k; i++)
 {
     for(j=0; j<k-i-1; j++)
     {
        printf( "Сравниваю %d и %d элементы\n", i, j );
        printf( "RASP[i].NUMBER = %d, RASP[j].NUMBER = %d\n", RASP[i].NUMBER, RASP[j].NUMBER );
        if(RASP[i].NUMBER < RASP[j].NUMBER) 
        {
           printf( "if(RASP[i].NUMBER < RASP[j].NUMBER). Меняем их местами\n" );
           T= RASP[j];
           RASP[j] = RASP[j+1];
           RASP[j+1]=T;
        }
        printf( "После очередного шага:\n" );
        for ( int tmp = 0; tmp < k; tmp++ )
        {
             printf( "%d ", RASP[ tmp ].NUMBER );
        }
        printf( "\n" );
     }
 }

Автор: Kruger2 14.7.2011, 18:03

Наплевал на всё и сделал как вы и советовали, boostcoder, через strcmp. Никто ведь не запрещает мне наперед учиться? Буду так и говорить smile

Тем более, что функция элементарна

Код


 if(strcmp(RASP[j].NAZN, RASP[j+1].NAZN)>0)
            {
              T=RASP[j];
              RASP[j]=RASP[j+1];
              RASP[j+1]=T    ;                  
            }

Автор: boostcoder 14.7.2011, 18:03

Kruger2, малаца!

Автор: borisbn 14.7.2011, 18:05

Kruger2, вот, посмотри http://forum.vingrad.ru/forum/topic-37776/anchor-entry285335/15.html. Только не бездумно копипасть, а внимательно разбери... Плюс можешь повставлять отладочный вывод, как я тебе показал выше...

Автор: Kruger2 14.7.2011, 18:08

borisbn,
Спасибо, надо убегать, позже обязательно разберу.
boostcoder,
Тоже спасибо за наводку.

Нафлужу ещё пару постов и расставлю плюсы всем smile

Автор: fish9370 16.7.2011, 10:16

вобще, strcmp реализуется довольно легко, не обязательно использовать библиотечную:

Код


int my_strcmp(const char *s1, const char *s2) {
       if(!s1 && s2)
                return -1;

        if(s1 && !s2)
                return 1;

        if(!s1 && !s2)
                return 0;

        for(;*s1 && *s2; s1++, s2++) {
                if(*s1 != *s2) {
                        if(*s1 > *s2)
                                return 1;
                        else
                                return -1;
                }
        }

        if (*s1)
                return 1;

        if (*s2)
                return -1;

        /*  1 - s1 greater then s2   */
        /* -1 - s1 less then s2      */
        /*  0 - s1 and s2 equal      */
        return 0;
}

Автор: volatile 16.7.2011, 11:04

Цитата(fish9370 @ 16.7.2011, 10:16

)

        while(*s1) {
                if(*s1++ != *s2++) {
                        if(*s1 > *s2)
                                return 1;
                        else
                                return -1;
                        break;
                }

Это не просто кривой велосипед, это очень кривой велосипед!
1.

Цитата(fish9370 @ 16.7.2011, 10:16

)

                if(*s1++ != *s2++) {
                        if(*s1 > *s2)
                }

Сначала мы проверили на не равенство *s1 != *s2, а потом сравниваем следующие за ними байты
Автор нужно срочно читать что такое постинкрементация.

Если даже исправим ошибку 1, это еще не все
2.

Цитата(fish9370 @ 16.7.2011, 10:16

)

while(*s1) {

Если s2 длиннее s1, но совпадает по начальным символам, этот код выдаст равенство.
напр:
s1 = "ABC";
s2 = "ABCDEFG";
Эти строки будут равны.

Уважаемые велосипедисты, когда изобретаете очередной велосипед, будьте осторожны!
Не пишите всякой фигни, где в среднем на 2 строчки кода по 3 ошибки!!!

Автор: fish9370 16.7.2011, 15:57

volatile, не нравишься ты мне smile

Автор: boostcoder 16.7.2011, 16:01

я конечно ничего против Си не имею... но когда видишь такой код от сишника, начинаешь задумываться...таки не плюсы виноваты.

Автор: fish9370 16.7.2011, 16:14

Цитата(boostcoder @ 16.7.2011, 16:01

)

но когда видишь такой код от сишника

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

Автор: boostcoder 16.7.2011, 16:16

Цитата(fish9370 @ 16.7.2011, 16:14

)

только не надо делать вид, что вы все никогда не ошибаетесь.

все ошибаются.

смысл в другом...

Автор: fish9370 16.7.2011, 16:17

Цитата(boostcoder @ 16.7.2011, 16:16

)

смысл в другом...

а в чем?

Автор: borisbn 16.7.2011, 16:43

Цитата(boostcoder @ 16.7.2011, 16:01

)

http://www.progz.ru/t134/ (1-й анекдот)

fish9370, вместо того, чтобы спасибо сказать

Цитата(fish9370 @ 16.7.2011, 15:57

)

volatile, не нравишься ты мне

не нравится - не ешь

Автор: fish9370 16.7.2011, 16:52

Цитата(borisbn @ 16.7.2011, 16:43

)

вместо того, чтобы спасибо сказать

сказал бы, если бы он не был таким smile

Автор: volatile 16.7.2011, 17:04

Цитата(fish9370 @ 16.7.2011, 10:16

)

int my_strcmp(const char *s1, const char *s2) {
       if(!s1 && s2)
                return -1;

        if(s1 && !s2)
                return 1;

        if(!s1 && !s2)
                return 0;

        for(;*s1 && *s2; s1++, s2++) {
                if(*s1 != *s2) {
                        if(*s1 > *s2)
                                return 1;
                        else
                                return -1;
                }
        }

        if (*s1)
                return 1;

        if (*s2)
                return -1;

        /*  1 - s1 greater then s2   */
        /* -1 - s1 less then s2      */
        /*  0 - s1 and s2 equal      */
        return 0;
}

Цитата(fish9370 @ 16.7.2011, 16:14

)

. вместо того чтобы сказать, что в коде есть ошибки, типа исправь

И после исправления в коде есть грубые ошибки!
fish9370, типа исправь, может с 3-раза получится.. smile

Автор: fish9370 16.7.2011, 17:24

Цитата(volatile @ 16.7.2011, 17:04

)

И после исправления в коде есть грубые ошибки

присвети меня мистер smile

Автор: Dov 16.7.2011, 17:47

Код

int my_strcmp(const char * s1, const char * s2)
{
    for( ; *s1 && *s2; s1++, s2++)
        if(*s1 != *s2)
            break;
        
    return *s1 - *s2;    
}

Автор: volatile 16.7.2011, 17:52

Цитата(fish9370 @ 16.7.2011, 17:24

)

да, опять не учел постфиксный инкримент.. спасибо мистер

да пожалуйста, только дело не в постфиксном инкрименте, а в том что строки теперь никогда не будут равны.

Цитата(volatile @ 16.7.2011, 17:04

)

        if (*s1)
                return 1;

        if (*s2)
                return -1;

        /*  1 - s1 greater then s2   */
        /* -1 - s1 less then s2      */
        /*  0 - s1 and s2 equal      */
        return 0;
}

Здесь никогда не дойдет до return 0;
!!!

Автор: fish9370 16.7.2011, 17:57

Цитата(volatile @ 16.7.2011, 17:52

)

Здесь никогда не дойдет до return 0;

да вы что? а это почему? smile

Автор: volatile 16.7.2011, 18:01

fish9370, А хотя да. сорри.

Автор: fish9370 16.7.2011, 18:03

мистер

ошибся?
не переживай, я не буду над тобой глумиться..

Автор: volatile 16.7.2011, 18:04

Цитата(Dov @ 16.7.2011, 17:47

)

int my_strcmp(const char * s1, const char * s2)
{
    for( ; *s1 && *s2; s1++, s2++)
        if(*s1 != *s2)
            break;

    return *s1 - *s2;
}

Dov, неплохо, только надо сделать что-то типа return sign(*s1 - *s2);

Автор: fish9370 16.7.2011, 18:05

Dov, классный код, но как же проверки на NULL?

Автор: volatile 16.7.2011, 18:13

Цитата(fish9370 @ 16.7.2011, 18:03

)

не переживай, я не буду над тобой глумиться..

fish9370, я не хотел не над кем глумиться. Я просто хотел сказать что изобретать велосипед дело не хорошее.
Если я вас чем-то обидел, прошу прещения.
Библиотеки создавали не лохи. И не к чему изобретать его снова и снова.
Можно нарваться на большие неприятности.

Автор: boostcoder 16.7.2011, 18:15

volatile, истину говоришь!

Автор: fish9370 16.7.2011, 18:27

Цитата(volatile @ 16.7.2011, 18:13

)

Я просто хотел сказать что изобретать велосипед дело не хорошее

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

что библиотеки создают не лохи, это правда, но часто стандартные функции оборачивают в обертки..

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

Автор: Dov 16.7.2011, 18:38

Цитата(volatile @ 16.7.2011, 18:04

)

Dov, неплохо, только надо сделать что-то типа return sign(*s1 - *s2);

извиняюсь, недопонял...

Цитата(fish9370 @ 16.7.2011, 18:05

)

Dov, классный код, но как же проверки на NULL?

Ну это это же просто пример, а не рабочий вариант. Кому надо, пусть проверяет.

Автор: JackYF 18.7.2011, 22:04

M
JackYF

fish9370 и volatile: будьте спокойнее, не "задевайте" друг друга.

Автор: Masha7 19.7.2011, 13:09

просто примени qsort(). это Си-функция для четкой сортировки.

________________________________________________________________________________________

http://www.avtostrahovanie-russia.ru/http://www.biznes-hroniki.ru/http://www.dorogi-rossii.ru/http://www.stroinay.ru/http://www.tehnoblogger.ru/http://www.neotext09.ru/http://www.h20-serial.ru/http://www.xponika.info/http://www.marketing-blogs.ru/http://mobiletelefons.ru/http://www.greek-serial.ru/http://www.glomerulonefritanet.ru/