0

Задача заключается в следующем: вводим текст с клавиатуры, на выходе должны получить предложения построчно, причем в порядке возрастания длины предложения. Какую структуру лучше выбрать, чтоб в последствии было легче написать алгоритм сортировки?( Опробовал варианты vector<vector<char>> и vector<string>, но туплю в написании алгоритма сортировки по длине строки.

5
  • Что означает в ваших терминах понятие "предложение"? И какой алгоритм сортировки вы собираетесь написать? 17 дек 2016 в 22:58
  • предложение есть набор слов, состоящих из букв, и знак препинания: точка, вопросительный, восклицательный.
    – Freddy
    17 дек 2016 в 23:01
  • А как насчет алгоритма сортировки? 17 дек 2016 в 23:04
  • Как я ниже написал, проблема упирается в то, как при считывании string из нескольких предложений, запушбэчить их в вектор по одному
    – Freddy
    17 дек 2016 в 23:14
  • Это уже другой вопрос. 17 дек 2016 в 23:36

3 ответа 3

2

Исполнение на 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;
}

Вывод:

Мама
Мама мыла
Мама мыла раму
2
  • Спасибо! Помогло)
    – Freddy
    17 дек 2016 в 22:54
  • В принципе, @VladD это успел написать даже раньше. Я просто скомпиленный пример привел. Расти большой)
    – Majestio
    17 дек 2016 в 22:57
1

Проще всего взять vector<string>. Для сортировки по длине используйте std::sort с компаратором.

vector<string> v;
// ...
sort(v.begin(), v.end(), 
     [](const string& l, const string& r) { return (l.length() < r.length()); });
7
  • Так и делал, проблема возникла в том, если за раз вводишь не одно, а несколько предложений в стринг, то как их потом по одному за пушбэчить в вектор?
    – Freddy
    17 дек 2016 в 22:44
  • @Freddy: А зачем вводить несколько в стринг? Вводите по одному.
    – VladD
    17 дек 2016 в 22:47
  • @Freddy: Если их уже несколько в строке, ну так разбейте на куски, соответствующие предложениям. Но это уже другая проблема, не связанная с вашим вопросом о сортировке и структуре данных.
    – VladD
    17 дек 2016 в 22:48
  • Это часть задачи. На ввод я обязан ввести сколько угодно предложений. Затем закидываю их в этот стринг, а стринг пушбэчу. Не могу сообразить, то ли стринг делить на предложения и частями пушбэчить, то ли как-то в стринг в процессе считывания их по одному заносить. Не знаю, как это реализовать.
    – Freddy
    17 дек 2016 в 22:49
  • VladD, все написал грамотно
    – Majestio
    17 дек 2016 в 22:56
0

Как я понимаю, то это задание на составление самостоятельно абстрактной структуры данных и ее сортировки.

В противном случае вы могли бы использовать контейнер 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 не эффективно, так как он будет постоянно перераспределять память при добавлении нового элемента, а затем еще потребуется сортировка.

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

2

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими пользовательским соглашением, политикой конфиденциальности и политикой о куки

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.