38021

ПРЕДСТАВЛЕНИЕ И РЕАЛИЗАЦИЯ АТД «СТЕК», «ОЧЕРЕДЬ», «ДВУСВЯЗНЫЙ СПИСОК»

Лабораторная работа

Информатика, кибернетика и программирование

Реализация «стека» посредством указателей. Обычно ячейка стека состоит из двух полей. Первое поле информационное, т.е. хранит сам элемент списка, отсюда название – element, а второе содержит указатель на следующую ячейку, поэтому имеет название next. Для формирования структуры АТД «стек» используется составной тип и описывается в разделе описания типов type.

Русский

2013-09-25

606.5 KB

17 чел.

13

Лабораторная работа № 2

ПРЕДСТАВЛЕНИЕ И РЕАЛИЗАЦИЯ АТД «СТЕК», «ОЧЕРЕДЬ», «ДВУСВЯЗНЫЙ СПИСОК»

Цель работы: исследовать и изучить АТД «стек», «очередь», «двусвязный список».

Задача работы: овладеть навыками написания программ по исследованию АТД «стек», «очередь», «двусвязный список» на любом языке программирования.

Порядок работы :

  1.  изучить описание лабораторной работы;
  2.  по заданию, данному преподавателем, разработать алгоритм программы решения задачи;
  3.  написать программу на языке ПАСКАЛЬ;
  4.  отладить программу;
  5.  решить задачу;
  6.  оформить отчет.

Краткая теория

Реализация «стека» посредством указателей. Обычно ячейка стека состоит из двух полей. Первое поле информационное, т.е. хранит сам элемент списка, отсюда название – element, а второе содержит указатель на следующую ячейку, поэтому имеет название next. Для формирования структуры АТД «стек» используется составной тип и описывается в разделе описания типов type.

Type

Stek=^pStek; {для соответствия типа ячейки и типа хранящегося адреса в поле next}

pStek=record

element: string;

next: Stek;

end;

Теперь в программе все переменные указатели, работающие с данным «стеком», будут иметь один и тот же тип – Stek. Если в программе формируются несколько «стеков», то для всех переменных указателей этих «стеков» тип будет одинаковым – Stek. Такое возможно в том случае, когда форма ячеек у «стеков» совпадает, т.е. количество полей, их название и тип.

Var p10, p20, q1, p1, q2, p2, p, q: Spisok;

Рассмотрим самые необходимые операторы для работы со «стеком». Первый из них – это PUSH, который помещает элемент в стек.

Procedure PUSH;

Begin

q:=p0; {создаётся копия указателя на вершину «стека»}

New(p0); {создание пустой ячейки без имени, но с адресом (рис.2.1), который помещается в ячейку p0 и является указателем на новую вершину «стека»}

Readln(x);

p0^.element:=x;{введённый с клавиатуры, x помещён в поле element ячейки с адресом p0}

p0^.next:=q;{поместили адрес предыдущей вершины в поле next новой вершины с адресом p0 (рис. 1.2)}

End; {Результат данной процедуры – это заполненная и присоединённая сверху ячейка и сохранённый адрес вершины «стека» - p0 (рис. 2.2)}

      

В процессе работы программы элементы будут постепенно добавляться по одному в «стек» по мере необходимости, т.е. заранее не известно число его элементов и конец формирования данной структуры. Для правильного формирования «стека» необходимо перед первым вызовом оператора PUSH присвоить указателю p0 на вершину стека nil. Это действие необходимо для дальнейшей проверки «стека» на пустоту, т.е. если p0=nil, то «стек» пустой.

Другим важным оператором для работы со «стеком» является оператор POP, который возвращает значение вершины «стека», а ниже лежащий элемент становится новой вершиной. Т.е. если «стек» имел вид – это рисунок 2.2, то после вызова оператора POP, стек будет уже другим (рис. 2.3).

function POP: char;

Begin

POP:=p0^.element;

p0:=p0^.next; {переприсвоение адреса указателя на вершину стека после ухода верхнего элемента}

End;

Ещё один необходимый оператор, работающий со «стеком», – это оператор PRINT_STEK, выводящий его на экран.

Procedure PRINT_STEK;

Begin

p:=p0;

Repeat

Write(p^.element, ‘,   ‘);

p:=p^.next;

Until p=nil;

End;

Приведём ниже пример кусочка программы формирующей «стек», выводящей его на экран и вынимающей из «стека» два элемента.

var x1, x2: string;

