Προς το περιεχόμενο

Αρχειοθετημένο

Αυτό το θέμα έχει αρχειοθετηθεί και είναι κλειστό για περαιτέρω απαντήσεις.

  • 0
Lomar

Δομές Δεδομένων -> Λίστες

Ερώτηση

Header: "list.h"

 

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

struct node {
int elem;
struct node *next;
};

enum boolean {false,true};
typedef enum boolean bool;
typedef struct node Node;
Node *head = NULL;
int len = 0;

/************ Έλεγχος αν η λίστα είναι κενή ******************/

bool isEmpty(Node *head)
{
 return (head == NULL);
}

/************* Δημιουργία νέου κόμβου ***********************/

Node *create(int k)
{
 Node *p = (Node *) malloc(sizeof(Node));
 p->elem = k;
 return p;
}	

/************** Εύρεση τελευταίου κόμβου *******************/

Node *Last(Node *head)
{
 Node *p = head;
 Node *l = NULL;
 while (p != NULL)
 {
    l = p;
    p = p->next;  
 }
 return l;
}

/*************** Εύρεση συγκεκριμένου στοιχείου *************/

Node *Search(Node *head, int x)
{
 bool found = false;
 Node *p = head;
 while (p != NULL && !found)
 {
   if (p->elem == x) found = true;
   else p = p->next;
 }
 return p;
}

/********** Εύρεση του προηγούμενου κόμβου του p **********/

Node *getPrev(Node *head,Node *p)
{
Node *q = head;
bool found = false;
while(q != NULL && !found)
{
	if (q->next == p) found = true;
	else
	    q = q->next;
}
return q;
}

/*************** Εισαγωγή του p μετά το q ******************/

void insertAfter(Node *p, Node *q)
{
 p->next = q->next;
 q->next = p;
 len++;
}

/************** Εισαγωγή στην αρχή της λίστας *************/

void insertFirst(Node **head,Node *p)
{
p->next=*head;
*head=p;
len++;
}

/****Διαγραφή του στοιχείου που βρίσκεται μετά το p *****/

void deleteAfter(Node *p)
{
if (p->next != NULL)
{
  Node *q = p->next;
  p->next = q->next;
  free(q);
  len--;
}
}

/************ Διαγραφή της κεφαλής της λίστας ********/

void deleteFirst(Node **head)
{
 if (head != NULL)
 {
   Node *q = *head;
   *head = (*head)->next;
   free(q);
   len--;
 }
}

 

SOURCE CODE

 

>
#include <stdio.h>
#include "list.h"

void insert(int k)
{
Node *p = create(k);
if (isEmpty(head))
  insertFirst(&head,p);
else
{
	Node *q = Last(head);
	insertAfter(p,q);
}

}

bool update(int k, int x)
{
 bool ok = false;
 Node *p = Search(head,k);
 if (p != NULL)
 {
  p->elem = x;
  ok = true;
 }
 return ok;
}


void delete(int k)
{
Node *p = Search(head,k);
if (p != NULL)
{
	if (p == head) deleteFirst(&head);
	else
	{
		Node *q = getPrev(head,p);
		deleteAfter(q);
	}
}
}

void show(Node *head)
{ 
Node *p = head;
while (p != NULL)
{
  printf("%3d ->",p->elem);
  p = p->next;
}
printf(" NULL\n");
}


main()
{
 int choise = 0;
 int k,x;
 while (choise != 5)
 {
  printf("****************\n");
  printf("*  1.Insert    *\n");
  printf("*  2.Update    *\n");
  printf("*  3.Delete    *\n");
  printf("*  4.Show      *\n");
  printf("*  5.Exit      *\n");
  printf("****************\n");
  scanf("%d",&choise);
  switch (choise)
  {
   case 1 : 	printf("Give a number ");
                   	scanf("%d",&k);
            	insert(k);
            	break;
   case 2 : 	printf("Give old value ");
   	    	scanf("%d",&k);
   	    	printf("Give new value ");
   	    	scanf("%d",&x);
   	    	if (update(k,x))
   	    		printf("Update ok...\n");
   	    	else printf("update not complete...\n");
   	    	break;
   case 3 : 	printf("Give value to delete ");
            	scanf("%d",&k);
            	delete(k);
            	break;
   case 4 : 	printf("****** List Items******\n");
            	show(head);
            	printf("***********************\n");
            	break;
         }
 }
}

 

Το ερώτημα μου είναι το εξής:

 

Στη βιβλιοθήκη, και συγκεκριμένα στη συνάρτηση:

 

>
void insertFirst(Node **head,Node *p)
{
p->next=*head;
*head=p;
len++;
}

 

το διπλό pointer στο 1ο argument της μεταβλητής head, σε τι ακριβώς εξυπηρετεί;

 

παρατήρησα οτι με μονό pointer, δεν δέχεται τη διεύθυνση για το υπο διαγραφή head (το 1ο δλδ pointer στη λίστα) η συνάρτηση:

 

>
void delete(int k)
{
Node *p = Search(head,k);
if (p != NULL)
{
	if (p == head) deleteFirst(&head);
	else
	{
		Node *q = getPrev(head,p);
		deleteAfter(q);
	}
}
}

 

συγκεκριμένα (απ'ότι καταλαβαίνω), το &head δε δέχεται τη διεύθυνση, δλδ χρειάζεται παραπάνω διπλό pointer.

 

Αλλά η χρήση των διπλών pointer απ'όσο έχω μέχρι στιγμής καταλάβει είναι για τη δυναμική αυξομείωση πινάκων.

 

πχ char **a; ==> δημιουργία με realloc ακόμη μιας θέσης string σε ενα array απο string.

 

Εδώ τα διπλά pointer δε μπορώ να καταλάβω σε τι ακριβώς εξυπηρετούν... Οποιαδήποτε βοήθεια για τη κατανόηση των διπλων pointer είναι κατι επιπλέον απο ευπρόσδεκτη! Δε ζητώ εξηγήσεις αποκλειστικά πάνω στο συγκεκριμένο κώδικα, όπως μπορεί κανείς να μου το εξηγήσει ακόμη και με διαφορετικά παραδείγματα, δεν έχω πρόβλημα :-)

Κοινοποιήστε αυτήν την ανάρτηση


Σύνδεσμος στην ανάρτηση
Κοινοποίηση σε άλλες σελίδες

Προτεινόμενες αναρτήσεις

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

.

 

:shifty:Πόσο πιο καθαρά να το γράψω;:shifty:

Over and out..

 

Υ.Γ.

1. Να ψάξετε στην αρχαιότητα (1950-1960/64+-) ΠΩΣ κάνανε Memory Allocation (δοκιμάστε το, η WikiPedia είναι φίλη μας!) και τότε θα καταλάβετε γιατί το λέω άχρηστο πια bug-prone TRICK -και να κάνετε τον σταυρό σας που έχουμε Dynamic Memory allocation όσοι προγραμματίζεται! :P

2. Alkisg, ευχαριστώ για τα μαθήματα στο Memory Management αλλά δεν θεωρώ πως τα έχω ανάγκη εντούτοις να είσαι καλά. Και θερμή παράκληση, την επόμενη φορά να διαβάζεις καλύτερα όσα γράφω (είναι η δεύτερη φορά στο παρόν topic που παρεξηγείς, ελπίζω ακούσια (χμμμμ), τα γραφόμενα μου ...).

Κοινοποιήστε αυτήν την ανάρτηση


Σύνδεσμος στην ανάρτηση
Κοινοποίηση σε άλλες σελίδες

@dark_banishing έδωσες την πιο κατατοπιστική και εύστοχη απάντηση!!!

 

Όλα τα παραπάνω τα γνώριζα, αλλά δε παρατήρησα/καλοσκέφτηκα οτι το head το δεχόταν σαν όρισμα μια συνάρτηση, οι οποίες συναρτήσεις, ούτως ή άλλως χρησιμοποιύν pointer όταν είναι void, ακριβώς για το λόγο που εξήγησες παραπάνω!

 

Τώρα πια το κατάλαβα επακριβώς!

 

Σας ευχαριστώ όλους πάρα πολύ για το χρόνο, το κόπο, τις πληροφορίες και γενικότερα τη βοήθειά σας!

Κοινοποιήστε αυτήν την ανάρτηση


Σύνδεσμος στην ανάρτηση
Κοινοποίηση σε άλλες σελίδες

Καλησπέρα!

 

Προσπαθώ εδώ και αρκετή ώρα να δημιουργήσω μια διπλά συνδεμένη λίστα στην Java, χωρίς όμως αποτέλεσμα...:fear: Βρήκα ένα εγχειρίδιο που λέει πάνω κάτω τι χρειάζεται μια διπλά συνδεμένη λίστα και βάση αυτού δημιούργησα όλες της μεθόδους που απαιτούνται. Μήπως θέλει κάποιος να του στείλω το αρχείο με τον κώδικα που δημιούργησα, να μου δώσει μια μικρή υπόδειξη πως λειτουργεί....

 

Έχω μπερδευτεί λίγο...:cry:

Κοινοποιήστε αυτήν την ανάρτηση


Σύνδεσμος στην ανάρτηση
Κοινοποίηση σε άλλες σελίδες
Ξεκάθαρα bug είναι. Σε καμία περίπτωση feature ανεξάρτητα από το πως δεσμεύεται η μνήμη (σειριακά ή όχι κάτι που δεν μπορεί να εγγυηθεί).

Εκτός και αν ξέρετε κάποιο τρόπο να κάνετε free μετά την μνήμη για να μην υπάρχει memory leak.

Προφανώς το παλικάρι που τον έκανε τον κώδικα εννούσε

>
 varray = malloc(10*sizeof(int *));
 for(i=0;i<10;i++)
               varray[i]=malloc(10*sizeof(int));

 

Αν το Λ.Σ. σου εγγυάται την σειριακή δέσμευση μνήμης από το πρώτο offset που δεσμεύεις τότε άκομψα (γιατί να μην αποθηκεύσεις την διεύθυνση σε ένα handle;) μπορείς να κάνεις αποδέσμευση μνήμης, με όλη την ταλαιπωρία που παρουσιάζει - σε κάθε άλλη περίπτωση υπάρχει πρόβλημα.

 

Ο τρόπος που ανήρτησα (και ΠΡΟΣΟΧΗ δουλεύει υπό τις ακόλουθες πάντα προϋποθέσεις) αποδεσμεύει όλη την δεσμευμένη μνήμη υπό την προϋπόθεσή α) πως το malloc επιστρέφει σειριακές θέσεις και β) πως γνωρίζω το μέγεθος κάθε μπλοκ και το memory-alignment του compiler μου.

 

Δεν λέω πως είναι σωστή τεχνική (είπα bug-prone) αλλά σε μια extreme περίπτωση την οποία διευκρίνισα (σειριακή δέσμευση) θα μπορούσε να λειτουργήσει (εξ' ου και ο χαρακτηρισμός τρικ) -ψάξτε τα παλία Λ.Σ. δεκαετία του '50 και '60 για την διαχείριση της μνήμης τους.

 

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

 

Αυτά, για να τελειώνουμε με το ΠΩΣ & ΓΙΑΤΙ - και καλή συνέχεια.

:-)

Κοινοποιήστε αυτήν την ανάρτηση


Σύνδεσμος στην ανάρτηση
Κοινοποίηση σε άλλες σελίδες

Παραθέτω από την ίδια σελίδα:

 

Return Value

A pointer to the reallocated memory block, which may be either the same as the ptr argument or a new location.

 

Αυτός στο παράδειγμα απλά καλεί την realloc και ενημερώνεται για τη νέα τιμή μέσω της ανάθεσης (=):

numbers = (int*) realloc (numbers, count * sizeof(int));

 

Αντίστοιχα, όταν φτιάχνεις μία συνάρτηση, π.χ.

void insertFirst(Node **head,Node *p)

 

αν δεν επιστρέφεις τη νέα τιμή μέσω return value της συνάρτησης, πρέπει υποχρεωτικά να χρησιμοποιήσεις διπλό αστεράκι, αλλιώς δεν έχεις τρόπο να επιστρέψεις την αλλαγμένη τιμή.

 

Ένας άλλος τρόπος να γραφεί η παραπάνω συνάρτηση θα ήταν:

