<< Пред. стр. 10 (из 19) След. >>
Список литературы по разделу
Чтобы это осуществить необходимо произвести следующие действия :
a) Создать пустой элемент на который указывает указатель q.
Q=getnode
b) Внести х в информационное поле созданного элемента.
Info(Q)=x
c) Связать элемент х с элементом В.
Ptr(Q)=Ptr(P) - это значит, что указателю созданного элемента присваивается значение указателя элемента р.
d) Связать элемент А с элементом х.
Ptr(p)=Q - это значит, что следующим за элементом А будет элемент на который указывает указатель Q.
Окончательно :
Удаление элемента из односвязного списка
Удалим из списка элемент, который следует за элементом с рабочим указателем р.
Чтобы это осуществить необходимо произвести следующие действия :
a) Ввести указатель Q, который будет указывать на удаляемый элемент.
Q=ptr(p)
b) Поставить за элементом А элемент В.
Ptr(p)=Ptr(Q)
с) Запомнить информацию, которая содержится в поле info удаляемого элемента.
K=info(Q)
d) Удалим элемент с указателем Q.
Freenode(Q)
Окончательно :
Задания
Варианты :
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-й человек.
2) Даны 2 кольцевых списка, содержащие фамилии спортсменов 2-х фехтовальных команд. Произвести жеребьевку. В первой команде выбирается каждый n-й игрок, а во второй - каждый m-й.
3) Задача Джозефуса.
4) Даны 2 кольцевых списка, содержащие фамилии участников лотереи и наименования призов. Выиграет N человек (каждый К-й). Число для пересчета призов - t.
5) Даны 2 списка, содержащих фамилии учащихся и номера экзаменационных билетов. Число пересчета для билетов - Е, для учащихся - К. Определить номера билетов, вытащенных учащимися.
6) Дан список содержащий перечень товаров. Из элементов 1-го списка (товары изготовленные фирмой SONY) создать новый список.
7) Даны 2 списка, содержащие фамилии студентов 2-х групп. Перевести L студентов из 1-й группы во вторую. Число пересчета -К.
8) Даны 2 списка, содержащие перечень товаров, производимых Концернами BOSH и FILIPS. Создать список товаров, выпускаемых как одной так и другой фирмой.
9) Даны 2 списка, содержащие фамилии футболистов основного состава команды и запасного. Произвести К замен.
10) Даны 2 списка, содержащие фамилии солдат 1-го и 2-го взводов. Во время атаки М человек из 1-го взвода погибли. Произвести пополнение солдатами 2-го взвода.
11) Даны 2 списка, содержащие перечень товаров и фамилии покупателей. Каждый N-й покупатель покупает М-й товар. Вывести список покупок.
12) Даны 2 списка, содержащие наименования товаров, выпускаемых фирмами SONY и SHARP. Создать список товаров, конкурирующих между собой товаров.
Лабораторная работа № 4. "МОДЕЛЬ МАССОВОГО ОБСЛУЖИВАНИЯ"
Цель работы: исследовать и изучить применение списковых структур данных при моделировании систем массового обслуживания.
Задача работы: овладеть навыками написания программ для теории массового обслуживания на языке программирования ПАСКАЛЬ .
Порядок работы :
* изучить описание лабораторной работы;
* по заданию, данному преподавателем, разработать алгоритм программы решения задачи;
* написать программу на языке ПАСКАЛЬ;
* отладить программу;
* решить задачу;
* оформить отчет.
Краткая теория
Формулировка задачи.
Пусть обслуживающая система состоит из конечного числа обслуживающих аппаратов. Система относится к числу систем с ожиданием. Каждый аппарат может обслуживать одновременно только одно требование. Если в момент поступления очередного требования имеются свободные аппараты, то один из них немедленно приступает к обслуживанию, если свободных аппаратов нет, то требование ждет обслуживания. Естественно, если требований больше, чем обслуживающих аппаратов, то образуется очередь. Время обслуживания одного требования есть случайная величина, подчиненная показательному закону распределения:
F(t)=1-e-?t
Поток поступающих требований ограничен, то есть одновременно в системе обслуживания не может находиться больше m требований, где m - конечное число. Это дает право считать, что требования на обслуживание поступают от m обслуживаемых объектов, которые время от времени нуждаются в обслуживании. Пусть вероятность того, что поступит заявка на обслуживания на данном такте равна Р(А) и вероятность того, что требование из очереди поступит на обслуживание равно Р(В) ( на каждом такте может поступить не более одной заявки на обслуживание). Число обслуживающих аппаратов равно N. Допустим, требование дождалось своей очереди и оно начало обслуживаться. Обслуживание может длиться в течении не более 3-х тактов. Заявки могут быть двух приоритетов:
Заявка первого приоритета:
Это обычная заявка, она не обладает ни какими привилегиями. Она может покинуть систему через определенное число тактов Т. При приходе в обслуживающую систему заявка первого приоритета становится в конец очереди.
Заявка второго приоритета:
Эта заявка отличается только тем, что она при поступлении в обслуживающую систему становится в начало очереди, то есть как только освобождается аппарат, то она поступает на обслуживание с вероятностью Р(В).
Заявка второго приоритета , как и заявка первого приоритета, покидает систему через Т тактов. Естественно, что появление заявок второго приоритета достаточно мало ( хотя эта вероятность задается пользователем и может быть любой ). Теперь об обслуживании: Количество тактов, в течение которых будет обслуживаться та или иная заявка выбирается случайно (эта величина в данной задаче не должна быть больше 3). Если заявка обслужилась положенное ей число тактов, то она покидает систему. Если заявка находится в очереди больше Т тактов, то она с некоторой вероятностью покидает систему.
Алгоритм
Наиболее рациональна реализация очередей в виде списковых структур данных. Данная задача при ее реализации на ЭВМ дает большие навыки при работе со списковыми структурами и при написании алгоритма программы следует воспользоваться стандартными процедурами, такими как присоединение элемента в начало и конец списка, удаление произвольного элемента из списка. Эти процедуры имеют следующий вид:
Процедура прибавления элемента в начало списка.
p = getnode Node(p) - элемент, на который указывает
info(p) = d указатель Р
ptr(p) = lst info(ptr(p)) - информационное поле следующего
lst = b элемента списка
Процедура удаления из начала списка.
p = lst
х = info(p)
lst = ptr(p)
freenode(p) - делает свободный узел с указателем
Процедура прибавления элемента в список.
p = getnode q - вставляемый
info(p) = x
ptr(q) = ptr(p)
ptr(p) = q
Процедура удаления из списка
q = ptr(p) q - удаляемый
ptr(p) = ptr(q)
x = info(p)
freenode(q)
Задания
Общее задание для всех.
Пусть имеется обслуживающая система из n обслуживающих аппаратов. Работа этой системы разбита на такты. В течение одного такта может одна заявка стать в очередь и одна заявка приступить к обслуживанию, (разумеется, если аппарат свободен). Вероятность заявки поступить на обслуживание Р(A), вероятность обслужить заявку P(B), вероятность заявки покинуть очередь после Т тактов Р(С). После каждых L тактов давать информацию о длине очереди и число тактов, в течении которых обслуживающий аппарат простаивал. Четным вариантам реализовать обслуживающую систему c неограниченной очередью, нечетным вариантам с конечной очередью (т.е. если в очереди будет стоять К заявок, то следующая заявка получает отказ в обслуживании).
Варианты:
1) L=50, после окончания работы системы выдать информацию, сколько заявок покинуло систему без обслуживания.
2) L=55, после окончания работы системы выдать информацию, сколько заявок обслуживалось больше 2 тактов.
3) L=100, после окончания работы системы выдать информацию, сколько тактов очередь была пустой.
4) L=75 , после окончания работы системы выдать информацию, сколько заявок обслуживалось один такт.
5) L=25 , после окончания работы системы выдать информацию, сколько заявок первого приоритета приступили к обслуживанию.
6) L=40 , после окончания работы системы выдать информацию о среднем приращении очереди.
7) L=80 , после окончания работы системы выдать информацию, сколько заявок обслуживалось 2 такта.
8) L=100, после окончания работы системы выдать информацию, заявок обслужилось.
9) L=70 , после окончания работы системы выдать информацию, на каком такте была самая длинная очередь.
10) L=50, после окончания работы системы посчитать практическую вероятность простоя аппарата по формуле s/n, где s- число тактов простоя аппарат, n- общее число тактов.
11) L=65, после окончания работы системы выдать информацию, сколько заявок второго приоритета поступили на обслуживания.
12) L=30, после окончания работы системы выдать информацию, сколько заявок обслуживалось 2 или 3 такта.
Лабораторная работа № 5. "БИНАРНЫЕ ДЕРЕВЬЯ(основные процедуры)"
Цель работы: исследовать и изучить процедуры, используемые при работе с бинарными (двоичными) деревьями.
Задача работы: овладеть навыками написания программ по исследованию бинарных деревьев .
Порядок работы :
* изучить описание лабораторной работы;
* по заданию, данному преподавателем, разработать алгоритм программы решения задачи;
* написать программу на языке ПАСКАЛЬ;
* отладить программу;
* решить задачу;
* оформить отчет.
Краткая теория
Общие сведения о структуре данных – дерево.
Дерево - это нелинейная связанная структура данных, характеризуемая следующими признаками :
* дерево имеет один элемент, на который нет ссылок от других элементов. Этот элемент, или "узел", называется корнем дерева;
* в дереве можно обратиться к любому элементу путем прохождения конечного числа ссылок (указателей) ;
* каждый элемент дерева связан только с одним предыдущим элементом.
Каждый узел дерева может быть промежуточным (элементы 2,3,5,7) либо терминальным ("листом" дерева) (элементы 4,9,10,11,8,6). Характерной особенностью терминальных узлов является отсутствие ветвей.
Элемент Y, находящийся непосредственно ниже элемента X, называется непосредственным потомком X, если X находится на уровне i , то говорят, что Y лежит на уровне i+1.
Считается, что корень лежит на уровне 0.
Число непосредственных потомков элемента называется его степенью исхода, в зависимости от степени исхода узлов деревья классифицируют :
A) Если степень исхода узлов - М, то дерево называется М-арным ;
B) Если степень исхода узлов - М или 0, то - полное М-арное дерево;
C) Если степень исхода узлов дерева равна 2, то дерево называется бинарным ;
D) Если степень исхода равна 2 или 0, то - полное бинарное дерево.
Особенно важную роль играют бинарные деревья, далее мы будем рассматривать их более подробно.
Представление деревьев в памяти ЭВМ
Деревья наиболее удобно представлять в памяти ЭВМ в виде связанных нелинейных списков. Элемент должен содержать INFO-поле, где содержится характеристика узла. Следующее поле определяет степень исхода узла и количество полей указателей равное степени исхода. Каждый указатель элемента ориентирует данный элемент-узел с его сыновьями. Узлы, в которые входят стрелки от исходного элемента, называются его сыновьями.
INFO-поле содержит два поля : поле записи (rec) и поле ключа (key). Ключ задается числом, по ключу определяют место элемента в дереве.
Сведение М-арного дерева к бинарному
1. В каждом узле дерева отсекают все ветви, кроме крайних левых, соответствующих старшим сыновьям;
2. Соединяют горизонтальными линиями сыновей одного родителя (узла);
2. Старшим сыном в каждом узле полученной структуры будет узел под обрабатываемым узлом.
Построение бинарных деревьев
Согласно представлению деревьев в памяти ЭВМ каждый элемент (узел бинарного дерева) будет записью, содержащей четыре поля. Значением этих полей будут соответственно ключ записи, ссылка на элемент влево-вниз, на элемент вправо-вниз и на текст записи.
При построении необходимо помнить, что левый сын имеет ключ меньше чем отец (родитель). Значение ключа правого сына больше значения ключа отца.
Например, узлы дерева имеют значения 6, 21, 48, 49, 52, 86, 101.
Бинарное дерево будет иметь вид:
Получили упорядоченное бинарное дерево с минимальным числом уровней.
Идеально сбалансированное дерево - это дерево, в котором левое и правое поддеревья имеют уровни, отличающиеся не больше, чем на единицу.
Алгоритм
Процедура создания бинарного дерева
Для построения дерева необходимо создать в памяти ЭВМ элемент следующего типа:
<< Пред. стр. 10 (из 19) След. >>
Список литературы по разделу