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

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

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

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

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

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

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

методы ”

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

Дата сдачи: _____________

Подпись: _____________

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

Группа : 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

--> ЧИТАТЬ ПОЛНОСТЬЮ <--