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

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

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

им. К.Э. ЦИОЛКОВКОГО

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

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

к курсовой работе на тему : “Разработка алгоритмов и

программ выполнения операций над последовательными

и связанными представлениями структур данных ”

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

методы ”

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

Дата сдачи: _____________

Подпись: _____________

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

Группа : 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	index	next	index	next	Index	Next
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)

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

Если из какой-то вершины не выходит ни одного ребра , то для нее в исходных данных задаем только ноль (например ‘0’ - вершина 2 изолирована). Таким образом, для каждого графа должно вводится в общей сложности N нолей.

Формат печати результатов <

Внимание, отключите Adblock

Вы посетили наш сайт со включенным блокировщиком рекламы!
Ссылка для скачивания станет доступной сразу после отключения Adblock!

Скачать