Advertisement
VladimirKostovsky

Хочется квакать

Nov 18th, 2023
1,039
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 7.50 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <locale.h>
  3. #include <stdlib.h>
  4.  
  5. // Константы для работы с графом
  6. #define MIN_N 2
  7. #define MAX_N 7
  8. #define FILENAME "input.txt"
  9.  
  10. // Функция для ввода размера графа с клавиатуры
  11. void inputGraphSize(int* n) {
  12.     printf_s("Введите количество вершин графа в диапазоне [%d; %d]: ", MIN_N, MAX_N);
  13.     scanf_s("%d", n);
  14. }
  15.  
  16. // Функция для проверки корректности размера графа
  17. int checkGraphSize(int n) {
  18.     if (n < MIN_N || n > MAX_N) {
  19.         printf_s("Ошибка: введенное значение n вне допустимого диапазона.\n");
  20.         return 1; // Возврат с ошибкой
  21.     }
  22.     return 0; // Все в порядке
  23. }
  24.  
  25. // Функция для создания матрицы смежности с клавиатуры
  26. void createAdjacencyMatrix(int n, int(*m1)[MAX_N]) {
  27.     printf_s("Матрица смежности c размерностью %d x %d\n", n, n);
  28.     for (int i = 0; i < n; i++) {
  29.         for (int j = i; j < n; j++) {
  30.             printf_s("m1[%d][%d] = ", i, j);
  31.             scanf_s("%d", &m1[i][j]);
  32.             m1[j][i] = m1[i][j];
  33.         }
  34.     }
  35. }
  36.  
  37. // Функция для чтения матрицы смежности из файла
  38. void readAdjacencyMatrixFromFile(int n, int(*m1)[MAX_N]) {
  39.     FILE* file;
  40.     if (fopen_s(&file, FILENAME, "r") != 0) {
  41.         printf_s("Ошибка открытия файла %s\n", FILENAME);
  42.         exit(1);
  43.     }
  44.  
  45.     for (int i = 0; i < n; i++) {
  46.         for (int j = i; j < n; j++) {
  47.             fscanf_s(file, "%d", &m1[i][j]);
  48.             m1[j][i] = m1[i][j];
  49.         }
  50.     }
  51.  
  52.     fclose(file);
  53. }
  54.  
  55. // Функция для вывода матрицы смежности на экран
  56. void printAdjacencyMatrix(int n, int(*m1)[MAX_N]) {
  57.     printf_s("Вывод матрицы смежности m1\n");
  58.     for (int i = 0; i < n; i++) {
  59.         for (int j = 0; j < n; j++) {
  60.             printf_s("%d\t", m1[i][j]);
  61.         }
  62.         printf_s("\n");
  63.     }
  64. }
  65.  
  66. // Функция для подсчета количества рёбер в графе
  67. int countEdges(int n, int(*m1)[MAX_N]) {
  68.     int k0 = 0;
  69.     for (int i = 0; i < n - 1; i++) {
  70.         for (int j = 0; j < n - 1; j++) {
  71.             k0 += m1[i][j];
  72.         }
  73.     }
  74.     return k0 / 2;
  75. }
  76.  
  77. // Функция для подсчета связей каждой вершины
  78. void countVertexConnections(int n, int(*m1)[MAX_N], int* sum) {
  79.     for (int j = 0; j < n - 1; j++) {
  80.         sum[j] = 0;
  81.         for (int i = 0; i < n - 1; i++) {
  82.             sum[j] += m1[j][i];
  83.         }
  84.     }
  85. }
  86.  
  87. // Функция для проверки связности графа
  88. int checkConnectivity(int n, int* sum) {
  89.     int p = 0;
  90.     for (int i = 0; i < n - 1; i++) {
  91.         if (sum[i] == 0) {
  92.             printf_s("Матрица несвязная\n");
  93.             p++;
  94.         }
  95.     }
  96.     return p;
  97. }
  98.  
  99. // Функция для проверки, является ли граф деревом
  100. int isTree(int k, int n, int p) {
  101.     return (k == n - 2 && p == 0);
  102. }
  103.  
  104. // Главная функция программы
  105. int main() {
  106.     setlocale(LC_ALL, "Russian");
  107.  
  108.     int n; // Переменная для хранения размера графа
  109.  
  110.      // Справка
  111.     printf_s("\nАлгоритм работы программы:\n");
  112.     printf_s("1. Пользователь выбирает источник данных: клавиатура или файл (input.txt).\n");
  113.     printf_s("2. В зависимости от выбора, программа либо запрашивает ввод размера графа и матрицы смежности с клавиатуры,\n");
  114.     printf_s("   либо считывает данные из файла input.txt.\n");
  115.     printf_s("3. Программа выводит матрицу смежности.\n");
  116.     printf_s("4. Программа выполняет проверку.\n");
  117.     printf_s("5. Память, выделенная под матрицы, освобождается.\n");
  118.     printf_s("\nАвтор: Павликова Екатерина, группа ПМИ-13\n");
  119.  
  120.     // Выбор источника данных (клавиатура или файл)
  121.     printf_s("Выберите источник данных (1 - клавиатура, 2 - файл): ");
  122.     int choice;
  123.     scanf_s("%d", &choice);
  124.  
  125.     // Обработка выбора пользователя
  126.     if (choice == 1) {
  127.         // Ввод размера графа с клавиатуры
  128.         inputGraphSize(&n);
  129.  
  130.         // Проверка корректности введенного размера графа
  131.         if (checkGraphSize(n)) {
  132.             return 1; // Возврат с ошибкой
  133.         }
  134.     }
  135.     else if (choice == 2) {
  136.         // Инициализация переменной n с использованием константного значения
  137.         printf_s("Чтение данных из файла %s\n", FILENAME);
  138.         FILE* file;
  139.         if (fopen_s(&file, FILENAME, "r") != 0) {
  140.             printf_s("Ошибка открытия файла %s\n", FILENAME);
  141.             return 1; // Возврат с ошибкой
  142.         }
  143.  
  144.         // Чтение размера графа из файла
  145.         fscanf_s(file, "%d", &n);
  146.         fclose(file);
  147.                 // Проверка корректности введенного размера графа
  148.         if (checkGraphSize(n)) {
  149.             return 1; // Возврат с ошибкой
  150.         }
  151.     }
  152.     else {
  153.         printf_s("Ошибка: неверный выбор источника данных.\n");
  154.         return 1; // Возврат с ошибкой
  155.     }
  156.  
  157.     // Выделение памяти под матрицу смежности
  158.     int(*m1)[MAX_N] = malloc(MAX_N * sizeof(int[MAX_N]));
  159.  
  160.     // Проверка успешности выделения памяти
  161.     if (m1 == NULL) {
  162.         printf_s("Ошибка: не удалось выделить память для матрицы смежности.\n");
  163.         return 1;
  164.     }
  165.  
  166.     // Ввод или чтение матрицы смежности в зависимости от выбора пользователя
  167.     if (choice == 1) {
  168.         createAdjacencyMatrix(n, m1);
  169.     }
  170.     else if (choice == 2) {
  171.         readAdjacencyMatrixFromFile(n, m1);
  172.     }
  173.  
  174.     // Вывод матрицы смежности на экран
  175.     printAdjacencyMatrix(n, m1);
  176.  
  177.     // Подсчет количества рёбер в графе
  178.     int k = countEdges(n, m1);
  179.     printf_s("В графе %d рёбер\n", k);
  180.  
  181.     // Массив для хранения связей каждой вершины
  182.     int sum[MAX_N - 1];
  183.  
  184.     // Подсчет связей каждой вершины
  185.     countVertexConnections(n, m1, sum);
  186.  
  187.     // Проверка связности графа
  188.     int p = checkConnectivity(n, sum);
  189.  
  190.     // Проверка, является ли граф деревом
  191.     if (isTree(k, n, p)) {
  192.         printf_s("m1 является деревом\n\n");
  193.     }
  194.     else {
  195.         printf_s("m1 не является деревом\n\n");
  196.     }
  197.  
  198.     // Освобождение выделенной памяти
  199.     free(m1);
  200.  
  201.     return 0;
  202. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement