38020

ПРЕДСТАВЛЕНИЕ И РЕАЛИЗАЦИЯ АТД «СПИСОК»

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

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

Краткая теория Реализация списка посредством массивов. При реализации списка посредством массивов используют два способа.n] of record pole1: integer; pole2: Boolen; end; vr :Spisok; Обращение к элементам такого списка будет выглядеть так. Тип для второй реализации списка посредством массивов рис 1.

Русский

2013-09-25

355.5 KB

20 чел.

11

EMBED Word.Picture.8  

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

«ПРЕДСТАВЛЕНИЕ И РЕАЛИЗАЦИЯ АТД «СПИСОК»»

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

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

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

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

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

Реализация «списка» посредством массивов. При реализации «списка» посредством массивов используют два способа. Первый способ – это массив ячеек, состоящих из нескольких полей (рис. 1.1). А второй способ – это составной тип, одно из полей которого является массивом (рис. 1.2).

         

Описание типа для первой реализации (рис. 1.1) выглядит следующим образом:

Type

Spisok=array [1..n] of record

pole1: integer;

pole2: Boolean;

end;

var a:Spisok;

Обращение к элементам такого списка будет выглядеть так. К первому полю ячейки ia[i].pole1, а к другому полю той же ячейки – a[i].pole2.

Тип для второй реализации «списка» посредством массивов (рис 1.2) выглядит следующим образом:

Type

Spisok= record

a: array [1..n] of integer;

top1, top2: Boolean;

end;

var S:Spisok;

Обращение к полю элементов списка имеет следующий вид – S.a[i], а к указателю начала и конца списка – S.top1 и S.top2. Указатели начала и конца списка содержат индексы первого и последнего элемента списка размещённого в поле a.

Количество полей в ячейках может быть разное, а все эти виды реализаций предполагают и более сложную вложенную структуру. Операторы, используемые со «списком», реализованным посредством массивов, имеют уникальные алгоритмы, работающие именно с такой структурой, но должны твёрдо выдерживают ту идею, для которой они предназначены. Например, оператор FIRST добавляет в список первый элемент, а оператор INSERT помещает последовательно элементы в «список», тогда как оператор DELETE удаляет элемент из любого места в «списке». Необходимо учитывать и нюансы такой структуры. Например, при удалении элементов необходимо перемещать все элементы после удалённого элемента на одну позицию, аналогично и для вставки элемента в любую позицию списка. Так же надо помнить, что эти реализации не совершенны, так как позволяют работать только с ограниченным, заранее определённым количеством элементов, а так же не позволяют экономить используемую память. Об этом необходимо помнить при составлении операторов и использовать проверки внештатных ситуаций.

Procedure INSERT;

Begin

top2:=top2+1; {перевод указателя конца списка на следующий новый элемент}

If top2<=max {если ещё есть место для вставки элемента в «список»}

then a[i].pole1:=x {или S.a[i]:=x}

else writeln(‘Spisok overflow!’);

End;

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

Type

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

pSpisok=record

element: string;

next: Spisok;

end;

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

Var p0, p, p1, p2, q: Spisok;

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

Procedure FIRST;

Begin

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

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

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

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

      

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

Procedure INSERT;

Begin

Repeat

Writeln(‘Enter element? y/n’);

Readln(b);

If b=’ythen

begin

q:=p1; {копируется адрес из одной ячейки в другую, т.к при следующем выполнении new(p1), предыдущий адрес ячейки заменятся новым адресом}

New(p1); {создаётся новая ячейка рис. 1.5}

Writeln(‘element’);

Readln(x);

p1^.element:=x;

p1^.next:=nil;

q^.next:=p1; {соединяется предыдущая ячейка с адресом q, там копия её адреса, и новая ячейка рис. 1.6}

End;

Until b<>’y’;

End;

 

Для корректной работы программ необходимо перед первым вызовом процедуры INSERT присвоить переменной p1 указатель на начало списка – p0, чтобы присоединить новый элемент «списка» к его заголовку header, т.е. к ячейке, изображённой на рисунке 1.4 , результат присоединения будет соответствовать рисунку 1.6. При дальнейших вызовах оператора INSERT такого присвоения делать не нужно, последующие элементы будут подсоединены к последнему элементу списка, адрес которого будет сохраняться в ячейке q.

… Begin

FIRST;

p1:=p0;

INSERT;

INSERT;…

End.

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

Procedure PRINT_SPISOK;

Begin

p:=p0;

Repeat

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

p:=p^.next;

Until p=nil;

End;

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

… Begin

…  INSERT;…

PRINT_SPISOK;…

DELETE;…

PRINT_SPISOK;

End.

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

Function LOCATE:Spisok;

Begin

Writeln(‘Enter located element: ’);

Readln(x);

p:=p0;

LOCATE:=nil;

Repeat

q1:=p; {хранит копию указателя на предыдущий элемент}

p:=p^.next;

Until (p=nil) or (p^.element=x);

If p=nil then writeln(‘Located element not found!’)

else LOCATE:=q1;

End;

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

Procedure DELETE;

Begin

Repeat

Writeln(‘Do you want to delete element? y/n’);

Readln(b);

If b=’y’ then

Begin 

Writeln (What element might delete?’);

Readln(x);

p2:=LOCATE;

{проверка на наличие элемента в «списке»}

If p2=nil then writeln (‘No same element in spisok!’);

{если удаляемый элемент последний в «списке», то в поле next предпоследнего элемента помещается nil, т.е. обрывается связь с удаляемым элементом (рис. 1.7)}

If p2^.next^.next=nil then p2^.next:=nil;

{если это любой другой элемент «списка»}

If p2<>nil then p2^.next:=p2^.next^.next;

End;

Until b<>’y’;

End;

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

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

Для каждого варианта A задание состоит из двух частей:

1) по теме реализация «списка» посредством массивов (табл. 1);

2) реализация «списка» посредством указателей (табл. 2).

Таблица 1

Задание по первой части лабораторной работы №1

A

Задание

1

2

1

Составить оператор ISERT_IN_i, который добавляет элемент в позицию i «списка».

2

Составить оператор DELETE_2, удаляющий чётные элементы

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

1

2

3

Составить оператор, проверяющий «список» на пустоту.

4

Составить оператор FIND_MAX, который ищет максимальный элемент в «списке».

5

Составить оператор PRINT_SPISOK, который выводит «список» на экран в прямом порядке.

6

Составить оператор INSERT_NEW, который проверяет наличие элемента в «списке» и, если его там нет, то вставляет его в конец списка.

7

Составить оператор LOCATE, который ищет заданный элемент в «списке».

8

Составить оператор PRINT_half_SPISOK, который выводит на экран первую половину «списка».

9

Составить оператор DELETE, который удаляет элемент так: ставит FALSE в поле view, которое определяет присутствие элемента в «списке».

10

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

11

Составить оператор, определяющий количество элементов в «списке».

12

Структура «список» состоит из трёх полей. Первое поле elements, состоит из 8 элементов, второе поле beg1 определяет индекс начала списка, а третье поле count содержит информацию о числе элементов «списка». Составить тип для данной структуры.

13

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

14

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

15

Составить оператор PREVIOUS, который определяет предыдущий элемент от заданного.

16

Составить оператор CHANGE_i, который меняет местами два соседних элемента i и i+1.

17

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

18

Составить оператор LOCATE_and_INSERT, который ищет в «списке» заданный элемент и вставляет его в конец «списка», если уже такой элемент есть.

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

1

2

19

Составить оператор PRINT_SPISOK, который выводит «список» на экран в обратном порядке.

20

Составить оператор FIND_place, который определяет число свободных ячеек, не занятых «списком».

21

Составить оператор INSERT_2, который добавляет в список только чётные элементы.

22

Составить оператор END_SPISOK, который определяет конец «списка».

23

Составить оператор MAKENUL, который делает «список» пустым.

24

Составить оператор INSERT, который вставляет элементы в начало «списка».

