c++ - 从 C++ 转换为 C

Question

我试图将此代码从 C++ 转换为 C。它应该找到图的欧拉循环，但这在这里并不重要。我的问题是我不知道为什么会收到此编译错误。

C++ 代码:

#include <iostream>
#include <iomanip>

using namespace std;

// Typy danych

struct dlistEl
{
      dlistEl *next,*prev;
  int v;
};

// Zmienne globalne

int m,n;                        // Liczba krawędzi i wierzchołków
char **graf;                    // Dynamiczna macierz sąsiedztwa
bool * visited;                 // Tablica odwiedzin


void addC(int x, dlistEl *p)
{
  dlistEl * r;

  r = new dlistEl;
  r->v = x;
  r->next = p->next;
  if(r->next) r->next->prev = r;
  r->prev = p;
  p->next = r;
}

// Procedura usuwa z listy element wskazywany przez p
//---------------------------------------------------
void remC(dlistEl *p)
{
  if(p->next) p->next->prev = p->prev;
  if(p->prev) p->prev->next = p->next;
  delete p;
}

// Rekurencyjna funkcja dodająca do listy nowy cykl
// v - wierzchołek startowy i końcowy cyklu
// w - wierzchołek bieżący
// p - referencja do wskazania punktu wstawiania na liście
//--------------------------------------------------------
bool DFSaddCycle(int v, int w, dlistEl * & p)
{
  int u;

  visited[w] = true;            // Oznaczamy v jako odwiedzony
  addC(w,p);                    // Dodajemy w do cyklu
  p = p->next;                  // p wskazuje dodany element
  for(u = 0; u < n; u++)        // Przeglądamy sąsiadów w
    if(graf[w][u])
    {
      if(u == v)                // Cykl znaleziony?
      {
        addC(v,p);              // Zamykamy cykl na liście C
        do
        {
          graf[p->v][p->next->v] = 0; // Usuwamy krawędzie cyklu
          if(p->v == v) return true;
          p = p->prev;            } while(true);
      }
  if(!visited[u] && DFSaddCycle(v,u,p)) return true;
    }
  p = p->prev;                 // Z listy usuwamy w
  remC(p->next);
  return false;
}

// **********************
// *** PROGRAM GŁÓWNY ***
// **********************

