🗊Презентация Линейные списки

ЛИНЕЙНЫЕ СПИСКИ

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

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

Для работы с однонаправленными списками шаблон структуры (структурный тип) будет иметь следующий вид: Для работы с однонаправленными списками шаблон структуры (структурный тип) будет иметь следующий вид: struct TList1 { Информационная часть (ИЧ) TList1 *next; – Адресная часть }; Информационная часть – описание полей (членов структуры), определяющих обрабаты-ваемую в списке информацию; next – указатель на следующий элемент.

Для работы с двунаправленными списками шаблон структуры будет иметь следующий вид: Для работы с двунаправленными списками шаблон структуры будет иметь следующий вид: struct TList2 { Информационная часть (ИЧ) TList2 *prev, *next; }; prev – указатель на предыдущий элемент; next – указатель на следующий элемент.

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

Структура данных СТЕК Структура данных СТЕК Стек – упорядоченный набор данных, в ко-тором добавление и удаление элементов производится только с конца, который на-зывают вершиной стека, т.е. стек – список с одной точкой доступа к его элементам. Стек это структура данных типа LIFO (Last In, First Out) – последним вошел, первым выйдет.

Графически Стек можно изобразить так: Графически Стек можно изобразить так:

Число элементов стека не ограничивается. При добавлении элементов в стек память должна динамически выделяться и освобождаться при удалении. Таким образом, стек – динамическая структура данных, состоящая из переменного числа элементов одинакового типа. Число элементов стека не ограничивается. При добавлении элементов в стек память должна динамически выделяться и освобождаться при удалении. Таким образом, стек – динамическая структура данных, состоящая из переменного числа элементов одинакового типа. Операции, выполняемые над стеком, имеют спе-циальные названия: push – добавление элемента (вталкивание); pop – удаление (извлечение) элемента, верхний элемент стека удаляется (не может приме-няться к пустому стеку).

Кроме этих обязательных операций используется операция top (peek) для чтения информации в вершине стека без извлечения. Кроме этих обязательных операций используется операция top (peek) для чтения информации в вершине стека без извлечения. Рассмотрим основные алгоритмы работы со стеком, взяв для простоты в качестве информационной части целые числа (int info;), хотя информационная часть может состоять из любого количества объектов допустимого типа, за исключением файлов.

Алгоритм формирования стека Алгоритм формирования стека Рассмотрим данный алгоритм для первых двух элементов. 1. Описание типа для структуры, содержащей информационное и адресное поля:

2. Объявление указателей на структуру (можно объявить в шаблоне глобально): 2. Объявление указателей на структуру (можно объявить в шаблоне глобально): Stack *begin, – Вершина стека *t; – Текущий указатель 3. Так как первоначально стек пуст: begin = NULL; 4. Захват памяти под первый элемент: t = new Stack; в памяти формируется конкретный адрес (обозначим его А1) для первого элемента, т.е. адрес текущего элемента t равен А1.

5. Ввод информации (обозначим i1); 5. Ввод информации (обозначим i1); а) формирование информационной части: t -> info = i1; б) формирование адресной части: значение адреса вершины стека записываем в адресную часть текущего элемента (там был NULL) t -> next = begin; На этом этапе получили:

6. Вершина стека переносится на созданный первый элемент: 6. Вершина стека переносится на созданный первый элемент: begin = t; В результате получается следующее:

8. Ввод информации для второго элемента (i2); 8. Ввод информации для второго элемента (i2); а) формирование информационной части: t -> info = i2; б) в адресную часть записываем адрес вершины, т.е. адрес первого (предыдущего) элемента (А1): t -> next = begin; Получаем:

