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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 16, средняя оценка - 4.75
Bellfator
0 / 0 / 0
Регистрация: 15.04.2013
Сообщений: 17
#1

Лексикографическая сортировка - C++

12.08.2013, 03:40. Просмотров 2342. Ответов 5
Метки нет (Все метки)

Задача:

Пусть имеется N строк различной длины алфавита мощности M с заданным на них лексикографическим порядком (см. [3,4,9,12]). Необходимо отсортировать их в соответствии с этим порядком, т.е. отсортировать, используя алгоритм лексикографической сортировки. Данная сортировка относится к классу распределяющих сортировок и имеет линейную трудоемкость относительно числа сортируемых строк при условии, что M<

Указания:

При реализации данного алгоритма для хранения данных следует использовать структуру данных очередь. В начале создается очередь, в которую записываются все сортируемые строки. Далее формируются M вспомогательных очередей по числу символов в алфавите. Если, например, в текущей рассматриваемой строке i-ый символ равен “a”, то данная строка размещается в очередь, соответствующую символу “a”. Просмотр символов в строке производится справа налево. Перед началом работы основного цикла алгоритма строки разбиваются по длинам. Сортировка начинается со строк большей длины.

________________________________________________________________________________________________________




Такая вот печаль, задачу целой компании в 3 человека решить не можем, ничего не понятно, глухо как в танке. Помогите кто чем может. Сдавать в сентябре, а еще конь не валялся.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
12.08.2013, 03:40     Лексикографическая сортировка
Посмотрите здесь:

Лексикографическая сортировка по имени - C++
Привет всем форумчанам! Вот у меня такая проблемка: нужно реализовать лексикографическую сортировку по имени, а для этого придумать...

Сортировка подсчетом и LSD сортировка - C++
Кто может дать реализацию сортировки подсчетом и lsd сортировки на C?

Сортировка методом "быстрая сортировка" - C++
Здравствуйте! Имеется структура: struct BMS_Data { int* SortNodesList; double* NodesX; double* NodesY; ...

Лексикографическая сортировка слов - Visual C++
Мне срочно нужно сделать задачу по программированию на С++. Пожалуйста кому не трудно ее сделать помогите.Лексикографическая сортировка...

Лексикографическая сортировка java - Java SE
Помогите, пожалуйста! Есть код, в него нужно добавить лексикографическую сортировку. Чтобы на выходе было получено: мыла мама ...

Лексикографическая Сортировка Цепочек Последовательностей Различной Длины - Pascal
Необходимо реализовать лексикографический алгоритм сортировки цепочек последовательностей различной длины.. Как это сделать не знаю.....

Сортировка Хоара, быстрая сортировка - Алгоритмы
2 дня сижу пытаюсь написать программу С++ быстрой сортировки #include &quot;stdafx.h&quot; #include &lt;stdio.h&gt; #include &lt;stdlib.h&gt; #include...

Быстрая сортировка и сортировка Шелла - Java SE
есть трудности с быстрой сортировкой и сортировкой Шелла также нужен их сравнительный анализ

Сортировка файлов Трехленточная сортировка - Delphi
Реализовать алгоритм трехленточной сортировки исходного файла, содержащего N элементов (2500&lt;N&lt;100000). Подобные ссылки запрещены...

Сортировка массивов. Сортировка выбором - Pascal
Помогите пожалуйста, я что-то совсем запуталась при составлении данной программы... Сортировка выбором. Дана последовательность чисел...

Сортировка списка, главная сортировка по второму числу, второстепенная по первому числу - C#
CardList.Sort(new Comparison&lt;int&gt;((arg1, arg2) =&gt; { return (arg1 % 10).CompareTo(arg2 % 10); })); В данном коде сортируется список...


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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
salam
160 / 141 / 12
Регистрация: 10.07.2012
Сообщений: 720
12.08.2013, 06:26     Лексикографическая сортировка #2
Цитата Сообщение от Bellfator Посмотреть сообщение
(см. [3,4,9,12])
поясните, что здесь имеется ввиду.

Добавлено через 6 минут
если можно, выложите задание в том виде, в котором оно дано, без изменений и полностью.
ya_noob
_
201 / 145 / 9
Регистрация: 08.10.2011
Сообщений: 432
12.08.2013, 10:58     Лексикографическая сортировка #3
Bellfator, в условии описана поразрядная LSD-сортировка. если погуглите, то скорее всего найдете ее реализацию на основе сортировки подсчетом. но если заменить сортировку подсчетом на операции с очередью (как описано в условии), то всё получится.
идея такая: раскладываете слова из основной очереди по вспомогательным очередям в соответствии с текущей буквой, затем сливаете содержимое вспомогательных очередей в основную очередь, затем переходите к следующей букве (левее) и повторяете процесс. еще нужно решить вопрос со словами различной длины.
Bellfator
0 / 0 / 0
Регистрация: 15.04.2013
Сообщений: 17
12.08.2013, 21:35  [ТС]     Лексикографическая сортировка #4
Цитата Сообщение от salam Посмотреть сообщение
поясните, что здесь имеется ввиду.

Добавлено через 6 минут
если можно, выложите задание в том виде, в котором оно дано, без изменений и полностью.
Задание как раз таки выглядит так, цифры, нам не понятны, но это вроде как Лексикографический порядок, даже препод незнает как сделать
Андрей Xomach
8 / 8 / 0
Регистрация: 22.01.2012
Сообщений: 59
12.08.2013, 21:38     Лексикографическая сортировка #5
Bellfator, http://ru.wikipedia.org/wiki/%D0%9F%...B2%D0%BA%D0%B0
тут есть применение для строк, не оно?
iifat
2219 / 1372 / 101
Регистрация: 05.06.2011
Сообщений: 3,771
13.08.2013, 03:48     Лексикографическая сортировка #6
Не очень какая-то хорошая ссылка. Если и без того знать, оно более-менее понятно, но для первого знакомства лучше, имхо, вот тут почитать.
Yandex
Объявления
13.08.2013, 03:48     Лексикографическая сортировка
Ответ Создать тему
Опции темы

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