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

Содержание слайда: ЛИНЕЙНЫЕ СПИСКИ

Содержание слайда: Некоторые задачи требуют введения структур, способных увеличивать или уменьшать свой размер в процессе работы программы. Некоторые задачи требуют введения структур, способных увеличивать или уменьшать свой размер в процессе работы программы. Основу таких структур составляют динамиче-ские переменные, которые хранятся в неко-торой области памяти. Обращение к ним производится с помощью указателя. Как правило, такие переменные организуются в виде списков, элементы которых являются структурами (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 Вывод результата! . . . В функцию передаем вершину стека, а в точку вызова возвращаем количество найденных элементов…