Begin

p0:=nil;{стек ещё пустой и в ячейке p0 нет адреса на первый элемент}

repeat PUSH; until x=’end’; {«стек» заполняется пока не введут элемент ‘end’}

PRINT_STEK;

x1:=POP; x2:=POP;

End.

Реализация «очереди» посредством указателей. Обычно ячейка «очереди» состоит из двух полей. Первое поле информационное, т.е. хранит сам элемент списка, отсюда название – element, а второе содержит указатель на следующую ячейку, поэтому имеет название next. Для формирования структуры АТД «очередь» используется составной тип и описывается в разделе описания типов type.

Type

Queue=^pQueue; {для соответствия типа ячейки и типа хранящегося адреса в поле next}

pQueue =record

element: string;

next: Queue;

end;

Теперь в программе все переменные указатели, работающие с данной «очередью», будут иметь один и тот же тип – Queue. Если в программе формируются несколько «очередей», то для всех переменных указателей этих «очередей» тип будет одинаковым – Queue. Такое возможно в том случае, когда форма ячеек у «очередей» совпадает, т.е. количество полей, их название и тип.

Var p10, p20, q1, p1, q2, p2, p, q: Queue;

Рассмотрим самые необходимые операторы для работы с «очередью». Первый из них – это HEADER, который создаёт первый элемент «очереди», т.е. заголовок.

Procedure HEADER;

Begin

New(p0); {создание пустой ячейки без имени, но с адресом (рис.2.4), который помещается в ячейку p0}

p0^.element:=’ochered’;{поместили x= ochered в поле element ячейки с адресом p0}

p0^.next:=nil;{поместили знак конца списка nil в поле next ячейки p0}

End; {Результат данной процедуры – это заполненная ячейка и записанный её адрес в ячейку p0 (рис. 2.5)}

      

В процессе работы программы элементы будут постепенно добавляться в «очередь» по мере необходимости, т.е. заранее не известно число её элементов и конец формирования данной структуры. Для этого используется оператор вставки элемента в «очередь» ENQUEUE, который добавляет элементы в конец очереди.

Procedure ENQUEUE;

Begin

New(p^.next); {создаётся новая безымянная ячейка, адрес которой помещается в поле next ячейки с адресом p, т.е. записывается в p^.next (см. рис 2.6)}

Readln(x);

p^.next^.element:=x;{так как адрес новой ячейки хранится в поле next предыдущей ячейки, то обратиться к этому адресу нужно так p^.next, а чтобы поместить x в поле element, нужно пойти по этому адресу и в поле element поместить x }

p:=p^.next;{перевод указателя на текущую ячейку (рис. 2.7)}

p^.next:=nil; {отмечаем, что данный элемент последний}

End; {Результат данной процедуры – это заполненная и присоединённая вконец «очереди» ячейка и сохранённый адрес конца «очереди» - p (рис. 2.8), что позволяет сразу же присоединить новый элемент в конец «очереди при вызове оператора ENQUEUE}

После того, как «очередь» будет сформирована посредством операторов HEADER и ENQUEUE, к её началу можно будет обратиться через указатель p0, а к концу очереди через p.

 

Для правильного формирования «очереди» необходимо перед первым вызовом оператора ENQUEUE присвоить указателю p на первый и пока ещё последний элемент очереди значение p0 (рис. 2.9). Это действие необходимо для дальнейшей проверки «очереди» на пустоту, т.е. если p=p0, то «очередь» пуста.

Другим важным оператором для работы с «очередью» является оператор DEQUEUE, который возвращает значение первого элемента из начала «очереди», а следующий за ним элемент становится новым первым элементом, т.е. началом очереди, идущим сразу же после заголовка. Т.е. если «очередь» имела вид – это рисунок 2.10, то после вызова оператора DEQUEUE, она будет уже другой (рис. 2.11).

function DEQUEUE: char;

begin

{так как адрес первой ячейки хранится в поле next заголовка «очереди», то обратиться к этому адресу нужно так p0^.next, а чтобы записать значение из поля element в DEQUEUE, нужно пойти по этому адресу и произвести соответствующее присвоение}

DEQUEUE:=p0^.next^.element;

{в поле next заголовка «очереди» помещают указатель нового начала очереди рис. 2.11}

p0^.next:=p0^.next^.next;

end;

  

Ещё один необходимый оператор, работающий с «очередью», – это оператор PRINT_QUEUE, выводящий её на экран.

Procedure PRINT_QUEUE;

