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

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


 

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

32140. LC {DL аббревиатура на звания известной консалтинговой фирмы rthur D. 27.5 KB
  Конкретные модели относящиеся к отмеченному концептуальному подходу в основном различаются по 3 ключевым характеристикам: 1 оценочные показатели по осям матрицы которые так или иначе определяют существенные характеристики каждого конкретного бизнеса; 2 содержание и форма самих матриц характеризующие уровень глубины и детализации позиционирования; 3 наборы типовых стратегических решений которые соответствуют различным позициям бизнеса на сетке матрицы а также различным маршрутам возможного движения бизнеса по разным позициям в...
32141. Производственная стратегия как подсистема корпоративных стратегий 27.5 KB
  Производственная стратегия это подсистема корпоративной стратегии представленная в виде долгосрочной программы конкретных действий по созданию и реализации продукта организации; подсистема предусматривает использование и развитие всех производственных мощностей организации в целях достижения стратегического конкурентного преимущества. Для многих промышленных компаний производство того или иного продукта как правило является наиболее сложной и масштабной деятельностью. При системной оценке производственных затрат как для...
32142. Стратегия управления персоналом 28.5 KB
  Стратегия управления персоналом Стратегия управления персоналом это подсистема стратегии организации представленная в виде долгосрочной программы конкретных действий по реализации концепции использования и развития потенциала персонала организации в целях обеспечения ее стратегического конкурентного преимущества. Стратегия использования и развития потенциала персонала наряду с продуктовомаркетинговой стратегией является ключевой функциональной стратегией организации. Стратегия реализующая принцип купить предполагает привлечение...
32143. Финансовая стратегия. Первичный формат. Особенности 32 KB
  Особенности Финансовая стратегия это подсистема корпоративной стратегии представленная в виде долгосрочной программы конкретных действий по использованию собственных и привлеченных внешних финансовых ресурсов в организации для достижения стратегического конкурентного преимущества. Первичный формат стратегии. Значение финансовой стратегии т. Определение основных целей финансовой стратегии.
32144. Основные этапы цикла реализации стратегии 31 KB
  Основные этапы цикла реализации стратегии Реализация стратегии в широком смысле это непрерывная цикличная деятельность когда одна корпоративная стратегия регулярно заменяется другой качественно новой. Другими словами при расширенном толковании понятия циклическая реализация стратегии и стратегический менеджмент понимаемая как постоянная профессиональная деятельность фактически совпадают. На стадии запуска корпоративной стратегии каждый уровень менеджмента организации должен решать свои особые задачи. Вовторых завершить...
32145. Сущность стратегической эффективности 32.5 KB
  Сущность стратегической эффективности и одну из коренных причин текущей и перспективной актуальности стратегического менеджмента раскрывает тезис: в современном бизнесе ошибки в стратегии неизбежно приводят к поражению в конкурентной борьбе и ослаблению позиций организации на рынке; при этом стратегические ошибки исправить сколь угодно эффективными приемами оперативного менеджмента нельзя в принципе. Основные задачи стратегической рефлексии: логическое завершение стратегии организации; предложения по совершенствованию...
32146. Стратегический и тактический контролинг 40.5 KB
  Современный контроллинг включает в себя управление рисками страховой деятельностью предприятий обширную систему информационного снабжения предприятия систему оповещания путём управления системой ключевых финансовых индикаторов управление системой реализации стратегического тактического и оперативного планирования и систему менеджмента качества. Стратегический контролинг координация функции стратегического анализа целеполагания планирования и коррекции стратегии; осуществление контроля за функционированием всей системы в целом;...
32147. Элементы сбалансированной системы показателей 24.5 KB
  Элементы сбалансированной системы показателей Основной принцип ССП который во многом стал причиной высокой эффективности этой технологии управления управлять можно только тем что можно измерить. ССП делает акцент на нефинансовых показателях эффективности давая возможность оценить такие казалось бы с трудом поддающиеся измерению аспекты деятельности как степень лояльности клиентов или инновационный потенциал компании. Авторы ССП предложили четыре направления оценки эффективности отвечающие на самые значимые для успешной деятельности...
32148. Задачи и функции подразделения стратегического развития 31 KB
  Перед отделом стратегического развития который должен функционировать на постоянной профессиональной основе стоят две главные задачи: Сведение всех стратегических наработок произведенную в первую очередь самим отделом а также другими по разделениями Организации в заданные определенным форматом проекты решений. Проекты в установление порядке представляются отделом в органы управления организации которые уполномочены принимать соответствующие стратегические решения. В большинстве организаций такими органами управления являются:...