Ερωτήσεις για C

migf1 · 29 Οκτωβρίου 2012

Yeap, αναφέρθηκε σχετικά και ο imitheos στην απάντησή του.

Η μεγάλη πλειοψηφία των compilers τους υλοποιούν με ίδιο μέγεθος (με πιο συχνή εξαίρεση τους void). Αντί για assert μπορεί κανείς να χρησιμοποιεί casting που είναι πολύ πιο ευέλικτο, αλλά γενικώς όντως δεν πρέπει κανείς να βασίζει τον κώδικά του σε αυτή την υπόθεση.

nik324 · 29 Οκτωβρίου 2012

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

Εχω τα εξης structs

>
typedef struct a{
int aValue;
struct a *next;
}A;
typedef struct b{
int bValue;
struct b *next;
A *p;	
}B;

Κανοντας μια αναζητηση στην λιστα Β, επιστρεφω ενα pointer τυπου B, σε ενα απο τους κομβους της λιστας Β (εστω οτι θελω να εισαγω μια λιστα στην οποια δειχνει το πεδιο p της λιστας Β)

Ως τωρα εχω ενα δεικτη (εστω ο ptr- ο οποιος ειναι τυπου A ) στον κομβο της λιστας οπου θελω να προσθεσω μια αλλη λιστα...

Exω και μια συναρτηση p *Insert(B *list, type value)...

Kαμια συμβουλη για το πως θα το κανω;

Μπερδευεnται οi τυποi των μεταβλητων που χρησιμοποιω στην συναρτηση Insert() και δεν μπρορω να βγαλω ακρη

imitheos · 29 Οκτωβρίου 2012

Για όποιον ενδιαφέρεται, δεν είναι απαραίτητο ότι όλοι οι pointers έχουν το ίδιο μέγεθος:

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

Yeap, αναφέρθηκε σχετικά και ο imitheos στην απάντησή του.

Η μεγάλη πλειοψηφία των compilers τους υλοποιούν με ίδιο μέγεθος (με πιο συχνή εξαίρεση τους void). Αντί για assert μπορεί κανείς να χρησιμοποιεί casting που είναι πολύ πιο ευέλικτο, αλλά γενικώς όντως δεν πρέπει κανείς να βασίζει τον κώδικά του σε αυτή την υπόθεση.

Ναι καλύτερα να μην χρησιμοποιούνται τέτοιες μαγκιές. Στην πιο ειδική περίπτωση που θέλουμε να χρησιμοποιήσουμε ένα δείκτη σαν αριθμό μπορεί να γίνει χρήση του uintptr_t που παρέχει η C99. ΑΝ η πλατφόρμα εμφανίζει την μνήμη σαν μια flat μονοκόμματη περιοχή τότε ένας C99 compiler είναι υποχρεωμένος να παρέχει τον uintptr_t οπότε σχεδόν παντού θα υλοποιείται αλλά και πάλι δεν είμαστε σίγουροι για την ύπαρξή του.

Μια (ψιλοάχρηστη πλέον) σημείωση είναι ότι ακόμη και για ίδιο τύπο δεν μας εγγυάται ότι δύο δείκτες θα έχουν ίδιο μέγεθος. Σε DOS σε μοντέλο με near δείκτες (μέχρι και medium νομίζω) ένας απλός δείκτης σε int θα έδειχνε στο παρόν segment ενώ μπορούσαμε να δηλώσουμε και far δείκτη (πχ να δείχνει στην περιοχή 0040:τάδε για να πάρουμε κάποια πληροφορία από την cmos ή οπουδήποτε) που θα είχε άλλο μέγεθος.

Edit:

Κανοντας μια αναζητηση στην λιστα Β, επιστρεφω ενα pointer τυπου B, σε ενα απο τους κομβους της λιστας Β (εστω οτι θελω να εισαγω μια λιστα στην οποια δειχνει το πεδιο p της λιστας Β)