Node *insertFirst(Node *head, Node *p)

 

και τότε θα έπρεπε να τη χρησιμοποιείς έτσι:

head = insertFirst(head, p);

 

το οποίο (προφανώς, από την τρέχουσα συζήτηση) δεν είναι τόσο κατανοητό...

Κοινοποιήστε αυτήν την ανάρτηση


Σύνδεσμος στην ανάρτηση
Κοινοποίηση σε άλλες σελίδες

thnks παιδιά αν και ακόμα δε κατάλαβα πιο είναι το πρόβλημα... :-(

 

Τον παραπάνω κώδικα τον έχει γράψει καθηγητής και μας τον έδωσε στο αντίστοιχο εργαστήριο το οποίο και έχω αύριο και απ'ότι φαίνεται θα τα ακούσει καλα!

 

Παντού τη malloc έτσι την βλέπουμε στη σχολή... ρε γμτ δε μπορώ να καταλάβω τελικά πως δεσμεύεις με γενικούς ANSI κανόνες μνήμη...

 

EDIT:

 

μα η δέσμευση μνήμης μέσα στη δεύτερη for γίνεται μια φορά για κάθε i μέσα στο array. H πρώτη for αν κατάλαβα καλά είναι ανούσια επειδή δεσμεύεται 10 φορές το ίδιο πράγμα σε διαφορετική θέση μνήμης;

Κοινοποιήστε αυτήν την ανάρτηση


Σύνδεσμος στην ανάρτηση
Κοινοποίηση σε άλλες σελίδες

Ξεκάθαρα bug είναι. Σε καμία περίπτωση feature ανεξάρτητα από το πως δεσμεύεται η μνήμη (σειριακά ή όχι κάτι που δεν μπορεί να εγγυηθεί).

Εκτός και αν ξέρετε κάποιο τρόπο να κάνετε free μετά την μνήμη για να μην υπάρχει memory leak.

Προφανώς το παλικάρι που τον έκανε τον κώδικα εννούσε

>
 varray = malloc(10*sizeof(int *));
 for(i=0;i<10;i++)
               varray[i]=malloc(10*sizeof(int));

Κοινοποιήστε αυτήν την ανάρτηση


Σύνδεσμος στην ανάρτηση
Κοινοποίηση σε άλλες σελίδες

ΟΚ, απλά στο μυαλό μου ο 2ος τρόπος είναι πιο ορθόδοξος (ίσως επειδή θυμίζει και την ίδια τη malloc) και δεν το σκέφτηκα έτσι... :-)

Κοινοποιήστε αυτήν την ανάρτηση


Σύνδεσμος στην ανάρτηση
Κοινοποίηση σε άλλες σελίδες

Δε νομίζω. Γίνεται στην αρχή και γίνεται για να δεσμεύσει το κατάλληλο μέγεθος (πλήθος κελιών μνήμης) για το array (varray) που δημιουργείται, σαν αρχικοποίηση μεγέθους. Δε καταχωρούνται κάπου δεδομένα.

 

 

Το πρόγραμμα πάντως τρέχει σωστά. Αν θέλεις εξηγήσου λιγάκι παραπάνω :-)

Κοινοποιήστε αυτήν την ανάρτηση


Σύνδεσμος στην ανάρτηση
Κοινοποίηση σε άλλες σελίδες

Στα πολύ γρήγορα και χωρίς να διαβάσω αναλυτικά το θέμα:

 

σε realloc χρειάζεται διπλό αστεράκι.

 

Αυτό επειδή έστω ότι το x είναι ένας δείκτης σε 1 Mb RAM. Ζητάς realloc για 100Mb RAM. Το σύστημα έχει 100 Mb ελεύθερα, αλλά δεν τα έχει εκεί που είχε τοποθετήσει αρχικά το δείκτη σου. Επομένως σου τα δίνει αλλού, και μάλιστα αν θυμάμαι καλά η βιβλιοθήκη της C σου αντιγράφει και το 1 Mb με τα δεδομένα σου.

 

Τελικά ο δείκτης άλλαξε, επομένως για να μπορείς να τον επιστρέψεις από συνάρτηση αναγκαστικά θες **.

