[C] Znalezienie elementu w tablicy struktur

MlodyMatematykAmator
Użytkownik
Użytkownik
Posty: 55
Rejestracja: 23 mar 2019, o 17:45
Płeć: Mężczyzna
wiek: 19
Lokalizacja: Kraków
Podziękował: 16 razy

[C] Znalezienie elementu w tablicy struktur

Post autor: MlodyMatematykAmator » 30 gru 2019, o 19:03

Witam!

Mam pewien problem. Otóż w celach programu będącego swoistą grą o wielu polach (plansza gry nie musi być kwadratowa!) stworzyłem następującą strukturę:

Kod: Zaznacz cały

typedef struct pole {
    int x;
    int y;
    int c;
    int n;
} pole;
x i y to współrzędne pól szachownicy jak w układzie Gaussa, c to pewna informacja co się na danym polu znajduje. n to numer pola w tablicy, którą wkrótce stworzyłem:

Kod: Zaznacz cały

pole *plansza=NULL;
Tablicę tą uzupełniłem kolejnymi polami. Tak jak w układzie Gaussa każdy punkt ma unikatowe współrzędne, tak samo każde pole ma unikatowe współrzędne x i y w tym programie.

Mam następujący problem: znając zmienną 'n' danego pola łatwo mogę poznać jego współrzędne. Niech p - pewne pole.

Kod: Zaznacz cały

x=plansza[p.n].x
y=plansza[p.n].y
Ale czy jest jakiś sposób, abym poznał zmienną 'n' pola, którego zmienne 'x' i 'y' są mi znane w czasie stałym?

Pozdrawiam,
Damian
Rekrutacja Instytut Matematyczny, Uniwersytet Wrocławski (gif)

Afish
Moderator
Moderator
Posty: 2817
Rejestracja: 15 cze 2008, o 15:45
Płeć: Mężczyzna
Lokalizacja: Seattle, WA
Podziękował: 3 razy
Pomógł: 353 razy

Re: [C] Znalezienie elementu w tablicy struktur

Post autor: Afish » 1 sty 2020, o 00:34

Zrób słownik std::pair<int, int> -> int i wtedy masz czas stały.

Dudenzz
Użytkownik
Użytkownik
Posty: 90
Rejestracja: 8 mar 2009, o 18:21
Płeć: Mężczyzna
Pomógł: 19 razy

Re: [C] Znalezienie elementu w tablicy struktur

Post autor: Dudenzz » 7 sty 2020, o 15:40

Zrób słownik std::pair<int, int> -> int i wtedy masz czas stały.
Pamiętaj o tym, że STL nie jest biblioteką przeznaczoną dla języka C (tylko C++), więc jeżeli chciałbyś użyć słownika, zapewne chciałbyś wykonać jego własną implementację. Poza tym słownik w tym przypadku jest rozwiązaniem nadmiarowym, a w może się i okazać, że jest rozwiązaniem złym i utrudniającym optymalizację.

Struktura, którą chcesz zbudować, to plansza do gry, a zatem to właśnie ona - plansza, powinna być opisana jako programistyczna struktura. Z tego co widzę, przechowywane wartości (pola tej planszy) są typu liczby całkowitej, nie ma więc potrzeby używać złożonej struktury do opisu samego pola (gdyby wartość była złożona, wtedy sprawa ma się inaczej). A zatem należy zdefiniować strukturę przechowującą niezbędne pola.

Kod: Zaznacz cały

struct Board
{
        int *values;
        int height;
        int width;
};
typedef struct Board Board;
Należałoby napisać procedurę inicjalizującą taką planszę. W tej funkcji przypisujesz wysokość oraz szerokość zadanej planszy. Musisz również przypisać miejsce w pamięci dla tablicy przechowującej wartości pól tej planszy - miejsca potrzeba tyle, ile jest pól, razy miejsce potrzebne do przechowania jednego pola (czyli jednej liczby całkowitej). Czyli dla zadanej planszy \(\displaystyle{ B}\), typu pola \(\displaystyle{ P}\), wysokości \(\displaystyle{ h}\) oraz szerokości \(\displaystyle{ w}\), potrzebna pamięć planszy \(\displaystyle{ s(B)}\) będzie wyrażona równaniem:
\(\displaystyle{
s(B) = w \cdot h \cdot s(P)
}\)

Ja dla bezpieczeństwa wypełniam planszę zerami. Nie trzeba tego robić, ale należy mieć świadomość, że odnoszenie się do niewypełnionego miejsca w pamięci to zły pomysł. Całość w języku C wygląda tak:

Kod: Zaznacz cały

void InitializeBoard(Board *b, int w, int h)
{
        b->width = w;
        b->height = h;
        b->values = (int*)malloc(sizeof(int)*w*h);
        for(int i = 0; i<w*h; i++)
                b->values[i] = 0;
}
Definiuje również dwie proste metody - jedna pobiera wartość z planszy, druga zapisuje wartość na planszy. Obydwie metody mają STAŁY czas dostępu do pamięci. Aby obliczyć indeks \(\displaystyle{ i}\) pola na wysokości \(\displaystyle{ y}\) i szerokości \(\displaystyle{ x}\) dla planszy o całkowitej wysokości \(\displaystyle{ h}\) i całkowitej szerokości \(\displaystyle{ w}\) posłużę się wzorem:
\(\displaystyle{
i = y \cdot w + x < h \cdot w
}\)

Kod: Zaznacz cały

int GetValue(Board b,int x, int y)
{
        return b.values[y*b.width+x];
}
void SetValue(Board *b,int x, int y, int value)
{
        b->values[y*b->width+x] = value;
}
Pomocniczo definiuję metodę drukującą elementy planszy.

Kod: Zaznacz cały

void PrintBoard(Board b)
{
        for(int i = 0; i<b.height; i++)
        {
                for(int j = 0; j<b.width; j++)
                        printf("%d\t",b.values[i*b.width + j]);
                printf("\n");
        }
}
W końcu testuje działanie zaimplementowanych przeze mnie metod.

Kod: Zaznacz cały

int main()
{
        Board *b;
        b = (Board*)malloc(sizeof(Board*));
        InitializeBoard(b,5,6);
        PrintBoard(*b);
        SetValue(b,3,4,5);
        printf("------------------------\n");
        PrintBoard(*b);
        return 0;
}
Jeżeli chciałbyś przetestować to co napisałem, nie zapomnij o bibliotekach:

Kod: Zaznacz cały

#include <stdlib.h>
#include <stdio.h>
Model programu w którym "struktura planszy" wynika ze "struktury pola" jest modelem problematycznym, żeby nie powiedzieć złym - może z niego wynikać (jak u ciebie) na przykład liniowy czas dostępu do pamięci (co jest stanowczo niefektywne). Zauważyłem, że napisałeś, że zadana plansza nie musi być kwadratem. Mam podejrzenia (ze względu na mało precyzyjny język, którego używasz), że miałeś na myśli to, że plansza nie musi być prostokątem. Zaimplementowana przez mnie plansza kwadratem być nie musi, ale musi być prostokątem. Kiedy będziesz wykonywał własną implementację rozpocznij od definiowania planszy, a nie pola.

ODPOWIEDZ