Forum Mjukvara Programmering och digitalt skapande Tråd Inlägg

Länkad lista [C++]

1
Skriv svar
Permalänk
Medlem
●

Länkad lista [C++]

Har problem med en enkellänkad lista i C++.
Varning för mycket okommenterad kod. ^^-~
Får en core-dump när element skall läggas till i listan. Kan någon kanske hjälpa mig lite med att se varför jag inte kan lägga till ett nytt element?
Kan antagligen inte ta bort element heller.

Körning ger:

Lägg till: 34
På position: 0
Segmentation fault (core dumped)
//Constructor
List::List()
{
   size = 0;
   head = 0;
}

//Destructor
List::~List()
{
   for(int i=0; i<getSize(); i++)
   {
      remove(i);
   }
}

void List::insert(Element e, int position)
{
    Node *tempnod, *newNode = new Node;
    tempnod = getNode(position);
    newNode = getNode(position);
    if (position == 0)
    {
        newNode->next = tempnod;
    } else {
        newNode->next = getNode(position+1);
    }
    newNode->data = e;
    size++;
}

void List::remove(int position)
{
    Node *tempnod, *toRemove = getNode(position);
    if (position == 0)
    {
        head = toRemove->next;
    } else {
        tempnod = getNode(position-1);
        tempnod->next = toRemove->next;
    }
    delete toRemove;
    toRemove = 0;
    size--;
}

Node* List::getNode(int position)
{
   Node *temp = head;
   for( int i=0; i<position-1; i++)
      temp = temp->next;
   return temp;
}

void List::sort()
{
   Node *temp, *Node1, *Node2;
   int i, n;
   for (i=0; i<size-1; i++)
   {
      for (n=0; n<size-1; n++)
      {
         Node1 = getNode(i);
         Node2 = getNode(n);
         if (Node1->data > Node2->data)
         {
            temp = Node1;
            Node1 = Node2;
            Node2 = temp;
         }
      }
   }
}

bool List::isElement(Element e)
{
    for (int i=0; i<size; i++)
    {
       Node *pos = getNode(i);
       if (pos->data == e)
          return true;
    }
    return false;
}

int List::getPosition(Element e)
{
    int i;
    Node *temp;
    for ( i=0; i<size; i++)
    {
        temp = getNode(i);
        if (temp->data == e)
           return i;
    }
    return -1;
}

bool List::isEmpty()
{
   if (size>0)
      return false;
   return true;
}

int List::getSize()
{
   return size;
}

int List::getElement(int position)
{
   Node *temp = getNode(position);
   return temp->data;  
}

Klassen Lista:

class List
{
      public:
             typedef int Element;

             List();
             
             ~List();

             void insert(Element e, int position);

             void remove(int position);

             void sort();

             int getPosition(Element e);

             bool isEmpty();

             bool isElement(Element e);

             int getSize();

             int getElement(int position);
         
      private:
            Node *getNode(int position);
       
            Node *head;  // Pekar på första noden.

            int size;        
};

Edit:
Glömde klassen Node

class Node
{
    friend class List;

    private:
            int data;
            Node* next;
};
Visa signatur

Light travels faster than sound. Is that why some people appear to be smart before they speak?
It's a big rock. I can't wait to tell my friends. They don't have a rock this big.

Redigera
Citera flera Citera
Permalänk
Medlem
●

newNode = getNode(position);
Varför gör du det e.g.? (I insert funktionen)

Visa signatur

I just love the fact that there is a global integer variable named 'i'. Just think, you will never need to declare your loop variable again!
To avoid collisions where a loop that uses 'i' calls another function that loops with 'i', be sure to stack 'i' and restore it when your function exits.

Redigera
Citera flera Citera
Permalänk
Medlem
●

Du måste ju kolla om (node)->next innehåller en nod eller inte överallt i koden... Speciellt i getNode();

Redigera
Citera flera Citera
Permalänk
Medlem
●

Du vet om att std::list finns va? Men det är bra att veta hur man gör en länkad lista såklart, men sen när du vet det

Redigera
Citera flera Citera
Permalänk
Medlem
●
Citat:

Ursprungligen inskrivet av Myris
newNode = getNode(position);
Varför gör du det e.g.? (I insert funktionen)

För att få en pekare till den nya noden.

Edit: Ereinion, jo jag vet, men om man alltid använder sig av fördefinerade saker så sitter man hjälplös när dessa inte finns att tillgå ^^.

Senast redigerat
Visa signatur

Light travels faster than sound. Is that why some people appear to be smart before they speak?
It's a big rock. I can't wait to tell my friends. They don't have a rock this big.

Redigera
Citera flera Citera
Permalänk
Medlem
●

Hmm... först gör du detta:
newNode = getNode(position);
Sen ändrar du dess data och dess next-pekare, varför då göra getNode först?

Men iaf, har du ingen debugger så du kan stega till dit det blir fel?

Visa signatur

I just love the fact that there is a global integer variable named 'i'. Just think, you will never need to declare your loop variable again!
To avoid collisions where a loop that uses 'i' calls another function that loops with 'i', be sure to stack 'i' and restore it when your function exits.

Redigera
Citera flera Citera
Permalänk
Medlem
●

Nej.

Däremot har jag skrivit om funktionen, så det nästan verkar funka.
Det tar typ 20 sekunder, men det krashar inte... utom när jag ska skriva ut listan.

void List::insert(Element e, int position)
{
    Node *newNode = new Node;
    Node *tempnode = getNode(position);
    if (tempnode == tail)
    {
        tail->next = newNode;
        tail = tail->next;
        tail->next = 0;
    }
    else if (tempnode == head)
    {
        head = newNode;
        head->next = tempnode;
    }
    else
    {
        newNode->next = tempnode;
        tempnode = getNode(position-1);
        tempnode->next = newNode;
    }
    newNode->data = e;

    size++;
}

void List::remove(int position)
{
    Node *tempnod, *toRemove = getNode(position);
    if (toRemove == head)
    {
    	tempnod = head;
    	head = head->next;
    	delete tempnod;
    } else if (toRemove == tail)
    {
    	tempnod = tail;
        tail = getNode(position-1);
    	tail->next = 0;
    	delete tempnod;
    } else
    {
        tempnod = getNode(position-1);
        tempnod->next = toRemove->next;
        delete toRemove;
    }
    current = head;
    size--;
}
Visa signatur

Light travels faster than sound. Is that why some people appear to be smart before they speak?
It's a big rock. I can't wait to tell my friends. They don't have a rock this big.

Redigera
Citera flera Citera
Permalänk
Medlem
●

Lite ändring bara:

Antar att det retuneras 0 om tex getNode(-5) anropas
Du börjar index "utifrån" på 1!?
Om du ger en högre position än vad som finns vad ska hända då?
Kasta ett exception ?
Gör detta först i metoden om du vill kasta exception,
/*
if(position>=size)
{
String s = "Position does not exsist"
throw s;
}
*/

void List::insert(Element& e, int position)
{
//Om positionen inte finns, bör vara exception eller gör metoden till bool
if(position>=size) retrun;

Node *newNode = new Node;

Node *before_ins = this->getNode(position-1);
if(before_ins == 0) //head
{
newNode->next = head;
head = newNode;
}
//om du har satt head till 0 från början så kommer alltid sista nodens next vara 0
//alltså kvittar det om det är tail eller mitt i vi ska inserta
else
{
newNode->next = before_ins->next;
before_ins->next = newNode;
}
newNode->data = e;

size++;
}

void List::remove(int position)
{
//Om listan är tom eller elementet inte finns gör inget. Bra att göra om metoden till bool...
if(posistion>=size || head == 0) return;

Node *beforeRemoveNode = this->getNode(position-1);
if (beforeRemoveNode == 0)
{
beforeRemoveNode = head->next;
delete head;
head = beforeRemoveNode ;
}
else
{
Node *remove = beforeRemoveNode->next;
beforeRemoveNode->next = beforeRemoveNode->next->next;
delete remove;
}
size--;
}

Visa signatur
Redigera
Citera flera Citera
1
Skriv svar
Senaste nyheterna
Hårdvara
Mjukvara
Övrigt
Nytt i forumet
Datorkomponenter
System
Ljud, bild och kommunikation
Spel och mjukvara