C - один из самых популярных языков программирования в мире. Работа со строками - важная часть любой программы на C. В этой статье мы подробно разберем все аспекты сравнения строк в C: от базовых функций до сложных алгоритмов и оптимизаций. Узнаете, как правильно выбрать подход, избежать типичных ошибок и написать эффективный код для сравнения строк. Погружаемся в увлекательный мир строк в C!
Базовые функции сравнения строк в C
Одним из основных способов сравнения строк в C является использование встроенных библиотечных функций. Рассмотрим самые популярные из них.
Функция strcmp()
Эта функция определена в заголовочном файле string.h и является основным способом сравнения строк в C.
Синтаксис выглядит так:
int strcmp(const char *str1, const char *str2);
strcmp сравнивает две строки посимвольно, сравнивая коды символов. Возвращает 0, если строки одинаковы, положительное число, если str1 > str2, и отрицательное, если str1 < str2.
char str1[] = "hello"; char str2[] = "hello"; int result = strcmp(str1, str2); // 0 char str3[] = "apple"; char str4[] = "banana"; result = strcmp(str3, str4); // отрицательное число Таким образом strcmp удобно использовать для сравнения слов в лексикографическом порядке.
Другие функции сравнения
Помимо strcmp(), есть и другие полезные функции:
- strncmp() - сравнивает первые n символов строк
- strcoll() - сравнивает строки с учетом правил локали
- memcmp() - сравнивает определенное количество байт в памяти
Эти функции полезны в специфических случаях, например при сравнении подстрок или строк на разных языках.
Сравнение строк без функций
Сравнить строки в C можно и без использования специальных функций. Рассмотрим два распространенных способа.
Посимвольное сравнение в цикле
Можно написать простой цикл, который будет сравнивать символы строк:
int compareStrings(char *str1, char *str2) { int i = 0; while(str1[i] != '\0' && str2[i] != '\0') { if(str1[i] < str2[i]) return -1; if(str1[i] > str2[i]) return 1; i++; } return 0; } Этот подход прост в реализации, но менее эффективен при работе с большими строками.
Использование указателей
Другой вариант - сравнивать строки при помощи указателей:
int stringCmp(char *str1, char *str2) { while(*str1 && *str2) { if(*str1 != *str2) return *str1 - *str2; str1++; str2++; } return 0; } Здесь мы получаем символы по указателям и сравниваем их коды.
Оптимизация сравнения строк
При работе с очень большими строками стандартные функции могут работать неэффективно. Давайте рассмотрим способы оптимизации.
Хеширование строк
Один из подходов - вычислить хеш-коды строк и сравнить их. Это значительно быстрее прямого сравнения символов.
unsigned long hash(char *str) { unsigned long hash = 5381; int c; while (c = *str++) hash = ((hash << 5) + hash) + c; return hash; } bool stringEquals(char *s1, char *s2) { return hash(s1) == hash(s2); } Главный минус - возможность коллизий хешей.
Алгоритм Кнута-Морриса-Пратта
Этот алгоритм использует заранее построенную таблицу частичного совпадения, чтобы пропускать символы в строке. Это позволяет достичь линейной сложности алгоритма.
int KMPSearch(char *txt, char *pat) { int n = strlen(txt); int m = strlen(pat); // создаем таблицу префиксов int lps[m]; computeLPSArray(pat, m, lps); int i = 0; int j = 0; while (i < n) { if (pat[j] == txt[i]) { j++; i++; } if (j == m) { return i-j; } // несовпадение, используем таблицу else if (i < n && pat[j] != txt[i]) { if (j != 0) j = lps[j-1]; else i = i+1; } } return -1; } Типичные ошибки при сравнении строк
Рассмотрим распространенные ошибки, которые встречаются при сравнении строк в Си.
Неверная обработка результата функций
Например, если перепутать порядок сравнения:
if(strcmp(str1, str2) > 0) { // на самом деле надо наоборот } Или неправильно интерпретировать 0 как равенство строк.
Проблемы с регистром символов
По умолчанию Си чувствителен к регистру. Нужно явно преобразовывать символы:
for(int i = 0; str[i]; i++) str[i] = tolower(str[i]); Неизвестная кодировка
Строки в Си обычно в ASCII. При работе с Unicode нужно использовать специальные функции mbscmp().
Мы рассмотрели различные способы сравнения строк в Си - от простых встроенных функций до сложных алгоритмов. Для оптимального решения нужно учитывать особенности данных и задачи. Тщательное тестирование поможет избежать типичных ошибок.