Ως τωρα εχω ενα δεικτη (εστω ο ptr- ο οποιος ειναι τυπου A ) στον κομβο της λιστας οπου θελω να προσθεσω μια αλλη λιστα...

Exω και μια συναρτηση p *Insert(B *list, type value)...

Kαμια συμβουλη για το πως θα το κανω;

Μπερδευεnται οi τυποi των μεταβλητων που χρησιμοποιω στην συναρτηση Insert() και δεν μπρορω να βγαλω ακρη

Μάλλον δεν κατάλαβα αλλά ας ρωτήσω. Κάνεις μια αναζήτηση με κάποια κριτήρια στη λίστα Β και βρίσκεις τον Χ κόμβο. Μετά θέλεις να προσθέσεις ένα νέο κόμβο μετά από τον Χ που βρήκες με την αναζήτηση ?

nik324 · 29 Οκτωβρίου 2012

Μάλλον δεν κατάλαβα αλλά ας ρωτήσω. Κάνεις μια αναζήτηση με κάποια κριτήρια στη λίστα Β και βρίσκεις τον Χ κόμβο. Μετά θέλεις να προσθέσεις ένα νέο κόμβο μετά από τον Χ που βρήκες με την αναζήτηση ?

Ο κομβος Χ ,εκτος των αλλων, περιεχει και ενα δεικτη σε μια αλλη λιστα, στην οποια θελω να προσθεσω ενα κομβο!

migf1 · 29 Οκτωβρίου 2012

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

Εχω τα εξης structs...
>
typedef struct a{
int aValue;
struct a *next;
}A;
typedef struct b{
int bValue;
struct b *next;
A *p;    
}B;
Κανοντας μια αναζητηση στην λιστα Β, επιστρεφω ενα pointer τυπου B, σε ενα απο τους κομβους της λιστας Β (εστω οτι θελω να εισαγω μια λιστα στην οποια δειχνει το πεδιο p της λιστας Β)

Ως τωρα εχω ενα δεικτη (εστω ο ptr- ο οποιος ειναι τυπου A ) στον κομβο της λιστας οπου θελω να προσθεσω μια αλλη λιστα...

Exω και μια συναρτηση p *Insert(B *list, type value)...

Kαμια συμβουλη για το πως θα το κανω;

Μπερδευεnται οi τυποi των μεταβλητων που χρησιμοποιω στην συναρτηση Insert() και δεν μπρορω να βγαλω ακρη

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

>
typedef struct CollisionNode {
   int nodePos;
   struct CollisionNode *next;
}CollisionNode ;

typedef struct HashNode {
   int nodePos;
   struct HashNode *next;
   CollisionNode *collisionList;
}HashNode;

...
HashNode *hashList = NULL;

Δηλαδή κάτι σαν μια hash-list, ο κάθε κόμβος της οποίας περιέχει την έναρξη μια λίστας από πιθανά collisions?

Αν ναι, πες μας τι προσπαθείς να κάνεις και δεν σου βγαίνει.

nik324 · 29 Οκτωβρίου 2012

αν το γραψω ετσι, ειναι πιο ξεκαθαρο; Γιατι οπως το εγραψες εσυ με μπερδεψε...

>
typedef struct CollisionNode {
 int nodePos;
 struct CollistionNode *next;
}COLLISIONNODE;
typedef struct HashNode {
 int nodePos;
 struct hashNode *next;
 COLLISIONNODE *collisionList;
}HASHNODE;

Το παραπανω ειναι η δομη μου...Να προχωρισω σε μερικες ερωτησεις;

Ευχασιστω πολυ για την ανταποκριση

>
type (*)Inseert( type *list, int value )   //δεν ξερω αν πρεπει να επιστεψω δεικτη η οχι
{
    type *new = calloc(1, sizeof(type) );
    if ( !new )
		    return;
    new->value = value;
    new->next = list;
    list = new;
    return;
}

Εστω η παταπανω συναρτηση εισαγωγης κομβου στης αρχη...Της περνας σας ορισμα ενα δεικτη που δειχνει σε ενα απο τα HASHNODE...