Begin

q:=p0;

Repeat

Write(q^.element, ‘,   ‘);

q:=q^.next;

Until q=nil;

End;

Приведём ниже пример кусочка программы формирующей «очередь», выводящей её на экран и вынимающей из «очереди» два элемента.

var x1, x2: string;

 Begin

HEADER;

p:=p0;{«очередь» ещё пуста}

repeat ENQUEUE; until x=’end’; {«очередь» заполняется пока не введут ‘end’}

PRINT_QUEUE;

x1:= DEQUEUE; x2:= DEQUEUE;

End.

Реализация «двусвязного списка» посредством указателей. Обычно ячейка «двусвязного списка» состоит из трёх полей. Первое поле информационное, т.е. хранит сам элемент списка, отсюда название – element, а второе и третье поля содержат указатели на следующую и предыдущую ячейки, поэтому имеют названия next и prev. Для формирования структуры АТД «двусвязный список» используется составной тип и описывается в разделе описания типов type.

Type

D_spisok=^pD_spisok; {для соответствия типа ячейки и типа хранящегося адреса в поле next}

pD_spisok =record

element: string;

next: D_spisok;

prev: D_spisok;

end;

Теперь в программе все переменные указатели, работающие с данным «двусвязным списком», будут иметь один и тот же тип – D_spisok. Если в программе формируются несколько «двусвязных списков», то для всех переменных указателей этих списков тип будет одинаковым – D_spisok. Такое возможно в том случае, когда форма ячеек у «двусвязных списков» совпадает, т.е. количество полей, их название и тип.

Var p10, p20, q11, q12, p11, p12, q21, q22, …: D_spisok;

Рассмотрим самые необходимые операторы для работы с «двусвязными списками». Первый из них – это INSERT, который помещает элемент в «двусвязный список».

Procedure INSERT;

Begin

q:=p2;{копирует указатель на предыдущий конец списка}

New(p2);{создаётся пустая безымянная ячейка, адрес которой записывается в p2, который хранит адрес конца «двусвязного списка» (рис. 2.12)}

Readln(x);

p2^.element:=x;

p2^.prev:=q;{вновь созданная ячейка соединяется с предыдущим элементом, который был до этого концом «двусвязного списка» (рис. 2.13)}

q^.next:=p2;{предыдущий элемент соединяется с новым элементом (рис. 2.14)}

p2^.next:=nil;{отмечаем то, что после новой ячейки элементов больше нет}

End; {результатом данного оператора является подсоединённая новая заполненная ячейка (рис. 2.15)}

  

  

Второй из них – это оператор DELETE, который удаляет элемент из «двусвязного списка», если известен адрес удаляемого элемента.

Procedure DELETE;

Begin

p^.prev^.next:=p^.next;

p^.next^.prev:=p^.prev;

End;{Результат данного оператора смотри на рисунке 2.16}

Так же необходим оператор выводящий «двусвязный список» на экран – это PRINT_D_SPISOK. После окончания формирования «двусвязного списка» (циклическое выполнение оператора INSERT) в ячейке p2 сохраняется адрес последней ячейки «двусвязного списка». Чтобы вывести список на экран мы можем начать с конца списка и осуществить вывод «двусвязного списка» . Для этого перед выводом списка необходимо сделать следующее p:=p2. Если перед переходом на предыдущий элемент (p:=p^.prev) осуществить присваивание q:=p, то в переменной q будет сохранён адрес первой ячейки «двусвязного списка». Теперь будет возможен вывод элементов «двусвязного списка» сверху вниз (). Оператора PRINT_D_SPISOK создан таким образом, что повторный его вызов позволяет выводить список сначала , а потом . Если рассмотреть рисунок 2.16, то можно увидеть путь по указателям при выполнении обхода . Это будет такая последовательность: хх:хх4, хх:хх3, хх:хх2, хх:хх1. А для обхода последовательность такая: хх:хх1, хх:хх2, хх:хх3, хх:хх4.

Procedure PRINT_D_SPISOK;

Begin

p:=p2; {начало вывода элементов в направлении }

Repeat

Writeln(p^.element);

q:=p;

p:=p^.prev;

Until p=nil;

p:=q; { начало вывода элементов в направлении }

Repeat

Writeln(p^.element);

q:=p;

p:=p^.next;

Until p=nil;

End;

Ниже приводится пример кусочка программы формирования «двусвязного списка», вывода его на экран и удаления из «двусвязного списка» двух элементов.