25

Составить оператор DELETE_END, который удаляет последний элемент списка.

26

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

27

Составить оператор NEXT, который определяет элемент следующий после заданного x.

28

Составить оператор PRINT_double_SPISOK, который выводит на экран список сначала в прямом, а потом в обратном порядке.

29

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

30

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

31

Составить оператор FIND, который определяет пустые ячейки в «списке».

32

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

33

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

34

Составить оператор PRINT_step, который выводит на экран элементы «списка» с шагом 1.

35

Составить оператор FIND_same, который ищет одинаковые элементы и помещает TRUE в поле same найденных ячеек «списка».

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

36

Составить оператор LOCATE_i, который ищет позицию заданного элемента в «списке».

37

Составить оператор DELETE, который удаляет любо элемент в «списке».

38

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

39

Составить оператор INSERT_del_el, который отменяет удаление элементов, заменяя FALSE на TRUE в поле view ячейки списка.

40

Составить оператор FIND_MIN, который ищет минимальный элемент в «списке».

41

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

42

«Список» состоит из 50 элементов, каждый имеет по 3 поля – информационное info; фиксирующее удалён или нет view; определяющее количество одинаковых count. Составить для этой структуры тип.

43

Составить оператор INSERT_3, который добавляет в список только нечётные элементы.

44

Составить оператор PRINT_half_SPISOK, который выводит на экран вторую половину «списка».

45

Составить оператор CHANGE_i, который меняет местами два соседних элемента i-1 и i.

1

2

46

Составить оператор DELETE_all_find, который удаляет все найденные элементы, равные заданному элементу

47

Составить оператор INSERT_NEW, который проверяет наличие элемента в «списке» и, если его там нет, то вставляет его в начало списка.

48

Составить оператор PRINT, который выводит на экран первый и последний элемент списка.

49

Составить оператор DELETE_10, который удаляет последние десять элементов.

50

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

Таблица 2

Задание по второй части лабораторной работы №1

A

Задание

1

2

1

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

2

Является ли искомый элемент последним в «списке».

3

Вывести на экран каждый третий элемент «списка».

4

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

5

Удалить все нечётные элементы в «списке».

6

Проверить «список» на пустоту и добавить 5 элементов.

7

Удалить третий элемент «списка».

8

Из двух последних элементов 1-го «списка», сделать 2-ой.

9

Сформировать «список» из положительных элементов.

10

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

11

Вывести на экран первую половину «списка».

12

Соединить два «списка» в один.

13

Если список не пустой, то удалить центральный элемент.

14

Является ли искомый элемент первым в 2 «списках».

15

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

16

Если искомый элемент последний, то удалить его.

17

Если элемент x в «списке» есть, то вставить его в начало.

18

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

19

Создать два «списка».

20

Удалить весь «список» по одному элементу.

21

Поменять местами первый и последний элементы.

22

Удалить элемент из «списка», стоящий после заданного x.

23

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

24

Создать 2 списка и вывести на экран их первые элементы.

25

Если такого элемента нет в «списке», то вставить его туда.

26

Если 1-ый элемент «–», то сделать список из 8 элементов.

27

Удалить найденный элемент «списка».

28

Переместить из 1 списка «–» элементы во 2 «список».

29

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

30

Удалить первых 3 элемента «списка» одним оператором.

31

Сделать «список» кольцевым.

32

Проверить наличие искомого элемента x в 2 «списках».

33

Сформировать «список» из не повторяющихся элементов.

34

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

35

В начало «списка» вставлять + числа, в конец – числа.

36

Удалить заголовок «списка».

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

37

Из двух разных «списков» составить один «список».

38

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

39

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

40

Создать два списка из положительных и отрицательных х.

41

Посчитать число совпадений заданного x в «списке».

42

Удалить все чётные элементы в «списке».

43

Сформировать три разных «списка».

44

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

45

Если в «списке» нет элементов, то добавить несколько.

46

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

47

Необходимо вывести элементы на экран с шагом 2.

48

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

49