migf1 · 29 Οκτωβρίου 2012

Με το δίκιο σου, γιατί είχα κάνει κάτι typos, τα οποία και διόρθωσα με edit.

Οπότε το ίδιο πράγμα εννοούμε, σωστά; (btw κατά τις περισσότερες συμβάσεις με όλα κεφαλαία γράφουμε τα macros και λοιπά pre-proccessor directives, οπότε προσπάθησε να ακολουθείς τις συμβάσεις στους κώδικές σου).

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

>
typedef struct CollisionNode CollisionNode;
struct CollisionNode{
   int nodePos;
   CollisionNode *next;
}CollisionNode ;

typedef struct HashNode HashNode;
struct HashNode {
   int nodePos;
   HashNode *next;
   CollisionNode *collisionList;
}HashNode;

...
HashNode *hashList = NULL;

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

Παράθεσέ μας το πρώτο πρόβλημα...

nik324 · 29 Οκτωβρίου 2012

Κανω αναζητηση στην λιστα hashnode και οταν βρεθει η ζητουμενη τιμη nodePos επιστρεφω ενα δεικτη(που ειναι τυπου hashnode-σωστα; ) σε αυτο το node.

Αφου εχω προσβαση στoν μομβο της λιστας hashnode , θελω ακολουθώντας τον δεικτη *collitionList , να δημιουργησω μια κανουργια λιστα...Στην συναρτηση ομως Ιnsert μπερδευονταιι οι τυποι μεταβλητων, δηλαδη κανω α=β την στιμη που το α ειναι τυπου hashnode και το β ειναι τυπου collitionList..

migf1 · 29 Οκτωβρίου 2012

Μαζί γράφουμε

Οπότε έθετες την 1η απορία όσα έγραφα.

Αυτή η insert αναφέρεται στην hashList ή στην collisionList ενός κόμβου της hashList? Προφανώς χρειάζεσαι 2 ξεχωριστές συναρτήσεις για το καθένα.

Επίσης καλό είναι να μην τις αφήσεις έτσι τις δομές σου, αν δλδ πρόκειται για λίστες όπως συμφωνήσαμε, αλλά να δημιουργήσεις άλλες 2 με head/tail pointers στην κάθεμιά τους...

>
typedef struct CollisionNode CollisionNode;
struct CollisionNode{
       int nodePos;
       CollisionNode *next;
}CollisionNode ;

typedef struct CollisionList {
   CollisionNode *head, *tail;
   size_t len;
}CollisionList;

typedef struct HashNode HashNode;
struct HashNode {
       int nodePos;
       HashNode *next;
       CollisionList collisionList;
}HashNode;

typedef struct HashList {
   HashNode *head, *tail;
   size_t len;
}HashList;
...
HashNode hashList = {NULL, NULL, 0);

Τις hashList και collisionList τις "κατέβασα" στους ορισμούς τους από pointers σε απλά structs, για να διευκολυνθούμε στον μετέπειτα κώδικα.

EDIT:

Φεύγω για σπίτι, θα είμαι εκεί σε καμια ώρα.

nik324 · 29 Οκτωβρίου 2012

Μαζί γράφουμε

Οπότε έθετες την 1η απορία όσα έγραφα.

Αυτή η insert αναφέρεται στην hashList ή στην collisionList ενός κόμβου της hashList? Προφανώς χρειάζεσαι 2 ξεχωριστές συναρτήσεις για το καθένα.

Insert στην collisionList , στην οποια δειχνει ο δεικτης του πεδιου της hashlist...

imitheos · 29 Οκτωβρίου 2012

Insert στην collisionList , στην οποια δειχνει ο δεικτης του πεδιου της hashlist...

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

typedef struct CollisionNode CollisionNode;
struct CollisionNode{
       int nodePos;
       CollisionNode *next;
};

typedef struct HashNode HashNode;
struct HashNode {
       int nodePos;
       HashNode *next;
       CollisionNode *collisionList;
};