Begin

p2:=nil;{делается отметка того, что ещё нет элементов в «двусвязном списке»}

repeat INSERT; until x=’end’;{«двусвязный список» заполняется элементами}

PRINT_D_SPISOK;

p:=p2^.prev^.prev^.prev;{адрес на четвёртый элемент «двусвязного списка» с правого конца}

DELETE;{удаляем из списка четвёртый элемент}

p:=p2^.prev^.prev;{адрес на третий элемент «двусвязного списка» с правого конца }

DELETE;{удаляем из списка третий элемент}

PRINT_D_SPISOK;{просмотр «двусвязного списка» после удаления из него двух элементов}

End;

Задания по вариантам:

Для всех вариантов сначала нужно сформировать и заполнить элементами три структуры – «стек», «очередь», «двусвязный список». Для проверки вывести их на экран. Далее выполнить задание в соответствии с вариантом А (см. таблицу 2.1).

Таблица 2.1

Задание по лабораторной работе №2

А

Задание

1

2

1

Удалить элемент из «стека» и поместить его в «очередь» и «двусвязный список». Результат проверить.

2

Если все элементы «двусвязного списка» положительны, то обнулить «очередь». Результат проверить.

3

В «стек», «очередь» и «двусвязный список» добавить по одному одинаковому элементу. Результат проверить.

4

Если «очередь» пуста, то в неё добавить по одному элементу из «стека» и «двусвязного списка». Результат проверить.

5

Удалять из вершины «стека» n элементов, а последний элемент поместить в «двусвязный список». Результат проверить.

6

Все элементы «двусвязного списка» переместить в «стек». результат проверить.

7

Из элементов «стека» сформировать второй «двусвязный список». Результат проверить.

8

Удалить два элемента из «двусвязного списка», первый поместить в «очередь», а второй в «стек». Результат проверить.

9

Положительные элементы «двусвязного списка» добавить в «очередь». Результат проверить.

10

Если все элементы «двусвязного списка» отрицательны, то удалить элемент «стека». Результат проверить.

11

Из «очереди» удалить три элемента и поместить их в конец той же «очереди». Результат проверить.

12

По удалять из «стека», «очереди», «двусвязного списка» по 2 элемента. Результат проверить

13

Из первых элементов «стека» и «очереди» сформировать второй «двусвязный список». Результат проверить.

14

В «двусвязный список» добавить два разных элемента, а в «стек» - один. Результат проверить.

15

Из элементов «стека» сформировать вторую очередь. Результат проверить.


Продолжение таблицы 2.1

1

2

16

Удалить элемент из «очереди» и поместить его в «стек» и «двусвязный список». Результат проверить.

17

Если число элементов в «двусвязном списке» больше пяти, то добавить в него ещё три элемента. Результат проверить.

18

Если первый элемент очереди положительный, то удалить из стека все элементы кроме последнего, т.е. дна «стека». Результат проверить.

19

Все элементы «очереди» переместить в «двусвязный список». Результат проверить.

20

Из элементов «очереди» сформировать второй «стек». Результат проверить.

21

Если «стек» пуст, то в него добавить по одному элементу из «очереди» и «двусвязного списка». Результат проверить.

22

Вынимая элементы из «очереди», помещать их через один в «стек». Результат проверить.

23

Удалять из конца «двусвязного списка» заданное число элементов, а последний поместить в «стек». Результат проверить.

24

Если x равен вершине «стека», то удалить из «очереди» элемент и поместить его в «стек». Результат проверить.

25

Удалить два элемента из «стека», первый поместить в «очередь», а второй в «двусвязный список». Результат проверить.

26

Выбрать n элементов из «стека» и поместить их в очередь. результат проверить.

27

Из отрицательных элементов «двусвязного списка» сформировать вторую «очередь».

28

Все элементы «стека» переместить в «двусвязный список». Результат проверить.

29

Посчитать сколько элементов в «двусвязном списке», если их больше четырёх, то удалить два последних. Результат проверить.

30

Если три последних элемента «очереди» положительны, то скопировать их в «двусвязный список». Результат проверить.

31

N элементов «стека» поместить в очередь, а M элементов в «двусвязный список». Результат проверить.

32

Удалить элемент из «двусвязного списка» и поместить его в «очередь» и «стек». Результат проверить.


Продолжение таблицы 2.1

1

2

33

Из «очереди» удалять элементы. Первые пять положительных добавить снова в «очередь». Результат проверить.

