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 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;}

int hash(char* nome){ int i,soma=0; for (i=0;nome[i]!=‘\0’;i++) soma=(soma+nome[i])%N; return soma;}

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); /* mostra sae */ printf("%d ", a->info); /* mostra raiz */ imprime(a->dir); /* 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(">");}