Quick Union Implementation in C

Question

#include<stdio.h> 
#include<stdlib.h> 
int *id,N; 

main() 
{ 
    FILE* file=fopen("a.txt","r"); 
    int i,p,q,c; 
    fscanf(file,"%d",&N); 

    id=(int *)malloc(N*sizeof(int)); 

    for(i=0;i<N;i++) 
     *(id+i)=i; 

    while(!feof(file)) 
    { 
     fscanf(file,"%d %d",&p,&q); 
     if(!connected(p,q)) 
      unn(p,q); 
    } 
    fclose(file); 
    c=1; 

    while(c==1) 
    { 
     scanf("%d %d",&p,&q); 
     printf("%d\nYes(1) or No(0) ",connected(p,q)); 
     scanf("%d",&c); 
    } 
} 

connected(int p,int q) 
{ 
    return((root(p))==(root(q))); 
} 

unn(int p,int q) 
{ 
    int j=root(q); 
    int i=root(p); 
    *(id+j)=i; 
} 

root(int i) 
{ 
    while(i!=(*(id+i))) 
     i=*(id+i); 
    return(i); 
} 

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

Быстрая находка была выполнена . без каких-либо хлопот, используя один и тот же файл «a.txt» лишь несколько настроек для этого кода в снаряженном GDB, он говорит:

«Программа получила сигнал SIGSEGV, сегментация Fault
0x08048729 в ​​к.т. (я = 134761) at ic: 47 "

Значение переменной" i "при каждом запуске составляет 134761, что не должно быть искренним e значения только от 1 до 11 в текстовом файле.
* Да или Нет для запроса пользователя.

Answer 1

ВСЕГДА проверяем результат fopen();

Answer 2

В корневой функции у вас есть:

i=*(id+i); 

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

Некоторые комментарии:

• пожалуйста, добавьте явные возвращающимся типы каждой функции :)
• , когда просят о проблеме, что компилятор сказал линии XX, пожалуйста, указать линию, я должен был рассчитывать :)

Приветствия

Answer 3

Последнее fscanf терпит неудачу, и вы не можете сказать. Посмотрите на этот выход из GDB

a.txt является

5 

(только что)

Когда мы отлаживать мы получаем Segfault, мы спрашиваем где это произошло, и она печатает вызов стек

(gdb) run 
Starting program: /home/guido/a.out 
warning: Could not load shared library symbols for linux-vdso.so.1. 
Do you need "set solib-search-path" or "set sysroot"? 

Program received signal SIGSEGV, Segmentation fault. 
0x0000000000400911 in root (i=4195888) at a.c:53 
53  while(i!=(*(id+i))) 
(gdb) where 
#0 0x0000000000400911 in root (i=4195888) at a.c:53 
#1 0x0000000000400889 in connected (p=0, q=4195888) at a.c:41 
#2 0x00000000004007cd in main() at a.c:23 
(gdb) 

main.c: 23

22   fscanf(file,"%d %d",&p,&q); 
23   if(!connected(p,q)) 
24    unn(p,q); 

Мы видим, что после этого fscanf p is 0 и q is 4195888 (он отличается от вашего прогона, это происходит с неопределенным поведением;). Это вызвано тем, что для чтения scanf не было номеров. Ваш while (!feof(file)) не будет работать, потому что, хотя мы еще не достигли конца файла, чисел больше нет (я думаю, мы могли бы «исправить» это, сканировав «% d% d \ n» в цикле и «% d \ n "в начале).

Более правильный способ был бы

22   if(2 == fscanf(file,"%d %d",&p,&q)) 
23    if(!connected(p,q)) 
24     unn(p,q); 

2 относится к спецификаторам формата 2. scanf и друзья возвращают количество согласованных элементов. Таким образом, мы обязательно работаем только с допустимым вводом. (Это не для меня, я думаю, он исправляет его полностью)

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

EDIT: Кстати, вы должны действительно объявить прототипы функций и указать типы возврата. Вот моя «чистка» вашего кода (http://pastebin.com/r0csiCyj). Также глобальные переменные являются злыми.