 |
АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция
Мультисписки
|
Читайте также: |
Иногда возникают ситуации, когда имеется несколько разных списков, которые включают в свой состав одинаковые элементы. В таком случае при использовании традиционных списков происходит многократное дублирование динамических переменных и нерациональное использование памяти. Списки фактически используются не для хранения элементов данных, а для организации их в различные структуры. Использование мультисписков позволяет упростить эту задачу.
Мультисписок состоит из элементов, содержащих такое число указателей, которое позволяет организовать их одновременно в виде нескольких различных списков. За счет отсутствия дублирования данных память используется более рационально.
| |||||||||||||||||||||
| Рис.1.5. Объединение двух линейных списков в один мультисписок. A – множество элементов списка 1 B – множество элементов списка 2 C – множество элементов мультисписка (С = A È B |
Экономия памяти – далеко не единственная причина, по которой применяют мультисписки. Многие реальные структуры данных не сводятся к типовым структурам, а представляют собой некоторую комбинацию из них. Причем комбинируются в мультисписках самые различные списки – линейные и циклические, односвязанные и двунаправленные.
Представление стека и очередей в виде списков
Стек
Стек представляет собой структуру данных, из которой первым извлекается тот элемент, который был добавлен в нее последним. Стек как динамическую структуру данных легко организовать на основе линейного списка. Для такого списка достаточно хранить указатель вершины стека, который указывает на первый элемент списка. Если стек пуст, то списка не существует и указатель принимает значение nil.
Рис.1.6. Организация стека на основе линейного списка.
Приведем пример программы, реализующей стек как динамическую структуру.
Program stack;
type
element=record
data:string;
next:pointer;
end;
var
n: integer;
current:^element;
pnt:^element;
procedure put_element(s:string); {занесение элемента в стек}
begin
new(pnt);
x^.data:=s;
x^.next:=current;
current:=pnt;
end;
procedure get_element(var s:string); {получение элемента из стека}
begin
if current=nil then s:=’пусто’ else
begin
pnt:=current;
s:=pnt^.data;
current:=pnt^.next;
dispose(pnt);
end;
end;
{------------program--------------}
begin
current:=nil;
repeat
writeln(‘1 - добавить в стек’);
writeln(‘2 - удалить из стека’);
writeln(‘0 - выход’);
readln(n);
if n=1 then
begin
write(‘элемент? ‘);
readln(s);
put_element(s);
end;
if n=2 then
begin
get_element(s);
writeln(s);
end;
until n=0;
end.
В программе добавление нового элемента в стек оформлено в виде процедуры put_element, а получение элемента из стека – как процедура get_element.
Поиск по сайту: