Struct και stack

Re4cTiV3 · 4 Ιουνίου 2012

Γίνεται μέσω αυτού του struct να κατασκευάσουμε μια δυναμική στοίβα με pop,push;

>
typedef struct datum {
int value;
float coefficient;
char * token;
} element;

migf1 · 4 Ιουνίου 2012

Αν και δεν καταλαβαίνω τι ακριβώς εννοείς όταν ρωτάς αν γίνεται, σαφώς και γίνεται. Όλα τα structs μπορείς να τα ορίσεις ως κόμβους όποιας δομής θέλεις, ορίζοντας κατάλληλα πεδία-δείκτες μέσα τους.

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

>
typedef struct datum {
...
struct datum *back;
} Datum;
...
Datum *stack = NULL;

Re4cTiV3 · 4 Ιουνίου 2012

Το ξέρω αυτό. Αλλά δεν θέλω ο pointer να είναι μέσα στο struct datum, έτσι το ξέρω. Γίνεται αλλιώς;

Το μόνο που σκέφτηκα είναι με ένα άλλο struct με έναν Pointer μέσα που θα δείχνει στο struct datum αλλά δεν ξέρω αν μπορεί να επιτυγχανθεί αυτό..

Καμία ιδεά;

migf1 · 4 Ιουνίου 2012

Το ξέρω αυτό. Αλλά δεν θέλω ο pointer να είναι μέσα στο struct datum, έτσι το ξέρω. Γίνεται αλλιώς;

Το μόνο που σκέφτηκα είναι με ένα άλλο struct με έναν Pointer μέσα που θα δείχνει στο struct datum αλλά δεν ξέρω αν μπορεί να επιτυγχανθεί αυτό..

Καμία ιδεά;

>
typedef struct Datum {
       int value;
       float coefficient;
       char * token;
}Datum;

typedef struct node Node;
struct node {
Datum *datum;  // ή Datum datum (αλλά έτσι θα σπαταλήσεις και μνήμη και ταχύτητα)
Node *back;
};
...
Node *stack;
...

Re4cTiV3 · 4 Ιουνίου 2012

Και γώ έτσι το σκέφτηκα, δυστυχώς έτσι πρεπει να γίνει η "άσκηση".Και θα γίνουν και δυο malloc ένα για το to datum και ένα για το Node? Ή μόνο ένα για το Node οπου θα προσπελαύνω τα στοιχεία με . και όχι με -> ;

migf1 · 4 Ιουνίου 2012

Αν δεν το ορίσεις ως δείκτη το datum στο Node τότε δεν χρειάζεται να το κάνεις ξεχωριστά malloc(), αρκεί να ορίσεις σχετική μεταβλητή στην main() (ή όπου τη χρειάζεσαι, απέφυγε όμως το global namespace) και μετά να την περνάς ως όρισμα σε όποιες συναρτήσεις τη χρειάζονται.

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

>
typedef struct Datum {
       int value;
       float coefficient;
       char *token;
}Datum;

typedef struct node Node;
struct node {
 Datum datum;
 Node *back
};

