Словарь частоупотребимых слов

@prizrak39 · Регистрация: 10.12.2012

Студворк — интернет-сервис помощи студентам

Здравствуйте. Столкнулся со следующим задачей. На входе задается список слов, для которых указана частота из появления в словаре. Также на входе задается несколько слов или часть слов (возможно просто один символ). Необходимо вывести из введенного ранее словаря в порядке убывания по частоте слова которые содержать введенные значения.
Например.
На входе задается словарь.

Code
1
2
3
qard 10
qanojd 20
qaretachd 1

Далее задаются символы.

Code
1
2
q
qar

В результате должно вывестись следующее.

Code
1
2
3
4
5
qanojd
qard
qaretachd
qard
qaretachd

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

@Igor3D · 25.02.2013, 22:07

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

Если так то все очень банально: сортируете словарь (одномерный массив).по алфавиту, при вводе ищете минимальное совпадающее. Потом идете вправо по словарю пока совпадения не кончились. В результате известен диапазон подходящих индексов, напр [10-15]. Делаете временный массив индексов и сортируете его по частоте, вот и все

@prizrak39 · 25.02.2013, 23:05 **[ТС]**

Массив по алфавиту я отсортирую, а как мне их потом связать с их частотой? Этот момент я не совсем понял.

@gazlan · 25.02.2013, 23:34

Небходимо использовать не массив слов, а массив записей (пар) типа слово-счетчик. При сортировке слова и их счетчики будут сцеплены.

@prizrak39 · 25.02.2013, 23:36 **[ТС]**

Лучше наверное использовать списки?

@iama · 25.02.2013, 23:48

prizrak39, сортируете просто массив структур, а потом проходите за линию за запрос. Вообще, можно тут бор припилить, но это слишком сложно, мне кажется, для ваших потребностей.

@prizrak39 · 25.02.2013, 23:52 **[ТС]**

Из всего я понял что лучше всего отсортировать массив по алфавиту и в нем уже осуществлять поиск. Интересно а возможно сортировать массив по мере чтения значений?

@iama · 25.02.2013, 23:57

Сообщение от prizrak39

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

Сообщение от prizrak39

Из всего я понял что лучше всего отсортировать массив по алфавиту и в нем уже осуществлять поиск.

Противоречие.

@prizrak39 · 26.02.2013, 00:03 **[ТС]**

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

@gazlan · 26.02.2013, 00:18

Примерно так (сортировка по двум ключам):

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
if (p1->v1 > p2->v1)
{
   return 1;
}
else if (p1->v1 < p2->v1)
{
   return -1;
}
else
{
   if (p1->v2 > p2->v2)
   {
      return 1;
   }
   else if (p1->v2 < p2->v2)
   {
      return -1;
   }
   else
   {
      return 0;
   }
}

@prizrak39 · 26.02.2013, 00:21 **[ТС]**

Сначала сортируем по частоте, а потом внутри каждых одинаковых значений по алфавиту. Я правильно понял?

@gazlan · 26.02.2013, 00:25

Да, правильно. По частоте - в обратном порядке ключей, по алфавиту - в прямом. Если будете использовать массив структур, рекомендую стандартный qsort().

@prizrak39 · 26.02.2013, 00:26 **[ТС]**

Большое спасибо постараюсь реализовать.

@Igor3D · 26.02.2013, 11:31

Сообщение от prizrak39

Массив по алфавиту я отсортирую, а как мне их потом связать с их частотой? Этот момент я не совсем понял.

Ну вот в результате поиска выяснилось: подходят слова с 10 по 15 в словаре. Делаете массив int { 10, 11, 12, 13, 14, 15 } и сортируете его напр таким функтором

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
struct Word {
 string mText;      // слово
 int mFrequency;  // частота
};
 
struct CompFrequency {
 CompFrequency( const vector  <Word> & data ) : mData(data) {}
 bool operator () ( int i1, int i2 ) const
 {
   return mData[i1].mFrequency > mData[i2].mFrequency;
 }
 
