Juliana Jenny Kolb
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.