// ---------------------------------------
char *datum_set( Datum *datum, int value, float coeff, const char *token)
{
 if ( !datum || !token || NULL == (datum->token = strdup(token) )
return NULL;

 datum->value = value;
 datum->coefficient = coeff;

 return datum->token;
}

// ---------------------------------------
int main( void )
{
Datum datum = { .value=0, .coefficient=0.0, .token=NULL};
...
if ( !datum_set( &datum, 10, 1.3, "I'm a token") )
   	// handle error here
...
free( datum.token);
}

Η strdup() δεν είναι στάνταρ (μόνο σε περιβάλλοντα Posix είναι) αλλά μπορείς πολύ εύκολα να τη φτιάξεις. Τη χρησιμοποιώ γιατί είδα πως το token το ορίζεις ως δείκτη (οπότε ή πρέπει να το κάνεις mallloc ή να το βάλεις να δείχνει σε ένα ήδη ορισμένο string... εγώ εδώ το έκανα malloc() και του κόπιαρα την τιμή του ορίσματος token, μέσω της strdup() ).

EDIT:

Α, ξέχασα την στοίβα στον παραπάνω κώδικα

Αφού κάνεις επιτυχημένο datum_set() μετά θες κι ένα...

>
int main( void )
{
 Node *stack = NULL;
 Datum datum = { .value=0, .coefficient=0.0, .token=NULL};

if ( !datum_set( &datum, 10, 1.3, "I'm a token") )
       // handle error here
 stack_push( &stack, &datum );
...
  free( datum.token );
}

Θα σου πρότεινα το token να το ορίσεις string σταθερού μέγιστου μήκους μέσα στην Node, αλλιώς κινδυνεύεις να χάσεις την μπάλα με την δυναμική του διαχείριση.

Επίσης, αντί για datum_set() μπορείς να κάνεις τις αναθέσεις απευθείας μέσα στην stack_push()...

>bool stack_push( Node **stack,  int value, float coeff, const char *token );

Είτε έτσι είτε αλλιώς, στην stack_pop( &stack ) θα πρέπει να αποδεσμεύεις και το (*stack)->datum.token της κορυφής αν το αφήσεις όπως το έχεις τώρα (σε αυτή την περίπτωση το free(token) του προηγούμενου κώδικα θα πρέπει να το κάνεις μέσα στην stack_pop() );

Re4cTiV3 · 4 Ιουνίου 2012

Ο κώδικας κάπως έτσι;

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

/* ==================================== */
typedef struct Datum {
       int value;
       float coefficient;
       //char *token;
}Datum;

typedef struct node {
       Datum datumPtr;
       struct node *back;
}Node;
/* ===================================== */
void push(Node **top, int info1, float info2);
void pop(Node **top);
void printStack(Node *top);

int main(int argc, char *argv[])
{
 Node *top = NULL;
  
 pop(&top);

 push(&top, 3, 3.3); 
 push(&top, 5, 5.3);
 push(&top, 7, 7.3);

 
 printStack(top);
 pop(&top);
 puts("\n");
 printStack(top);
 pop(&top);
 puts("\n");
 printStack(top);
 pop(&top);
 puts("\n");
 printStack(top);
 pop(&top);
 puts("\n");
 printStack(top);
 puts("\n");
 system("PAUSE");	
 return 0;
}

void push(Node **top, int info1, float info2) {
    Node * newPtr = (Node*)malloc(sizeof(Node));
    Datum* newDatPtr = (Datum*)malloc(sizeof(Datum));
    
    if (newPtr != NULL) {
       newDatPtr->value = info1;
       newDatPtr->coefficient = info2;
       newPtr->datumPtr = *newDatPtr;
       newPtr->back = *top;
       *top = newPtr;
    }
    else
        printf("Not enough memory.\n\n");
}

void pop(Node **top) {
    if(!isEmpty(top)) {
              Node* tempPtr;
              tempPtr = *top;
              *top = (*top)->back;
              free( tempPtr );
              printf("Popped.\n\n");
    }
    else printf("Nothing to pop from the list.\n\n");
}
    
void printStack(Node *top) {
    printf("|==============|\n");
    if(!isEmpty(&top)) {
       while(top != NULL) { 
                     printf("|  (%d - %g)   |\n",top->datumPtr.value,top->datumPtr.coefficient);
                     printf("|==============|\n");
              top = top->back;
       }
       printf("|              |\n");
       printf("|              |\n");
    }
    else printf("Empty stack list.\n\n");
}

int isEmpty(Node *top) { return top == NULL; }

τα χω κάνει μαντάρα;;

Επεξ/σία 4 Ιουνίου 2012 από Re4cTiV3

migf1 · 4 Ιουνίου 2012

Ο κώδικας κάπως έτσι;

>
typedef struct Datum {
       int value;
       float coefficient;
       //char *token;
}Datum;

typedef struct node {
       Datum datumPtr;
       struct node *back;
}Node;

void push(Node **top, int info1, float info2) {
	Node * newPtr = (Node*)malloc(sizeof(Node));
	Datum* newDatPtr = (Datum*)malloc(sizeof(Datum));
	
	if (newPtr != NULL) {
       newDatPtr->value = info1;
       newDatPtr->coefficient = info2;
       newPtr->datumPtr = newDatPtr;
       newPtr->back = *top;
       *top = newPtr;
	}
	else
		printf("Not enough memory.\n\n");
}

void pop(Node **top) {
	if(!isEmpty(top)) {
      		Node* tempPtr;
      		tempPtr = *top;
      		*top = (*top)->back;
      		//free(    tempPtr->(*datumPtr)  ); /* xreiazetai kati tetoio???? */
      		free(tempPtr);
      		printf("Popped.\n\n");
	}
	else printf("Nothing to pop from the stack.\n\n");
}

void printStack(Node *top) {
	if(!isEmpty(&top)) {
       while(top->back != NULL) { 
      		printf("|-------|\n"
                     "|   (%d,%g)   |\n",top->datumPtr.value,top->datumPtr.coefficient);
      		top = top->back;
       }
       printf("|              |\n");
       printf("|              |\n");
	}
	else printf("Empty stack.\n\n");
}

int isEmpty(Node *top) { return top->back == NULL; }


int main(int argc, char *argv[])
{
 Node *top = NULL;
 
 push(&top, 3, 3.3); // pou phgainei auto to stoixeio? :S
 push(&top, 5, 5.3);
 push(&top, 7, 7.3);
 
 printStack(top);
 
 pop(&top);
 pop(&top);
 pop(&top);
 
 printStack(top); //crasharei kapou edw
 
 system("PAUSE");	
 return 0;
}

τα χω κάνει μαντάρα μπερδεύτηκα τελείως!

Βασικά επειδή πήζω με τη μετάφραση της Pelles C από το πρωί και το μυαλό μου έχει κουρκουτιάνει ήδη, δεν μου είναι εύκολο να κάνω Trace τον κώδικά σου αυτή τη στιγμή. Πρόχειρα βλέπω όμως πως κάνεις malloc() και το Datum μέσα στην pop() push()... δεν χρειάζεται... από τη στιγμή που το "datumPtr" ΔΕΝ το ορίζεις ως δείκτη μέσα στη δομή Node (άρα δεν χρειάζεται και το Ptr στο τέλος του ονόματος του ) αρκεί μονάχα το malloc() της Node μέσα στην pop() push(), διότι...

sizeof(Node) = sizeof(Datum) + sizeof(Node *);

Re4cTiV3 · 4 Ιουνίου 2012

Επειδή έκανα edit το ποστ πριν..όταν μπορέσεις δες πως είναι τώρα ο κώδικας για να μην ξανακάνω copy paste...

και πως θα βάλω να δείχνει ο Node->datumPtr στο struct datum(Datum) ; :/

migf1 · 4 Ιουνίου 2012

Επειδή έκανα edit το ποστ πριν..όταν μπορέσεις δες πως είναι τώρα ο κώδικας για να μην ξανακάνω copy paste...΄

Οκ, αλλά πιο μετά.

και πως θα βάλω να δείχνει ο Node->datumPtr στο struct datum(Datum) ; :/

Έτσι όπως το 'χεις δεν είναι δείκτης το datumPtr, δεν χρειάζεται ξεχωριστό malloc(). Αρκεί το malloc() που κάνεις στην Node κι από εκεί και πέρα έχεις απευθείας πρόσβαση στο πεδίο datumPtr, με: node->datumPtr (σβήστο το Ptr από το όνομα, γιατί αποπροσανατολίζει αφού δεν είναι δείκτης αυτό το πεδίο).

ΥΓ. Στο προηγούμενο ποστ γράφω pop() αντί για push() που ήθελα να γράψω.

Re4cTiV3 · 4 Ιουνίου 2012

Άρα κάτι τέτοιο. :)

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

