Gistrec

Поиск детей в матрице смежности [C++]

Apr 11th, 2017
255
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.07 KB | None | 0 0
  1. // Файл исходного кода
  2.  
  3. #include <cstdio>
  4. #include <iostream>
  5. #include <stdio.h>
  6.  
  7. void main() {
  8.     int j, i, n, k;
  9.     int a[10][10];
  10.  
  11.     list parent, child;
  12.     create2(&parent);
  13.     create2(&child);
  14.  
  15.     printf("\nWrite parent number: 0"); scanf_s("%d", &k);
  16.     add(&parent, k);
  17.  
  18.     // Создание матрицы
  19.     printf("\nWrite matrix resolution: 3"); scanf_s("%d", &n);
  20.     for (i = 0; i < n; i++) {
  21.         for (j = 0; j < n; j++) {
  22.             scanf_s("%d", &a[i][j]);
  23.         }
  24.     }
  25.  
  26.     printf("\nWritten matrix: \n");
  27.     for (i = 0; i < n; i++) {
  28.         for (j = 0; j < n; j++) {
  29.             printf_s("%d ", a[i][j]);
  30.         }
  31.         printf("\n");
  32.     }
  33.     while (!isEmpty(&parent)) {
  34.         // Перебор родителей
  35.         while (!isEmpty(&parent)) {
  36.             get(&parent, &k);
  37.             for (j = 0; j < n; j++) {
  38.                 if (a[j][k] == 1) {
  39.                     add(&child, j);
  40.                 }
  41.             }
  42.         }
  43.         // Выводим детишек :)
  44.         printChain(&child); printf("  ");
  45.         // Приравниваем детей к родителям и выводим
  46.         while (!isEmpty(&child)) {
  47.             get(&child, &k);
  48.             add(&parent, k);
  49.         }
  50.     }
  51.     getchar();
  52. }
  53.  
  54. ===============================================================================================
  55.  
  56. // Заголовочный файл
  57.  
  58. #include <cstdio>
  59. #include <iostream>
  60.  
  61. const int N = 10;
  62.  
  63. struct list {
  64.     int begin; // Позиция первого элемента в очереди (массиве)
  65.     int end; // Позиция последнего элемента в очереди (массиве)
  66.     int data[N];
  67. };
  68.  
  69. // Проверка на пустоту
  70. int isEmpty(list *q) {
  71.     //return (q->begin == 0) && (q->end == -1);
  72.     return ((q->begin - q->end) == 1);
  73. }
  74.  
  75.  
  76.  
  77.  
  78. // elem == приоритет
  79. int add(list *q, int elem) {
  80.     // Если очередь заполнена - проверяеи на 'ПСЕВДОПОЛНОСТЬ'
  81.     if (q->end == N - 1) {
  82.         if (q->begin != 0) {
  83.             int i;
  84.             for (i = 0; i <= (q->begin - q->end); i++) {
  85.                 q->data[i] = q->data[i + q->begin];
  86.             }
  87.             q->end = q->end - q->begin;
  88.             q->begin = 0;
  89.         }
  90.         else return 0;
  91.     }
  92.     // i - позиция в массиве, куда будем добавлять новый элемент
  93.     int i = q->begin;
  94.     while ((i <= q->end) && (elem >= q->data[i])) {
  95.         i++;
  96.     }
  97.     // От конца до i передвигаем все элементы вправо
  98.     for (int now = q->end; now >= i; now--) {
  99.         q->data[now + 1] = q->data[now];
  100.     }
  101.     // добавляем новый элемент на освободившемся месте
  102.     q->data[i] = elem;
  103.     q->end++;
  104.     return 1;
  105. }
  106.  
  107. // Получить первый элемент из очереди
  108. int get(list *q, int *elem) {
  109.     if (!isEmpty(q)) {
  110.         *elem = q->data[q->begin];
  111.         q->data[q->begin] = NULL;
  112.         q->begin++;
  113.         return 1;
  114.     }
  115.     return 0;
  116. }
  117.  
  118. void create2(list *P) {
  119.     P->begin = 0;
  120.     P->end = -1;
  121.     P->data[10];
  122. }
  123.  
  124. void printChain(list *q) {
  125.     int  data;
  126.     list Q;
  127.     create2(&Q);
  128.     while (!isEmpty(q)) {
  129.         get(q, &data);
  130.         printf("%d", data);
  131.         add(&Q, data);
  132.     }
  133.     while (!isEmpty(&Q)) {
  134.         get(&Q, &data);
  135.         add(q, data);
  136.     }
  137. }
Advertisement
Add Comment
Please, Sign In to add comment