АкушерствоАнатомияАнестезиологияВакцинопрофилактикаВалеологияВетеринарияГигиенаЗаболеванияИммунологияКардиологияНеврологияНефрологияОнкологияОториноларингологияОфтальмологияПаразитологияПедиатрияПервая помощьПсихиатрияПульмонологияРеанимацияРевматологияСтоматологияТерапияТоксикологияТравматологияУрологияФармакологияФармацевтикаФизиотерапияФтизиатрияХирургияЭндокринологияЭпидемиология

Сравнение строк

а) точное сравнение производится на полное совпадение строк или для определения, какая из них предшествует другой лексикографически (как в словарях). В языке C для этого служит функция strcmp.

б) приближенное сравнение используется при поиске слова, точное написание которого неизвестно, и желательно найти похожие на него слова (варианты написания) с измененными, пропущенными или переставленными буквами: Вильсон вместо Уилсон, Высотский вместо Высоцкий и т. п. Для этого есть много методов. Меру близости слов X и Y (расстояние между ними) можно, например, определять по формуле:

D(X,Y) = (1-K/(DX-1))*(1-K/(DY-1)) (3.1)

где DX, DY - длины слов; K - число пар соседних букв, входящих в оба слова одновременно; D(X,Y) = 0..1.

Пример: D("Саша","Маша") = (1-2/(4-1))*(1-2/(4-1)) = 1/9.

в) Другая разновидность приближенного сравнения - сопоставление слова с шаблоном (образцом). Так, в командах операционных систем UNIX и MS DOS имя файла может содержать метасимволы: '*' обозначает любое количество любых символов, '?' - один любой символ. Такое имя является шаблоном и заменяется последовательностью соответствующих ему имен файлов заданного каталога.

Например, имя a*.c обозначает все файлы с расширением "c", имена которых начинается на букву "a"; *.* - все файлы;??.txt - все файлы с расширением "txt", имена которых состоят из двух символов.

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

3. Поиск строки S длиной M в тексте T длиной N - определение индекса первого вхождения.

а) Прямой метод - просмотр текста и строки слева направо с продвижением на один символ. В худшем случае (когда T содержит N-1 букв 'A' и одну 'B', S содержит M-1 букв 'A' и одну 'B') требует порядка O(N*M) сравнений.

б) БМ-алгоритм (Боуер и Мур, 1975) - просмотр текста слева направо, строки справа налево; при несовпадении строка сдвигается на расстояние, равное смещению от конца строки до символа текста в ней. Почти всегда меньше N сравнений, в лучшем случае O(N/M) сравнений.

в) КМП-алгоритм (Кнут, Моррис и Пратт, 1970) - при несовпадении строка сдвигается на длину максимальной предшествующей подстроки, совпадающей с началом строки. Требует порядка O(N+M) операций.

Массив

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

Размерность (число измерений) массива – это количество индексов каждого элемента. Массив с n индексами называют n-мерным. Одномерный массив называют вектором, двумерный - матрицей. Матрица состоит из строк и столбцов. Первый индекс - номер строки, второй - номер столбца.

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

Пример 3.16. Непрямоугольный массив - матрица Y - состоит из следующих элементов

Y[1,2] Y[1,3]

Y[2,1] Y[2,2] Y[2,3] Y[2,4]

Y[3,1] Y[3,2]

Здесь пределы изменения номера столбца зависят от номера строки: в 1-й строке от 2 до 3, во 2-й строке от 1 до 4, в 3-й – от 1 до 2. Аналогично диапазон номеров строки зависит от номера столбца: в 1-м столбце – от 2 до 3, во 2-м столбце – от 1 до.3 и т. д.

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

Массивы имеются во всех языках высокого уровня, причем в большинстве языков, в том числе C и Pascal, используются только прямоугольные массивы. Обычно допускаются только поэлементные операции, а над всем массивом иногда разрешается выполнять ввод/вывод.

В некоторых языках (APL, PL/1 и др.) имеются групповые операции над всем массивом. В языке ассемблера программисту самому приходится реализовать массив.

Базовой операцией над массивом является доступ к элементу по его индексам для определения его адреса и получения или изменения его значения.

Дата добавления: 2015-09-27 | Просмотры: 412 | Нарушение авторских прав