C++ string Сортировка строк без векторов, мультисетов и без всего подобного

Опубликовано 14.05.2012 | Автор: admin

Предлагаю вашему вниманию решение одной из задач: сортировка строк, когда вводится неопределенное число строк.

Показываемый код демонстрируется желающим решить эту задачу без stl. Сколько строк будет заранее неизвестно.

Мной будет задействован тип std::string из заголовочного файла <string> Этот тип возможно использовать в компиляторах, которые поддерживают stl. В совсем старых компиляторах этого типа нет.

//clang     сортировка строк
#include <iostream>
#include <string>
#include <windows.h>

using namespace std;


/*ФУНКЦИЯ ВВОДА НЕОПРЕДЕЛЕННОГО ЧИСЛА СТРОК*/
string GetMyStr(int &count_word) {

	string S, temp;                   //S - это буферная строка, в нее читаем информацию с клавиатуры
									  //temp - это итоговая строка, скомпилированная из всех полученных строк в S

	cout << "Для прекращения ввода нажми CTRL+Z или введи пустую строку (НАЖМИ Enter)\n";
	while ((getline(cin, S)) && (S.length())>2) {   //Считываем символы с клавиатуры
		temp = temp + S + '\n';						 //Запоминаем строку в temp
		count_word++;								 //Увеличиваем счетчик строк

	}
	return temp;	//Возвращаем скомпилированную строку
}

/*ФУНКЦИЯ ДЛЯ ПОЛУЧЕНИЯ СТРОКИ ПО НОМЕРУ СТРОКИ*/
string GetStrFromMyStr(string S, int N) {

	int i = 0;										//Количество встреченных разделителей
	string buf;										//Вытаскиваемая строка
	const char *temp = (S.c_str());					//Указатель на начало строки S

	while (i != N) {								//Пока мы не встретим разделитель указанное число раз, будет цикл
		while (*temp != '\n') {						//Ищем разделитель
			if (i == N - 1) buf = buf + *temp;		//Если следующая итерация последняя, то начинаем собирать строчку (Это та самая, взятая по номеру)
			*temp++;								//Переход к следующему символу
		}
		*temp++;									//Переход к след символу
		i++;										//Увеличиваем счетчик разделителей
	}
	return buf;										//Возвращаем выбранную строчку
}

/*ФУНКЦИЯ СОРТИРОВКИ СТРОК*/
void sort(string *S, int N)
{
	for (int i = 0; i < N - 1; i++)
		for (int j = i + 1; j < N; j++) {
			if (strcmp(S[i].c_str(), S[j].c_str())>0) swap(S[i], S[j]);
		}
}

int main()
{
	setlocale(LC_ALL, "");
	SetConsoleOutputCP(1251);
	SetConsoleCP(1251);

	int count_word = 0;

	string MyStr = GetMyStr(count_word);
	cout << "***********ЗАКОНЧИЛИ ВВОД ДАННЫХ***********\n\n";
	//cout<<MyStr;  //MyStr == многострочная строка
	//Пишем функцию для взятия любой строчки из оной GetStrFromMyStr (обратимся к ней позднее)

	string *S = new string[count_word]; //Массив строк

										//заполняем массив строками
	for (int i = 0; i < count_word; i++) {
		S[i] = GetStrFromMyStr(MyStr, i + 1);
	}


	sort(S, count_word); //Сортируем массив

						 //ВЫВОДИМ МАССИВ НА ЭКРАН
	for (int i = 0; i < count_word; i++) {
		cout << S[i] << "\n";
	}

	cin.ignore();
	delete[]S;
}

//clang сортировка строк

#include <iostream>

#include <string>

#include <windows.h>

using namespace std;

/*ФУНКЦИЯ ВВОДА НЕОПРЕДЕЛЕННОГО ЧИСЛА СТРОК*/

string GetMyStr(int &count_word) {

string S, temp; //S - это буферная строка, в нее читаем информацию с клавиатуры

//temp - это итоговая строка, скомпилированная из всех полученных строк в S

cout << "Для прекращения ввода нажми CTRL+Z или введи пустую строку (НАЖМИ Enter)\n";

while ((getline(cin, S)) && (S.length())>2) { //Считываем символы с клавиатуры

temp = temp + S + '\n'; //Запоминаем строку в temp

count_word++; //Увеличиваем счетчик строк

}

return temp; //Возвращаем скомпилированную строку

}

