WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!

Pages:     | 1 | 2 || 4 |

«МИНИСТЕРСТВО ОБРАЗОВАНИЯ РЕСПУБЛИКИ БЕЛАРУСЬ УЧРЕЖДЕНИЕ ОБРАЗОВАНИЯ «БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИНФОРМАТИКИ И РАДИОЭЛЕКТРОНИКИ» Кафедра информатики А.А. Мелещенко Основы ...»

-- [ Страница 3 ] --

выделит ровно 16 байтов памяти кучи, скопирует в эту область памяти 15 символьную строку «Двойная тревога» плюс завершающий нуль и возвратит адрес этой области. По окончании работы со строкой следует освободить эту область памяти обычным способом:

free(s);

Предупреждение. Вы можете модифицировать строки, создаваемые функцией strdup(), но при этом не должны расширять их за пределы отведенных им объемов памяти. Если все-таки это необходимо сделать, скопируйте вашу строку в новый, больший по размеру буфер, зарезервированный функцией malloc(), после чего освободите память, которую строка занимала ранее.

Листинг 5.6 представляет собой основную программу, которая использует функцию GetStringAt(), объявленную в файле gets.h и описанную в модуле gets.c. Чтобы создать работающую программу, вы должны скомпоновать эти модули вместе. Для этого откройте новый файл проекта, добавьте в него модули duped.c и gets.c, а затем выберите команду Run в вашей среде программирования. Эта команда: 1) скомпилирует модуль gets.c, создавая объектный файл с именем gets.obj, 2) скомпилирует модуль duped.c и создаст объектный файл duped.obj, 3) скомпонует эти два объектных файла и 4) создаст файл duped.exe, который вы можете запускать на исполнение.

Листинг 5.6. duped.c (использование функции GetStringAt()) 1: #include 2: #include 3: #include 4: #include 5: #include "gets.h" 6:

7: #define PROMPT "String: " /* приглашение на ввод */ 8:

9: main() 10: { 11: char *s;

/* указатель на результат функции GetStringAt()*/ 12:

13: clrscr();

14: printf(PROMT);

15: s = GetStringAt(MAXLEN);

16: if (s) { 17: puts("Your entry is: ");

18: puts(s);

19: printf("Length = %d characters\n", strlen(s));

20: free(s);

21: } else 22: puts("Error duplicating string!");

23: return 0;

24: } Строка 15 вызывает функцию GetStringAt(), передавая ей в виде параметра максимальную длину строки. В строке 16 программа проверяет результат функции GetStringAt(). Если она возвращает нуль, это значит, что функция strdup() не смогла создать копию строки, возможно, из-за недостатка памяти в куче. Обратите внимание также на освобождение памяти в строке 20 после того, как строка оказывается больше не нужной.

Упражнение. Создайте рекурсивную версию функции GetStringAt().

Сравнение строк С помощью функции GetStringAt() вы можете написать программу, которая предлагает ввести пароль. Чтобы определить, правильный ли вы ввели пароль, листинг 5.7 вызывает функцию strcmp(), которая сравнивает две строки.

Программа password вызывает функцию GetStringAt() из модуля gets.c. Чтобы создать исполняемый файл, вы должны скомпоновать программу с этим модулем. Для компиляции, компоновки и выполнения программы откройте файл проекта под именем password, добавьте в него модули password.c и gets.c, а затем выполните команду Run. (Если программа не запуститься, попробуйте команду Build All. Проверьте также имена маршрутов каталогов в проекте).

Чтобы программа password успешно завершилась, введите пароль “Informatics” с учетом прописных и строчных букв. Если вы введете пароль неправильно, программа отобразит сообщение об ошибке и потребует начать сначала.

Листинг 5.7. password.c (предложение ввести пароль) 1: #include 2: #include 3: #include 4: #include 5: #include "gets.h" 6:

7: #define FALSE 8: #define TRUE 9: #define PASSWORD "Informatics" 10: #define PROMPT "Enter password: " 11:

12: main() 13: { 14: char *s;

15: int done = FALSE;

16:

17: clrscr();

18: while (!done) { 19: printf(PROMPT);

20: s = GetStringAt(MAXLEN);

21: clrscr();

22: if (!s) { 23: puts("Error: Out of memory");

24: return 1;

25: } else { 26: done = (strcmp(s, PASSWORD) == 0);

27: if (!done) 28: puts("Error in password! Type "PASSWORD" to quit");

29: free(s);

/* освобождаем память */ 30: } 31: } 32: clrscr();

33: puts("Correct password given");

34: return 0;

35: } В строке 26 показано, как сравнивать две строки. Оператор done = (strcmp(s, PASSWORD) == 0);

устанавливает переменную done равной значению «истина», если строка, адресуемая указателем s, равна строке “Informatics”, представленной константой PASSWORD.

Если i – переменная типа int, и если s1 и s2 – указатели на char, то оператор i = strcmp(s1, s2);

установит i равной –1 или другому отрицательному числу, если строка, адресуемая указателем s1, в алфавитном порядке меньше строки, адресуемой указателем s2. Если строки в точности совпадают, функция возвратит нуль.

Если строка s1 в алфавитном порядке больше строки s2, она вернет +1 или другое положительное число.

Функция strcmp() чувствительна к регистру букв – при сравнении строчные буквы считаются большими, чем их прописные эквиваленты (так как буквы нижнего регистра имеют большие ASCII-значения, чем буквы верхнего регистра). Для сравнения двух строк без учета регистра вызовите функцию stricmp(). Буква i означает «ignore case» («игнорировать регистр»).

Эта функция действует аналогично функции strcmp(), но перед сравнением преобразует все буквы в прописные. Например, если сравнение выполнять с помощью функции strcmp(), то строка “Apple” алфавитно окажется меньше строки “apple”. Если же для сравнения использовать функцию stricmp(), эти строки будут считаться идентичными.

Чтобы сравнить только часть двух строк, используйте функцию strncmp(). Например, оператор i = strncmp(s1, s2, 2);

установит целую переменную i равной нулю только в том случае, если первые два символа строк, адресуемых указателями s1 и s2, в точности совпадают. Для сравнения части строк без учета регистра вызывайте функцию strnicmp().

Конкатенация строк Конкатенация двух строк означает их соединение, при этом создается новая, более длинная строка. При объявлении строки char original[128] = "Проверка ";

оператор strcat(original, "связи");

превратит первоначальную строку original в “Проверка связи”.

При вызове функции strcat() убедитесь, что первый аргумент типа char * инициализирован и имеет достаточно места, чтобы запомнить результат, в противном случае может возникнуть серьезная ошибка.

Функция strcat() возвращает адрес результирующей строки (совпадающий с ее первым параметром) и может использоваться как каскад нескольких вызовов функций:

strcat(strcat(s1, s2), sЗ);

Этот оператор добавляет строку, адресуемую s2, и строку, адресуемую s3, к строке, адресуемой sl, что эквивалентно двум отдельным операторам:

strcat(s1, s2);

strcat(s1, sЗ);

Листинг 5.8 показывает, как использовать функцию strcat() для решения типичной проблемы – получения полного имени человека из фамилии, имени и отчества, запомненных по отдельности, например в базе данных. Скомпилируйте программу concat аналогично предыдущим примерам: откройте новый файл проекта, добавьте в него модули concat.c и gets.c и запустите программу на исполнение. Введите фамилию, имя и отчество. Программа соединит введенные вами строки и отобразит имя как одну строку.

Листинг 5.8. concat.c (конкатенация строк) 1: #include 2: #include 3: #include 4: #include 5: #include 6: #include "gets.h" 7:

8: char *PromptFor(char *prompt);

9:

10: main() 11: { 12: char *firstName;

13: char *middleName;

14: char *lastName;

15: char fullName[128];

16:

17: clrscr();

18: firstName = PromptFor("first name");

19: middleName = PromptFor("middle name");

20: lastName = PromptFor("last name");

21: strcpy(fullName, firstName);

22: strcat(fullName, " ");

23: strcat(fullName, middleName);

24: strcat(fullName, " ");

25: strcat(fullName, lastName);

26: printf ("Your name is: %s", fullName);

27: free(firstName);

/* освобождает */ 28: free(middleName);

/* выделенную */ 29: free(lastName);

/* память */ 30: return 0;

31: } 32:

33: char *PromptFor(char *prompt) 34: { 35: char *temp;

/* временный строковый указатель */ 36:

37: printf("Enter your %s: ", prompt);

38: temp = GetStringAt(MAXLEN);

39: if (!temp) { 40: puts("\nError: Out of memory");

41: exit(1);

42: } 43: return temp;

44: } Строки 21-25 демонстрируют важный принцип конкатенации строк:

всегда инициализируйте первый строковый аргумент. В данном случае символьный массив fullName инициализируется вызовом функции strcpy(), которая копирует символы firstName в fullName. После этого программа добавляет пробелы и две другие строки – middleName и lastName.

Функция PromptFor (строки 33-44) выводит приглашение и возвращает строку, введенную пользователем. Кроме того, функция PromptFor демонстрирует способ обработки исключительных ситуаций.

Если функция GetStringAt() не сможет выделить память в куче и вернет NULL, то в строке 41 будет вызвана функция exit(), которая немедленно завершит программу и вернет операционной системе некоторое значение, позволяющее идентифицировать ошибку.

Если вы не уверены в том, что в строке достаточно места для присоединяемых подстрок, вызовите функцию strncat(), которая аналогична функции strcat(), но требует дополнительного аргумента, определяющего число копируемых символов. Для строк s1 и s2, которые могут быть либо указателями типа char *, либо символьными массивами, оператор strncat(s1, s2, 4);

присоединяет максимум четыре символа из s2 в конец строки s1. Результат обязательно завершается нулевым символом.

Поиск элементов строк Программам часто приходится выполнять поиск символов в строках.

Распространенный пример – проверка имен файлов на заданное расширение.

Например, после того как пользователю предложили ввести имя файла, проверяется, ввел ли он расширение “.txt”, и если это так, то выполняется заданное действие.

Поиск символов Листинг 5.9 показывает, как использовать функцию strchr() для поиска отдельных символов в строке.

Листинг 5.9. ext1.c (проверка расширения файла, пример 1) 1: #include 2: #include 3:

4: main() 5: { 6: char fileName[128];

7:

8: printf("Enter file name: ");

9: gets(fileName);

10: printf("As entered: %s\n", fileName);

11: if (strchr(fileName,.)) 12: printf("File name is probably complete\n");

13: else 14: strcat(fileName, ".txt");

15: printf("Final file name: %s\n", fileName);

16: return 0;

17: } Скомпилируйте и запустите программу ext1, затем введите имя файла с расширением. Например, если вы введете “test.txt”, программа отобразит:

Enter file name: test.txt As entered: test.txt File name is probably complete Final file name: test.txt Но если вы введете “test” без расширения, программа добавит к имени файла расширение:

Enter file name: test As entered: test Final file name: test.txt Программа ext1 находит расширение в имени файла, выполняя поиск символа точки во введенной строке. Ключевым в этой программе является оператор if-else (строки 11-14):

if (strchr(fileName,.)) printf("File name is probably complete\n");

else strcat(fileName, ".txt");

Выражение strchr(fileName, ‘.’) возвращает fileName t указатель на символ точки в строке fileName.

Если такой символ не найден, функция e strchr() возвращает нуль. Поскольку s ненулевые значения означают «истину», вы можете использовать функцию strchr() в t качестве логического выражения в. p операторах if.

t Присвоим указателю p типа char значение, возвращаемое функцией strchr():

x p = strchr(fileName,.);

t Теперь на строку fileName указывают \ два указателя: fileName, адресующий полную строку, и р, адресующий подстроку “.txt” Рис. 5.2. Функция strchr() (рис. 5.2).

находит символ в строке Строковые функции не заботятся о байтах, которые предшествуют их первому символу, поэтому оператор puts(p);

отображает подстроку “.txt” так, будто она полная строковая переменная, а не часть другой строки. Здесь вы должны проявить осторожность. Если строка расположена в куче, то оператор free(fileName);

корректно освобождает занимаемую строкой память, а оператор free(p);

/* ??? */ вызовет трудноуловимую ошибку. Никогда не используйте указатели на подстроки для освобождения памяти, занимаемой целой строкой.

Функция strchr() отыскивает первое появление символа в строке.

Чтобы найти последнее появление, вызовите функцию strrchr(). Операторы char s[] = "Abracadabra";

char р = strrchr(s, b);

установят указатель р равным адресу подстроки “bra” в конце строки “Abracadabra”.

Поиск подстрок Кроме поиска символов в строке, вы можете «поохотиться» и за подстроками. Листинг 5.10 демонстрирует этот метод.

Листинг 5.10. ext2.c (проверка расширения файла, пример 2) 1: #include 2: #include 3:

4: main() 5: { 6: char fileName[128];

7: char *p;

8:

9: printf("Enter file name: ");

10: gets(fileName);

11: printf("As entered: %s\n", fileName);

12: strlwr(fileName);

13: p = strstr(fileName, ".txt");

14: if (p) 15: printf("File name is complete\n");

16: else { 17: p = strchr(fileName,.);

18: if (p) 19: *p = NULL;

/* удалить любое другое расширение */ 20: strcat(fileName, ".txt");

21: } 22: printf("Final file name: %s\n", fileName);

23: return 0;

24: } Новая программа создает имя файла, которое обязательно заканчивается расширением “.txt”. Запустите программу ext2 и введите “test” или “test.txt”, что даст результат, аналогичный программе ext1. Но если вы введете “test.c”, программа ext2 отобразит следующее:

Enter file name: test.с As entered: test.c Final file name: test.txt Чтобы определить, есть ли в имени файла расширение “.txt”, программа выполняет в строке 13 оператор р = strstr(fileName, ".txt");

Подобно strchr(), функция strstr() возвращает адрес искомой подстроки или нуль, если подстрока не найдена. Поскольку расширение может быть введено и прописными буквами, программа выполняет оператор strlwr(fileName);

чтобы перед вызовом функции strstr() преобразовать буквы введенной строки в строчные. Используйте оператор strupr(fileName);

чтобы преобразовать все буквы строки fileName в прописные.

Программа ext2 также демонстрирует способ усечения строки в позиции заданного символа. Строка 17 вызывает функцию strchr(), чтобы установить указатель р равным адресу первой точки в строке fileName. Если результат этого поиска не нулевой (строка 18), строка 19 выполнит оператор, который запишет вместо точки нулевой байт:

*р = NULL;

Теперь строка готова к добавлению нового расширения путем вызова функции strcat() в строке 20.

Упражнение. Модифицируйте программу ext2, чтобы она не использовала функцию strstr() для поиска расширения файла. Другими словами, ваша программа должна заменить расширение файла на “.txt” без обязательного поиска этого расширения.

Разложение строк на подстроки Прикладное программирование часто требует нахождения компонентов строки или лексем – этот процесс называется синтаксическим анализом. Если составные части строки отделены друг от друга запятыми, пробелами или другими разделителями, вы можете использовать мощную функцию strtok() для разложения ее на несколько подстрок.

Рассмотрим следующие объявления:

char s[] = Now I know my ABCs;

char *p1, *p2, *p3, *p4, *p5;

Строковая переменная s инициализирована строкой “Now I know my ABCs”. Пять указателей на тип char пока что не инициализированы – функция strtok() использует эти указатели, чтобы сделать разбор строки.

Сначала вызовите функцию strtok(), передав в качестве первого аргумента указатель на строку, а в качестве второго – разделительный символ:

р1 = strtok(s, );

Функция strtok() возвращает адрес первого компонента строки, отделенного от следующего заданным разделителем (в данном примере – символом пробела) или NULL, если разделитель не обнаружен. Разделителей может быть несколько. Например, чтобы разложить строки на элементы, разделенные запятыми, точками с запятой или пробелами, используйте в качестве второго аргумента строку,;

.

Функция вставляет нулевой байт в позицию первого обнаруженного разделителя. Тем самым создается маленькая подстрока, адрес которой возвращается функцией strtok(). Кроме того, эта функция настраивает свой внутренний указатель на символ, следующий за концом сформированной подстроки, чтобы следующий вызов strtok() мог продолжить разложение строки.

Чтобы выделить другие компоненты строки s, нужно просто несколько раз вызвать функцию strtok() с первым аргументом, имеющим значение NULL:

р2 = strtok(NULL, );

рЗ = strtok(NULL, );

р4 = strtok(NULL, );

р5 = strtok(NULL, );

На рис. 5.3 показана разобранная строка и ее указатели от р1 до р5.

Каждый указатель адресует завершающуюся нулем подстроку внутри первоначальной строки. Каждая из подстрок является отдельной строковой переменной, которую можно передавать строковым функциям, таким как strlen(), strcpy() и strdup().

Замечание. Функция strtok() модифицирует исходную строку, поэтому перед ее разбором убедитесь, что вы сделали копию на случай необходимости использования строки в первоначальном виде.

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

