Struktury i Abstrakcyjne Typy Danych

[The Strokes]

Oh no
29 different attributes
And only seven that you like, uh oh
20 ways to see the world, oh oh
Or 20 ways to start a fight

The Strokes, “You Only Live Once”

Linki:

Struktury

Jak definiujemy i korzystamy z struktur?

struct point { /* „point” to tzw. etykietka struktury */
  int x;
  int y;
};             /* ważny średnik */

struct point maxpt = { 8, 16 };
struct point minpt;
minpt.x = 0;  minpt.y = 2;

Zagnieżdżone struktury:

struct rect {
  struct point ll;
  struct point ur;
}

struct rect screen;
screen.ll.x = 16;

Czasami definując strukturę korzystamy z typedef:

typedef struct point {
  int x;
  int y;
} point_t;

point_t maxpt;
maxpt.x = 32; maxpt.y = 64;

Ale częściej definujemy wskaźnik na strukturę:

typedef struct point {
  int x;
  int y;
} *point_t;

point_t maxpt;
maxpt = malloc(sizeof(struct point));
maxpt->x = 128; maxpt->y = 256;

Przykład w którym użyto powyższych konstrukcji.

Czasami potrzebujemy tablic struktur. Można je zdefiniować na kilka sposobów:

struct key {
  char *word;
  int count;
} keytab[NKEYS];

struct key {
  char *word;
  int count;
};
struct key keytab[NKEYS];

typedef struct key {
  char *word;
  int count;
} key_t;
key_t keytab[NKEYS];

Ciekawy przykład zastosowania tablic struktur – tablica łącznikowa.

Struktury i funkcje – pierwiastki wielomianów:

Better Structures in C99

Funkcje napisane w języku Python, Ruby mogą zwracać wiele wartości, a w języku C tylko jedną. Ale w C możemy zwrócić strukturę, która może składać się z tylu elementów ile potrzebujemy.

Zilustrujemy to za pomocą tego przykładu. Kompilujemy go tak:

cc -std=c99 -Wall papersize.c
[Ants 2]

Misunderstandings can arise when an author is thinking in a broader context than the reader. A reader might be thinking tactically:
How can I do a better job today?
while the author is thinking strategically: How can we make a better tomorrow? The misunderstanding becomes especially acute when real progress requires abandoning today's world and starting over.

— B. Victor, Reading Tip #3

Abstrakcyjne Type Danych (ADT)

Abstract Data Type (w skrócie ADT). Implementacja stosu jako ADT.

Abstrakcyjne Typy Danych służą do oddzielenia interfejsu od implementacji (ang. information hiding).

To oddzielenie osiągamy w C korzystając z nieprzezroczystych struktur danych (ang. opaque data structures).

W pliku nagłówkowym (.h) wpisujemy:

typedef struct structCDT *structADT;

albo

struct structCDT;

W pliku implementującym ADT (.c) wpisujemy:

struct structCDT {
  /* definicje pól */
}

Dlaczego powyższe definicje nie powodują błędów w trakcie kompilacji?

Dlaczego pozwalają oddzielić interfejs od implementacji? Jak to „oddzielenie” działa?

Przykład ADT – punkt na płaszczyźnie:

Stos (Stack) to klasyczny przykład, który implementujemy jako ADT:

(W kodzie powyżej korzystamy z CSLib.)

Jeszcze jeden program przykładowy

Struktury odwołujące się do samych siebie – zliczanie wystąpień wszystkich słów podanych na wejściu

struct tnode {         /* węzeł drzewa */
  char *word;          /* wskaźnik do tekstu słowa */
  int count;           /* licznik wystąpień */
  struct tnode *left;  /* lewy potomek */
  struct tnode *right; /* prawy potomek */
};

Uwaga: C nie dopuszcza, aby struktura zawierała w sobie swoje własne wcielenie. Ale struktura może zawierać wskaźnik do samej siebie.

Wersja opisowa programu zliczającego słowa fw.pdf (zob. rozdział 6.5 w K&R).

Po kompilacji fw.w:

ctangle fw.w
cc -Wall fw.c -o fw

program fw uruchamiamy tak:

./fw < fw.w | sort -nr -k1 | head -n 10

GLib & paths

Biblioteki mogą być zainastalowane w kilku miejscach. Jakich?

Aby się przekonać, gdzie została zainstalowana konkretna biblioteka możemy skorzystać z programu pkg-config, np. jeśli

pkg-config --libs glib gsl
pkg-config --cflags glib gsl
pkg-config --cflags --libs glib gsl

Tak wygląda kompletny przykład:

cc -o specific specific.c `pkg-config --cflags --libs glib`

Uwaga: Na Sigmie jest zainstalowana biblioteka GLib w wersji 2.0-beta. Dlatego musimy dopisać wersję w poleceniu powyżej:

cc -o specific specific.c `pkg-config --cflags --libs glib-2.0`

Dwa przykłady: