[c#] double linked list

glennox · 24 Januari 2012

Beste mede forumers,

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

PHP

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;
        }


    }

Toon Meer

Hier onder mijn implementatie van c# double linked list.

PHP

//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);

Toon Meer

Darsstar · 25 Januari 2012

Een linked list is een opject dat een verwijzing heeft naar de eerste node van de lijst die het voorstelt. Elke node heeft een verwijzing naar de volgende node in de lijst. Handig voor een stack bijvoorbeeld.

Een doubly linked list is een linked list waar elke node een verwijzing naar de volgende EN vorrige node heeft. Je list object verwijst dus nog steeds naar de eerste node.

Een double ended list is een list object waar je naar zowel de eerste en de laatste node van de lijst een verwijzing bevat. Erg fijn voor een queue.

Hier kun je natuurlijk wanneer gewenst gesorteerde varianten van maken. Bij het inserten van een nieuwe waarde in de lijst begin je bij de eerste node op de lijst.
- Als de nieuwe waarde kleiner (of hoe je de lijst wilt sorteren) is zet je list.first in newNode.next waarna je list.first overschrijft met newNode. (mFore())
- Als de nieuwe waarde groter is loop je door de list tot het niet zo is en stop je de nieuwe tussen de twee nodes.
- Als de nieuwe waarde groter is dan elke andere waarde in je lijst voeg je een nieuwe node toe op het eind.

Het eerste wat mij opvalt is dat jij de node en list gecombineerd hebt. Het tweede is dat je variabele geen beschrijvende naam geeft. (Of ik ken C# conventies niet.)
Als je een gesorteerde list wilt hebben, dan wil je niet dat programmeurs zelf methods als mFore() mTween() en mHind() aan kunnen roepen. Of toegang hebben tot pL en pR. Al snap ik dat je nu alleen wilt leren hoe het werkt.

Je kunt hier een voorbeeldje aan nemen

PHP

class LinkedList {


    public Node first = null;


    public void insert(int value)
    {
        Node newNode = new Node(value);


        if (first == null)
        {
            first = newNode;
            return;
        }


        newNode.next = first;
        first = newNode;
    }
}


class SortedLinkedList : LinkedList {


    public void insert(int value)
    {
        if (first == null || value < first.value)
        {
            return base.insert(value);
        }


        Node newNode = new Node(value);
        Node current = first;


        while (current.next != null)
        {
            if (value < current.next.value)
            {
                newNode.next = current.next;
                current.next = newNode;
                return;
            }


            current = current.next;
        }


        current.next = newNode;
    }
}


class Node {


    public int value;
    public Node next = null;


    public Node(int v)
    {
        value = v;
    }
}

Toon Meer

Ps. ik ben onder andere bekend met JAVA, PHP en C niet met C# al heb ik wel snel wat dingen opgezocht. Ik ga niet garanderen dat er geen fouten in zitten en het gaat ook vooral om het idee.

DNS update Directadmin

Graag advies voor mijn website

Ik wil op afstand studeren, kennen jullie Tech?

PC probleem

Let op Vimexx klanten

wie kan mij helpen met Security aanscherpen voor nmijn website

Ik ben op zoek naar een goede hosting

App bouwer gezocht

Dating software

250 Nieuwe domeinnamen April 2024

Xenforo buckaroo plugin

[c#] double linked list

Participate now!

ING Nederland streeft naar ondersteuning van Google Pay tegen eind februari

Het Belang van Standaardisatie

De Revolutionaire Rol van IT in Alzheimeronderzoek

Functioneel ontwerp

Access Control List implementatie in PHP/MySQL - deel 1/2

Access Control List implementatie in PHP/MySQL - deel 2/2

Delen

Gebruikers die dit topic bekijken