/* ==================================== */
typedef struct Datum {
       int value;
       float coefficient;
       //char *token;
}Datum;

typedef struct node {
       Datum datum;
       struct node *back;
}Node;
/* ===================================== */

void push(Node **, int , float );
void pop(Node **);
void printStack(Node *);
int isEmpty(Node *);

int main(int argc, char *argv[])
{
 Node *top = NULL;
  
 pop(&top);
 
 push(&top, 3, 3.3); 
 push(&top, 5, 5.3);
 push(&top, 7, 7.3);

 
 printStack(top);
 pop(&top);
 puts("\n");
 printStack(top);
 pop(&top);
 puts("\n");
 printStack(top);
 pop(&top);
 puts("\n");
 printStack(top);
 pop(&top);
 puts("\n");
 printStack(top);
 puts("\n");
 system("PAUSE");	
 return 0;
}

void push(Node **top, int info1, float info2) {
    Node * newPtr = (Node*)malloc(sizeof(Node));
    
    if (newPtr != NULL) {
       Datum newDat;
       newDat.value = info1;
       newDat.coefficient = info2;
       newPtr->datum = newDat;
       newPtr->back = *top;
       *top = newPtr;
    }
    else
        printf("Not enough memory.\n\n");
}

void pop(Node **top) {
    if(!isEmpty(*top)) {
              Node* tempPtr;
              tempPtr = *top;
              *top = (*top)->back;
              free( tempPtr );
              printf("Popped.\n\n");
    }
    else printf("Nothing to pop from the list.\n\n");
}
    