Функция формирования элемента стека Функция формирования элемента стека Простейший вид функции (типа push), в которую передаются указатель на вершину (р) и введенная информация (in), а измененное значение вершины (t) возвращается в точку вызова оператором return: Stack* InStack (Stack *p, int in) { Stack *t = new Stack; // Захват памяти t -> info = in; // Формируем ИЧ t -> next = p; // Формируем АЧ return t; }

Участок программы с обращением к функции InStack для добавления n элементов (исполь-зуем случайные числа) в стек может иметь следующий вид: Участок программы с обращением к функции InStack для добавления n элементов (исполь-зуем случайные числа) в стек может иметь следующий вид: for (i = 1; i <= n; i++) { in = random (20); begin = InStack (begin, in); }

Если в функцию InStack указатель на вершину передавать по адресу, то она может иметь следующий вид: Если в функцию InStack указатель на вершину передавать по адресу, то она может иметь следующий вид: void InStack (Stack **p, int in) { Stack *t = new Stack; t -> info = in; t -> next = *p; *p = t; } Обращение к ней в данном случае будет: InStack (&begin, in);

Просмотр стека (без извлечения) Просмотр стека (без извлечения) 1. Устанавливаем текущий указатель на вершину t = begin; 2. Проверяем, если стек пуст (begin = NULL), то выводим сообщение и либо завершаем работу, либо переходим на формирование стека. 3. Если стек не пуст, выполняем цикл до тех пор, пока текущий указатель t не равен NULL, т.е. пока не обработаем последний элемент, адресная часть которого равна NULL.

4. ИЧ текущего элемента t -> info выводим на экран или в Memo1. 4. ИЧ текущего элемента t -> info выводим на экран или в Memo1. 5. Переставляем текущий указатель t на сле-дующий элемент: t = t -> next; 6. Конец цикла.

Функция, реализующая этот алгоритм: Функция, реализующая этот алгоритм: void View (Stack *p) { Stack *t = p; if ( p == NULL ) { // Или if (!p) cout << “ Стек пуст! ” << endl; return; } while( t != NULL) { cout << t->info << endl; t = t -> next; } } Обращение к этой функции: View (begin);

Алгоритм освобождения памяти Алгоритм освобождения памяти 1. Начинаем цикл, выполняющийся пока begin не станет равным NULL. 2. Устанавливаем текущий указатель на вершину: t = begin; 3. Вершину переставляем на следующий элемент: begin = begin -> next; 4. Освобождаем память, занятую бывшей верши-ной delete t; 5. Конец цикла.

Вариант 1. Функция, реализующая этот алго-ритм, может иметь следующий вид: Вариант 1. Функция, реализующая этот алго-ритм, может иметь следующий вид: void Del_All ( Stack **p ) { Stack *t; while ( *p != NULL) { t = *p; *p = (*p) -> next; delete t; } }

Вершина стека передается в функцию по адресу с помощью указателя для того, чтобы его измененное значение было возвращено из функции в точку вызова. Вершина стека передается в функцию по адресу с помощью указателя для того, чтобы его измененное значение было возвращено из функции в точку вызова. Обращение к этой функции: Del_All (&begin); После ее выполнения указатель на вершину begin будет равен NULL.

Вариант 2: Вариант 2: void Del_All ( Stack *&p ) { Stack *t; while ( p != NULL) { t = p; p = p -> next; delete t; } }

Вершина стека передается в функцию по адресу с помощью ссылки (копии адреса) для того, чтобы его измененное значение было возвращено из функции в точку вызова. Вершина стека передается в функцию по адресу с помощью ссылки (копии адреса) для того, чтобы его измененное значение было возвращено из функции в точку вызова. Обращение к этой функции: Del_All (begin); После ее выполнения указатель на вершину begin будет равен NULL.

Вариант 3: Вариант 3: Stack* Del_All ( Stack *p ) { Stack *t; while ( p != NULL) { t = p; p = p -> next; delete t; } return p; } В этом случае обращение к ней будет: begin = Del_All (begin);

В данном случае в функцию передаем указатель на вершину стека, а его измененное значение, равное NULL, возвращаем из функции в точку вызова с помощью оператора return. В данном случае в функцию передаем указатель на вершину стека, а его измененное значение, равное NULL, возвращаем из функции в точку вызова с помощью оператора return.

Алгоритм получения информации из вершины стека c извлечением Алгоритм получения информации из вершины стека c извлечением 1. Устанавливаем текущий указатель t на вершину t = begin; 2. Сохраняем значение ИЧ out (выводим на экран) out = begin -> info; 3. Переставляем вершину на следующий элемент begin = begin -> next; 4. Освобождаем память бывшей вершины t delete t; После этого в переменной out находится нужное нам значение, а стек стал короче на один элемент.

Функция (типа pop), в которую передаются вершина (р) и адрес переменной out для интересующей нас информации, измененное значение вершины (p) возвращается в точку вызова оператором return: Функция (типа pop), в которую передаются вершина (р) и адрес переменной out для интересующей нас информации, измененное значение вершины (p) возвращается в точку вызова оператором return: Stack* OutStack (Stack *p, int *out) { Stack *t = p; *out = p -> info; p = p -> next; delete t; return p; }

Обращение к этой функции: Обращение к этой функции: begin = OutStack ( begin, &out ); Необходимая нам информация out (в нашем примере тип int) известна в точке вызова, т.к. передается по адресу. Если в функцию OutStack указатель на вершину передавать по адресу, а нужную информацию out возвращать из функции оператором return, то она может иметь следующий вид:

int OutStack ( Stack **p ) { int OutStack ( Stack **p ) { int out ; Stack *t = *p; out = (*p) -> info; *p = (*p) -> next; delete t; return out; } Обращение к ней в данном случае будет: out = OutStack (&begin);

Рассмотрим примеры удаления из стека элементов, кратных 5. Рассмотрим примеры удаления из стека элементов, кратных 5. Текст функции удаления непосредственно из стека может иметь следующий вид:

Stack* Del_5(Stack *b) Stack* Del_5(Stack *b) { b = InStack (b, 21); // Добавляем любое число Stack *p = b; t = p ->next; // p предыдущий, t текущий while (t != NULL) { if ( t->info % 5 == 0 ) { p -> next = t -> next; delete t; t = p -> next; }

else { else { p = t; t = t -> next; } } t = b; // Удаление из вершины 21 b = b -> next; delete t; return b; } Обращение к функции: begin = Del_5 (begin);

Указатель на вершину стека передаем в функцию, а его измененное значение, возвращаем из функции в точку вызова с помощью оператора return. Указатель на вершину стека передаем в функцию, а его измененное значение, возвращаем из функции в точку вызова с помощью оператора return. Функция удаления из стека элементов, кратных 5, с использованием динамического массива:

Stack* Del_5_mas (Stack *b) Stack* Del_5_mas (Stack *b) { int n = 0, *a, i, m; Stack *t = b; //--------- Расчет количества элементов n ------- while (t != NULL) { n++; t = t -> next; } Form1->Memo1->Lines ->Add(“ Всего = " + IntToStr ( n ) );

a = new int[n]; // Создаем динамический массив a = new int[n]; // Создаем динамический массив // Извлекаем все элементы из стека в массив for ( i = 0; i < n; i++ ) b = OutStack ( b, a + i ); /* Удаляем из массива кратные 5, т.е. переписы-ваем в массив только те, что не кратны 5 */ for ( m = i = 0; i < n; i++ ) if ( a[i] % 5 != 0 ) a[m++] = a[i]; // m – количество оставшихся элементов

/* Создаем стек снова – переписываем в него элементы, оставшиеся в массиве: */ /* Создаем стек снова – переписываем в него элементы, оставшиеся в массиве: */ for ( i = 0; i < m; i++ ) b = InStack ( b, a[i] ); delete []a; // Освобождаем память /* Возвращаем в точку вызова вершину вновь созданного стека */ return b; } Обращение к функции: begin = Del_5_mas ( begin );

И в этом случае в функцию передаем указатель на вершину стека, а его измененное значение, возвращаем из функции в точку вызова оператором return. И в этом случае в функцию передаем указатель на вершину стека, а его измененное значение, возвращаем из функции в точку вызова оператором return. Функция создания нового стека из элементов уже созданного стека, не кратных 5:

Stack* New_Stack_5 (Stack *b) Stack* New_Stack_5 (Stack *b) { int inf; Stack *new_b = NULL; while (b != NULL) { b = OutStack ( b, &inf ); if ( inf % 5 != 0 ) new_b = InStack ( new_b, inf ); } return new_b; }

Обращение к функции: Обращение к функции: begin = New_Stack_5 ( begin ); Что в созданном стеке не совсем корректно в сравнении с исходным? Линейный поиск нужной информации в стеке может быть выполнен на базе функции просмотра View. Например, найдем в стеке количество элементов кратных 5 :

int Poisk (Stack *p) int Poisk (Stack *p) { int k = 0; Stack *t = p; while( t != NULL) { if ( t -> info % 5 == 0 ) k ++ ; t = t -> next; } return k; }

Часть кода с обращением к этой функции: Часть кода с обращением к этой функции: . . . int kol; . . . kol = Poisk (begin); if (kol == 0) Сообщение, что таких НЕТ! else Вывод результата! . . . В функцию передаем вершину стека, а в точку вызова возвращаем количество найденных элементов…