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

Lomar · 25 Νοεμβρίου 2007

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 είναι κατι επιπλέον απο ευπρόσδεκτη! Δε ζητώ εξηγήσεις αποκλειστικά πάνω στο συγκεκριμένο κώδικα, όπως μπορεί κανείς να μου το εξηγήσει ακόμη και με διαφορετικά παραδείγματα, δεν έχω πρόβλημα

Red_Phantom · 25 Νοεμβρίου 2007

H ουσία είναι ότι το ** συμαίνει δείκτης σε δείκτη.

>
#include <stdio.h>

int main(void)
{
       int a=3;
       int *pa;
       int **ppa;

       pa=&a;

       ppa=&pa;

       printf("%d\n",**ppa);


       return 0;
}

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

int main(void)
{
       int i,j;
       int **varray;

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

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


       for(i=0;i<10;i++)
               for(j=0;j<15;j++)
                       varray[i][j]=i*j;

       for(i=0;i<10;i++)
       {
               for(j=0;j<15;j++)
                       printf("%d\t",varray[i][j]);

               printf("\n");
       }

       return 0;


}

Πιστεύω να καταλάβεις τι παίζει απο τα παραπάνω.

parsifal · 25 Νοεμβρίου 2007

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

Τσούκου. realloc μπορείς να κάνεις και σε απλό δείκτη. Ένας διπλός δείκτης είναι απλά δείκτης προς έναν άλλον, απλό δείκτη. Αυτό, σε συνδυασμό με δυναμική δέσμευση μνήμης, σου επιτρέπει να εξομοιώνεις τη δημιουργία δυναμικών δισδιάστατων πινάκων, που θα μπορούσαν κάλλιστα να είναι και μη ορθογώνιοι. Π.χ ένας πίνακας Α[][]:

┌─┐

├─┼─┐

├─┼─┼─┐

└─┴─┴─┘

Ένας «πίνακας» 3 γραμμών με μεταβλητό αριθμό στηλών ανά γραμμή. Για να καταλάβεις πώς γίνεται αυτό, δες σχηματικά τα παρακάτω:

>int **A;

Δεσμεύει μία θέση μνήμης, της οποίας το περιεχόμενο πρέπει να είναι η διεύθυνση μνήμης ενός άλλου δείκτη:

>
┌─┐
└─┘

>A = (int**) malloc(3 * sizeof(int));

Δεσμεύει 3 συνεχόμενες θέσεις μνήμης, στην πρώτη από τις οποίες δείχνει ο A. Κάθε μία θέση αποτελεί ξεχωριστό δείκτη σε ακέραιο, οπότε μπορεί να αποθηκευθεί ως τιμή της η διεύθυνση μνήμης μίας μεταβλητής int:

>
┌─┐
└─┘
│
▼
┌─┐
│ │
├─┤
│ │
├─┤
│ │
└─┘

>Α[0] = (int*) malloc(sizeof(int));
Α[1] = (int*) malloc(2 * sizeof(int));
Α[2] = (int*) malloc(3 * sizeof(int));

Δεσμεύει αντίστοιχα 1, 2 και 3 συνεχόμενες θέσεις μνήμης, που στην πρώτη από καθεμιά τους δείχνουν οι προηγούμενοι 3 δείκτες:

>
┌─┐
└─┘
│
▼
┌─┐   ┌─┐
│ │──►└─┘
├─┤   ┌─┬─┐
│ │──►└─┴─┘
├─┤   ┌─┬─┬─┐
│ │──►└─┴─┴─┘
└─┘

Σκίστηκα λίγο να το βγάλω με ASCII art, αλλά πιστεύω ότι είναι αρκετά παραστατικό και θα σε βοηθήσει...

Lomar · 26 Νοεμβρίου 2007

Σας ευχαριστώ πολύ για το κόπο σας! parsifal έτσι φανταζόμουν και εγώ τα pointer, αλλά σε μια λίστα δε μπορώ να καταλάβω γιατί το 1ο στοιχείο της (head) σε κάποιες περιπτώσεις χρειάζεται 1 και σε άλλες διπλό...

