Listas Lineares Listas Generalizadas

Juliana Jenny Kolb

teste seu conhecimento

Home > Simulados on-line  > Questões de Concursos > Tecnologia da Informação (TI) Algoritmos e Estruturas de Dados Estruturas de Dados

Listas Lineares Listas Generalizadas

São listas contendo dois tipos de elementos: elementos ditos “normais” (e.g., que armazenam chaves) e elementos que representam entradas para sublistas. Para decidir se um nó armazena uma chave ou um ponteiro de sublista, usamos um campo tag cuja manutenção é responsabilidade do programador.

Dependendo do valor de tag, armazenamos em um campo de tipo variável (um union em C) o dado correspondente. Para evitar a criação de códigos especiais para o tag, usamos a seguir uma enumeração dos dois valores possíveis (elemLista, inicioLista) para variáveis do tipo IDENT. Note no entanto que o uso de um tipo enumerado não é obrigatório e de fato não tem relação com o uso de union.

typedef enum{elemLista, inicioLista}

IDENT;

typedef struct estrutura {

IDENT tag;
union {

TIPOCHAVE chave;
struct estrutura *sublista;

};

estrutura *prox;

} NO;

// Inicialização
void inicializarLista(NO* *l)
{

*l = NULL;

}

// Quantidade de chaves na lista
int contarChaves(NO* p)
{

int chaves = 0;
while (p)

{

if( p->tag == elemLista)
chaves++;
else
chaves = chaves + contarChaves(p->sublista);
p = p->prox;

}

return(chaves);

}

// Quantidade de nos na lista
int contarNos(NO* p)
{

int nos = 0;
while (p)
{

nos++;
if( p->tag == inicioLista)
nos = nos + ContarNos(p->sublista);
p = p->prox;

}
return(nos);

}

// Profundidade maxima da lista
int profundidade(NO* p)
{

int maximo = 0;
int resp;
if(!p) return(maximo);
while(p)
{

if( p->tag == elemLista) resp = 0;
else resp = profundidade(p->sublista);
if(resp > maximo) maximo = resp;
p = p->prox;

}
return(maximo + 1);

}

// copia uma lista inteira
NO* copiarListaGen(NO* p)
{

NO* novo;
NO* abaixo;
NO* dir;
IDENT tipo;
novo = NULL;
if (p)
{

tipo = p->tag;
if( tipo == inicioLista)
abaixo = copiarListaGen(p->sublista);
dir = copiarListaGen(p->prox);
novo = (NO *) malloc(sizeof(NO));
novo->tag = tipo;
novo->prox = dir;
if( tipo == elemLista)
novo->chave = p->chave;
else
novo->sublista = abaixo;

}
return(novo);

}

// verifica se duas listas são identicas
bool listasIguais(NO* a, NO* b)
{

bool resp = false;
if((!a) && (!b)) return(true);
if((a) && (b))
{

if( a->tag == b->tag)
{

if( a->tag == elemLista)
resp = (a->chave == b->chave);
else
resp = listasIguais(a->sublista, b->sublista);
if(resp)
resp = listasIguais(a->prox, b->prox);

}

}
return(resp);

}

Referência Bibliográfica

Honda, Willian Yukio; Paraboni, Ivandré. ACH2023 – ALGORITMOS E
ESTRUTURAS DE DADOS I. Trabalho Acadêmico, 2011.

Deixe uma resposta