34

В «очередь» добавить один элемент, а в «стек» два элемента. Результат проверить.

35

Посчитать сколько элементов в «двусвязном списке», если их больше трёх, то добавить ещё несколько. Результат проверить.

36

Из элементов «стека» сформировать вторую «очередь». Результат проверить.

37

Обнулить «стек» и заполнить его элементами «очереди». результат проверить.

38

Все элементы «двусвязного списка» переместить в «очередь». Результат проверить.

39

Удалить первый и последний элементы из «двусвязного списка». Результат проверить.

40

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

41

Из трёх первых элементов «стека» сформировать вторую «очередь». Результат проверить.

42

Удалить два элемента из «очереди», первый поместить в «стек», а второй в «двусвязный список». Результат проверить.

43

Отрицательные элементы «двусвязного списка» добавить в «стек». Результат проверить.

44

Все элементы «стека» переместить в «очередь». Результат проверить.

45

Обнулить «очередь», оставив только заголовок, а потом заполнить её любыми элементами. Результат проверить.

46

Если «двусвязный список» пуст, то в него добавить по одному элементу из «очереди» и «стека». Результат проверить.

47

Из элементов «очереди» сформировать второй «двусвязный список». Результат проверить.

48

Если первые элементы «стека», «очереди», и последний элемент «двусвязного списка» «+», то удалить их. Результат проверить.

49

В «стек» добавить три элемента, а в «двусвязный список» добавить максимальный элемент из этих трёх. Результат проверить.

50

Все элементы «очереди» переместить в «стек». Результат проверить.


 

А также другие работы, которые могут Вас заинтересовать

57619. КООПЕРАЦІЯ, КОЛЕКТИВІ3АЦІЯ, ГОЛОДОМОР В УКРАІНІ У 1932-33 РОКАХ 247.09 KB
  Мета - розкрити причини та наслідки політики радянського уряду щодо селянства в України у 20—их поч.30-их років; познайомити з фотодокументами, спогадами очевидців, що підтверджують існування голодомору в Україні у 1932-33 роках...
57620. ГОЛОДОМОР 1932-1933 РР. – ГЕНОЦИД УКРАЇНСЬКОГО НАРОДУ 120.5 KB
  Навчальна. Ознайомити учнів з історичними передумовами виникнення Голодомору, з політикою більшовиків проти українського народу, охарактеризувати наслідки Голодомору. Довести злочинний характер сталінізму. Простежити висвітлення Голодомору в українській літературі та фольклорі.
57621. Особливості розвитку культури у другій половині 19ст. Освіта. Наука 156 KB
  Мета: виявити загальні закономірності та особливості розвитку культури в Україні у другій половині 19ст. Грушевського в розвиток української науки; виховувати шанобливе ставлення учнів до визначних діячів української культури другої половини 19ст.
57622. The Еarth is our home 56.5 KB
  We live in a wonderful world. It is our Earth. For thousands of years the earth has given a support to all forms of life-human beings, animals, birds, insects and plants. Our planet looks like a paradise but it is in danger now. Our task is to understand it and to take care of it.
57623. What can you do to keep the Earth clean and healthy? You should be a friend to her 363.5 KB
  Aims: to develop students’ speaking skills through different methods of work (group, pair work, individual); to broaden students’ knowledge of the topic; to practice listening and making up the students’ own opinion on the topic; to practice students’ grammar and reading skills;
57624. Foreigh languages in our life. English and English speaking countries 119 KB
  Practical: to practise pupil’s speaking, listening, writing skills; to create an English – speaking atmosphere; to expand pupil’s vocabulary on this theme; to develop student’s creativity.
57625. The History of a Portrait (Home reading) 146.5 KB
  Objectives: to revise and enrich student’s vocabulary on topic; to develop student’s reading, writing and speaking skills; to teach students to describe objects; to practice students in using Conditional sentences; to foster student’s desire to speak English;
57626. Урок позакласного читання «Little Red Riding Hood» 214.5 KB
  Мета: ввести нові лексичні одиниці: a wood, a woodcutter, a basket, a cake to see, to hear, to smell, to shout; повторити правила читання буквосполучень: оо, sh, ou, ea; розвивати навички читання та усного мовлення;
57627. Round the calendar. My favourite holiday 58 KB
  Today we shall speak about different holidays in Ukraine and Britain. We shall do exercises, sing, listen to a very interesting tale. So, you must be active, careful and try to get good marks for the lesson.