Instituto de Computação - UNICAMP

MC202 - Gabarito do Exame

Islene Calciolari Garcia

Questão 1

Considere que os elementos de uma lista ligada estão em ordem crescente. Escreva uma função que insere um elemento com valor $v$ nesta lista, mantendo a ordenação. Caso um elemento com o mesmo valor já esteja presente na lista, a inserção não deve ser feita e uma mensagem de erro deve ser emitida. 
typedef struct no {
   int v;
   struct no* prox;
} No;

Versão recursiva 

void insere_ordenado (No** l, int v) {
   if (*l == NULL || (*l)->v > v) {
     No* n = (No*) malloc (sizeof(No));
     n->v = v;
     n->prox == *l;
     *l = n;
   }
   else
     if ((*l)->v == v) 
        printf("Elemento %d já existente.\n", v);
     else
        insere_ordenado (&(*l)->prox, v);
}

Versão não recursiva 1 

void insere_ordenado (No** l, int v) {
   if (*l == NULL || (*l)->v > v) {
     No* n = (No*) malloc (sizeof(No));
     n->v = v;
     n->prox = *l;
     *l = n;
     return;
   }
   No* p = *l;
   while (1) {
      if (p->prox == NULL || p->prox->v > v) {  
        No *n (No*) malloc (sizeof(No));
        n->v = v;
        n->prox = p->prox;
	p->prox = n;
        return;
      }
      if (p->prox->v == v) {
          printf("Elemento %d já existente.\n", v);
	  return;
      }
      p = p->prox;
   }
}

Versão não recursiva 2 

void insere_ordenado (No** l, int v) {
  while (1) {
    if (*l == NULL || (*l)->v > v) {
       No* n = (No*) malloc (sizeof(No));
       n->v = v;
       n->prox = *l;
       *l = n;
       return;
     }
     if ((*l)->v == v) {
        printf("Elemento %d já existente.\n", v);
	return;
      }
      l = &(*l)->prox;
  }
}
Por que é necessário utilizar um parâmetro do tipo No**? Se a lista tivesse um nó cabeça, um parâmetro do tipo No* seria adequado?

Precisamos utilizar um parâmetro do tipo No** porque o apontador que marca o nó inicial da lista pode ser alterado. No caso de listas com nó cabeça, as inserções não alteram o apontador para o nó cabeça, e, portanto, o parâmetro do tipo No* seria suficiente.

Questão 2

Escreva uma função recursiva que percorre uma lista ligada de inteiros e remove (liberando adequadamente a memória) todos os nós que contêm elementos nulos (vide figura). A função retorna um apontador para a lista modificada. Utilize as declarações abaixo. 

typedef struct no {
  int v;
  struct no *prox;
} No;

Resposta 

No* remove_zeros(No* l) {
  if (l == NULL)
   return NULL;
  if (l->v == 0) {
   No* r = l;
   l = l->prox;
   free(r);
   return remove_zeros(l);
  }
 else{
   l->prox = remove_zeros(l->prox);
  return l;
 }  
}

Questão 3

Escreva uma função que percorre uma árvore binária de busca e retorna uma lista ligada ordenada em ordem decrescente contendo todos os elementos da árvore. 
typedef struct no_arv {              typedef struct no_lista {
  int v;                               int v;
  struct no_arv *esq, *dir;            struct no_lista *prox; 
} No_arv;                          } No_lista;

No_lista* monta_lista(No_arv *arv);
Para que você obtenha nota integral nesta questão, sua solução, além de correta

Versão ineficiente 

/* Percorre a lista referente à sub-árvore esquerda 
   para fazer a concatenação entre as listas. */
No_lista* monta_lista(No_arv* arv) {
    if (arv == NULL)
      return NULL;
    No_lista* lesq = monta_lista(arv->dir);
    No_lista* l =  malloc (sizeof(No_lista));
    l->v = arv->v;
    l->prox = monta_lista(arv->esq);
    if (lesq == NULL)
      return l;
    No_lista* aux = lesq;
    while (aux->prox != NULL)
      aux = aux->prox;
    aux->prox = l;
    return lesq;
}

Versão eficiente 1 


/* Cria listas, indicando um apontador para o início e outro
   para o final da lista. Desta forma, é possível fazer a concatenação
   de forma eficiente.
*/

void monta_aux(No_arv *arv, No_lista** prim, No_lista** ult) {
      
   No_lista *l =  malloc (sizeof(No_lista));
   l->v = arv->v;
      
   if (arv->dir) {
      No_lista *ult_lesq;
      monta_aux(arv->dir, prim, &ult_lesq);
      ult_lesq->prox = l;
   }
   else
     *prim = l;
     
   if (arv->esq) 
     monta_aux(arv->esq, &l->prox, ult);
   else
     *ult = l;          
}

No_lista* monta_lista(No_arv* arv) {
    if (arv == NULL)
       return NULL;
    No_lista *prim, *ult;
    monta_aux(arv, &prim, &ult);
    ult->prox = NULL;
    return prim;
}

Versão eficiente 2 

/* Esta versão faz um percurso inordem invertido na árvore 
   e vai montando a lista do último nó até o primeiro. 
 */
No_lista* aux_monta_lista(No_arv* arv, No_lista* prox) {
  No_lista *l =  malloc (sizeof(No_lista));
  l->v = arv->v;
  if (arv->esq != NULL)
    l->prox = aux_monta_lista(arv->esq, prox);
  else
    l->prox = prox;
  if (arv->dir != NULL)
    return aux_monta_lista(arv->dir, l);
  else
    return l;
}

No_lista* monta_lista(No_arv* arv) {
    if (arv == NULL)
       return NULL;
    return aux_monta_lista(arv, NULL);
}

Questão 4

Considere a seguinte declaração para os nós de uma árvore 2-3, com as restrições apresentadas em aula. Escreva uma função que libera todos os nós desta árvore. 
typedef struct no23{
  int nch;                       /* Número de chaves (1 ou 2) no nó         */ 
  struct no23 *esq, *cen, *dir;  /* Apontadores esquerdo, central e direito */
  int chesq, chdir;              /* Chaves esquerda e direita               */ 
} No23;

void libera(No23* no) {
   if (no != NULL) {
     if (no->esq != NULL) {  /* Não é folha */
       libera(no->esq);
       libera(no->cen);
       if (no->nch == 2)
         libera(no->dir);
     }
     free(no);
   }
}