«Напишите программу, которая читает последовательность символов, введенных пользователем и завершенных точкой (‘.’). Ваша программа должна позволять пользователю вводить несколько строк ввода, нажимая клавишу ввода в конце каждой строки. Программа должна распечатать таблицу частот, отсортированную в порядке убывания по количеству вхождений, перечисляя каждую встречающуюся букву, а также количество повторений. Все не алфавитные символы должны игнорироваться. Любые символы, введенные после точки (‘. ‘) следует оставлять во входном потоке необработанным. Не допускается ограничение длины входных данных. «
Я не знаю, с чего начать. Пока это то, что я придумал:
#include<iostream>
using namespace std;int main(){int count=0;
char ch[count];
int i=0;
cout<<"Enter a sequence of characters (end with '.'): ";
cin>>ch[count];
while(ch[count]!='.')
{
count++;
cin>>ch[count];}
cout<<"There were "<<count<<" characters in the string"<<endl;
return 0;
}
Прямо сейчас программа принимает ввод пользователя и отображает количество символов в нем, но я не могу заставить его отображать любой из символов, не говоря уже о порядке убывания. Сортировка не моя проблема, я полностью понимаю, как программировать, но я не могу отобразить символы, хранящиеся во входном потоке.
Мой инструктор предложил использовать структуру, но сейчас мне просто нужно направление. Вывод должен быть отформатирован следующим образом:
Enter a sequence of characters (end with '.'): do be Do bo. xyzLetter: Number of Occurrences
o 3
d 2
b 2
e 1
Я не прошу никого делать кодирование для меня, мне просто нужна помощь в том, с чего начать и как отобразить символы. Мы не можем использовать строковый класс и, следовательно, любые строковые функции, кроме strlen()
,
Вы можете читать ввод по одному символу за раз (это то, что вы будете использовать) или читать его целые куски (более быстрое решение), если ввод загружается из текстового файла или проверяется онлайн-судьей или чем-то похожим, что загружает весь ввод сразу, но это sidenote.
Прежде всего, я бы начал с добавления этой строки в ваш код прямо в начале вашего main
ios::sync_with_stdio(false);
Эта строка значительно ускорит ваш код, потому что ввод-вывод C ++ больше не синхронизируется с вводом-выводом C, поэтому он устраняет значительные накладные расходы, но имейте в виду, что вы получите бессмысленный мусор, если вы смешаете две библиотеки ввода-вывода после эта линия.
Как только ввод / вывод будет готов, я добавлю код, который читает входные данные и подсчитывает количество случаев. Чтобы достичь этого, вы должны быть заинтересованы в одной конкретной функции — получить. Теперь вам просто нужен массив целых чисел, который больше 0 (должен соответствовать любым символам, которые могут появиться в качестве входных данных, набор символов должен быть указан где-то, но безопасным числом будет 256 для ASCII), цикл, условие который завершает цикл (символ из ввода == '.'
) и вы почти закончили читать и считать (для этого не нужно никаких функций!).
Сортировка не так уж и ужасна. Скорее всего, пузырьковая сортировка — это не самый лучший способ, но сколько там символов? 40-иш? 50-иш? 100-иш? Если вы не выйдете за рамки 300-500 символов, не стоит реализовывать лучшее из когда-либо неизвестных человечеству O(lgn)
время, O(1)
Пространственный, устойчивый алгоритм сортировки, потому что в среднем он работает хуже, чем более простые алгоритмы. Ищите сортировку слиянием или быструю сортировку, если вы хотите использовать сверхмощный алгоритм, или ищите более простые альтернативы, например, пузырьковая сортировка (самая простая и самая медленная) или вставная сортировка.
Есть две части, которые должны быть решены. Во-первых, читая один за другим символы, игнорируя любой не-альфа-символ, и считайте остальные; Во-вторых, напечатать оценки в порядке убывания.
Первая часть может быть решена путем простой обработки символа как значения ASCII в диапазоне от 0 до 255 (т. Е. В диапазоне без знака) и наличия массива счетчиков для каждого из этих значений.
Во-вторых, вы можете просто просмотреть счетчик, найти максимум и распечатать его. Продолжайте до тех пор, пока все значения> 0 не будут учтены.
Смотрите следующий код, иллюстрирующий этот подход:
#include <sstream>
int main() {
stringstream ss("do be Do bo. xyz");
unsigned char c;
unsigned int counts[256] = {0};
while (ss >> c && c != '.') {
if (! isalpha(c)) {
continue;
}
c = tolower(c);
counts[c]++;
}
while (1) {
// find next maximum
int max = 0;
int maxPos = -1;
for (int i=0; i<256; i++) {
if (counts[i] > max) {
max = counts[i];
maxPos = i;
}
}
if (max == 0) {
break;
}
else {
cout << (char)maxPos << ":" << max << endl;
counts[maxPos] = 0; // don't consider this pos in next run
}
}
}
Выход:
o:3
b:2
d:2
e:1