Jak v C uložit do pole char pointer na další slovo – C / C++ – Fórum – Programujte.com

Ahoj,

řešil jsem úkol s vytvořením pole jednotlivých slov ve větě podle delimiteru.

řeším to 2 fázově nejdříve spočítám slova, alokuji char** na daný počet char* a poté počítám znaky slov a alokuji char* pro daný počet písmen a zkopíruji znaky.
 

přemýšlel jsem jak to zjednodušit, zda by nešlo přeskočit první fázi a jít rovnou do počítání znaků a kopírování s tím, že ve slově přidám do alokace místo na pointer na další slovo, ale nevím jak do char* dostat na ten konec za "\0" ten pointer, tedy obě cesty jak uložení tak přečtení.

něco jako spojitý seznam v jiném jazyce bych to nadefinoval např jako strukturu

{slovo : string ;
next : pointer;}

Pokud muzes ten prohledavany retezec menit, tak proste zapisujes \0 misto delimiteru a pokracujes na dalsim znaku. Jen si pak samozrejme pamatovat, ze tyhle podretezce ti nepatri a free se da udelat jen na ten uplne prvni jako celek.

Na seznam pointeru se hodi spise spojovy seznam. Ale s pomoci reallocu se to da zmaknout taky a v jednom kole.

#1 MilanL
Nějak nechápu ten poslední dostavec. C taky "umí" struktury.

struct neco {
  typ jmeno;
  typ jmeno;
};

#3 gna
ano vím tomu jsem se chtěl ale vyhnou.

napadá mě řešení s přetypováním

char* slovo = malloc(počet znaků);
{ kopie slova }
char** next = (char**) slovo;   nebo to má být   *(next) = slovo; ?
najdi další slovo

slovo  = malloc(počet znaků);
next = slovo;

přiznám se trošku v těch pointerech plavu

no já si to tedy vyzkouším, různé varianty a snad to dopade

btw to už si rovnou můžu udělat kopii textu a nahradit delimitery v té kopii, nebo předem vytvořit pole pointerů ** určité velikosti a jen v případě překročení ho realokovat.

ještě mě tak napadá že ten next by měl být na začátku kvůli pozdějšímu uvolňování

Teda next v té struktuře by samozřejmě zase byla ta struktura. 

struct item {                                                                   
    struct item *next;                                                      
    char data[1];                                                           
};

#6 gna
oki díky moc za objasnění hlavně ta druhá část mi to trošku vyjasnila,

ještě otázka ten malock alokuje jen opravdu potřebnou paměť nebo blok s nějakou minimální velikostí, případně s paměťovým zarovnáním?

Alokátory typicky interně podporují jen velikosti s nějakou granularitou, takže reálná alokovaná velikost bude vždycky s nějakým zarovnáním.

#8 MilanL
mallock() alokuje tuším se zarovnáním na jedno slovo, tedy 4 nebo 8 bajtů dle arcarchitektury. Plus ještě jedno slovo režie. Alokace po několika bajtech není tedy efektivní.

Nechal bych slova v původním stringu, spočítal je a alokoval jedno pole pro indexy do toho původního stringu.

Zkus se podívat, jak to interně řeší jazyky Lisp a Forth, které jsou na slovnících založeny.

#8 MilanL
Tak jsem si to zmapoval. Když chci alokovat 1-24 bajtů, tak si malloc() vždy ukousne 32 B. Pro alokaci 25-40 B si vezme 48 B atd.

Alokace malých kousků RAM se prostě nevyplácí. Doporučuje se alokovat prostor pro celé pole a při potřebě změny velikosti udělat realloc() na dvojnásobnou, resp. poloviční velikost.

#11 Kit
souhlasím, včera jsem ty pointery vyřešil mám  to hotové bez struktury jen holé  

pointer1+slovo0 , pointer2+slovo1....pointer poslední+slovo předposlední , pointer=0 slovo poslední

samozřejmě s uložením startovního pointeru pro další práci a následné uvolnění

#12 MilanL
Takže tu strukturu vyrábíš "ručním" čarováním s pointery, abys ušetřil práci překladači :-)

#13 gna
Vytváření vlastních abstraktních datových struktur je náhodou dobrým cvičením.

Mě šlo vlastně o to zredukovat to několikanásobné procházení zdrojovým textem:

1.průchod - počítání slov

2.průchod - počítání znaků

3.průchod - kopírování slova vnořený ve 2., ať už pomocí memcpy nebo znak po znaku

Myslel jsem i na další varianty

spočítání znaků a slov, alokace pole na pointery a pole pro kopii věty, kopie věty s nahrazením delimiterů a uložením začátků slov do pole pointerů opět 3 průchody počítání/kopírování/náhrada delim s uložením pointerů

další 2 průchodový algoritmus byl se zásahem do původního 

1 průchodové varianty by se také našly ví o dvou
- alokovat pole pointerů a cílového řetězce určité velikosti a rovnou kopírovat, nahrazovat delimitery a ukládat pointery, při překročení kapacity pole pointerů nebo cíle realokovat na vyšší kapacitu

- struktura 2x char** první ukazuje na slovo, druhý na další strukturu  opět s alokací a realokací cílového řetězce

jako představit si to dokážu, ale jde občas o ty operace a pointery.

#16 MilanL
Ty jednoprůchodové varianty máš správně. První používá např. Perl, druhou Lisp.

#17 Kit
no když by se ty alokace udělali dostatečně velké dalo by se i těm realokacím vyhnout případně hodně omezit jejich potřebu, např char** pro 100 slov a char* pro cíl třeba 128-1024

#18 MilanL
Ano, tohle je také používané řešení, například u databází. Udělá se chunk vhodné velikosti a následně se uspořádají třeba do B-stromu. Je výhodné, pokud jsou všechny stejné velikosti, protožprotožprotože tak nedochnedochází k fragmentaci.