int insertCNatHN(HashNode *node, int value);
void print(HashNode *node);

int main(void)
{
   CollisionNode mycn = { 0, NULL };
   HashNode myhn = { 2, NULL, &mycn };

   insertCNatHN(&myhn, 3);
   insertCNatHN(&myhn, 4);
   print(&myhn);

   return 0;
}

int insertCNatHN(HashNode *node, int value)
{
   CollisionNode *temp;

   temp = node->collisionList;
   while (temp->next != NULL)
       temp = temp->next;
   temp->next = malloc(sizeof(CollisionNode));
   temp = temp->next;

   temp->nodePos = value;
   temp->next = NULL;

   return 0;
}

void print(HashNode *node)
{
   CollisionNode *temp;
   temp = node->collisionList;
   while (temp != NULL) {
       printf("%d\n", temp->nodePos);
       temp = temp->next;
   }
}
Έξοδος:
0
3
4

Κάτι τέτοιο θέλεις ? Ξεκινάμε με την HashNode να έχει ένα κόμβο μόνο με τιμές 2 και μια διεύθυνση CollisionNode η οποία περιέχει μόνο ένα κόμβο με τιμή 0. Η συνάρτηση δέχεται ένα κόμβο σε HashNode και εισάγει CollisionNodes στο τέλος. Δεν πραγματοποιεί κανένα από τους απαραίτητους ελέγχους φυσικά.

nik324 · 29 Οκτωβρίου 2012

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

typedef struct CollisionNode CollisionNode;
struct CollisionNode{
int nodePos;
CollisionNode *next;
};

typedef struct HashNode HashNode;
struct HashNode {
int nodePos;
HashNode *next;
CollisionNode *collisionList;
};

int insertCNatHN(HashNode *node, int value);
void print(HashNode *node);

int main(void)
{
CollisionNode mycn = { 0, NULL };
HashNode myhn = { 2, NULL, &mycn };

insertCNatHN(&myhn, 3);
insertCNatHN(&myhn, 4);
print(&myhn);

return 0;
}

int insertCNatHN(HashNode *node, int value)
{
CollisionNode *temp;

temp = node->collisionList;
while (temp->next != NULL)
temp = temp->next;
temp->next = malloc(sizeof(CollisionNode));
temp = temp->next;

temp->nodePos = value;
temp->next = NULL;

return 0;
}

void print(HashNode *node)
{
CollisionNode *temp;
temp = node->collisionList;
while (temp != NULL) {
printf("%d\n", temp->nodePos);
temp = temp->next;
}
}
Έξοδος:
0
3
4
Κάτι τέτοιο θέλεις ? Ξεκινάμε με την HashNode να έχει ένα κόμβο μόνο με τιμές 2 και μια διεύθυνση CollisionNode η οποία περιέχει μόνο ένα κόμβο με τιμή 0. Η συνάρτηση δέχεται ένα κόμβο σε HashNode και εισάγει CollisionNodes στο τέλος. Δεν πραγματοποιεί κανένα από τους απαραίτητους ελέγχους φυσικά.

Θα το κοιταξω αργοτερα, γιατι τωρα εχω μαθημα...

Ευχαριστω πολυ παντως για τις απαντησεις!

παπι · 29 Οκτωβρίου 2012

Μπορούμε να ελέγχουμε αν ένας void pointer δείχνει σε int ή long κτλ;

Οχι, πρεπει να φτιαξεις κατι τετοιο

>


char TypeOf(void* p)
{
return *((char*)p - 1);
}

void* MallocEx(size_t size,char type)
{
char* p = malloc(size+1);
*p = type;
return ++p;
}
void FreeEx(void* p)
{
free( (char*)p - 1);
}
typedef void* ptr;
#define INTTYPE 1
#define FLOATTYPE 2
#define ARRAYINYTYPE 3
//..

