Двухмерный массив. Пузырьковая сортировка строк

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

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

Эта тема связана с темой:

Пример пузырьковой сортировки массива, хранящего числа

Код пузырьковой сортировки массива символьных строк:

//clang    Пузырьковая сортировка массива строк     Листинг #1
 #include <iostream>
#include <string.h>
#include <windows.h>

 using namespace std;


int main(){
    /*ЗАДАНИЕ ДАННЫХ ДЛЯ ПОСТРОЕНИЯ МАССИВА СТРОК*/
    const int COUNT_OF_STRINGS = 5;                     //Число строк
    const int MAX_STRING_LEN = 256;                     //Длина строк
    char S[COUNT_OF_STRINGS][MAX_STRING_LEN] = {};      //Двумерный массив строк
    /*КОНЕЦ ЗАДАНИЯ ДАННЫХ ДЛЯ ПОСТРОЕНИЯ*/

    char temp[MAX_STRING_LEN] = {}; //Буфер для хранения строки, при обмене значениями ячейками строк

    /*ВВОДИМ СТРОКИ*/
    cout << "input " << COUNT_OF_STRINGS << " strings" << '\n';
    for (int i=0; i<COUNT_OF_STRINGS; i++){
        cin.getline(S[i], MAX_STRING_LEN);      //Чтение строки с клавиатуры и
                                                //сохранение её в массив
    }
    /*КОНЕЦ ВВОДА СТРОК*/

    /*ПУЗЫРЬКОВАЯ СОРТИРОВКА МАССИВА СТРОК*/
    for (int i = 1; i<COUNT_OF_STRINGS; i++){
        for (int j = 0; j<COUNT_OF_STRINGS-1; j++){
            if (strcmp(S[i],S[j]) > 0){                 //Для сравнения строк задействована специальная функция
                //обмен ячеек значениями
                strcpy(temp,S[i]);
                strcpy(S[i],S[j]);
                strcpy(S[j],temp);
                //КОнец обмена
                //Обмен можно написать в одну строчку: swap(S[i],S[j]);
            }
        }
    }
    /*КОНЕЦ СОРТИРОВКИ*/

    /*ВЫВОД СТРОК НА ЭКРАН*/
    for (int i=0; i<COUNT_OF_STRINGS; i++){
        cout << S[i] << '\n';
    }
    /*КОНЕЦ ВЫВОДА СТРОК*/

    cin.get();
}

//clang Пузырьковая сортировка массива строк Листинг #1

#include <iostream>

#include <string.h>

#include <windows.h>

using namespace std;

int main(){

/*ЗАДАНИЕ ДАННЫХ ДЛЯ ПОСТРОЕНИЯ МАССИВА СТРОК*/

const int COUNT_OF_STRINGS = 5; //Число строк

const int MAX_STRING_LEN = 256; //Длина строк

char S[COUNT_OF_STRINGS][MAX_STRING_LEN] = {}; //Двумерный массив строк

/*КОНЕЦ ЗАДАНИЯ ДАННЫХ ДЛЯ ПОСТРОЕНИЯ*/

char temp[MAX_STRING_LEN] = {}; //Буфер для хранения строки, при обмене значениями ячейками строк

/*ВВОДИМ СТРОКИ*/

cout << "input " << COUNT_OF_STRINGS << " strings" << '\n';

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

cin.getline(S[i], MAX_STRING_LEN); //Чтение строки с клавиатуры и

//сохранение её в массив

}

/*КОНЕЦ ВВОДА СТРОК*/

/*ПУЗЫРЬКОВАЯ СОРТИРОВКА МАССИВА СТРОК*/

for (int i = 1; i<COUNT_OF_STRINGS; i++){

for (int j = 0; j<COUNT_OF_STRINGS-1; j++){

if (strcmp(S[i],S[j]) > 0){ //Для сравнения строк задействована специальная функция

//обмен ячеек значениями

strcpy(temp,S[i]);

strcpy(S[i],S[j]);

strcpy(S[j],temp);

//КОнец обмена

//Обмен можно написать в одну строчку: swap(S[i],S[j]);

}

/*КОНЕЦ СОРТИРОВКИ*/

/*ВЫВОД СТРОК НА ЭКРАН*/

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

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

}

/*КОНЕЦ ВЫВОДА СТРОК*/

cin.get();

}

По коду можно легко увидеть, что для сравнения строк используется функция strcmp, а для перестановки ячеек вместо привычного знака присваивания используется функция strcpy, которая копирует одну строку в другую. Для временного хранения строки нужно задавать отдельную переменную, эту роль выполняет символьная строка temp.

Можно немного изменить этот код таким образом, чтобы ёмкость массива символьных строк можно было указывать в ходе работы программы:

//clang     Пузырьковая сортировка массива символьных строк     Листинг #2
#include <iostream>
#include <сstring>

 using namespace std;