 const vector  <Word> & mData; 
}; 
 
// использование
vector  <Word>  dictionary; 
vector <int> temp;  // заполнили temp
...
std::sort(temp.begin(), temp.end(), CompFrequency(dictionary));

Добавлено через 3 минуты

Сообщение от prizrak39

Сначала сортируем по частоте, а потом внутри каждых одинаковых значений по алфавиту. Я правильно понял?

По-моему совершенно неправильно

. Отсортировав по первому ключу = частота Вы не сможете найти нужные слова

@prizrak39 · 26.02.2013, 11:40 **[ТС]**

Тогда получается необходимо пробежать по всему введенному массиву и найти совпадения и записать их в отдельный массив. Далее отсортировать этот массив по частоте. Правильно?

@Igor3D · 26.02.2013, 12:02

Сообщение от prizrak39

Тогда получается необходимо пробежать по всему введенному массиву и найти совпадения и записать их в отдельный массив. Далее отсортировать этот массив по частоте. Правильно?

Не по всему, если массив отсортирован по алфавиту то просто lower_bound (найти первый подходящий) и upper_bound (найти первый НЕподходящий). Это быстрые поиски

@prizrak39 · 26.02.2013, 18:42 **[ТС]**

А не подскажите какой лучше тип данных использовать? Например в C#. List я думаю не подходит, ArrayList возможно, тогда необходимо будет в нем хранить структуру?

@gazlan · 26.02.2013, 19:21

Сообщение от Igor3D

По-моему совершенно неправильно

. Отсортировав по первому ключу = частота Вы не сможете найти нужные слова

Перечитайте задание: "в порядке убывания по частоте" ... "Если частота упоминаний совпадает, тогда вывод необходимо осуществлять в алфавитном порядке"

Делать надо именно так, как сказано в #10.

Если вам непонятно, что такое multikey sort, посмотрите в литературе.

