Απορία - ουρές C

[kopsti]

Γειά σας, θέλω να φτιάξω ένα πρόγραμμα που (για αρχή) θα δημιουργεί 2 ουρές και θα τις αρχικοποιεί. Έχω γράψει αυτό αλλά κάτι δεν πάει καλά , αν μπορείτε εξηγήστε μου.

 

typedef struct queueNode {

int info;

struct queueNode *next;

} queueNode1;

 

 

typedef struct queue1 {

queueNode1 front, rear;

} landing ;

 

typedef struct queue2 {

queueNode1 front, rear;

} takeoff ;

 

void queue_init( queueNode *queue )

{

queue->front = NULL;

queue->rear = NULL;

return;

}

[thanos713]

>/* This Queue implementation of singly linked list in C implements 3
* operations: add, remove and print elements in the list.  Well, actually,
* it implements 4 operations, lats one is list_free() but free() should not
* be considered the operation but  a mandatory practice like brushing
* teeth every morning, otherwise you will end up loosing some part of
* your body(the software) Its is the modified version of my singly linked
* list suggested by Ben from comp.lang.c . I was using one struct to do
* all the operations but Ben added a 2nd struct to make things easier and
* efficient.
*
* I was always using the strategy of searching through the list to find the
*  end and then addd the value there. That way list_add() was O(n). Now I
* am keeping track of tail and always use  tail to add to the linked list, so
* the addition is always O(1), only at the cost of one assignment.
*
*
* VERISON 0.5
*
*/

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

struct my_struct
{
 int num;
 struct my_struct* next;
};

struct my_list
{
 struct my_struct* head;
 struct my_struct* tail;
};

struct my_list* list_add_element( struct my_list*, const int);
struct my_list* list_remove_element( struct my_list*);

struct my_list* list_new(void);
struct my_list* list_free( struct my_list* );

void list_print( const struct my_list* );
void list_print_element(const struct my_struct* );

int main(void)
{
 struct my_list*  mt = NULL;

 mt = list_new();
 list_add_element(mt, 1);
 list_add_element(mt, 2);
 list_add_element(mt, 3);
 list_add_element(mt, 4); 

 list_print(mt);

 list_remove_element(mt);
 list_print(mt);

 list_free(mt);   /* always remember to free() the malloc()ed memory */
 free(mt);        /* free() if list is kept separate from free()ing the structure, I think its a good design */
 mt = NULL;      /* after free() always set that pointer to NULL, C will run havon on you if you try to use a dangling pointer */

 list_print(mt);

 return 0;
}

/* Will always return the pointer to my_list */
struct my_list* list_add_element(struct my_list* s, const int i)
{
 struct my_struct* p = malloc( 1 * sizeof(*p) );

 if( NULL == p )
   {
     fprintf(stderr, "IN %s, %s: malloc() failed\n", __FILE__, "list_add");
     return s;
   }

 p->num = i;
 p->next = NULL;

 if( NULL == s )
   {
     printf("Queue not initialized\n");
     free(p);
     return s;
   }
 else if( NULL == s->head && NULL == s->tail )
   {
     /* printf("Empty list, adding p->num: %d\n\n", p->num);  */
     s->head = s->tail = p;
     return s;
   }
 else if( NULL == s->head || NULL == s->tail )
   {
     fprintf(stderr, "There is something seriously wrong with your assignment of head/tail to the list\n");
     free(p);
     return NULL;
   }
 else
   {
     /* printf("List not empty, adding element to tail\n"); */
     s->tail->next = p;
     s->tail = p;
   }

 return s;
}

/* This is a queue and it is FIFO, so we will always remove the first element */
struct my_list* list_remove_element( struct my_list* s )
{
 struct my_struct* h = NULL;
 struct my_struct* p = NULL;

 if( NULL == s )
   {
     printf("List is empty\n");
     return s;
   }
 else if( NULL == s->head && NULL == s->tail )
   {
     printf("Well, List is empty\n");
     return s;
   }
 else if( NULL == s->head || NULL == s->tail )
   {
     printf("There is something seriously wrong with your list\n");
     printf("One of the head/tail is empty while other is not \n");
     return s;
   }

 h = s->head;
 p = h->next;
 free(h);
 s->head = p;
 if( NULL == s->head )  s->tail = s->head;   /* The element tail was pointing to is free(), so we need an update */

 return s;
}

/* ---------------------- small helper fucntions ---------------------------------- */
struct my_list* list_free( struct my_list* s )
{
 while( s->head )
   {
     list_remove_element(s);
   }

 return s;
}

struct my_list* list_new(void)
{
 struct my_list* p = malloc( 1 * sizeof(*p));

 if( NULL == p )
   {
     fprintf(stderr, "LINE: %d, malloc() failed\n", __LINE__);
   }

 p->head = p->tail = NULL;

 return p;
}

void list_print( const struct my_list* ps )
{
 struct my_struct* p = NULL;

 if( ps )
   {
     for( p = ps->head; p; p = p->next )
{
  list_print_element(p);
}
   }

 printf("------------------\n");
}

void list_print_element(const struct my_struct* p )
{
 if( p )
   {
     printf("Num = %d\n", p->num);
   }
 else
   {
     printf("Can not print NULL struct \n");
   }
}

[Timonkaipumpa]

Γειά σας, θέλω να φτιάξω ένα πρόγραμμα που (για αρχή) θα δημιουργεί 2 ουρές και θα τις αρχικοποιεί. Έχω γράψει αυτό αλλά κάτι δεν πάει καλά , αν μπορείτε εξηγήστε μου.

 

typedef struct queueNode {

int info;

struct queueNode *next;

} queueNode1;

 

 

typedef struct queue1 {

queueNode1 front, rear;

} landing ;

 

typedef struct queue2 {

queueNode1 front, rear;

} takeoff ;

 

void queue_init( queueNode *queue )

{

queue->front = NULL;

queue->rear = NULL;

return;

}

 

 

 

Δοκίμασε αυτό:

 

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


typedef struct _queueNode{
   int info;
   struct _queueNode* next;
}QueueNode, *pQueueNode;

typedef struct _queue{
   pQueueNode head;
//    pQueueNode tail;
}Queue, *pQueue;

int initialiseQueue(pQueue*);
int isEmpty(pQueue);
int makeQueueNode(pQueueNode*, int);
int enqueue(pQueue*, int);
int dequeue(pQueue*, int*);

int initialiseQueue(pQueue* theQueue){
   int result = 0;

   *theQueue = (pQueue) malloc( sizeof (Queue));

   if(*theQueue == NULL){
       result = 0;
   } else {
       (*theQueue)->head = NULL;
//        (*theQueue)->tail = NULL;
       result = 1;
   }

   return result;
}

int isEmpty(pQueue theQueue){
   int result = 0;

/*
   if(theQueue->head == theQueue->tail){
	if (theQueue->head == NULL) {
		result = 1;
	}*/
if(theQueue->head == NULL){
	result = 1;
   } else {
       result = 0;
   }

   return result;
}

int makeQueueNode(pQueueNode* theNode, int datum){
   int result = 0;

   *theNode = (pQueueNode) malloc( sizeof (QueueNode));

   if(*theNode == NULL){
       result = 0;
   } else {
       (*theNode)->next = NULL;
       (*theNode)->info = datum;
       result = 1;
   }

   return result;
}

int enqueue(pQueue* theQueue, int datum){
   int result = 0;

   pQueueNode tmp, tmp2;

   if(isEmpty(*theQueue)){
       if(makeQueueNode(&tmp, datum)){
           (*theQueue)->head = tmp;
//			(*theQueue)->tail = tmp;
           result = 1;
       } else {
           result = 0;
       }
   } else {
       if(makeQueueNode(&tmp, datum)){
/*			(*theQueue)->tail->next = tmp;
		(*theQueue)->tail = tmp;*/
		tmp2 = (*theQueue)->head;
		while(tmp2->next != NULL){
			tmp2 = tmp2->next;
		}
		tmp2->next = tmp;
           result = 1;
       } else {
           result = 0;
       }
   }

   tmp = NULL;
   return result;
}

int dequeue(pQueue* theQueue, int* datum){
   int result = 0;

   if(isEmpty(*theQueue)){
       result = 0;
   } else {
       *datum = (*theQueue)->head->info;
	pQueueNode tmp = (*theQueue)->head;
       (*theQueue)->head = (*theQueue)->head->next;
	/*
	if((*theQueue)->head == NULL){
		(*theQueue)->tail = NULL;
	}*/
	tmp->next = NULL;
       free(tmp);
       result = 1;
   }

   return result;
}

/*
* 
*/
int main(int argc, char** argv) {

   pQueue theQueue;
   int result, theCounter, datum;
   result = theCounter = 0;

   if (!initialiseQueue(&theQueue)){
       result = -1; //Problem with initialise
   } else {
       result = 1;
   }

   if(result > 0){
       for(theCounter = 0; theCounter < 100000 & result > 0; theCounter++){
           result = enqueue(&theQueue, theCounter);
       }

       if(!result){
           result = -2; //Problem with enqueue
       }
   }

   if(result > 0){
       result = dequeue(&theQueue, &datum);
       while(result > 0){
           printf("Dequeued %d\n", datum);
           result = dequeue(&theQueue, &datum);
       }

       if(!result){
           if(!isEmpty(theQueue)){
               result = -3; //Problem with dequeue
           }
       }
   }

   if(result < 0){
       return result;
   } else {
	printf("SUCCESS");
       return (EXIT_SUCCESS);
   }
}

 

Αν και το while μέσα στο enqueue βάζει (ΠΟΛΥ) παραπάνω χρόνο εάν έχεις μακριά ούρα...

 

Μπορείς να το αποφύγεις ενεργοποιώντας το tail στο struct Queue και κάνοντας και τις απαραίτητες διορθώσεις.