/*ФУНКЦИЯ ДЛЯ ПОЛУЧЕНИЯ СТРОКИ ПО НОМЕРУ СТРОКИ*/

string GetStrFromMyStr(string S, int N) {

int i = 0; //Количество встреченных разделителей

string buf; //Вытаскиваемая строка

const char *temp = (S.c_str()); //Указатель на начало строки S

while (i != N) { //Пока мы не встретим разделитель указанное число раз, будет цикл

while (*temp != '\n') { //Ищем разделитель

if (i == N - 1) buf = buf + *temp; //Если следующая итерация последняя, то начинаем собирать строчку (Это та самая, взятая по номеру)

*temp++; //Переход к следующему символу

}

*temp++; //Переход к след символу

i++; //Увеличиваем счетчик разделителей

}

return buf; //Возвращаем выбранную строчку

}

/*ФУНКЦИЯ СОРТИРОВКИ СТРОК*/

void sort(string *S, int N)

{

for (int i = 0; i < N - 1; i++)

for (int j = i + 1; j < N; j++) {

if (strcmp(S[i].c_str(), S[j].c_str())>0) swap(S[i], S[j]);

}

int main()

{

setlocale(LC_ALL, "");

SetConsoleOutputCP(1251);

SetConsoleCP(1251);

int count_word = 0;

string MyStr = GetMyStr(count_word);

cout << "***********ЗАКОНЧИЛИ ВВОД ДАННЫХ***********\n\n";

//cout<<MyStr; //MyStr == многострочная строка

//Пишем функцию для взятия любой строчки из оной GetStrFromMyStr (обратимся к ней позднее)

string *S = new string[count_word]; //Массив строк

//заполняем массив строками

for (int i = 0; i < count_word; i++) {

S[i] = GetStrFromMyStr(MyStr, i + 1);

}

sort(S, count_word); //Сортируем массив

//ВЫВОДИМ МАССИВ НА ЭКРАН

for (int i = 0; i < count_word; i++) {

cout << S[i] << "\n";

}

cin.ignore();

delete[]S;

}

Что такое скомпилированная строка? В этом материале под этот термин попадает такая строка, которая собрана из нескольких строк. Просто к каждой строке добавляется некоторый разделитель. В моем случае этот разделитель есть символ '/n'. После добавления очередного разделителя строка склеивается со следующей строкой, считанной с клавиатуры. Таким образом получается одна строка, содержащая много таких разделителей.

Если говорить коротко, то: "из множества получаемых строк делаем только одну строку.".

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

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

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

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

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

Единственное, что, по-моему, может быть непонятно, это c_str(). Этот c_str() используют, чтобы получить СИ-строку. Это для перевода объекта, тип которого std::string в тип const char*

string S1 = "Привет";
const char *S2 = S1.c_str();

1 2	string S1 = "Привет"; const char *S2 = S1.c_str();

Нужно это, чтобы можно было работать с функциями, которые работают не со строкой типа string, а со строками типа char*.

Теперь дело за малым. После того как мы считали данные с клавиатуры? у наc сразу посчитано количество строчек? и мы можем обратиться к любой. Создаем массив типа string, указывая, что в нем столько строчек, сколько мы ввели с клавиатуры? и запихиваем в него данные. Запускаем функцию сортировки и получаем массив строк, отсортированный в нужном виде.

Можно не писать функции склейки строки и вытаскивания нужной, но тогда придется указывать количество вводимых строк. Код будет намного меньше и делать так проще, но показанный пример не может быть бесполезным. В реальности, конечно, это решают другим способом. Но для навыков пригодится. Да и адаптировать его на пример вообще без string не должно составить труда. Тогда вообще решение без STL получается, а это значит, что оно пригодное для старых компиляторов. (Не пробовал, но выглядит так, что совсем мало переделывать).

Рубрика: Массивы, Решения задач, строки, Функции

C++ string Сортировка строк без векторов, мультисетов и без всего подобного

Добавить комментарий Отменить ответ

Поиск

Последние темы

Случайная книга в электронном формате

Последние комментарии

Мета