On-line: гостей 0. Всего: 0 [подробнее..]
Программисты всех стран, объединяйтесь!

АвторСообщение



ссылка на сообщение  Отправлено: 05.07.15 01:45. Заголовок: Queue using a linked list


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.

Спасибо: 0 
ПрофильЦитата Ответить
Ответов - 6 [только новые]





ссылка на сообщение  Отправлено: 05.07.15 09:19. Заголовок: You need yo include ..


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

Спасибо: 0 
ПрофильЦитата Ответить



ссылка на сообщение  Отправлено: 08.07.15 09:17. Заголовок: hello. its me hammod..


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

Спасибо: 0 
ПрофильЦитата Ответить



ссылка на сообщение  Отправлено: 08.07.15 10:21. Заголовок: my insert tail funct..


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

Спасибо: 0 
ПрофильЦитата Ответить



ссылка на сообщение  Отправлено: 08.07.15 20:33. Заголовок: Hi, try the followi..


Hi,

try the following function implementation

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



Спасибо: 0 
ПрофильЦитата Ответить



ссылка на сообщение  Отправлено: 09.07.15 06:37. Заголовок: actually i fixed the..


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

Спасибо: 0 
ПрофильЦитата Ответить



ссылка на сообщение  Отправлено: 09.07.15 11:34. Заголовок: It is not clear why ..


It is not clear why the function is declared like
 
void destroy(MY_QUEUE* queue)

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
 
Node_ptr current = head->head;

and only after that you check whether head is equal to NULL
 
if (head == NULL) {
return;
}

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



Спасибо: 0 
ПрофильЦитата Ответить
Ответ:
1 2 3 4 5 6 7 8 9
большой шрифт малый шрифт надстрочный подстрочный заголовок большой заголовок видео с youtube.com картинка из интернета картинка с компьютера ссылка файл с компьютера русская клавиатура транслитератор  цитата  кавычки моноширинный шрифт моноширинный шрифт горизонтальная линия отступ точка LI бегущая строка оффтопик свернутый текст

показывать это сообщение только модераторам
не делать ссылки активными
Имя, пароль:      зарегистрироваться    
Тему читают:
- участник сейчас на форуме
- участник вне форума
Все даты в формате GMT  3 час. Хитов сегодня: 2
Права: смайлы да, картинки да, шрифты да, голосования нет
аватары да, автозамена ссылок вкл, премодерация откл, правка нет