Συνδεδεμενες λιστες και ελεγχος τελευταιου στοιχειου

[migf1]

Επίσης, μη ξεχνάς πως πριν τερματίσεις το πρόγραμμά σου, για κάθε πετυχημένο malloc()/calloc() πρέπει ΠΑΝΤΑ να καλείς ένα αντίστοιχο free()

[Star_Light]

Bασικα ο δικος σου κωδικας ειναι στοιβα LIFO τωρα το προσεξα χαχαχα.
Ναι καταλαβαινω καλυτερα αν δωσεις int *x;
και μετα x=2;

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

[migf1]

Bασικα ο δικος σου κωδικας ειναι στοιβα LIFO τωρα το προσεξα χαχαχα.
Ναι καταλαβαινω καλυτερα αν δωσεις int *x;
και μετα x=2;

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

Έχω πτυχίο Computer Science από το Boston University με εξειδίκευση στην Τεχνητή Νοημοσύνη

[migf1]

[snip]
Ναι καταλαβαινω καλυτερα αν δωσεις int *x;
και μετα x=2;
[snip]

Όχι, αυτό δεν είναι σωστό!

Τους δείκτες πρέπει να τους αρχικοποιείς είτε σε NULL, είτε στη διεύθυνση κάποιας άλλης μεταβλητής, συνεπούς ως προς το definition του δείκτη, είτε σε έναν άλλον δείκτη ίδιου τύπου.

Ποτέ σε απόλυτα νούμερα!

[Star_Light]

[snip]
Ναι καταλαβαινω καλυτερα αν δωσεις int *x;
και μετα x=2;
[snip]

Όχι, αυτό δεν είναι σωστό!

Τους δείκτες πρέπει να τους αρχικοποιείς είτε σε NULL, είτε στη διεύθυνση κάποιας άλλης μεταβλητής, συνεπούς ως προς το definition του δείκτη, είτε σε έναν άλλον δείκτη ίδιου τύπου.

Ποτέ σε απόλυτα νούμερα!

αΚΡΙβως την μυριστηκα την δουλεια οτι θα γινεται μονο σε NULL αυτο.

[migf1]

Επειδή υποψιάζομαι πως ακόμα δεν είναι εντελώς ξεκάθαρη η διαφορά του να περνάμε τη λίστα by reference στην list_insert() με το να την περνάμε by value (πράγμα καθόλου υποτιμητικό κι απόλυτα κατανοητό) παραθέτω νέα έκδοση του κώδικα.

Έχω μετονομάσει την list_insert() σε...

Κώδικας: Επιλογή όλων

Bool list_insrear( List **list, int data )

ώστε να είναι σαφές από το όνομα πως προσθέτει τους νέους κόμβους στο τέλος της λίστας, και έχω προσθέσει τη συνάρτηση...

Κώδικας: Επιλογή όλων

List *vlist_insrear( List *list, int data )

η οποία κάνει ακριβώς ότι και η list_insrear() με τη διαφορά πως εδώ την λίστα την περνάμε By Value (στην list_insrear() την περνάμε By Reference... ο διπλός δείκτης).

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

Αν δηλαδή στην main() γράψουμε απλώς:

Κώδικας: Επιλογή όλων

vlist_insrear(list, i);

τα i που περνιούνται στη λίστα μέσα στην συνάρτηση δεν γυρίζουν πίσω στην main()... επειδή στην vlist_insrear(list, i) περνιέται ένα ΑΝΤΙΓΡΑΦΟ της list (pass by value) και όχι η αυθεντική list. Για αυτό μέσα στη συνάρτηση έχουμε βάλει τιμή επιστροφής το αλλαγμένο αντίγραφο, ώστε να μπορούμε στην main() να το εκχωρήσουμε στην αυθεντική list, ως εξής:

Κώδικας: Επιλογή όλων

list = vlist_insrear(list, i);

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

Περνώντας λοιπόν την λίστα by reference στην συνάρτηση, αρκεί ένα κάλεσμά της στη main() ως εξής:

Κώδικας: Επιλογή όλων

list_insrear( &list, i);

για να εισαχθούν τα i στην list και οι αλλαγές να διατηρηθούν και μετά το πέρας της συνάρτησης.

Αν το καλοσκεφτείτε, είναι ακριβώς το ίδιο πράγμα που συμβαίνει με οποιονδήποτε τύπο μεταβλητής στη C. Αν την περάσετε σε μια συνάρτηση by value, τυχόν αλλαγές που της κάνει η συνάρτηση δεν μεταφέρονται έξω από τη συνάρτηση. Αντίθετα, αν περάσετε τη μεταβλητή by reference (ως δείκτη στη μνήμη της δηλαδή) και μέσα στη συνάρτηση τη διαχειριστείτε ως δείκτη, τότε τυχόν αλλαγές που της κάνει η συνάρτηση μεταφέρονται και στην main. Απλά εδώ η μεταβλητή μας (η list) είναι ήδη δείκτης, οπότε για να την περάσουμε by reference στην list_insrear() πρέπει να την διαχειριστούμε ως δείκτη σε δείκτη