int main(int argc, char **argv)
{
ptr p1,p2,p3,p4,p5;
p1 = MallocEx(sizeof(int),INTTYPE);
p2 = MallocEx(sizeof(float),FLOATTYPE);
p3 = MallocEx(sizeof(int) * 10, ARRAYINYTYPE);
p4 = MallocEx(sizeof(int),INTTYPE);

printf(
"p1==p2 %d\n"
"p1==p3 %d\n"
"p1==p4 %d\n",
TypeOf(p1)==TypeOf(p2),
TypeOf(p1)==TypeOf(p3),
TypeOf(p1)==TypeOf(p4)
);
FreeEx(p1);
FreeEx(p2);
FreeEx(p3);
FreeEx(p4);

return 0;
}

migf1 · 29 Οκτωβρίου 2012

Κανω αναζητηση στην λιστα hashnode και οταν βρεθει η ζητουμενη τιμη nodePos επιστρεφω ενα δεικτη(που ειναι τυπου hashnode-σωστα; ) σε αυτο το node.

Αφου εχω προσβαση στoν μομβο της λιστας hashnode , θελω ακολουθώντας τον δεικτη *collitionList , να δημιουργησω μια κανουργια λιστα...Στην συναρτηση ομως Ιnsert μπερδευονταιι οι τυποι μεταβλητων, δηλαδη κανω α=β την στιμη που το α ειναι τυπου hashnode και το β ειναι τυπου collitionList..

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

Λοιπόν, τα πάντα εξαρτώνται για μια ακόμα φορά από τα ζητούμενα του project. Δηλαδή δεν υπάρχει μια υλοποίηση.

Σου έγραψα ένα μικρό πρόγραμμα πάνω σε αυτά που σου πρότεινα (hopefully πλήρες, δλδ με sanity-checks, error-checks, κλπ)...

>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <stdbool.h>            // C99

#define errMSG( msg )            \
do {                    \
   fprintf(stderr, "%s\n", (msg) );\
   fprintf(stderr, "*** file:%s | line:%d | %s()\n", __FILE__, __LINE__, __func__ );    \
   fflush( stderr );        \
}while(0)

/**
* struct describing a collision node
*/
typedef struct ColliNode{
   size_t         pos;        // node's position in the collision-list
   struct ColliNode *next;        // pointer to the next node in the collision-list
}ColliNode;

/**
* struct describing a collision-list (with head & tail)
*/
typedef struct ColliList {
   ColliNode     *head;        // this is the start of the collision-list
   ColliNode     *tail;        // pointer to the last node of the collision-list
   size_t         len;        // the length of the collision-list (total # of nodes)
}ColliList;

/**
* struct describing a hash node
*/
typedef struct HashNode {
   size_t         pos;        // node's position in the hasing-list
   struct HashNode  *next;        // pointer to the next node in the hashing-list
   ColliList     colliList;    // the collision-list of this particular hash-node
}HashNode;

/**
* struct describing a hashing list (with head & tail)
*/
typedef struct HashList {
   HashNode     *head;        // this is the start of the hashing-list
   HashNode     *tail;        // pointer to the last node of the hashing-list
   size_t         len;        // the length of the hashing-list (total # of nodes)
}HashList;


/*************************************************//**
* Create & append a node at the end of the specified collision-list
* (node->pos is auto-set)
*****************************************************
*/
bool colliList_append_auto( ColliList *colliList )
{
   ColliNode *newNode = NULL;

   if ( !colliList ) {
       errMSG( "*** INTERNAL ERROR (invalid pointer) ***" );
       return false;
   }

   newNode = malloc( sizeof(ColliNode) );
   if ( !newNode )
       return false;

   newNode->next = NULL;

   // when colliList is empty
   if ( NULL == colliList->tail ) {
       newNode->pos = 0;
       colliList->head = colliList->tail = newNode;
       colliList->len = 1;
       return true;
   }

   // when colliList in NOT empty
   newNode->pos         = colliList->len;
   colliList->tail->next     = newNode;
   colliList->tail     = newNode;
   (colliList->len)++;

   return true;
}

