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

МИНИСТЕРСТВО ОБЩЕГО И ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ. МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ АВИАЦИОННО-ТЕХНОЛОГИЧЕСКИЙ УНИВЕРСИТЕТ им. К.Э. ЦИОЛКОВКОГО КАФЕДРА ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ ПОЯСНИТЕЛЬНАЯ ЗАПИСКА к курсовой работе на тему: “Разработка алгоритмов и программ выполнения операций над последовательными и связанными представлениями структур данных” по курсу “Теория алгоритмов и вычислительных

методы” Руководитель: Авдошин С.М. Дата сдачи: _____________ Подпись: _____________ Студент: Лицентов Д.Б. Группа: 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) Если из какой-то вершины не