Линейные списки

Июль 31, 2022

Главная
Информатика
Линейные списки

Содержание

2. Некоторые задачи требуют введения структур, способных увеличивать или уменьшать свой размер в процессе работы программы. Основу
3. Если для связи элементов в структуре задан указатель (адресное поле) на следующий элемент, то такой список
4. Для работы с однонаправленными списками шаблон структуры (структурный тип) будет иметь следующий вид: struct TList1 {
5. Схема такого списка может иметь вид: begin – адрес первого элемента в списке; Адресная часть последнего
6. Для работы с двунаправленными списками шаблон структуры будет иметь следующий вид: struct TList2 { Информационная часть
7. Схема такого списка будет иметь вид: begin и end – адреса первого и последнего элементов в
8. Над списками обычно выполняются следующие операции: – начальное формирование списка (создание первого элемента); – добавление нового
9. Структура данных СТЕК Стек – упорядоченный набор данных, в ко-тором добавление и удаление элементов производится только
10. Графически Стек можно изобразить так: Стек получил свое название из-за схожести с обоймой патронов: когда добавляется
11. Число элементов стека не ограничивается. При добавлении элементов в стек память должна динамически выделяться и освобождаться
12. Кроме этих обязательных операций используется операция top (peek) для чтения информации в вершине стека без извлечения.
13. Алгоритм формирования стека Рассмотрим данный алгоритм для первых двух элементов. 1. Описание типа для структуры, содержащей
14. 2. Объявление указателей на структуру (можно объявить в шаблоне глобально): Stack *begin, – Вершина стека *t;
15. 5. Ввод информации (обозначим i1); а) формирование информационной части: t -> info = i1; б) формирование
16. 6. Вершина стека переносится на созданный первый элемент: begin = t; В результате получается следующее: 7.
17. 8. Ввод информации для второго элемента (i2); а) формирование информационной части: t -> info = i2;
18. 9. Вершина стека снимается с первого и устана-вливается на новый элемент (A2): begin = t; Получается
19. Функция формирования элемента стека Простейший вид функции (типа push), в которую передаются указатель на вершину (р)
20. Участок программы с обращением к функции InStack для добавления n элементов (исполь-зуем случайные числа) в стек
21. Если в функцию InStack указатель на вершину передавать по адресу, то она может иметь следующий вид:
22. Просмотр стека (без извлечения) 1. Устанавливаем текущий указатель на вершину t = begin; 2. Проверяем, если
23. 4. ИЧ текущего элемента t -> info выводим на экран или в Memo1. 5. Переставляем текущий
24. Функция, реализующая этот алгоритм: void View (Stack *p) { Stack *t = p; if ( p
25. Алгоритм освобождения памяти 1. Начинаем цикл, выполняющийся пока begin не станет равным NULL. 2. Устанавливаем текущий
26. Вариант 1. Функция, реализующая этот алго-ритм, может иметь следующий вид: void Del_All ( Stack **p )
27. Вершина стека передается в функцию по адресу с помощью указателя для того, чтобы его измененное значение
28. Вариант 2: void Del_All ( Stack *&p ) { Stack *t; while ( p != NULL)
29. Вершина стека передается в функцию по адресу с помощью ссылки (копии адреса) для того, чтобы его
30. Вариант 3: Stack* Del_All ( Stack *p ) { Stack *t; while ( p != NULL)
31. В данном случае в функцию передаем указатель на вершину стека, а его измененное значение, равное NULL,
32. Алгоритм получения информации из вершины стека c извлечением 1. Устанавливаем текущий указатель t на вершину t
33. Функция (типа pop), в которую передаются вершина (р) и адрес переменной out для интересующей нас информации,
34. Обращение к этой функции: begin = OutStack ( begin, &out ); Необходимая нам информация out (в
35. int OutStack ( Stack **p ) { int out ; Stack *t = *p; out =
36. Рассмотрим примеры удаления из стека элементов, кратных 5. Текст функции удаления непосредственно из стека может иметь
37. Stack* Del_5(Stack *b) { b = InStack (b, 21); // Добавляем любое число Stack *p =
38. else { p = t; t = t -> next; } } t = b; //
39. Указатель на вершину стека передаем в функцию, а его измененное значение, возвращаем из функции в точку
40. Stack* Del_5_mas (Stack *b) { int n = 0, *a, i, m; Stack *t = b;
41. a = new int[n]; // Создаем динамический массив // Извлекаем все элементы из стека в массив
42. /* Создаем стек снова – переписываем в него элементы, оставшиеся в массиве: */ for ( i
43. И в этом случае в функцию передаем указатель на вершину стека, а его измененное значение, возвращаем
44. Stack* New_Stack_5 (Stack *b) { int inf; Stack *new_b = NULL; while (b != NULL) {
45. Обращение к функции: begin = New_Stack_5 ( begin ); Что в созданном стеке не совсем корректно
46. int Poisk (Stack *p) { int k = 0; Stack *t = p; while( t !=
48. Скачать презентацию

Слайд 2

Некоторые задачи требуют введения структур, способных увеличивать или уменьшать свой размер

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

Слайд 3

Если для связи элементов в структуре задан указатель (адресное поле) на

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

Слайд 4

Для работы с однонаправленными списками шаблон структуры (структурный тип) будет иметь

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

Слайд 5

Схема такого списка может иметь вид:
begin – адрес первого элемента в

списке;
Адресная часть последнего элемента равна NULL – признак того, что следующего за ним НЕТ!

Слайд 6

Для работы с двунаправленными списками шаблон структуры будет иметь следующий вид:
struct

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

Слайд 7

Схема такого списка будет иметь вид:
begin и end – адреса первого

и последнего элементов в списке;
Адресные части prev первого элемента и next последнего элемента равны NULL.

Слайд 8

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

элемента);
– добавление нового элемента в список;
– обработка (просмотр, поиск, удаление и т.п.);
– освобождение памяти, занятой всем списком.

Слайд 9

Структура данных СТЕК
Стек – упорядоченный набор данных, в ко-тором добавление и

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

Слайд 10

Графически Стек можно изобразить так:
Стек получил свое название из-за схожести с

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

Слайд 11

Число элементов стека не ограничивается. При добавлении элементов в стек память

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

Слайд 12

Кроме этих обязательных операций используется операция top (peek) для чтения информации

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

Слайд 13

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

для структуры, содержащей информационное и адресное поля:

Структурный тип (шаблон) рекомендуется объ-являть глобально:
struct Stack {
int info;
Stack *next;
} ;

Слайд 14

2. Объявление указателей на структуру (можно объявить в шаблоне глобально):
Stack

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

Слайд 15

5. Ввод информации (обозначим i1);
а) формирование информационной части:
t -> info

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

Слайд 16

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

получается следующее:

7. Захват памяти под второй элемент:
t = new Stack;
формируется конкретный адрес (A2) для второго элемента.

Слайд 17

8. Ввод информации для второго элемента (i2);
а) формирование информационной части:
t

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

Слайд 18

9. Вершина стека снимается с первого и устана-вливается на новый элемент

(A2):
begin = t;
Получается следующая цепочка:

Обратите внимание, что действия 7, 8 и 9 идентичны действиям 4, 5 и 6, т.е. добавление новых элементов в стек можно выполнять в цикле, до тех пор, пока это необходимо.

Слайд 19

Функция формирования элемента стека
Простейший вид функции (типа push), в которую передаются

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

Слайд 20

Участок программы с обращением к функции InStack для добавления n элементов

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

Слайд 21

Если в функцию InStack указатель на вершину передавать по адресу, то

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

Слайд 22

Просмотр стека (без извлечения)
1. Устанавливаем текущий указатель на вершину
t =

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

Слайд 23

4. ИЧ текущего элемента t -> info выводим на экран или

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

Слайд 24

Функция, реализующая этот алгоритм:
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);

Слайд 25

Алгоритм освобождения памяти
1. Начинаем цикл, выполняющийся пока begin не станет равным

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

Слайд 26

Вариант 1. Функция, реализующая этот алго-ритм, может иметь следующий вид:
void Del_All

( Stack **p ) {
Stack *t;
while ( *p != NULL) {
t = *p;
*p = (*p) -> next;
delete t;
}
}

Слайд 27

Вершина стека передается в функцию по адресу с помощью указателя для

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

Слайд 28

$Вариант 2: void Del_All ( Stack &p ) { Stack t;$

Вариант 2:
void Del_All ( Stack &p ) {
Stack t;
while ( p

!= NULL) {
t = p;
p = p -> next;
delete t;
}
}

Слайд 29

Вершина стека передается в функцию по адресу с помощью ссылки (копии

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

Слайд 30

$Вариант 3: Stack* Del_All ( Stack p ) { Stack t;$

Вариант 3:
Stack* Del_All ( Stack p ) {
Stack t;
while ( p

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

Слайд 31

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

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

Слайд 32

Алгоритм получения информации из вершины стека c извлечением
1. Устанавливаем текущий указатель

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

Слайд 33

Функция (типа pop), в которую передаются вершина (р) и адрес переменной

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

Слайд 34

Обращение к этой функции:
begin = OutStack ( begin, &out );
Необходимая

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

Слайд 35

int OutStack ( Stack **p ) {
int out ;
Stack *t

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

Слайд 36

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

из стека может иметь следующий вид:

Слайд 37

$Stack* Del_5(Stack *b) { b = InStack (b, 21); // Добавляем$

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;
}

Слайд 38

else {
p = t;
t = t -> next;
}

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

Слайд 39

Указатель на вершину стека передаем в функцию, а его измененное значение,

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

Слайд 40

$Stack* Del_5_mas (Stack b) { int n = 0, a, i,$

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 ) );

Слайд 41

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 – количество оставшихся элементов

Слайд 42

/* Создаем стек снова – переписываем в него элементы, оставшиеся в

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

Слайд 43

И в этом случае в функцию передаем указатель на вершину стека,

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

Слайд 44

$Stack* New_Stack_5 (Stack b) { int inf; Stack new_b = NULL;$

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;
}

Слайд 45

Обращение к функции:
begin = New_Stack_5 ( begin );
Что в созданном

стеке не совсем корректно в сравнении с исходным?
Линейный поиск нужной информации в стеке может быть выполнен на базе функции просмотра View.
Например, найдем в стеке количество элементов кратных 5 :

Слайд 46

int Poisk (Stack p)
{
int k = 0;
Stack t = p;
while(

t != NULL) {
if ( t -> info % 5 == 0 )
k ++ ;
t = t -> next;
}
return k;
}

Линейные списки

Содержание

Некоторые задачи требуют введения структур, способных увеличивать или уменьшать свой размер

Если для связи элементов в структуре задан указатель (адресное поле) на

Для работы с однонаправленными списками шаблон структуры (структурный тип) будет иметь

Схема такого списка может иметь вид: begin – адрес первого элемента в

Для работы с двунаправленными списками шаблон структуры будет иметь следующий вид:struct

Схема такого списка будет иметь вид: begin и end – адреса первого

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

Структура данных СТЕКСтек – упорядоченный набор данных, в ко-тором добавление и

Графически Стек можно изобразить так:Стек получил свое название из-за схожести с

Число элементов стека не ограничивается. При добавлении элементов в стек память

Кроме этих обязательных операций используется операция top (peek) для чтения информации

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

2. Объявление указателей на структуру (можно объявить в шаблоне глобально): Stack

5. Ввод информации (обозначим i1); а) формирование информационной части: t -> info

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

8. Ввод информации для второго элемента (i2); а) формирование информационной части: t

9. Вершина стека снимается с первого и устана-вливается на новый элемент

Функция формирования элемента стекаПростейший вид функции (типа push), в которую передаются

Участок программы с обращением к функции InStack для добавления n элементов

Если в функцию InStack указатель на вершину передавать по адресу, то

Просмотр стека (без извлечения)1. Устанавливаем текущий указатель на вершину t =

4. ИЧ текущего элемента t -> info выводим на экран или

Функция, реализующая этот алгоритм:void View (Stack *p) { Stack *t = p; if

Алгоритм освобождения памяти1. Начинаем цикл, выполняющийся пока begin не станет равным

Вариант 1. Функция, реализующая этот алго-ритм, может иметь следующий вид: void Del_All