Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь FAQ Написать работу КАТЕГОРИИ: АрхеологияБиология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия Экология ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Однонаправленные (линейные) списки. Описание, создание, просмотр списка, добавление и удаление элементовСодержание книги
Похожие статьи вашей тематики
Поиск на нашем сайте
Список - это конечное множество динамических элементов, размещающихся в разных областях памяти и объединенных в логически упорядоченную последовательность с помощью специальных указателей (адресов связи). Список - структура данных, в которой каждый элемент имеет информационное поле (поля) и ссылку (ссылки), то есть адрес (адреса), на другой элемент (элементы) списка. Список - это так называемая линейная структура данных, с помощью которой задаются одномерные отношения. Каждый элемент списка содержит информационную и ссылочную части. Порядок расположения информационных и ссылочных полей в элементе при его описании - по выбору программиста, то есть фактически произволен. Информационная часть в общем случае может быть неоднородной, то есть содержать поля с информацией различных типов. Ссылки однотипны, но число их может быть различным в зависимости от типа списка. В связи с этим для описания элемента списка подходит только тип «запись», так как только этот тип данных может иметь разнотипные поля. В зависимости от числа ссылок список называется одно-, двунаправленным… В однонаправленном списке каждый элемент содержит ссылку на последующий элемент. Если последний элемент списка содержит «нулевую» ссылку, то есть содержит значение предопределенной константы NIL и, следовательно, не ссылается ни на какой другой элемент, такой список называется линейным. Для доступа к первому элементу списка, а за ним - и к последующим элементам необходимо иметь адрес первого элемента списка. Этот адрес обычно записывается в специальное поле - указатель на первый элемент, дадим ему специальное, «говорящее» имя - FIRST. Если значение FIRST равно NIL, это значит, что список пуст, он не содержит ни одного элемента. Оператор FIRST:= NIL; должен быть первым оператором в программе работы со списками. Он выполняет инициализацию указателя первого элемента списка, иначе говоря, показывает, что список пуст. Всякое другое значение будет означать адрес первого элемента списка. Формирование пустого списка. PROCEDURE CREATE_EMPTY_LIST (VAR FIRST: EL); BEGIN FIRST = NIL; END; Формирование очередного элемента списка. PROCEDURE CREATE_NEW_ELEM(VAR P: EL); BEGIN NEW (P); WRITELN ('введите значение первого информационного поля: '); READLN (P^.INF1); WRITELN ('введите значение второго информационного поля: '); READLN (P^.INF2); P^.NEXT:= NIL; { все поля элемента должны быть инициализированы } END; Вставка элемента в начало списка. PROCEDURE INS_BEG_LIST(P: EL; {адрес включаемого элемента} VAR FIRST: EL); BEGIN IF FIRST = NIL THEN BEGIN FIRST:= P; P^.NEXT:= NIL END ELSE BEGIN FIRST:=P;{ включаемый элемент становится первым } P^.NEXT:=FIRST;{ссылка на бывший первым элемент} END; END; Включение элемента в конец списка. PROCEDURE INS_END_LIST(P: EL; VAR FIRST: EL); BEGIN IF FIRST = NIL THEN FIRST:=P ELSE BEGIN Q:=FIRST; {цикл поиска адреса последнего элемента} WHILE Q^.NEXT <> NIL DO Q:=Q^.NEXT; Q^.NEXT:=P;{ссылка с бывшего последнего на включаемый элемент} P^.NEXT:=NIL; {не обязательно} END; END; Включение в середину (после i-ого элемента). PROCEDURE INS_AFTER_I (FIRST: EL; P: EL; I: INTEGER); VAR T, Q: EL; K,N: INTEGER; BEGIN N:= COUNT_EL(FIRST); {определение числа элементов списка} IF (I < 1) OR (I > N)THEN BEGIN WRITELN ('i задано некорректно'); EXIT; END ELSE BEGIN IF I = 1 THEN BEGIN T:= FIRST;{адрес 1 элемента} Q:= T^.NEXT; {адрес 2 элемента} T^.NEXT:= P; P^.NEXT:= Q; END ELSE IF I = N THEN BEGIN { см. случай вставки после последнего элемента} ... END ELSE {вставка в «середину» списка} BEGIN T:= FIRST; K:= 1; WHILE (K < I) DO BEGIN {поиск адреса i-го элемента} K:= K + 1; T:= T^.NEXT; END; Q:= T^.NEXT; {найдены адреса i-го (t) и i+1 -го (q) элементов } T^.NEXT:= P; P^.NEXT:= Q; {элемент с адресом р вставлен} END; END; END; Удаление элемента из начала списка. PROCEDURE DEL_BEG_LIST (VAR FIRST: EL); VAR P: EL; ANSWER: STRING; BEGIN IF FIRST <> NIL THEN BEGIN { список не пуст } WRITELN ('Вы хотите удалить первый элемент?(да/нет) '); READLN (ANSWER); IF ANSWER = 'ДА' THEN BEGIN P:=FIRST; IF P^.NEXT = NIL THEN {в списке один элемент } BEGIN DISPOSE (P); {уничтожение элемента} FIRST:=NIL; {список стал пустым } END ELSE BEGIN P:= FIRST;{адрес удаляемого элемента } FIRST:=FIRST^.NEXT; {адрес нового первого элемента} DISPOSE(P); {удаление бывшего первого элемента } END; END END ELSE WRITELN (' список пуст, удаление первого элемента невозможно'); END; Подсчет числа элементов списка FUNCTION COUNT_EL(FIRST:EL):INTEGER; VAR K: INTEGER; Q: EL; BEGIN IF FIRST = NIL THEN K:=0 { СПИСОК ПУСТ } ELSE BEGIN {СПИСОК СУЩЕСТВУЕТ} K:=1; {В СПИСКЕ ЕСТЬ ХОТЯ БЫ ОДИН ЭЛЕМЕНТ} Q:=FIRST; {ПЕРЕБОР ЭЛЕМЕНТОВ СПИСКА НАЧИНАЕТСЯ С ПЕРВОГО} WHILE Q^.NEXT <> NIL DO BEGIN K:=K+1; Q:=Q^.NEXT; {ПЕРЕХОД К СЛЕДУЮЩЕМУ ЭЛЕМЕНТУ СПИСКА} END; END; COUNT_EL:=K; END; Двунаправленные, симметричные списки. Описание, создание, просмотр списка, добавление и удаление элементов Список - это конечное множество динамических элементов, размещающихся в разных областях памяти и объединенных в логически упорядоченную последовательность с помощью специальных указателей (адресов связи). Список - структура данных, в которой каждый элемент имеет информационное поле (поля) и ссылку (ссылки), то есть адрес (адреса), на другой элемент (элементы) списка. Список - это так называемая линейная структура данных, с помощью которой задаются одномерные отношения. Каждый элемент списка содержит информационную и ссылочную части. Порядок расположения информационных и ссылочных полей в элементе при его описании - по выбору программиста, то есть фактически произволен. Информационная часть в общем случае может быть неоднородной, то есть содержать поля с информацией различных типов. Ссылки однотипны, но число их может быть различным в зависимости от типа списка. В связи с этим для описания элемента списка подходит только тип «запись», так как только этот тип данных может иметь разнотипные поля. При обработке однонаправленного списка могут возникать трудности, связанные с тем, что по списку с такой организацией можно двигаться только в одном направлении, как правило, начиная с первого элемента. Обработка списка в обратном направлении сильно затруднена. Для устранения этого недостатка служит двунаправленный список, каждый элемент которого содержит ссылки на последующий и предыдущий элементы (для линейных списков - кроме первого и последнего элементов). Такая организация списка позволяет от каждого элемента двигаться по списку как в прямом, так и в обратном направлениях. Наиболее удобной при этом является та организация ссылок, при которой движение, перебор элементов в обратном направлении является строго противоположным перебору элементов в прямом направлении. В этом случае список называется симметричным. Например, в прямом направлении элементы линейного списка пронумерованы и выбираются так: 1, 2, 3, 4, 5. Строго говоря, перебирать элементы в обратном направлении можно по-разному, соответствующим способом организуя ссылки, например: 4, 1, 5, 3, 2. Симметричным же будет называться список, реализующий перебор элементов в таком порядке: 5, 4, 3, 2, 1. циклический, кольцевой список организован таким образом, что в адресную часть конечного элемента вместо константы NIL помещается адрес начального элемента (список замыкается на себя). В симметричном кольцевом списке такое положение характерно для обоих - прямого и обратного - списков, следовательно, можно построить циклический двунаправленный список. Действия со списками: Описание элемента двунаправленного списка TYPE POINT=^ZAP; ZAP=RECORD INF1: INTEGER; { первое информационное поле } INF2: STRING; { второе информационное поле } NEXT:POINT; {ссылочное поле на следующий элемент} PREV:POINT; {ссылочное поле на предыдущий элемент} END; Все действия над элементами списка, приводящие к изменению порядка обработки элементов списка - вставка, удаление, перестановка - сводятся к действиям со ссылками. Сами же элементы не меняют своего физического положения в памяти. Формирование пустого списка. PROCEDURE CREATE_EMPTY_LIST (VAR FIRST: EL); BEGIN FIRST = NIL; END;
|
||||
Последнее изменение этой страницы: 2016-08-15; просмотров: 1040; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 3.138.134.247 (0.011 с.) |