{"id":194,"date":"2018-05-02T14:32:18","date_gmt":"2018-05-02T12:32:18","guid":{"rendered":"http:\/\/www.kompikownia.pl\/?p=194"},"modified":"2018-05-02T14:32:18","modified_gmt":"2018-05-02T12:32:18","slug":"stos-generyczny-w-jezyku-c","status":"publish","type":"post","link":"https:\/\/www.kompikownia.pl\/index.php\/2018\/05\/02\/stos-generyczny-w-jezyku-c\/","title":{"rendered":"Stos generyczny w j\u0119zyku C"},"content":{"rendered":"Czas czytania:<\/span> 3<\/span> minut<\/span><\/span>

W jednym z poprzednich artyku\u0142\u00f3w<\/a> opisa\u0142em, jak mo\u017cna w j\u0119zyku C zaprogramowa\u0107 stos. Z pewno\u015bci\u0105 przy tworzeniu bardziej zaawansowanego projektu napotkasz na pewien problem: Co zrobi\u0107, je\u015bli chcesz posiada\u0107 kilka stos\u00f3w, przechowuj\u0105cych r\u00f3\u017cne rodzaje danych? W C++, Javie, C# i innych tego typu j\u0119zykach rozwi\u0105zanie tego problemu jest dosy\u0107 proste. Mo\u017cemy stworzy\u0107 stos generyczny, czyli mog\u0105cy przechowywa\u0107 wybrany przez nas rodzaj danych. Niestety, zwyk\u0142y C nie wspiera tego rodzaju u\u0142atwiaj\u0105cych \u017cycie programisty wynalazk\u00f3w. W C nie mamy typ\u00f3w generycznych, kt\u00f3re pozwala\u0142yby na \u0142atwe utworzenie dynamicznej struktury danych mog\u0105cej przechowywa\u0107 r\u00f3\u017cne rodzaje danych.<\/p>\n

\"generic_stack\"
Pi\u0119kny stos, prawda?<\/figcaption><\/figure>\n

Mo\u017cemy oczywi\u015bcie oby\u0107 si\u0119 bez typ\u00f3w generycznych. Wystarczy stworzy\u0107 kilka ro\u017cnych rodzaj\u00f3w struktury stack_node. Ka\u017cda z wersji przechowywa\u0142aby inny typ zmiennej w polu data. Rozwi\u0105zanie to niesie za sob\u0105 bardzo wiele wad. Po pierwsze – kod funkcji push i pop, kt\u00f3ry zmienia si\u0119 w bardzo niewielkim stopniu dla poszczeg\u00f3lnych rodzaj\u00f3w stos\u00f3w b\u0119dzie musia\u0142 by\u0107 skopiowany tyle razy, ile r\u00f3\u017cnych typ\u00f3w stos\u00f3w posiadamy. Wyobra\u017a sobie teraz, \u017ce musisz mie\u0107 kilkana\u015bcie stos\u00f3w przechowuj\u0105cych kilkana\u015bcie r\u00f3\u017cnych rodzaj\u00f3w danych. Funkcja push i pop jest skopiowana kilkadziesi\u0105t razy. Nast\u0119pnie zauwa\u017casz, \u017ce tw\u00f3j stos nie dzia\u0142a poprawnie. Musisz zatem poprawi\u0107 kilkadziesi\u0105t r\u00f3\u017cnych wersji kodu. Jest to niezbyt zach\u0119caj\u0105ca perspektywa …<\/p>\n

Jak zatem rozwi\u0105za\u0107 ten problem? K\u0142opot mo\u017cemy za\u0142agodzi\u0107 na kilka sposob\u00f3w. Zajmiemy si\u0119 tymi najlepszymi i najprostszymi metodami<\/p>\n

Stos generyczny za pomoc\u0105 unii<\/h1>\n

Otw\u00f3rz ten artyku\u0142<\/a> i przeanalizuj stos w nim opisany. Zastan\u00f3wmy si\u0119, jak mo\u017cemy go zmodyfikowa\u0107 tak, aby przechowywa\u0107 w\u00a0nim r\u00f3\u017cne rodzaje danych.<\/p>\n

W naszym rozwi\u0105zaniu wykorzystamy uni\u0119. Unia jest podobnym tworem do struktury. Podobnie jak struktura, mo\u017ce zawiera\u0107 kilka p\u00f3l. Jednak\u017ce, w przeciwie\u0144stwie do niej, w unii wszystkie pola znajduj\u0105 si\u0119 pod tym samym adresem pami\u0119ci. Ju\u017c ta definicja powinna ci nasuwa\u0107 pomys\u0142, w jaki wykorzystamy uni\u0119 do stworzenia pseudo generyczno\u015bci.<\/p>\n

Utw\u00f3rzmy sobie strukturk\u0119 person, kt\u00f3ra b\u0119dzie jednym z mo\u017cliwych typ\u00f3w danych, kt\u00f3re b\u0119dzie da\u0142o si\u0119 odk\u0142ada\u0107 na nasz nowy, lepszy stos.<\/p>\n

struct person\r\n{\r\n    char name[32];\r\n    char surname[32];\r\n};\r\n<\/pre>\n
Zadeklarujmy sobie nasz\u0105 uni\u0119. Wewn\u0105trz niej umie\u015bcimy wszystkie mo\u017cliwe rodzaje danych, jakie b\u0119dzie przechowywa\u0142 nasz stos.<\/p>\n
union data_types\r\n{\r\n    int number;\r\n    char text[64];\r\n    struct person per;\r\n};\r\n<\/pre>\n
Dodajmy teraz pole naszej unii do struktury stack_node.<\/p>\n
struct stack_node\r\n{\r\n    union data_types dt;\r\n    struct stack_node* next;\r\n};\r\n<\/pre>\n
Musimy zastanowi\u0107 si\u0119, jak mo\u017cemy zmodyfikowa\u0107 funkcj\u0119 push, aby poprawnie wsp\u00f3\u0142pracowa\u0142a z now\u0105 struktur\u0105 stack_node. P\u00f3jdziemy najprostsz\u0105 mo\u017cliw\u0105 \u015bcie\u017ck\u0105. Przeka\u017cemy uni\u0119 jako argument funkcji. Zmodyfikowane funkcje push i pop widoczne s\u0105 na listingach poni\u017cej.<\/p>\n
struct stack_node *push(struct stack_node* top, union data_types new_dt)\r\n{\r\n     struct stack_node* new_node = NULL;\r\n     new_node = (struct stack_node*) malloc(sizeof(struct stack_node));\r\n     if(new_node!=NULL)\r\n     {\r\n         new_node->dt = new_dt;\r\n         new_node->next = top;\r\n         top = new_node; \r\n     }\r\n     return top;\r\n}\r\nbool pop(struct stack_node * * top, union data_types * result) {\r\n if ( * top != NULL) {\r\n     *result = (*top)->dt;\r\n     struct stack_node * tmp = (*top)->next;\r\n     free(*top); \r\n     *top = tmp;\r\n     return true;\r\n   }\r\n   return false;\r\n}\r\n<\/pre>\n
Jak powiniene\u015b zauwa\u017cy\u0107, r\u00f3\u017cnice nie s\u0105 zbyt wielkie. Dotykaj\u0105 one definicji funkcji (w kt\u00f3rej jako argument przekazujemy teraz uni\u0119, a nie zmienn\u0105 typu int). Wi\u0119cej zmian zasz\u0142o w funkcji pop. Wcze\u015bniej funkcja ta zwraca\u0142a warto\u015b\u0107 typu int. Teraz zwracamy bool. Dlaczego? Dzi\u0119ki temu b\u0119dziemy wiedzieli, kiedy stos jest pusty. Funkcja pop zwr\u00f3ci teraz w takim wypadku fa\u0142sz.<\/p>\n
Spr\u00f3bujmy teraz wykorzysta\u0107 nasz stos.<\/p>\n
int main() {\r\n  struct stack_node * stack1 = NULL, * stack2 = NULL;\r\n  \/\/Odk\u0142adamy na stos\r\n  for (int i = 0; i<5; i++) {\r\n    union data_types dt;\r\n    dt.number = i;\r\n    stack1 = push(stack1, dt);\r\n  }\r\n  union data_types person1, person2;\r\n  strcpy(person1.per.name, \"Jan\");\r\n  strcpy(person1.per.surname, \"Kowalski\");\r\n  strcpy(person2.per.name, \"Anna\");\r\n  strcpy(person2.per.surname, \"Nowak\");\r\n  stack2 = push(stack2, person1);\r\n  stack2 = push(stack2, person2);\r\n  \/\/ Zdejmujemy ze stosu\r\n  for (int i = 0; i<5; i++) {\r\n    union data_types dt = pop( &stack1);\r\n    printf(\"Zdj\u0105\u0142em %d\\n\", dt.number);\r\n  }\r\n  puts(\"zdejmuj\u0119 ci\u0105gi znak\u00f3w\");\r\n  union data_types dt2, dt3;\r\n  dt2 = pop( &stack2);\r\n  dt3 = pop( &stack2);\r\n  printf(\"Pierwsza osoba: %s %s\\n\", dt2.per.name, dt2.per.surname);\r\n  printf(\"Druga osoba: %s %s\\n\", dt3.per.name, dt3.per.surname);\r\n}\r\n<\/pre>\n
Powy\u017cej znajduje si\u0119 listing funkcji main. Co robimy naszym stosem? Na pocz\u0105tku, w linii 2 tworzymy sobie dwa stosy. Pierwszy z nich wype\u0142niamy liczbami naturalnymi od 0 do 4. Drugi z nich wype\u0142niamy imionami i nazwiskami. W drugiej cz\u0119\u015bci funkcji zdejmujemy cyfry z pierwszego stosu i struktury z drugiego. Wynik dzia\u0142ania funkcji wy\u015bwietlamy na ekranie.
\n\"\"<\/p>\n
Co mo\u017cna poprawi\u0107?<\/h1>\n
Zauwa\u017c, \u017ce w przypadku powy\u017cszej implementacji nie jeste\u015bmy ograniczeni do przechowywania jednego konkretnego typu danych na danym stosie. Na jednym stosie mo\u017cemy przechowywa\u0107 kilka r\u00f3\u017cnych rodzaj\u00f3w danych. Np.: Na szczycie mo\u017ce znajdowa\u0107 si\u0119 liczba, ni\u017cej ci\u0105g znak\u00f3w, a na samym dnie osoba (struktura person). Dla rozr\u00f3\u017cnienia, co przechowujemy w danym polu stosu mo\u017cemy doda\u0107 dodatkow\u0105 zmienn\u0105 typu enum, albo int w stack_node. Informowa\u0142aby nas, co przechowujemy w danym polu stosu. Modyfikacj\u0119 tego rodzaju zostawiam ci, czytelniku, na prac\u0119 domow\u0105.
\nPe\u0142ny kod programu, kt\u00f3ry omawiali\u015bmy powyzej znajduje si\u0119 w moim repozytorium<\/a>.<\/p>\n","protected":false},"excerpt":{"rendered":"
Czas czytania:<\/span> 3<\/span> minut<\/span><\/span> W jednym z poprzednich artyku\u0142\u00f3w opisa\u0142em, jak mo\u017cna w j\u0119zyku C zaprogramowa\u0107 stos. Z pewno\u015bci\u0105 przy tworzeniu bardziej zaawansowanego projektu napotkasz na pewien problem: Co zrobi\u0107, je\u015bli chcesz posiada\u0107 kilka …<\/p>\n","protected":false},"author":1,"featured_media":211,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_monsterinsights_skip_tracking":false,"_monsterinsights_sitenote_active":false,"_monsterinsights_sitenote_note":"","_monsterinsights_sitenote_category":0,"footnotes":""},"categories":[25,22],"tags":[],"_links":{"self":[{"href":"https:\/\/www.kompikownia.pl\/index.php\/wp-json\/wp\/v2\/posts\/194"}],"collection":[{"href":"https:\/\/www.kompikownia.pl\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.kompikownia.pl\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.kompikownia.pl\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.kompikownia.pl\/index.php\/wp-json\/wp\/v2\/comments?post=194"}],"version-history":[{"count":25,"href":"https:\/\/www.kompikownia.pl\/index.php\/wp-json\/wp\/v2\/posts\/194\/revisions"}],"predecessor-version":[{"id":221,"href":"https:\/\/www.kompikownia.pl\/index.php\/wp-json\/wp\/v2\/posts\/194\/revisions\/221"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.kompikownia.pl\/index.php\/wp-json\/wp\/v2\/media\/211"}],"wp:attachment":[{"href":"https:\/\/www.kompikownia.pl\/index.php\/wp-json\/wp\/v2\/media?parent=194"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.kompikownia.pl\/index.php\/wp-json\/wp\/v2\/categories?post=194"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.kompikownia.pl\/index.php\/wp-json\/wp\/v2\/tags?post=194"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}