Блог

Я написал следующую программу на C.

 #include<stdio.h>
#include<stdlib.h>

struct stack{
    int *arr;
    int top;
};

struct stack* init(int size){
    struct stack *s=NULL;
    s=malloc(sizeof(struct stack));
    s->arr=malloc(sizeof(int) * (size));
    s->top=-1;
    return s;
}

void push(struct stack* t, int val){
      (t->top);
    t->arr[t->top]=val;
}

void pop(struct stack* t){
    if(t->top != -1)
        t->top--;
}

int peek(struct stack *t){
    if(t->top != -1)
        return t->arr[t->top];
    return -1;
}

int isEmpty(struct stack *t){
    if(t->top == -1)
        return 1;
    return 0;
}

int adjVisited(int n, int **g, int i){
    for(int j=0;j<n;j  ){
        if(g[i][j] == 1)
            return 0;
    }
    return 1;
}

void Euler(int v, int n, int **g, int e){
    struct stack *temp=init(e 2);
    struct stack *ans=init(e 2);
    push(temp, v);
    while(!isEmpty(temp)){
        int u=peek(temp);

        if(adjVisited(n, g, u)){
            push(ans, u);
            pop(temp);
        }
        else{
            for(int j=0;j<n;j  ){
                if(g[u][j] == 1){
                    push(temp, j);
                    g[u][j] = 0;
                    g[j][u] = 0;
                    break;
                }
            }
        }
    }
    free(temp->arr);
    free(temp);
    while(!isEmpty(ans)){
        printf("%d ", peek(ans));
        pop(ans);
    }
}

void addEdge(int n, int** g, int u, int v){
    g[u][v]=1;
    g[v][u]=1;
}

int main(){
    int n, e, x, y;
    printf("Enter number of nodes in the graphn");
    scanf("%d", amp;n);

    int **graph = (int **)calloc(n, sizeof(int *)); 
    for (int i=0; i<n; i  ) 
         graph[i] = (int *)calloc(n, sizeof(int));

    printf("Enter number of edges in the graphn");
    scanf("%d", amp;e);

    printf("Enter end vertices of the edge to be addedn");
    while(e--){
        scanf("%d %d", amp;x,amp;y);
        addEdge(n, graph, x, y);
    }
    
    Euler(0, n, graph, e);
    for(int i=0;i<n;i  )
        free(graph[i]);
    free(graph);
    return 0;
}
  

Valgrind выдает мне ошибку недопустимой записи и недопустимого чтения. Это первый раз, когда я сталкиваюсь с этой ошибкой. Из того, что я знаю об этом, это происходит всякий раз, когда я хочу записать данные в ячейку памяти, которая не была динамически выделена.

 ==4199== Memcheck, a memory error detector
==4199== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==4199== Using Valgrind-3.15.0 and LibVEX; rerun with -h for copyright info
==4199== Command: ./a.out
==4199== 
Enter number of nodes in the graph
6
Enter number of edges in the graph
6
Enter end vertices of the edge to be added
0 1
1 2
2 3
3 4
4 5
5 0
==4199== Invalid write of size 4
==4199==    at 0x109294: push (hier.c:31)
==4199==    by 0x109477: Euler (hier.c:75)
==4199==    by 0x1096D4: main (hier.c:114)
==4199==  Address 0x4a52bc4 is 0 bytes after a block of size 4 alloc'd
==4199==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==4199==    by 0x10923E: init (hier.c:24)
==4199==    by 0x1093AA: Euler (hier.c:60)
==4199==    by 0x1096D4: main (hier.c:114)
==4199== 
==4199== Invalid read of size 4
==4199==    at 0x1092F4: peek (hier.c:41)
==4199==    by 0x1093F2: Euler (hier.c:66)
==4199==    by 0x1096D4: main (hier.c:114)
==4199==  Address 0x4a52bc4 is 0 bytes after a block of size 4 alloc'd
==4199==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==4199==    by 0x10923E: init (hier.c:24)
==4199==    by 0x1093AA: Euler (hier.c:60)
==4199==    by 0x1096D4: main (hier.c:114)
==4199== 
==4199== Invalid write of size 4
==4199==    at 0x109294: push (hier.c:31)
==4199==    by 0x10941E: Euler (hier.c:69)
==4199==    by 0x1096D4: main (hier.c:114)
==4199==  Address 0x4a52c64 is 0 bytes after a block of size 4 alloc'd
==4199==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==4199==    by 0x10923E: init (hier.c:24)
==4199==    by 0x1093CC: Euler (hier.c:62)
==4199==    by 0x1096D4: main (hier.c:114)
==4199== 
==4199== Invalid read of size 4
==4199==    at 0x1092F4: peek (hier.c:41)
==4199==    by 0x10951A: Euler (hier.c:86)
==4199==    by 0x1096D4: main (hier.c:114)
==4199==  Address 0x4a52c78 is 20 bytes after a block of size 4 alloc'd
==4199==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==4199==    by 0x10923E: init (hier.c:24)
==4199==    by 0x1093CC: Euler (hier.c:62)
==4199==    by 0x1096D4: main (hier.c:114)
==4199== 

  

РЕДАКТИРОВАТЬ: я получаю эту ошибку при тестировании следующего ввода

 6 as number of vertices
9 as number of edges
0 1
1 2
2 3
3 4
4 5
5 0
0 2
2 4
0 4 as the edges of the graph
  

Кто-нибудь может помочь мне устранить эту ошибку?

Вы присваиваете количество ребер переменной e , в вашем примере e == 9 .

Затем у вас есть цикл while, в котором вы уменьшаете e при чтении по краям:

 while (e--)
{ ... }
  

После этого e будет -1 .

Вы вызываете Euler с e==-1 в качестве аргумента. Вы выделяете память в arr для -1 2 == 1 элементов, чего недостаточно для 9 ребер.

При втором вызове push вы пытаетесь записать индекс элемента, 1 в arr котором он не выделен. Таким образом, valgrind репостит то, что вы записываете размером 4, на адрес, который равен 0 байтам после блока размером 4.

Вы переполняете свои стеки. Добавьте некоторые записи в журнал push , и вы увидите, что это произойдет.