Динамические структуры данных. Прикладное программирование

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

Прикладное программирование

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

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

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

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

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

Динамическая
структура
характеризуется тем что:
данных
она не имеет имени;
ей выделяется память в процессе выполнения
программы;
количество элементов структуры может не
фиксироваться;

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

размерность структуры может меняться в
процессе выполнения программы;
в процессе выполнения программы может
меняться характер взаимосвязи
элементами структуры.
между

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

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

7. Указатели

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

8. Указатели

Если имеем объявление int а,
то
можно
определить
переменной &а.
адрес
этой
Если pа - указатель, который будет указывать
на
переменную
типа
int,
то
можем
записать: pа=&а.

9. Указатели

• Существует унарная операция *
• (она называется операцией разыменования),
которая
воздействует
на переменную,
содержащую адрес объекта (т. е. на
указатель).

10. Указатели

При этом извлекается содержимое переменной,
адрес которой находится в указателе.
Если, pа=&а, то, воздействуя на обе части
операцией *, получим (по определению этой
операции): *pа=а;.

11. Указатели

Исходя из этого, указатель объявляется так:
<тип переменной>* <имя указателя>
Здесь:
•<тип переменной> - это тип той переменной, на
которую указывает указатель, т. е. тип переменной,
чей адрес может находился в переменной, которую
мы задаем как указатель;
•<имя указателя> - это имя переменной.

12. Указатели

Если мы присвоим указателю константу 0, то
получим указатель с нулевым значением.
Такой
указатель
можно
сравнивать
с
мнемоническим
NULL,
определенным
в
стандартной библиотеке stdio.h

13. Указатели

Указатель может иметь тип void, т. е. указывать
на "ничто", но указатель этого типа нельзя путать с
нулевым.
Объявление:
void *ptr;

14. Указатели

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

15. Указатели

• Например, для выделения памяти под объект
типа char, то надо объявить:
• char object[];
• char *p=(char *)malloc(sizeof(object));

16. Типы указателей

Существует указатели трех типов:
регулируемые указатели;
нерегулируемые указатели;
нерегулируемые указатели функций.

17. Типы указателей

18. Регулируемый указатель

• Регулируемый указатель - это тип указателя,
который ссылается на объекты (адреса
памяти, по которым можно обращаться к
объектам),
расположенные
в
общей
регулируемой куче памяти, предоставленной
приложению в момент его исполнения.
• Для таких указателей принято специальное
обозначение: вместо символа * применяется
символ ^.

19. Регулируемый указатель

#include "stdafx.h"
using namespace System;
ref struct Message
{ System::String ^sender, ^receiver, ^data; };

20. Регулируемый указатель

int main()
{
Message^ M = gcnew Message;
M->sender="Сообщение для всех";
M->data="20.01.2019";
Console::WriteLine(M->sender);
Console::WriteLine(M->data);
Console::WriteLine(L"Здравствуй, мир!");
Console::ReadLine(); //для задержки экрана
return 0;
}

21. Регулируемый указатель

22. Нерегулируемые указатели

Пусть имеем массив:
int А[10];
и указатель, указывающий на какой-то
объект типа int:
int pa;

23. Нерегулируемые указатели

Адрес первого элемента массива занесем в указатель:
pа=&А[0];
Тогда pa+i будет указывать на i-й элемент массива,
т. е. можно достать такой элемент из массива путем
выполнения оператора:
int a=*(pa+i);

24. Нерегулируемые указатели

Но по определению массива можно записать:
int a=A[i];
Массив элементов строится так,
что его имя - это адрес первого элемента массива,
в нашем случае А=&А[0] и pа=&А[0].
Следовательно:
pа = А
pa + i = A + i
*(pa + i) = *(A + i) = A[i]

25. Операции над указателями

• Над указателями, содержащими адрес одного
и того же объекта, можно
определенные операции:
выполнять
• операции отношения (>, < и т. д.).
• операции равенства и неравенства (==, ! =);
• указатель можно сравнивать с NULL.

26. Операции над указателями

• Объявим указатель char *p, чтобы записать
символы, начиная с адреса, указанного в р,
указатель должен быть предварительно
инициализирован, т. е. ему должен быть
присвоен некий адрес, указывающий на
участок, где будут располагаться объекты
типа char.

