VPF::сортировка однобайтовых чисел

frukt

Дата 23.1.2007, 19:12 (ссылка)

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

Загрузка ...

Новичок

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

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

Подскажите пожалуйста как будет выглядеть основная часть кода программы цифровой сортировки однобайтовых чисел. Или у кого-нибудь может есть готовая программа. Вот такое вот задание. Как я понял, преподавателя вообще не интересует вид сортировки.Это на мое усмотрение, ну и на ваше тоже. Хочу еще обратить внимание на то, что в нашем институте приветствуется написание программ на С++, хотя в программе обучения изучение этого языка предусмотренно через год. Вот такой вот маразм. Это я все говорю к тому, что для меня сейчас является доступным понимание программы написанной на С. Но дареному коню в зубы не смотрят, так что помогите чем "могите"!

zkv

Дата 23.1.2007, 19:22 (ссылка)

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

Загрузка ...

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

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

Цитата(frukt @ 23.1.2007, 19:12

)

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

я правда не знаю что такое "цифровая сортировка" smile

Код


#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
    char cArr[] = {1,3,5,8,3,8,4,9,0,3,7}; 

    int length = sizeof(cArr)/sizeof(cArr[0]);

    sort( &cArr[0], &cArr[ length ]);

    for( int i = 0; i < length; ++i )
        cout<<"\n"<<(int)cArr[i];

    cin.get();
}

TeRiX

Дата 23.1.2007, 19:22 (ссылка)

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

Загрузка ...

Новичок

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

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

Посмотри здесь, может поможет

Сортировка_пузырьком

или здесь

Алгоритм сортировки

frukt

Дата 23.1.2007, 19:42 (ссылка)

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

Загрузка ...

Новичок

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

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

Спасибо тебе большое ZKV, но проблема в том, что С++ еще плохо понимаем мною, и все рассуждения строятся на предположении. Естественно, хотелось бы чтобы ты прокомментировал свою программу. Сделай это, если не трудно.

Anikmar

Дата 23.1.2007, 19:44 (ссылка)

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

Загрузка ...

Эксперт

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

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

Цитата(frukt @ 23.1.2007, 19:42

)

Ну это свосем запущено... Ну хоть чуть-чуть какую-нибудь книжечку почитайте... Все равно ведь С++ изучать придется!

zkv

Дата 23.1.2007, 21:36 (ссылка)

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

Загрузка ...

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

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

Цитата(Anikmar @ 23.1.2007, 19:44

)

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

Код


//для ввода/вывода данных
#include <iostream> 
//для использования sort()
#include <algorithm>
//работаем в стандартном пространстве имен
using namespace std;
//точка входа в приложение, правильнее было бы обозвать как нибудь так:
//int main(int argv, char **argc)
int main()
{
    //объявление с инициализацией массива в стеке, размер массива будет 
    //расчитан компилятором на этапе компиляции 
    char cArr[] = {1,3,5,8,3,8,4,9,0,3,7}; 
    //расчитываем длину массива, способ работает только для массивов 
    //размещенных в стеке
    //sizeof(cArr) - размер всего массива в байтах, sizeof(cArr[0]) - размер первого 
    //элемента, делим первое на второе - получаем количество элементов
    int length = sizeof(cArr)/sizeof(cArr[0]);
    //для сортировки используем функцию sort() стандартной библиотеки, в 
    //качестве итераторов передаем ей указатели на первый и следующий за 
    //последним элементы массива
    sort( &cArr[0], &cArr[ length ]);
    //выводим элементы отсортированного массива, "\n" - служебный символ     
    //перевода на новую строку, перед выводом каждый элемент приводится к типу
    //int чтобы на экран выводилось число а не символ 
    for( int i = 0; i < length; ++i )
        cout<<"\n"<<(int)cArr[i];
    //задержка перед завершением, чтобы мы могли полюбоваться на результат
    //для завершения надо нажать Enter
    cin.get();
    //отсутствие return в main() эквивалентно return 0; те нормальное завершение
}

PS есть неточности, например, "\n" конечно не символ, а строка, символ это '\n', но в нашем случае не важно

Это сообщение отредактировал(а) zkv - 23.1.2007, 21:38

Anikmar

Дата 23.1.2007, 21:38 (ссылка)

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

Загрузка ...

Эксперт

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

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

zkv, Это пять! Снимаю шляпу, ставлю +

JackYF

Дата 24.1.2007, 15:55 (ссылка)

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

Загрузка ...

полуавантюрист

Профиль
Группа: Участник
Сообщений: 5814
Регистрация: 28.8.2004
Где: страна тысячи озё р

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

Все-таки return 0 лучше ставить.
main() - самая обычная функция...

Цитата(zkv @ 23.1.2007, 21:36

)

/отсутствие return в main() эквивалентно return 0;

Не эквивалентно. Но подойдет.

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

Пожаловаться на меня как модератора можно здесь.

zkv