р = strtok(string, ";

");

while (p) { /* обработка подстроки, адресуемой указателем р */ p = strtok(NULL, ";

");

} Сначала указатель р N s устанавливается равным p результату функции strtok(), o которой были переданы указатель w на исходную строку string и Нулевой символ \ разделитель “;

”. Затем цикл while проверяет значение указателя р на I p равенство нулю. Если указатель Нулевой символ \ имеет ненулевое значение, то он адресует очередную подстроку в k p строке buffer, и вы можете n передавать его строковым o функциям. После обработки найденной подстроки внутри w цикла осуществляется попытка Нулевой символ \ поиска других подстрок с p m помощью нового вызова функции strtok(), но теперь со значением y NULL в качестве первого Нулевой символ \ аргумента.

A p Листинг 5.11 показывает, как использовать функцию strtok() для B выделения слов из строки.

C Скомпилируйте и запустите программу. После приглашения s введите строку, состоящую из Первоначальный \ слов, разделенных пробелами.

нулевой символ Операторы в строках 14- Рис. 5.3. Строка после разбора выполнят анализ введенного текста с помощью функции strtok() и отобразят его результаты на экране в виде отдельных слов.

Листинг 5.11. tokens.c (анализ строки слов) 1: #include 2: #include 3:

4: main() 5: { 6: char buffer[128];

7: char *p;

8:

9: printf("Enter a string of words separated by blanks.\n");

10: printf(": ");

11: gets(buffer);

12: printf("As entered: %s\n", buffer);

13: printf("As words (tokens):\n");

14: p = strtok(buffer, " ");

15: while (p) { 16: puts(p);

17: p = strtok(NULL, );

18: } 19: return 0;

20: } Резюме • Строка представляет собой массив значений типа char, заканчивающийся нулевым байтом. Если строка не заполняет полностью выделенную для нее память, то байты, находящиеся после завершающего нуля, остаются неиспользованными.

• Символы строки – это на самом деле целые числа, представляющие собой номера символов в таблице ASCII.

• Строки имеют одну из трех форм: литеральные строки, вводимые непосредственно в текст программы, массивы символов фиксированного размера и указатели типа char *, которые обычно адресуют строки, хранящиеся в куче.

• Нулевая строка не имеет никаких значащих символов, кроме нуля, запомненного в ее первом байте.

• Строки можно использовать для ввода в программу целых и дробных чисел.

• Функция puts() отображает строку на экрана. Используйте эту быструю функцию для простого вывода строки. Для более сложного форматированного вывода воспользуйтесь могущественной printf().

• С помощью функции scanf() в строку можно ввести заданное количество символов. Для ввода строк, содержащих пробелы, используйте gets().

• Файл string.h содержит богатую библиотеку строковых функций (см.

следующий раздел). Многие строковые функции возвращают указатели типа char *, поэтому результат одной функции может передаваться другой в качестве аргумента.

Обзор функций Таблица 5. Функции для работы со строками Функция Прототип и краткое описание 1 Библиотека stdio.h char *gets(char *str);

gets() Получает следующую строку со стандартного потока ввода и записывает ее в str;

в случае успешного завершения функция возвращает str, в противном случае – NULL.

int puts(const char *str);

puts() Записывает строку в стандартный поток вывода. В случае ошибки функция возвращает значение EOF.

int sprintf(char *str, const char *format,...);

sprintf() Копирует форматированную строку format в указанную строку.

В случае успешного завершения функция возвращает количество записанных байтов информации (не считая завершающего нуля);

в противном случае возвращается значение EOF.

int sscanf(const char *str, const char *format,...);

sscanf() Считывает форматированный ввод из указанной строки (см.

функцию scanf()).

Библиотека stdlib.h double atof(const char *str);

atof() Преобразует строку str в вещественное число типа double.

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

int atoi(const char *str);

atoi() Преобразует строку str в целое число типа int. Преобразование завершается по достижении первого символа, который не является частью числа. Возвращается нуль, если не было найдено ни одного числа.

long atol(const char *str);

atol() Преобразует строку str в целое число типа long. Преобразование завершается по достижении первого символа, который не Продолжение табл. 5. 1 является частью числа. Возвращается нуль, если не было найдено ни одного числа.

char *itoa(int value, char *str, int base);

itoa() Преобразует целое число value в строку str. Для преобразования числа используется основание base (2 base 36). Для десятеричной системы base равно 10.

char *ltoa(long value, char *str, int base);

ltoa() Преобразует переменную value типа long в строку str. Для преобразования числа используется основание base (2 base 36). Для десятеричной системы base равно 10.

char *ultoa(unsigned long value, char *str, int base);

ultoa() Преобразует беззнаковую переменную value типа long в строку str. При изображении числа используется основание base (2 base 36). Для десятеричной системы base равно 10.

Библиотека string.h char *strcat(char *str1, const char *str2);

strcat() Объединяет строки str1 и str2 (конкатенация строк);

результат записывается в str1. Функция возвращает str1.

char *strchr(const char *str, int c);

strchr() Возвращает указатель на первое вхождение в строке str символа c. Если символ не найден, возвращает NULL.

int strcmp(const char *str1, const char *str2);

strcmp() Сравнивает строки str1 и str2. Результат отрицателен, если строка str1 алфавитно меньше строки str2;

равен нулю, если строки равны;

положителен, если строка str1 алфавитно больше строки str2.

char *strcpy(char *str1, const char *str2);

strcpy() Копирует строку str2 в строку str1. Возвращает str1.

char *strdup(const char *str);

strdup() Выделяет память в куче и копирует в нее строку str. В случае успешного завершения возвращает указатель на копию строки в куче, в противном случае возвращает NULL.

Продолжение табл. 5. 1 int stricmp(const char *str1, const char *str2);

stricmp() Сравнивает строки str1 и str2, не делая различия регистров.

Результат отрицателен, если строка str1 алфавитно меньше строки str2;

равен нулю, если строки равны;

положителен, если строка str1 алфавитно больше строки str2.

unsigned strlen(const char *str);

strlen() Возвращает длину строки str, не считая завершающий нулевой символ ‘\0’.

char *strlwr(char *str);

strlwr() Преобразует буквы верхнего регистра в строке (A-Z) в соответствующие буквы нижнего регистра (a-z). Возвращает преобразованную строку.

char *strncat(char *str1, const char *str2, int n);

strncat() Дописывает n символов строки str2 к строке str1 (конкатенация строк). Возвращает str1.

int strncmp(const char *str1, const char *str2,int n);

strncmp() Сравнивает первые n символов строк str1 и str2. Результат отрицателен, если строка str1 алфавитно меньше строки str2;

равен нулю, если строки равны;

положителен, если строка str алфавитно больше строки str2.

char *strncpy(char *str1, const char *str2, int n);

strncpy() Копирует n символов строки str2 в строку str1. Возвращает str1.

int strcspn(const char *str1, const char *str2);

strcspn() Возвращает длину первого сегмента строки str1, содержащего символы, не входящие во множество символов строки str2.

int strnicmp(char *str1, const char *str2, int n);

strnicmp() Сравнивает n символов строки str1 и str2, не делая различия регистров. Результат отрицателен, если строка str1 алфавитно меньше строки str2;

равен нулю, если строки равны;

положителен, если строка str1 алфавитно больше строки str2.

char *strnset(char *str, int c, int n);

strnset() Заменяет первые n символов строки str символом c. Возвращает модифицированную строку.

Окончание табл. 5. 1 char *strpbrk(const char *str1, const char *str2);

strpbrk() Ищет в строке str первое появление любого из множества символов, входящих в строку str2. В случае успешного поиска возвращает указатель на найденный символ, в противном случае возвращает NULL.

char *strrchr(const char *str, int c);

strrchr() Возвращает указатель на последнее вхождение символа с в строку str. Если символ не найден, возвращает NULL.

char *strset(char *str, int c);

strset() Заменяет все символы строки (за исключением завершающего нуля) на заданный символ c. Возвращает модифицированную строку.

char *strstr(const char *str1, const char *str2);

strstr() Ищет в строке str1 подстроку str2. Возвращает указатель на символ в строке str1, с которого начинается str2, или NULL, если подстрока не найдена.

char *strtok(char *str1, const char *str2);

strtok() Ищет в строке str1 лексемы, разделенные символами из строки str2.

char *strupr(char *str);

strupr() Преобразует буквы нижнего регистра (a-z) в строке str в буквы верхнего регистра (A-Z) и возвращает модифицированную строку.

Кроме функций работы со строками библиотека string.h определяет несколько функций, которые оперируют памятью на общем уровне.

Таблица 5. Функции работы с памятью (string.h) Функция Прототип и краткое описание 1 void *memchr(const void *s, int c, size_t n);

memchr() Ищет первое вхождение символа с среди исходных n символов объекта, на который указывает s;

возвращает указатель на первое появление символа либо NULL, если символ не найден.

Окончание табл. 5. 1 int memcmp(const void *s1, const void *s2, size_t n);

memcmp() Сравнивает посимвольно две области памяти s1 и s2 длиной n байтов;

интерпретирует каждое значение как unsigned char.

Возвращает нуль, если объекты одинаковы;

отрицательное значение, если первый объект численно меньше, чем второй;

положительное значение, если первый объект больше, чем второй.

void *memcpy(void *dest, const void *src, int n);

memcpy() Копирует n байтов из области памяти, на которую указывает src, в область, указанную dest. Возвращает dest. Если указатели dest и src адресуют перекрывающиеся области памяти, результат непредсказуем.

int memicmp(const void *s1, const void *s2, unsigned memicmp() n);

Работает аналогично memcmp(), но не делает различия регистров.

void *memmove(void *dest, const void *src, int n);

memmove() Копирует n байтов из src в dest. Возвращает указатель dest.

Функция аналогична memcpy() за тем исключением, что если указатели dest и src адресуют перекрывающиеся области памяти, копирование происходит корректно.

void *memset(void *s, int c, unsigned n);

memset() Записывает во все байты области s значение c. Длина области s равна n байтов. Возвращает указатель s.

Таблица 5. Функции, завершающие работу программы (stdio.h) Функция Прототип и краткое описание void exit(int status);

exit() Немедленно прекращает выполнение программы. Значение status, равное нулю, обычно говорит о нормальном завершении программы. Ненулевое значение свидетельствует об ошибках.

6. Структуры Структуры помогают упорядочить данные, объединяя несколько переменных «под одной крышей». В отличие от массивов, которые могут содержать значения только одного типа, структуры могут состоять из значений различных типов данных.

Чтобы объявить структуру, напишите ключевое слово struct и добавьте к нему идентификатор (имя структуры) со списком переменных в скобках (членами структуры). Объявление каждого члена и всей структуры в целом должны заканчиваться точкой с запятой.

struct coordinate { int x;

int y;

};

Структура coordinate имеет два члена типа int: x и у. Такую структуру удобно использовать, например, для описания точек на карте или графике.

Теперь объявим переменную структурного типа:

struct coordinate point;

Слово struct в таком объявлении нужно включить обязательно, несмотря на то, что вы уже объявили структурный тип ранее. Следующая запись не будет скомпилирована:

coordinate p;

/* ??? */ Чтобы избежать повторного набора слова struct, при объявлении структуры вы можете воспользоваться услугами оператора typedef:

typedef struct coordinate { int x;

int y;

} Coordinate;

Как вы знаете, typedef не создает новый тип данных – он только связывает существующий тип данных с псевдонимом, который обычно пишется с прописной буквы. При объявлении структуры с помощью этого оператора вы можете опустить имя структуры и просто записать:

typedef struct { int x;

int y;

} Coordinate;

Теперь с помощью нового псевдонима можно объявить структурную переменную:

Coordinate point;

Переменная point содержит два целых значения: х и y. Чтобы получить доступ к ним, используйте запись через точку. Например:

point.x = 5;

point.y = 6;

Имена членов должны быть уникальными внутри одной и той же структуры, но они не вступают в конфликт с именами других переменных.

Например, не будет ошибкой, если в программе будет объявлена структура Coordinate, а также переменные х и у.

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

typedef struct complexStruct { float aFloat;

int anInt;

char aString[8];

char aChar;

long aLong;

} ComplexStruct;

ComplexStruct представляет собой структуру, состоящую их пяти членов: четырех переменных и одного массива. Переменная data, объявленная как ComplexStruct data;

запоминает эти значения в одной удобной «упаковке».

Сравнивание и присваивание структур Вы можете присваивать значения одной структурной переменной другой при условии, что эти переменные имеют один и тот же тип. После объявления Coordinate var1, var2;

Следующий оператор присваивает значения переменной var2 переменной var1:

var1 = var2;

Непосредственно сравнивать две структуры нельзя. Оператор, подобный следующему, не будет скомпилирован:

if (var1 == var2) /* ??? */ оператор;

Но если вы не можете сравнивать две структуры, то никто не запрещает вам сравнивать их члены. Вот корректный способ выполнения оператора, если переменные var1 и var2 равны:

if ((var.x == var2.x) && (var1.y == var2.y)) оператор;

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

typedef struct date { char day;

char month;

unsigned year;

} Date;

Члены структуры day и month имеют тип char, диапазон значений которого вполне достаточен, чтобы вместить значения дня (от 1 до 31) и месяца (от 1 до 12). Член структуры year имеет тип unsigned int. Листинг 6. демонстрирует использование структуры Date.

Листинг 6.1. date.c (запоминание даты в структуре) 1: #include 2:

3: typedef struct dateStruct { 4: char day;

5: char month;

6: unsigned year;

7: } Date;

8:

9: main() 10: { 11: Date date;

12:

13: printf(Date test\n);

14: date.day = 1;

15: date.month = 9;

16: date.year = 2004;

17: printf(The date is: %02d.%02d.%04d\n, 18: date.month, date.day, date.year);

19: return 0;

20: } В строках 14-16 происходит присваивание значений членам структуры date. В строках 17-18 оператор printf() выводит эти значения на экран, добавляя точки и ведущие нули для удобства отображения:

Date test The date is: 01.09. Вы можете присваивать начальные значения членам структуры прямо в объявлении. Используйте следующую форму записи:

struct name var = {элементы};

Здесь name – имя структуры, var – переменная данного структурного типа, элементы – константные выражения для присваивания членам структуры.

Отделяйте константы запятыми, располагая их в соответствии с порядком объявленных в структуре членов. Например, следующая запись присвоит дату 1.09.2010 переменной date:

Date date = {1, 9, 2010};

Использование вложенных структур Если членом структуры является другая структура, то в результате получаем вложенную структуру – одна структура внутри другой.

Предположим, вы объявляете структуру для запоминания времени:

typedef struct time { char hour;

/* от 0 до 23 */ char minute;

/* от 0 до 59 */ char second;

/* от 0 до 59 */ } Time;

Используя структуру Date, описанную в предыдущем разделе, вы можете построить вложенную структуру DateTime следующим образом:

typedef struct dateTime { Date theDate;

Time theTime;

} DateTime;

Структура DateTime объявляет два члена: theDate и theTime, причем каждый их них является структурой. После объявления переменной dt DateTime dt;

выражение dt.theDate обозначает член theDate типа Date структуры dt, а dt.theTime – член theTime типаTime.

Замечание. Структура не может объявлять в качестве члена структуру своего собственного типа. Другими словами, структура не может объявлять членом саму себя. Однако членом структуры может быть указатель на структуру того же типа.

Для доступа к вложенным членам структур используйте необходимое число точек. Например, выражение dt.theDate.month ссылается на член month, принадлежащий структуре theDate, которая, в свою очередь, принадлежит структуре dt.

Листинг 6.2 расширяет возможности предыдущей программы. С помощью вложенных структур программа запоминает и отображает значения даты и времени.

Листинг 6.2. datetime.c (запоминание даты и времени в структурах) 1: #include 2:

3: typedef struct dateStruct { 4: char day;

5: char month;

6: unsigned year;

7: } Date;

8:

9: typedef struct timeStruct { 10: char hour;

11: char minute;

12: char second;

13: } Time;

14:

15: typedef struct dateTime { 16: Date theDate;

17: Time theTime;

18: } DateTime;

19:

20: main() 21: { 22: DateTime dt;

23:

24: printf(Date and time test\n);

25: dt.theDate.day = 1;

26: dt.theDate.month = 9;

27: dt.theDate.year = 2004;

28: dt.theTime.hour = 18;

29: dt.theTime.minute = 30;

30: dt.theTime.second = 0;

31: printf(The data is: %02d.%02d.%04d\n, 32: dt.theDate.day, dt.theDate.month, dt.theDate.year);

33: printf(The time is: %02d:%02d:%02d\n, 34: dt.theTime.hour, dt.theTime.minute, dt.theTime.second);

35: return 0;

36: } В строках 25-30 членам вложенных структур структуры dt присваиваются значения. Два оператора printf() в строках 31-34 отображают эти значения на экране:

Date and time test The data is: 01.09. The time is: 18:30: Структуры и функции Члены структур могут быть любого типа данных, но они не могут быть функциями. Несмотря на это ограничение, структуры и функции могут активно взаимодействовать. Структуры могут передаваться параметрам функции, а функции могут возвращать структуры как результаты своей работы.

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

typedef struct rectangle { int left;

int top;

int right;

int bottom;

} Rectangle;

Структура Rectangle имеет четыре члена, представляющих левую, верхнюю, правую и нижнюю координаты прямоугольника на дисплее.

Программам, которые используют структурные переменные типа Rectangle, понадобится поддержка различных функций. Например, вместо явного присваивания переменной Rectangle четырех координат:

Rectangle r;

r.left = 5;

r.top = 8;

r.right = 60;

r.bottom = 18;

вы можете написать функцию (допустим с именем RectAssign), которая возвращает инициализированную структуру типа Rectangle:

Rectangle r;

r = RectAssign(5, 8, 60, 18);

Вот один из вариантов реализации такой функции:

Rectangle RectAssign(int l, int t, int r, int b) { Rectangle rtemp;

rtemp.left = l;

rtemp.top = t;

rtemp.right = r;

rtemp.bottom = b;

return rtemp;

} Несмотря на то что переменная rtemp локальна в функции и не существует вне области ее действия, функция может возвращать значение переменной rtemp в качестве своего результата. При выполнении оператора return переменная rtemp временно копируется в стек, а затем оттуда – в переменную, которой присваивается результат функции. После этого данные из стека удаляются.

Вы также можете передавать структуры параметрам функции.

Например, если вам нужно сравнивать две структуры типа Rectangle, вы можете написать такую функцию:

int RectsEqual(Rectangle r1, Rectangle r2) { return ((r1.left == r2.left ) && (r1.top == r2.top ) && (r1.right == r2. right) && (r1.bottom == r2.bottom));

} Совет. В сложных выражениях выравнивайте скобки и операторы как показано выше, чтобы облегчить восприятие текста и отладку.

Теперь вы можете вызывать функцию RectsEqual() в любом месте программы, где разрешены логические выражения. Например, оператор if выполнит оператор, если две структуры типа Rectangle – var1 и var2 – равны:

if (RectsEqual(var1, var2)) оператор;

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

• массивы структур;

• структуры с членами, являющимися массивами.

Давайте рассмотрим подробно каждый из этих типов данных.

Массивы структур Два или несколько массивов, содержащих связанные между собой данные, часто можно преобразовать в один массив структур, который, как правило, более эффективен. Пусть, к примеру, нам необходимо запомнить 100-элементный набор трехмерных координат. Вы могли бы объявить три массива:

double x[100];

double y[100];

double z[100];

Это решает задачу, однако, чтобы получить доступ к одной точке, потребуется выполнить три операции индексирования. Используя гипотетическую функцию PlotPoint() для вычерчивания одиннадцатой точки, вы должны были бы записать примерно следующее:

PlotPoint(x[10], y[10], z[10]);

Лучший вариант – объявление структуры с тремя членами типа double:

struct point3D { double x;

double y;

double z;

} Использование структуры point3D позволяет обойтись только одним массивом для запоминания 100-элементного набора данных:

struct point3D points[100];

Такие выражения, как points[9] и points[50], обозначают трехчленные структуры point3D, расположенные согласно их индексу. Теперь можно объявить функцию PlotPoint(), которая имеет только один параметр:

void PlotPoint(struct point3D p);

и передавать функции PlotPoint() структуры, организованные в массив:

PlotPoint(points[9]);

Структуры с членами, являющимися массивами Структуры в качестве своих членов могут иметь массивы. Вот типичный пример структуры с несколькими символьными массивами:

struct person { char name[30];

char address[40];

char city[15];

...

};

Членами структур могут быть массивы и любых других типов данных, в том числе и массивы других структур.

Динамические структуры данных Чтобы эффективно использовать память компьютера, большие структуры с множеством членов (особенно если некоторые из них являются массивами) лучше хранить в куче. Вначале объявите указатель на структурный тип, наприме:

Coordinate *p;

Затем вызовите функцию malloc(), чтобы выделить память в куче и присвоить адрес указателю р:

p = (Coordinate *)malloc(sizeof(Coordinate));

Указатель р сейчас адресует блок памяти, размер которого как раз такой, чтобы запомнить одну структуру типа Coordinate. Но в отличие от глобальных или локальных структурных переменных, вы не можете использовать точку для доступа к членам структуры. Следующие операторы не будут работать:

p.x = 123;

/* ??? */ p.y = 321;

/* ??? */ Указатель р не является структурной переменной. Это указатель на структуру, поэтому вы должны использовать оператор –>, который похож на стрелку:

p->x = 123;

p->y = 321;

Как обычно, вы можете разыменовать указатель на структуру.

Выражение *p представляет структуру, адресуемую р. Выражение (*p).x эквивалентно p–>x. Листинг 6.3 демонстрирует, как использовать структуры, адресуемые указателями.

Листинг 6.3. pstruct.c (адресация членов структур с помощью указателей) 1: #include 2: #include 3:

4: typedef struct coordinate { 5: int x;

6: int y;

7: } Coordinate;

8:

9: main() 10: { 11: Coordinate* pixel;

/* объявление указателя на структуру */ 12:

13: pixel = (Coordinate *)malloc(sizeof(Coordinate));

14: if (pixel == NULL) { 15: puts(Out of memory!);

16: exit(1);

17: } 18: pixel–>x = 10;

/* присваивание 10 члену х */ 19: pixel–>y = 11;

/* присваивание 11 члену y */ 20: printf(x = %d\n, pixel–>x);

21: printf(y = %d\n, pixel–>y);

22: free(pixel);

23: return 0;

24: } Самоссылочные структуры Структуры, ссылающие на себя, обычно располагаются в динамической памяти. Каждая структура содержат указатель, который ссылается на другую структуру того же типа. «Цепляясь» с помощью указателей друга за друга, подобно виноградной лозе, цепочки структур такого типа могут динамически расти при добавлении элементов и сокращаться при их удалении. Память в куче при этом расходуется очень экономно, т.к. выделяется ровно столько памяти, сколько нужно для хранения данных.

Самыми распространенными самоссылочными структурами являются списки, стеки, и очереди.

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

Стек – это набор связанных между собой элементов, размещаемых в динамической памяти. Стеки организованы по принципу: последним вошел – первым вышел. Данные добавляются в начало стека, называемое вершиной, и извлекаются также из начала стека. Представить себе стек позволяет пример:

шарики закатываются в трубку, запаянную с одного конца.

Рис.6.1. Модель стека Чтобы организовать стек, объявите вначале следующую структуру:

struct item { int data;

/* любые члены */ struct item *next;

/* указатель на другую структуру типа item*/ };

Структура типа struct item имеет два члена: целую переменную, которая в этом примере представляет информацию для запоминания в структуре, и указатель next на «свой» тип структуры. Какое же это мощное средство! Несколько переменных типа item теперь могут формировать список, просто связываясь друг с другом с помощью указателя на следующий элемент.

Для упрощения программирования используйте оператор typedef:

typedef struct item { int data;

struct item *next;

} Item;

Далее, объявите указатель типа Item, который будет служить вершиной стека:

Item *top = NULL;

Если указатель top равен нулю, значит стек пуст, поэтому хорошая идея – проинициализировать указатель прямо в его объявлении. Чтобы начать стек, проверьте его член top, и, если он окажется нулевым, выделяйте память для нового элемента типа Item:

if (top == NULL) { top = (Item *)malloc(sizeof(Item));

top->data = 1;

top->next = NULL;

} Теперь в стеке есть один элемент, адресуемый указателем top.

Указатель next указывает на NULL, что является признаком конца стека (рис. 6.2).

Из одного элемента стек состоит data top [1] крайне редко. Рано или поздно вам понадобиться добавить в стек новую next NULL информацию. С помощью указателя p следующие операторы добавят в стек Рис. 6.2. Стек из 1 элемента новый элемент:

Item* p;

p = (Item *)malloc(sizeof(Item));

p->data = 2;

p->next = top;

top = p;

Внимательно изучите эти операторы. После того как программа выделит память для элемента, адресуемого р, она присвоит переменной data значение 2, а указателю p–>next – адрес вершины стека. После этого указателю top присваивается значение p, чтобы он вновь указывал на последний созданный элемент. Сейчас стек выглядит, как показано на рис. 6.3.

После добавления еще data data нескольких структур стек top [2] [1] принимает вид, показанный на рис. 6.4. Каждая структура типа p next next NULL Item связана со следующей с помощью указателя next.

Рис. 6.3. Стек из 2 элементов Путем разыменования указателя top можно получить доступ к любому элементу стека. Выражение top–>data относится к переменной data в последнем элементе стека. Чтобы получить доступ к другим членам, вы должны использовать операторы, подобные следующим (каждый из них присваивает переменной i значение члена data разных элементов стека):

i = top->data;

/* i = 4 */ i = top->next->data;

/* i = 3 */ i = top->next->next->data;

/* i = 2 */ i = top->next->next->next->data;

/* i = 1 */ data data data data top [4] [3] [2] [1] next next NULL next next Рис. 6.4. Стек из нескольких элементов, связанных с помощью указателей на следующий элемент Однако многоссылочные выражения слишком громоздки и в таком виде используются редко. Вместо этого, чтобы «пройтись» по элементам стека, большинство программистов используют цикл:

Item *p = top;

while (p != NULL) { printf(%d\n, p->data);

p = p->next;

} Временный указатель р типа Item * инициализируется адресом вершины стека. В цикле оператор printf() отображает значение члена структуры data, а указателю p присваивается адрес следующей структуры в стеке. Чтобы цикл мог успешно закончиться, последняя структура должна иметь член next, равный нулю.

Еще одна распространенная операция над стеками – удаление элементов. Для стека, изображенного на рис. 6.4, следующие операторы удаляют элемент, адресуемый указателем top:

Item *p = top;

top = top->next;

free(p);

Временному указателю р типа Item * присваивается значение top, после чего указателю top присваивается адрес следующей структуры (рис. 6.5). Последний оператор передает указатель р в функцию free(), удаляя отсоединенный элемент стека из кучи.

data data data data top [4] [3] [2] [1] next next NULL next next p Рис. 6.5. Удаление элемента в стеке Листинг 6.4 демонстрирует принципы добавления и удаления данных из стека. Скомпилируйте и запустите программу, затем нажмите несколько раз, чтобы добавить в стек новые элементы. Нажмите , чтобы удалить элементы. Если вы удалите все элементы, программа напечатает, что стек пуст.

Листинг 6.4. stack.c (запоминание значений в стеке) 1: #include 2: #include 3: #include 4: #include 5:

6: #define FALSE 7: #define TRUE 8:

9: typedef struct item { 10: int data;

/* данные для запоминания в стеке */ 11: struct item *next;

/* указатель на следующий элемент */ 12: } Item;

13:

14: void Push(void);

15: void Pop(void);

16: void Display(void);

17:

18: Item* top = NULL;

/* указатель на стек */ 19:

20: main() 21: { 22: int done = FALSE;

/* если TRUE, программа завершается */ 23: char c;

/* символ команды пользователя */ 24:

25: while (!done) { 26: Display();

27: printf("\n\nA)dd, D)elete, Q)uit ");

28: c = getch();

29: switch (toupper(c)) { 30: case A:

31: Push();

32: break;

33: case D:

34: Pop();

35: break;

36: case Q;

37: done = TRUE;

38: break;

39: } 40: } 41: return 0;

42: } 43:

44: /* Добавление элемента в стек */ 45: void Push(void) 46: { 47: Item* p;

48:

49: p = (Item *)malloc(sizeof(Item));

/* создание элемента */ 50: p->data = rand();

51: p->next = top;

52: top = p;

53: } 54:

55: /* Удаление элемента из стека */ 56: void Pop(void) 57: { 58: Item* p;

59:

60: if (top != NULL) { /* если стек не пуст... */ 61: p = top;

62: top = top->next;

63: free(p);

64: } 65: } 66:

67: /* Отобразить содержимое стека */ 68: void Display(void) 69: { 70: Item* p = top;

71:

72: clrscr();

73: if (p == NULL) 74: printf("Stack is empty");

75: else 76: printf("Stack: ");

77: while (p != NULL) { 78: printf("\n%d", p->data);

79: p = p->next;

/* адресовать следующий элемент стека*/ 80: } 81: } В строке 18 объявляется указатель на вершину стека top. Будучи глобальным, указатель автоматически инициализируется нулевым значением, однако здесь ему явно присваивается значение NULL, чтобы подчеркнуть, что в начале программы стек пуст.

Основные функции, используемые при работе со стеками – это Push() и Pop(). Функция Push() (строки 45-53) создает новый элемент и помещает его на вершину стека. В строках 49-50 с помощью указателя p происходит создание нового элемента и инициализация переменной data случайным числом. Оператор в строке 51:

p->next = top;

связывает новый элемент с предыдущими, образуя цепочку элементов.

Функция Pop() (строки 56-65) удаляет элемент, являющийся вершиной стека и освобождает выделенную память. Функция действует в полном соответствии с принципом «Последним вошел – первым вышел».

Функция Display() (строки 68-81) отображает содержимое стека. С помощью оператора в строке 79:

p = p–>next;

цикл while последовательно перебирает элементы стека, до тех пор, пока не встретится указатель на NULL.

Очередь Еще одной распространенной структурой данных является очередь.

Очередь можно представить себе как трубку с двумя открытыми концами (рис. 6.6): данные добавляются в начало очереди, а извлекаются из ее конца.

Другими словами, очередь работает по принципу: «Первый вошел – первый вышел».

Рис.6.6. Модель очереди Очереди находят в компьютерных системах многочисленные применения. Большинство компьютеров оборудовано только одним процессором, поэтому в каждый конкретный момент времени может обсуживаться только один процесс или задача. Остальные задачи ставятся в очередь.

Информационным пакетам в сети Internet также приходится «стоять в очередях». Пакет в сети переправляется от одного сетевого узла к другому, пока не достигнет узла назначения. Сетевой узел способен послать в каждый момент всего один пакет, поэтому все остальные пакеты становятся в очередь, ожидая, когда пересылающий узел сможет их обработать.

Листинг 6.5 представляет собой пример работы с очередью. Программа queue предлагает выполнить следующие действия: поставить элемент в очередь, удалить его из очереди либо выйти из программы.

Листинг 6.5. queue.c (работа с очередью) 1: #include 2: #include 3: #include 4: #include 5:

6: #define FALSE 7: #define TRUE 8:

9: typedef struct item { 10: int data;

11: struct item *next;

12: } Item;

13:

14: void Enqueue(void);

15: void Dequeue(void);

16: void Display(void);

17:

18: /* Указатели на начало (голову) и конец (хвост) очереди */ 19: Item *head = NULL, *tail = NULL;

20:

21: main() 22: { 23: int done = FALSE;

24: char c;

25:

26: while (!done) { 27: Display();

28: printf("\n\nA)dd, D)elete, Q)uit ");

29: c = getch();

30: switch (toupper(c)) { 31: case A:

32: Enqueue();

33: break;

34: case D:

35: Dequeue();

36: break;

37: case Q:

38: done = TRUE;

39: break;

40: } 41: } 42: return 0;

43: } 44:

45: /* Поставить элемент в очередь */ 46: void Enqueue(void) 47: { 48: Item* p;

49:

50: p = (Item *)malloc(sizeof(Item));

/* создать элемент */ 51: p->data = rand();

/* присвоить data случайное число */ 52: p->next = NULL;

/* установить признак конца очереди */ 53: if (head == NULL) /* если очередь пуста... */ 54: head = p;

/* head указывает на созданный элемент*/ 55: else /* иначе... */ 56: tail->next = p;

/* поставить новый эл. в конец очереди*/ 57: tail = p;

/* tail указывает на конец очереди */ 58: } 59:

60: /* Удалить элемент из очереди */ 61: void Dequeue(void) 62: { 63: Item* p = head;

/* p указывает на голову очереди */ 64:

65: if (head != NULL) { /* если очередь не пуста... */ 66: head = head->next;

/* head указывает на следующий эл. */ 67: if (head == NULL) /* если очередь содержит 1 элемент */ 68: tail = NULL;

/* tail равен нулю */ 69: free(p);

/* удалить элемент */ 70: } 71: } 72:

73: /* Отобразить содержимое очереди */ 74: void Display(void) 75: { 76: Item* p = head;

77:

78: clrscr();

79: if (p == NULL) 80: printf("Queue is empty");

81: else 82: printf("Queue: ");

83: while (p != NULL) { 84: printf("\n%d", p->data);

85: p = p->next;

86: } 87: } За исключением нескольких важных особенностей листинг 6.5 похож на предыдущий. В строке 18 для работы с очередью объявляется два указателя: head («голова») и tail («хвост») очереди. Указателя два, т.к. в очереди необходимо отслеживать начальный и конечный элемент (рис. 6.7).

head tail data data data data next next NULL next next Рис. 6.7. Очередь, состоящая из 4 элементов Функция Enqueue() («поставить в очередь»), описанная в строках 45-57, похожа на функцию Push() для работы со стеками. С помощью временного указателя p создается новый элемент, член data которого инициализируется случайным значением. Указатель next создаваемого элемента всегда должен быть нулевым, т.к. элементы могут добавляться только в конец очереди. Если очередь пуста, то и «голова», и «хвост» очереди будут указывать на создаваемый (первый) элемент. В противном случае на новый элемент будет указывать лишь tail («хвост»).

Функция Dequeue() («удалить из очереди»), описанная в строках 60-70, напоминает функцию Pop(). Вначале проверяется, есть ли в очереди элементы. Если это так, то указателю head присваивается адрес следующего элемента. После этого элемент, на который head указывал раньше, удаляется.

Функция работает в полном соответствии с принципом «Первым вошел – первым вышел», так как удаляет элементы только из «головы» очереди.

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

Листинг 6.6 демонстрирует работу со списками. Программа list расширяет возможности предыдущих программ, позволяя вставлять символы в список в алфавитном порядке.

Листинг 6.6. list.c (управление списком символов) 1: #include 2: #include 3: #include 4: #include 5:

6: typedef struct item { 7: char data;

8: struct item *next;

9: } Item;

10:

11: void Insert(char value);

12: void Delete(char value);

13: void Display(void);

14:

15: Item* list = NULL;

16: #define FALSE 17: #define TRUE 18:

19: main() 20: { 21: int done = FALSE;

22: char c, value;

/* символ команды пользователя и */ 23: /* вводимое значение */ 24: while (!done) { 25: Display();

26: printf("\n\nA)dd, D)elete, Q)uit ");

27: c = getch();

28: switch (toupper(c)) { 29: case A:

30: printf("\nEnter a character: ");

31: value = getch();

/* получить символ */ 32: Insert(value);

/* вставить его в список */ 33: break;

34: case D:

35: if (list != NULL) { /* если список не пуст */ 36: printf("\nEnter character to be deleted: ");

37: value = getch();

/* получить символ */ 38: Delete(value);

/* удалить его из списка */ 39: } 40: break;

41: case Q:

42: done = TRUE;

43: break;

44: } 45: } 46: return 0;

47: } 48:

49: /* Вставить элемент в список */ 50: void Insert(char value) 51: { 52: Item *p, *cur = list, *prev = NULL;

53:

54: p = (Item *)malloc(sizeof(Item));

55: p->data = value;

56: p->next = NULL;

57: /* Цикл while находит место для вставки элемента */ 58: while (cur != NULL && value > cur->data) { 59: prev = cur;

60: cur = cur->next;

61: } 62: if (prev == NULL) { /* если новый элемент должен быть */ 63: /* первым в списке... */ 64: p->next = list;

/* связать его со списком */ 65: list = p;

/* list указывает на первый элемент */ 66: } else { /* иначе... */ 67: prev->next = p;

/* вставить элемент */ 68: p->next = cur;

/* в середину или конец списка */ 69: } 70: } 71:

72: /* Удалить элемент из списка */ 73: void Delete(char value) 74: { 75: Item *prev = list, *cur = list->next, *p;

76:

77: if (value == list->data) { /* если нужно удалить */ 78: /* начальный элемент списка */ 79: p = list;

/* p указывает на удаляемый элемент*/ 80: list = list->next;

/* list указывает на след. элемент */ 81: free(p);

/* удалить элемент */ 82: } else { /* иначе... */ 83: /* С помощью цикла while найти элемент */ 84: while (cur != NULL && cur->data != value) { 85: prev = cur;

86: cur = cur->next;

87: } 88: if (cur != NULL) { /* если элемент найден... */ 89: p = cur;

/* p указывает на удаляемый элемент*/ 90: prev->next = cur->next;

/* перенастроить связи */ 91: free(p);

/* удалить элемент */ 92: } 93: } 94: } 95:

96: /* Отобразить список */ 97: void Display(void) 98: { 99: Item* p = list;

100:

101: clrscr();

102: if (p == NULL) 103: printf("List is empty");

104: else { 105: printf("List: ");

106: while (p != NULL) { 107: printf("%c -> ", p->data);

108: p = p->next;

109: } 110: printf("NULL");

111: } 112: } Функция Insert() (строки 50-70) добавляет символ value в список в алфавитном порядке. Функция объявляет на один, а три временных указателя: p – рабочий указатель, с помощью которого в список добавляются элементы;

cur (от англ. current) – «текущий» указатель и prev (от англ.

previous) – «предыдущий» указатель, которые помогают определить место вставки элемента и перенастроить связи. Указатель cur инициализируется адресом первого элемента списка (или нулем, если список не создан), указатель prev инициализируется значением NULL.

После создания нового элемента, в строках 58-61 запускается цикл while:

while (cur != NULL && value > cur->data) { prev = cur;

cur = cur->next;

} Цикл последовательно «перебирает» все элементы списка до тех пор, пока не будет найден элемент, с большим по алфавиту значением члена data либо не будет достигнут конец списка. В теле цикла указатели cur и prev «ходят» друг за другом подобно влюбленной парочке: сначала указателю prev присваивается значение cur, потом cur «переходит» на следующий элемент списка. Таким образом, после завершения цикла указатель cur будет указывать на элемент, перед которым нужно делать вставку, а prev – на предыдущий элемент (рис. 6.8).

prev cur A list B D NULL next next next p C next NULL...Новый элемент...

Рис. 6.8. Элемент ‘C’ должен быть вставлен между элементами ‘B’ и ‘D’ Если по окончании цикла указатель prev равен нулю (строка 62), то это значит, что либо список пуст, либо все его элементы имеют алфавитно большие значения, чем value. В обоих случаях элемент должен быть вставлен в начало списка, а его адрес присвоен указателю list.

Если указатель prev не равен нулю, то новый элемент придется вставлять в середину или конец списка. Для этого нужно перенастроить связи списка, как это показано в строках 67-68 (см. рис. 6.9).

Новый элемент p C prev->next = p next p->next = cur prev cur A D list B next next next NULL Рис. 6.9. Вставка элемента ‘С’ в середину списка Функция Delete(), описанная на строках 73-94, позволяет удалить из списка элемент, содержащий заданный символ. Функция вызывается, только если список не пуст (строки 35-39). Так же как и Insert(), функция Delete() объявляет три вспомогательных указателя p, prev и cur. Если удалить нужно начальный элемент списка, на который указывает list (строка 77), то используется тот же алгоритм, что и при удалении элемента из стека. В противном случае перед удалением происходит перенастройка связей: члену next предыдущего элемента присваивается адрес следующего за найденным элемента (строка 90).

Двунаправленные списки Однонаправленные списки, которые мы рассматривали выше, отличаются тем, что каждый элемент знает о следующем, но ничего не знает о предыдущем элементе. Как вы уже заметили, в такой список легко добавлять элементы в начало, немного труднее в конец, а вот удаление или вставка элемента посередине вызывает определенные трудности. Существует еще один существенный недостаток: пройти однонаправленный список можно только от начала до конца, но невозможно от конца до начала.

Двунаправленные списки лишены этих недостатков, так как каждый элемент такого списка «знает» о своем предыдущем и следующем элементах.

struct item { int data;

struct item *next;

/* указатель на следующий элемент списка */ struct item *prev;

/* указатель на предыдущий элемент списка*/ };

Схематически двунаправленный список можно изобразить можно следующим образом:

head tail NULL NULL Рис. 6.10. Двусвязный список Листинг 6.7 похож на предыдущий. Но для работы с элементами программа использует более «надежный» двунаправленный список.

Листинг 6.7. list2.c (работа с двунаправленным списком) 1: #include 2: #include 3: #include 4: #include 5:

6: typedef struct item { 7: char data;

8: struct item *next;

9: struct item *prev;

10: } Item;

11:

12: void Insert(char value);

13: void Delete(char value);

14: void Display(void);

15:

16: Item *head = NULL, *tail = NULL;

17: #define FALSE 18: #define TRUE 19:

20: main() 21: { 22: int done = FALSE;

23: char c, value;

24:

25: while (!done) { 26: Display();

27: printf("\n\nA)dd, D)elete, Q)uit ");

28: c = getch();

29: switch (toupper(c)) { 30: case A:

31: printf("\n Enter a character: ");

32: value = getch();

33: Insert(value);

34: break;

35: case D:

36: if (head != NULL) { 37: printf("\n Enter the character to be deleted: ");

38: value = getch();

39: Delete(value);

40: } 41: break;

42: case Q:

43: done = TRUE;

44: break;

45: } 46: } 47: return 0;

48: } 49:

50: void Insert(char value) 51: { 52: Item *p, *cur = head;

53: /* Создание нового элемента */ 54: p = (Item *)malloc(sizeof(Item));

55: p->data = value;

56: p->next = p->prev = NULL;

57:

58: if (head == NULL) { /* если список пуст... */ 59: head = tail = p;

/* head и tail указывают на */ 60: return;

/* созданный элемент */ 61: } 62: /* Поиск места для вставки */ 63: while (cur != NULL && value > cur->data) 64: cur = cur->next;

65:

66: if (cur == head) { /* если элемент нужно вставить */ 67: p->next = head;

/* в начало...*/ 68: head->prev = p;

69: head = p;

70: } 71: else if (cur == NULL) { /* если элемент нужно вставить */ 72: tail->next = p;

/* в конец...*/ 73: p->prev = tail;

74: p->next = NULL;

75: tail = p;

76: } 77: else { /* если элемент нужно вставить в середину...*/ 78: cur->prev->next = p;

79: p->prev = cur->prev;

80: cur->prev = p;

81: p->next = cur;

82: } 83: } 84:

85: void Delete(char value) 86: { 87: Item *p = head;

88: /* Найти элемент, содержащий заданное значение */ 89: while (p != NULL && p->data != value) 90: p = p->next;

91:

92: if (p == NULL) /* если элемент не найден */ 93: return;

/* выйти из функции */ 94: if (p == head) { /* если нужно удалить первый эл. */ 95: head = head->next;

/* перенастроить */ 96: head->prev = NULL;

/* связи */ 97: } 98: else if (p == tail) { /*... удалить последний элемент */ 99: tail = tail->prev;

/* перенастроить */ 100: tail->next = NULL;

/* связи */ 101: } 102: else { /* если нужно удалить элемент в середине списка */ 103: p->prev->next = p->next;

/* перенастроить */ 104: p->next->prev = p->prev;

/* связи */ 105: } 106: free(p);

/* удалить элемент */ 107: } 108:

109: void Display(void) 110: { 111: Item *p = head;

112:

113: clrscr();

114: if (p == NULL) 115: puts("List is empty");

116: else { 117: printf("NULL <-> ");

118: while (p != NULL) { 119: printf("%c <-> ", p->data);

120: p = p->next;

121: } 122: printf("NULL");

123: } 124: } Задание. Внимательно рассмотрите функции Insert() и Delete(). С помощью карандаша и бумаги попробуйте самостоятельно разобраться, как происходит вставка и удаление элементов в начало, конец и середину двунаправленного списка.

Упражнение. Функция Display() выводит элементы двунаправленного списка в прямом порядке, реализуйте функцию DisplayBack(), которая выводила бы их в обратном порядке.

Упражнение. Какой общий недостаток имеют листинги 6.4, 6.5, 6.6 и 6.7?

(Подумайте, прежде чем читать дальше). Правильно, при выходе из программы не освобождается память, занятая элементами динамических структур. Обычно это не вызывает проблем, т.к. при завершении программы память освобождается автоматически, но все же лучше освобождать память явным образом. Реализуйте для названных листингов функцию Clear(), которая при выходе из программы удаляла бы из памяти все элементы динамических структур.

Резюме • Структуры могут объединять несколько переменных одного или разных типов «под одной крышей». Структуры помогают организовать данные так же, как папки помогают организовать документы на рабочем столе.

• Для объявления структуры используйте ключевое слово struct.

Определение структуры создает новый тип данных, который можно использовать для объявления переменных.

• С помощью точки вы можете обратиться к конкретному члену структуры.

Если у вас есть указатель, адресующий структуру, используйте оператор –>.

• Структурам можно присваивать начальные значения, используя список инициализации. Для этого после имени переменной в объявлении структуры ставится знак равенства, за которым следует помещенный в фигурные скобки и разделенный запятыми список инициализаторов. Если инициализаторов в списке меньше, чем имеется членов структуры, оставшимся членам автоматически присваивается значение 0 (или NULL, если член структуры – указатель).

• Структуры можно присваивать, но нельзя сравнивать. Если вам нужно сравнить две структуры, используйте поэлементное сравнение их членов.

• Структуры можно передавать функциям в качестве аргументов, а функции могут возвращать структуры. Структурные аргументы и возвращаемые значения передаются через стек.

• В языке С вы можете объявлять массивы структур, а также массивы, являющиеся элементами структур.

• Чтобы эффективно использовать память, громоздкие структуры (или массивы структур) лучше хранить в куче. Такие структуры называются динамическими.

• Структуры ссылающиеся на себя содержат один или несколько указателей, которые адресуют структуры того же типа. Это позволяет самоссылочным структурам связываться между собой, образуя динамические «цепочки» структур.

• Связанный список – это линейный набор ссылающихся на себя структур.

Длина списка может увеличиваться (при добавлении элементов) или уменьшаться (при их удалении). Добавлять и удалять элементы в список можно в произвольном порядке.

• Стеки и очереди являются разновидностями списков. Стек организован по принципу «Первый вошел – первый вышел», так как элементы добавляются и удаляются только из вершины стека.

• В очереди элементы удаляются с начала, а добавляются в конец. Благодаря этому их называют структурами данных типа «Первый вошел – первый вышел».

• Каждый элемент двунаправленного списка содержит указатели на предыдущий и следующий элемент в списке.

• Двунаправленный список легко пройти в прямом и обратном направлениях, вставить элемент в заданное место. Используйте двунаправленные списки для организации больших объемов данных, над которыми нужно производить операции вставки, удаления, перестановки элементов, сортировки и т.п.

7.Сортировка и поиск данных Методы и алгоритмы сортировки Сортировка данных является одним из наиболее важных применений компьютера. Телефонные компании сортируют списки своих клиентов по фамилиям, чтобы облегчить поиск телефонных номеров. Центры по обслуживанию и продаже автомобилей имеют специальные базы данных, отсортированные по названию модели либо году выпуска. Файлы, хранящиеся на вашем компьютере, тоже, скорее всего, отсортированы по какому-либо признаку: названию, расширению или дате создания.

Поставщики вычислительных машин считают, что на сортировку в среднем по отрасли тратится более 25% машинного времени.

Цель любой сортировки – облегчить поиск элементов в некотором множестве (массиве). Действительно, если мы имеем дело с неотсортированным массивом, то будем вынуждены вести поиск с последовательным перебором, т.е. необходимо просматривать и проверять каждый элемент массива. Данный подход приемлем, если мы имеем дело с небольшими объемами информации, но что делать, если имеется массив данных, состоящий из нескольких миллионов или миллиардов элементов? В таких случаях просто не обойтись без эффективного метода сортировки.

Алгоритмы сортировки уже хорошо исследованы и изучены.

Различные подходы к сортировке обладают своими достоинствами и недостатками. Хотя некоторые методы в среднем могут быть лучше других (например, это относится к быстрой сортировке), ни один из методов не будет идеальным для всех ситуаций, поэтому каждый программист должен иметь в своем арсенале несколько различных алгоритмов сортировки.

Для оценки эффективности сортировок можно использовать следующие параметры:

1. Число сравнений элементов множества (массива).

2. Число перестановок элементов.

3. Скорость сортировки в наилучшем случае.

4. Скорость сортировки в «среднем» случае.

5. Скорость сортировки в наихудшем случае.

Интенсивность работы алгоритма основана на количестве сравнений и перестановок, которые он выполняет. Наибольшая скорость сортировки, как правило, достигается, если массив уже упорядочен. Если массив не упорядочен, алгоритму приходится выполнять больший объем работы. И, наконец, наибольшие трудозатраты обычно требуются в тех случаях, когда массив отсортирован в обратном порядке.

Прямые сортировки Прямые методы сортировки основаны на простых и очевидных алгоритмах. Общим у этих методов является то, что они решают поставленную задачу «в лоб», затрачивая на сортировку много времени.

Во всех методах сортировки, которые мы рассмотрим ниже, для перемены местами элементов используется уже знакомая вам функция Swap():

void Swap(int *x, int *y) { int t = *x;

/* промежуточная переменная */ /* Перемена данных местами */ *x = *y;

*y = t;

} В конце раздела все алгоритмы будут собраны в рабочую программу.

Сортировка методом обмена Сортировка методом обмена больше известна под названием пузырьковой сортировки, которое хорошо отражает суть метода. Будем рассматривать массив расположенным сверху вниз. Согласно методу «пузырька» «легкие» элементы массива должны «всплывать» наверх, а «тяжелые» – «тонуть». Алгоритмически это можно реализовать следующим образом. Будем просматривать весь массив снизу вверх и менять стоящие рядом элементы в том случае, если «нижний» элемент меньше («легче»), чем «верхний». Таким образом, «всплывет на поверхность» самый «легкий» элемент всего массива. Теперь повторим эту операцию для оставшихся неотсортированными n – 1 элементов, которые находятся «ниже» первого.

«Тяжелые» элементы будут опускаться на дно, а «легкие», подобно пузырям, «всплывать» наверх, пока весь массив не окажется отсортирован.

На рис. 7.1 показан пример сортировки 1 1 1 массива методом «пузырька». На рис. 7.1,а 3 3 0 изображен исходный массив из четырех 0 3 элементов. Будем просматривать его «снизу 2 2 2 вверх». Так как элемент 2 «тяжелее» чем 0, элементы остаются на своих местах (рис.

а б в г 7.1,б). На следующей итерации рассматриваются элементы 0 и 3. Поскольку Рис. 7.1. Пузырьковая 0 «легче», он «всплывает наверх», а элемент сортировка: первый проход 3 «опускается вниз» (рис. 7.1,в). Наконец, сравниваются 0 и 1. После того, как элементы поменяются местами, элемент 0, как самый «легкий», «всплывет на поверхность», а элемент 1 «опустится вниз» (рис. 7.1,г). На этом первый проход завершен и элемент 0 занимает свое окончательное место. На следующих итерациях аналогичным образом будут отсортированы оставшиеся элементы: 1, 3 и 2.

Функция BubbleSort() реализует алгоритм сортировки методом «пузырька»:

void BubbleSort(int a[], int n) /* функции передается массив */ { /* и его размерность */ int i, j;

/* переменные цикла */ for (i = 0;

i < n;

i++) for (j = n - 1;

j > i;

j--) if(a[j - 1] > a[j]) /* если элемент тяжелее следующего */ Swap(&a[j - 1], &a[j]);

/* поменять их местами */ } Как видно, алгоритм достаточно прост, но, как иногда замечают, является непревзойденным по своей неэффективности. Для алгоритма пузырьковой сортировки количество сравнений всегда одинаково и равно (n2 – n) / 2, где n - количество сортируемых значений.

В наилучшем случае (если массив уже отсортирован) количество перестановок равно нулю. Количество перестановок в среднем и в худшем случаях равны соответственно:

В среднем случае: (n2 - n).

В худшем случае: (n2 - n).

Пузырьковая сортировка относится к n-квадратичным алгоритмам;

это значит, что время ее выполнения пропорционально квадрату количества элементов сортируемого массива. Данный алгоритм весьма неэффективен при работе с большими массивами.

Сортировка методом выбора В основе этого метода лежит следующий алгоритм:

1. Находится наименьший элемент в массиве.

2. Найденный элемент меняется с первым элементом.

3. Процесс повторяется с оставшимися n – 1 элементами, n – 2 элементами и так далее, пока в конце не останется самый большой элемент, который перемещать уже не нужно.

Функция MinSort() сортирует передаваемый ей массив методом выбора:

void MinSort(int a[], int n) { int i, j, k;

for (i = 0;

i < n - 1;

i++) { for (k = i, j = i + 1;

j < n;

j++) /* находим в цикле */ if(a[j] < a[k]) /* минимальный элемент */ k = j;

/* и запоминаем его номер в k */ Swap(&a[k], &a[i]);

/* меняем местами минимальный и элем., */ } /* с которого начинался цикл */ } К сожалению, сортировка методом выбора тоже является n квадратичным алгоритмом. Она требует (n2 – n) / 2 сравнений, что сильно замедляет работу при большом количестве элементов. Количество перестановок соответственно равно:

В наилучшем случае: 3(n -1) (если массив уже упорядочен, требуется сравнить только (n – 1) элемент, и каждое сравнение требует трех промежуточных шагов).

В среднем случае: n(ln n + y), где y – константа Эйлера, примерно равная 0.577216.

n В наихудшем случае: + 3(n -1).

Хотя количество сравнений для пузырьковой сортировки и сортировки методом выбора одинаковы, количество перестановок в сортировке выбором намного лучше.

Сортировка методом вставки Большинство картежников, сами того не сознавая, пользуются именно этим методом для упорядочения пришедших им карт. Когда игрок получает очередную карту, все предыдущие уже отсортированы, поэтому он просто вставляет ее в нужное место.

На первом шаге алгоритма методом вставки выполняется сортировка первых двух элементов массива. Далее к ним добавляется третий элемент, который занимает позицию среди элементов в соответствии со своим значением. Затем в этот список вставляется четвертый элемент и т.д. Процесс продолжается до тех пор, пока все элементы не будут отсортированы.

Функция InsertSort() реализует алгоритм сортировки методом вставки:

void InsertSort(int a[], int n) { int i, j;

for (i = 1;

i <= n - 1;

i++) { j = i;

while (a[j] < a[j - 1] && j >= 1) { Swap(&a[j], &a[j - 1]);

j--;

} } } В отличие от пузырьковой сортировки и сортировки методом выбора количество сравнений при сортировке методом вставки, зависит от исходной упорядоченности массива. В наилучшем, среднем и наихудшем случаях количество сравнений определяется формулами:

Наилучший случай: 2(n -1).

Средний случай: (n2 + n).

Наихудший случай: (n2 + n).

n Количество перестановок в этом методе не превышает.

Как мы видим, в наихудших случаях алгоритм вставки так же плох, как и пузырьковый метод или метод выбора;

в среднем случае он лишь немногим лучше этих методов;

однако с частично упорядоченными массивами этот метод работает хорошо. Тем не менее существуют еще более совершенные методы сортировки.

Усовершенствованные методы сортировки Сортировка методом Шелла Основная идея Дональда Шелла заключалась в том, чтобы вначале устранить массовый беспорядок в массиве, сравнивая далеко стоящие друг от друга элементы;

затем сравнивать элементы, которые находятся ближе друг другу;

и, наконец, сортировать смежные элементы.

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

Но какие расстояния между сравниваемыми элементами выбрать?

Точная последовательность расстояний может изменяться. Например, хорошо себя зарекомендовала последовательность 9, 5, 3, 2, 1, которая использована в примере ниже. Это значит, что в начале сортируются элементы, отстоящие друг от друга на 9 позиций, потом на 5, на 3, на позиции, и, наконец, сортируются смежные элементы. В алгоритме можно задать и другую последовательность, главное, чтобы последний шаг равнялся единице.

Предупреждение. Избегайте последовательностей степеней 2, поскольку математически доказано, что это снижает эффективность алгоритма.

void ShellSort(int a[], int n) { int i, j, k, temp;

int gap;

/* текущее расстояние сравниваемых элементов */ int d[] = {9, 5, 3, 2, 1};

/* последовательность расстояний */ for (k = 0;

k < 5;

k++) { gap = d[k];

for (i = gap;

i < n;

i++) { temp = a[i];

for (j = i - gap;

temp < a[j] && j >= 0;

j -= gap) a[j + gap] = a[j];

a[j + gap] = temp;

} } } Время выполнения алгоритма Шелла пропорционально n1.2 при сортировке n элементов.Число операций сравнения пропорционально nlog n.

Это существенный прогресс по сравнению с n-квадратичными методами сортировки. Однако прежде, чем вы решите использовать сортировку Шелла, имейте в виду, что быстрая сортировка дает еще лучшие результаты.

Замечание. Когда говорится, что время выполнения алгоритма пропорционально n1.2, то имеется в виду не точное время исполнения, а то, что время (или какой-либо другой параметр) возрастает приблизительно с той же скоростью, что и функция n1.2. Чтобы получить точное значение времени, нужно домножить это выражение на константу, которая зависит от конкретной реализации алгоритма, производительности компьютера и т.п. По этой же причине в формуле nlog n не приводится основание логарифма. Домножив на заданную константу, мы можем перейти к любому основанию, поэтому записывать его не имеет смысла.

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

Производительность метода быстрой сортировки хорошо изучена.

Алгоритм подвергался математическому анализу, поэтому на этот счет существуют точные математические формулы. Среднее число выполняемых сравнений для метода быстрой сортировки равно 2nlog n. Среднее log n количество перестановок равно. Время работы алгоритма пропорционально nlog n. Как и в методе Шелла, ускорение достигается за счет сравнения далеко стоящих друг от друга элементов, потом – более близких и т.д.

Алгоритм быстрой сортировки выглядит следующим образом:

1) Этап разбиения. Возьмите первый элемент несортированного массива и определите его расположение в отсортированном массиве. Это положение будет найдено, если все значения слева от данного элемента будут меньше, а все значения справа от элемента – больше значения данного элемента. Теперь мы имеем один элемент, расположенный на своем месте в отсортированном массиве и два несортированных подмассива.

2) Этап рекурсии. Выполните шаг 1 на каждом из несортированных подмассивов. Каждый раз после выполнения шага 1 в подмассиве следующий элемент массива помещается на свое место в отсортированном массиве, и создаются два несортированных подмассива.

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

