Введение графа. Нахождение и выведение кратчайшего пути из одной вершины в другую

Министерство образования Республики Беларусь

Белорусский государственный университет информатики и электроники

Факультет компьютерных систем и сетей

Кафедра электронных вычислительных машин

Отчёт по учебной практике

Задача № 3

            Выполнил студент                                                                                                           Проверил

            группы 950501                                                                                                                Луцик Ю. А.

            Иванютенко А. А.                                                                                             _________________

Минск 2010

Условие поставленной задачи

Ввести граф. Найти и вывести кратчайший путь из одной вершины в другую.

Описание структур

Структура stack (служит для хранения вершин графа):

         int numb  – номер вершины графа;

          stack  *pre  –  указатель на стек типа stack;

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

1)  int count(stack *s) —  считает количество элементов стека s.

2)  int check(stack *head) — проверяет посредством просмотра стека, не было лиранее перехода на последнюю вершину.

3)  struct stack* miniway(stack *s, int numb) — функция поиска кратчайшего пути путёмрекурсивного перебора всех возможных переходов.

4)  void course (stack *h) — выводит на экран заданный путь.

5)  void output (stack *h) — функция выводит количество шагов и путь или извещает, что вершины не связаны.

6)  Функция stack *minway(stack *s , int numb)

Принимает указатель s на структуру типа stack и целочисленную переменную numb. Возвращает указатель  на структуру типа stack.

1.  Описание переменных: целочисленных i (переменная цикла), tmp_int (временная целочисленная), указателей на структуры stack: nw (новый элемент стека), min (указатель на вершину стека, содержащего кратчайший путь, инициализируется нулевым указателем), tmp_st (для временного хранения результата вызова функции minway).

2.  Выделение памяти для новой структуры nw и копирование в неё параметров функции (numb и s).

3.  Если текущая вершина (numb) — требуемая конечная (end), то вернуть nx.

4.  Если функция проверки check покажет, что в данную вершину (numb) уже проходили, то очистить память по nw и вернуть NULL.

5.  Начало цикла по переменной i, от 1 до n (количество вершин) + 1.

6.  Если текущая вершина (numb) связана с i-той (gt[numb][i] != 0), то

7.  tmp_st присвоить возврат функции fun со следующими параметрами: s = nnumb, v = i.

8.  Если tmp_st равен нулевому указателю, то продолжить выполнения цикла со следующей итерации.

9.  tmp_int присвоить возврат функции count с параметром tmp_st, т. е. Посчитать количество элементов в tmp_st.

10.  Если min равен нулевому указателю или tmp_min меньше числу шагов текущего минимального пути, то min присвоить значения tmp_st.

11.  Конец цикла, начатого в п. 5.

12.  Возврат значения min  и завершение функции.

7)  Функция int check(stack *head)

Принимает указатель head на структуру типа stack и целочисленную переменную numb. Возвращает ,1 если вершина уже содержится в стеке, иначе 0.

1.  Описание указателя s на структуру stack, который инициализируется значением head.

2.  Начало цикла: пока s ненулевой указатель выполнять

3.  Если значение поля numb по адресу s равно полю numb структуры по адресу head, то функция возвращает 1.

4.  Указателю s присваивается адрес структуры, следующей за той, на которую указывает s в данный момент.

5.  Конец цикла, описанного в п.2.

6.  Вернуть 0 и завершить функцию.

Блок-схемы

                                                  Функция minway

  Функция check

Кодпрограммы

#include <stdio.h>

#include <stdlib.h>

#include <conio.h>

#include <locale.h>

struct stack

{

    int numb;                       // номер вершины

    stack *pr;            // указатель на следующий элемент

};

int n;                                       // количество вершин

int end;                    // конечная вершина

int **m;                                 // матрица, хранящая связи вершин