/*************************************************//**
* Collision-list destructor.
*****************************************************
*/
bool colliList_free( ColliList *colliList )
{
   ColliNode *dummy = NULL;

   if ( !colliList ) {
       errMSG( "*** INTERNAL ERROR (invalid pointer) ***" );
       return false;
   }

   while ( colliList->head ) {
       dummy = colliList->head->next;
       free( colliList->head );
       colliList->head = dummy;
   }
   colliList->head = colliList->tail = NULL;
   colliList->len = 0;

   return true;
}

/*************************************************//**
*
*****************************************************
*/
bool colliList_print( const ColliList *colliList )
{
   ColliNode *walk = NULL;

   if ( !colliList ) {
       errMSG( "*** INTERNAL ERROR (invalid pointer) ***" );
       return false;
   }

   printf( "\tcollisions: " );

   if ( NULL == colliList->head ) {
       puts( "NULL" );
       fflush( stdout );
       return true;
   }

   walk = colliList->head;
   while ( walk ) {
       printf("%zu ", walk->pos );
       walk = walk->next;
   }
   puts("\b");
   fflush( stdout );

   return true;
}

/*************************************************//**
* Create & append a node to the end of the specified hashing-list
* (node->pos is auto-set)
*****************************************************
*/
bool hashList_append_auto( HashList *hashList )
{
   HashNode *newNode = NULL;

   if ( !hashList ) {
       errMSG( "*** INTERNAL ERROR (invalid pointer) ***" );
       return false;
   }

   newNode = malloc( sizeof(HashNode) );
   if ( !newNode )
       return false;

   newNode->colliList.head = newNode->colliList.tail = NULL;
   newNode->colliList.len = 0;
   newNode->next = NULL;

   // when hashList is empty
   if ( NULL == hashList->tail ) {
       newNode->pos = 0;
       hashList->head = hashList->tail = newNode;
       hashList->len = 1;
       return true;
   }

   // when hashList in NOT empty
   newNode->pos         = hashList->len;
   hashList->tail->next     = newNode;
   hashList->tail         = newNode;
   (hashList->len)++;

   return true;
}

/*************************************************//**
* Hashing-list destructor.
*****************************************************
*/
bool hashList_free( HashList *hashList )
{
   HashNode *dummy = NULL;

   if ( !hashList )
       return false;

   while ( hashList->head ) {
       dummy = hashList->head->next;
       colliList_free( &hashList->head->colliList );
       free( hashList->head );
       hashList->head = dummy;
   }
   hashList->head = hashList->tail = NULL;
   hashList->len = 0;

   return true;
}

/*************************************************//**
*
*****************************************************
*/
bool hashList_print( const HashList *hashList )
{
   HashNode *walk = NULL;

   if ( !hashList ) {
       errMSG( "*** INTERNAL ERROR (invalid pointer) ***" );
       return false;
   }

   if ( NULL == hashList->head ) {
       puts( "\tNULL" );
       fflush( stdout );
       return true;
   }

   walk = hashList->head;
   while ( walk ) {
       printf("HASHPOS %zu\n", walk->pos );
       colliList_print( &walk->colliList );
       walk = walk->next;
   }
   putchar('\n');

   return true;
}

/*************************************************//**
* @brief    Lookup the specified hashing-list for its pos'th node.
* @return     A pointer to the pos'th node, or NULL if there's no pos'th node.
*****************************************************
*/
HashNode *hashList_lookup_pos( const HashList *hashList, size_t pos )
{
   HashNode *walk = NULL;

   if ( !hashList ) {
       errMSG( "*** INTERNAL ERROR (invalid pointer) ***" );
       return NULL;
   }

   if ( pos > hashList->len - 1 ) {
       printf( "__%2zu__ No such position in the hashList\n", pos );
       return NULL;
   }

   walk = hashList->head;
   while ( walk && walk->pos < pos )
       walk = walk->next;

   return walk;
}

