[c#] double linked list

[glennox]

Beste mede tweakers,

Ik zoek jullie hulp voor mijn probleem. Door mijn docent programmeren is het aangeraden om eens uit te zoeken hoe een double linked list werkt, en deze vervolgens uit te programmeren zodat ik een voorsprong kan op bouwen voor komend jaar aangezien we dan een binary tree moeten uit programmeren om zo kennis over algoritmes op te doen.

In theorie lijkt de double linked list helemaal niet zo moeilijk, maar in de praktijk valt het toch wel een stukje tegen. De eerste 2 nodes gingen vrij makkelijk omdat ik de logica hiervan zag

Mijn probleem waar ik tegen aan loop is dat ik niet hoe ik nou kan zien of een getal achter gezet moet worden(hind) of voor gezet moet worden (fore) of ergens tussen gezet moet worden (tween)

Wat ik van plan ben te doen is 2 listboxjes, 1 met random getallen en de ander met de door de linked list gesorteerde uitkomst.

Ik hoop dat iemand de moeite wil en zou kunnen nemen om mij met dit probleem te helpen.

Hier mijn klasse cnode

C#:

class cNode
    {
        public static cNode[] nar;
        public cNode pL, pR;
        public int pw;

        public static cNode v,m,a;

        public cNode(cNode L, int w, cNode R)
        {
            pL = L;
            pR = R;
            pw = w;
        }

        public static void mTween(int x)
        {
             //nog verder uit te programeren
        }

        public static void mFore(int x)
        {
            m.pL = nar[x];
            nar[x].pR = m;
            v = nar[x];

        }
        public static void mHind(int x)
        {
            m.pR = nar[x];
            nar[x].pL = m;
        }

    }

Hier onder mijn implementatie van c# double linked list.

C#:

          //clear zooi
            lbU.Items.Clear();
            lbS.Items.Clear();
            //WAT TE DOEN
            //vul linker random

            Random r = new Random();
            int n = 4;
            for (int T = 0; T < n; T++)
            {
                lbU.Items.Add(r.Next(0, 10));
            }

            //make dllist en voeg alle items in
            cNode.nar = new cNode[n];
            //MAAK nulde NODE (VOORSTE)
            cNode.nar[0] = new cNode(null, (int)lbU.Items[0], null);
            cNode.v = cNode.nar[0];
            cNode.m = cNode.v;
            cNode.a = cNode.v;
            //rest nodes aanmaken en plaatsen
            //maak node 1
            int tpw = (int)lbU.Items[1];
            cNode.nar[1] = new cNode(null,tpw, null);
            //fore, hind
            if (tpw > cNode.v.pw)
            {
                //groter
                cNode.mHind(1);
            }
            else
            {
                //kleiner of gelijk
                cNode.mFore(1);
            }
            //loop langs rest
            //2e en verder
            for (int i = 2; i < n; i++)
            {
                int pw = (int)lbU.Items[i];

                cNode.nar[i] = new cNode(null, (int)lbU.Items[i], null);
                
                while (cNode.m.pR != null)
                {
                    if (pw > cNode.m.pw && cNode.m.pR != null)
                    {
                        cNode.m = cNode.m.pR;
                    }
                }
            }


            //******
            //uitlezen;
            for (cNode.m = cNode.v; cNode.m.pR != null; cNode.m = cNode.m.pR)
            {
                lbS.Items.Add(cNode.m.pw);
            }
            lbS.Items.Add(cNode.m.pw);

[pedorus]

Tijd om wat te lezen dan. Ik zou zeggen begin met MSDN: General Naming Conventions want duidelijk is dit allemaal niet. Voor de rest zou ik eens kijken naar Wikipedia: Doubly linked list of zelf een antwoord verzinnen. En misschien is MSDN: An Introduction to C# Generics ook wel interessant.

Een linked list hoeft niet perse gesorteerd zijn ofzo, of is dat een bepaalde opdracht?

[glennox]

Wikipedia heb ik door gelezen aan de hand daarvan ben ik hierop gekomen, ik dacht dat ik op de goede weg was. Maar schijnbaar kan ik beter alles weggooien en helemaal overnieuw beginnen? Het was wel mijn bedoeling om een aantal random getallen te sorteren met de linked list. Maar het liefste zou ik willen dat jullie mij hiermee helpen. Indien dit niet mogelijk is zal ik het overwegen om over nieuw te beginnen, de leraar zei dat ik goed op weg was met mijn class.

[alex3305]

Leuk dat je een double linkedlist wilt maken, maar zoals pedorus zegt zou ik eerst beginnen aan wat basale kennis. public accessors op variabelen is bijvoorbeeld nooit handig. Daar zijn eventueel properties voor uit gevonden. Gebruik daarnaast gewone variabel namen in plaats van eenletterige namen. Dit is namelijk voor een outsider niet te lezen. Ook je functienamen is niet echt volgens de Microsoft-conventies.

Naar mijn mening kun je dus beter eerst het een en ander aanpassen en verduidelijken voordat je gaat beginnen met algoritmiek. Er is namelijk toch geen performance verschil tussen i of index tijdens een for-loop. En houdt het gewoon duidelijk .

[RobIII]

* RobIII sluit zich aan bij wat ^ zij zeggen.

glennox schreef op woensdag 25 januari 2012 @ 00:11:
Maar het liefste zou ik willen dat jullie mij hiermee helpen.

Mja, nee, sorry. We wijzen je graag in de juiste richting bij concrete vragen maar we zitten hier uitdrukkelijk niet om handjes vast te houden of je huiswerk te (helpen) maken. Waarom begin je niet eens met debuggen (Debuggen: Hoe doe ik dat?) en probeer je uit te vinden wat er wel/niet werkt en waarom wel/niet? Ik zou overigens ook overwegen even from scratch te beginnen; het is maar een paar regels code en niet alsof je 2 manweken weggooit en de vorm die 't nu heeft is niet bepaald helder, leesbaar of overzichtelijk.

glennox schreef op woensdag 25 januari 2012 @ 00:11:
Indien dit niet mogelijk is zal ik het overwegen om over nieuw te beginnen, de leraar zei dat ik goed op weg was met mijn class.

Leraren zeggen helaas wel meer moet ik je uit ervaring vertellen; we zien zat topics hier met de regelmaat van de klok voorbij komen waar de leraren geen enkel benul hebben waar ze 't over hebben. Ik zeg niet dat dat in jouw geval zo is, maar ga er zeker niet blind op af en wees alsjeblieft kritisch bij alles wat hij/zij je vertelt.

glennox schreef op dinsdag 24 januari 2012 @ 23:27:
Hier onder mijn implementatie van c# double linked list.

Euh; nee. Dat is geen "implementatie van c# double linked list" (die staat erboven; althans je poging ertoe ), wat er onder die zin staat is een stuk (geflanste if you don't mind me saying) code die je double linked list tracht te gebruiken.

Tot slot zou ik niet testen met lisboxes e.d. (hoewel dat misschien de zaak leuk 'inzichtelijk' maakt, gebruik gewoon een debugger (en veel beter dan die in Visual Studio ga je niet snel vinden dus daar ligt 't niet aan)) maar met unittests.

Of lever gewoon dit in: MSDN: LinkedList(T) Class (System.Collections.Generic)

[ Voor 24% gewijzigd door RobIII op 25-01-2012 00:42 ]

[acemoo]

Een double linked list is toch gewoon een data structuur?
Lijkt me niet helemaal de bedoeling om je data structuur iets te laten sorteren.
Gelukkig doe je dat ook niet, maar wat je precies wel doet.. geen idee, geen zin om die code te ontcijferen.
Maak een mooie functie sorteer die als input een ongesorteerde lijst krijgt en als output een gesorteerde lijst geeft zou een goeie oplossing kunnen zijn. 2e stap zou dan kunnen zijn ascending en descending sorting toe te kunnen passen.
Ook dacht ik dat een double linked list alleen voor en achteraan iets kon plakken? niet ergens in het midden.

[kutagh]

Eerste probleem wat ik zie is dat je 2 concrete problemen behandelt alsof het 1 probleem is:
-Hoe sorteer je een lijst van random getallen?
-Hoe maak je een dubbel gelinkte lijst?

Een dubbel gelinkte lijst is op zich eenvoudig te programmeren, als de voorwaarde is dat elke node de node ervoor en erachter kan bereiken.

Vervolgens moet je kijken naar hoe je een dubbel gelinkte lijst kunt sorteren. Er zijn hier verschillende mogelijkheden voor, onder andere (excuus voor de vakjargon) insertion sort, merge sort, bubble sort etcetera.
Het eenvoudigste zou zijn om van begin tot eind te lopen en nodes die een lagere waarde hebben dan de vorige node dichterbij naar het begin te schuiven tot de vorige node lager is dan de eigen node en de volgende node gelijk aan of hoger is dan de eigen node. Hoe je dat implementeert mag je zelf uitzoeken (hint, probeer niet alles tegelijkertijd te doen maar breek het eerst op in onderdelen).

@Br men: Het is niet per se zo dat je alleen aan het begin of eind kunt plakken, het kan ook prima in het midden (zie ook LinkedList.AddBefore() en LinkedList.AddAfter())

[ Voor 8% gewijzigd door kutagh op 25-01-2012 00:44 ]

[acemoo]

kutagh schreef op woensdag 25 januari 2012 @ 00:43:
@Br men: Het is niet per se zo dat je alleen aan het begin of eind kunt plakken, het kan ook prima in het midden (zie ook LinkedList.AddBefore() en LinkedList.AddAfter())

Klopt ja, addBefore en addAfter goeie methodes, ik kon er alleen niet ff zo 123 op komen na het lezen van mtween

[RobIII]

kutagh schreef op woensdag 25 januari 2012 @ 00:43:
Vervolgens moet je kijken naar hoe je een dubbel gelinkte lijst kunt sorteren. Er zijn hier verschillende mogelijkheden voor, onder andere (excuus voor de vakjargon) insertion sort, merge sort, bubble sort etcetera.
Het eenvoudigste zou zijn om van begin tot eind te lopen en nodes die een lagere waarde hebben dan de vorige node dichterbij naar het begin te schuiven tot de vorige node lager is dan de eigen node en de volgende node gelijk aan of hoger is dan de eigen node. Hoe je dat implementeert mag je zelf uitzoeken (hint, probeer niet alles tegelijkertijd te doen maar breek het eerst op in onderdelen).

Voor 't sorteren kun je natuurlijk ook gewoon IComparable implementeren (zie hier). Het is natuurlijk afhankelijk van de opdracht of dat toegestaan is of niet.

@TS: Ondanks dat ik 't netjes vind dat je niet "spiekt" bij de vele, véle, online beschikbare voorbeeld/demonstratie/tutorial-implementaties (of je hebt de moeite nog niet genomen 't te googlen...?) zou je deze natuurlijk wél kunnen gebruiken om inspiratie op te doen of om van te leren.

[ Voor 12% gewijzigd door RobIII op 25-01-2012 01:02 ]

[farlane]

implementeer het ding in C of C++; heb je iig geen last van mensen die over MS coding guidelines beginnen.

[Oguz286]

No offence, maar iemand die op dit moment moeite heeft met het implementeren van een double linked list in C# zou ik dus echt niet aanraden om het in C(++) te gaan doen. Zelfs de meeste studenten Technische Informatica denken als ze het woord pointer horen

Zoals de anderen hebben aangeraden:
• Implementeer eerst een double linked list.
• Implementeer ook handige methoden (addBefore etc.)
• Zoek wat sorteeralgoritmen op en implementeer er een (of meerdere van).

[aCb1780]

Ik zou het in C proberen te implementeren.

Dat is wel wat moeilijker maar dan snap je wat een (double) linked list doet en waar je hem kan gebruiken.

Een struct met data, *prev en *next en knallen maar.

En dan kan je heel die LinkedList klasse van C# zelf in C schrijven.

[Amras]

aCb1780 schreef op woensdag 25 januari 2012 @ 12:39:
Dat is wel wat moeilijker maar dan snap je wat een (double) linked list doet en waar je hem kan gebruiken.

Waarom zou je dit niet snappen als je hem in C# implementeert?

Volgens mij maakt de taal weinig uit, het gaat erom dat je weet hoe zo'n double linked list werkt onder water. Gewoon de taal gebruiken die je beheerst.

[RobIII]

aCb1780 schreef op woensdag 25 januari 2012 @ 12:39:
Ik zou het in C proberen te implementeren.

Dat is wel wat moeilijker maar dan snap je wat een (double) linked list doet en waar je hem kan gebruiken.

Een struct met data, *prev en *next en knallen maar.

En dat kan allemaal niet in C# omdat ... En waarom zou je 't wél snappen als je 't in C schrijft en niet (of minder goed) als je 't in C# schrijft Los van 't feit dat 't al in de BCL zit uiteraard; voor educatieve doeleinden kun je zo'n ding prima in C# (of eender welke taal for that matter) schrijven.

[ Voor 9% gewijzigd door RobIII op 25-01-2012 12:54 ]

[farlane]

Oguz286 schreef op woensdag 25 januari 2012 @ 11:43:
No offence, maar iemand die op dit moment moeite heeft met het implementeren van een double linked list in C# zou ik dus echt niet aanraden om het in C(++) te gaan doen.

Afgezien van het feit dat ik het niet met je eens ben, is dat niet het punt wat ik probeerde te maken.

[Oguz286]

farlane schreef op woensdag 25 januari 2012 @ 13:22:
[...]
Afgezien van het feit dat ik het niet met je eens ben, is dat niet het punt wat ik probeerde te maken.

Dat begreep ik Ik wilde reageren op wat jij zei en ook wat anders zeggen, maar die twee liepen door elkaar

Ik snap alleen niet waarom mensen ineens niet zouden zeuren over codingstandaarden als hij C(++) zou gebruiken. Ik vind zijn code niet leesbaar en zou dat nog steeds niet vinden als het in C(++) was geschreven. In het geval van C(++) zouden mensen zeggen dat hij get/set methoden zou moeten implementeren i.p.v. variabelen public te maken.

Ergens kan ik het begrijpen dat als je princiepe van een pointer kent, dat zo'n linked list ineens makkelijker te begrijpen zou zijn. Maar alle geheugen (de-)allocatie die daarbij komt kijken is de moeite niet waard en is het m.i. beter om het in een managed taal met garbage collection te doen. Helaas is daarbij het probleem dat mensen dan veel geheugen inefficiente dingen kunnen gaan doen omdat ze weten dat de garbage collector hun troep opruimt.

Dus ik ben het er wel mee eens dat een linked list implementeren in C(++) je beter leert hoe het werkt, omdat je moet weten wat een pointer is, maar je moet dan gelijk ook leren hoe new en delete werken en waarom je het moet gebruiken.

EDIT: @Caelorum: hopen ja

[ Voor 7% gewijzigd door Oguz286 op 25-01-2012 15:18 ]

[Caelorum]

Oguz286 schreef op woensdag 25 januari 2012 @ 14:01:
[...]Helaas is daarbij het probleem dat mensen dan veel geheugen inefficiente dingen kunnen gaan doen omdat ze weten dat de garbage collector hun troep opruimt.[...]

[..]omdat ze hopen dat de garbage collector hun troep opruimt.
Ik vind het altijd jammer als mensen met C# bezig zijn en niet weten hoe de GC werkt. Dan krijg je van die enorm trage inefficiënte algoritmes terwijl het helemaal niet nodig is.