Узел существует, но ребра неправильны в CSR - PullRequest
Новая
       71

Узел существует, но ребра неправильны в CSR

0 голосов
/ 11 января 2020

Я пытаюсь создать график в формате CSR (сжатые разреженные строки), читая узлы / ребра из таблицы, которая читается из файла. Это происходит с использованием трех массивов: один в качестве хэш-карты, которая переводит различные узлы в более простые числа для экономии места, один для узлов и один для ребер. Проблема в том, что когда я набираю число, чтобы найти, оно печатает «найдено», но оно печатает края правильно или совершенно неправильно, или ничего, и я понятия не имею, что вызвало это. Файл выглядит так: 

Nodes Edges
30    1412
30    3352
30    5254
30    5543
30    7478
3     28
3     30
3     39
3     54
3     108
3     152
3     178
3     182
3     214
3     271
3     286

А код такой: 

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

int hashdoublesize(int** hash,int nodes){
    int* new_array=malloc(nodes*2*sizeof(int));
    if(new_array==NULL){
        printf("Error allocating memory\n");
        abort();
    }

    for(int i=0;i<nodes;i++){
        new_array[i]=(*hash)[i];
    }
    nodes*=2;
    free(*hash);
    *hash=new_array;
    return nodes;
}

typedef struct {
    int start;
    int end;   
} path;

int cmp(const void *a,const void *b){
    int l=((path*)a)->start;
    int r=((path*)b)->start;

    if(l>r)
        return 1;
    if(l<r)
        return -1;
    if(l==r)
        return 0;
}

int doublesize(path** array,int n){
    path* new_array=malloc(n*2*sizeof(path));
    if(new_array==NULL){
        printf("Error allocating memory\n");
        abort();
    }

    for(int i=0;i<n;i++){
        new_array[i]=(*array)[i];
    }
    free(*array);
    *array=new_array;
    n*=2;
    return n;
}


int main()
{
    int maxsize=10;
    int test;
    path* array=malloc(maxsize*sizeof(path));
    if(array==NULL) {
        printf("Error allocating memory\n");
        abort();
    }

    FILE* fd=fopen("File.txt","r");
    if(fd==NULL) {
        printf("Error opening file\n");
        abort();
    }
    char buff[200];
    int counter=0;

    char c;
    while(fgets(buff,200,fd)) {
        c=buff[0];
        if(c=='#') {
            continue;
        }
        sscanf(buff,"%d%d",&array[counter].start,&array[counter].end);
        counter++;
        if(counter==maxsize){
             maxsize=doublesize(&array,maxsize); 
        }
    }
    int i;
    maxsize=counter;
    counter=0;
    qsort(&array[0],maxsize,sizeof(path),cmp);

    counter=0;
    int nodes=10;
    int* hash=malloc(nodes*sizeof(int));
    if(hash==NULL){
        printf("Error allocating memory\n");
    }
    for(i=0;i<maxsize;i++){
        if(hash[counter]==array[i].start){
            continue;
        }
        hash[counter]=array[i].start;
        counter++;
        if(counter==nodes){
            nodes=hashdoublesize(&hash,nodes);
        }
    }

    int* arraynodes=malloc(nodes*sizeof(int));
    int* arrayedges=malloc(maxsize*sizeof(int));
    if(arraynodes==NULL||arrayedges==NULL){
        printf("Error allocating memory\n");
        abort();
    }
    counter=1;
    arraynodes[0]=0;
    for(i=0;i<maxsize;i++){
        arrayedges[i]=array[i].end;
        if(array[i].start!=array[i+1].start){
            arraynodes[counter]=i;
            counter++;
        }
    }

    int x;
    printf("give number to search: "); 
    scanf("%d",&x);
    for(i=0;i<nodes;i++){
        if(x==hash[i]){
            printf("found \n");
            break;
        } 
    }
    if(i==nodes){
        printf("not found \n");
        abort();
    }

    free(arraynodes);
    free(arrayedges);
    free(hash);
    fclose(fd);
    free(array);
    return 0;
}
...