/*************************************************//**
* UNUSED ****
*****************************************************
*/
/*
bool hashList_hash_pos( HashList *hashList, size_t pos )
{
   HashNode *temp = NULL;

   if ( !hashList ) {
       errMSG( "*** INTERNAL ERROR (invalid pointer) ***" );
       return false;
   }

   temp = hashList_lookup_pos( hashList, pos );
   if ( NULL == temp )
       return false;

   return colliList_append_auto( &temp->colliList );
}
*/

/*************************************************//**
*
*****************************************************
*/
int main( void )
{
   const int maxHASHNODES    = 5;
   HashList hashList     = { .head=NULL, .tail=NULL, .len=0 };
   size_t tempPos         = 0;
   HashNode *tempHashNode     = NULL;

   srand( time(NULL) );

   // create the hashing-list with maxHASHNODES nodes (positions) 
   for (int i=0; i < maxHASHNODES; i++)
       hashList_append_auto( &hashList );

   // generate & hash 30 positions, ranging from 0 to 14
   // (those that are less than maxHASHNODES will be left un-hashed)
   for (int i=0; i < 30; i++) {
       tempPos        = rand() % 15;
       tempHashNode     = hashList_lookup_pos(&hashList, tempPos);
       if ( tempHashNode && colliList_append_auto( &tempHashNode->colliList) )
           printf( "%zu has been hashed successfully\n", tempPos );
   }
   system( "pause" );

   puts( "\n________HASHING-LIST CONTENTS________\n" );
   hashList_print( &hashList );

   hashList_free( &hashList );

   system( "pause" );
   exit( EXIT_SUCCESS );
}

με μια πιθανή έξοδο αυτήν...

>
__ 9__ No such position in the hashList
2 has been hashed successfully
__ 5__ No such position in the hashList
__ 8__ No such position in the hashList
__ 9__ No such position in the hashList
0 has been hashed successfully
4 has been hashed successfully
__10__ No such position in the hashList
__13__ No such position in the hashList
2 has been hashed successfully
3 has been hashed successfully
0 has been hashed successfully
__ 8__ No such position in the hashList
1 has been hashed successfully
__14__ No such position in the hashList
__10__ No such position in the hashList
__ 6__ No such position in the hashList
__ 9__ No such position in the hashList
__11__ No such position in the hashList
__ 9__ No such position in the hashList
__13__ No such position in the hashList
2 has been hashed successfully
__ 9__ No such position in the hashList
1 has been hashed successfully
__12__ No such position in the hashList
__ 5__ No such position in the hashList
__12__ No such position in the hashList
1 has been hashed successfully
__ 9__ No such position in the hashList
1 has been hashed successfully
Press any key to continue . . .

>
________HASHING-LIST CONTENTS________

HASHPOS 0
   collisions: 0 1 
HASHPOS 1
   collisions: 0 1 2 3 
HASHPOS 2
   collisions: 0 1 2 
HASHPOS 3
   collisions: 0 
HASHPOS 4
   collisions: 0 
Press any key to continue . . .

Ο κώδικας χρησιμοποιεί ξεχωριστές δομές HashList και ColliList για την κεντρική hashing-list και τις επιμέρους collision-lists στον κάθε της κόμβο, αντίστοιχα.

Αυτές οι ξεχωριστές δομές (που ορίζονται ως απλές μεταβλητές και όχι δείκτες) διατηρούν τον δείκτη έναρξης της λίστας που αντιπροσωπεύουν (δηλαδή τον list->head) καθώς επίσης και δυο ακόμα πεδία που κάνουν το πρόγραμμά μας πολύ πιο efficient: έναν δείκτη στον τελευταίο κόμβο της λίστας (list->tail) και το μήκος της λίστας (list->len).

Οι κόμβοι των λιστών δεν περιέχουν data. Αντί για data χρησιμοποιώ τα index-numbers των κόμβων (αύξοντες αριθμούς δηλαδή) στο πεδίο pos, το οποίο κι ενημερώνω αυτόματα κατά την εισαγωγή του κάθε κόμβου.

Η συγκεκριμένη υλοποίηση κρίνεται ως efficient διότι:

Οι εισαγωγές γίνονται πάντα στο τέλος της λίστας σε O(1) λόγω της ύπαρξης του δείκτη: list->tail
Η ενημέρωση του index-number (pos) σε κάθε κόμβο γίνεται επίσης σε Ο(1) λόγω της ύπαρξης του πεδίου: list->len (και λόγω του ότι οι εισαγωγές γίνονται πάντα στο τέλος της λίστας).

Επίσης, δεν μπουκώνει με ορίσματα τις συναρτήσεις διαχείρισης των λιστών, αφού ότι χρειάζεται η κάθε λίστα τα διατηρεί ως πεδία στην κεντρική δομή της (δλδ τα πεδία tail και len που αναφέρω παραπάνω, καθώς και οποιοδήποτε άλλο απαιτούν οι ανάγκες κάποιου άλλου project). Οπότε στις συναρτήσεις μας αρκεί να περάσουμε είτε ας πούμε by-ref την βασική μεταβλητή της όποιας λίστας μας (xxxList *) είτε ας πούμε by-val έναν δείκτη σε αυτή την μεταβλητή (const xxxList *).

Επειδή λοιπόν δεν υπάρχουν actual data στους κόμβους, ότι κάνω το κάνω με τα index-numbers των κόμβων.

Αρχικά φτιάχνω με ένα for-loop την hashing-list (hashList) να έχει maxHASHNODES κόμβους, κι έπειτα σε ένα δεύτερο for-loop δημιουργώ και... hash-άρω 30 τυχαία νούμερα, με εύρος τιμών από το 0 έως και το 14.

Όσα από αυτά είναι μεγαλύτερα από το συνολικό πλήθος κόμβων της hashList (maxHASHNODES) μένουν α-hash-άριστα, ενώ τα υπόλοιπα hash-άρονται στην collision-list του hashNode του οποίο το index-number συμπίπτει με τον random αριθμό.

Ουσιαστικά η συνάρτηση για την οποία ρώτησες, σε αυτό τον κώδικα είναι η...

>bool colliList_append_auto( ColliList *colliList );

η οποία καλείται με όρισμα την τιμή επιστροφής της...

>HashNode *hashList_lookup_pos( const HashList *hashList, size_t pos );

(δηλαδή έναν δείκτη στον tempPos-ιοστό κόμβο της hashList)

Σου έχω μαρκακρισμένη ως UNUSED μέσα σε σχόλια και μια συνάρτηση...

>bool hashList_hash_pos( HashList *hashList, size_t pos )

η οποία ενοποιεί τις 2 παραπάνω κλήσεις σε μια μονή συνάρτηση (η κλήση της οποίας προφανώς χρειάζεται ελαφρώς διαφορετικό τρόπο αντιμετώπισης στην main() ).

EDIT:

Είχα ξεχάσει να καλέσω τον destructor της hashList πριν τον τερματισμό του προγράμματος.

EDIT2:

Διόρθωσα στις xxxList_append_auto() συναρτήσεις την ανάθεση του πεδίου xxxList->len σε ...

>xxxList->len = 1;

για τις περιπτώσεις που η λίστα είναι κενή (ήταν: (xxxList->len)++; ).

Είναι καλύτερα έτσι, να μην εξαρτάται δλδ από την αρχικοποίηση της xxxList.

Επεξ/σία 30 Οκτωβρίου 2012 από migf1

nik324 · 29 Οκτωβρίου 2012

Σε ευχαριστω...Με βοηθησες παρα πολυ...Εμαθα πραγματα μεσα απο αυτο που εγραψες...Ευχαριστω και παλι!!!

Σύνδεση

Ερωτήσεις για C

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

migf1

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

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

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

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

Δημοφιλή Μηνύματα

imitheos

migf1

defacer

Δημοσιευμένες Εικόνες

nik324

imitheos

nik324

migf1

nik324

migf1

nik324

migf1

nik324

imitheos

nik324

παπι

migf1

nik324

imitheos

migf1

defacer

Σύνδεση