Κοινοποιήστε αυτήν την ανάρτηση


Σύνδεσμος στην ανάρτηση
Κοινοποίηση σε άλλες σελίδες

Μην παρεξηγιέσαι βρε, τόσα χρόνια εδώ μέσα έχει φανεί η αξία σου σαν προγραμματιστής.

Και μόνο το ότι παρατήρησες ότι ο εν λόγω κώδικας μπορεί υπό προϋποθέσεις να δουλέψει σωστά είναι αξιέπαινο!!! :)

 

Απλά απάντησα στο

"υπό την προϋπόθεσή α) πως το malloc επιστρέφει σειριακές θέσεις"

ότι είναι αδύνατο, κάποτε τελειώνει το address space.

Άλλο να τύχει για 10 malloc στην αρχή της εκτέλεσης και άλλο να θεωρούμε ότι μπορεί να υπάρξει τέτοια υλοποίηση/προϋπόθεση.

 

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

 

Αλίμονο, είμαστε που είμαστε λίγοι οι codegear users, να κονταροχτυπιόμαστε και μεταξύ μας... :)

 

Υ.Γ. δε νομίζω ότι παρεξήγησα (αλήθεια η πρώτη φορά ποια ήταν; δεν κατάλαβα), δεν είπα ότι το προτείνεις σαν τεχνική, είπα μόνο το ότι είναι αδύνατη η σειριακή malloc.

Κοινοποιήστε αυτήν την ανάρτηση


Σύνδεσμος στην ανάρτηση
Κοινοποίηση σε άλλες σελίδες

>Node *head = NULL;

 

Έχει δηλωθεί ως *. Κι αυτό γιατί θέλεις όταν είναι άδεια ακόμη η λίστα να μπορεί να εισαχθεί ο πρώτος κόμβος με την create, η οποία επιστρέφει διεύθυνση σε ένα νεοδημιουργηθέντα κόμβο. Αυτό επίσης σημαίνει πως ανάλογα με το πώς θέλεις να χειριστείς τον κόμβο αυτό σε κάθε συνάρτηση, άλλοτε πρέπει να έχεις αποαναφοροποίηση στον κώδικά σου με *head και άλλοτε όχι...

Κοινοποιήστε αυτήν την ανάρτηση


Σύνδεσμος στην ανάρτηση
Κοινοποίηση σε άλλες σελίδες

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

 

Το θέμα θεωρείται λήξαν.

Να είσαι καλά.

 

:-)

Κοινοποιήστε αυτήν την ανάρτηση


Σύνδεσμος στην ανάρτηση
Κοινοποίηση σε άλλες σελίδες

EDIT:

μα η δέσμευση μνήμης μέσα στη δεύτερη for γίνεται μια φορά για κάθε i μέσα στο array. H πρώτη for αν κατάλαβα καλά είναι ανούσια επειδή δεσμεύεται 10 φορές το ίδιο πράγμα σε διαφορετική θέση μνήμης;

 

Ναι - και δεν κρατάς μάλιστα αυτές τις διευθύνσεις παρά την τελευταία οπότε ούτε να τις αποδεσμεύσεις μπορείς (χαμένα μπλοκς) ...

 

Τώρα γιατί αυτός ο κώδικας .. πάει κάπου το μυαλό μου αλλά είναι πολύ τολμηρό ... :mrgreen:

Κοινοποιήστε αυτήν την ανάρτηση


Σύνδεσμος στην ανάρτηση
Κοινοποίηση σε άλλες σελίδες

Βρε παιδιά μήπως υπάρχει μπλέξιμο;

 

Μου φαίνεται ότι ο Lomar μιλάει για τον κώδικα του καθηγητή του ενώ ο DirectX μιλάει για τον κώδικα του Red_Phantom... Καμία σχέση, εκτός αν κατάλαβα λάθος.

 

Κατά τα άλλα για το varray είναι όπως τα λέει ο DiAvOl.

Κοινοποιήστε αυτήν την ανάρτηση


Σύνδεσμος στην ανάρτηση
Κοινοποίηση σε άλλες σελίδες
×
×
  • Δημιουργία νέου...