Методичка Программирование

begin

if (m[i]>m[i+1]) then //сравниваем соседние элементы begin

swap(m[i],m[i+1]); //переставляем их местами i:=1; //переходим к первому элементу массива continue; //начинаем цикл заново,

// (не делаем i:=i+1;)

end;

i:=i+1; // переходим у следующему элементу end;

end;

Шейкерная сортировка (сложность O(n2))

Анализируя метод пузырьковой сортировки можно отметить два обстоятельства:

1)если при движении по части массива перестановки не происходят, то эта часть массива уже отсортирована и, следовательно, ее можно исключить из рассмотрения;

2)при движении по массиву максимальный элемент «всплывает» на последнюю позицию, а минимальный элемент сдвигается только на одну позицию влево.

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

Изменение последовательности элементов происходит следующим образом:

Условные обозначения:

|2 5| – элементы, которые поменяли местами;

и – направления движения.

Поиск

Во многих задачах иногда возникает необходимость поиска номера элемента, например, в массиве по значению элемента массива. Если в задаче

81

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

Бинарный (для массива, отсортированного по возрастанию) (сложность

O(log2 n)

1.L– первый элемент массива, R– последний элемент массива.

2.Проверить средний элемент массива (m L R ),

2

a)если он равен искомому, то поиск закончен;

b)если он меньше искомого, то установить R на текущий элемент13, перейти к шагу 1;

c)если он больше искомого, то установить L на текущий элемент14, перейти к шагу 1.

Интерполяционный поиск (сложность O(log log2 n)

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

m (Val [L]) (R L) L,

([R] [L])

где R – правая граница поиска; L – левая граница поиска;

[X] – значение элемента массива с индексом X;

Val – значение элемента, номер которого необходимо найти.

2. Как и в методе бинарного поиска устанавливаем новое значение R или L.

Задание

Напишите процедуры для сортировки элементов массива. Определите количество сравнений, перестановок выполняемых при сортировке массива размером: 10, 100, 1000, 10000 элементов, составьте таблицу с результатами; для каждого размера массива проведите сравнение 5 случайно сгенерированных массивов и найдите среднее арифметическое количества сравнений и перестановок.

Методы сортировки:

1) пузырьковая сортировка (bubble sort);

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

14И здесь необходимо пропустить средний элемент, т.к. он не является искомым.

82

2)сортировка методом прямого выбора (direct sort);

3)гномья сортировка (gnome sort);

4)сортировка перемешиванием (шейкерная сортировка).

Напишите функции для поиска номера элемента в отсортированном массиве по его значению. Определите количество сравнений, выполняемых при поиске элемента в массиве размером 10,100,1000,10000 элементов, составьте таблицу с результатами. Для каждого размера массива проведите сравнение 5 случайно выбранных чисел и найдите среднее арифметическое количества сравнений.

Методы поиска:

1)поиск перебором;

2)бинарный поиск в отсортированном массиве;

3)интерполяционный поиск в отсортированном массиве.

Варианты заданий

В соответствии с вариантом, выберите из табл. 9 методы сортировки и поиска и напишите соответствующие подпрограммы.

Тема № 7. Строки

В Object Pascal cтроки могут быть представлены следующими типами:

ShortString, LongString и WideString. Различаются эти типы предельно допустимой длиной строки, способом выделения памяти для переменных и способом кодирования символов.

Переменной типа ShortString память выделяется статически, т. е. до начала выполнения программы, и количество символов такой строки не может превышать 255. Для переменных типа LongString и WideString память выделяется динамически – во время работы программы.

Помимо перечисленных выше типов, можно применять универсальный строковый тип String. Тип String эквивалентен типу ShortString.

Переменная строкового типа должна быть объявлена в разделе объявления переменных. Инструкция объявления в общем виде выглядит так:

Имя: String;

83

или

Имя: String [длина]

где:

имя – имя переменной;

String – ключевое слово обозначения строкового типа;

