Πρόβλημα με λίστες σε C

[Shadowvault]

Καλημέρα, καλά Χριστούγεννα και χρόνια πολλά,

υποθέστε ότι έχουμε μια λίστα 2πλα συνδεδεμένη μη κυκλική που η κεφαλή δεν είναι άδεια αλλά περιέχει στοιχεία του πρώτου πράγματος που βάλαμε στη λίστα π.χ. ένα όνομα.Μετά εγώ φτιάχνω νέα nodes και αυτά έχουν μέσα ονόματα.Πώς μπορώ να βάζω τα nodes στη λίστα μου αλλά με αύξουσα αλφαβητική σειρά;

Ευχαριστώ προκαταβολικά 

 

[defacer]

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

 

That said, το να κάνεις κάτι τέτοιο καταστρέφει το σημαντικότερο ίσως πλεονέκτημα της λίστας -- προσθήκη σε O(1) χρόνο -- οπότε είναι σχεδόν σίγουρο πως αντί να κάνεις αυτό καλύτερα είναι να αλλάξεις data structure. Μπορείς δηλαδή να πιεις νερό από σφηνοπότηρο, αλλά δε νομίζω ότι θέλεις.

[nilosgr]

 

 

 

That said, το να κάνεις κάτι τέτοιο καταστρέφει το σημαντικότερο ίσως πλεονέκτημα της λίστας -- προσθήκη σε O(1) χρόνο -- οπότε είναι σχεδόν σίγουρο πως αντί να κάνεις αυτό καλύτερα είναι να αλλάξεις data structure. Μπορείς δηλαδή να πιεις νερό από σφηνοπότηρο, αλλά δε νομίζω ότι θέλεις.

 

Πιθανοτατα ειναι εργασια, οποτε δεν τον νοιαζει...

 

 

[defacer]

 

 

Πιθανοτατα ειναι εργασια, οποτε δεν τον νοιαζει...

 

Δεν λειτουργώ μ' αυτή τη λογική.

 

 

[Shadowvault]

Ναι εργασία και μας περιορίζουν πολύ.Κανουμε τραγικά πράγματα μόνο και μόνο για να δούμε πως δουλεύουν.Έτσι το πήγα και εγώ,κάθε φορα που βάζω κάτι στη λίστα πρεπει να κάνω συνέχεια αναζήτηση.Δεν υπάρχει κατι πιο αποτελεσματικό ε?Τώρα στην αναζήτηση εκανα κάτι του στιλ for (curr=head;strcmp(newnode->name,curr->name)<0;curr=curr->nxt);

Οταν η αναζήτηση σταματήσει θα έχω τον pointer που είναι μετά απο αυτό που χρειάζομαι.Σωστά?Πρεπει να βάλω και ένα found=curr πριν το curr=curr->nxt ή βλακείες λέω?Eπίσης την πρώτη φορά τι γίνεται που η λιστα είναι κενή?Πρέπει να κάνω αντιμεταθέσεις σε όλο το head με το newmode?

[defacer]

Δεν υπάρχει κατι πιο αποτελεσματικό ε?

 

Ο λόγος που μπαίνουν εργασίες με lists δεν είναι επειδή δεν έχουμε κώδικα για lists και περιμένουμε από τους φοιτητές να γράψουν. Είναι (εκτός των άλλων) το να έρθεις σε επαφή με κάτι απλό και να συνειδητοποιήσεις μόνος σου ότι στο 1 + 1 = ? δεν υπάρχουν πολλές πιθανές απαντήσεις.

 

Με άλλα λόγια "ναι, αλλά γιατί δεν αισθάνεσαι αρκετά σίγουρος να το απαντήσεις μόνος σου?"

 

Τώρα στην αναζήτηση εκανα κάτι του στιλ for (curr=head;strcmp(newnode->name,curr->name)<0;curr=curr->nxt);

Οταν η αναζήτηση σταματήσει θα έχω τον pointer που είναι μετά απο αυτό που χρειάζομαι.Σωστά?Πρεπει να βάλω και ένα found=curr πριν το curr=curr->nxt ή βλακείες λέω?Eπίσης την πρώτη φορά τι γίνεται που η λιστα είναι κενή?Πρέπει να κάνω αντιμεταθέσεις σε όλο το head με το newmode?

 

Μου άρεσε η ιδέα σου με το for (είναι ανέλπιστα "μάγκικο" για φοιτητική εργασία), αλλά δεν είναι αρκετό. Πρέπει να καλύψεις όχι μόνο την περίπτωση που η λίστα είναι άδεια αλλά επιπλέον και αυτή που το νέο στοιχείο θα πάει να κολλήσει στο τέλος (έτσι που είναι θα πάς ->next->next->next και τελικά θα κάνεις ->name στον null pointer).

 

Αυτό που θα έκανα εγώ θα ήταν να φτιάξω μια insert_before(*newNode, *node) και μια insert_after(*newNode, *node) και μετά κάτι σαν

 

if(κενή λίστα) {
    // head = newitem
    return;
}

if (strcmp(newnode->name, head->name) < 0) {
    insert_before(newnode, head);
    return;
}

preceding = head;
while(preceding->next != 0 && strcmp(newnode->name, preceding->next->name) < 0) {
    preceding = preceding->next;
}

insert_after(newnode, preceding);

 

Έγραψα το for τελικά σαν while γιατί θα ήταν πολύ μακαρόνι σαν for (και γενικά τα for με κενό body δε μου αρέσουν ιδιαίτερα, δε μπορώ να δικαιολογήσω τον σύντομο προβληματισμό που σου δημιουργούν όσον αφορά με το τι θέλει να πει ο ποιητής).

[nilosgr]

 

Δεν λειτουργώ μ' αυτή τη λογική.

 

Το ξερω και συμφωνω μαζι σου, αλλα εφ οσον αυτο λεει η ασκηση, αυτο πρεπει να κανει...

 

Ναι εργασία και μας περιορίζουν πολύ.Κανουμε τραγικά πράγματα μόνο και μόνο για να δούμε πως δουλεύουν.Έτσι το πήγα και εγώ,κάθε φορα που βάζω κάτι στη λίστα πρεπει να κάνω συνέχεια αναζήτηση.Δεν υπάρχει κατι πιο αποτελεσματικό ε?Τώρα στην αναζήτηση εκανα κάτι του στιλ for (curr=head;strcmp(newnode->name,curr->name)<0;curr=curr->nxt);

Οταν η αναζήτηση σταματήσει θα έχω τον pointer που είναι μετά απο αυτό που χρειάζομαι.Σωστά?Πρεπει να βάλω και ένα found=curr πριν το curr=curr->nxt ή βλακείες λέω?Eπίσης την πρώτη φορά τι γίνεται που η λιστα είναι κενή?Πρέπει να κάνω αντιμεταθέσεις σε όλο το head με το newmode?

if (head == NULL){  head = newnode;}else{  for (curr = head; curr != NULL && strcmp(newnode->name, curr->name) > 0; curr = curr->nxt);  /* vale to curr na einai o amesos epomenos tou newnode */}

[Shadowvault]

το curr!=NULL το έχω στον κώιδκα απλά ξέχασα να το βάλω,έχετε δίκιο.Ευχαριστώ πολύ παντως.Θα το διοκιμάσω και θα σας πω 

[defacer]

@nilosgr τα έσπασες (τα layout) φίλε!

 

Φυσικά στην εργασία κάνεις αυτό που λέει η εργασία, απλά το σωστό να λέγεται. Συνειδητοποίησα τώρα ότι το "δεν τον νοιάζει" που λες δεν το πήρα όπως το εννοούσες εσύ.

 

Σχετικά με τον κώδικα του loop, μια λεπτομέρεια που σου διέφυγε είναι ότι αν το loop τερματίσει με curr == NULL τότε έχεις μείνει χωνί. Γι' αυτό το λόγο πρέπει να θυμάσαι την τιμή "μία πριν το curr", πράγμα που θα πρέπει να γίνει είτε με έξτρα μεταβλητή είτε όπως το έδωσα παραπάνω (preceding->next αντί για curr).

[nilosgr]

Ουπθ!! ( να κανω bug report εε;; )

 

Χμμμ... οσο για το curr == NULL μπορουμε να κανουμε τη for καπως ετσι:

for (curr = head; strcmp(newnode->name, curr->name) > 0; curr = curr->nxt)
{
  if (curr->nxt == NULL)
  {
    /* work around */

    return;
  }
}

[defacer]

Αυτό θα παίξει αλλά δε μου αρέσει γιατί από τα 2 cases που είχαμε πριν (insert πρώτο πρώτο ή μετά από κάποιο άλλο) τώρα έχουμε 3. Προσωπικά για production κώδικα θα επέλεγα τη λύση με την επιπλέον μεταβλητή.

[Shadowvault]

if(section_array[l].head==NULL) {
		section_array[l].head=newnode;
		newnode->nxt=NULL;
		newnode->prv=NULL;
	}
	else {
		for(curr=section_array[l].head;curr!=NULL && strcmp(newnode->name,curr->name)<0;found=curr,curr=curr->nxt);
		
		
		if (curr!=NULL) { 
			if (curr==section_array[l].head) { //to newnode mpainei prin to head
				newnode->prv=curr->prv;
				newnode->nxt=curr;
				curr->prv=newnode;
				return(section_array);
			}
					newnode->prv=curr->nxt; //to newnode mpainei prin to curr
					newnode->nxt=curr;
					curr->prv->nxt=newnode;
					curr->prv=newnode;
		}
		else {
			newnode->nxt=found->nxt; //to newnode mpainei meta to curr/head
			newnode->prv=found;
			found->nxt=newnode;
		}
	}
			
			
	
	
	return(section_array);
	

Αυτο μου βγάζει seg fault.Βλεπετε τιποτα περίεργο?

Επεξ/σία 27 Δεκεμβρίου 2012 από Shadowvault

[nilosgr]

 

if(section_array[l].head==NULL) {
  section_array[l].head=newnode;
  newnode->nxt=NULL;
  newnode->prv=NULL;
}
else {
  for(curr=section_array[l].head;curr!=NULL && strcmp(newnode->name,curr->name)<0;curr=curr->nxt);		
  if (curr!=NULL) { 
    if (curr==section_array[l].head) { //to newnode mpainei prin to head
      newnode->prv=curr->prv;
      newnode->nxt=curr;
      curr->prv=newnode;
      return(section_array);
    }
    newnode->prv=curr->nxt; //to newnode mpainei prin to curr
    newnode->nxt=curr;
    curr->prv->nxt=newnode;
    curr->prv=newnode;
  }
  else { // edw eheis curr == NULL, ara to curr->nxt kanei BOOOM!
    newnode->nxt=curr->nxt; //to newnode mpainei meta to curr/head
    newnode->prv=curr;
    curr->nxt=newnode;
  }
}
return(section_array);
	

Αυτο μου βγάζει seg fault.Βλεπετε τιποτα περίεργο?

[Shadowvault]

Οχι αυτό το έφτιαξα γιατι κράτησα και το προηγούμενο.Έχω ενα found,δες πάνω.Βασικα πλεον δε βγάζει seg fault αλλα τα πραγματα δε μπαινουν σωστα στη λίστα.Καποια συνθήκη πρεπει να φταιει 

 

Eγω του δίνω τα : κwstas,niki,kiriakos,petros,eleni,nikos,alexis,nontas,paxoumios,navouxodonosor

 

και αυτό βγάζει :kwstas,kiriakos,eleni,alexis,

                           niki,navouxodonosor 

αντι για : alexis,eleni,kiriakos,kwstas,paxoumios
               navouxodonosor,nikos,niki,nontas,petros

Δηλαδή 2 λιστες και τις 2 αλφαβητικά 

[migf1]

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

 

Το αν θα χρησιμοποιήσεις for, while ή do-while για να διατρέξεις την λίστα σου δεν έχει απολύτως καμία σημασία. Σημασία έχει να μεριμνείς ξεχωριστά για τα special cases, όπως για παράδειγμα για το αν προσπαθείς να κάνεις εισαγωγή νέου κόμβου σε κενή ή σε μη κενή λίστα.

 

Παρεμπιπτόντως, ένα από τα πλεονεκτήματα της 2πλά συνδεδεμένης λίστας (έναντι της απλά συνδεδεμένης) είναι πως μπορείς να κινηθείς και προς τις 2 κατευθύνσεις. Οπότε για παράδειγμα, την ταξινομημένη εισαγωγή ενός νέου κόμβου μπορείς να την κάνεις είτε από τον προηγούμενο είτε από τον επόμενο κόμβο (ανάλογα ποια special cases έχεις επιλέξει να διαχειρίζεσαι ξεχωριστά).

 

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