Сортировка слов в строке по алфавиту

[sasha vedmak]

!!SOS!!
Помогите решить задачу на С++:
11. Строка состоит из слов. Переставить в ней слова, состоящие только из букв латиницы, так, чтобы они были упорядочены по алфавиту. При этом другие слова должны оставаться на месте. Слова в исходной строке разделяются некоторым множеством разделителей. Слова в новой строке должны разделяться ровно одним пробелом.

Нужно решить задачу с помощью char и с помощью string(по отдельности, то есть 2 кода, но мне хотя бы 1)

[Пётр Седов]

sasha vedmak, в C-шном стиле можно так:

#include <assert.h>
#include <string.h>
#include <algorithm>
#include <stdio.h>

using namespace std;

bool is_separator(char elem) {
  return (elem == ' ') || (elem == ',') || (elem == '.');
}

bool is_latin_letter(char elem) {
  return (('a' <= elem) && (elem <= 'z')) || (('A' <= elem) && (elem <= 'Z'));
}

struct word_t {
  const char* elems; // не завершается нулевым элементом ('\0')
  int len;
  bool latin_only;
};

// для учебного задания сойдёт глобальный массив фиксированного размера
// во «взрослом» коде будет локальный контейнер, например std::vector<word_t>
const int _max_words_count = 100;
word_t _words[_max_words_count];
int _words_count;

void get_words(const char* text) {
  _words_count = 0;
  int pos = 0;
  for (;;) {
    while (is_separator(text[pos])) {pos++;} // пропускаем разделители
    if (text[pos] == '\0') {break;} // если дошли до конца текста
    // сканируем слово
    int start = pos;
    bool latin_only = true;
    do {
      if (!is_latin_letter(text[pos])) {
        latin_only = false;
      }
      pos++;
    } while ((text[pos] != '\0') && !is_separator(text[pos]));
    // добавляем слово в массив
    assert(_words_count < _max_words_count);
    word_t* w = &_words[_words_count];
    w->elems = text + start;
    w->len = pos - start;
    w->latin_only = latin_only;
    _words_count++;
  }
}

// сравнивает слова как стандартная функция strcmp
// (которую здесь нельзя использовать, потому что строки не завершаются нулевыми элементами)
int compare(const word_t* w1, const word_t* w2) {
  int c = memcmp(w1->elems, w2->elems, min(w1->len, w2->len));
  if (c != 0) {return c;}
  return w1->len - w2->len;
}

char* sort_words(const char* text) {
  get_words(text);

  int result_len = 0;
  // сортируем слова (только которые latin_only)
  for (int i = 0; i < _words_count; i++) {
    if (_words[i].latin_only) {
      // ищем «минимальное» слово, начиная с i-го
      int min = i;
      for (int k = i + 1; k < _words_count; k++) {
        if (_words[k].latin_only && (compare(&_words[k], &_words[min]) < 0)) {
          min = k;
        }
      }
      // ставим «минимальное» слово в позицию i
      if (i != min) {
        swap(_words[i], _words[min]);
      }
    }
    result_len += _words[i].len + 1;
  }

  char* result = new char[result_len + 1];
  // копируем слова
  int pos = 0;
  for (int i = 0; i < _words_count; i++) {
    const word_t* w = &_words[i];
    memcpy(result + pos, w->elems, w->len);
    pos += w->len;
    result[pos++] = ' ';
  }
  assert(pos == result_len);
  result[pos] = '\0';
  return result;
}

int main() {
  char* t = sort_words("x d1, yy d2, zzz d3, aaa d4, bbb d5, ccc");
  printf("%s\n", t);
  delete[] t;
  return 0;
}

Вывод на консоль:

aaa d1 bbb d2 ccc d3 x d4 yy d5 zzz

Разбивать текст на слова можно стандартной функцией strtok, но я её не люблю, потому что она меняет содержимое исходной строки, и поэтому её нельзя использовать например для строковых литералов (текст в двойных кавычках).