Новые блоги и статьи Все статьи Все блоги /
моя боль iceja 24.01.2026 Выложила интерполяцию кубическими сплайнами www. iceja. net REST сервисы временно не работают, только через Web. Написала за 56 рабочих часов этот сайт с нуля. При помощи perplexity. ai PRO , при. . .	Модель сукцессии микоризы anaschu 24.01.2026 Решили писать научную статью с неким РОманом	http://iceja.net/ математические сервисы iceja 20.01.2026 Обновила свой сайт http:/ / iceja. net/ , приделала Fast Fourier Transform экстраполяцию сигналов. Однако предсказывает далеко не каждый сигнал (см ограничения http:/ / iceja. net/ fourier/ docs ). Также. . .	http://iceja.net/ сервер решения полиномов iceja 18.01.2026 Выкатила http:/ / iceja. net/ сервер решения полиномов (находит действительные корни полиномов методом Штурма). На сайте документация по API, но скажу прямо VPS слабенький и 200 000 полиномов. . .
Расчёт переходных процессов в цепи постоянного тока igorrr37 16.01.2026 / * Дана цепь(не выше 3-го порядка) постоянного тока с элементами R, L, C, k(ключ), U, E, J. Программа находит переходные токи и напряжения на элементах схемы классическим методом(1 и 2 з-ны. . .	Восстановить юзерскрипты Greasemonkey из бэкапа браузера damix 15.01.2026 Если восстановить из бэкапа профиль Firefox после переустановки винды, то список юзерскриптов в Greasemonkey будет пустым. Но восстановить их можно так. Для этого понадобится консольная утилита. . .	Сукцессия микоризы: основная теория в виде двух уравнений. anaschu 11.01.2026 https:/ / rutube. ru/ video/ 7a537f578d808e67a3c6fd818a44a5c4/	WordPad для Windows 11 Jel 10.01.2026 WordPad для Windows 11 — это приложение, которое восстанавливает классический текстовый редактор WordPad в операционной системе Windows 11. После того как Microsoft исключила WordPad из. . .

@Igor3D 1967 / 823 / 114 Регистрация: 01.10.2012 Сообщений: 4,831 Записей в блоге: 2
	25.02.2013, 22:07
	Может лучше сформулировать так: человек набирает какой-то текст, а ему выпадает напр popup menu в котором список всех слов из словаря начинающихся с введенной части. Если так то все очень банально: сортируете словарь (одномерный массив).по алфавиту, при вводе ищете минимальное совпадающее. Потом идете вправо по словарю пока совпадения не кончились. В результате известен диапазон подходящих индексов, напр [10-15]. Делаете временный массив индексов и сортируете его по частоте, вот и все 0

@prizrak39 0 / 0 / 0 Регистрация: 10.12.2012 Сообщений: 34
	25.02.2013, 23:05 [ТС]
	Массив по алфавиту я отсортирую, а как мне их потом связать с их частотой? Этот момент я не совсем понял. 0

@gazlan 3176 / 1935 / 312 Регистрация: 27.08.2010 Сообщений: 5,131 Записей в блоге: 1
	25.02.2013, 23:34
	Небходимо использовать не массив слов, а массив записей (пар) типа слово-счетчик. При сортировке слова и их счетчики будут сцеплены. 0

@prizrak39 0 / 0 / 0 Регистрация: 10.12.2012 Сообщений: 34
	25.02.2013, 23:36 [ТС]
	Лучше наверное использовать списки? 0

@iama 1360 / 988 / 119 Регистрация: 30.07.2010 Сообщений: 5,297
	25.02.2013, 23:48
	prizrak39, сортируете просто массив структур, а потом проходите за линию за запрос. Вообще, можно тут бор припилить, но это слишком сложно, мне кажется, для ваших потребностей. 0

@prizrak39 0 / 0 / 0 Регистрация: 10.12.2012 Сообщений: 34
	25.02.2013, 23:52 [ТС]
	Из всего я понял что лучше всего отсортировать массив по алфавиту и в нем уже осуществлять поиск. Интересно а возможно сортировать массив по мере чтения значений? 0

@prizrak39 0 / 0 / 0 Регистрация: 10.12.2012 Сообщений: 34
	26.02.2013, 00:03 [ТС]
	Если сортировать в порядке возрастания, то не совсем понятно как внутри одинакового количества упоминаний выводить значения по алфавиту. 0

@prizrak39 0 / 0 / 0 Регистрация: 10.12.2012 Сообщений: 34
	26.02.2013, 00:21 [ТС]
	Сначала сортируем по частоте, а потом внутри каждых одинаковых значений по алфавиту. Я правильно понял? 0

@gazlan 3176 / 1935 / 312 Регистрация: 27.08.2010 Сообщений: 5,131 Записей в блоге: 1
	26.02.2013, 00:25
	Да, правильно. По частоте - в обратном порядке ключей, по алфавиту - в прямом. Если будете использовать массив структур, рекомендую стандартный qsort(). 0

@prizrak39 0 / 0 / 0 Регистрация: 10.12.2012 Сообщений: 34
	26.02.2013, 00:26 [ТС]
	Большое спасибо постараюсь реализовать. 0

@prizrak39 0 / 0 / 0 Регистрация: 10.12.2012 Сообщений: 34
	26.02.2013, 11:40 [ТС]
	Тогда получается необходимо пробежать по всему введенному массиву и найти совпадения и записать их в отдельный массив. Далее отсортировать этот массив по частоте. Правильно? 0

@prizrak39 0 / 0 / 0 Регистрация: 10.12.2012 Сообщений: 34
	26.02.2013, 18:42 [ТС]
	А не подскажите какой лучше тип данных использовать? Например в C#. List я думаю не подходит, ArrayList возможно, тогда необходимо будет в нем хранить структуру? 0