Παραθέτω τον νέο κώδικα ολοκληρωμένο, με σχόλια στη main() που προτρέπουν να δοκιμάσετε όσα εξήγησα παραπάνω:

Κώδικας: Επιλογή όλων


#include <stdio.h>
#include <stdlib.h>

typedef enum { FALSE=0, TRUE } Bool; // πρόσθετος τύπος δεδομένων για Boolean τιμές
// (εφόσον FALSE=0, το TRUE ισούται με 1)

typedef struct node { // δομή δεομέμων για κάθε κόμβο της λίστας
int data; // τα δεδομένα του κόμβου
struct node *next; // δείκτης προς τον επόμενο κόμβο
} List;

/* ------------------------------------------------------------------
* Insert data as Last node of list (passing the list By Reference)
*/
Bool list_insrear( List **list, int data )
{
List *head = NULL, *dummy = NULL; // αρχικοποίηση 2 βοηθητικών δεικτών
List *new = calloc(1, sizeof(struct node) ); // δέσμευση μνήμης για νέο κόμβο
if ( !new ) // αποτυχία της calloc (new == NULL)
return FALSE;

new->data = data; // εκχώρηση του data στον νέο κόμβο
new->next = NULL; // αρχικοποίηση

if ( !*list ) { // η λίστα είναι κενή (*list == NULL)
*list = new; // κάνε τον νέο κόμβο αρχή της λίστας
return TRUE;
}

/* Εισαγωγή του νέου κόμβου στο τέλος της λίστας.
*
* Αλγοριθμος:
* Ο head διατρέχει τη λίστα μέχρι το τέλος της (μέχρι δλδ ο head να βρει NULL)
* κάθε φορά που ο head πάει στον επόμενο κόμβο, ο dummy δείχνει στον κόμβο που
* ήταν ο head πριν πάει στον επόμενο. Όταν τελειώσει το loop, ο head είναι
* NULL και ο dummy δείχνει στον τελευταίο κόμβο της λίστας
*/
head = dummy = *list; // οι head & dummy δείχνουν στην αρχή της λίστας
while ( head ) { // όσο ο head δεν είναι NULL
dummy = head; // εκχώρησέ τον στον dummy (θυμήσου τον)
head = head->next; // μετακίνησε τον στον επόμενο κόμβο
}

// σε αυτό το σημείο ο dummy δείχνει στον τελευταίο κόμβο της λίοτας
dummy->next = new; // κάνε τον να δείχνει στον new

return TRUE;
}

/* ------------------------------------------------------------------
* Insert data as Last node of list (passing the list By Value)
*/
List *vlist_insrear( List *list, int data )
{
List *head = NULL, *dummy = NULL;
List *new = calloc(1, sizeof(struct node) );
if ( !new )
return list;

new->data = data;
new->next = NULL;

if ( !list )
return new;

head = dummy = list;
while ( head ) {
dummy = head;
head = head->next;
}
dummy->next = new;

return list;
}

/* ------------------------------------------------------------------
* Print 'list' contents
*/
void list_print( List *list )
{
if ( !list ) // η λίστα είναι κενή
return;

while ( list ) { // όσο ο list δεν είναι NULL
printf("%d ", list->data ); //τύπωσε τα δεδομένα του κόμβου του list
list = list->next; // μετακίνησε τον list στον επόμενο κόμβο
}

return;
}

/* ------------------------------------------------------------------
* Free memory reserved for 'list'
*/
void list_destroy( List **list )
{
if ( !*list ) // η λίστα είναι κενή
return;

List *dummy = NULL; // αρχικοποίηση βοηθητικού δείκτη
while ( *list ) { // όσο ο *list δεν είναι NULL
dummy = *list; // εκχώρησέ τον στον dummy (θυμήσου τον)
*list = (*list)->next; // μετακίνησε τον στον επόμενο κόμβο
free( dummy ); // αποδέσμευσε τον προηγούμενο κόμβο
}

return;
}

/* ------------------------------------------------------------------
*
*/
int main( void )
{
register int i=0; // προσωρινός μετρητής
List *list = NULL; // αρχικοποίηση της λίστας

// εισαγωγή 10 ακεραίων στην λίστα (από το 0 έως το 9)
for (i=0; i<10; i++) // passing the list By Reference
list_insrear( &list, i); // τα data εισάγονται και διατηρούνται

/* Αντί του παραπάνω, δοκιμάστε επίσης: */
// for (i=0; i< 10; i++) // passing the list By Value
// vlist_insrear( list, i); // τα data ΔΕΝ διατηρούνται
// for (i=0; i< 10; i++) // passing the list By Value
// list = vlist_insrear(list, i); // τα data Διατηρούνται

list_print( list ); // τύπωμα των περιεχομένων της λίστας
list_destroy( &list ); // αποδεσμευση όλων των κόμβων της λίστας

fflush(stdin); getchar();
return 0;
}



[Star_Light]

ΝΑΙ ειχα και σε αυτο ενα κενο και το διαβαζα χθες.... δηλαδη στην κληση με τιμη ή με αναφορα.... απλα πλεον τα εχω ξαναπιασει απο την αρχη και ξανακανω μια επαναληψη γιατι βρηκα αρκετα κενα... εκεινο που θα ηθελα να ρωτησω ειναι το εξης :

Κώδικας: Επιλογή όλων

#include<stdio.h>
int main(void)
{
char *str="Hello World";
char *p=str;

printf("%d",str);

return 0;
}


Αν το μορφοποιησω με τον %d στην printf το αποτελεσμα που θα βγαλει ειναι η διευθυνση μνημης του πρωτου στοιχειου της συμβολοσειρας?

Κώδικας: Επιλογή όλων



#include<stdio.h>
int main(void)
{
char *str="Hello World";

printf(str);
return 0;
}


αφου το str ειναι μεταβλητη δεικτη και δειχνει σε διευθυνση πως μου τυπωνει τα περιεχομενα του Hello World???

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

[Star_Light]

με λιγα λογια δηλαδη δεν καταλαβαινω γιατι το printf(str);

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

[migf1]

[snip]

Κώδικας: Επιλογή όλων

#include<stdio.h>
int main(void)
{
char *str="Hello World";
char *p=str;

printf("%d",str);

return 0;
}


Αν το μορφοποιησω με τον %d στην printf το αποτελεσμα που θα βγαλει ειναι η διευθυνση μνημης του πρωτου στοιχειου της συμβολοσειρας?

Ναί! Αλλά όχι με %d, με %u (οι απόλυτες διευθύνσεις μνήμης είναι unsigned).
Επίσης, παρόλο που είναι το ίδιο πράγμα, προσπάθησε για μεταβλητές που αναφέρονται σε strings να χρησιμοποιείς συμβολισμούς πινάκων, και συμβολισμούς δεικτών για μεταβλητές που προορίζονται να χρησιμοποιηθούν ως δείκτες, παρά ως strings.

Π.χ. στο παραπάνω, είναι πιο ξεκάθαρο αν γράψεις:

Κώδικας: Επιλογή όλων


char str[]="Hello World";
char *p=str;


Και για να αποφεύγεις το ρίσκο buffer overflow, στην αρχικοποίηση καλό είναι να δηλώνεις και το μέγιστο μήκος του string σου..

Κώδικας: Επιλογή όλων


#define MAXSLEN 255+1;

char str[MAXSLEN]="Hello World";
char *p=str;


Κώδικας: Επιλογή όλων


#include<stdio.h>
int main(void)
{
char *str="Hello World";

printf(str);
return 0;
}


αφου το str ειναι μεταβλητη δεικτη και δειχνει σε διευθυνση πως μου τυπωνει τα περιεχομενα του Hello World???

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

Αυτό είναι επειδή έτσι δουλεύει η printf(). Δεν είναι αναγκαστικό να της βάλεις format string ως πρώτο όρισμα... αν της βάλεις κανονικό string (όπως είναι το *str) απλά το τυπώνει.

ΥΓ. Ρίξε μια ματιά εδώ όταν ευκαιρήσεις: http://www.gvrteam.gr/forum/viewtopic.p ... 178#p47178 (και στις πιο πίσω σελίδες που εξηγώ τους pointers).

[Star_Light]

Χιλια ευχαριστω. Θα το κοιταξω.

Ναι σωστα πρεπει να λαμβανουμε υποψιν και την υπερχειλιση της μνημης.

Για να εχουμε εναν ασφαλη κωδικα . Λοιπον θα αραξω να τα κοιταξω και θα ξαναμιλησουμε!!!

Π.Σ Κατι τελευταιο εδω ->

Κώδικας: Επιλογή όλων

char *p=str;

και παλι αν το κανω ετσι οπως μου ειπες..... μου εκτυπωνει το H και δεν μπορω να καταλαβω
τι ακριβως γινεται ξεγελας ας πουμε τον compiler επειδη ταυτοχρονα το str δειχνει στο 1ο στοιχειο του πινακα....
και ταυτοχρονα εχει και μια τιμη ωστε να μην κτυπησει ο μεταγλωττιστης μετα πιο κατω που το δινεις στο *p γιατι το *p περιεχομενα
περιμενει και οχι διευθυνση μνημης. Αν η απαντηση βρισκεται σε αυτο που μου εδωσες να διαβασω οκ μην μου απαντας!