Arrays og lenket liste i C

Har du noe lurt å dele med oss? NB. Dette er ikke et support forum.

Arrays og lenket liste i C

Innleggav moma » lør 29.10.2005 17:33

Kan hende at dette er av begrenset interesse...

-- Story beg --
Dette er ikke noe spørsmål eller forslag.

Bare koding i C:
Jef fikk et instant behov for en utvidbar (dynamisk) og generell "array" så jeg laget like godt en ny implementasjon for mitt prosjekt. Laget også en dobbelt lenket Liste. Det var av viktighed at disse (Parray og Pliste) kan holde pekere til hvilken som helst type data og at elementene kan holdes sortert.
----

Parray er meget rask. Den benytter en binær søkealgoritme O(log2) når den søker og holder data i sortert rekkefølge.

Parray (array of pointers):
parray.h og parray.c
----

PList er mæget treg til å søke. Den gjør et lineært løp O(n) når den søker og ordner data. Fordelen er at Plist kan holde svære mengder data (gjerne usortert data).

Kan hende at jeg reduserer søketiden til ~ O(n/2) ved å legge til en ekstra variabel (i plist_h) som peker alltid midt på lista. 2 ekstra variabler vil dele lista i 3 deler. Den vil gi ~ O(n/3). Listen må være sortert.

PList (list of pointers)
plist.h og plist.c

Har testet både plist og parray med vanlig data og allskens grenseverdier. Neste trinn er å la Valgrind... sjekke minneallokering (evt. bruker også Electric fence... eller dmalloc...). Benytter alltid GDB... i C prosjekter.

Feilhåndtering må også forbedres, men jeg er optimist å få det til.

All kode er GPL:
EDIT: Koden er flyttet til: http://www.futuredesktop.org/adt/

-- Story end --
Sist endret av moma den ons 15.02.2006 13:33, endret 1 gang

Erfaren
Brukerens avatar
medlem i 234 måneder
 

Innleggav ak » man 31.10.2005 7:18

Svært sannsynlig at du allerede kjenner til dette, men dette er en av favoritt-algoritmene hvor jeg studerer.

Red-black tree:
http://en.wikipedia.org/wiki/Red-black_tree

Administrator
Brukerens avatar
medlem i 236 måneder
 

Innleggav moma » man 31.10.2005 8:44

Takker så meget for info.

Den er rask med garantert maks. søketid (i.f.t treets høyde), men kompleks fordi den omrokkerer (roterer) noder etter insert og delete.

BARE EN TANKE:
Red-black-treet kan lett brukes for både SORTERT og USORTERT data. For usortert data, hver node bør ha en (unsigned integer) variabel (en teller) som ordner og putter inn nodene i _inserted rekkefølge_. Telleren løper fra 0,1,2,...n.

Man kan da lett liste ut nodene i samme (inserted) rekkefølge ved å utføre "in-order" traversal av treet.

Se: http://en.wikipedia.org/wiki/Tree_traversal
Kode: Merk alt
visit_inorder(node)
    if node.left  != null then visit_inorder(node.left)
    print node.value
    if node.right != null then visit_inorder(node.right)
--
Den interne telleren er helt transparent for programmereren og treet kan brukes som en LISTE eller enslags ARRAY.
Sist endret av moma den ons 15.02.2006 13:32, endret 2 ganger.

Erfaren
Brukerens avatar
medlem i 234 måneder
 

Innleggav moma » ons 15.02.2006 12:28

Hei alle,

Jeg trenger hjelp til en bitteliten TEST.

Jeg har laget en tar.gz pakke av noe c-kode for 3 abstrakte datatyper (array, dobbelt lenket liste og et binært søketre). Kunne du vennligst laste ned pakken og teste om den kompilerer og utfører på din maskin.
;-) ;-) ;-)

Hent pakke: http://www.futuredesktop.org/adt/adt-0.1.tar.gz

Instruksene finner du i README filen.
Kjør alle 3 tester.
Den siste, ptree_test'en er nokså interessant fordi den genererer noen svg-bilder som viser hvordan et Red-Black-balansert søketre oppfører ved insert og delete.

Merk: Koden til "ptree.c" (et binært søketre med sk. red-black balanseringsalgoritme) har jeg stort-sett (så-å-si 100%) kopiert fra eksistende kilder på internett. Likevel, jeg har lært nokså mye om R & B balansering, men må innrømme at algoritmen er nokså kinkig, spesielt delete-delen av det. Dok ikke helt umulig å fatte.

Les: http://en.wikipedia.org/wiki/Red-Black_tree

SVG-grafer er selvfølgelig en bra debugging-metode.
Et bilde:
Bilde

Øvelser:
http://www.ibr.cs.tu-bs.de/courses/ss98/
--------------------------------

Fungerer det ?
Sist endret av moma den fre 28.04.2006 8:41, endret 2 ganger.

Erfaren
Brukerens avatar
medlem i 234 måneder
 

Innleggav ak » ons 15.02.2006 16:45

Fungerer bra på x86_64-pc-linux-gnu-3.4.4

Eye of GNOME klarer å vise dem også, for de som ikke har Inkscape inne (enda)

Brukte Red-Black trær for å holde styr på prosesser og andre køer i et lite operativsystem jeg skrev før jul. Det hendte at det gikk litt stokk over stein ;)

Administrator
Brukerens avatar
medlem i 236 måneder
 

Innleggav moma » ons 15.02.2006 18:03

ak skrev:Fungerer bra på x86_64-pc-linux-gnu-3.4.4
Eye of GNOME klarer å vise dem også, for de som ikke har Inkscape inne (enda)

Veldig smart tips.
Starter bare Nautilus og åpner første tegningen "tree00.svg" i image viewer. Trykker deretter [Next>] knappen.

Var også innom Edit -> Preferences menyvalget og satte verdien på "Transparent parts" til "as background". (om det skulle bety noe)

Takk ak. Fint at du testet på 64 bits :--)
Nå kan jeg begynne med neste prosjekt.

Erfaren
Brukerens avatar
medlem i 234 måneder
 


Returner til Tips og triks / Favoritter



Hvem er i Forumene

Registrerte brukere: Google [Bot]



cron