Сравнение строк
Списки строк содержат записи об однотипных объектах, каждая из которых содержит совокупность данных различных типов (целые, вещественные, символьные и т.д.).
Списки могут содержать записи о преподавателях кафедры, студентах группы, лекарств, входящих в аптечку и т.п..
Поиск сведений об объектах по номеру записи не удобен, потому что он постоянно меняется, по мере добавления или удаления отдельных записей.
В связи с этим, для поиска необходимой записи используют одно из данных, чаще всего символьную строку. Например, строку, содержащую фамилию преподавателя или студента, номер машины и т.д.
Для решения подобных задач требуется сравнивать строки между собой. Функция strcmp( ) позволяет сравнить две строки между собой.
Прототип функции имеет следующую структуру
int strcmp(char *s1, char *s2);
Функция имеет два аргумента, указатели на первую (s1) и вторую (s2) сравниваемые строки.
Сравниваемые строки могут быть разной длины, т.е. иметь различное количество символов.
Функция возвращает значение 0, если две строки полностью идентичны, т.е. все символы первой строки (s1), совпадают с символами второй строки (s2) и, кроме того, длина строк одинакова.
Функция возвращает значение, отличное от нуля, если какие-то символы первой строки не совпали с теми же символами второй строки или если строки не одинаковой длины.
Например, фрагмент программы
…
char *st = “Данные”,
*b = “Переменные”;
if( strcmp( st , b ) = = 0 )
puts(“Строки идентичны.”);
else
puts(“Строки различны.”);
…
позволяет сравнить две символьные строки, на которые указывают указатели st и b. О результате сравнения выдаётся соответствующее сообщение. В данном случае будет выдано сообщение
Строки различны.
т. к. длина строк и их содержимое неодинаковы.
Строки, инициализируемые оператором
char data[ 10 ] = “Сети”,
*dt = “ПЭВМ”;
равны по длине, но отличны по содержимому, поэтому при выполнении фрагмента
…
if( strcmp( data , dt ) = = 0 )
puts(“Строки идентичны.”);
else
puts(“Строки различны.”);
…
на экран также выведется сообщение
Строки различны.
Фрагмент программы
…
char us[40],
ps[11] = “клавиатура”;
while( 1 ) /* заголовок бесконечного цикла */
{
puts(“Какое устройство позволяет вводить данные в ЭВМ?”);
gets( us );
if( strcmp( us , ps ) = = 0 ) /* условие выхода из цикла */
{
printf(“Правильно! %s”, ps);
break; /* выход из цикла */
}
else
puts(“Неверно. Попытайтесь еще раз.”);
}
…
позволяет организовать ввод ответа на вопрос и проверку правильности ответа. Цикл будет завершён только после ввода пользователем правильного ответа – «клавиатура».
Функция strcmp( ) сравнивает строки, а не все элементы массивов, в которых эти строки содержаться. Поэтому, хотя массив us занимает 40 ячеек памяти, а ps только 11 (10 символов строки «клавиатура» и символ конца строки), сравнение выполняется только с той частью массива us, которая заканчивается символом ‘\0’.
ü Внимание ! При сравнении строк функция strcmp( ) различает строчные и прописные буквы. Следовательно, строки “Клавиатура” и “клавиатура” различны и функция strcmp( ) при их сравнении возвратит значение отличное от 0.
При использовании списков строк часто возникает задача их сортировки. Например, фамилии студентов можно упорядочить по алфавиту. Функция strcmp( ) может быть использована для сортировки списков строк.
Рассмотрим подробнее алгоритм работы функции strcmp( ).
Функция получает адреса первых элементов сравниваемых строк и осуществляет посимвольную проверку, анализируя разность кодов текущих символов строк. Если разность равна 0, то символы одинаковы.
Например, символу ‘b’ соответствует код 98. Следовательно,
‘b’ - ‘b’ = 98 – 98 = 0
Если символы одинаковы, то анализируется следующая пара символов строк.
Если разность кодов текущих символов отлична от 0, то символы неодинаковы.
Например, символу ‘c’ соответствует код 99. Следовательно,
‘b’ - ‘c’ = 98 – 99 = -1
или
‘c’ - ‘b’ = 99 – 98 = 1
Если символы неодинаковы, то дальнейшая проверка бессмысленна, т. к. строки уже не идентичны и функция заканчивает работу, возвращая значение последней разности.
Проверка осуществляется, до тех пор, пока не будет достигнут конец одной из строк. В вызывающую функцию возвращается значение последней разности.
Анализ последней разности позволяет установить идентичность строк по длине. Если строки одинаковы, то разность равна 0 (‘\0’ - ‘\0’ = 0). Если не одинаковы (‘\0’ - ‘с’ = -99 или ‘с’ - ‘\0’ = 99) значение последней разности отлично от 0.
Составим пользовательскую функцию my_strcmp( ), которая полностью аналогична стандартной функции strcmp( ):
int my_strcmp(char *s1, char *s2)
{
int res, i = 0; /* текущая разность и индекс */
do /* начало цикла посимвольного анализа строк */
{
res = s1[i] – s2[i]; /* определение разности кодов */
/* текущих символов строк */
i = i + 1;
}while( res = = 0 && s1[ i - 1 ] != 0);
return res; /* возврат значения последней разности */
}
Анализ функции позволяет сделать вывод, что если строки не равны, то функция возвращает значение меньше 0, если код ASCII первого неодинакового символа первой строки меньше чем код ASCII соответствующего символа второй строки, и большее 0, если код символа первой строки больше кода символа второй строки.
Например, оператором
printf(“%d \n”, strcmp(“A”,”A”) );
будет произведено два сравнения, так как каждая строка состоит из двух символов: символа ‘A’ и символа конца строки ‘\0’.
Код ‘A’ - Код ‘A’ = 65 - 65 = 0
Код ‘\0’ - Код ‘\0’ = 0 - 0 = 0
Так как достигнут конец обеих строк, то будет возвращено значение 0, что говорит об идентичности строк.
Оператором
printf(“%d \n”, strcmp(“A”,”B”) );
будет произведено только одно сравнение
Код ‘A’ - Код ‘B’ = 65 – 66 = -1
после чего функция strcmp( ) завершит свою работу и вернет значение, равное -1.
Если поменять местами строки (strcmp(“B”, “A”)), то функция возвратит значение 1 (66 - 65 = 1).
Если сравнить строку “C” со строкой “A”, то функция возвратит значение 2
Код ‘C’ - Код ‘A’ = 67 - 65 = 2
В примере
printf(“%d \n”, strcmp(“Студенты”, “Студент”));
первые семь символов строк совпадают и значения разности кодов равно 0, а сравнение восьмых символов ‘ы’ и ‘\0’ равно
Код ‘ы’ - Код ‘\0’ = 235 - 0 = 235
Таблица кодировки символов упорядочена по алфавиту, т.е. символам ‘A’, ‘B’, ‘C’, …. соответствуют коды 65, 66, 67, …, следовательно функцию strcmp( ), сравнивающую строки по кодам их символов, можно использовать для сортировки.
Составим программу, осуществляющую сортировку в алфавитном порядке фамилий студентов. Список состоит не более чем из 30 фамилий, число символов в фамилии не превышает 20.
#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
#include<string.h>
#define N 30 /* максимальное количество вводимых строк */
#define S 21 /* предельная длина строки, включая символ \0 */
void sort(char *st, int n, int D); /* прототип функции сортировки */
void main(void)
{
char stud[N][S]; /* массив для хранения вводимых строк */
char str_n[6]; /* массив для ввода числа строк в текстовом виде */
int i, n; /* индекс текущей строки и число строк */
printf(“ Введите число студентов (не более %d): ”, N);
gets( str_n );
n = atoi( str_n );
for( i = 0 ; i < n ; i++ ) /* цикл ввода списка */
{
printf(“Введите фамилию %d-го студента: ”, i);
gets(stud[i]);
}
sort(stud[0], n, S); /* вызов функции сортировки */
puts(“Список студентов группы отсортирован по алфавиту”);
for( i = 0 ; i < n ; i++) /* цикл вывода упорядоченного списка */
puts(stud[i]);
getch( );
}
/* Функция сортировки */
void sort(char *st, int n, int D) /* st – указатель на массив строк */
{ /* n – число строк, D – максим. размер */
/* строки для составл. индексн. выраж. */
int i, j;
char buf[80];
for( i = 0 ; i < n ; i++ ) /* цикл перебора строк */
for( j = i + 1 ; j < n ; j++ ) /* цикл определения первой строки */
{ /* в диапазоне от i + 1 до n */
if( strcmp( st + i * D , st + j * D ) > 0 )
{
strcpy( buf , st + i * D ); /* поменяем */
strcpy( st + i * D , st + j * D ); /* строки */
strcpy( st + j * D , buf ); /* местами */
}
}
}
Макроопределение S определяет максимально допустимое число символов фамилии, включая символ конца строки, а макроопределение N – максимально допустимое количество вводимых фамилий. Использование макроопределений позволяет легко внести изменения в программу. Например, если необходимо изменить максимальное допустимое количество фамилий в списке, то изменяется только одна строка программы
#define N 40
а все остальные изменения автоматически внесет препроцессор перед компиляцией.
Запрос ввода фамилии реализован с помощью функции printf( ), что позволило вводить в той же строке фамилию студента.
Функция sort( ) осуществляет сортировку списка, а оператор for( ) с помощью функции puts( ) построчно выводит его на экран дисплея.
Функция sort( ) имеет три аргумента: указатель на массив (st), содержащий список, количество строк (n) и максимальную длину строки (D) для составления индексного выражения, определяющего адрес каждой строки.
Два цикла, входящих в функцию sort( ), позволяет поочередно (внешний цикл) перемещать по алфавиту фамилии (внутренний цикл).
Функция sort( ) работает по алгоритму сортировки в порядке возрастания массива чисел.