int main(){
    /*ЗАДАНИЕ ДАННЫХ ДЛЯ ПОСТРОЕНИЯ МАССИВА СТРОК*/
    int COUNT_OF_STRINGS = 0;                     //Число строк (будет задаваться при работе программы)
    const int MAX_STRING_LEN = 256;                     //Длина строк
    char *S[MAX_STRING_LEN] = {};      //Двумерный массив строк
    /*КОНЕЦ ЗАДАНИЯ ДАННЫХ ДЛЯ ПОСТРОЕНИЯ*/

    char temp[MAX_STRING_LEN] = {}; //Буфер для хранения строки, при обмене значениями ячейками строк

    cout << "input count for string: ";     //Диалог: сколько строк массив буде хранить
    (cin >> COUNT_OF_STRINGS).ignore();     //Вводим количество (при работе программы)

    /*ВЫДЕЛЯЕМ ПАМЯТЬ ДЛЯ КАЖДОЙ СТРОКИ*/
        for (int i=0; i<COUNT_OF_STRINGS; i++){
            S[i] = new char[MAX_STRING_LEN];
        }
    /*КОНЕЦ ВЫДЕЛЕНИЯ ПАМЯТИ*/

    /*ВВОДИМ СТРОКИ*/
    cout << "input " << COUNT_OF_STRINGS << " strings" << '\n';
    for (int i=0; i<COUNT_OF_STRINGS; i++){
        cin.getline(S[i], MAX_STRING_LEN);      //Чтение строки с клавиатуры и
                                                //сохранение её в массив
    }
    /*КОНЕЦ ВВОДА СТРОК*/

    /*ПУЗЫРЬКОВАЯ СОРТИРОВКА МАССИВА СТРОК*/
    for (int i = 1; i<COUNT_OF_STRINGS; i++){
        for (int j = 0; j<COUNT_OF_STRINGS-1; j++){
            if (strcmp(S[i],S[j]) > 0){     //Функция сравнения двух строк
                //обмен ячеек значениями
                strcpy(temp,S[i]);
                strcpy(S[i],S[j]);
                strcpy(S[j],temp);
                //КОнец обмена
                //Обмен можно написать в одну строчку: swap(S[i],S[j]);
            }
        }
    }
    /*КОНЕЦ СОРТИРОВКИ*/

        cout << '\n';

    /*ВЫВОД СТРОК НА ЭКРАН*/
    for (int i=0; i<COUNT_OF_STRINGS; i++){
        cout << S[i] << '\n';
    }
    /*КОНЕЦ ВЫВОДА СТРОК*/

    /*СТРОКИ БОЛЬШЕ НЕ НУЖНЫ, ЧИСТИМ ПАМЯТЬ*/
        for (int i=0; i<MAX_STRING_LEN; i++){
            delete []S[i];
        }
    /*КОНЕЦ ОЧИСТКИ ПАМЯТИ*/

    cin.get();
}

//clang Пузырьковая сортировка массива символьных строк Листинг #2

#include <iostream>

#include <сstring>

using namespace std;

int main(){

/*ЗАДАНИЕ ДАННЫХ ДЛЯ ПОСТРОЕНИЯ МАССИВА СТРОК*/

int COUNT_OF_STRINGS = 0; //Число строк (будет задаваться при работе программы)

const int MAX_STRING_LEN = 256; //Длина строк

char *S[MAX_STRING_LEN] = {}; //Двумерный массив строк

/*КОНЕЦ ЗАДАНИЯ ДАННЫХ ДЛЯ ПОСТРОЕНИЯ*/

char temp[MAX_STRING_LEN] = {}; //Буфер для хранения строки, при обмене значениями ячейками строк

cout << "input count for string: "; //Диалог: сколько строк массив буде хранить

(cin >> COUNT_OF_STRINGS).ignore(); //Вводим количество (при работе программы)

/*ВЫДЕЛЯЕМ ПАМЯТЬ ДЛЯ КАЖДОЙ СТРОКИ*/

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

S[i] = new char[MAX_STRING_LEN];

}

/*КОНЕЦ ВЫДЕЛЕНИЯ ПАМЯТИ*/

/*ВВОДИМ СТРОКИ*/

cout << "input " << COUNT_OF_STRINGS << " strings" << '\n';

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

cin.getline(S[i], MAX_STRING_LEN); //Чтение строки с клавиатуры и

//сохранение её в массив

}

/*КОНЕЦ ВВОДА СТРОК*/

/*ПУЗЫРЬКОВАЯ СОРТИРОВКА МАССИВА СТРОК*/

for (int i = 1; i<COUNT_OF_STRINGS; i++){

for (int j = 0; j<COUNT_OF_STRINGS-1; j++){

if (strcmp(S[i],S[j]) > 0){ //Функция сравнения двух строк

//обмен ячеек значениями

strcpy(temp,S[i]);

strcpy(S[i],S[j]);

strcpy(S[j],temp);

//КОнец обмена

//Обмен можно написать в одну строчку: swap(S[i],S[j]);

}

/*КОНЕЦ СОРТИРОВКИ*/

cout << '\n';

/*ВЫВОД СТРОК НА ЭКРАН*/

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

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

}

/*КОНЕЦ ВЫВОДА СТРОК*/

/*СТРОКИ БОЛЬШЕ НЕ НУЖНЫ, ЧИСТИМ ПАМЯТЬ*/

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

delete []S[i];

}

/*КОНЕЦ ОЧИСТКИ ПАМЯТИ*/

cin.get();

}

Чтобы появилась возможность задавать ёмкость во время работы программы, мы стали использовать указатели, точнее массив указателей. Массив указателей выступает в роли массива строк, а сколько указателей, т. е. строк должен уметь хранить массив, мы смогли указывать в ходе работы программы.

При смешанном вводе (числовые значения — строковые значения) иногда необходимо игнорировать символ перевода строки, остающийся в потоке ввода после нажатия клавиши Enter, из-за этого после ввода числового значения, но перед вводом строкового значения был использован метод ignore, который вам может быть или непонятен, или плохо понятен. Этот метод используется, чтобы перескочить нажатую клавишу Enter. Вы можете убрать, посмотреть, что получится, если этот след от нажатия клавиши Enter остаётся.

Рубрика: Без рубрики