Если x нет в «списке», то вставить его в начало «списка».

50

Удалять любой элемент из «списка».


 

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

45093. Психические и поведенческие расстройства вследствие употребления алкоголя (F10) 49 KB
  Психологической причиной является прием алкоголя как препарата улучшающего коммуникации как антидепрессанта для снижения уровня тревоги. Кроме того некоторые личностные черты сами по себе могут нивелироваться приемом алкоголя хотя алкоголизм обыкновенно в дальнейшем их заостряет. Для диагностики алкогольного опьянения применяются методы определения алкоголя в выдыхаемом воздухе пробы Раппопорта и Мохова Шинкаренко.
45094. Психические и поведенческие расстройства вследствие употребления опиоидов (F11) 31 KB
  Терапия острой передозировки опиатами включает применение налоксона 001 мг на кг веса или антаксона. К специфической терапии относятся метадоновая как первичная терапия при детоксикации так и в ходе реабилитации как поддерживающая терапия лечение клонидином в ходе детоксации а также терапия налоксоном и налтрексоном или бупренорфином как частичным агностом опиатов. Требуются также продолжительная и упорная групповая и индивидуальная психотерапия и реабилитация в специализированных центрах.
45095. Хронические бредовые расстройства (F22) 34.5 KB
  В строгом смысле это монотематический бред который вторично может приводить к депрессии если пациент не может реализовать своей моноидеи или агрессии против предполагаемых врагов. Идеи преследования величия отношения изобретательства или реформаторства ревности и влюбленности или убежденность в наличии некоего заболевания религиозные идеи аффективно заряжены. Идеи величия и религиозные идеи приводят пациентов к руководству еретическими сектами и новыми мессианскими течениями. Идеи ревности и влюбленности синдром Клерамбо нелепы при...
45096. Программирование КИХ-фильтра на языке ассемблера процессора ADSP-2181 569.5 KB
  Разработка программы КИХ-фильтра заданного типа и с заданными характеристиками на языке ассемблера ADSP-2181. Изучение характеристик спроектированного фильтра с использование программы DFT.ASM. Изучение преобразований типовых дискретных сигналов при прохождении через КИХ-фильтры.
45097. Исследование процесса аналого–цифрового преобразования радиолокационных эхо-сигналов 1.21 MB
  Исследование спектрально-корреляционных свойств радиолокационных сигналов и помех Временная реализация процесса: Автокорреляционная функция процесса: Спектр процесса: Исследование характеристик аналого-цифрового преобразования Исследование влияния на ошибки квантования спектры квантованного сигнала и сигнала ошибки выбора величины динамического диапазона АЦП Спектры квантованного сигнала и сигнала ошибки выбора величины динамического диапазона АЦП: А Д А=Д А Д При уменьшении амплитуды сигнала от D до...
45098. Знакомство с основами работы с Visual DSP++. Изучение программно-логической модели ADSP-2181 3.15 MB
  Сигнальный процессор взаимодействует с внешней средой путём использования адресной шины (ADDR), шины данных параллельного обмена (DATA), мультиплексированной шины адреса/данных (IAD)...
45099. Программная реализация алгоритма ДПФ на языке ассемблера процессора ADSP-2181 4.2 MB
  Сигнальный процессор взаимодействует с внешней средой путем использования адресной шины ADDR, шины данных параллельного обмена DATA, мультиплексированной шины адреса/данных IAD, линий последовательного обмена DT0, DR0, DT1, DR1 и использования информационных, управляющих, служебных сигналов и сигналов прерываний
45100. English in my life 15.61 KB
  English is the max widespread language nowadays. It is a world language, spoken by more than 1750 million people. Residents of more than 70 countries speak English(for example, Canada, Australia, New Zeeland, USA and others)
45101. Great Britain 14.21 KB
  Gret Britin is situted on the British Isles. The lrger of two big islnds is known s Gret Britin. The islnd of Gret Britin together with the neighboring minor islnds nd the northestern prt of Irelnd constitute the United Kingdom of Gret Britin nd Northern Irelnd.