Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Программирование
26.03.2013
Динамические структуры данных
Существуют 2 способа хранения данных:
1)Последовательное распределение (массив)
|
**** |
|
**** |
|
… |
|
… |
2)Связное распределение (динамические структуры данных) – в общем виде список.
|
* |
|
* |
|
* |
|
Признак сравнения |
Массив |
Список |
|
Добавление элемента в конец |
Пополняется легко |
Пополняется легко |
|
Добавление элементов в середину |
Связан со сдвигом большого количества элементов |
Легко |
|
Добавление элементов в начало |
Сдвиг всего массива |
Легко |
|
Удаление элемента из конца |
Легко |
Легко |
|
Удаление элемента из середины |
Связан со сдвигом большого количества элементов |
Легко |
|
Удаление элемента из начала |
Легко |
Легко |
|
Размер одного элемента |
Соответствует хранимым данным |
Хранимые данные + размер указателя |
|
Максимальный размер |
Ограничен способом его объявления |
Объёмом свободной памяти |
|
Обращение к элементу по его номеру |
Происходит естественным образом |
Только с помощью цикла, который позволяет переходить от одного элемента к другому, отсчитывая заданное количество |
|
Сортировка элементов |
Классические алгоритмы |
Требует дополнительной обработки |
Указатели и основные действия с ними
Указатель – это переменная специального типа, которая может в себе содержать адрес некоторой ячейки памяти.
Указатели бывают 2-х видов:
1) Типизированные
2) Нетипизированные
Каждый указатель может находить в одном из трёх состояний:
1-ое состояние – неопределённое. Указатель находится в неопределённом состоянии до первого присвоения ему какого-либо значения.
2-ое состояние – неопределённое. Указатель содержит адрес конкретной ячейки памяти
3-е состояние – указатель пустой. Происходит тогда, когда под указатель не выделена память (nil).
Основные операции, выполняемые с указателями:
Var p1:^Integer; (^-показать, что это указатель)
P1
P2:Pointer; (нетипизированный указатель)
|
|
P2
New (p1);
Dispose(p1);
p1^:=4;
-разыменование
5) Копирование адреса
P2:=p1
p1^:=p2^
p1
p2
Основные динамические структуры данных
Это структура данных, которая работает по принципу «последним защёл, первым вышел».
Type
pEl:^ tEl;
tEl=Record
data: Integer;
next: pEl;
end;
var pTop, pHelp: pEl; pTop
{создаём стек} pHelp
Procedure StackCreate;
Begin pTop
New(pTop);
pTop.next:=nil;
{мы подразумеваем pTop^.next)
pTop.data:=-1;
end;
{Добавляем один элемент}
Procedure StackAdd(x:Integer);
Begin
…..ДОПЕЧАТАТЬ
02.04.2013
Продолжение
Удаление элемента
pTop
Это структура данных, которая работает по принципу «первым защёл, первым вышел».
Структура данных для очереди, такая же как и для стека.
Type
pEl:^ tEl;
tEl=Record
data: Integer;
next: pEl;
end;
{для работы с очередью нам необходимо три указателя.}
Var pBeg, pEnd, pHelp: pE1
{пустая очередь выглядит следующим образом}
Рис1
{добавление в очередь}
….
Структуры данных, для однонаправленного списка аналогичны структурам данным для очереди.
Пустой список выглядит также как пустая процедура очереди.
Процедура вывода списка аналогична процедуре вывода очереди.
Процедура добавление элемента в конец списка, аналогична процедуре добавления элемента в очередь.
Процедура удаление элемента из начала списка аналогична процедуре удаления элемента в очереди.
Необходимо:
1.создание.
2.добавление элемента в начало списка
3. добавление элемента в конец списка
4. добавление элемента после элемента с номером k.
5.удаление элемента из начала списка
6.удаление элемента из конца списка
7.удаление элемента с номером k.
8.вывод списка на экран.
Д.З. картинки+процедуры
…..ДОПЕЧАТАТЬ