Языки программирования

Титульный лист

Оглавление

Введение        3

1.        Исходные данные        4

2. Алгоритм решения задачи        6

3. Листинг программы        8

4. Тестирование        17

Заключение        23

Список литературы        24

Введение

Цель курсовой работы по дисциплине «Языки программирования» состоит в закреплении и углублении знаний и навыков, полученных при изучении дисциплины.

Курсовая работа предполагает выполнение задания повышенной сложности по проектированию, разработке и тестированию программного обеспечения, а также оформлению сопутствующей документации.

Для достижения поставленной цели нужно выполнить следующие задачи:

• изучить алгоритмом согласно варианту задания;
• описать данный алгоритм;
• в соответствии с вариантом написать и отладить на компьютере программу;
• привести контрольную распечатку;
• оформить отчет.

1. Исходные данные

Задание № 47.

Алгоритм: Вывести на экран все существующие пути в ациклическом орграфе.

Способ представления: список смежности.

Для решения поставленной задачи с помощью средства отрисовки графов yEd Graph Editor были созданы 3 графа. Первый граф содержит 8 вершин и 9 ребер, в 2 графе 15 вершин и 17 ребер, в третьем графе 20 вершин и 21 ребро. Изоюражения графов представлены на рисунках 1 – 3.

[pic 1]

Рисунок 1. Граф 1

[pic 2]

Рисунок 2. Граф 2

[pic 3]

Рисунок 3. Граф 3

Полученные графы сохранены в двух форматах:

GraphML – язык описания (иногда упоминается как отдельный формат файлов) графов на основе XML.

Trivial Graph Format («простой формат графов», сокр. TGF) – простой формат файлов, основанный на тексте, для описания графов.

Для графа 1 необходимо подтвердить полученный результат вручную поэтапно показав, как был получен именно этот результат.

Для графов 2 и 3 нужно привести скриншот работы программы. Необходимо, используя граф 2 и 3, показать наиболее сложные с точки зрения алгоритма случаи работы программы.

2. Алгоритм решения задачи

Для решения поставленной задачи необходимо выполнить следующие шаги:

1. считать данные о графе из файла формата TGF;
2. заполнить по полученным данным список смежности графа и массив с названиями вершин;
3. написать функцию поиска всех путей в графе;
4. написать функции добавления вершины;
5. написать функции добавления ребра;
6. написать функцию вывода данных на экран.

Разработанная программа представляет собой консольное приложение. Для диалога с пользователем было создано меню. Внешний вид представлен на рис.4.

[pic 4]

Рисунок 4. Меню программы

Для представления графа с помощью списка смежности были созданы две структуры:

- для узлов списка смежности (входит ребро):

typedef struct node

- для заголовоков списка смежности

typedef struct graph_node

Назначение переменных

graph_node *graph – список смежности

int *vertex – массив для названий(номеров) вершин

int N – количество вершин в графе

ifstream f("g1.tgf") – файловая переменная для считывания  данных из файла

int a,b – для индексов элементов списка смежности

int c – для конвертирования строки в число

string s,s1 – для считывания строк из файла

int k=0,pos – k -индекс массива,pos-позиция символа 'v'

int m – выбор действия в меню

int name – номер вершины

int start– начальная вершина

int finish – конечная вершина

Описание функций

void printGraph(graph_node g[ ]) – вывод на экран списка смежности, в качестве параметра передается список смежностей