1

Есть готовый код, нужно код разобрать на заголовочный и 2 исходника. Когда пытаюсь сделать это, в многих вариантах выдает ошибку.

dopcode.h

#pragma once
#ifndef DOPCODE_H
#define DOPCODE_H
int MaxFlow(int,int);
int FindPath(int,int);


const int MAX_VERTICES = 40;
int c[MAX_VERTICES][MAX_VERTICES];

#endif

dopcode.cpp

#include <iostream>
#include <memory.h>
#include <stdio.h>
#include <conio.h>
#include <Windows.h>
#include "dopcode.h"
using namespace std;

//const int MAX_VERTICES = 40;
const int infinity = 10000;
int NUM_VERTICES = 8;
int f[MAX_VERTICES][MAX_VERTICES];
//int c[MAX_VERTICES][MAX_VERTICES];
int Flow[MAX_VERTICES];
int Link[MAX_VERTICES];
int Queue[MAX_VERTICES];
int QP, QC;


int FindPath(int source, int target)
{

    QP = 0; QC = 1; Queue[0] = source;
    Link[target] = -1;
    int i;
    int CurVertex;
    memset(Flow, 0, sizeof(int) * NUM_VERTICES);
    Flow[source] = infinity;

    while (Link[target] == -1 && QP < QC)
    {
        CurVertex = Queue[QP];
        for (i = 0; i < NUM_VERTICES; i++)
            if ((c[CurVertex][i] - f[CurVertex][i]) > 0 && Flow[i] == 0)
            {
                Queue[QC] = i; QC++;
                Link[i] = CurVertex;
                if (c[CurVertex][i] - f[CurVertex][i] < Flow[CurVertex])
                    Flow[i] = c[CurVertex][i];
                else
                    Flow[i] = Flow[CurVertex];
            }
        QP++;
    }

    if (Link[target] == -1)
        return 0;
    CurVertex = target;

    while (CurVertex != source)
    {
        f[Link[CurVertex]][CurVertex] += Flow[target];
        CurVertex = Link[CurVertex];
    }
    return Flow[target];
}
int MaxFlow(int source, int target)
{
//    c[0][0] = 0; c[0][1] = 39; c[0][2] = 10; c[0][3] = 23; c[0][4] = 0; c[0][5] = 0; c[0][6] = 0; c[0][7] = 0;
//    c[1][0] = 0; c[1][1] = 0; c[1][2] = 0; c[1][3] = 0; c[1][4] = 25; c[1][5] = 0; c[1][6] = 0; c[1][7] = 0;
//    c[2][0] = 0; c[2][1] = 81; c[2][2] = 0; c[2][3] = 0; c[2][4] = 0; c[2][5] = 61; c[2][6] = 15; c[2][7] = 0;
//    c[3][0] = 0; c[3][1] = 0; c[3][2] = 20; c[3][3] = 0; c[3][4] = 0; c[3][5] = 0; c[3][6] = 0; c[3][7] = 0;
//    c[4][0] = 0; c[4][1] = 0; c[4][2] = 18; c[4][3] = 0; c[4][4] = 0; c[4][5] = 0; c[4][6] = 0; c[4][7] = 44;
//    c[5][0] = 0; c[5][1] = 0; c[5][2] = 0; c[5][3] = 0; c[5][4] = 16; c[5][5] = 0; c[5][6] = 0; c[5][7] = 53;
//    c[6][0] = 0; c[6][1] = 0; c[6][2] = 0; c[6][3] = 33; c[6][4] = 0; c[6][5] = 71; c[6][6] = 0; c[6][7] = 95;
//    c[7][0] = 0; c[7][1] = 0; c[7][2] = 0; c[7][3] = 0; c[7][4] = 0; c[7][5] = 0; c[7][6] = 0; c[7][7] = 0;

    memset(f, 0, sizeof(int) * 40 * 40);
    int MaxFlow = 0;
    int AddFlow;
    do
    {
        AddFlow = FindPath(source, target);
        MaxFlow += AddFlow;
    } while (AddFlow > 0);
    return MaxFlow;
}

main.cpp

#include <iostream>
#include <memory.h>
#include <stdio.h>
#include <conio.h>
#include <Windows.h>
#include "dopcode.h"

using namespace std;


//const int MAX_VERTICES = 40;
//const int infinity = 10000;
//int NUM_VERTICES;
//int f[MAX_VERTICES][MAX_VERTICES];
//int c[MAX_VERTICES][MAX_VERTICES];
//int Flow[MAX_VERTICES];
//int Link[MAX_VERTICES];
//int Queue[MAX_VERTICES];
//int QP, QC;

int main()
{
    setlocale(0, "");

    int source, target;

    printf("Chislo vershin v graph \n--> ");
//    int NUM_VERTICES = 8; printf("%d", NUM_VERTICES);

    printf("\n Znach istoka \n--> ");
    source = 0; printf("%d", source);

    printf("\n Znach stoka \n--> ");
    target = 7; printf("%d", target);
//    const int MAX_VERTICES = 40;
//    int c[MAX_VERTICES][MAX_VERTICES];
    //Матрица содержащая вместимость ребер:
    c[0][0] = 0; c[0][1] = 39; c[0][2] = 10; c[0][3] = 23; c[0][4] = 0; c[0][5] = 0; c[0][6] = 0; c[0][7] = 0;
    c[1][0] = 0; c[1][1] = 0; c[1][2] = 0; c[1][3] = 0; c[1][4] = 25; c[1][5] = 0; c[1][6] = 0; c[1][7] = 0;
    c[2][0] = 0; c[2][1] = 81; c[2][2] = 0; c[2][3] = 0; c[2][4] = 0; c[2][5] = 61; c[2][6] = 15; c[2][7] = 0;
    c[3][0] = 0; c[3][1] = 0; c[3][2] = 20; c[3][3] = 0; c[3][4] = 0; c[3][5] = 0; c[3][6] = 0; c[3][7] = 0;
    c[4][0] = 0; c[4][1] = 0; c[4][2] = 18; c[4][3] = 0; c[4][4] = 0; c[4][5] = 0; c[4][6] = 0; c[4][7] = 44;
    c[5][0] = 0; c[5][1] = 0; c[5][2] = 0; c[5][3] = 0; c[5][4] = 16; c[5][5] = 0; c[5][6] = 0; c[5][7] = 53;
    c[6][0] = 0; c[6][1] = 0; c[6][2] = 0; c[6][3] = 33; c[6][4] = 0; c[6][5] = 71; c[6][6] = 0; c[6][7] = 95;
    c[7][0] = 0; c[7][1] = 0; c[7][2] = 0; c[7][3] = 0; c[7][4] = 0; c[7][5] = 0; c[7][6] = 0; c[7][7] = 0;

    printf("\n Max potok: ");
    printf("%d", MaxFlow(source, target));
    return 0;
}

Так же есть изначальный код:

#include <memory.h>
#include <stdio.h>
#include <conio.h>
#include <Windows.h>

using namespace std;

const int MAX_VERTICES = 40;
int NUM_VERTICES; // число вершин в графе
const int infinity = 10000; // условное число обозначающее бесконечность
// f - массив содержащий текушее значение потока// f[i][j] - поток текущий от вершины i к j
int f[MAX_VERTICES][MAX_VERTICES];
// с - массив содержащий вместимоти ребер,
// т.е. c[i][j] - максимальная величину потока способная течь по ребру (i,j)
int c[MAX_VERTICES][MAX_VERTICES];
// набор вспомогательных переменных используемых функцией FindPath - обхода в ширину
// Flow - значение потока чарез данную вершину на данном шаге поиска
int Flow[MAX_VERTICES];
// Link используется для нахождения собственно пути
// Link[i] хранит номер предыдущей вешины на пути i -> исток
int Link[MAX_VERTICES];
int Queue[MAX_VERTICES]; // очередь
int QP, QC; // QP - указатель начала очереди и QC - число эл-тов в очереди
// поск пути по которому возможно пустить поток алгоритмом обхода графа в ширину// функция ищет путь из истока в сток по которому еще можно пустить поток,
// считая вместимость ребера (i,j) равной c[i][j] - f[i][j],
// т.е. после каждой итерации(одна итерация - один поик пути) уменьшаем вместимости ребер,// на величину пущеного потока

int FindPath(int source, int target) // source - исток, target - сток
{
    QP = 0; QC = 1; Queue[0] = source;
    Link[target] = -1; // особая метка для стока
    int i;
    int CurVertex;
    memset(Flow, 0, sizeof(int) * NUM_VERTICES); // в начале из всех вершин кроме истока течет 0
    Flow[source] = infinity; // а из истока может вытечь сколько угодно

    while (Link[target] == -1 && QP < QC)
    {
        // смотрим какие вершины могут быть достигнуты из начала очереди
        CurVertex = Queue[QP];
        for (i = 0; i < NUM_VERTICES; i++)
            // проверяем можем ли мы пустить поток по ребру (CurVertex,i):
            if ((c[CurVertex][i] - f[CurVertex][i]) > 0 && Flow[i] == 0)
            {
                //если можем, то добавляем i в конец очереди
                Queue[QC] = i; QC++;
                Link[i] = CurVertex; // указываем, что в i добрались из CurVertex
                // и находим значение потока текущее через вершину i
                if (c[CurVertex][i] - f[CurVertex][i] < Flow[CurVertex])
                    Flow[i] = c[CurVertex][i];
                else
                    Flow[i] = Flow[CurVertex];
            }
        QP++;// прерходим к следующей в очереди вершине
    }

    // закончив поиск пути
    if (Link[target] == -1)
        return 0; // мы или не находим путь и выходим
    // или находим:
    // тогда Flow[target] будет равен потоку который "дотек" по данному пути из истока в сток
    // тогда изменяем значения массива f для данного пути на величину Flow[target]
    CurVertex = target;

    while (CurVertex != source) // путь из стока в исток мы восстанавливаем с помощбю массива Link
    {
        f[Link[CurVertex]][CurVertex] += Flow[target];
        CurVertex = Link[CurVertex];
    }

    return Flow[target]; // Возвращаем значение потока которое мы еще смогли "пустить" по графу
}

// основная функция поиска максимального потока
int MaxFlow(int source, int target) // source - исток, target - сток
{
    // инициализируем переменные:
    memset(f, 0, sizeof(int) * MAX_VERTICES * MAX_VERTICES); // по графу ничего не течет
    int MaxFlow = 0; // начальное значение потока
    int AddFlow;
    do
    {
        // каждую итерацию ищем какй-либо простой путь из истока в сток
        // и какой еще поток мажет быть пущен по этому пути
        AddFlow = FindPath(source, target);
        MaxFlow += AddFlow;
    } while (AddFlow > 0);// повторяем цикл пока поток увеличивается
    return MaxFlow;
}

int main()
{
    setlocale(0, "");
    int source, target;

    printf("Число вершин в графе \n--> ");
    NUM_VERTICES = 8; printf("%d", NUM_VERTICES);

    printf("\n Значение истока \n--> ");
    source = 0; printf("%d", source);

    printf("\n Значение стока \n--> ");
    target = 7; printf("%d", target);

    //Матрица содержащая вместимость ребер:
    c[0][0] = 0; c[0][1] = 39; c[0][2] = 10; c[0][3] = 23; c[0][4] = 0; c[0][5] = 0; c[0][6] = 0; c[0][7] = 0;
    c[1][0] = 0; c[1][1] = 0; c[1][2] = 0; c[1][3] = 0; c[1][4] = 25; c[1][5] = 0; c[1][6] = 0; c[1][7] = 0;
    c[2][0] = 0; c[2][1] = 81; c[2][2] = 0; c[2][3] = 0; c[2][4] = 0; c[2][5] = 61; c[2][6] = 15; c[2][7] = 0;
    c[3][0] = 0; c[3][1] = 0; c[3][2] = 20; c[3][3] = 0; c[3][4] = 0; c[3][5] = 0; c[3][6] = 0; c[3][7] = 0;
    c[4][0] = 0; c[4][1] = 0; c[4][2] = 18; c[4][3] = 0; c[4][4] = 0; c[4][5] = 0; c[4][6] = 0; c[4][7] = 44;
    c[5][0] = 0; c[5][1] = 0; c[5][2] = 0; c[5][3] = 0; c[5][4] = 16; c[5][5] = 0; c[5][6] = 0; c[5][7] = 53;
    c[6][0] = 0; c[6][1] = 0; c[6][2] = 0; c[6][3] = 33; c[6][4] = 0; c[6][5] = 71; c[6][6] = 0; c[6][7] = 95;
    c[7][0] = 0; c[7][1] = 0; c[7][2] = 0; c[7][3] = 0; c[7][4] = 0; c[7][5] = 0; c[7][6] = 0; c[7][7] = 0;

    printf("\n Максимальный поток равен: ");
    printf("%d", MaxFlow(source, target));
    system("pause");
    return 0;
}

Ошибка: Ошибка

5
  • Не надо объявлять переменные в заголовочном файле
    – avp
    21 апр 2021 в 21:18
  • Раскомментируйте в dopcode.cpp int c[MAX_VERTICES][MAX_VERTICES];, а в заголовочном файле впереди этого массива напишите extern: extern int c[MAX_VERTICES][MAX_VERTICES];. А вообще, глобальные переменные - зло (в большинстве случаев). Лучше передавайте этот массив в функции как параметр.
    – Vladimir
    21 апр 2021 в 21:20
  • Глобальные переменные я использовал для попытки ликвидировать ряд других ошибок связанных опять же с этим массивом c. Если я не объявляю глобальные переменные, а оставляю их в dopcode.cpp, то вылезает ряд других ошибок ссылка.
    – Mkorny
    21 апр 2021 в 21:36
  • @Mkorny, перенесите c[][] в dopcode.cpp рядом с f[][] (т.е. тоже сделайте его глобальным)
    – avp
    21 апр 2021 в 22:44
  • @avp ссылка
    – Mkorny
    22 апр 2021 в 5:09

1 ответ 1

1

Смотрите простейший пример

t1.cpp

#include <stdio.h>
#include "t.h"

int main () {
  for (int i = 0; i < MAX_VERTICES; i++)
    for (int j = 0; j < MAX_VERTICES; j++)
      c[i][j] = i * j;

  modify();

  for (int i = 0; i < MAX_VERTICES; i++)
    for (int j = 0; j < MAX_VERTICES; j++)
      printf("%d %d   %d\n", i, j, c[i][j]);
         
  return puts("End") == EOF;
}

t2.cpp

#include <stdio.h>
#include "t.h"

int c[MAX_VERTICES][MAX_VERTICES];

void
modify ()
{
  for (int i = 0; i < MAX_VERTICES; i++)
    for (int j = 0; j < MAX_VERTICES; j++)
      c[i][j]++;
}

t.h

#ifndef _T_H_
#define _T_H_

void modify (void);

#define MAX_VERTICES 3

extern int c[MAX_VERTICES][MAX_VERTICES];

#endif // _T_H_

Т.е. все декларации глобальных массивов выносите в .h, определения глобальных массивов делаете в одном файле, а обращаться к ним теперь можете в другом.

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.