Это описание алгоритма в целом кажется достаточно ясным, но как нам определить окончательную позицию первого элемента каждого подмассива?

В качестве примера рассмотрим следующий набор значений (элемент, выделенный жирным – элемент разбиения – должен быть помещен на свое окончательное место в массиве):

37 2 6 4 89 8 12 68 1) Начиная с правого элемента массива будем сравнивать каждый элемент с числом 37 до тех пор, пока не будет найден элемент меньший чем 37, после чего найденный элемент и 37 должны поменяться своими местами.

Первым элементом, который меньше 37, является число 12, поэтому они меняются местами. Теперь массив выглядит так:

12 2 6 4 89 8 37 68 2) Далее начинаем движение с левой части массива, но начинаем со следующего элемента после 12, и сравниваем каждый элемент с 37, пока не обнаружим элемент больший чем 37, после чего меняем местами 37 и этот найденный элемент. В нашем случае первый элемент больший чем 37 – это 89, так что 37 и 89 меняются местами. Новый массив имеет вид 12 2 6 4 37 8 10 89 68 3) Затем начинаем справа, но с элемента, предшествующего 89, и сравниваем каждый элемент с 37 до тех пор, пока не найдем меньший чем 37, и опять поменяем местами 37 и этот элемент. Первый элемент, который меньше 37 – это 10, – меняем местами с 37. Теперь наш массив имеет вид 12 2 6 4 10 8 37 89 68 4) После этого начинаем движение с левой части массива, но начинаем с элемента, следующего за 10, и сравниваем каждый элемент с 37, пока не обнаружим элемент, больший чем 37. В нашем случае таких элементов не оказалось, и когда мы сравним 37 с самим собой, это будет означать, что процесс закончен и элемент 37 нашел свое окончательное место.

После завершения этой операции мы имеем два неупорядоченных подмассива. Подмассив со значениями меньше 37 содержит элементы 12, 2, 6, 4, 10 и 8. Подмассив со значениями большими 37 содержит 89, 68 и 45.

Сортировка продолжается путем применения алгоритма разбиения к полученным подмассивам, как этот делалось с первоначальным массивам.

Как ни странно, рассмотренный алгоритм неэффективен при работе с уже упорядоченным массивом. Допустим, массив отсортирован по возрастанию. В этом случае, т.к. в качестве элемента разбиения мы берем первый элемент, элемент разбиения всегда будет минимальным. Это приведет к тому, что массив будет разделен наихудшим образом: в левом подмассиве окажется один элемент, а в правом останется n – 1 элементов.

Таким образом, за «один проход» метод быстрой сортировки уменьшит длину сортируемого массива всего лишь на 1. В результате время работы алгоритма становится пропорциональным n2. Один из способов решить эту проблему – выбрать в качестве элемента разбиения не первый, а средний либо случайный элемент массива.

void QuickSort(int a[], int n, int left, int right) { /*Инициализируем переменные левой и правой границами подмассива*/ int i = left, j = right;

/*Выбираем в качестве элемента разбиения средний элемент массива*/ int test = a[(left + right) / 2];

do { while (a[i] < test) i++;

/* находим элемент, больший элемента разбиения */ while (a[j] > test) j--;

/* находим элемент, меньший элемента разбиения */ if (i <= j) { Swap(&a[i], &a[j]);

i++;

j--;

} } while(i <= j);

/* рекурсивно вызываем алгоритм для правого и левого подмассива*/ if (i < right) QuickSort(a, n, i, right);

if (j > left) QuickSort(a, n, left, j);

} Листинг 7.1 позволяет сравнить эффективность методов «пузырька», выбора, вставок, Шелла и быстрой сортировки. Каждому методу «предлагается» задание: отсортировать неупорядоченный целочисленный массив из 15 тысяч элементов. Программа определяет время выполнения тестового задания для каждого метода и выводит его на экран. Не пытайтесь перезагрузить компьютер, если на экране какое-то время ничего не будет происходить: возможно, вам придется подождать, пока самые медленные алгоритмы справятся с заданием.

Листинг 7.1. sort.c (сравнение скорости работы пяти методов сортировки) 1: #include 2: #include 3: #include 4: #include 5:

6: #define N 7:

8: void InitArray(int a[], int n);

9: void CopyArrays(int a[], int b[], int n);

10: void Swap(int *x, int *y);

11: void BubbleSort(int a[], int n);

12: void SelectSort(int a[], int n);

13: void InsertSort(int a[], int n);

14: void ShellSort(int a[], int n);

15: void QuickSort(int a[], int n, int left, int right);

16:

17: void main() 18: { 19: int source[N], test[N];

20: long begin, end;

21:

22: clrscr();

23: printf("Sorting Methods Test\n\n");

24: printf("Number of elements: %d\n\n", N);

25: printf("Sorting methods Time (sec)\n");

26: InitArray(source, N);

27: CopyArrays(test, source, N);

28: begin = clock();

BubbleSort(test, N);

end = clock();

29: printf("\nBubble sort %15f", (end - begin) / CLK_TCK);

30: CopyArrays(test, source, N);

31: begin = clock();

SelectSort(test, N);

end = clock();

32: printf("\nSelection sort%15f", (end - begin) / CLK_TCK);

33: CopyArrays(test, source, N);

34: begin = clock();

InsertSort(test, N);

end = clock();

35: printf("\nInsertion sort%15f", (end - begin) / CLK_TCK);

36: CopyArrays(test, source, N);

37: begin = clock();

ShellSort(test, N);

end = clock();

38: printf("\nShell sort %15f", (end - begin) / CLK_TCK);

39: CopyArrays(test, source, N);

40: begin = clock();

QuickSort(test, N, 0, N-1);

end = clock();

41: printf("\nQuick sort %15f", (end - begin) / CLK_TCK);

42: } 43:

44: void CopyArrays(int a[], int b[], int n) 45: { 46: int i;

47:

48: for (i = 0;

i < n;

i++) 49: a[i] = b[i];

50: } 51:

52: void InitArray(int a[], int n) 53: { 54: int i;

55:

56: randomize();

57: for (i = 0;

i < n;

i++) 58: a[i] = rand();

59: } 60:

61: void Swap(int *x, int *y) 62: { 63: int t = *x;

64:

65: *x = *y;

66: *y = t;

67: } 68:

69: void BubbleSort(int a[], int n) 70: { 71: int i, j;

72:

73: for (i = 0;

i < n;

i++) 74: for (j = 0;

j < n - i - 1;

j++) 75: if(a[j] > a[j + 1]) 76: Swap(&a[j], &a[j + 1]);

77: } 78:

79: void SelectSort(int a[], int n) 80: { 81: int i, j, k;

82:

83: for (i = 0;

i < n - 1;

i++) { 84: for (k = i, j = i + 1;

j < n;

j++) 85: if (a[j] < a[k]) 86: k = j;

87: Swap(&a[k], &a[i]);

88: } 89: } 90:

91: void InsertSort(int a[], int n) 92: { 93: int i, j;

94:

95: for (i = 1;

i <= n - 1;

i++) { 96: j = i;

97: while (a[j] < a[j-1] && j >= 1) { 98: Swap(&a[j], &a[j - 1]);

99: j--;

100: } 101: } 102: } 103:

