Row with circular chained list with head

Asked

Viewed 848 times

0

Implement a queue in a circular chained list with head (do functions that implement the operations of Insertion and Removal). The first Row element is in the second cell and the last element is in the cell anterior to the head.

Celula *inserir(Celula *fim, Pessoa *p){
    Celula *nova = (Celula*) malloc(sizeof(Celula));
    nova->ptrpessoa = p;
    nova->prox = fim->prox;
    fim->prox = nova;
    fim = nova;
    return fim;
}

void remover(Celula *ini){
    Celula *li = ini->prox;
    ini->prox = li->prox;
    printf("OPA");
    free(li);
}

queue statement 

Fila ini;
Fila fim;

to have head I what I do ? I tried so.

Celula cini, cfim;
ini = &cini;  /aqui o  ini da fila recebe o endereço d cini?
fim = ini; /aqui o  final  da fila recebe o endereço d cini?

/and here it gets circular ? ini->Prox = ini;

c
  • 1

    Its functions inserir and remover seem correct (it depends on how you are using them, of course - the remover for example remove the next one after ini, which in the case of a row is correct). I didn’t quite understand the doubt: to have a head, all you need is that the initial/special knot does not store elements. How is your data structure? (i.e. what is the relationship between Fila and Celula?)

  • I understood what you meant, but I wanted to know is that the beginning of the queue has to be dps the head and the end before I wanted to know if this implementation that I made is correct in this aspect. cabeca->ini->...->fim->cabeca relaçoes struct pessoa{ char nome[MAX_NOME]; int num; }; typedef struct pessoa Pessoa; struct celula{ Pessoa *ptrpessoa; struct celula *Prox; }; typedef struct celula Celula; typedef struct celula *List; these are the relations

  • So the structure is the same, my question was whether Celula and Fila were two different things or not. Only ini is the head or the first element? Its function remover is correct if ini is the head, otherwise it is incorrect (it will remove the 2nd element). By the way, if the list were double chained it was enough to store the head, but as it is not, it is necessary to store the head and the last (as you are already doing). Anyway, at first glance what you did is ok.

1 answer

2


First of all, for the list to have a head and to be circular it is necessary to create this head and make it point to itself. Dynamically, it would be this:

Celula *cabeca = (Celula*) malloc(sizeof(Celula));
cabeca->prox = cabeca;

Second, if you want a queue, you also need to keep a reference for the last element (for efficiency) - which at first is equal to the head:

Celula *ultimo = cabeca;

From there your current code should work correctly - inserir(ultimo, p) creates a node after the last by updating it, and remover(cabeca) removes the first element that is not the head (hint: it is interesting to check also if the queue is empty - what happens when cabeca == ultimo).

His attempt at statement, on the other hand, has some minor problems:

Celula cini, cfim; // Criou duas células, mas você só precisa de uma
ini = &cini;       // ok
fim = ini;         // ok, mas faltou ini->prox = ini pra ser circular

  • I wasn’t getting it Cellula new = (Cellule) malloc(sizeof(Cell); new->ptrpessoa = p; new->Prox = end->Prox; end->Prox = new; end = new; // was not understanding how the head was pointing to the new end only I now understood I think Return end; is that in my main end = ini; and ini->Prox = ini; then it means ini->Prox= points to new; ? right?

  • The head does not point to the new end, the new end is that it points to the head (in general, it is clear that if the row has only 1 element then one points to the other and vice versa). Your main seems to be right.

Browser other questions tagged c

You are not signed in. Login or sign up in order to post.