Понедельник, Июль 5th, 2010

Структуры и алгоритмы обработки данных

Задания

Варианты :
1. Написать программу передвижения элемента на n позиций.
2. Создать копию списка.
3. Добавить элемент в начало списка.
4. Склеить два списка.
5. Удалить n-ый элемент из списка.
6. Вставить элемент после n-го элемента списка.
7. Создать список содержащий элементы общие для двух списков.
8. Упорядочить элементы в списке по возрастанию.
9. Удалить каждый второй элемент списка.
10. Удалить каждый третий элемент списка.
11. Упорядочить элементы списка по убыванию.
12. Очистить список.

Лабораторная работа № 3. «КОЛЬЦЕВЫЕ СПИСКИ»

Цель работы: исследовать и изучить кольцевые списки на примере основных процедур.

Задача работы: овладеть навыками написания программ по исследованию основных процедур списковых структур на языке программирования ПАСКАЛЬ .

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

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

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

Как видно на рисунке, список замыкается в своеобразное «кольцо»: двигаясь по ссылкам, можно от последнего элемента списка переходить к заглавному элементу. В связи с этим списки подобного рода называют кольцевыми списками.
Чтобы закольцевать список необходимо присвоить указателю последнего элемента указатель начала списка (Ptr(p)=lst).
Ptr(p) — указатель последнего элемента;
Lst — указатель начала списка.

Алгоритм

Операции с кольцевыми списками:
Вставка элемента в кольцевой список

Чтобы это осуществить необходимо произвести следующие действия:

a) Создать пустой элемент на который указывает указатель q
q=getnode
b) Внести х в информационное поле созданного элемента
info(q)=x
c) Связать элемент Х с элементом В
ptr(q)=ptr(p) — это означает, что указателю
созданного элемента присваивается значение указателя элемента p.
d) Связать элемент А с элементом Х
ptr(p)=q — это означает, что следующим за элементом
А будет элемент на который указывает указатель q.
Окончательно:

Детально процесс вставки был проиллюстрирован в предыдущей работе.

Удаление элемента из кольцевого списка

Удалим из списка элемент, который следует за элементом с рабочим указателем р.

Чтобы это осуществить, необходимо произвести следующие действия:
a) Ввести указатель q, который будет указывать на удаляемый элемент.
q=ptr(p)
b) Поставить за элементом А элемент В
ptr(p)=ptr(q)
c) Запомнить информацию, которая содержится в поле info удаляемого элемента.
k=info(q)
d) Удалить элемент с указателем q.
Freenode(q)
Окончательно:

Задания

Варианты:
1) Дан кольцевой список, содержащий 20 фамилий игроков футбольной    команды. Разбить игроков на 2 группы по 10 человек. Во вторую группу попадает каждый 12-й человек.

Страницы: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84

Категория: Учебники