104: void ShellSort(int a[], int n) 105: { 106: int i, j, k, temp;

107: int gap;

108: int d[] = {9, 5, 3, 2, 1};

109:

110: for (k = 0;

k < 5;

k++) { 111: gap = d[k];

112: for (i = gap;

i < n;

i++) { 113: temp = a[i];

114: for (j = i - gap;

temp < a[j] && j >= 0;

j -= gap) 115: a[j + gap] = a[j];

116: a[j + gap] = temp;

117: } 118: } 119: } 120:

121: void QuickSort(int a[], int n, int left, int right) 122: { 123: int i = left, j = right;

124: int test = a[(left + right) / 2];

125:

126: do { 127: while (a[i] < test) 128: i++;

129: while (a[j] > test) 130: j--;

131: if (i <= j) { 132: Swap(&a[i], &a[j]);

133: i++;

134: j--;

135: } 136: } while(i <= j);

137: if (i < right) 138: QuickSort(a, n, i, right);

139: if (j > left) 140: QuickSort(a, n, left, j);

141: } В строках 11-15 объявляются прототипы функций пяти методов сортировки. В строках 69-141 приведены уже знакомые вам описания. Все функции используют вспомогательную функцию Swap(), меняющую местами значение двух элементов (строки 61-67).

Символическая константа N, объявленная в строке 6, определяет количество сортируемых элементов. В строке 19 объявлено два массива:

исходный (source) и тестовый (test) размерности N.

В функции main() в строке 26 вызывается функция InitArray(), которая инициализирует исходный массив случайными значениями. После этого с помощью функции CopyArrays() исходный массив копируется в тестовый.

Обратите внимание на строку 28:

begin = clock();

BubbleSort(test, N);

end = clock();

Функция clock(), объявленная в заголовочном файле time.h, возвращает количество программных тактов (один такт примерно равен 1/18 секунды), прошедших со времени запуска программы. Таким образом, вызывая clock() до и после вызова функции сортировки мы можем засечь время выполнения функции в тактах. Чтобы определить время работы функции в секундах, используйте выражение (end – begin) / CLK_TCK, как это сделано в следующей строке.

После выполнения строки 28 массив test уже отсортирован, поэтому, прежде чем передать его следующей функции сортировки, в строке 30 мы вновь наполняем его случайными значениями из массива source.

После окончания работы Sorting Methods Test программы вы увидите таблицу, похожую на ту, что изображена на Number of elements: рис. 7.2. В полном соответствии с теорией метод «пузырька» Sorting methods Time (sec) оказался самым медленным – Bubble sort 28. секунд. Метод выбора показал Selection sort 7. значительно лучшие результаты: в Insertion sort 22. данном случае он работал в 4 раза Shell sort 0. быстрее «пузырька». Метод Quick sort 0. вставки затратил на выполнение задания примерно такое же время, Рис. 7.2. Результаты работы программы что и метод «пузырька», однако в sort случае частично упорядоченных массивов этот метод работает гораздо быстрее. Усовершенствованные методы сортировки затратили на сортировку менее одной секунды. Быстрая сортировка оказалась в 514 раз быстрее «пузырька»!

Упражнение. Расширьте тестирующие возможности программы sort, измеряя скорость работы пяти методов при сортировке частично отсортированных, полностью отсортированных и отсортированных в обратном порядке массивов.

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

• Обычно наилучшие результаты дает метод быстрой сортировки.

• При сортировке небольших массивов (менее 100 элементов) лучше использовать прямые методы, так как сложные алгоритмы имеют больший размер кода и при малом количестве сортируемых элементов неэффективны.

• Если сортируется связный список, то для него более эффективны методы вставок (метод обычных вставок или алгоритм Шелла).

• Если массив частично упорядочен, также лучше работают методы вставок.

Поиск данных Пожалуй, одним из самых частых действий в программировании и повседневной жизни является поиск. Что только мы не ищем! Конспекты, аудитории, IP-адреса, телефоны, – одним словом, любой предмет среди ему подобных. Причем, как будет видно из этого раздела, человек использует один из самых эффективных методов поиска, даже не подозревая об этом.

Поиск – это процесс, результатом которого является указание точного места расположения искомого элемента (или, как его еще называют, ключа).

Ниже рассмотрены несколько основных методов поиска.

Линейный поиск Если никакой дополнительной информации о разыскиваемых данных нет (например, неизвестно, отсортирован массив или нет), то самый очевидный подход – это простой последовательный просмотр массива. Такой метод называется линейным поиском.

Условие окончания поиска:

1. Элемент найден, т.е. array[i] == key, либо 2. Весь массив просмотрен и совпадения не обнаружено.

Используя эти условия, реализуем алгоритм линейного поиска:

int LinearSearch(int array[], int n, int key) { int i;

for (i = 0;

i < n;

i++) if (array[i] == key) return i;

return -1;

} Функция LinearSearch() принимает в виде параметров массив, в котором будет производиться поиск, его размерность n и искомый элемент key. Обратите внимание, что если элемент найден, то определяется только его первое вхождение в массив. Функция возвращает –1, если совпадения не существует.

Поскольку массив не упорядочен, вероятность нахождения требуемого значения в первом и последнем элементах массива одинакова. Таким образом, в среднем программа должна будет сравнить искомый элемент с половиной элементов массива, т.е. среднее число сравнений в данном методе равно n / 2. Очевидно, что метод линейного поиска в больших массивах применять нецелесообразно.

Бинарный поиск Алгоритм линейного поиска неэффективен по своей природе, и его улучшение – неблагодарная задача. Значит, задачу поиска нужно решать другим путем. А что если массив отсортировать? Этот путь очень эффективен, так как сортировка занимает немного времени, а пользу приносит многократную. Действительно, интенсивный поиск в неотсортированном массиве даже представить трудно: кто же будет пользоваться телефонным справочником, в котором фамилии не отсортированы по алфавиту?

Алгоритм поиска делением пополам (так иногда называют бинарный поиск) заключается в следующем. Для определенности предположим, что элементы в массиве упорядочены по возрастанию. Выберем случайно некоторый элемент, например array[m], и сравним его с искомым элементом key. Если он равен key, то поиск заканчивается, если он меньше key, то делаем вывод, что все элементы с индексами, меньшими или равными m, можно исключить из дальнейшего поиска;

если же он больше key, то исключаются индексы большие и равные m.

Выбор m совершенно не влияет на корректность алгоритма, но влияет на его эффективность. Очевидно, что чем большее количество элементов исключается на каждом шаге алгоритма, тем этот алгоритм эффективнее.

Оптимальным решением будет выбор среднего элемента, так как при этом в любом случае будет исключаться половина массива.

int BinarySearch (int array[], int key, int i, int j) { int middle;

while (i <= j) { middle = (i + j) / 2;

if (key == array[middle]) return middle;

else if (key < array[middle]) j = middle - 1;

else i = middle + 1;

} return -1;

} Приведенный алгоритм, как и в случае линейного поиска, находит первый совпадающий элемент в массиве. Максимальное число сравнений равно log2 n, время работы пропорционально log n.

Чтобы оценить эти цифры, представьте, что вам необходимо найти информацию в 1000-элементном массиве. Поскольку 210 > 1000, то, используя метод бинарного поиска, для нахождения заданного элемента вам нужно сделать не более десяти сравнений! Для поиска в массиве, содержащем миллион элементов, потребуется не более двадцати сравнений, поскольку 220 > 1 000 000. Чтобы найти элемент среди миллиарда подобных потребуется только около 30 сравнений, что значительно(!) меньше, чем порядка 500 000 000 сравнений при использовании линейного поиска.

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

Листинг 7.2. search.c (эффективность линейного и бинарного поиска) 1: #include 2: #include 3: #include 4: #include 5:

6: #define N 7: #define M 8:

9: void InitArray(int a[], int n);

10: int LinearSearch(int a[], int n, int key);

11: int BinarySearch(int a[], int key, int i, int j);

12: void ShellSort(int a[], int n);

13:

14: unsigned long counter1 = 0, counter2 = 0;

15:

16: main() 17: { 18: int array[N];

19: int i, key;

20:

21: clrscr();

22: for (i = 0;

i < M;

i++) { 23: InitArray(array, N);

24: key = array[random(N)];

25: LinearSearch(array, N, key);

26: ShellSort(array, N);

27: BinarySearch(array, key, 0, N);

28: } 29: counter1 /= M;

30: counter2 /= M;

31: printf("Linear Search...\n");

32: printf("Average amount of operations of matching: %ld\n", 33: counter1);

34: printf("\nBinary Search...\n");

35: printf("Average amount of operations of matching: %ld\n", 36: counter2);

37: printf("\nNumber of elements: %d\n", N);

38: return 0;

39: } 40:

41: void InitArray(int a[], int n) 42: { 43: int i;

44:

45: randomize();

46: for (i = 0;

i < n;

i++) 47: a[i] = rand();

48: } 49:

50: int LinearSearch(int array[], int n, int key) 51: { 52: int i;

53:

54: for (i = 0;

i < n;

i++) { 55: counter1++;

56: if (array[i] == key) 57: return i;

58: } 59: return -1;

60: } 61:

62: int BinarySearch(int a[], int key, int i, int j) 63: { 64: int middle;

65:

66: while (i <= j) { 67: middle = (j + i) / 2;

68: if (key == a[middle]) { 69: counter2++;

70: return middle;

71: } 72: else if (key < a[middle]) { 73: counter2++;

74: j = middle - 1;

75: } 76: else 77: i = middle + 1;

78: } 79: return -1;

80: } 81:

82: void ShellSort(int a[], int n) 83: { 84: int i, j, k, temp;

85: int gap;

86: int d[] = {9, 5, 3, 2, 1};

87:

88: for (k = 0;

k < 5;

k++) { 89: gap = d[k];

90: for (i = gap;

i < n;

i++) { 91: temp = a[i];

92: for (j = i - gap;

temp < a[j] && j >= 0;

j -= gap) 93: a[j + gap] = a[j];

94: a[j + gap] = temp;

95: } 96: } 97: } Функции InitArray() (описана в строках 41-48) и ShellSort (строки 82 97) уже вам знакомы. Символическая константа N определяет количество элементов в массиве. Глобальная переменная counter1 используется, чтобы подсчитать количество сравнений в алгоритме линейного поиска, counter2 – в алгоритме бинарного поиска.

Для того чтобы получить усредненное количество сравнений, поиск заданного значения выполняется в цикле (строки 22-28) M раз. На каждой итерации массив инициализируется случайными значениями (строка 23) и переменной key присваивается значение случайно выбранного элемента массива. После этого данное значение ищется методом линейного поиска (строка 25) и, после сортировки, методом бинарного поиска (строка 27).

После окончания цикла значение переменных counter1 и counter2 делится на M, что позволяет получить усредненное значение.

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

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

Рассмотрим функцию, реализующую алгоритм прямого поиска строки:

int DirectSearch(char *text, int n, char *str, int m) { int i = -1, j;

do { i++;

j = 0;

while (j < m && text[i + j] == str[j]) j++;

} while (! ((j == m) || (i == n - m)) );

if (j == m) return i;

return -1;

} В функцию передаются в виде параметров текст (text), количество символов в тексте (n), искомое слово или строка (str) и ее длина (m).

Вложенный цикл while начинает выполняться тогда, когда первый символ искомой строки совпадает с очередным, i-м, символом текста. Цикл завершается при исчерпании символов строки (перестает выполняться условие j < m) или при несовпадении очередных символов text и str (не выполнятся условие text[i + j] == str[j]).

Количество совпадений подсчитывается с использованием переменной j. Если совпадение произошло со всеми символами str (т.е. строка найдена), то выполняется условие j == m, и алгоритм завершается. В противном случае поиск продолжается до тех пор, пока не останется непросмотренной часть текста, которая содержит меньше символов, чем содержится в строке (т.е.

этот остаток уже не может совпасть с str).

В худшем случае метод прямого поиска требует порядка m n сравнений. Алгоритм работает достаточно эффективно в ситуациях, когда несовпадение символов обнаруживается достаточно рано, после небольшого числа сравнений во внутреннем цикле. Для текстов большой длины его использование, скорее всего, будет неэффективным.

Алгоритм Боуера–Мура В 1975 г. Р. Боуер и Д. Мур изобрели более эффективный алгоритм.

Его основным отличием от алгоритма прямого поиска является то, что сдвиг строки (слова) на каждом шаге алгоритма осуществляется не на один символ, а на некоторое количество символов, как правило, большее единицы.

В алгоритме Боуера-Мура сравнение символов начинается не с начала слова, а с конца. Перед началом поиска слово трансформируется в специальную таблицу. Для каждого символа x из алфавита рассчитывается величина dx – расстояние от самого правого в слове вхождения x до правого конца строки. Пусть, например, мы ищем строку “abcd”. Посмотрим на четвертую букву текста: если, к примеру, это буква e, то нет никакой необходимости читать первые три буквы. (В самом деле, в слове буквы e нет, поэтому оно может начаться не раньше пятой буквы.) Следовательно, мы можем сделать сдвиг вправо на всю длину строки. Если же, например, это буква b, то необходимо сделать сдвиг на величину dx = 2, равное расстоянию символа b до конца строки.

Функция BMSearch() реализует упрощенную схему алгоритма Боуера– Мура.

int BMSearch(char *text, int n, char *str, int m) { int i = m, j = m, k, i1, D[128];

/* Таблица расстояний */ for (i1 = 0;

i1 < n;

i1++) D[i1] = m;

for (i1 = 0;

i1 < m - 1;

i1++) D[(int)str[i1]] = m - i1 - 1;

/* Поиск заданной строки в тесте */ while(j > 0 && i <= n) { j = m;

k = i;

while(j > 0 && text[k - 1] == str[j - 1]) { k--;

j--;

} i += D[(int)text[i - 1]];

/* сдвиг слова */ } if (m > 0 && n > 0 && j == 0) return k;

/* возвращается позиция 1-го элемента строки */ return -1;

/* или -1 в случае неудачи */ } В подавляющем большинстве случаев БМ-поиск требует значительно меньше n сравнений. В лучшем случае число сравнений равно n / m.

Листинг 7.3 осуществляет поиск строки в тексте методом Буера–Мура и прямого поиска строки. Как и в предыдущем примере, программа оценивает эффективность алгоритмов по количеству сравнений, необходимых для поиска нужного элемента.