длина – константа целого типа, которая задает максимально допустимую длину строки.

Пример объявления переменных строкового типа: name: string[30];

buff: string;

Если в объявлении строковой переменной длина строки не указана, то ее длина задается равной 255 символам, т. е. объявления

stroka: string [255];

и

stroka: string; – эквивалентны.

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

parol:= 'Секретный пароль';

или

parol:= '2001';

Следует обратить внимание, что инструкция parol:=2001; неверная, так как тип константы не соответствует типу переменной. Во время компиляции этой инструкции будет выведено сообщение:

incompatible types: 'Char' and 'Integer' - (типы Char

и Integer несовместимы).

Используя операции =, <, >, <=, >= и <>, переменную типа String можно сравнить с другой переменной типа String или со строковой константой. Строки сравниваются посимвольно, начиная с первого символа. Если все символы сравниваемых строк одинаковые, то такие строки считаются равными. Если в одинаковых позициях строк находятся разные символы, большей считается та строка, у которой в этой позиции находится символ с большим кодом. В табл. 10 приведены примеры сравнения строк.

84

Кроме операции сравнения, к строковым переменным и константам можно применить операцию сложения, в результате выполнения которой получается новая строка. Например, в результате выполнения инструкций

first__name: ='Иван' ; last_name:='Иванов'; full_name:=first_name+last_name;

переменная full_name получит значение 'Иван Иванов'.

Стандартные функции обработки строк

В языке Object Pascal есть функций и процедур для обработки строк. Функция length возвращает длину строки. У этой функции один параметр

– выражение строкового типа. Значением функции length (целое число) является количество символов, из которых состоит строка.

Например, в результате выполнения инструкций n:=length('Иванов');

m:=length(' Невский проспект ');

значения переменных n и m будут равны 6 и 20 соответственно.

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

delete(str, p , n)

где:

str – переменная или константа строкового типа;

p – номер символа, с которого начинается удаляемая подстрока;

n – длина удаляемой подстроки.

Например, в результате выполнения инструкций p:='Пётр Иванов';

delete(s,5,7);

значением переменной s будет строка ' Пётр'.

Функция роs позволяет определить положение подстроки в строке. В общем виде обращение к функции выглядит так:

pos (SubStr,Str);

где SubStr –строковая константа или переменная, которую надо найти. Str – строка в которой производится поиск.

Например, в результате выполнения инструкции

р := pos('Ив', 'Пётр Иванов');

значение переменной р будет равно 6. Если в строке нет искомой подстроки, то значение функции pos будет равно нулю.

Функция сору позволяет выделить фрагмент строки. В общем виде обращение к функции сору выглядит так:

сору( str, p, n );

где:

85

str – выражение строкового типа, содержащее строку, фрагмент которой надо получить;

p – номер первого символа, с которого начинается выделяемая подстрока;

n – длина выделяемой подстроки.

Например, в результате выполнения инструкций

st:= 'Инженер Иванов'; fam:=copy(st, 9, 6) ;

значением переменной fam будет строка 'Иванов'.

Функция UpperCase возвращает строку, в которой все латинские буквы переведены в верхний регистр. В общем виде обращение к функции UpperCase выглядит так:

UpperCase(S);

где:

S – строка, символы в которой нужно перевести в верхний регистр.

Функция LowerCase возвращает строку, в которой все латинские буквы переведены в нижний регистр. В общем виде обращение к функции LowerCase выглядит так:

LowerCase (S);

где:

S – строка, символы в которой нужно перевести в нижний регистр.

Образец выполнения задания

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

Текст программы (результат ее работы приведен на рис. 21):

Function word_count(s:string):integer; Var i,word_cnt,char_cnt,any_cnt:integer; begin

for i:=1 to Length(S) do //просматриваем всю строку begin

if(S[i]=’ ’) then //если текущий символ пробел begin

if((char_cnt= any_cnt) and (any_cnt>0)) then //П. 2.а алгоритма

86

