Студопедия  
Главная страница | Контакты | Случайная страница

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

Структура данных список. Базовые операции над списком

Читайте также:
  1. A) структура рабочего стола
  2. Cохранение данных в двоичных файлах.
  3. CТРУКТУРЫ ДАННЫХ И АЛГОРИТМЫ
  4. I - операции с подакцизными товарами, совершаемые производителями этих товаров;
  5. I)Однофакторный дисперсионный анализ (выполняется с применением программы «Однофакторный дисперсионный анализ» надстройки «Анализ данных» пакета Microsoft Excel).
  6. I. БАЗОВЫЕ КОРМА
  7. I. Правосознание: понятие, структура, функции и виды.
  8. II. Система культуры и её структура.
  9. II. СТРУКТУРА отчетА по Практике по профилю специальности
  10. II. СТРУКТУРА отчетА по УЧЕБНОЙ Практике

Структуры данных очередь и стек являются частными представлениями более сложной структуры данных списка. Списки бывают различных типов. Рассмотрим линейные однонаправленные списки и кольцевые однонаправленные списки.

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

Кольцевой однонаправленный список - это линейный список, который имеет дополнительную связь между последним и первым элементов.

Базовые операции с однонаправленным линейным списком следующие:

¾ построить пустой список;

¾ добавить элемент в список;

¾ отыскать нужный элемент в списке;

¾ удалить элемент из списка;

¾ вставить элемент в список.

Однонаправленный линейный список может быть представлен в виде двумерного массива. При представлении списка с помощью двумерного массива Sps элементы этого массива Sps[1,j] содержат элементы списка, а элементы массива Sps[2,j] являются указателями и определяют индекс (позицию) каждого последующего элемента в списке. Такой список может быть представлен и в виде одномерного массива, элементами которого являются предопределенные записи из двух полей, смысловое назначение которых аналогично двумерному массиву.

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

Задача. Опишите и постройте с помощью двумерного массива Sps линейный однонаправленный список из пяти целых чисел и сделайте этот список пустым. После этого добавьте в список четыре элемента 9,8,7,6, затем найдите указатель на элемент 8 и удалите этот элемент. В конце работы со списком вставьте после элемента со значением 6 элемент со значением 5, предварительно отыскав указатель на элемент со значением 6, а элемент со значением 15 вставьте после элемента со значением 9.

Const maxel=7;

Type Spis=array[1..2,1..maxel] of integer;

Var Assm, Afe: integer; { Assm указывает индекс/адрес первого элемента в списке свободных мест}{ Afe – индекс (адрес) первого элемента в списке. }

El,i,pap,j:integer;

Sps:Spis;

Procedure Nspis(Var Sps:Spis); {процедура оформления пустого списка}

Begin

for i:=1 to maxel-1 do

Sps[2,i]:=i+1;

Sps[2,maxel]:=0;

Assm:=1;

Afe:=0;

End;

Procedure Addsp(Var Sps:Spis); { процедура добавления элемента в список}

Var Asmn:integer;

Begin

Asmn:=Sps[2,Assm];

Sps[1,Assm]:=el;

Sps[2,Assm]:=Afe;

Afe:=Assm;

Assm:=Asmn

End;

Procedure DelSp(Pap,j:integer; Var Sps:Spis); {процедура удаления элемента из списка}

Begin

Sps[2,Pap]:=Sps[2,j];

Sps[2,j]:=Assm;

Assm:=j

End;

Procedure UstSp(j:integer; Var Sps:Spis); {процедура вставки элемента в список}

Var Asmn:integer;

Begin

Asmn:=Sps[2,Assm];

Sps[2,Assm]:=Sps[2,j];

Sps[2,j]:=Assm;

Sps[1,Assm]:=El;

Assm:=Asmn;

End;

Procedure PoshSp(Var Sps:Spis; el:integer; Var Pap,j:integer); {процедура поиска указателя (адреса) на элемент списка}

Begin

j:=Afe;

Pap:=0;

While (Sps[1,j]<>el) and (j<>0) do

Begin

Pap:=j;

j:=Sps[2,j];

End;

if j=0 then Writeln('Элемент не найден')

End;

BEGIN {Основная программа}

Nspis(Sps); {построение пустого списка}

for i:=1 to 4 do

begin

write(‘el[‘,i,’]=’);

readln(el);

Addsp(Sps) {добавление элементов в список по одному}

end;

el:=8; {найденный указатель j, pap – предыдущий указатель}

PoshSp(Sps,el,pap, j ); {поиск указателя на элемент со значением 8}

Delsp(pap,j,sps); {удаление элемента с указателем j}

el:=6;

PoshSp(Sps,el,pap,j); {поиск указателя на элемент со значением 6}

el:=5;

Ustsp(j,Sps); {вставка элемента со значением 5 после элемента со значением 6}

el:=9;

PoshSp(Sps,el,pap,j); {поиск указателя на элемент со значением 9}

el:=15;

Ustsp(j,Sps); {вставка элемента со значением 15 после элемента со значением 9}

END.

Распишем детально порядок выполнения основного алгоритма.

Построение пустого списка процедура Nspis: Assm:=1, Afe:=0, массив Sps:

 

Индекс массива              
элементы списка              
Указатель на элемент списка              

Добавление четырех элементов в список процедура Addsp: Assm:= 5, Afe:= 4, массив S p s:

 

Индекс массива              
элементы списка              
Указатель на элемент списка              

В результате построения списка из 4-х элементов строится цепочка 6→7→8→9.

Поиск указателя на элемент со значением 8 с помощью процедуры PoshSp: j:=2, Pap:=3;

Удаление элемента со значением 8 из списка с помощью процедуры Delsp: Assm:=2, Afe:=4, массив Sps:

 

Индекс массива              
элементы списка              
Указатель на элемент списка              

В результате удаления из списка элемента со значением 8 строится цепочка 6 →7→9.

Поиск указателя на элемент со значением 6 с помощью процедуры PoshSp: j:=4, Pap:=0;

Вставка элемента со значением 5 в список после элемента со значением 6 с помощью процедуры Ustsp: Assm:=5, Afe:=4, массив Sps:

 

Индекс массива              
элементы списка              
Указатель на элемент списка              

В результате вставки в список элемента со значением 5 после элемента со значением 6 получаем цепочку 6 →5→7→9.

Поиск указателя на элемент со значением 9 с помощью процедуры PoshSp: j:=1, Pap:=3;

Вставка элемента со значением 15 в список после элемента со значением 9 с помощью процедуры Ustsp: Assm:=6, Afe:=4, массив Sps:

 

Индекс массива              
элементы списка              
Указатель на элемент списка              

В результате вставки в список элемента со значением 15 после элемента со значением 9 получаем цепочку 6 →5→7→9→15.

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

Контрольные вопросы:

1. Дайте определение статической и динамической памяти. Назовите различие между ними.

2. Дайте определение структуре данных «стек». Опишите принцип работы с данной организацией данных.

3. Дайте определение структуре данных «очередь». Опишите принцип работы с данной организацией данных.

4. Дайте определение структуре данных «список». Опишите принцип работы с данной организацией данных.




Дата добавления: 2014-12-18; просмотров: 29 | Поможем написать вашу работу | Нарушение авторских прав




lektsii.net - Лекции.Нет - 2014-2024 год. (0.011 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав