Ερωτήσεις πάνω σε ουρά- διπλά συνδεδεμένη λίστα σε C++

[realez]

Καλησπέρα προσπαθώ να υλοποιήσω μια ουρά με διπλά συνδεδεμένη λίστα σε c++(πάνω στην οποία έχω λίγες γνώσεις). Αν μπορείτε πείτε μου αν η συνάρτηση enqueue(εισαγωγή στοιχείου στο τέλος της λίστας) είναι σωστή. Αν είμαι σίγουρος πως είναι σωστή θα μου είναι πολύ πιο εύκολο να φτιάξω τις ύπόλυπες συναρτήσεις.(η main είναι υπό κατασκευή ακόμα)

 

>
#include <iostream>
#include <cstdlib>
using namespace std;

class dll
{
   private:
       struct node
    {
   	    int item;
   	    node *next;
   	    node *prev;
    };
       node *head;
       node *tail;
      
   public:
       dll();
       bool isEmpty();
       void Enqueue(int& element);   
       int Dequeue();
       int First();
       int Last();
       int Search(int element);
       void Print();
       void Destroy();       
   };
  
   dll::dll()
   {
       head = NULL;
       tail = NULL;
   }
  
   bool dll::isEmpty()
   {
       return (head == NULL) ? true : false; //Ama iso true alliws false
   }
  
   void dll::Enqueue(int& element)
   {
       if(isEmpty())
       {
           node *temp = new node;
           head = temp;
           tail = temp;
           temp -> prev = NULL;
           temp -> next = NULL;
           temp -> item = element;
       }
       else
       {
           node *temp = new node;
           temp -> item = element;
           temp -> prev = tail;
           tail -> next = temp;
           temp -> next = NULL;
           tail = temp;
       }
                
   }
      
      
  
      
  





int main()
{
   dll q;
   int ch, temp;
   while(1)
   {
       cout<<endl;
       cout<<" 1. Enqueue "<<endl;
       cout<<" 1. Dequeue "<<endl;
       cout<<" 1. First "<<endl;
       cout<<" 1. Last "<<endl;
       cout<<" 1. Search "<<endl;
       cout<<" 1. Split "<<endl;
       cout<<" 1. Exit "<<endl;
       cin>>ch;
       switch(ch)
       {
           case 1 : cout<<" dwse mou to x pou tha mpei sto telos :";
           cin>>temp;
           q.Enqueue(temp);
           break;
           case 2 : cout<<" diagrafh kai epistrofh tou 1ou :";
           temp = q.Dequeue();
           cout<<temp;
           break;
           case 3 : cout<<" epistrofh tou 1ou stoixeiou :";
           temp = q.First();
           cout<<temp;
           break;
           case 4 : cout<<" epistrofh tou teleutaiou stoixeiou :";
           temp = q.Last();
           cout<<temp;
           break;
           case 5 : cout<<" dwse x gia anazhthsh :";
           cin>>temp;
           q.Search(temp);//den eimai sigouros meta ti grafw
           break;
           case 6 : cout<<" dwse mou to x pou tha mpei sto telos :";
           cin>>temp;
           q.Enqueue(temp);
           break;
           case 7 : cout<<" exiting :";
           system("pause");
           return 0;
           break;
       }
   }
          
}

Επεξ/σία 30 Νοεμβρίου 2012 από realez

[migf1]

Βασικά το Ιντερνετ είναι γεμάτο. Με ένα πολύ πρόχειρο γκούγκλινγ έπεσα αμέσως πάνως π.χ. σε αυτό: http://www.brilliantsheep.com/queue-implementation-using-a-doubly-linked-list/, σε αυτο http://www.biostat.umn.edu/~johnh/book/10.pdf και σε αυτό: http://lispmachine.wordpress.com/2011/06/13/queue-using-doubly-linked-list/

[realez]

Το google κοντεύει να χαλάσει από τόσο που το έχω χρησιμοποιήσει τις τελευταίες ώρες

Απλώς και το σωστό να βρω δε θα είμαι σίγουρος πως είναι αυτό που χρειαζομαί :/

Ευχαριστώ πάντως θα τα κοιτάξω. Επίσης έκανα κάποιες τροποποιήσεις στον κώδικα.

[realez]

πως μπορώ να διαγράψω τελείως ένα στοιχείο της λίστας; Βρήκα κάποια άρθρα που λένε για τη destroy αλλά δυσκολεύομαι να καταλάβω.

[ChRis6]

Αρχικά πρέπει να εξετάσεις αν υπάρχει στη λίστα ο κόμβος που θες να διαγράψεις( εκτός αν θες να διαγράφεις συνέχεια από το τέλος π.χ ).Όταν αποφασίσεις ποιός κόμβος πρέπει να βγει,πρέπει να αναδιαμορφώσεις τους δείκτες των κόμβων πριν και μέτα τον κόμβο προς διαγραφή,ώστε να παραμείνει η λίστα σωστά συνδεδεμένη.

 

Έπειτα κάνεις free() τον δείκτη που δείχνει στον κόμβο προς διαγραφή( ή delete στη C++ ).Επίσης μια καλή πρακτική είναι,αφότου κάνεις free ή delete, να θέτεις την τιμή NULL στο δείκτη ώστε να μη δείχνει σε μνήμη που δεν σου ανήκει πια.

[realez]

Έχω προβληματιστεί πάρα πολύ με το παρακάτω. Θέλω η συνάρτηση Spliter να επιστρέφει 2 Pointer το head1 και το head2.

Για να το κάνω αυτό σκεύτικα να φτιάξω άλλο ένα struct με 2 πεδία ptr1 και ptr2. Οπότε στη συνάρτηση δημιουργώ ένα αντικείμενο τύπου ptr, στο πρώτο πεδίο του(ptr1) βάζω το head1 και στο δευτερο πεδίο του(ptr2) το head2. αλλά μου βγάζει σφάλμα ptr does not namy a type.

>
  	 struct spliter1 //thetika
  	 {
           int item;
           spliter1 *next;
           spliter1 *prev;
       };
       spliter1 *head1;
       spliter1 *tail1;
       
  	 struct spliter2 //arnhtika
  	 {
           int item;
           spliter2 *next;
           spliter2 *prev;
       };
       spliter2 *head2;
       spliter2 *tail2;
   public:
       
       struct ptr
       {
           spliter1 *ptr1; //ptr sto thetiko
           spliter2 *ptr2; //ptr sto arnhtiko
       };
       ptr *retur;

   ptr* dll::Split()
   {
       spliter2 *temp2 = new spliter2;
       temp = head;
       do
       {
           node *temp = new node
           if( temp->item < 0 )
           {
               spliter2 *temp1 = new spliter2;
               if(head2 == NULL)
               {
                   head2 = temp1;
                   tail2 = temp1;
                   temp1 -> next = NULL;
                   temp1 -> prev = NULL;
                   temp1 -> item = temp -> item;
               }
               else
               {
                   tail2 -> next = temp1;
                   temp1 -> prev = tail2;
                   tail2 = temp1;
                   tail2 -> item = temp -> item;
               }
           }
           else
           {
               spliter1 *temp1 = new spliter1;
               if(head1 == NULL)
               {
                   head1 = temp1;
                   tail1 = temp1;
                   temp1 -> next = NULL;
                   temp1 -> prev = NULL;
                   temp1 -> item = temp -> item;
               }
               else
               {
                   tail1 -> next = temp1;
                   temp1 -> prev = tail1;
                   tail1 = temp1;
                   tail1 -> item = temp -> item;
               }
               
           }
           temp = temp -> next;
       }while(temp != NULL);
       retur -> ptr1 = head1;
       retur -> ptr2 = head2;
       return retur;    
   }