Com cabeça ou sem cabeça?

Com cabeça ou sem cabeça?

por José Coelho de Pina -
Número de respostas: 2

Salve,

A seguir estão duas implementações para a função initQueue() de uma fila.
Essas implementações utilizam listas encadeadas com ou sem cabeça?

/* implementaçao 1 */

typedef struct queueNode* Link;
struct queueNode { 
  Item conteudo; 
  Link prox; 
};

static Link inicio;

void 
queueInit() 
{ 
  inicio = (Link) mallocSafe(sizeof *inicio);
  inicio->prox = inicio;
}

/* implementacao 2 */

typedef struct queueNode* Link;
struct queueNode { 
  Item conteudo; 
  Link prox; 
};

struct queue { /* aqui esta especificado o que e' */
  Link inicio; /* uma fila: dois apontadores para struct queueNode */
  Link fim;    
}; 

typedef struct queue *Queue;

Queue 
queueInit(int maxN) 
{ 
  Queue q = mallocSafe(sizeof *q); 
  q->inicio = NULL; 
  q->fim    = NULL; 
  return q;
}
Em resposta à José Coelho de Pina

Re: Com cabeça ou sem cabeça?

por Marcelo Rabello Rossi -

No primeiro caso aloca-se um queueNode, aponta-se inicio para esse queueNode, com o campo prox apontando para ele mesmo: lista encadeada circular com cabeça.

No segundo caso aloca-se um queue, que são apenas dois ponteiros para queueNode, e aponta-se início e fim para NULL. Nenhum queueNode é alocado: lista encadeada sem cabeça.

 

É isso?

Em resposta à José Coelho de Pina

Re: Com cabeça ou sem cabeça?

por João Henrique Luciano -

Eu diria que a primeira é com cabeça e a segunda, sem. Isso porque, após inicializar a segunda fila, q->inicio e q->fim não apontam pra nada, o que infere que não há nenhuma célula inicialmente (nem mesmo uma dummy cell).
Já na inicialização da primeira, o inicio->prox aponta para si mesma e não apresenta nenhum conteúdo, o que dá a enteder que é a dummy cell.

 

EDIT: Como o Marcelo disse, é com cabeça e circular, por isso me confundi um pouco. Mas acho que você está certo, Marcelo, deve ser circular.