27. Операции над указателями

Этот участок должен быть получен с помощью
функции new(), которая возвратит указатель на
выделенный участок, после чего значение этого
указателя надо будет присвоить указателю р.
char *p;
p = new char [i]; //выделение памяти в куче
delete [] p; //возврат памяти в кучу

28. Порядок работы с динамическими структурами данных следующий:

• создать (отвести место в динамической
памяти);
• работать при помощи указателя;
• удалить (освободить занятое структурой
место).

29. Классификация динамических структур данных

однонаправленные (односвязные) списки;
двунаправленные (двусвязные) списки;
циклические списки;
стек;
дек;
очередь;
бинарные деревья.

30. Объявление динамических структур данных

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

31. Объявление динамических структур данных

• Поле данных может быть переменной, массивом или
структурой.
Для
наилучшего
представления
изобразим отдельную компоненту в виде:
где поле Р – указатель; поле D – данные.

32. Объявление динамических структур данных

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

33. Объявление динамических структур данных

• Объявление
структуры
образом:
элемента
динамической
данных выглядит следующим
• struct имя_типа {
информационное поле;
адресное поле;
};

34. Связь указателя с адресуемым объектом

35. Списки

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

36. Списки

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

37. Списки

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

38. Списки

• Список,
отражающий отношения соседства
между элементами, называется линейным.
• Линейные
связные
списки
являются
простейшими
динамическими
структурами
данных. Можно выделить следующие виды
списков:
• однонаправленные (односвязные) списки;
• двунаправленные (двусвязные) списки;
• циклические (кольцевые) списки.

39. Списки

• Каждый элемент списка представим структурой
языка C++ с двумя полями:
• информационное поле, которое в общем случае
может содержать произвольное количество полей
разных типов;
• ссылка на следующий элемент списка.

40. Списки

Можно описать звено списка так:
struct node
{
int elem; //Информационный элемент звена списка
node *sled; // Указатель на следующее звено списка
};

41. Списки

Чтобы иметь возможность оперировать со списком
как с единым объектом, введем в употребление
статическую ссылочную переменную phead,
которая указывает на первое звено списка и
описывается следующим образом:
struct node *phead;

42. Построение списка без заглавного звена. 

Построение списка без
заглавного звена.
1. Отвести место для указателей в статической
памяти:

43. Построение списка без заглавного звена. 

Построение списка без
заглавного звена.
• 2.
В
куче
зарезервировать
динамического объекта:
место
для

44. Построение списка без заглавного звена. 

Построение списка без
заглавного звена.
• 3.
Присвоить значение переменной t, и
поместить в информационное поле значение
элемента:

45. Построение списка без заглавного звена. 

Построение списка без
заглавного звена.
• 4. Поместить в поле звена адрес нового
динамического объекта, зарезервированного в
куче:

46. Построение списка без заглавного звена. 

Построение списка без
заглавного звена.
• 5. Переменная t должна содержать адрес
последнего добавленного элемента:

47. Построение списка без заглавного звена. 

Построение списка без
заглавного звена.
• 6. Если требуется завершить построение списка,
то в поле указателя последнего элемента нужно
поместить NULL:

48. Построение списка без заглавного звена. 

Построение списка без
заглавного звена.
• В результате построен линейный
однонаправленный список без заглавного звена,
содержащий два узла:

49. Однонаправленные (односвязные) списки

50. Построение списка с заглавным звеном

Построение
списка
заглавным звеном
void POSTROENIE (node **phead)
// Построение списка с заглавным звеном.
// *phead - указатель на заглавное звено.
{
node *t;
int el;
с

51. Построение списка с заглавным звеном

Построение
списка
заглавным звеном
// Вначале создадим заглавное звено
*phead = new (node);
t = *phead;
(*t).sled = NULL;
с

52. Построение списка с заглавным звеном

Построение
списка
заглавным звеном
с
cout<<"Вводите элементы звеньев списка: ";
cin>>el;
while (el!=0)
{ (*t).sled = new (node); //Резервируем место для
нового объекта.
t = (*t).sled; //Указатель t содержит адрес
//расположения созданного объекта.

53. Построение списка с заглавным звеном

Построение
списка
заглавным звеном
(*t).elem = el; //Заполняем поля объекта.
(*t).sled = NULL;
cin>>el;
}
}
с

