Wskaźniki do struktur i funkcje je wykorzystujące

Question

Dzień dobry!

Wykonuję w języku C program dotyczący sortowania topologicznego grafu skierowanego przy użyciu kolejki. Graf niestety musi być reprezentowany za pomocą list sąsiedztwa.

Jedyną funkcją, która w moim programie musi operować na tych listach jest Wstawianie na koniec listy. Wiem, że muszę mieć tabelę list, gdzie lista[i] zawiera jako wyrazy numery wierzchołków j takich, że z j prowadzi krawędź skierowana do i.

Mam jednak problem z reprezentacją grafu w postaci struktury, wskaźnikami do tych struktur i tą funkcją.

Na wstępie chciałbym zaznaczyć, że jestem studentem matematyki, a nie informatyki, więc proszę powstrzymać się od komentarzy "Jak się dostałeś na te studia?" itd. W liceum teoretycznie miałem rozszerzoną informatykę, która wyglądała tak, że nauczyciel kazał nam na większości lekcji odrabiać prace domowe lub uczyć się do innych przedmiotów, programowania mieliśmy bardzo mało.

Na wykładzie lista jednokierunkowa była wykreowana tak:

typedef struct lista {
int elem;
struct lista *nast;
}lista, *plista;

W swoim programie wczytuję z klawiatury liczbę wierzchołków, a potem pytam użytkownika w podwójnej petli for czy istnieje krawędź z wierzchołka j do i ;jeśli tak, to wstawiam na koniec i-tej kolejki nowe pudełko, w ktorym elem=j;

//funkcja wstawiania na początek nie jest mi do niczego potrzebna//

void WstawNaKoniec ( int x, plista p)
{
p->elem = x;
p->nast = NULL;
} /*WstawNaKoniec*/

Tutaj zaczynaja się problemy - nie wiem, czy zadeklarować tablicę list i od razu po niej tablicę wskaźników do nich i w pętli for przypisywać i-ty wskaźnik do adresu i-tej listy, nie wiem czy to działa ale tak zrobiłem póki co.

Nie wiem tez jak z ta funkcja wstawiania na koniec listy, bowiem jak próbuję ja wywołać to mam w GCC (code blocks) błędy ze "nazwa wskaźnika" undeclared, 1st use in this function, a ja przecież wcześniej wyżej zadeklarowałem i listy i wskaźniki do nich.. W wersji tej funkcji z wykladu zmienna x byla jedynym parametrem a wskaźnik był deklarowany wewnątrz struktury i mallocowany, ale tu jest tablica wskaźnikow wiec nie dało się tak zrobić. Myślałem jeszcze, czy w funkcji nie zrobić tak jakby plista p[] i sam indeks i przekazywać jako parametr, ale tez były problemy przy tym czy malloc czy calloc nieważne jak nie udało się nigdy nic.

Mam deklarować te tablice poza funkcjami czy tylko ciągle na jakimś jednym wskaźniku wewnatrzfunkcyjnym operować - nie mam pojęcia. Cokolwiek zrobię tylko błędy warningi i 0 postępu i 0 rozwiązywania wątpliwości.

A jeśli mam te wskaźniki do każdej listy przypisać poza funkcjami to mam tradycyjnie te listy

stworzyć czy tym callociem bo nie wiem jaka jest różnica jeśli liczbę wierzchołków będę miał już wtedy daną, bo listy tworzę po tym wczytaniu.

Gdyby treść zadania umożliiwiała reprezentowanie tego grafu w postaci macierzy sąsiedztwa, a nie list, to byłoby to dla mnie 5x łatwiejsze zadanie.

Proszę w odpowiedziach nie pisać komentarzy typu "Skorzystaj z gotowej bibiliteki XXX i gotowej funkcji YYY", ja muszę wszystko napisać sam tutaj co związane z tym zadaniem.

Answer 1

Tablica list wydaje się dobrym pomysłem.
1. Na początku musisz utworzyć tablicę odpowiedniej długości (ilość wierzchołków) i umieścić w nich puste listy.
2. Następnie możesz zacząć dodawać elementy do odpowiednich list. Upewnij się, że prawidłowo obsługujesz listę pustą.
Trochę kodu do pomocy:

typedef struct lista {
    int elem;
    struct lista *nast;
} lista;

void WstawNaKoniec ( int x, lista *p)
{
    lista* ostatni = p;
    while (ostatni->nast) {
        ostatni = ostatni->nast;
    }
    ostatni->nast = (lista*)malloc(sizeof(lista));
    ostatni->nast->elem = x;
    ostatni->nast = NULL;
}

void InicjalizacjaTablicy(lista **wskaznik_na_tablice, int rozmiar) {
    int i;
    *wskaznik_na_tablice = (lista*)malloc(sizeof(lista)*rozmiar);
    for (i=0; i<rozmiar;i++)
        (*wskaznik_na_tablice)[i] = NULL;
}

void DodajKrawedz(int i, int j, lista *tablica) {
    if (tablica[j] == NULL) {
        tablica[j] = (lista*)malloc(sizeof(lista));
        tablica[j]->elem = i;
        tablica[i]->nast = NULL;
    } else {
        WstawNaKoniec(j, &tablica[i]);
    }
}

int main() {
    int rozmiar = 10;
    lista *tablica_list = NULL;
    inicjalizacjaTablicy(&tablica_list, rozmiar);
    DodajKrawedz(0, 1, tablica_list);
    return 0;
}

Uwaga: Kod może się nie skompilować, nie testowałem go.