Θα το κοιτάξω αύριο που θα έχω μπόλικο χρόνο και θα ξαναρωτήσω με πιο συγκεκριμένες και σαφής ερωτήσεις.

thnks anyway

parsifal · 26 Νοεμβρίου 2007

>Node *head = NULL;

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

alkisg · 26 Νοεμβρίου 2007

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

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

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

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

parsifal · 26 Νοεμβρίου 2007

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

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

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

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

Σε αυτό το παράδειγμα π.χ. που χρησιμοποιεί απλό δείκτη, που είναι το λάθος;

alkisg · 26 Νοεμβρίου 2007

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

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);

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

parsifal · 26 Νοεμβρίου 2007

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

dark_banishing · 26 Νοεμβρίου 2007

Σας ευχαριστώ πολύ για το κόπο σας! parsifal έτσι φανταζόμουν και εγώ τα pointer, αλλά σε μια λίστα δε μπορώ να καταλάβω γιατί το 1ο στοιχείο της (head) σε κάποιες περιπτώσεις χρειάζεται 1 και σε άλλες διπλό...

Θα το κοιτάξω αύριο που θα έχω μπόλικο χρόνο και θα ξαναρωτήσω με πιο συγκεκριμένες και σαφής ερωτήσεις.

thnks anyway

Λοιπόν Lomar για να το καταλάβεις πρόσεξε ένα εύκολο τρόπο.

Όταν θες να αλλάξεις την τιμή ενός int, που περνάς σε μια συνάρτηση, χωρίς να κάνεις return την τιμή του, τότε χρησιμοποιείς έναν pointer στο int δηλαδή έναν int*.

Οπότε, κατά την ίδια αναλογία, όταν θες να μεταβάλεις την τιμή ενός (head*) -χωρίς να κάνεις return την νέα τιμή- τότε χρειάζεσαι ένα pointer στο head* δηλαδή ένα head**.

Όταν δεν θες να αλλάξεις την τιμή αλλά μόνο να την χρησιμοποιήσεις τότε σου αρκεί ο head*.

Lomar · 27 Νοεμβρίου 2007

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

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

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

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

28 Νοεμβρίου 2007

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

Auto einai la8os... kaneis 10 fores allocate kai xaneis ka8e fora ton prohgoumeno pointer = memory leak

Epishs to sizeof(int) prepei na ginei sizeof(int *) ...

Lomar · 28 Νοεμβρίου 2007

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

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

Directx · 28 Νοεμβρίου 2007

Όπως τα λέει ο φίλος DiAvOl ...

Δηλαδή ...

Απλά το varray ισούται με την διεύθυνση της δεσμευμένης μνήμης που υποδεικνύει η malloc.

Τώρα αν εσύ γράψεις ξανά στο varray μια νέα malloc η παλιά διεύθυνση χάνεται καθώς αντικαθίσταται από την καινούργια..

Και εσύ δεν έχεις τρόπο να την εντοπίσεις ξανά όποτε έχεις ένα δεσμευμένο μεν αλλά χαμένο (καθώς δεν μπορείς να το χρησιμοποιήσεις) memory block ..

Δεν έχει σημασία αν καταχωρούνται δεδομένα, εσύ ζητάς από την malloc 10*sizeof(int) και αυτό σου δίνει (όσο υπάρχει διαθέσιμη μνήμη) ..

Συνεπώς αυτός ο κώδικας for είναι καταστροφή για την διαχείριση μνήμης αφού η τιμή της varray γίνεται πάντα overwrite από το νέο malloc ..

Μια πιθανή λύση η varray = i κτλ..

Καλή συνέχεια.

Υ.Γ.

Και το sizeof(int) καλό είναι ...

Lomar · 28 Νοεμβρίου 2007

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

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

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

EDIT:

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

Σύνδεση

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

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

Lomar

Red_Phantom

parsifal

Lomar

parsifal

alkisg

parsifal

alkisg

parsifal

dark_banishing

Lomar

Επισκέπτης

Lomar

Directx

Lomar

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

Σύνδεση