Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 13, средняя оценка - 4.77
TGrey[WoLf]
39 / 39 / 1
Регистрация: 14.09.2008
Сообщений: 685
#1

Алгоритм сортировки - C++

17.01.2009, 15:05. Просмотров 1544. Ответов 9
Метки нет (Все метки)

Здравствуйте, подскажите пожалуйста какой алгоритм можно использовать при решении такой задачи:
Дана строка char * из букв и цифр разделенных пробелами, нужно отсортировать слова в алфавитном порядке при этом цифры не учитывать.
К примеру
p2og3oda 2bu7la h9oros6hey6
Должно получится
2bu7la h9oros6hey6 p2og3oda
Код не вылаживаю т.к. не придумал, как делать(
Прошу писать не код, а алгоритм.
Спасибо.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Фенрир
42 / 38 / 2
Регистрация: 05.01.2009
Сообщений: 394
17.01.2009, 15:20     Алгоритм сортировки #2
дял начала раздели предложение на лексемы используя strtok например, и сохрани слова в строковом массиве.
затем напиши функцию сравнения слов, чтото вроде
C++
1
2
3
4
5
int Compare (const char* str1, const char* str2)
{    while(isdigit(*str1)) {str1++;}
      while (isdigit(*str2)) {str2++;}
      return (*str1>*str2); // тоесть настрой указаетли на первые буквы и сравни их
 }
Затем используй алгоритм сортировки, который будет использовать функцию сравнения....как-то так
TGrey[WoLf]
39 / 39 / 1
Регистрация: 14.09.2008
Сообщений: 685
17.01.2009, 17:03  [ТС]     Алгоритм сортировки #3
Через 1 место вышел у меня такой код))) Он сортирует слова по алфавиту, но учитывает только первые буквы + не учитывает цифры, доделаю.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
    char a[50], tmp[20]; 
    strcpy(a,phrase);
    int c=0, cw=0;
 
    for(int l=1; l < strlen(phrase); l++)
        if( phrase[l] == ' ' && phrase[l+1] != ' ' && phrase[l+1] != '\0' )
            cw++;
 
    ++cw;
    cout<<"Words:"<<cw<<endl;
    char **words;
    words = new char*[cw];
 
    for(int i = 0; i < (cw); i++)
        words[i] = new char[20];
 
 
 
    char *ans = strtok(a," ");
    while( ans != NULL )
    {
        cout<<ans<<endl;
        strcpy(words[c++],ans);
        ans = strtok(NULL," ");
    }
 
    for(i=0; i < cw-1; i++)
    {
        for(int j=i+1; j < cw; j++)
        if(words[i][0] > words[j][0])
        {
            strcpy(tmp, words[i]);
            strcpy(words[i],words[j]);
            strcpy(words[j],tmp);
        }
    }
 
    for(i=0; i < cw; i++)
        cout<<words[i]<<" ";
    cout<<endl;
 
 
 
    for(i = 0; i < cw; i++)
        delete [] words[i];
    delete []words;
В результате:
den ochen bul aoroshim
<=>
aoroshim bul den ochen
Фенрир
42 / 38 / 2
Регистрация: 05.01.2009
Сообщений: 394
17.01.2009, 17:21     Алгоритм сортировки #4
C++
1
2
3
4
// вместо
if(words[i][0] > words[j][0])
// используй... функцию не проверял....наверно в не кажый раз нужно указатель //устанавливать в начало
if (Compare(words[i], words[j]))
TGrey[WoLf]
39 / 39 / 1
Регистрация: 14.09.2008
Сообщений: 685
17.01.2009, 20:16  [ТС]     Алгоритм сортировки #5
Что-то я не нашел прототипа этой функции
Фенрир
42 / 38 / 2
Регистрация: 05.01.2009
Сообщений: 394
17.01.2009, 20:51     Алгоритм сортировки #6
C++
1
2
3
4
5
6
7
8
9
  
int Compare (const char* str1, const char* str2)   
{    
     char* a = &str1[0];
     char* b = &str2[0];
     while(isdigit(*a)) a++;   
      while (isdigit(*b)) b++;
      return (*a>*b); // тоесть настрой указаетли на первые буквы и сравни их   
 }
TGrey[WoLf]
39 / 39 / 1
Регистрация: 14.09.2008
Сообщений: 685
17.01.2009, 21:28  [ТС]     Алгоритм сортировки #7
Что-то я не пойму этот код. Зачем в цикле увеличивать указатели? Я же только по первой букве сравниваю. и тогда по моему проще сравнить моим способом чем делать эту функцию. Или я что-то недопонял?
accept
4819 / 3239 / 165
Регистрация: 10.12.2008
Сообщений: 10,682
17.01.2009, 21:36     Алгоритм сортировки #8
p2og3oda 2bu7la h9oros6hey6
это три структуры такого вида

Код
struct {
    char *input;
    char *modif;
};
в input кладётся само слово, а в modif выборка символов алфавита
потом проводится обычная пузырьковая сортировка со strcmp всех структур по полю modif а затем сохранение полей input из получившегося порядка
Фенрир
42 / 38 / 2
Регистрация: 05.01.2009
Сообщений: 394
17.01.2009, 21:40     Алгоритм сортировки #9
ты ж сравниваешь имено 1е буквы
тоесть например
2222222bbbb надо поменять местами c 2222aaaaa поэтому при сравнении надо добраться до букв игнорируя цифры..так??

Добавлено через 1 минуту 9 секунд
или вариант который accept предложил.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
18.01.2009, 01:12     Алгоритм сортировки
Еще ссылки по теме:

Алгоритм сортировки C++
Неизвестный алгоритм сортировки C++
Алгоритм быстрой сортировки C++
Не алгоритм быстрой сортировки C++
C++ Алгоритм сортировки вставками

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
TGrey[WoLf]
39 / 39 / 1
Регистрация: 14.09.2008
Сообщений: 685
18.01.2009, 01:12  [ТС]     Алгоритм сортировки #10
Ааа извиняюсь, я перепутал значения isdigit я подумал, что она возвращает истину если это Буква, а не цифра. Теперь ясно. Да спасибо за советы. Доделаю выложу, мб кому когда-нибудь понадобится.
Yandex
Объявления
18.01.2009, 01:12     Алгоритм сортировки
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru