Помощничек
Главная | Обратная связь


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

Добавление элементов очереди



1. Исходное состояние:

 

2. Выделение памяти под новый элемент и занесение в него информации:

New(p);

P^.Inf:=5;

P^.Link:=nil;

 

3. Установка связи между элементом очереди и новым, а также перемещение указателя конца очереди EndQ на новый элемент:

EndQ^.Link:=P;

EndQ:=P;

Удаление элемента очереди

1. Исходное состояние:

2. Извлечение информации из удаляемого элемента в переменную Val и установка на него вспомогательного указателя P:

Val:=BegQ^.Inf;

P:=BegQ;

 

3. Перестановка указателя начала очереди BegQ на следующий элемент, используя значение поля Link, которое хранится в первом элементе. После этого освобождается память начального элемента очереди, используя дополнительный указатель P:

BegQ:=P^.Link;

Dispose(P);

В качестве примера рассмотрим два задания на темы: сортировка элементов списка и операции работы с очередью.

Пример 1. Надо упорядочить элементы списка по убыванию, используя сортировку посредством выбора максимального элемента. Используйте список без заглавного элемента.

Решение:

procedure List_Sort( L: TList );

{ обмен информационных частей двух звеньев списка }

{ L.R - указатели на звенья }

procedure SwapInfo(L, R: TList );

begin

with L^ do Info :=R^.Info-Info;

with R^ do Info :=Info-L^.Info;

with L^ do Info := R^.Info+Info;

end;

var { указатель, используемый при поиске максимума }

R: TList;

Max: TList; { указатель на максимальный элемент }

begin

if L<>nil then { если список не пуст }

begin

while L^.Next <> nil do

{сортируем подсписок, если в нем более одного элемента}

begin

{ сначала считаем, что первый элемент }

{ подсписка является максимальным }

Мах := L;

R := L^.Next;

{ ищем максимальный элемент }

while R <> nil do

begin

if R^.Info > Max^.Info

{запоминаем указатель на максимальный}

then Max := R:

{переходим к следующему элементу подсписка}

R := R^.Next

end;

if Max <> L

{ обмениваем информационные части }

then Swaplnfo( L, Max );

{ переходим к следующему элементу списка}

L := L^.Next

end

end

end; { List_Sort }

 

Задание 2

Реализуйте операции работы с очередью, построенной на основе:

а) массива;

б) динамических структур.

Решение

а).

const

{ Максимальное число элементов очереди + 1 }

MaxN=100;

type

ТЕlem = integer: { Тип элементов очереди }

TElements = array [1..MaxN] of TElem;

TQueue = record { Представление очереди }

{Массив для хранения элементов очереди}

Elements: TElements;

Head: integer; { "Голова" очереди }

Tail : integer { "Хвост" очереди }

end;

{ Инициализация очереди Q }

procedure Queue_Init( var Q : TQueue);

begin

{ Изначально очередь не содержит элементов }

Q.Head := 1;

Q.Tail := 1

end;{ Queue_Init }

{ Проверка очереди Q на пустоту }

{ Результат функции: }

{ true - очередь пуста; false - очередь не пуста }

function Queue_IsEmpty( Q: Tqueue ): boolean;

begin

QueueJsEmpty := ( Q.Head = Q.Tail )

end;{ Queue_IsEmpty }

{ Поместить элемент E в очередь Q }

procedure Queue_Push( var Q: TQueue; E : TElem);

const

ErrorCode = 255;

begin

with Q do

begin

{ заносим новый элемент в очередь }

Elements[Tail] := Е;

{вычисляем значение индекса для следующего элемента очереди}

Tail := (Tail mod MaxN) + 1;

if Tail = Head then

begin

writelnt ('Переполнение очереди !!!' );

{ Аварийное завершение программы }

Halt( ErrorCode )

end

end

end;{ Queue_Push }

 

{возможна другая реализация операции помещения значения в очередь}

{ Поместить элемент Е в очередь Q }

{Результат функции:}

{ true - операция выполнена успешно; false - переполнение очереди }

function Queue_Push_Func( var Q: TQueue; E: TElem): boolean;

var

newTail: integer; { индекс для следующего элемента очереди } begin

newTail := (Q.Tail mod MaxN) + 1;

with Q do

if newTail <> Head then

begin

Tail := newTail;

Elements[Tail] :- E;

Queue_Push_Func := true

end

else { Переполнение очереди }

Queue_Push_Func := false

end: { Queue_Push_Func }

{ Извлечь элемент из "головы" очереди Q }

{ Результат функции: извлеченный из очереди элемент }

function Queue_Pop( van Q : TQueue): Telem;

const

ErrorCode = 255;

begin

if Queue_IsEmpty( Q )

then

begin

writeln('Извлечение элемента из пустой очереди !!!');

{ Аварийное завершение программы }

Halt( ErrorCode )

end

else

with Q do

begin

Queue_Pop := Elements[Head];

Head := (Head mod MaxN) + 1;

End

end;{ Queue_Pop }

 

{возможна другая реализация операции извлечения значения из очереди}

{ Извлечь элемент из "головы" очереди Q }

procedure Queue_Pop_Proc( var Q: Tqueue; var E: Telem );

const

ErrorCode = 255;

begin

if Queue_IsEmpty( Q )

then

begin

writeln( 'Извлечение элемента из пустой очереди !!!')

{ Аварийное завершение программы }

Наlt( ErrorCode )

end

else

with Q do

begin

E := Elements[Head];

Head :- (Head mod MaxN) + 1;

end

end; { Queue_Pop_Proc }

 

б).

type

TElem = integer: { Тип элементов очереди }

TList = ^TElement; { Список, предназначенный для хранения элементов очереди }

Telement = record { Элемент списка }

Info: TElem; { Информационная часть }

Next: Tlist { Указатель на следующий элемент списка }

end;

TQueue = record { Представление очереди }

Head: TList; { "Голова" очереди }

Tail: TList { "Хвост" очереди }

end;

{ Инициализация очереди Q }

procedure Queue_Init ( var Q: TQueue );

begin

{ Изначально список, хранящий элементы очереди, пуст }

Q.Head := nil

end; { Queue_Init }

{ Проверка: пуста ли очередь Q ?

Результат функции: true – очередь пуста; false – очередь не пуста }

function Queue_IsEmpty ( Q: TQueue ): boolean;

begin

{ Очередь пуста, если пуст соответствующий список }

Queue_IsEmpty := ( Q.Head = nil )

end; { Queue_IsEmpty }

{ Поместить элемент Е в "хвост" очереди Q }

procedure Queue_Push ( var Q: TQueue; E: TElem );

var Z: TList;

begin

new(Z); { Создаем новое звено списка }

Z^.Info := E;

Z^.Next := nil;

If Queue_IsEmpty(Q)

then Q.Head := Z

else Q.Tail^.Next := Z;

Q.Tail := Z

end; { Queue_Push }

{ Извлечь элемент из очереди Q }

{ Результат функции: извлеченный из "головы" очереди элемент}

function Queue_Pop ( var Q: TQueue ): TElem;

const ErrorCode = 255;

var Z: TList;

begin

If Queue_IsEmpty(Q) then

begin

writeln( ‘Извлечение элемента из пустой очереди !!!’ );

{ Аварийное завершение программы }

Halt(ErrorCode )

end

else

begin

{ Сохраняем указатель на звено списка }

Z := Q.Head;

{ Перемещаемся к следующему звену }

Q.Head := Z^.Next;

Queue_Pop := Z^.Info;

dispose( Z ) { Удаляем звено списка }

end

end; { Queue_Pop }

КОНТРОЛЬНЫЕ ВОПРОСЫ

1. В чем особенность объявления данных динамической структуры?

2. Что выполняет операция разыменования?

3. С помощью каких процедур происходит распределение памяти под динамические переменные?

4. Какие состояния может принимать указательная переменная?

5. В каких случаях указатель может находиться в неопределенном состоянии?

6. В чем различие между состоянием nil и неопределенным состоянием?

