Αποριες σε λιστες

[nik324]

Λοιπον...εφτιαξα μια συναρτηση για την εισαγωγη ενος νεου κομβου σε διπλα συνδεδεμεη λιστα στο τελος της και ο κωδικας μου ειναι ο εξης

 

>
typedef struct node{
const void *data;
struct link *next;
struct link *prev;
}Node;

typedef struct Tail{
Node *first;
Node *last;

}TAIL;

void addNode(TAIL *list, void *data){
Node *link;

link=calloc(1,sizeof(Node));

if(!link){
	fprintf (stderr, "calloc failed.\n");
    exit(EXIT_FAILURE);
 }
link->data=data;
if(list->last){
	list->next=link;            */ ??? /*
	list->last=link;            */ ??? /*
	link->prev=list->last;      */ ??? /*
}else{
	list->first=link;
	list->last=link;
}
}

 

εκει που εχω τα ερωτηματικα εχω και τις αποριες!

 

Καταρχας, θα μπορουσα να εχω μια διπλα συνδεδεμενη λιστα χωρις να εχω τους δεικτες first και last?

Kαι τελος, με τον κωδικα μου -αν δεν εχω κανει καποιο λαθος- εχω κανει την εισαγωγη ενος κομβου και εχω "τακτοποιησει" τους δεικτες next,last,prev ενω για τον first δεν εχω κανει τιποτα...τι μπορω να κανω και για αυτον;

[Timonkaipumpa]

Διπλά συνδεδεμένη = συνδέεται διπλά.

 

 

Για το first και last... διάβασε την προηγούμενή μου απάντηση. Θαρρώ πως θα σου λυθεί η απορία.

 

 

Επίσης, γιατί const ο δείκτης για τα data; Και εάν θες να αλλάξεις data; Θα πας να πειράζεις τις τιμές εκεί μέσα;

 

Ή, εάν θες να αλλάξεις τύπο data... θα καταστρέφεις τον κόμβο, θα φροντίζεις τους δείκτες από τους πλαϊνούς κόμβους, θα φτιάχνεις καινούργιο, θα βάζεις τον νέο μέσα στην λίστα;

 

Επίσης.. το struct TAIL δεν νομίζω ότι έχει σωστό όνομα... δεν είναι TAIL αλλά listHandler. TAIL έχει το queue...

 

Επίσης... η συνάρτηση addNode δεν κάνει compile.. και φαίνεται χωρίς να την κάνεις καν compile.

 

Θα πετάξει κάτι σαν undefined member next for struct TAIL

 

Επίσης, το link τι είναι στο struct Node;

[nik324]

Διπλά συνδεδεμένη = συνδέεται διπλά.

 

 

Για το first και last... διάβασε την προηγούμενή μου απάντηση. Θαρρώ πως θα σου λυθεί η απορία.

 

 

Επίσης, γιατί const ο δείκτης για τα data; Και εάν θες να αλλάξεις data; Θα πας να πειράζεις τις τιμές εκεί μέσα;

 

Ή, εάν θες να αλλάξεις τύπο data... θα καταστρέφεις τον κόμβο, θα φροντίζεις τους δείκτες από τους πλαϊνούς κόμβους, θα φτιάχνεις καινούργιο, θα βάζεις τον νέο μέσα στην λίστα;

 

Επίσης.. το struct TAIL δεν νομίζω ότι έχει σωστό όνομα... δεν είναι TAIL αλλά listHandler. TAIL έχει το queue...

 

Επίσης... η συνάρτηση addNode δεν κάνει compile.. και φαίνεται χωρίς να την κάνεις καν compile.

 

Θα πετάξει κάτι σαν undefined member next for struct TAIL

 

Επίσης, το link τι είναι στο struct Node;

 

 

Δεν προσπαθω να κανω κατι συγκεκριμενο απλα πειραματιζομαι για εξασκηση!

 

Εχεις δικιο για την ονομασια που εδωσα..!

 

Οσο για το οτι δεν περναει το combile για αυτο ανεβασα τον κωδικα εδω! Για την ευρεση λαθων...

[migf1]

Εγώ είμαι κουρασμένος αυτή τη στιγμή για να κοιτάξω τον κώδικα, αλλά θα σου πρότεινα την εξάσκηση να την κάνεις με απλά int data αντί για void *.

 

Μπορείς επίσης να βρεις στο google πολλά άρθρα που να σου εξηγούν βήμα-βήμα και να έχουν και κώδικα. Π.χ στο "doubly linked list in c" εμένα μου βγάζει 1ο-1ο αυτό: http://www.thelearni...ram-source-code

[nik324]

απο οτι ειδα για να ειναι σωστη η συναρτηση πρεπει να προσθεσω μεσα στην if το εξης

> 
       list->last->next = link;
       link->prev = list->last;
       list->last = link;

 

αλλα δεν μπορω να καταλαβω πως λειτουργει!

 

η πρωτη σειρα ειναι το ιδιο με το να γραφοταν ετσι;

>
         list->last=link;
         list->next=link;

[imitheos]

Λοιπον...εφτιαξα μια συναρτηση για την εισαγωγη ενος νεου κομβου σε διπλα συνδεδεμεη λιστα στο τελος της και ο κωδικας μου ειναι ο εξης

 

>
typedef struct node{
const void *data;
struct link *next;
struct link *prev;
}Node;

Όπως είπε και ο Timon, το link δεν έχει νόημα εδώ αλλά μάλλον θέλεις node.

 

>
void addNode(TAIL *list, void *data){
Node *link;

link=calloc(1,sizeof(Node));

if(!link){
	fprintf (stderr, "calloc failed.\n");
    exit(EXIT_FAILURE);
 }
link->data=data;
if(list->last){
               list->last->next = link;
               link->prev = list->last;
               list->last = link;

}else{
	list->first=link;
	list->last=link;
}
}

απο οτι ειδα για να ειναι σωστη η συναρτηση πρεπει να προσθεσω μεσα στην if το εξης

> 
       list->last->next = link;
       link->prev = list->last;
       list->last = link;

 

αλλα δεν μπορω να καταλαβω πως λειτουργει!

 

η πρωτη σειρα ειναι το ιδιο με το να γραφοταν ετσι;

>
         list->last=link;
         list->next=link;

 

Υποθέτω ότι όταν αρχικοποιείς την list (που είναι TAIL), θα θέτεις και το first και το last σε NULL. Αυτό το πράγμα ελέγχει και το if. Αν η last σου είναι NULL, τότε σημαίνει ότι η λίστα σου είναι άδεια οπότε στο else θέτει και το first και το last να είναι η link που έφτιαξες μια και είναι ο μοναδικός κόμβος οπότε είναι και πρώτος και τελευταίος.

 

Αν τώρα η last δεν είναι NULL, σημαίνει ότι υπάρχει τουλάχιστον ένας κόμβος. Ας υποθέσουμε ότι έχεις 5 κόμβους οπότε η "list->last" δείχνει στον 5ο κόμβο. Η "list->last->next = link" θέτει ως επόμενο του 5ου κόμβου να είναι ο κόμβος που δημιούργησες ώστε να γίνει 6ος στη σειρά. Η "link->prev = list->last" ορίζει ως προηγούμενο κόμβο του link τον μέχρι τώρα τελευταίο κόμβο (τον 5ο δηλαδή). Έτσι η σύνδεση του 5ου με τον 6ο κόμβο έγινε. Και οι δύο δείχνουν ο ένας στον άλλον. Τώρα μένει απλά να πεις ότι τελευταίος κόμβος στη λίστα σου είναι ο καινούριος και αυτό το κάνεις με την 3η εντολή "list->last = link".

 

Αν έγραφες την 1η σειρά όπως παραπάνω θα ήταν άραγε το ίδιο ? Γιατί δεν "τρέχεις" με το μυαλό σου το πρόγραμμα να δεις τι κάνει. Η "list->next" υπάρχει ? Η list είπαμε είναι TAIL οπότε έχει πεδία first και last.

[Timonkaipumpa]

απο οτι ειδα για να ειναι σωστη η συναρτηση πρεπει να προσθεσω μεσα στην if το εξης

> 
       list->last->next = link;
       link->prev = list->last;
       list->last = link;

 

αλλα δεν μπορω να καταλαβω πως λειτουργει!

 

η πρωτη σειρα ειναι το ιδιο με το να γραφοταν ετσι;

>
         list->last=link;
         list->next=link;

 

 

Όπως σου είπα στην αρχή... τα πάντα από τις δομές είναι περιοχές μνήμης που συνδέονται με κάποιο τρόπο.

 

Το struct TAIL έχει δύο δείκτες μέσα. Τον first και τον last.

 

Οπότε, έχεις το first που δείχνει, -> , κάπου...

και το last που δείχνει, ->, κάπου.

 

 

Εάν βάλεις ένα κόμβο στη λίστα, ο first θα δείχνει στην ΠΕΡΙΟΧΗ ΜΝΗΜΗΣ που είναι ένα struct Node.

 

 

Αυτό το κάνεις λέγοντας στον δείκτη first του struct TAIL να δείξει εκεί που είναι ένας Node.

 

Π.χ.

 

>
TAIL *pTail;
Node *pNode;

pTail->first = pNode;

 

(φυσικά παρέλειψα το allocation μνήμης και διάφορους ελέγχους για το allocation... χάρη συντομίας)

 

 

Εάν θες να προσθέσεις ένα κόμβο, ΜΕΤΑ τον πρώτο Node που έβαλες, θα κάνεις:

 

>

TAIL *pTail;
Node *pNode1;
Node *pNode2;

pTail->first = pNode1;

pTail->first->next = pNode2;

 

Δηλαδή... από το TAIL, πας εκεί που ΔΕΙΧΝΕΙ το first και από εκεί, εκεί που ΔΕΙΧΝΕΙ ο next βάζεις τον δεύτερο Node.

 

 

Εάν ήθελες να βάλεις τον 2ο πριν τον 1το...

 

>
TAIL *pTail;
Node *pNode1;
Node *pNode2;

pTail->first = pNode1;

pTail->first->previous = pNode2;

pTail->first = pTail->first->previous;

 

Εάν παρατήρησες... έβαλα τον pNode2 χωρίς να μπω στον pNode1... μόνο από το TAIL (το οποίο είναι λάθος ονομασμένο, το είπαμε αυτό )

 

Για αυτό βολεύει ο listHandler... για να μπορείς να χειρίζεσαι την λίστα χωρίς να μπαίνεις στους κόμβους... αλλά μόνο από τον listHandler.

 

 

Ή, εάν ο Node ήταν:

 

>
typedef struct listnode{
 int theDatum;
 struct listnode *previous;
 struct listnode *next;
}listNode, *pListNode;

 

και ένα listHandler:

 

>
typedef struct listhandler{
 pListNode head;
 pListNode tail;
}listHandler, *pListHandler;

 

και ήθελες να έχεις μία ταξινομημένη λίστα και έβαζες κόμβο στην λίστα (θα σου εξηγήσω μετά τι άλλο θα μπορούσες να βάλεις) θα είχες:

 

>
int addNodeSorted(pListNode *incomingNode, pListHandler *theList)
{
 pListNode tmp;
 
 tmp = (*theList)->head;
 int reachedEnd = 0;

 while ( tmp )
 {
   if ( tmp->theDatum > (*incomingNode)->theDatum )
   {
     reachedEnd = 0;
     (*incomingNode)->previous = tmp->previous;
     tmp->previous->next = (*incomingNode);
     (*incomingNode)->next = tmp;
     break;
   } else {
     reachedEnd = 1;
     tmp = tmp->next;
   }
 }

 if ( reachedEnd )
 {
   (*theList)->last->next = (*incomingNode);
   (*incomingNode)->previous = (*theList)->last;
   (*theList)->last = (*incomingNode);
   (*theList)->last->next = (pListNode) NULL;
 }
}

 

(εννοείται πως για να λειτουργήσει η συνάρτηση αυτή, θα πρέπει να φροντίζεις τις "αρχικοποιήσεις" των ακριανών listNode ή pListNode σε NULL εάν δεν συνδέονται κάπου)

 

Θα μπορούσες να έχεις ένα πρότυπο:

 

>
int addNodeSorted(int incomingDatum, pListHandler *theList)

 

Όπου απλά θα δημιουργούσες ένα κόμβο μέσα στην συνάρτηση... και από εκεί και έπειτα θα κάνεις ό,τι και στην προηγούμενη.

 

 

Για να καταλάβεις ακριβώς τι γίνεται... κάτσε σχεδίασε!

[migf1]

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

 

Σχετικά με την ονοματολογία, προσωπικά προτιμώ τον listHandler που χρησιμοποιεί ο Timon να το ονομάζω list (ή π.χ. dlist για doubly linked-list, αν περιέχει κι άλλες λίστες το πρόγραμμα). Και το listHandler είναι εύστοχο όμως.

 

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

 

Οπότε, σχετικά με το τρέχον μήκος, αν έχουμε ας πούμε...

 

>
...
typedef struct node Node;
typedef struct list List;

struct node {
int data;
Node *prev;
Node *next;
};

struct list {
Node *head;
Node *tail;
unsigned long int len;
};
...

και ορίσουμε την λίστα μας (που ουσιαστικά είναι ο Handler με την ορολογία του Timon) στην main...

 

>
...
List list = { .head=NULL, .tail=NULL, .len=0U);
...

τότε στη συνάρτηση εισαγωγής (και διαγραφής) κόμβων μπορούμε να υπολογίζουμε πολύ γρήγορα και να αποθηκεύουμε και το νέο μήκος της λίστας...

 

>
bool list_insert( List *list, int data)
{
// κώδικας εισαγωγής κόμβου εδώ

  if ( empty_list )
  	list->len = 0;
  else if ( πετυχημένη εισαγωγή )
		(list->len)++;

  ...
}
/* ο κώδικας ενημέρωση του len είναι λίγο πιο πολύπλοκος από τον παραπάνω, γιατί συμφέρει να το υπολογίζουμε inplace στα διάφορα branches του κώδικα που κάνουν την εισαγωγή */

Kαλώντας την συνάρτηση ας πούμε στην main() ταυτόχρονα έχουμε υπολογίσει και το μήκος της:

 

>
...
if ( list_insert( &list, 10 ) )
printf( "len = %d\n", list.len );
...

[Timonkaipumpa]

Χαχαχαχαχαχα!!!

 

 

Να φανταστώ ότι δεν ήθελες να γράψεις για το pNode.. που, εάν θυμάμαι καλά, έχεις κάποια αντίρρηση για την δημιουργία μεταβλητών δεικτών απευθείας;

 

 

(απλά σε πειράζω... ούτως ή άλλως... κανένας δεν έχει ολο-ίδια προσέγγιση με τον άλλο )

[migf1]

Χαχαχαχαχαχα!!!

 

 

Να φανταστώ ότι δεν ήθελες να γράψεις για το pNode.. που, εάν θυμάμαι καλά, έχεις κάποια αντίρρηση για την δημιουργία μεταβλητών δεικτών απευθείας;

 

 

(απλά σε πειράζω... ούτως ή άλλως... κανένας δεν έχει ολο-ίδια προσέγγιση με τον άλλο )

 

:lol:

 

Όχι ρε συ, το βασικό μου point ήταν να δείξω στον φίλο μας την προοπτική να κρατάει και το len της λίστας μέσα στον handler. Τα ονόματα έτσι κι αλλιώς όταν είναι χαρακτηριστικά για αυτό που περιγράφουν είναι όλα οκ (το TAIL του φίλου nik δεν είναι χαρακτηριστικό).

 

Μάλλον αναφέρεσαι στο typedef struct blabla { } *BlaBlaPtr στο οποίο έχω όντως ένσταση, αλλά δεν το έθιξα καθόλου εδώ.

[Timonkaipumpa]

 

 

Μάλλον αναφέρεσαι στο typedef struct blabla { } *BlaBlaPtr στο οποίο έχω όντως ένσταση, αλλά δεν το έθιξα καθόλου εδώ.

 

 

Yes! Σε αυτό αναφέρομαι!

 

 

[nik324]

 

 

Αν τώρα η last δεν είναι NULL, σημαίνει ότι υπάρχει τουλάχιστον ένας κόμβος. Ας υποθέσουμε ότι έχεις 5 κόμβους οπότε η "list->last" δείχνει στον 5ο κόμβο. Η "list->last->next = link" θέτει ως επόμενο του 5ου κόμβου να είναι ο κόμβος που δημιούργησες ώστε να γίνει 6ος στη σειρά. Η "link->prev = list->last" ορίζει ως προηγούμενο κόμβο του link τον μέχρι τώρα τελευταίο κόμβο (τον 5ο δηλαδή). Έτσι η σύνδεση του 5ου με τον 6ο κόμβο έγινε. Και οι δύο δείχνουν ο ένας στον άλλον. Τώρα μένει απλά να πεις ότι τελευταίος κόμβος στη λίστα σου είναι ο καινούριος και αυτό το κάνεις με την 3η εντολή "list->last = link".

 

 

http://staff.science.uva.nl/~heck/JAVAcourse/ch4/sss1_2_3.html

Η 'μορφη' της λιστας μου ειναι οπως στο απλετ του λινκ αυτου,σωστα;

 

Τοτε γιατι το prev του νεου κομβου δειχνει στον last της λιστας και πιο πριν το last του ειχαμε πει να δειχνει καπου αλλου;

 

 

Eπισης κατι ασχετο...Αν ηθελα ο δεικτης prev του πρωτου στοιχειο να δειχνει στο NULL και ο δεικτης next του τελευταιου στοιχειου αν δεχνει και αυτος στο ΝULL τοτε δεν θα ηταν αναγκη να χρησιμοποιησω τους δεκτες first and last αρα και τη struct που τους περιεχει,σωστα;

[nik324]

Ασχολουμε με ενα Project τωρα πανω σε λιστες το οποιο λεει οτι θα πρεπει να εκτελειται καλώντας την ακόλουθη εντολή:

run <input-file> όπου run είναι το όνομα του εκτελέσιμου αρχείου του προγράμματος και <input-file> είναι το όνομα ενός αρχείου εισόδου που περιέχει γεγονότα των ακόλουθων μορφών...

B<ISBN> <Category> <Author> <Publisher> <Year> <Price> <Stock>: Γεγονός τύπου Book το οποίο.....και συνεχιζει...

 

Τα isbn,category,author κτλ κτλ ειναι μερος της ασκησης...

 

 

 

Δεν μπορω να καταλαβω ακριβως τι ειναι αυτο που ζηταει...

 

Ευχαριστω παιδια και αλλη μια φορα για την βοοηθεια σας...

[nik324]

Ασχολουμε με ενα Project τωρα πανω σε λιστες το οποιο λεει οτι θα πρεπει να εκτελειται καλώντας την ακόλουθη εντολή:

run <input-file> όπου run είναι το όνομα του εκτελέσιμου αρχείου του προγράμματος και <input-file> είναι το όνομα ενός αρχείου εισόδου που περιέχει γεγονότα των ακόλουθων μορφών...

B<ISBN> <Category> <Author> <Publisher> <Year> <Price> <Stock>: Γεγονός τύπου Book το οποίο.....και συνεχιζει...

 

Τα isbn,category,author κτλ κτλ ειναι μερος της ασκησης...

 

 

 

Δεν μπορω να καταλαβω ακριβως τι ειναι αυτο που ζηταει...

 

Ευχαριστω παιδια και αλλη μια φορα για την βοοηθεια σας...

Ok βρηκα αυτο που εψαχνα...