int main()
{
  int i,j,v1,v2;
  dlistEl *C,*p;

  cin >> n >> m;                // Czytamy liczbę wierzchołków i krawędzi

  // Tworzymy tablice dynamiczne

  graf    = new char * [n];
  visited = new bool [n];
  for(i = 0; i < n; i++)
  {
    graf[i] = new char [n];
    for(j = 0; j < n; j++) graf[i][j] = 0;
  }

  // Odczytujemy definicje krawędzi grafu

  for(i = 0; i < m; i++)
  {
    cin >> v1 >> v2;
    graf[v1][v2] = 1;
  }

  C = new dlistEl;              // Tworzymy listę z wierzchołkiem v1
  C->v = v1;
  C->next = NULL;
  C->prev = NULL;

  for(p = C; p; p = p->next)    // Przeglądamy listę C
    for(i = 0; i < n; i++)      // Szukamy sąsiadów
      if(graf[p->v][i])
      {
        for(j = 0; j < n; j++) visited[j] = false;
        DFSaddCycle(p->v,i,p);  

  cout << endl;

  // Wyświetlamy zawartość listy C, czyli pełny cykl Eulera

  for(p = C; p; p = p->next) cout << setw(3) << p->v;

  cout << endl;

  // Usuwamy zmienne dynamiczne

  p = C;
  while(p)
  {
    p = C->next;
    remC(C);
    C = p;
  }

  for(i = 0; i < n; i++) delete [] graf[i];

  delete [] graf;
  delete [] visited;

  return 0;
}

这是 C 中的代码:

#include<stdio.h>
#include<stdlib.h>
#pragma warning(disable: 4996)

typedef enum { true = 1, false = 0 } bool;



struct dlistEl
{
    struct dlistEl *next, *prev;
    int v;
};



int m, n;                        // Liczba krawędzi i wierzchołków
char **graf;                    // Dynamiczna macierz sąsiedztwa
bool * visited;                 // Tablica odwiedzin

void addC(int x, struct dlistEl *p)
{
    struct dlistEl * r;

    r = (struct dlistEL *)malloc(sizeof(struct dlistEL));
    r->v = x;
    r->next = p->next;
    if (r->next) r->next->prev = r;
    r->prev = p;
    p->next = r;
}

void remC(struct dlistEl *p)
{
    if (p->next) p->next->prev = p->prev;
    if (p->prev) p->prev->next = p->next;
    free(p);
}

bool DFSaddCycle(int v, int w, struct dlistEl * & p)
{
    int u;

    visited[w] = true;            // Oznaczamy v jako odwiedzony
    addC(w, p);                    // Dodajemy w do cyklu
    p = p->next;                  // p wskazuje dodany element
    for (u = 0; u < n; u++)        // Przeglądamy sąsiadów w
        if (graf[w][u])
        {
            if (u == v)                // Cykl znaleziony?
            {
                addC(v, p);              // Zamykamy cykl na liście C
                do
                {
                    graf[p->v][p->next->v] = 0; // Usuwamy krawędzie cyklu
                    if (p->v == v) return true;
                    p = p->prev;
                } while (true);
            }
            if (!visited[u] && DFSaddCycle(v, u, p)) return true;
        }
    p = p->prev;                 // Z listy usuwamy w
    remC(p->next);
    return false;
}

int main()
{
  int i,j,v1,v2;
  struct dlistEl *C,*p;

  scanf("%d %d", n, m);         // Czytamy liczbę wierzchołków i krawędzi

  // Tworzymy tablice dynamiczne

  graf    =(char **)malloc(sizeof(char *)*n);
  visited =(bool *)malloc(sizeof(bool)*n);
  for(i = 0; i < n; i++)
  {
    graf[i] =(char *)malloc(sizeof(char)*n);
    for(j = 0; j < n; j++) graf[i][j] = 0;
  }

  // Odczytujemy definicje krawędzi grafu

  for(i = 0; i < m; i++)
  {
      printf("podaj def krawedzie grafu: \n");
      scanf("%d %d", v1, v2);
    graf[v1][v2] = 1;
  }

  C = (struct dlistEL *)malloc(sizeof(struct dlistEL));   
  C->v = v1;
  C->next = NULL;
  C->prev = NULL;

  for(p = C; p; p = p->next)    // Przeglądamy listę C
    for(i = 0; i < n; i++)      // Szukamy sąsiadów
      if(graf[p->v][i])
      {
        for(j = 0; j < n; j++) visited[j] = false;
        DFSaddCycle(p->v,i,p);  
      }

  printf("\n");

  // Wyświetlamy zawartość listy C, czyli pełny cykl Eulera

  for (p = C; p; p = p->next) printf("   %d", p->v);

  printf("\n");

  // Usuwamy zmienne dynamiczne

  p = C;
  while(p)
  {
    p = C->next;
    remC(C);
    C = p;
  }

  for(i = 0; i < n; i++) free(graf[i]);

  free(graf);
  free(visited);

  return 0;
}

当我尝试编译用 C 编写的程序时，它说:

error: invalid application of 'sizeof' to incomplete type 'struct dlistEL'|

error: expected ';', ',' or ')' before '&' token|

error: invalid application of 'sizeof' to incomplete type 'struct dlistEL'|

Answer 1

我认为，问题是

1. 在您的代码中

   bool DFSaddCycle(int v, int w, struct dlistEl * & p)
   

   您可能想将其更改为

   bool DFSaddCycle(int v, int w, struct dlistEl * p)
   

   C 中没有按引用传递。您只能使用它的指针。

2. 您输错了结构名称。

    malloc(sizeof(struct dlistEL));  //uppercase
   

   应该是

    malloc(sizeof(struct dlistEl));  //lowercase
   

3. 最后，do not cast the return value of malloc() .