Матрица инцидентности

Матрица I(G) размером n x m (n - число вершин, m - число ребер/дуг графа G), (i, j)-й элемент, которой равен 1, если вершина n_i инцидентна ребру e_ij в неориентированном графе или если n_i есть начало дуги e_j равен -1, если вершина n_i есть конец дуги e_j (только для ориентированных графов), и равен 0 в остальных случаях.

В данной задаче задается граф и строится его матрица инцидентности:

//Построение матрицы инцидентности#include <stdio.h>#include <stdlib.h>#include <string.h>#include <conio.h>#include <iostream.h>struct elem{ int num; /* Номер вершины */ int suns; /* Количество сыновей */ char str[20]; /* Строка с номерами сыновей */ elem *next; /* Указатель на следующую вершину */} *head, *w1, *w2;int connected(int i, int j){ int k; char *str1; w2 = head; if(i == j) return 0; for(k=1; k<i; k++) w2 = w2->next; if(strchr(w2->str, j)) return 1; return 0;}void main(){ int tops; int i,j,k,l; char *str1; clrscr(); printf("Введите количество вершин \n"); scanf("%d", &tops); head = (elem *)malloc(sizeof(elem)); head->num = 1; head->suns = 0; head->str[0] = '\0'; head->next = NULL; w1 = head; for(i=2;i<=tops;i++) { w2 = (elem *)malloc(sizeof(elem)); w2->num = i; w2->suns = 0; w2->str[0] = '\0'; w2->next = NULL; w1->next = w2; w1 = w2; } w1 = head; for(i=1; i<=tops; i++) { // clrscr(); printf("Введите количество путей из вершины %d\n", i); scanf("%d", &k); for(j=1; j<=k; j++) { printf("Введите связь %d\n", j); scanf("%d", &l); if((l<=0) || (l > tops)) { printf("Такой вершины нет, повторите попытку\n"); l = 0; j--; continue; } w1->str[w1->suns++] = l; w1->str[w1->suns] = '\0'; if(w1->suns == 49) { printf("Слишком много связей!"); exit(1); } } w1 = w1->next; } clrscr(); printf("\n\n Матрица инциндентности:\n"); for(i=1; i<=tops; i++) { printf("\n %d) ", i); for(j=1; j<=tops; j++) { printf("%d ", connected(i, j)); } } printf("\n\n Нажмите любую клавишу..."); getch();}

Структуры данных

Решение комбинаторных задач предполагает выделение структур сложного типа с их последующей реализацией средствами выбранного языка программирования. При этом структура данных может не зависеть от конкретных языковых конструкций (абстрактная структура данных).

Под структурой данных понимают совокупность элементов фиксированных типов и набор базисных операций, определяющих организацию и способ обработки данных.

Рассмотрим некоторые основные структуры данных.

Стеки

Стеком называется структура данных, загрузка или увеличение элементов для которой осуществляется с помощью указателя стека в соответствии с правилом LIFO (last-in, first-out - последним введен, первым выведен).

Указатель стека sp (stack pointer) содержит в любой момент времени индекс (адрес) текущего элемента, который является единственным элементом стека, доступным в данный момент времени для работы со стеком (для случая, когда указатель стека всегда задает ячейку, находящуюся непосредственно над его верхним элементом).