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

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

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

 

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

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

 

 

 

 

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

 

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

 

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

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

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

 

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

методы

 

 

 

 

 

 

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

Дата сдачи: _____________

 

Подпись: _____________

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

 

 

Группа: 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 нолей.

 

Формат печати результатов работы программы представлен в следующем формате:

Даны неориентированные графы X и Y без кратностей.

Для каждого графа задаем номера вершины смежности с данной.

Граф X (в ЭВМ в последовательном представлении):

1 : X11 X12 ... X1k1

2 : X21 X22 ... X2k2

...

N : XN1 XN2 ... XNkN

Граф Y (в ЭВМ в связанном представлении):

1 : Y11 Y12 ... Y1k1

2 : Y21 Y22 ... Y2k2

...

N : YN1 YN2 ... YNkN

Над графами выполняется операция разности двумя способами

с получением нового графа Z (в связанном представлении):

1 : Z11 1,Z12 ... Z1k1

2 : Z21 Z22 ... Z2k2

...

N : ZN1 ZN2 ... ZNkN

И исправлением старого графа X (в последовательном представлении):

1 : X11 X12 ... X1k1

2 : X21 X22 ... X2k2

...

N : XN1 XN2 ... XNkN

Кол-во вершин, кол-во дуг графа X, кол-во дуг графа Y

и кол-во времени, затраченного на вычисление разности X и Y:

N MX MY T

где T - кол-во времени, затраченного на вычисление разности X и Y

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

MX - кол-во дуг в графе X

MY - кол-во дуг в графе Y

Страницы: 1, 2, 3, 4



2012 © Все права защищены
При использовании материалов активная ссылка на источник обязательна.