7. Какие действия выполняют процедуры New и Dispose?

8. В чем выражаются динамические свойства несвязанных динамических данных?

9. Что такое стек?

10. Какие процедуры нужно создать для обслуживания динамического стека?

11. Что представляет собой очередь как структура данных?

12. Что требуется для создания связанных динамических структур данных?

13. В чем особенность описания типов для создания динамических структур данных?

14. Сколько указателей требуется для работы с очередью?

15. Какие действия необходимо выполнить для создания очереди?

16. Как добавить или удалить элемент очереди?

17. Есть ли разница между добавлением 1-го и очередного элемента очереди?

КОНТРОЛЬНЫЕ ЗАДАНИЯ

Задание 1.

program zadanie1;

var X: ^boolean;

Y: boolean;

begin

{a} New(X);

{b} X^:=True; Y:=not X^;

{c} Dispose (X);

{d} Writeln(Y);\

end.

Ответьте на следующие вопросы:

а). Какие переменные существуют в каждой из точек a, b, c, d, каковы их значения в эти моменты?

б). Можно ли переменной X присвоить ссылку на переменную Y? Можно ли с помощью процедуры Dispose уничтожить переменные X и Y?

 

Задание 2.

Найдите ошибки в следующей программе:

program Errors;

var A, B: ^integer;

begin

if A=Nil then Read(A);

A^:=5;

B:=Nil;

B^:=2;

New(B);

Read(B^);

Writeln(B,B^);

New(A);

B:=A;

Dispose(A);

B^:=4;

end.

Задание 3.

Дан список случайных чисел. Переверните список, т.е. расставьте все числа в обратном порядке. Подсчитайте среднее арифметическое его элементов. Создайте два новых списка, в один из которых запишите все элементы больше 5, а в другой – основные элементы исходного списка.

 

Задание 4.

Дан текстовый файл. Распечатайте текст в обратном порядке слов.

Задание 5.

Дан файл картотеки сведений об автомобилях (марка, номер и фамилия владельца). Найдите:

а). Фамилию владельцев, номера автомобилей указанной марки и их количество;

б). Фамилию владельца по указанному номеру автомобиля;

в). Исключите из картотеки сведения об автомобиле заданного владельца.

Задание 6.

Многочлен

P(x) = an x n + an-1 x n-1 +...+ a1 x + a0

с целыми коэффициентами можно представить в виде списка (рис. 1 а):

Рис 1а Представление многочлена P(x) = anx n + an-1x n-1 +...+ a1 x+ a0  

Причем если аi=0, то соответствующее звено не включается в список. На рис. 14,6 показано представ­ление многочлена S(х)=52х40—Зх8+х..

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

Задание 7.

Если представление многочлена такого, как показано на рис. 1а и 1б, то написать процедуру, которая считывает данные из текстового файла и заносит их в структуру, как показано на рис. 1а.

Задание 8.

Если представление многочлена такого, как показано на рис. 1а и 1б, то написать процедуру, которая считает значение многочлена, при том значении х, вводимое с терминала.

Задание 9.

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

Задание 10.

Даны 2 списка: L1 и L2

Type slowo=array [1..10] of char;

P=^spis;

Spis=record

Sl: slowo;

Yk: P

End;

Var L1, L2 : P;

Создать процедуру, которая печатает и удаляет из списка L1 все слова, которые отсутствуют в списке L2.

Задание 11.

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

Задание 12.

Создайте 2 динамических массива целых чисел. Один заполните случайными числами, а во второй перенесите чётные числа из первого.

Задание 13.

Создайте динамический массив и заполните его таким образом, чтобы каждый элемент равнялся квадрату своего индекса. Например 1-й элемент должен быть равен 1, второй – 22 =4 и т.д.

Задание 14.

Создайте динамический список и заполните его таким образом, чтобы каждый элемент равнялся квадрату своего порядкового номера в списке. Например, 1-й элемент должен быть равен 1, второй – 22 =4 и т.д.

 

 




Поиск по сайту:

©2015-2020 studopedya.ru Все права принадлежат авторам размещенных материалов.