void printStack(Node *top) {
    if(!isEmpty(top)) {
       printf("|==============|\n");
       while(top != NULL) { 
                     printf("|  (%d - %g)   |\n",top->datum.value,top->datum.coefficient);
                     printf("|==============|\n");
              top = top->back;
       }
       printf("|              |\n");
       printf("|              |\n");
    }
    else printf("Empty stack list.\n\n");
}

int isEmpty(Node *top) { return top == NULL; }

migf1 · 4 Ιουνίου 2012

Ναι (εφόσον σου δουλεύει, γιατί δεν το έχω τσεκάρει).

Απλοποίησε και την push() σε ...

>
void push(Node **top, int info1, float info2) {
    Node * newPtr = (Node*)malloc(sizeof(Node));
    
    if (newPtr != NULL) {
       newPtr->datum.value = info1;
       newPtr->datum.coefficient = info2;
       newPtr->back = *top;
       *top = newPtr;
    }
    else
        printf("Not enough memory.\n\n");
}

και είσαι jet

Re4cTiV3 · 4 Ιουνίου 2012

Μια χαρά και έτσι.Δεν ήταν άσκηση για την σχολή αλλα ήταν άσκηση για μένα

migf1 · 4 Ιουνίου 2012

Σούπερ

Downloadpercent · 4 Ιουνίου 2012

http://pastebin.com/egrSZiX2

Να και μια εικόνα

Σύνδεση

Struct και stack

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

Re4cTiV3

Συχνή συμμετοχή στο θέμα

Δημοφιλείς Ημέρες

Συχνή συμμετοχή στο θέμα

Δημοφιλείς Ημέρες

migf1

Re4cTiV3

migf1

Re4cTiV3

migf1

Re4cTiV3

migf1

Re4cTiV3

migf1

Re4cTiV3

migf1

Re4cTiV3

migf1

Downloadpercent

Δημιουργήστε ένα λογαριασμό ή συνδεθείτε για να σχολιάσετε

Δημιουργία λογαριασμού

Σύνδεση

Σύνδεση