Задача заключается в следующем: вводим текст с клавиатуры, на выходе должны получить предложения построчно, причем в порядке возрастания длины предложения. Какую структуру лучше выбрать, чтоб в последствии было легче написать алгоритм сортировки?( Опробовал варианты vector<vector<char>>
и vector<string>
, но туплю в написании алгоритма сортировки по длине строки.
-
Что означает в ваших терминах понятие "предложение"? И какой алгоритм сортировки вы собираетесь написать?– Vlad from Moscow17 дек 2016 в 22:58
-
предложение есть набор слов, состоящих из букв, и знак препинания: точка, вопросительный, восклицательный.– Freddy17 дек 2016 в 23:01
-
А как насчет алгоритма сортировки?– Vlad from Moscow17 дек 2016 в 23:04
-
Как я ниже написал, проблема упирается в то, как при считывании string из нескольких предложений, запушбэчить их в вектор по одному– Freddy17 дек 2016 в 23:14
-
Это уже другой вопрос.– Vlad from Moscow17 дек 2016 в 23:36
3 ответа
Исполнение на ideone
#include <algorithm>
#include <iostream>
#include <vector>
int main() {
std::vector<std::string> Vec = {
"Мама",
"Мама мыла раму",
"Мама мыла"
};
std::sort(Vec.begin(),Vec.end(),[](const std::string& a, const std::string& b) {
return a.size()<b.size();
});
for(const auto &i:Vec) std::cout << i << std::endl;
return 0;
}
Вывод:
Мама
Мама мыла
Мама мыла раму
-
-
В принципе, @VladD это успел написать даже раньше. Я просто скомпиленный пример привел. Расти большой)– Majestio17 дек 2016 в 22:57
Проще всего взять vector<string>
. Для сортировки по длине используйте std::sort
с компаратором.
vector<string> v;
// ...
sort(v.begin(), v.end(),
[](const string& l, const string& r) { return (l.length() < r.length()); });
-
Так и делал, проблема возникла в том, если за раз вводишь не одно, а несколько предложений в стринг, то как их потом по одному за пушбэчить в вектор?– Freddy17 дек 2016 в 22:44
-
-
@Freddy: Если их уже несколько в строке, ну так разбейте на куски, соответствующие предложениям. Но это уже другая проблема, не связанная с вашим вопросом о сортировке и структуре данных.– VladD17 дек 2016 в 22:48
-
Это часть задачи. На ввод я обязан ввести сколько угодно предложений. Затем закидываю их в этот стринг, а стринг пушбэчу. Не могу сообразить, то ли стринг делить на предложения и частями пушбэчить, то ли как-то в стринг в процессе считывания их по одному заносить. Не знаю, как это реализовать.– Freddy17 дек 2016 в 22:49
-
Как я понимаю, то это задание на составление самостоятельно абстрактной структуры данных и ее сортировки.
В противном случае вы могли бы использовать контейнер std::multiset
, в котором элементы сами бы упорядочивались по возрастанию длин предложений без всякой сортировки. Например,
#include <iostream>
#include <string>
#include <set>
int main()
{
auto compare = [](const std::string &a, const std::string &b)
{
return a.length() < b.length();
};
std::multiset< std::string, decltype(compare)> sentences(compare);
for (const std::string & s : { "123", "12", "12345", "1234", "1" })
{
sentences.insert(s);
}
for (const auto &s : sentences) std::cout << s << std::endl;
}
Вывод программы на консоль
1
12
123
1234
12345
Если вам надо разбить строку на предложения, то это можно сделать примерно следующим образом
#include <iostream>
#include <string>
#include <set>
int main()
{
auto compare = [](const std::string &a, const std::string &b)
{
return a.length() < b.length();
};
std::multiset< std::string, decltype(compare)> sentences(compare);
std::string text("I'm learning C++... How to write the program? I did it!");
for (std::string::size_type pos = 0; pos != text.size(); )
{
auto last_pos = text.find_first_of(".?!", pos);
if (last_pos == std::string::npos)
{
sentences.insert(text.substr(pos));
pos = text.size();
}
else
{
while (last_pos < text.size() && text[last_pos] == '.') ++last_pos;
sentences.insert(text.substr(pos, last_pos - pos + 1));
while (++last_pos < text.size() &&
(text[last_pos] == ' ' || text[last_pos] == '\t'));
pos = last_pos;
}
}
for (const auto &s : sentences) std::cout << s << std::endl;
}
Вывод программы на консоль:
I did it!
I'm learning C++...
How to write the program?
Использовать для такой задачи контейнер std::vector
не эффективно, так как он будет постоянно перераспределять память при добавлении нового элемента, а затем еще потребуется сортировка.
Если говорить о собственноручно написании структуры данных для хранения предложений, то постройте односвязный список. В него также добавляйте новые элементы в порядке возрастания ключей.
-
-
find_first_of(".?!;", pos);
иначе Кондратий Рылеев не парсится)))) stih.pro/je-vous-assure-chto-vi-mne-mili/ot/ryleev– Majestio18 дек 2016 в 0:31