|
Vi har fått uppgift att skapa en Linked List och Binärt Sökträd.
Linked List är:
En länkad lista är en dynamisk datastruktur som används inom programmering. Att den är dynamisk innebär att den enkelt kan öka och minska i storlek efter behov, till skillnad från till exempel en array, som har en fix storlek. I en länkad lista kan även element läggas till och tas bort i mitten.
En länkad lista innehåller noll eller flera noder. En nod består av två fält; ett informationsfält och ett adressfält. Informationsfältet är det data som ska sparas. Adressfältet innehåller adressen till nästa nod i listan eller ett speciellt värde, null, om det inte finns fler noder.
#Wikipedia
Binary SearchTree
Ett binärt sökträd är ett binärträd (dvs varje nod har högst två barn) med följande egenskaper:
- varje nod har ett värde.
- det högra delträdet till en nod innehåller bara värden som är högre än värdet i noden.
- det vänstra delträdet till en nod innehåller bara värden som är lägre än värdet i noden.
Binära sökträd är användbara eftersom det finns effektiva sökalgoritmer som kan användas på dem. I genomsnitt är algoritmen av ordning Θ(log n) och i värsta fall Θ(n).
#Wikipedia
Jag började med att göra Linked List men avbröt min programmering för att göra klart komplettering i spelprogrammering 2. Men det jag har gjort är:
struct Node
{
T NewNode; //Tommi sa att vi skulle utgå irån att använda int så det är vad jag tänker göra varje gång jag skapar en ny nod.
Node* FirstNode; //En pekare till första noden i listan <——–Behöver inte vara med i structen
Node* CurrentNode; //En pekare till den noden man är på <——–Behöver inte vara med i structen
Node* NextNode; //En pekare till nästa nod
};
Node* m_node;
public:
Lista()
{
//m_node = new Node();
//m_node->FirstNode = NULL;
//m_node->CurrentNode = NULL;
}
~Lista()
{
}
void AddNode(int tal1) //Lägga till en node
{
Node* node = new Node(); //Skapar en ny nod
node->NewNode = tal1; //sätter värdet på noden som man matar in i konsolen
node->NextNode = nullptr; //Går vidader till nästa element och pekar på NULL så länge
if ( node->FirstNode != NULL) // Om FirstNode hittar något att peka på
{
CurrentNode = FirstNode; //Om FirstNode pekar på något så ska den noden vi jobbar med också peka på den
while (CurrentNode->NextNode != NULL) //Kolla om vi är på slutet av listan (Så länge nuvarande noden inte är NULL)
{
CurrentNode = CurrentNode->NextNode; //När den kommer till slutet av listan så tar den det tomma utrymmet
}
CurrentNode->NextNode = node; //Efter att ha gått igenom till sista platsen i listen så sätts värdet på den nya noden
}
else //Om det är första noden kommer den skapa FirstNode som första noden
{
node->FirstNode = node->NewNode;
}
CurrentNode = node; //Sätter nästa nod till Current ifall man ska lägga till fler tal så kommer den peka vidare till nästa.
}
void DeleteNode(int tal1) //Peka på NULL deleta nod
{
}
void Testalista()
{
}
Jag vet att det är fel på mina pekare men jag har inte rättat till det än
 
About Folke Stövring Nielsen
2014 Programming
|
