В чем причина ошибки сегментации? - PullRequest
Новая
       1

В чем причина ошибки сегментации?

2 голосов
/ 18 октября 2019

Я не могу отладить следующий код в любом отладчике, так как он показывает: «Во время запуска программы закончилась ошибка сегментации SIGEGV»

Этот код позволяет определить, является ли график двудольным или нет. 

#include <stdlib.h>
#define ll long long

ll queue[1000000000];
ll last=0;
ll top=0;

int qempty()
{
    if(top==last) return 1;
    else return 0;
}

void emptyq()
{
    top=0;
    last=0;
}
void enqueue(long long x)
{
    queue[top++] = x;
}
void dequeue()
{
    queue[last++];
}

Здесь я определил очередь. Ниже приведены функции для графика. 

struct node
{
    ll vertex;
    struct node* next;
};

struct node* createNode(ll v)
{
    struct node *newnode = malloc(sizeof(struct node));
    newnode->vertex = v;
    newnode->next = NULL;
    return newnode;
}

struct Graph
{
    ll numVertices;
    struct node** adjLists;
};

struct Graph *createG (ll vertices)
{
    struct Graph *G = malloc(sizeof(struct Graph));
    G->numVertices = vertices;
    G->adjLists = malloc(vertices*sizeof(struct node*));
    for(int i=0;i<vertices;i++) G->adjLists[i]=NULL;
    return G;
}

void add(struct Graph* G, ll src, ll dest)
{
    struct node* newnode = createNode(dest);
    newnode->next = G->adjLists[src];
    G->adjLists[src] = newnode;

    newnode = createNode(src);
    newnode->next = G->adjLists[dest];
    G->adjLists[dest] = newnode;

}

Это функция для проверки границ между одним и тем же слоем поиска в ширину. 

ll BU(struct Graph *G, ll src, ll *color)
{ 
    color[src] = 1;
    emptyq();
    enqueue(src);
    while (qempty); 
    { 
        ll u = queue[last];
        dequeue;
        struct node *y = G->adjLists[u];
        while(y)
        { 
            if(color[y->vertex]==-1)
            { 
                color[y->vertex] = 1-color[u]; 
                enqueue(y->vertex);
            } 
            else if (color[y->vertex] == color[u]) return 0;

            y=y->next;
        }
    } 
    return 1; 

}

ll B(struct Graph *G) 
{ 
    ll x = G->numVertices;
    ll *color = malloc(x*sizeof(long long));
    for (ll i = 0; i < x; ++i) color[i] = -1; 

    for (ll i = 0; i < x; i++) 
    if (color[i] == -1) 
        if (BU(G,i,color)==0) 
        return 0; 

    else  return 1; 
}

Это основная функция. Я добавил точку останова в самой первой строке основной функции, но она отказалась продолжать. 

int main()
{
    ll t;
    scanf("%lld",&t);
    printf("%lld",t);
    while(t--)
    {
        ll V,E;
        scanf("%lld %lld",&V,&E);
        printf("%lld %lld",V,E);
        struct Graph *G = createG(V);
        while(E--)
        {
            ll x,y;
            scanf("%lld %lld",&x,&y);
            add(G,x,y);
        }
        if(B(G)==1) printf("Yes\n");
        else printf("No\n");

    }
    return 0;
}

Ответы [ 2 ]

5 голосов
/ 18 октября 2019

Вы можете уменьшить размер этого: 

ll queue[1000000000];

до более разумного значения, скажем 1024.

0 голосов
/ 18 октября 2019

Максимальный размер статически распределенных данных процесса обычно невелик. Это неотъемлемая проблема сопоставления адресного пространства, точного размера, если зависит от системы, но на практике не ожидайте больше, чем несколько мегабайт.

Вы можете сделать один из них:

  • выделять память динамически
  • использовать меньший статический блок памяти
  • вы можете изменить - аналогично сильно зависящие от платформы - настройки, которые увеличивают исходный размер статических данных.
...