МИНИСТЕРСТВО ОБЩЕГО И ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ.

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ АВИАЦИОННО-ТЕХНОЛОГИЧЕСКИЙ УНИВЕРСИТЕТ им. К.Э. ЦИОЛКОВКОГО

КАФЕДРА ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

к курсовой работе на тему: “Разработка алгоритмов и программ выполнения операций над последовательными и связанными представлениями структур данных”

по курсу “Теория алгоритмов и вычислительных методы”

Руководитель: Авдошин С.М.

Дата сдачи: _____________

Подпись: _____________

Студент: Лицентов Д.Б.

Группа: 3ИТ-2-26

Москва

1998

1. Постановка задачи.

Дано:
Два орграфа X и Y с N вершинами (X в последовательном представлении, Y в связанном представлении) без кратностей. Дуги орграфов образуют неупорядоченные списки. Орграфы задаются неупорядоченными списками смежных вершин - номеров вершин, в которые ведут ребра из каждой вершины графа.

Требуется:
Выполнить над ребрами орграфов операцию разности(X/Y). В результате выполнения этой операции новый орграф Z определяется в связанном представлении, а старый орграф X исправляется в последовательном представлении.

Особенности представления данных:

Последовательное представление данных: одномерный массив Array, содержащую два целочисленных поля I (содержит номер вершины, из которой исходит дуга) и J (содержит номер вершины, в которую входит дуга).

|Array[_]| |I | |J |
|Array[ 1 ]| |From | |To |
|Array[ 2 ]| |From | |To |
|… | |From | |To |
|Array[ N ]| |From | |To |

N – количество дуг в орграфе X.

Связанное представление данных: одномерный массив Spisok указателей на структуру index, представляющую собой элемент списка и содержащий поле: целочисленное index (содержит номер вершины, в которую входит дуга) и Next
- указатель на структуру Spisok, указывающее на следующий элемент списка
|Spisok[ _|NEXT | |inde|next| |inde|next| |Inde|Next |
|] | | |x | | |x | | |x | |
|Spisok[ 1| | |To | | |… | | |To |NULL |
|] | | | | | | | | | | |
|… | | |To | | |… | | |To |NULL |
|Spisok[ N| | |To | | |… | | |To |NULL |
|] | | | | | | | | | | |

N - количество вершин в графе Y,Z.

2. Внешнее описание программы.

Ввод информации об неориентированных графах происходит из файла, формат которого должен быть нижеследующим:
N
X11 X12 ... X1k1 0
X21 X22 ... X2k2 0
...
XN1 XN2 ... XNkN 0
Y11 Y12 ... Y1k1 0
Y21 Y22 ... Y2k2 0
...
YN1 YN2 ... YNkN 0 где N - число вершин в графах

Xij - номер очередной вершины смежной i в графе X (i = 1..N, j=1..ki)