Листинг 7.3. tsearch.c (метод прямого поиска строки и БМ-поиск) 1: #include 2: #include 3: #include 4: #include 5:

6: #define N 7: int counter1 = 0, counter2 = 0;

8: int DirectSearch(char *text, int n, char *str, int m);

9: int BMSearch(char *text, int n, char *str, int m);

10:

11: void main() 12: { 13: char str[N], text[N];

14: int index, n, m;

15:

16: printf("Input the text: ");

17: gets(text);

18: n = strlen(text);

19: printf("Input the string to find: ");

20: gets(str);

21: m = strlen(str);

22: printf("\nText: %s\n", text);

23: printf("Text length: %d\n\n", n);

24: printf("Direct Search...\n");

25: index = DirectSearch(text, n, str, m);

26: printf("Position in text: %d\n", index);

27: printf("Amount of operations of matching: %d\n",counter1);

28: printf("\nBM-Search...\n");

29: index = BMSearch(text, n, str, m);

30: printf("Position in text: %d\n", index);

31: printf("Amount of operations of matching: %d\n",counter2);

32: } 33:

34: int DirectSearch(char *text, int n, char *str, int m) 35: { 36: int i = -1, j;

37: do { 38: i++;

39: j = 0;

40: counter1++;

41: while (j < m && text[i + j] == str[j]) { 42: j++;

43: counter1++;

44: } 45: } while (! ((j == m) || (i == n - m)));

46: if (j == m) 47: return i;

48: return -1;

49: } 50:

51: int BMSearch(char *text, int n, char *str, int m) 52: { 53: int i = m, j = m, k, i1, D[N];

54:

55: for (i1 = 0;

i1 < N;

i1++) 56: D[i1] = m;

57: for (i1 = 0;

i1 < m - 1;

i1++) 58: D[(int)str[i1]] = m - i1 - 1;

59:

60: while(j > 0 && i <= n) { 61: j = m;

62: k = i;

63: counter2++;

64: while(j > 0 && text[k - 1] == str[j - 1]) { 65: k--;

66: j--;

67: counter2++;

68: } 69: i += D[(int)text[i - 1]];

70: } 71: if (m > 0 && n > 0 && j == 0) 72: return k;

73: return -1;

74: } Замечание. В данном упрощенном примере текст представлен 128 байтовой строкой. Следующая глава расскажет, как обрабатывать большие объемы текстовой информации, хранящейся в файлах.

Какой метод выбрать?

Как и в случае с сортировками, идеального метода поиска не существует. Для поиска среди 20 элементов нет разницы, какой метод использовать (скорее тот, который меньше набирать), но если речь идет о поиске информации в массиве данных с сотнями тысяч элементов, метод бинарного поиска будет значительно эффективнее.

Используйте простой алгоритм прямого поиска строки в небольших текстах. При работе с большими объемами текстовой информации выберите метод Буера–Мура.

Резюме • Сортировка необходима, чтобы быстро найти нужную информацию в большом массиве данных. Сортировка и поиск являются одними из самых распространенных задач программирования.

• Прямые методы сортировки просты в реализации, но работают медленно.

Наиболее известны метод «пузырька», выбора и вставок. Эти методы идеально подходят для сортировки массивов, содержащих не более элементов. Усовершенствованные методы сортировки более сложны, но работают гораздо быстрее. Их лучше использовать при сортировке больших массивов данных.

• Запомните следующие формулы: время, необходимое для сортировки прямыми методами, пропорционально n2, методом Шелла – n1.2, методом быстрой сортировки – nlog n, где n – количество сортируемых элементов.

• При линейном поиске происходит сравнение каждого элемента массива с ключом. Среднее число сравнений в данном методе равно n / 2. Метод хорошо работает в массивах небольшого размера, а также (за неимением лучшего) в массивах, которые по каким-то причинам нельзя упорядочить.

• В бинарном поиске после каждого сравнения исключается половина элементов отсортированного массива. Среднее число сравнений в данном методе не превышает log2 n. При поиске информации в крупных массивах он оказывается наиболее эффективен.

• Метод прямого поиска строки просматривает текст последовательно, символ за символом, пытаясь установить соответствие между заданной строкой и частью текста. Метод работает хорошо, когда в тексте мало похожих слов, и расхождение обнаруживается на первых же итерациях. В худшем случае количество сравнений в данном методе равно произведению длины текста и слова: n m.

• В алгоритме поиска Боуера-Мура сравнение начинается с конца слова.

Символы в тексте просматриваются не последовательно, а скачками, что значительно ускоряет алгоритм. Кроме специально подобранных случаев, БМ-поиск требует количества сравнений, намного меньшего n, поэтому метод целесообразно применять для поиска в текстах большой длины.

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

Обзор функций Таблица 7. Функции работы со временем (time.h) Функция Прототип и краткое описание 1 clock_t clock(void);

clock() Возвращает приближенное время процессора, прошедшее с момента запуска программы;

чтобы получить время в секундах, необходимо разделить эту величину на значение CLK_TCK;

возвращает –1, если информация о времени недоступна или непредставима.

char *ctime(const time_t *tp);

ctime() Преобразует календарное время tp в 26-символьную строку в форме Thu Mar 18 13:09:23 2004\n\0, и возвращает указатель на эту строку.

double difftime(time_t t2, time_t t1);

difftime() Вычисляет разницу (t2 – t1) между двумя отметками календарного времени, выражает результат в секундах и возвращает его как число типа double.

Окончание табл. 7. 1 int stime(time_t *tp);

stime() Устанавливает системное время и дату, выраженных как количество секунд, прошедших с первой секунды 1970 года. tp указывает на новое значение времени.

time_t time(time_t *tp);

time() Возвращает текущее календарное время и также помещает его по адресу, указанному tp, если tp не равен NULL. Возвращает –1, если календарное время недоступно.

Примечание. Тип clock_t, который используют функции из табл. 7.1, представляет собой определяемый тип, соответствующий типу long.

Календарное время, которое он представляет, понимается как количество секунд, прошедших с первой секунды 1970 года.

8. Файлы Файлы являются существенной частью современных компьютерных систем. Они используются для хранения программ, документов, данных, корреспонденции, форм, графиков и многих других типов информации.

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

Что такое файл?

Файл – это именованный раздел (обычно на диске) для сохранения информации. Язык С рассматривает файл как последовательность байтов, каждый из которых считывается в индивидуальном порядке (рис. 8.1).

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

Признак конца 0 1 2 3 4 5 6 7 8 9.... n-1 файла....

EOF Рис. 8.1. Вид файла из n байтов Последний байт файла имеет значение EOF (End Of File). Используйте эту константу в ваших программах, чтобы определить конец файла.

Например, do { /* выполнять */... /* операторы */ } while (c != EOF) /* пока не встретится конец файла */ Язык С имеет богатую библиотеку функций чтения, записи файлов и выполнения других операций (см. раздел «Обзор функций»). Большинство функций для работы с файлами начинается на букву f. Примите к сведению следующие замечания:

• Перед тем как использовать файлы на диске, вы должны их открыть. При открытии вы должны задать специальный режим доступа, чтобы было понятно, с каким типом файлов вы собираетесь работать и что именно вы собираетесь делать: читать или записывать данные.

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

• После окончания работы с файлом его нужно закрыть. Закрытие файла переносит в файл все данные, буферизованные в памяти. Когда программа завершается, все открытые файлы автоматически закрываются. Но все же лучше всегда закрывать файлы явным образом.

Текстовые файлы Существует два основных способа обработки текстовых файлов: по символам или по строкам. Выбор обычно диктуют потребности вашей программы.

Чтение в посимвольном режиме Открытие файла в режиме посимвольного чтения дает вам возможность проверить каждый символ файла. Листинг 8.1 демонстрирует этот метод. Откройте новый проект и скомпилируйте вместе модули gets.c из главы 5 и rchar.c. Перед запуском программы создайте текстовый файл в том же каталоге, где находятся модули. После этого запустите программу на выполнение и введите имя текстового файла.

Листинг 8.1. rchar.c (посимвольное чтение текстового файла) 1: #include 2: #include 3: #include 4: #include 5: #include 6: #include "gets.h" 7:

8: #define SIZE 128 /* макс. размер строки для имени файла */ 9: void Error(const char *message);

10:

11: main() 12: { 13: FILE *fp;

14: char c, *filename;

15:

16: printf("File name? ");

17: filename = GetStringAt(SIZE);

18: fp = fopen(filename, "r");

19: if (!fp) 20: Error("Opening file");

21: while ((c = fgetc(fp)) != EOF) 22: putchar(c);

23: fclose(fp);

24: free(filename);

25: return 0;

26: } 27:

28: void Error(const char *message) 29: { 30: printf("\n\nError: %s\n\n", message);

31: exit(1);

32: } Функция main() использует три переменные. Строка 13 объявляет указатель типа FILE *. Файловые функции в дальнейшем используют этот указатель для доступа к файлам. Две другие переменные предназначены для хранения символов, прочитанных из файла (char с), и адресации строки, содержащей имя файла (char *filename).

Оператор filename = GetStringAt(SIZE);

устанавливает значение filename равным адресу строки, возвращаемой уже знакомой вам функцией GetStringAt(). После того как программа получит имя файла, программа в строке 18 вызывает функцию fopen(), для того чтобы открыть файл:

fp = fopen(filename, "r");

Первым параметром функции является имя файла, который необходимо открыть, второй параметр, “r”, определяет режим доступа к файлу. Этот параметр может быть одной из строк, перечисленных в табл. 8.1.

Таблица 8.1.

Режимы доступа к файлам для функции fopen() Строка Описание r Открывает файл только для чтения. Модификации файла не разрешены w Создает новый файл только для записи. Перезаписывает любой существующий файл с тем же именем. Чтение информации из файла не разрешено а Открывает файл в режиме только для записи с добавлением новой информации в конец файла. Если файла не существует, он создается, и любой существующий файл с тем же именем перезаписывается. Чтение информации из файла не разрешено r+ Открывает существующий файл для чтения и записи w+ Создает новый файл для чтения и записи. Перезаписывает любой существующий файл с тем же именем а+ Открывает файл в режиме чтения и записи для добавления новой информации в конец файла. Если файла не существует, он создается, и любой существующий файл с тем же именем перезаписывается Функция fopen() возвращает указатель файла типа FILE *, который вы должны запомнить в переменной, как показано в строке 18. Если возвращаемое значение равно NULL, значит, файл не может быть открыт (возможно, файла с указанным именем нет в директории либо он поврежден).

Если функция fopen() возвращает ненулевое значение, значит, файл открыт и готов к работе.

Строки 21-22 демонстрируют процесс посимвольной обработки текстового файла. Цикл while вызывает функцию fgetc(), передавая ей в качестве аргумента указатель на файл fp и присваивая результат функции переменной с. Функция fgetc() аналогична функции getchar(), но в отличие от нее требует аргумент типа FILE * и, таким образом, может читать символы из любого файла, открытого функцией fopen(). Строка отображает каждый символ, возвращаемый функцией fgetc().

Цикл while завершится, когда функция fgetc() возвратит значение EOF, означающее, что программа прочитала последний символ в файле. Отличие этого значения от любого допустимого данного, которое может вернуть функция fgetc() (и другие функции чтения из файлов), гарантируется. После этого строка 23 закрывает файл путем вызова функции fclose().

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

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

Листинг 8.2 показывает, как следует выполнять построчное чтение текстового файла. Скомпилируйте и запустите программу аналогично предыдущему примеру, но вместо модуля rchar.c включите rline.c. Текстовые файлы, которые вы будете читать с помощью этой программы, не должны содержать строки длиной более 128 символов.

Листинг 8.2. rline.c (построчное чтение текстового файла) 1: #include 2: #include 3: #include 4: #include 5: #include "gets.h" 6:

7: #define SIZE 128 /* максимальный размер строки имени файла*/ 8: void Error(const char *message);

9:

10: main() 11: { 12: FILE *fp;

13: char buffer[128], *filename;

14:

15: printf("File name? ");

16: filename = GetStringAt(SIZE);

17: fp = fopen(filename, "r");

18: if (!fp) 19: Error("Opening file");

20: while (fgets(buffer, 128, fp) != NULL) 21: puts(buffer);

22: fclose(fp);

23: return 0;

24: } 25:

26: void Error(const char *message) 27: { 28: printf("\n\nError: %s\n\n", message);

29: exit(1);

30: } Программа rline имеет одно существенное отличие от программы rchar.

Ее цикл while в строках 20-21 вызывает функцию fgets(), чтобы прочитать строку из файла в буфер, объявленный в строке 13. Функция fgets() требует наличия трех аргументов: строковой переменной для запоминания строки текста, максимального числа читаемых символов и переменной типа FILE *, инициализированной с помощью функции fopen().

При чтении строки из открытого файла функция fgets() добавляет в строку завершающий нуль. Если функция встречает символ новой строки (‘\n’), он также заносится в буфер. Убедитесь, что вы подготовили достаточно большой буфер для работы функции fgets(): любые строки, длина которых превышает размер буфера, усекаются.

Упражнение. Напишите программу, которая читает строки текстового файла и выводит их на экран в алфавитном порядке.

Посимвольная запись Чтобы создать новый текстовый файл, объявите переменную типа FILE *, например, с именем fp и откройте его следующим образом:

fp = fopen("newfile.txt", "w");

Режим “w” создает новый файл, перезаписывая существующий с таким же именем. Убедитесь, что это как раз то, что вы хотели сделать! Чтобы открыть существующий файл для чтения и записи, используйте режим “r+”.

В этом случае существующий файл не будет перезаписан.

После вызова функции fopen(), если fp не равно нулю, файл будет открыт и готов к приему символов. Например, записать в файл символы А, В и С можно следующим образом:

fputc(A, fp);

fputc(B, fp);

fputc(C, fp);

После работы с файлом закройте его с помощью функции fclose():

fclose(fp);

Pages:     | 1 | 2 || 4 |



© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.