54. Вывод содержимого однонаправленного линейного списка

• void Spisok::VYVOD ()
• {
• node *t;
• t = (*phead).sled;
• cout<<"Список: ";
• while (t!=NULL)
• { cout<<(*t).elem<<" "; t = (*t).sled; }
cout<<endl; }

55. Удаление списка из памяти

• Алгоритм удаления можно сформулировать
следующим образом:
• заводим два указателя q и q1, один из которых
будет
"опережать"
(пусть q1 опережает q);
• начальное
другой
значение q - это адрес
расположения в памяти заглавного звена,
а q1 - адрес расположения первого элемента
списка;

56. Удаление списка из памяти

• организуем цикл, пока q1!=NULL, то есть
пока q1 "не доберется"
последнего элемента списка;
до
указателя
• в теле цикла переместим указатели на
следующую пару элементов списка (то есть
для первого случая q будет содержать адрес
первого звена списка, а q1 - второго), и
удалим
элемент,
который
адресуется
значением q;

57. Удаление списка из памяти

• после выполнения цикла у нас останется
только
заглавное
звено,
адресуемое
указателем phead. Его также нужно удалить.

58. Удаление списка из памяти

59. Поиск звена

60. Включение звена

• В куче резервируется место для
динамического объекта:
• q = new (node);

61. Включение звена

• В информационное поле этого объекта
помещается значение
необходимо вставить:
• (*q).elem = el;
элемента,
который

62. Включение звена

• В поле указателя помещается адрес элемента,
следующего
за
указывает Res:
• (*q).sled = (*Res).sled;
звеном,
на
которое

63. Включение звена

• после выполнения оператора
• (*Res).sled = q;

64. Включение звена

65. Алгоритм включения в список перед звеном

66. Алгоритм включения в список перед звеном

67. Алгоритм включения в список перед звеном

68. Алгоритм включения в список перед звеном

69. Алгоритм включения в список перед звеном

70. Удаление звена, расположенного после звена

q = (*Res).sled;

71. Удаление звена, расположенного после звена

• Проверяем, не является ли звено, после
которого нужно удалять, последним. В этом
случае удалять нечего.

72. Удаление звена, расположенного после звена

73. Удаление звена, расположенного после звена

74. Алгоритм удаления звена, на которое указывает ссылка Res.

Алгоритм удаления звена, на
которое указывает
ссылка Res.

75. Алгоритм удаления звена, на которое указывает ссылка Res.

Алгоритм удаления звена, на
которое указывает
ссылка Res.
• Определяем, не является ли удаляемое звено
последним. В зависимости от этого
реализация алгоритма будет различной.

76. Алгоритм удаления звена, на которое указывает ссылка Res.

Алгоритм удаления звена, на
которое указывает
ссылка Res.
• Последняя тонкость: присоединение
"кусочка" heap-области к списку свободной
памяти:

77. Алгоритм удаления звена, на которое указывает ссылка Res.

Алгоритм удаления звена, на
которое указывает
ссылка Res.
• Теперь рассмотрим ситуацию, когда
удаляемое звено является последним
звеном списка:

78. Алгоритм удаления звена, на которое указывает ссылка Res.

Алгоритм удаления звена, на
которое указывает
ссылка Res.
• Найдем указатель на предпоследнее звено
линейного списка с помощью двух
вспомогательных указателей q1 и q2,
перемещающихся по списку "параллельно друг
другу", причем указатель q2 "опережает"
указатель q1 на один шаг.

79. Алгоритм удаления звена, на которое указывает ссылка Res.

Алгоритм удаления звена, на
которое указывает
ссылка Res.
• После выполнения цикла while, мы получим
следующую ситуацию:

80. Алгоритм удаления звена, на которое указывает ссылка Res.

Алгоритм удаления звена, на
которое указывает
ссылка Res.

81. Алгоритм удаления звена, на которое указывает ссылка Res.

Алгоритм удаления звена, на
которое указывает
ссылка Res.