Panel użytkownika
Nazwa użytkownika:
Hasło:
Nie masz jeszcze konta?

[C] Przeszukiwanie grafu , problem z działaniem programu

Ostatnio zmodyfikowano 2017-06-01 19:36
Autor Wiadomość
baronsob
Temat założony przez niniejszego użytkownika
[C] Przeszukiwanie grafu , problem z działaniem programu
» 2017-06-01 17:58:55
Cześć, mam do zrobienia pewien program z tworzeniem i przeszukiwaniem grafu jako list sąsiedztwa. Wyszło mi na razie takie coś, byłbym wdzięczny jeśli ktoś pomógłby mi z błędami. Nie ma błędów przy kompilacji, tylko program nie działa jak powinien i się wyłącza. Mam na myśli, że pod odpaleniu DFS program się zawiesza.

C/C++
typedef struct nodeTAG {
    int data;
    struct nodeTAG * next;
} nodeT;

typedef struct listTAG {
    nodeT * front;
    nodeT * end;
} listT;

void listinit( listT * plist )
{
    plist->front = NULL;
    plist->end = NULL;
}

int isempty( listT * plist )
{
    if( plist->front = NULL )
         return 1;
    else
         return 0;
   
}

void addfront( listT * plist, int * x )
{
    nodeT * temp;
    temp =( nodeT * ) malloc( sizeof( nodeT ) );
    temp->data = x;
    if( plist->front == NULL ) {
        temp->next = NULL;
        plist->front = temp;
        plist->end = temp;
    }
    else {
        temp->next = plist->front;
        plist->front = temp;
    }
}

void addend( listT * plist, int x )
{
    nodeT * temp;
    temp =( nodeT * ) malloc( sizeof( nodeT ) );
    temp->data = x;
    if( plist->front == NULL ) {
        temp->next = NULL;
        plist->front = temp;
        plist->end = temp;
    }
    else {
        temp->next = NULL;
        plist->end->next = temp;
        plist->end = temp;
    }
}

void removefront( listT * plist, int * x )
{
    if( isempty( plist ) == 0 ) {
        nodeT * temp;
        * x = plist->front->data;
        temp = plist->front;
        plist->front = temp->next;
        free( temp );
    }
}

void displist( listT * plist )
{
    nodeT * temp;
    if( isempty( plist ) == 0 ) {
        temp = plist->front;
        printf( "zawartosc listy: " );
        printf( "%d", temp->data );
        while( temp->next != NULL ) {
            temp = temp->next;
            printf( "%d", temp->data );
        }
        printf( " \n " );
    }
    else
         printf( "lista pusta" );
   
}

void destroylist( listT * plist )
{
    nodeT * temp;
    while( plist->front != plist->end ) {
        temp = plist->front;
        plist->front = temp->next;
        free( temp );
    }
    if( plist->front != NULL ) {
        temp = plist->front;
        plist->front = NULL;
        plist->end = NULL;
        free( temp );
    }
}
int * tabzaznaczen;
listT * tabwierz;

void DFS( int wierz )
{
    listT * Stos;
    nodeT * p;
    listinit( Stos );
    addfront( Stos, & wierz );
    tabzaznaczen[ wierz ] = 1;
    while( Stos ) {
        removefront( Stos, & wierz );
        printf( "%d\n", wierz );
        for( p =( tabwierz[ wierz ] ).front; p; p = p->next ) {
            if( !tabzaznaczen[ p->data ] ) {
                addfront( Stos, &( p->data ) );
                tabzaznaczen[ p->data ] = 1;
            }
        }
    }
}

int main()
{
    int lwierzcholkow; //liczba wierzcholkow
    int lkrawedzi; //liczba krawedzi
    printf( "Ile jest wierzcholkow?\n" );
    scanf( "%d", & lwierzcholkow ); //pyta i wczytuje z klawiatury ile wierzcholkow
    printf( "Ile jest krawedzi?\n" );
    scanf( "%d", & lkrawedzi ); //pyta i wczytuje z klawiatury ile krawedzi
    tabzaznaczen =( int * ) malloc( lwierzcholkow * sizeof( * tabzaznaczen ) );
    tabwierz =( listT * ) malloc( lwierzcholkow * sizeof( * tabwierz ) ); //alokuje tablice dynamiczna o dlugosci = ilosci wierzcholkow
    for( int k = 0; k < lwierzcholkow; k++ ) {
        tabzaznaczen[ k ] = 0;
        listinit( & tabwierz[ k ] ); //inicjalizuje listy sasiedzkie oraz ustawiam tablicę zaznaczeń na 0
    }
   
    printf( "Dostepne wierzcholki to:\n" );
    for( int j = 0; j < lwierzcholkow; j++ ) {
        printf( "%d \n", j );
    } //wyswietlam wiercholki ktore moze wykorzystac uzytkownik do tworzenia grafu
    for( int i = 1; i < lkrawedzi + 1; i++ ) {
        int wierz1;
        int wierz2;
       
        printf( "Z czym laczy sie krawedz %d ? Napisz po spacji\n", i );
        scanf( "%d %d", & wierz1, & wierz2 ); //wczytuje z klawiatury z czym ma sie laczyc dana krawedz
        if( wierz1 > lwierzcholkow - 1 || wierz2 > lwierzcholkow - 1 ) {
            printf( "Bledne wierzcholki" );
            return 0;
        }
        else {
            addend( & tabwierz[ wierz1 ], wierz2 );
            addend( & tabwierz[ wierz2 ], wierz1 ); //konstruje graf dodajac odpowiednie wiercholki na koniec list
        }
    }
    int ktory;
    int start;
    printf( "Dla DFS wcisnij '1' a dla BFS wcisnij '2' " );
    scanf( "%d", & ktory );
    printf( "Z ktorego wierzcholka zaczac?" );
    scanf( "%d", start );
    if( ktory = 1 && start < lwierzcholkow ) {
        DFS( start );
    }
    else {
        printf( "Bledne dane" );
        return 0;
    }
   
    return 0;
}
P-161938
Monika90
» 2017-06-01 18:22:29
isempty powinno wyglądać tak:
C/C++
int isempty( const listT * plist )
{
    return plist->front == NULL;
}
nie oznacza to, że nie ma innych błędów.
P-161939
baronsob
Temat założony przez niniejszego użytkownika
» 2017-06-01 19:36:00
Ok, zmieniłem i teraz działa np. wyświetlanie listy poprawnie ale DFS nadal nie działa więc błąd może być w funkcji DFS gdzieś, byłbym wdzięczny za pomoc w odszukaniu i poprawieniu.
P-161945
« 1 »
  Strona 1 z 1