Форум » C/C++ для начинающих (C/C++ for beginners) » Queue using a linked list » Ответить
Queue using a linked list
hammodi: so I am now doing a Queue using a linked list instead of a stack. a queue is basically similar but when you add. you add at the tail. tail insert. here is the header file #include "status.h" struct my_queue_public; typedef struct my_queue_public* MY_QUEUE; struct my_queue_public { void(*destroy)(MY_QUEUE* phMy_queue); Status(*service)(MY_QUEUE hMy_queue); Status(*append)(MY_QUEUE hMy_queue, int item); Bool(*empty)(MY_QUEUE hMy_queue); int* (*front)(MY_QUEUE hMy_queue); }; MY_QUEUE my_queue_init_default(void); //service queue //add to the queue //init and destroy //empty? //look at the front element here is the implementation #include "my_queue.h" #include <stdio.h> #include <stdlib.h> struct node; typedef struct node Node; typedef Node* Node_ptr; struct node { int data; Node_ptr next; }; struct head_node; typedef struct head_node Head_node; typedef Head_node *Head_ptr; struct head_node { struct my_queue_public methods; Node_ptr head; }; void destroy(MY_QUEUE queue); Status append(MY_QUEUE queue, int item); Status service(MY_QUEUE queue); int* front(MY_QUEUE queue); Bool empty(MY_QUEUE stack); void init_functions(MY_QUEUE queue) { queue->destroy = destroy; queue->empty = empty; queue->service = service ; queue->append = append; queue->front = front; } MY_QUEUE my_queue_init_default(void) { Head_ptr head; head = malloc(sizeof(Head_node)); if (head != NULL) { head->head = NULL; init_functions((MY_QUEUE)head); } return (MY_QUEUE)head; } void destroy(MY_QUEUE queue) { /*Head_ptr head = (Head_ptr)queue; Node_ptr tmp; if (head == NULL) { return; } for (Node_ptr current = head->head; current != NULL;) { tmp = current; current = current->next; free(tmp); } head->head = NULL;*/ } Status append(MY_QUEUE queue, char item) { Node_ptr temp; //create a new node temp = (Node_ptr)malloc(sizeof(Node)); //allocates the space if (temp == NULL) { printf("Failed to allocate node\n"); return FAILURE; } temp->data = item; temp->next = NULL; ((Node_ptr)queue)->next = temp; return SUCCESS; } Status service(MY_QUEUE queue) { Head_ptr head = (Head_ptr)queue; Node_ptr tmp; if (head == NULL || head->head == NULL) { return FAILURE; } tmp = head->head; head->head = head->head->next; free(tmp); return SUCCESS; } int* front(MY_QUEUE queue) { Head_ptr head = (Head_ptr)queue; if (head == NULL || head->head == NULL) { return NULL; } return &(head->head->data); } Bool empty(MY_QUEUE stack) { Head_ptr head = (Head_ptr)stack; return head == NULL || head->head == NULL; } this is not working. the problem is https://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=1975 i have the function for the problem working. because i have a vector implementation that works fine. but am required to do it with a linked list. btw the Destroy function crashes. and if i comment it out. i get wrong answers.
Ответов - 6
Сыроежка: You need to include also data member tail and write method add. Also along with the method front there should be a method that removes a node from the head like pop_front
sgtham: hello. its me hammodi. just different account i forgot old password. this destroy function isn't working for the queue. void destroy(MY_QUEUE queue) { Head_ptr head = (Head_ptr)queue; Node_ptr tmp; Node_ptr current; if (head == NULL) { return; } for ( current = head->head; current != NULL;) { tmp = current; current = current->next; free(tmp); } head->head = NULL; } any ideas
sgtham: my insert tail function isn't working either. for some reason the first item i enter is not in the list. Status append(MY_QUEUE queue, int item) { Node_ptr temp; Head_ptr head = (Head_ptr) queue; //create a new node temp = (Node_ptr)malloc(sizeof(Node)); //allocates the space if (temp == NULL) { printf("Failed to allocate node\n"); return FAILURE; } temp->data = item; temp->next = NULL; while (1){ if (head->head == NULL){ head->head = temp; break; } else if ((head->head)->next == NULL) { (head->head)->next = temp; break; } head->head = (head->head)->next; printf("a"); } return SUCCESS; }
Сыроежка: Hi, try the following function implementation [pre2] Status append( MY_QUEUE queue, int item ) { Head_ptr head = (Head_ptr) queue; //create a new node Node_ptr temp; temp = ( Node_ptr )malloc( sizeof( Node ) ); //allocates the space if ( temp == NULL ) { printf( "Failed to allocate node\n" ); return FAILURE; } temp->data = item; temp->next = NULL; Node_ptr *current = &head->head; while ( *current != NULL ) current = &( *current )->next; *current = temp; return SUCCESS; } [/pre2]
sgtham: actually i fixed the append function. but the destroy function is not working. its crashing. void destroy(MY_QUEUE* queue) { Head_ptr head = (Head_ptr)queue; Node_ptr tmp; Node_ptr current = head->head; if (head == NULL) { return; } while (current !=NULL){ tmp = current; current = current->next; free(tmp); } head->head = NULL; }
Сыроежка: It is not clear why the function is declared like [pre2] void destroy(MY_QUEUE* queue) [/pre2] That is why does the parameter have type MY_QUEUE* instead of MY_QUEUE? Also if to replace MY_QUEUE* with MY_QUEUE in the parameter declaration nevertheless there is a wrong order of the stetement execution in the function. At first you use expression head->head in statement [pre2] Node_ptr current = head->head; [/pre2] and only after that you check whether head is equal to NULL [pre2] if (head == NULL) { return; } [/pre2] So if head is indeed equal to NULL then the first statement can result in the function crash. You could use the function from the class stack that I already showed. For example [pre2] void destroy( MY_QUEUE queue ) { if ( queue == NULL ) return; Head_ptr head = ( Head_ptr )queue; for ( Node_ptr current = head->head; current != NULL; ) { Node_ptr tmp = current; current = current->next; free( tmp ); } head->head = NULL; } [/pre2]
полная версия страницы