Лабораторная работа № 9 Задачи сортировки и поиска

ЦЕЛЬ РАБОТЫ: Закрепление теоретических знаний и приобретение практических навыков по составлению алгоритмов и программ различных методов сортировки.

Выполнение работы: в соответствии с заданиями пунктов 1-4, учитывая вариант (п. 3), составить и реализовать программу.

Задание

1. Сформировать при помощи генератора псевдослучайных чисел линейный целочисленный массив A[20], таким образом, что бы элементы массива принадлежали отрезку [-50, 50].

2. Выполнить в нём линейный поиск заданного элемента.

3. Отсортировать массив определённым методом в соответствии с вариантом (см. таблицу).

   Метод сортировки	Вариант
   Вставкой	1, 4, 7, 10, 13, 16, 19, 22
   Обменом	2, 5, 8, 11, 14, 17, 20, 23
   Выбором	3, 6, 9, 12, 15, 18, 21, 25

4. Выполнить бинарный поиск элемента.

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

Контрольные вопросы

1. Понятие сложности алгоритмов.

2. На какие классы делятся алгоритмы в соответствии с их временной или пространственной сложностью?

3. Постановка задачи сортировки данных.

4. Прямые и быстрые методы внутренней сортировки.

5. Алгоритм сортировки массива методом вставки.

6. Алгоритм сортировки массива методом прямого выбора.

7. Алгоритм сортировки массива методом прямого обмена.

8. Понятие инверсии.

9. Постановка задачи поиска элемента в массиве.

10. Алгоритм последовательного (линейного) поиска.

11. Алгоритм бинарного поиска.

10. Указатели и массивы

10.1. Понятие статической и динамической переменной

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

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

10.2. Указатели

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

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

type *ptr;

где type - один из предопределенных или определенных пользователем типов, а ptr - указатель. Например,

int *countPtr, count;

объявляет переменную countPtr типа int * (т.е. указатель на целое число) и переменную count целого типа. Символ * в объявлении относится только к countPtr. Каждая переменная, объявляемая как указатель, должна иметь перед собой знак «звездочка» (*). Если в приведенном примере желательно, чтобы и переменная count была указателем, надо записать:

int *countPtr, *count;

Символ * в этих записях обозначает операцию косвенной адресации.

Может быть объявлен и указатель на void:

void *Pv;

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

Pv = countPtr;

В Cи указатели используются широко. Они должны инициализироваться либо при своем объявлении, либо с помощью оператора присваивания. Указатель может получить в качестве начального значения 0, NULL или адрес. Указатель с начальным значением 0 или NULL ни на что не указывает. NULL – это символическая константа, определенная с целью показать, что данный указатель ни на что не указывает. Пример объявления указателя с его инициализацией:

int *countPtr = NULL;

Для присваивания указателю адреса некоторой переменной используется операция адресации &, которая возвращает адрес своего операнда. Например, если имеются объявления

int Step = 5;

int *ptr, Num;

то оператор

ptr = &Step;

присваивает адрес переменной Step указателю ptr.

Для того чтобы получить значение, на которое указывает указатель, используется операция *, обычно называемая операцией косвенной адресации или операцией разыменования. Она возвращает значение объекта, на который указывает ее операнд (т.е. указатель). Например, если продолжить приведенный выше пример, то оператор

Num = *ptr;

присвоит переменной Num значение 5, т.е. значение переменной Step, на которую указывает ptr.

Операцию разыменования нельзя применять к указателю на void, поскольку для него неизвестно, какой размер памяти надо разыменовывать.

Здесь необходимо обратить внимание на разночтение символа «*». Если символ «*» стоит перед идентификатором переменной при ее объявлении, то смысл этой «звездочки» – сказать, что объявляется не обычная переменная, а переменная-указатель. Во всех остальных случаях символ «*» читается и воспринимается программой как «взятие значения по адресу», то есть является операцией косвенной адресации.