КАФЕДРА ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ
ПОЯСНИТЕЛЬНАЯ ЗАПИСКА
к курсовой работе на тему : “Разработка алгоритмов и
программ выполнения операций над последовательными
и связанными представлениями структур данных ”
по курсу “ Теория алгоритмов и вычислительных
методы ”
Руководитель : Авдошин С.М.
Дата сдачи: _____________
Подпись: _____________
Студент: Лицентов Д.Б.
Группа : 3ИТ- 2-26
Москва
1998
1. Постановка задачи.
Возможно вы искали - Реферат: Разработка алгоритмов и программных средств подсистемы документооборота системы управления содержанием информационного сервера
Дано :
Два орграфа X и Y с N вершинами ( X в последовательном представлении , Y в связанном представлении) без кратностей. Дуги орграфов образуют неупорядоченные списки. Орграфы задаются неупорядоченными списками смежных вершин - номеров вершин , в которые ведут ребра из каждой вершины графа.
Требуется :
Выполнить над ребрами орграфов операцию разности (X/Y ). В результате выполнения этой операции новый орграф Z определяется в связанном представлении , а старый орграф X исправляется в последовательном представлении.
Особенности представления данных :
Похожий материал - Реферат: Разработка альтернативных моделей предметной области в виде многоуровневых контекстных диаграмм
Последовательное представление данных : одномерный массив Array , содержащую два целочисленных поля I ( содержит номер вершины, из которой исходит дуга) и J ( содержит номер вершины, в которую входит дуга).
| Array[_] |
| I |
| J | |
|
|
| From |
| To | |
| Array[ 2 ] |
| From |
| To | |
| … |
| From |
| To | |
| Array[ N ] |
| From |
| To | |
Array[ 1 ]
Очень интересно - Реферат: Разработка антивирусного монитора
N – количество дуг в орграфе X.
Связанное представление данных : одномерный массив Spisok указателей на структуру index , представляющую собой элемент списка и содержащий поле : целочисленное index ( содержит номер вершины, в которую входит дуга) и Next - указатель на структуру Spisok , указывающее на следующий элемент списка
| Spisok[ _ ] | NEXT | index | next | index | next | Index | Next |
|
| To | … | To | NULL | |||
| … | To | … | To | NULL | |||
| Spisok[ N ] | To | … | To | NULL |
Spisok[ 1 ]N - количество вершин в графе Y,Z.
2. Внешнее описание программы.
Ввод информации об неориентированных графах происходит из файла, формат которого должен быть нижеследующим :
Вам будет интересно - Реферат: Разработка аппарата измерения торцевого биения
N
X11 X12 ... X1k1 0
X21 X22 ... X2k2 0
...
XN1 XN2 ... XNkN 0
Похожий материал - Реферат: Разработка баз данных в Delphi
Y11 Y12 ... Y1k1 0
Y21 Y22 ... Y2k2 0
...
YN1 YN2 ... YNkN 0