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

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


 

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

57510. Іменники-синоніми. Іменники-антоніми. Багатозначні слова 35 KB
  Мета: удосконалювати вміння вживати в мовленні іменники-синоніми антоніми як засіб увиразнення мовивміти застосовувати в мовленні багатозначні словарозвивати і збагачувати мовлення дітей виховувати інтерес до рідної мови.
57511. Омоніми 91 KB
  Мета: дати учням поняття про омоніми, формувати вміння визначати омоніми в реченнях, пояснювати їхнє лексичне значення, доречно вживати їх у мовленні; удосконалювати орфографічні та пунктуаційні навички.
57513. Слово. Значення слова 230.5 KB
  Мета: закріплювати знання про пряме і переносне значення слів багатозначність слова синоніми і антоніми удосконалювати навички користування фразеологізмами; збагачувати словниковий запас розвивати творче мислення та мовлення учнів...
57514. Соціально-економічний розвиток українських земель у І половині ХVІІ століття 41.5 KB
  Мета: розглянути процес зростання магнатського землеволодіння, зростання міст; розвивати вміння узагальнювати матеріал; виховувати інтерес до предмету.
57515. Реформи адміністративно-полiтичного управління 60—70-х років ХІХ ст. у підросійській Україні 91 KB
  Реформи адміністративнополiтичного управління 60 70х років ХІХ ст.у Російській імперії розуміти значення та наслідки перетворень для українського народу аналізувати історичні події та давати характеристику історичним постатям того часу; розвивати історичне мислення учнів та вміння порівнювати реформи минулого з сучасними перетвореннями сприяти критичному осмисленню минулого...
57516. Наш край у I половині ХІХ століття 82 KB
  Мета уроку: Сприяти оволодінню учнями програмовим матеріалом із визначеної теми Самостійно структурувати зміст уроку, складати опорний конспект, аналізувати та узагальнювати історичні факти, визначати зв’зки між ними, їх причини, сутність, наслідки та значення.
57517. Внутрішня і зовнішня політика Павла Скоропадського 37.5 KB
  Внутрішня і зовнішня політика Павла Скоропадського. Як гетьман ставився до української національної справи 29 квітня 1918останній день правління УЦР і початок правління гетьманату Скоропадського. Саме так одним з факторів приходу Скоропадського до влади стала підтримка з боку окупаційних військ.
57518. Люблінська унія 66 KB
  Мета: визначити передумови обєднання Великого князівства Литовського та Польського королівства в одну державу та наслідки, які мала ця подія для українських земель...