Дата 24.1.2007, 16:52 (ссылка)

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

Загрузка ...

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

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

Цитата(JackYF @ 24.1.2007, 15:55

)

Все-таки return 0 лучше ставить.
main() - самая обычная функция...

Цитата(zkv @ 23.1.2007, 21:36 Найти цитируемый пост)
/отсутствие return в main() эквивалентно return 0;

Не эквивалентно. Но подойдет.

идем читать стандарт по поводу "обычности" main и ее возвращаемого значения
(копировал из pdf где то пробелы потерялись, извините smile

)

Цитата

3.6.1 Main function [basic.start.main]
1  Aprogram shall contain aglobal function calledmain,which is the designated start of the program. It is implementation-defined whether a program in a freestanding environment is required to define a main function. [ Note: in a freestanding environment, start-up and termination is implementation-defined; start-up contains the execution of constructors for objects ofnamespace scope with static storage duration; termination contains the execution of destructors for objects with static storage duration. — end note ]
2  An implementation shall not predefine the main function. This function shall not be overloaded. It shall have a return type of type int,but otherwise its type is implementation-defined. All implementations shall allowboth of the following definitions of main :
    i n t m a i n ( ) { /∗ . . . ∗ / }
    and
    i n t m a i n ( i n t a r g c , c h a r * a r g v [ ] ) { /∗ . . . ∗ / }
    In the latter form argc shall be the number of arguments passed to the program from the environment in which the program is run. If argc is nonzero these arguments shall be supplied in argv[0] through argv[argc-1] as pointers to the initial characters of null-terminated multibyte strings (NTMBSs) (17.3.2.1.3.2)andargv[0] shall be the pointer to the initial character of a NTMBS that represents the name used to invoke the program or "". The value of argc shall be nonnegative. The value of argv[argc] shall be 0. [ Note: it is recommended that anyfurther (optional) parameters be added after argv. — end note ]
3  The function main shall not be used (3.2)within a program. The linkage (3.5)ofmain is implementation-defined. A program that declares main to be inline or static is ill-formed. The name main is not otherwise reserved. [ Example: member functions, classes, and enumerations can be called main, as can entities in other namespaces. — end example ]
4  Calling the function std::exit(int) declared in <cstdlib> (18.3)terminates the program without leaving the current block and hence without destroying anyobjects with automatic storage duration (12.4). If std::exit is called to end a program during the destruction of an object with static storage duration, the program has undefined behavior.
5  A return statement in main has the effect of leaving the main function (destroying anyobjects with automatic storage duration) and calling std::exit with the return value as the argument. If control reaches the end of main without encountering a return statement, the effect is that of executing
return 0;

JackYF

Дата 24.1.2007, 17:20 (ссылка)

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

Загрузка ...

полуавантюрист

Профиль
Группа: Участник
Сообщений: 5814
Регистрация: 28.8.2004
Где: страна тысячи озё р

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

Ну что же, со стандартом спорить глупо smile

.

Однако,
ИМХО:
1. Не универсально... зачем? вопрос к стандарту.
2. GCC не зря выдает предупреждение в этом случае (если нету return 0;)

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

Пожаловаться на меня как модератора можно здесь.

comp

Дата 24.1.2007, 17:49 (ссылка)

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

Загрузка ...

Шустрый

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

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

Это реализованно применительно к спискам... самое очевидное, для чего она нужна(ну + ещё сортировка "длинных" чисел)...
Вот небольшой пример, который объясняет принципы цифровой сортировки
И - исходный список
О - очереди
П - после "сливания" очередей в кучу

И:631 403 220 302 103 133 730 321

О:
1 - 220 730
2 - 631 321
3 - 302
4 - 403 103 133
П:
220 730 631 321 302 403 103 133

О:
1 - 302 403 103
2 - 220 321
3 - 730 631 133
П:
302 403 103 220 321 730 631 133

О:
1 - 103 133
2 - 220
3 - 302 321
4 - 403
6 - 631
7 - 730
П:
103 133 220 302 321 403 631 730

Код


struct sp
{
 sp *next;
 union
 {
  int x;
  unsigned char digit[sizeof(int)];
 };
};

struct fifo
{
 sp *head, *tail;
};

void dsort(sp* &s)
{
 sp *p;
 fifo c[256];
 int d, L = 5, m[5] = {4, 3, 2, 1, 0};

 for (int j = L; j > 0; j--)
     {
      for (int i = 0; i < 256; i++) 
       c[i].tail = (sp *)&(c[i].head);
      
      for (p = s; p; p = p->next)
          {
           d = p->digit[m[j]];
           c[d].tail->next = p;
           c[d].tail = p;
          }

      p = (sp *)&s;
      for (int i = 0; i < 256; i++)
       if (c[i].tail != (sp *)&(c[i].head))
          {
           p->next = c[i].head;
           p = c[i].tail;
          }
      p->next = NULL;
     }
}

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