Exercicios sobre a matéria da
P3 de 2006.1
Listas, Árvores e Tabela de
Dispersão
ex_p3.c
int intervalo(Arv* a, int x1, int x2)
{
if (a==NULL) return 0;
if (a->info>x2) { return intervalo(a->esq,x1,x2); }
else if (a->info<x1) { return intervalo(a->dir,x1,x2); }
else { /* pertence ao intervalo */
return 1 + intervalo(a->esq,x1,x2) + intervalo(a->dir,x1,x2);
}
}
hashAluno.c
int hash(char* nome)
{
int i,soma=0;
for (i=0;nome[i]!=‘\0’;i++)
soma=(soma+nome[i])%N;
return soma;
}
int busca(Hash tab, char* nome)
{
int i = hash(nome);
Aluno* p;
for (p=tab[i];p!=NULL;p=p->prox) {
if (strcmp(p->nome,nome)==0) return p->quant;
}
return -1;
}
lista2.c
struct lista {
char nome[81];
float nota;
struct lista* prox
};
typedef struct lista Lista;
Lista* insere (Lista* lst, char* nome, float nota)
{
Lista* novo=(Lista*) malloc(sizeof(Lista));
strcpy(novo->nome,nome);
novo->nota=nota;
novo->prox=lst;
return novo;
}
Lista* retira_ultimo(Lista* lst)
{
if (lst==NULL) return NULL;
else{
Lista* ant=NULL;
Lista* p=lst;
while (p->prox!=NULL) { ant=p; p=p->prox; }
free(p);
if (ant!=NULL) { ant->prox=NULL; return lst; }
else return NULL;
}
}
int cheia(Arv* a)
{
if (a==NULL) return 1;
if (a->esq==NULL&&a->dir==NULL) return 1;
if (a->esq==NULL||a->dir==NULL) return 0;
return cheia(a->esq)&&cheia(a->dir);
}
int maximo(ArvGen* a)
{
if (a->prim==NULL) return a->info;
else {
int max=a->info;
ArvGen* p;
for (p=a->prim;p!=NULL;p=p->prox) {
int mp=maximo(p);
max=(max>mp)?max:mp;
}
return max;
}
}
Lista* constroi(int n, int* v)
{
int i;
Lista* head=NULL;
for (i=0;i<n;i++) {
Lista* novo=(Lista*) malloc(sizeof(Lista));
novo->info=v[i];
novo->prox=head;
head=novo;
}
return head;
}
int soma_info_folhas (Arv* a)
{
if (a==NULL ) return 0;
else if (a->esq==NULL&&a->dir==NULL) return a->info;
else
return soma_info_folhas(a->esq)+soma_info_folhas(a->dir);
}
int num_nos_x(ArvGen* a,int x)
{
if (a->prim==NULL) return (a->info>x)?1:0;
else {
ArvGen* p;
int n=(a->info>x)?1:0;
for (p=a->prim; p!=NULL; p=p->prox) {
n+=num_nos_x(p,x);
}
return n;
}
}
void imprime (Arv* a)
{
if (!arv_vazia(a)){
imprime(a->esq);
printf("%d ", a->info);
imprime(a->dir);
}
}
/* mostra sae */
/* mostra raiz */
/* mostra sad */
/* conta o numero de nos ate o nivel n */
int conta (Arv* a, int n)
{
if (a==NULL || n==-1) return 0;
else
return 1+conta(a->esq,n-1)+conta(a->dir,n-1);
}
void imprime (ArvGen* a)
{
ArvGen* p;
printf("<%d",a->info);
for (p=a->prim; p!=NULL; p=p->prox)
imprime(p);
/* imprime cada sub-árvore filha */
printf(">");
}