Advertisement
baadgeorge

Untitled

Mar 21st, 2021
56
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 10.17 KB | None | 0 0
  1. #include <iostream>
  2.  
  3. using namespace std;
  4.  
  5. const int n = 12; // кол-во вершин графа
  6.  
  7. // определение структуры для элемента стека
  8. struct cell
  9. {
  10. double value; // значение в элемента
  11. struct cell* next; // указатель на следующий элемент
  12. };
  13.  
  14. // определение имени list для типа cell
  15. typedef struct cell list;
  16.  
  17. // функция создания списка
  18. list* modStack(double val)
  19. {
  20. list* newStack; // создание указателя на новый список
  21. newStack = new list; // выделение памяти под новый список
  22. newStack->value = val; // запись в ячейку значения элемента списка
  23. newStack->next = NULL; // запись в ячейку указателя NULL на следующий элемент
  24. return(newStack);
  25. }
  26.  
  27. // функция вывода содержимого стека на экран
  28. void outputScreen(list* myStack)
  29. {
  30. int pos = 0; // индекс позиции элемента в стеке
  31. list* tmp = myStack; // указатель на стек
  32. if (tmp == NULL)
  33. {
  34. std::cout << "Стек пустой или не создан\n";
  35. }
  36. else
  37. {
  38. std::cout << "\n";
  39. do
  40. {
  41. pos++; // увеличение индекса позиции на 1
  42. std::cout << "-[" << pos << "]" << "(" << tmp->value << ")-"; // форматированный вывод элементов стека
  43. tmp = tmp->next; //присвоение tmp указателя на следующий элемент стека
  44. } while (tmp != NULL);
  45. }
  46.  
  47. std::cout << "\n";
  48. return;
  49. }
  50.  
  51.  
  52. // функция очистки стека
  53. void clearList(list** myStack)
  54. {
  55. list* tmp = *myStack; // указатель на первый элемент стека
  56. list* tmpNext = NULL; // указатель на следующий элемент стека
  57. if (tmp == NULL)
  58. {
  59. std::cout << "Невозможно очистить пустой или не созданный стек\n";
  60. }
  61. else
  62. {
  63. do
  64. {
  65. tmpNext = tmp->next; // присвоение указателя на следующий элемент
  66. delete tmp; // удаление указателя на текущий элемент
  67. tmp = tmpNext; // присвоение текущему указателю указателя на следующий элемент
  68. } while (tmp != NULL);
  69. *myStack = NULL; // обнуление указателя на стек
  70. std::cout << "Стек успешно очищен\n";
  71. }
  72.  
  73. return;
  74. }
  75.  
  76.  
  77.  
  78. // функция извлечения элемента стека на заданной позиции
  79. int PopStack(list** myStack)
  80. {
  81. int val;
  82. list* tmp = *myStack; // указатель на первый элемент стека
  83. list* tmpPrev = NULL; // указатель на предыдущий элемент стека
  84. int i = 1; // индексная переменная
  85.  
  86. if (tmp == NULL) // указатель на первый элемент стека NULL
  87. {
  88. std::cout << "Невозможно извлечь элемент из пустого или не созданного стека\n";
  89. }
  90. else
  91. {
  92. if (tmp->next == NULL) // указатель на следующий элемент NULL
  93. {
  94. clearList(myStack); // удаление всего стека из 1 элемента
  95. }
  96. else
  97. {
  98. do
  99. {
  100. i++; // увеличение счетчика на 1
  101. tmpPrev = tmp; // присвоение указателю на предыдущий элемент указателя на текущий элемент
  102. tmp = tmp->next; // присвоение указателю на текущий элемент указателя на следующий элемент
  103. } while (tmp->next != NULL);
  104. val = tmp->value;
  105.  
  106. tmpPrev->next = NULL; // указателю на следующий элемент для i-1 элемента присвоить указатель NULL
  107. delete tmp; // удаление указателя на извлеченный элемент
  108. }
  109. }
  110. return val;
  111. }
  112.  
  113. // функция добавления элемента в стек
  114. void PushStack(list** myStack, double val)
  115. {
  116. list* tmp = *myStack; // указатель на первый элемент стека
  117. list* tmpPrev = NULL; // указатель на предыдущий элемент стека
  118.  
  119.  
  120. if (tmp == NULL)
  121. {
  122. *myStack = modStack(val); // создание стека с текущим элементом
  123. std::cout << "Новый стек успешно создан\n";
  124. }
  125. else
  126. {
  127. do
  128. {
  129. tmpPrev = tmp; // присвоение указателю на предыдущий элемент указателя на текущий элемент
  130. tmp = tmp->next; // присвоение указателю на текущий элемент указателя на следующий элемент
  131. } while (tmp != NULL); // указатель на текущий элемент NULL
  132.  
  133. tmpPrev->next = modStack(val); // присвоение указателю предыдущего элемента на следующий элемент указателя на введенный элемент
  134. }
  135.  
  136. std::cout << "Новый элемент со значением " << val << " добавлен в конец стека\n";
  137. return;
  138. }
  139.  
  140.  
  141. // функция топологичесской сортировки графа
  142. void topological_s(int(*matrix)[n], int inf, list** next, int*& sorted)
  143. {
  144.  
  145. int i,j, k; // индексные переменные
  146. int u = 0; // номер рассматриваемой вершины
  147. int in_degree[n] = { 0 }; // массив входящих степеней вершин
  148.  
  149. // заполнение массива входящих степеней вершин
  150. for (i = 0; i < n; i++)
  151. {
  152. for (j = 0; j < n; j++)
  153. {
  154. if (matrix[i][j] != inf)
  155. {
  156. in_degree[j]++;
  157. }
  158. }
  159. }
  160.  
  161. for (i = 0; i < n; i++)
  162. {
  163. if (in_degree[i] == 0)
  164. {
  165. PushStack(next, i);
  166. }
  167. }
  168.  
  169. k = 0;
  170. // пока существую вершины с входящей степенью 0
  171. while (next != NULL)
  172. {
  173. u = PopStack(next); // выбор вершины для обработки из начала списка next
  174. sorted[k] = u; // запись вершины u в список sorted
  175. k++;
  176.  
  177. // поиск вершин с входящей степенью 0 после ослабления графа
  178. for (i = 0; i < n; i++)
  179. {
  180. if (matrix[u][i] != inf)
  181. {
  182. in_degree[i]--;
  183. if (in_degree[i] == 0)
  184. {
  185. PushStack(next, i);
  186. }
  187. }
  188. }
  189.  
  190. }
  191. return;
  192. }
  193.  
  194.  
  195. // поиск кратчайших путей
  196. int* dag_shortest_path(int(*matrix)[n], int s, int inf, int *sorted)
  197. {
  198. int* shortest = new int[n]; // массив весов кратчайших путей
  199. int* pred = new int[n]; // массив предыдущих вершин
  200. int i, j; // индексные переменные
  201.  
  202. // инициализация массива shortest и pred
  203. for (i = 0; i < n; i++)
  204. {
  205. pred[i] = -1;
  206. if (i != s-1) shortest[i] = inf;
  207. else shortest[i] = 0;
  208. }
  209.  
  210. // вычисление кратчайших путей из заданной вершины s
  211. for (i = 0; i < n; i++)
  212. {
  213. for (j = 0; j < n; j++)
  214. {
  215. if(matrix[sorted[i]][j] != inf) // если путь существует
  216. {
  217. if ((shortest[sorted[i]] + matrix[sorted[i]][j]) < shortest[j]) // новый вес пути меньше текущего
  218. {
  219. shortest[j] = shortest[sorted[i]] + matrix[sorted[i]][j]; // присвоить новый вес кратчайшего пути
  220. pred[j] = sorted[i];
  221. }
  222. }
  223. }
  224. }
  225. return shortest;
  226. }
  227.  
  228. int main()
  229. {
  230. setlocale(LC_ALL, "RUS");
  231.  
  232. int s = 0; // вершина для поиска критического пути
  233. int inf = 10000; // бесконечно большая величина
  234. int* shrt; // указатель на массив кратчайших путей
  235. int i = 0; // счетчик
  236. bool print_f = 1; // флаг печати доп. информации
  237. int* sorted = new int [n];
  238. list* next = NULL;
  239.  
  240.  
  241. int matrix[][n] =
  242. {
  243. { inf, 4, 21, 7, inf, 9, 13, inf, inf, inf, inf, inf },
  244. { inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf },
  245. { inf, inf, inf, 18, inf, inf, inf, inf, inf, inf, inf, inf },
  246. { inf, inf, inf, inf, 5, 31, inf, inf, inf, inf, inf, inf },
  247. { inf, inf, inf, inf, inf, inf, inf, inf, inf, 2, inf, inf },
  248. { inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf },
  249. { inf, inf, inf, inf, inf, inf, inf, inf, inf, 33, inf, inf },
  250. { inf, inf, inf, inf, inf, inf, 24, inf, inf, inf, inf, inf },
  251. { inf, inf, inf, inf, inf, inf, inf, 36, inf, inf, inf, inf },
  252. { inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, 16, 29 },
  253. { inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, 14 },
  254. { inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf }
  255. };
  256.  
  257. cout << "Введите начальную вершину " << endl;
  258. cin >> s; // исходная вершина
  259.  
  260. // форматированный вывод массива, возвращаемого топологической сортировкой
  261. cout << "Линейный список вершин графа возвращаемый топологической сортировкой: " << endl;
  262. for (i = 0; i < n; i++)
  263. {
  264. cout << sorted[i] + 1 << " ";
  265. }
  266.  
  267. topological_s(matrix, inf, &next, sorted);
  268.  
  269. shrt = dag_shortest_path(matrix, s, inf, sorted);// массив кратчайших путей из вершины s
  270.  
  271.  
  272.  
  273. cout << "\n\n";
  274.  
  275. // форматированный вывод массива кратчайших путей
  276. for (i = 0; i < n; i++)
  277. {
  278. if (shrt[i] == inf)
  279. {
  280. cout << "(" << s << ", " << i + 1 << ") не существует "<< endl;
  281. }
  282. else
  283. {
  284. cout << "(" << s <<", "<< i + 1<< ") = " << shrt[i] << endl;
  285. }
  286. }
  287. cout << endl;
  288.  
  289. print_f = 0; // смена флага печати доп. информации
  290.  
  291. system("pause");
  292.  
  293. }
  294.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement