Fórum Root.cz
Hlavní témata => Vývoj => Téma založeno: dl 03. 02. 2015, 21:32:27
-
Jak se nejlépe dají implementovat znovupoužitelné datové struktury v C? Pokud mám jednosměrný/obousměrný spojový seznam, liší se v ukazateli na head, který je typem single_node nebo double_node:
[item]-->next vs prev<--[item]-->nex.
Chtěl bych co nejvíce přepoužívat hlavičkové soubory, něco jako jako dědičnost. Budu to muset zuřivě přetypovávat? Jak si neuseknout nohy?
+-----List-----+
^ ^
Single-List Doubly-List <-- uses Double-Node
^ uses Single-Node
Tak nějak. Pak třeba zásobník implementovaný pomocí Single Listu, který už je předpřipraven. Děkuji za rady.
Implementovat každou zvlášť zvládnu. Jde mi o nějakou hiararchii -- jako v Javě a spol.
-
nevim jestli java je uplne nejlepsi priklad, v jave si lehce pouzijes interface a nadefinujes rozhrani trid, ktere pak muze sdilet
cela hierarchie trid, tohle bych do C ani netahal.
to je takovy problem mit hlavicku a implementaci pro single linked list a samostatnou pro double linked list?
kod samozrejme muzu znovupouzit a trochu prepsat.
myslim, ze chcete udelat z komara velblouda.
-
Pokud chceš simulovat dědičnost, tak můžeš vložit rodičovskou strukturu jako první položku do dceřiné struktury:
struct parent
{
struct parent *prev;
struct parent *next;
};
struct child
{
struct parent _super; // musí být první položkou!
int data;
};
Pokud pak máš ukazatel na struct child, tak ho můžeš přímo přetypovat na struct parent. Norma ti zaručuje, že je to korektní:
struct child *pointer1 = get_child();
struct parent *pointer2 = (struct parent *) pointer1;
Explicitním přetypováním se ale přitom nevyhneš.
-
Jinak seznamy se často řeší pomocí maker. Nadefinuješ si třeba takovou strukturu:
struct my_struct
{
struct my_struct *foo_prev;
struct my_struct *foo_next;
int data;
}
Makru pro práci se seznamem pak předáváš typ položek (struct my_struct *) a prefix ukazatelů prev a next (foo). Takový přístup má pak tu výhodu, že můžeš strkat jednu instanci do více seznamů, pokud si na to definuješ více pointerů:
struct my_struct2
{
struct my_struct2 *foo_prev;
struct my_struct2 *foo_next;
struct my_struct2 *bar_prev;
struct my_struct2 *bar_next;
int data;
}
Pro práci s prvním seznamem předáš makru parametr foo, pro práci s druhým pak bar.
-
to je takovy problem mit hlavicku a implementaci pro single linked list a samostatnou pro double linked list?
kod samozrejme muzu znovupouzit a trochu prepsat.
Mne jen zajímá jestli to někdo v C dělá ..., jinak máte pravdu. Trochu se nutím do procedurálního -- modulárního programování, tak mne to vrtá hlavou, kde jsou limity. Jak říkám, udělat si to zvláště umím, stejně jako jsem koukal jak je uděláno v linux/list.h. Díky za podnět.
-
jinak s tema strukturama a pretypovanim jdou i takove veci, protoze ten int je v paneti jako bajty za sebou, takze se to muze rozseknout
na mensi typ:
#include<stdio.h>
struct aaa {
unsigned int a;
};
struct bbb {
unsigned char x;
unsigned char y;
};
int main()
{
struct aaa bitu16;
bitu16.a=65535;
printf ("%d\n",bitu16.a);
struct bbb *bitu8 = (struct bbb*) &bitu16;
printf ("%d %d\n",bitu8->x,bitu8->y);
return 0;
}
-
Na tohle používá přetypování, funkce na operace se seznamem pak pracují pouze s hlavičkami.
Kdo se bojí přetypování musí použít union, což je převlečené přetypování
struct item_head
{
struct item_head * prev;
struct item_head * next;
}
union custom_item
{
item_head head;
struct
{
item_head head1;
int data1;
int data2;
}
}
Jednosměrný spojový seznam se nepoužívá od té doby co je paměti přebytek.
-
int je v paneti jako bajty za sebou, takze se to muze rozseknout na mensi typ
Teoreticky ano, prakticky je problém s align a endianess. Vyřešit to lze, ale dá to práci.
-
struct bbb *bitu8 = (struct bbb*) &bitu16;
Já teda nejsem kdoví jaký znalec normy jazyka C, ale myslím, že tohle není (od C99) validní (porušuje to strict-aliasing rule).
-
Díky za náměty, musím si je projít zítra s čistou hlavou. Teď jen odbočka -- sáhli byste raději po knihovně jako Glib či jiné, nebo implementovat základní DS vlastnoručně má své místo? -- s ohledem na C nikoliv C++.
-
http://home.gna.org/gdsl/
-
struct aaa {
unsigned int a;
};
struct bbb {
unsigned char x;
unsigned char y;
};
struct aaa bitu16;
bitu16.a=65535;
struct bbb *bitu8 = (struct bbb*) &bitu16;
Musím tedy varovat, že toto je nepřenositelné, navíc i na jedné architektuře to může a nemusí pracovat na základě příznaků při překladu, fáze měsíce, verze překladače a kdovíčeho dalšího, takže prosím pozor.
-
Já bych k tomu ještě dodal, že docela záleží na tom, o co ti vlastně jde. Jestli je to jenom takové cvičení, aby sis vyzkoušel pokročilejší C, ok, nic proti. Pokud jsi v C začátečník a snažíš se na něj naroubovat něco, co znáš z jiných jazyků (Java apod.), tak to mi nepřijde jako dobrej nápad - dřív nebo později se do toho imho zamotáš a stejně se ti nepodaří získat chování, na které jsi byl zvyklý. Jestli se chceš učit C, tak se ho snaž poznat takové, jaké je, jak se používá, nesnaž se na něj naroubovat něco cizího...
A pokud z nějakého důvodu fakt na vážno potřebuješ objektový přístup a zároveň C, tak by možná stálo za zvážení jít cestou http://cs.wikipedia.org/wiki/Vala_%28programovac%C3%AD_jazyk%29 nebo nějakou podobnou.
---
P.S.
Znovupoužitelnost kódu nespočívá jenom v "objektovosti" a dědičnosti. Ve funkcionálním programování bys viděl spoustu znovupoužitelného kódu a žádná dědičnost se tam nepoužívá :) Zrovna snažit se abstrahovat společné vlastnosti double- a single-linked listu mi nepřijde úplně dobrý příklad, množina společných operací* tam bude minimální (např. pokud bys chtěl takový "zobecněný" list třídit, jak to budeš dělat? Přidáš do double-linked nějaký callback, který ex post opraví vazby? Nebo budeš uvnitř funkce pořád ifovat? ;) To by bylo přesně to peklo, do kterýho se dostat nechceš ;) ).
* tj. operací, které bys mohl jedním způsobem implementovat nad oběma typy seznamů
A ještě jeden tip bych měl: ke zobecňování můžeš přistupovat i tak trochu "z druhé strany" - pomocí přístupu, který se v Elixiru jmenuje protokoly (http://elixir-lang.org/getting_started/16.html). Podobně to má i Go (http://golangtutorials.blogspot.cz/2011/06/structs-in-go-instead-of-classes-in.html) Princip spočívá v tom, že si nadefinuješ nějakou množinu operací nad strukturou, naimplementuješ pro každý typ struktury zvlášť (nejsi ničím omezený!), ale přistupuješ k nim pak jednotným způsobem. V C bys to mohl udělat třeba tak, že bys měl strukturu callbacků a pak bys volal nějaké makro třeba sort(my_linked_list) a přeložilo by se ti to třeba na "my_linked_list -> sorting -> sort(my_linked_list)", kde tvůj typ obsahuje pointer na strukturu obsahující pointery na jednotlivé operace. Strukturu s pointery máš pak jenom jednu a každý "objekt" na ni má jenom ukazatel. (pointa: v OOP se začala děsně zdůrazňovat dědičnost a zapomnělo se na skládání :) Pořád je to ale "neCéčkovský" přístup, který bys měl volit jenom z hodně dobrých důvodů.
-
Doporučuji podívat se jak to dělají v Linuxovém jádru. Moc pěkné. Jednoduché výkonné a elegantní. Sám používám (svou lite) modifikaci pro jednočipy.
-
Doporučuji podívat se jak to dělají v Linuxovém jádru. Moc pěkné. Jednoduché výkonné a elegantní. Sám používám (svou lite) modifikaci pro jednočipy.
Jo, http://lwn.net/Articles/444910/ a http://lwn.net/Articles/446317/
-
Když už se tu znínila ta přenositelnost, tak například (co si tak pamatuji) po provedení něčeho takového
foo *x = neco;
foo *y = (foo*) ((bar*) x)
nemusí (kvůli rozdílným požadavkům foo a bar na zarovnání v paměti) vůbec platit y == x. S ukazateli se tedy ne vždy vyplatí různě kouzlit.
-
např. pokud bys chtěl takový "zobecněný" list třídit, jak to budeš dělat? Přidáš do double-linked nějaký callback, který ex post opraví vazby? Nebo budeš uvnitř funkce pořád ifovat? ;) To by bylo přesně to peklo, do kterýho se dostat nechceš ;).
Vy už jste to zapomněl ? ;) Před OOP se porovnávalo takhle, úplně stejně to bude pro double-linked list:
void qsort(void *base, size_t nitems, size_t size, int (*compar)(const void *, const void*))
foo *x = neco;
foo *y = (foo*) ((bar*) x)
V žádném známém překladači se do y nedostane jiná hodnota než je v x. Zarovnání se uplatní při deklaraci, ne při přetypování.
-
Vy už jste to zapomněl ? ;) Před OOP se porovnávalo takhle, úplně stejně to bude pro double-linked list:
Problém není v porovnání, ale v přeskládání té struktury - u SLL musím udělat jiné operace než u DLL. Představa, že udělám jeden kód, který bude fungovat nad jakoukoli strukturou, není v tomhle případě úplně šťastná, pokud mi nejde čistě o bubble sort.
-
... Pořád je to ale "neCéčkovský" přístup, který bys měl volit jenom z hodně dobrých důvodů. ...
Nene, já se nasnažím za každou cenu naroubovat Javu na C, zkouším co se dá zpětně uplatnit. Víte dnes většina lidí nezačíná na C, takže se na mne nezlobte. Stejně jako pro C-čkaře mohl být přechod na OOP zas opačný problém .) -- Jinak jste to odhadl správně, že jsem narazil na problémy .), proto sem přišel s otázkou...
Proč podle vás nemají D-List a S-List společné operace?
insertAfter
insertBefore
insertBeginning
insertEnd
...
-
Doporučuji podívat se jak to dělají v Linuxovém jádru. Moc pěkné. Jednoduché výkonné a elegantní. Sám používám (svou lite) modifikaci pro jednočipy.
Díky, již jsem včera studoval a poznamenal jsem to v otázce -- také jiné knihovny, nějakou, kde mají většinu DS pomocí maker, a taky něco z NGinx a Asterisk.
-
Vy už jste to zapomněl ? ;) Před OOP se porovnávalo takhle, úplně stejně to bude pro double-linked list:
Problém není v porovnání, ale v přeskládání té struktury - u SLL musím udělat jiné operace než u DLL. Představa, že udělám jeden kód, který bude fungovat nad jakoukoli strukturou, není v tomhle případě úplně šťastná, pokud mi nejde čistě o bubble sort.
Já sem to myslel na úrovni hlavičkových souborů ... pro společné operace jeden header file a různé implemntace v Slisti a Dlistu, nebo nějaká společná makra.
-
Představa, že udělám jeden kód, který bude fungovat nad jakoukoli strukturou, není v tomhle případě úplně šťastná, pokud mi nejde čistě o bubble sort.
Kód pro SLL/DLL musí být jiný, kód pro operace s uživatelskými daty v SLL/DLL může být stejný.
Já sem to myslel na úrovni hlavičkových souborů ... pro společné operace jeden header file a různé implemntace v Slisti a Dlistu, nebo nějaká společná makra.
Můžete mít void DirectoryList(LinkedListManager * manager, LinkedListControlData * control_data, char * directory) a naimplementovat si co potřebujete, ale je to tedy psaní moc.
Příklady nemůžete najít proto že single linked list už prakticky nikdo nepoužívá, kromě mikrokontrolérů.
-
Mrkni na http://www.root.cz/knihy/object-oriented-programming-in-ansi-c/
Jinak pokud jde o C, tak na jednočipech není obecně dynamická paměť dobrý nápad (a je pro to kupa hodně dobrých důvodů), na všem silnějším se dá použít C++
-
Me pripada ze vsichni snazi resit jednoduche veci slozite ...
typedef struct tagLinkedList {
void *pData;
struct tagLinkedList *lpNext,*lpPrev;
} LINKEDLIST, *LPLINKEDLIST;
-
foo *x = neco;
foo *y = (foo*) ((bar*) x)
V žádném známém překladači se do y nedostane jiná hodnota než je v x. Zarovnání se uplatní při deklaraci, ne při přetypování.
Tak jsem se koukal, co říká norma (C99). Pokud hodnota, na kterou odkazuje x, není správně zarovnána podle typu bar, pak výsledek operace (bar*) x není definován. Ovšem zpětná konverze na foo* musí zase dát původní hodnotu.
Moc bych to nepodceňoval, pokud si například udělám strukturu dvou 32bitových intů a pokusím se někdy ukazatel na ni přetypovat na ukazatel na 64bitový int, tak mi to na některých architekturách nemusí projít (pokud budou vyžadovat zarovnání 64bitových intů na 64 bitů).
-
Nene, já se nasnažím za každou cenu naroubovat Javu na C, zkouším co se dá zpětně uplatnit. Víte dnes většina lidí nezačíná na C, takže se na mne nezlobte.
Samozřejmě :) Vůbec se nezlobím, akorát jsem chtěl říct, že častý problém začátečníků v jakémkoli jazyku je v tom, že se snaží do nového jazyka vkládat návyky z toho, který už umí. A většinou to dopadá špatně. Zkusit něco uplatnit je super, ale chce to nejprve *oba* jazyky dobre znát, aby člověk mohl dobře posoudit, jestli jde správným směrem. Začátečník to neposoudí.
Stejně jako pro C-čkaře mohl být přechod na OOP zas opačný problém
Však taky je :) Spousta lidí programuje strukturálně, akorát funkce nějak mírnixtýrnix sdruží v nějakých třídách a s OOP to nemá nic společného :)
.) -- Jinak jste to odhadl správně, že jsem narazil na problémy .), proto sem přišel s otázkou...
Proč podle vás nemají D-List a S-List společné operace?
Společné funkce mají, ale problém nastane, pokud se budeš snažit v céčku udělat polymorfismus - tj. mít nějakou jednu funkci "sort", která bude umět pracovat s oběma strukturami. To prostě v tomhle případě není dobrý přístup, lepší je mít dvě implementace, každou pro tu konkrétní strukturu. Jestli je potom budeš chtít nějak zabalit, aby se volaly stejně pro obě struktury, to už je jiná otázka.
-
Já sem to myslel na úrovni hlavičkových souborů ... pro společné operace jeden header file a různé implemntace v Slisti a Dlistu, nebo nějaká společná makra.
Jo, to je schůdný přístup za předpokladu, že ta makra jenom sjednocují interface a nic moc víc od nich nečekáš. Takhle to funguje v tom kernelu (nakolik to můžu posoudit).
I tak ale zůstává otázka, jestli to v céčku v nějaké konkrétní situaci dává nějaký smysl. Určitě je to super někde, kde očekávám od různých kusů software stejný interface (typicky pluginy). Jinde to ale může způsobit víc škody než užitku... Typicky se v C programuje tak, že když někam předám SLL, tak nad ním volám funkci určenou pro zpracování SLL a that's it ;)
-
Nene, já se nasnažím za každou cenu naroubovat Javu na C, zkouším co se dá zpětně uplatnit. Víte dnes většina lidí nezačíná na C, takže se na mne nezlobte.
Samozřejmě :) Vůbec se nezlobím, akorát jsem chtěl říct, že častý problém začátečníků v jakémkoli jazyku je v tom, že se snaží do nového jazyka vkládat návyky z toho, který už umí. A většinou to dopadá špatně. Zkusit něco uplatnit je super, ale chce to nejprve *oba* jazyky dobre znát, aby člověk mohl dobře posoudit, jestli jde správným směrem. Začátečník to neposoudí.
Stejně jako pro C-čkaře mohl být přechod na OOP zas opačný problém
Však taky je :) Spousta lidí programuje strukturálně, akorát funkce nějak mírnixtýrnix sdruží v nějakých třídách a s OOP to nemá nic společného :)
.) -- Jinak jste to odhadl správně, že jsem narazil na problémy .), proto sem přišel s otázkou...
Proč podle vás nemají D-List a S-List společné operace?
Společné funkce mají, ale problém nastane, pokud se budeš snažit v céčku udělat polymorfismus - tj. mít nějakou jednu funkci "sort", která bude umět pracovat s oběma strukturami. To prostě v tomhle případě není dobrý přístup, lepší je mít dvě implementace, každou pro tu konkrétní strukturu. Jestli je potom budeš chtít nějak zabalit, aby se volaly stejně pro obě struktury, to už je jiná otázka.
Proc dve impementace ?
void qsort(void *base, size_t nitems, size_t size, int (*compar)(const void *, const void*))
-
Proc dve impementace ?
void qsort(void *base, size_t nitems, size_t size, int (*compar)(const void *, const void*))
Ach jo... druhej :)
No, protože tahle funkce může existovat jenom proto, že pracuje nad polem. Jak bys chtěl udělat stejně obecnou funkci a nevědět, jak uložená data jí předáš? Co když jí předám třeba strom?
Obecně to může fungovat tak maximálně pro bubble sort, který od struktury neočekává nic jinýho než operaci swap.
-
Pokud nevadi makra pak sys/queue.h (https://svnweb.freebsd.org/base/head/sys/sys/queue.h?view=markup sys/queue.h) muze byt cesta.
-
Proc dve impementace ?
void qsort(void *base, size_t nitems, size_t size, int (*compar)(const void *, const void*))
Ach jo... druhej :)
No, protože tahle funkce může existovat jenom proto, že pracuje nad polem. Jak bys chtěl udělat stejně obecnou funkci a nevědět, jak uložená data jí předáš? Co když jí předám třeba strom?
Obecně to může fungovat tak maximálně pro bubble sort, který od struktury neočekává nic jinýho než operaci swap.
No pokud bude operace swap netrivialni muzu ji vytahnout stejnym zpusobem vne "sortu" jako "compare" a fungovat to bude pro cokoliv otazkou je jestli to jeste bude optimalni .. (vzdy je to kompormis mezi rychlosti a lenosti)
-
No pokud bude operace swap netrivialni muzu ji vytahnout stejnym zpusobem vne "sortu" jako "compare" a fungovat to bude pro cokoliv otazkou je jestli to jeste bude optimalni .. (vzdy je to kompormis mezi rychlosti a lenosti)
Ano, pokud ti k celýmu sortu stačí jenom swap, tak se to ještě dá. Pokud ale budeš potřebovat vkládat kamkoli, tak už to přestává být zajímavý - a dostáváš se přesně do toho bodu, kdy snaha o sjednocení udělá víc škody než užitku. Pak už je prostě jednodušší napsat sort_struktura1, sort_strutkura2, ... a nějakým způsobem je (když už) sjednotit, aby se při volání sort(...) zavolala ta správná funkce pro danou strukturu. Bonus pak je, že můžeš jednotlivý funkce parádně optimalizaovat na míru.
On je to obecný "filosofický" problém - takový ten klasický "OOP polymorfismus" vždycky nějakým způsobem využívá princip "nejmenšího společného jmenovatele", čili když se to implementuje neuváženě, vede to jenom ke zpkriplení struktur, který by jinak byly super :)