Составление алгоритма решения. Математическая формулировка задачи и выбранный детализированный метод ее решения позволяют создать одношаговую схему алгоритма решения (рис
Математическая формулировка задачи и выбранный детализированный метод ее решения позволяют создать одношаговую схему алгоритма решения (рис. 9.17).
Рис. 9.17. Схема алгоритма сортировки массива символьных строк модифицированным методом «всплывающего пузырька»
Анализ выполненного алгоритма показывает его полную идентичность алгоритму сортировки символов в строке. Отличительная особенность – содержимое блока проверки условия (сравнение двух строк, а не сравнение двух символов). Вывод исходных и получаемых сортировкой строк предусматривается отдельными последовательно выполненными циклами.
Программирование задачи
Трудоемкая процедура последовательной сортировки существенно упрощается при использовании специальных функций языка Си/Си++, осуществляющих сравнение строк целиком и копирование их.
Функция сравнения символьных строк strcmp( )
Предназначена для посимвольного сравнения двух строк. Структура функции:
strcmp( buf1, buf2 )
где strcmp – обозначение функции (сравнение строк);
buf1, buf2 – сравниваемые аргументы;
( ) – ограничители аргументов.
Функция располагается в библиотеке string.h.
Правила записи и использования
1. В качестве аргументов используются имена сравниваемых строк (buf1 и buf2).
2. Длина сравниваемых строк buf1 и buf2 может быть различной.
3. Окончание строк buf1 и buf2 – символ «\0» в каждой.
4. Сравнение осуществляется попарно, начиная с первых символов.
5. Если символы одинаковы (коды равны), происходит переход к следующей паре символов анализируемых строк.
6. Если код символа первой строки отличается от кода символа второй, сравнение завершается.
7. Результат работы функции – разность кодов последнего сравнения (нуль, если все символы строк одинаковы, положительное число, если код последнего сравниваемого символа первой строки, больше кода второй или отрицательное – в противном случае).
8. Функция используется как операнд арифметического или логического выражения (присваивания или сравнения).
Пример фрагмента программы сравнения символьных строк buf и str:
#include <string.h> /* директива препроцессора*/
…
char str[25], buf[10]; /*описатель символьных строк*/
int result; /* описатель переменной для хранения результата сравнения строк*/
…
EditStr->GetText(str, 12); /*ввод str из поля EditStr*/
EditBuf->GetText(buf, 10); /*ввод buf из поля EditBuf*/
result = strcmp(str, buf); /*формирование результата сравнения строк buf и str*/
…
Описатель типа определяет массивы str и buf как символьные максимальной длины 25 и 10 символов. Шестая и седьмая строки предписывают ввод str и buf из поля EditStr и EditBuf соответственно. Восьмая строка осуществляет посимвольное сравнение введенных строк str и buf и присваивает результат сравнения переменной целого типа result.
Функция копирования символьных строк strcpy( )
Функция предназначена для копирования содержимого исходной строки в формируемую. Используется как аналог операции присваивания, если операнды – символьные строки. Структура функции:
strcpy( buf1, buf2 )
где strcpy – обозначение функции;
buf1 – имя формируемой символьной строки;
buf2 – имя копируемой исходной символьной строки;
( ) – ограничители аргумента.
Функция располагается в библиотеке string.h.
Правила записи и использования
1. Строка buf2 должна заканчиваться символом «\0».
2. Функция посимвольно считывает строку buf2 и копирует её в строку buf1. Считывание завершается по символу «\0» (он копируется последним).
3. Размеры строк-операндов функции должны быть заданы в описателе (длина результирующей должна быть не меньше исходной).
4. Проверка результирующей строки на переполнение не выполняется.
5. Функция используется как операнд арифметического выражения (присваивания) или самостоятельный оператор.
Общий вид фрагмента программы копирования символьных строки buf в str:
#include <string.h> /* директива препроцессора*/
…
char str[25] = “ ”, buf[10]; /*описатель символьных строк*/
…
EditBuf->GetText(buf, 10); /*ввод buf из поля EditBuf*/
strcpy(str, buf); /*формирование результирующей строки str копированием исходной строки buf*/
…
Описатель типа определяет массивы str и buf как символьные максимальной длины 25 и 10 символов соответственно и идентифицирует массив str как пустой. Пятая строка предписывает ввод buf из поля EditBuf. Оператор strcpy(str, buf); формирует строку str, копированием содержимого строки buf.
С учетом изложенного, выполним идентификацию переменных и программирование задачи.
Таблица идентификации переменных алгоритма и создаваемой программы представлена в табл. 9.7.
Таблица 9.7
| Обозначение в алгоритме | стрпр | n | i | j | стрi | стрj |
| Обозначение в программе | strpr | n | i | j | str[i] | str[j] |
Классический вариант программирования задачи
#include<stdio.h>
#include<stdlib.h>
#include<windows.h>
#include<conio.h>
#include<string.h>
#define N 25
main()
{
int i,j,n; /* описание локальных переменных */
char str[N][30], strpr[30], /*описание символьных*/
buf[40]; /*массивов*/
clrscr();
for(i=0 ; i < N; i++)
{
CharToOem(" Введите строку ",buf);
printf("\n %s[%d] ",buf,i+1); /* ввод*/
gets(str[i]); /* текущей*/
if(str[i][0] == '\0') /*строки массива*/
break;
else
n = i + 1;
}
CharToOem(" \n Исходный массив А\n", buf);
printf("%s",buf);
for(i=0;i<n;i++)
printf(" %s \n ",str[i]);
for (i=0; i< n-1; i++)/* заголовок внешн. цикла сортировки */
for(j=i+1; j<n; j++) /* заголовок внутр. цикла сортировки */
if(strcmp(str[i],str[j]) >0)
{
strcpy(strpr, str[i]);
strcpy(str[i], str[j]);
strcpy(str[j],strpr);
}
CharToOem(" \n Отсортированный массив А \n",buf);
printf("%s",buf);
for(i=0;i<n;i++)
printf(" %s \n ",str[i]);
getch();
}
Матвеев М.В.
Юдин С.П.
Лебедев В.Н.
Петров К.П.
Федосеев В.Г.
Под закрывающей скобкой приведены исходные данные для решения задачи.
Результаты решения представлены в приложении 9.13.
Программирование задачи с графическим интерфейсом
Программирование задачи при использовании графического интерфейса предварим его разработкой.
|
Для ввода массива строк планируем многострочное поле редактирования (EditStr). Для вывода отсортированного массива строк – поле-список (ListBoxSortStr).
Управление процессом решения реализуем двумя командными кнопками, расположенными в нижней части окна. Назначение каждой определяется ее названием.
С учетом планируемого интерфейса выполним программирование задачи.
#include<stdio.h>
#include<stdlib.h>
#include <string.h>
#define N 25
void TVrDlgClient::BNClickedOk()
{
// INSERT>> Your code here.
int i,j,n; /* описание локальных переменных */
char str[N][30],strpr[30] ; /*описание символьных массивов*/
ListBoxSortStr->ClearList();
for(i=0 ; i < N; i++)
{
EditStr->GetLine(str[i],30,i); /* ввод*/
if(str[i][0] == '\0') /* текущей строки массива*/
break;
else
n = i + 1;
}
for (i=0; i< n-1; i++)/* заголовок внешн. цикла сортировки */
for(j=i+1; j<n; j++) /* заголовок внутр. цикла сортировки */
if(strcmp(str[i],str[j]) >0)
{
strcpy(strpr, str[i]);
strcpy(str[i], str[j]);
strcpy(str[j],strpr);
}
for (i=0; i< n; i++)/* заголовок внешн. цикла вывода */
ListBoxSortStr->AddString(str[i]); /* вывод строки массива*/
}
Матвеев М.В.
Юдин С.П.
Лебедев В.Н.
Петров К.П.
Федосеев В.Г.
Под закрывающей скобкой приведены исходные данные для решения задачи.
Результаты решения представлены в приложении 9.14.
Заключение
Вычисления с вложенными циклами – процесс, в котором хотя бы один цикл расположен внутри другого.
Вложенный (внутренний) – цикл, расположенный внутри другого.
Внешний (наружный) – цикл, внутри которого располагаются другие циклы.
При многократном вложении циклов некоторые из них могут быть внутренними и внешними одновременно.
Разновидности вложенных циклов определяет форма их расположения:
· последовательно размещенные;
· параллельно размещенные.
Последовательно размещенные (вложенные) циклы – структура, в которой каждый следующий цикл полностью расположен внутри предыдущего (другого);
Параллельно размещенные (вложенные) циклы – структура, во внешнем цикле которой два или более цикла расположены один под другим.
Типовое использование последовательно вложенных циклов – обработка многомерных массивов и преобразования одномерных массивов (сортировка элементов).
Двумерный массив представляется в виде таблицы (матрицы), при этом первое измерение определяет строку, второе – столбец. Каждый элемент двумерного массива имеет два индекса. Первый задает номер строки, второй – номер столбца элемента в таблице.
Трехмерный массив – последовательная совокупность одинаковых по структуре таблиц (страниц книги). Каждый элемент такого массива имеет три индекса, первый из которых определяет номер страницы, второй – номер строки, третий – номер столбца, где расположен элемент.
Индексированная переменная (индексное выражение) – обозначение ячейки для хранения конкретного элемента массива указанием идентификатора массива и индексов элемента по каждому измерению.
В массивах Си/Си++ индексы элементов на единицу меньше заданных математически.
Ранжирование – размещение элементов некоторой совокупности данных по убыванию (возрастанию) их численных значений (кодов).
Под совокупностью данных может пониматься как числовая, так и символьная информация.
В математике разработаны различные методы сортировки числовых массивов по убыванию и возрастанию.
Особенность цифровых вычислительных машин – представление любой информации конкретными цифровыми комбинациями – кодами.
В кодовой таблице ASCII ANSI символы обозначаются десятичными триадами от 000 до 255. Традиционное расположение их в таблице – по возрастанию кодов:
· специальные символы;
· цифры;
· прописные буквы латинского алфавита (A – Z);
· строчные буквы латинского алфавита (a – z);
· прописные буквы русского алфавита (А – Я);
· строчные буквы русского алфавита (а – я).
Это позволяет организовать сравнение и перебор символьной информации (ее кодов) не только по каждой из позиций, но и их совокупностей.
Возможно ранжирование символьной информации в двух вариантах: символов в строке и строк в массиве.
Предложенные алгоритмы универсальны – пригодны для ранжирования числовой и символьной информации.
Вложенные циклы – инструмент организации смешанных вычислительных процессов. Эффективность использования вложенных циклов бесспорна.
Вопросы для контроля
1. Что представляет собой вычислительный процесс с вложенными циклами?
2. Какой цикл называют внешним, а какой внутренним?
3. Как схематично представить последовательно или параллельно вложенные циклы?
4. Как схематично представить смешанный вариант вложенных циклов?
5. Какова структура оператора описания многомерного массива?
6. Что такое индексированная переменная?
7. Как схематично представить распределение оперативной памяти для хранения двумерного и трехмерного массивов?
8. Какова структура обозначения индексированной переменной многомерного массива?
9. Как ввести индексированную переменную многомерного массива?
10. Как рассчитать адрес текущего элемента многомерного массива?
11. Как рассчитать смещение в индексном выражении для определения адреса элемента в двумерном и трёхмерном массивах?
12. Чем отличаются увеличенные и фактические размеры массива?
13. Какие размеры массива указываются в индексном выражении?
14. Что такое ранжирование (сортировка)?
15. Как схематично представить основные методы ранжирования информации?
16. Каковы основные методы ранжирования?
17. В чем особенность ранжирования символьной информации?