any_cnt:= any_cnt+1; //увеличиваем счетчик символов if(S[i] in [‘A’..’Z’,’a’..’z’])) then //если это

буква то

if((char_cnt= any_cnt) and (any_cnt>0)) then //п. 5.а

алгоритма

word_cnt:= word_cnt+1;

Result:= word_cnt; //возвращаем кол-во слов end;

Var str:string; begin

Write(‘stroka:’) ; Readln(str);

Writeln(‘slov: ’, word_count(str)); Readln;

end.

Рис. 21. Результат работы программы

Варианты домашних заданий

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

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

2.Найти самое короткое слово в предложении.

3.Найти самое длинное слово в предложении.

4.Найти среднюю длину слов в предложении.

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

87

6.Найти самое короткое слово в предложение из слов, длиной не менее 4 символов.

7.Подсчитать количество слов, в которых встречаются гласные буквы и цифры.

8.Подсчитать количество слов, в которых встречаются согласные буквы и цифры.

9.Подсчитать количество слов, в которых встречаются только гласные буквы.

10.Подсчитать количество слов, в которых встречаются только согласные буквы.

11.Подсчитать количество слов, в которых встречаются цифры.

12.Подсчитать количество слов, состоящих только из цифр.

13.Подсчитать количество слов, состоящих только из заглавных латинских букв.

14.Подсчитать количество слов, состоящих только из букв.

15.Подсчитать количество слов, состоящих только из строчных букв.

16.Подсчитать количество слов, состоящих только из строчных букв, но начинающихся с большой буквы.

17.Вывести на экран все слова, начинающиеся с цифры, а заканчивающиеся строчной латинской буквой.

18.Вывести на экран все слова, заканчивающиеся заглавной буквой.

19.Вывести на экран все слова, начинающиеся не с цифры.

20.Вывести на экран все слова, начинающиеся с заглавной буквы.

21.Вывести на экран все слова, начинающиеся с заглавной буквы, а заканчивающиеся цифрой.

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

23.Вывести на экран все слова, преобразовав их следующим образом: заменить в каждом слове первую букву на последнюю букву в этом слове.

24.Вывести на экран все слова, преобразовав их следующим образом: поменять местами первую и последнюю буквы.

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

Тема № 8. Динамические структуры данных

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

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

88

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

Каждый элемент списка представим записью с двумя полями:

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

ссылка на следующий элемент списка.

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

С учетом сказанного, мы можем описать элемент списка так:

данных, например число integer

Next:pTList;//служебная информация (адрес следующего //элемента, или nil если его нет)

end;

Чтобы иметь возможность оперировать со списком как с единым объектом, введем в употребление указатель на начало списка – переменную root, которая указывает на первое звено списка.

Для списков обычно определяются такие операции, как:

добавление нового элемента списка (вставка звена);

удаление элемента;

просмотр (или прохождение) списка;

поиск данных в списке;

сортировка списка;

обращение (реверсирование) списка, т.е. перестановка всех его элементов в обратном порядке.

Односвязный линейный список

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

89

Рис. 22. Односвязный линейный список

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

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

2.Список также «рвётся» по месту вставки или удаления звена, но указатель в элементе списка, ставшем последним, получает какое-то произвольное значение, которое трактуется как адрес следующего элемента (реально не существующего), у которого также есть указатель next, содержащий какой-то адрес, и так далее, до тех пор, пока случайно не попадётся блок данных, для которого указатель next не будет равен nil. При попытке просмотра списка на дисплей сначала выводятся правильные данные, а затем случайный набор символов и в некоторый момент времени может появиться ошибка об обращении к несуществующему адресу памяти.

Вобоих случаях к элементам в «оторвавшейся» части («хвосте») списка больше нет доступа, и хранящиеся в них данные можно считать потерянными.

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

//E1 – элемент, за которым добавляем новый элемент //data – добавляемый данные

procedure add_data(var E1:pTList;data:integer); var tmp:pTList; //новый элемент

begin

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

90