Resolução da Primeira Lista

Exercício 1)b) 


#include <stdio.h>

#define _MAX_ 100
typedef int Indice;
typedef int TipoDoElemento;

typedef struct _Pilha{
     Indice topo; /* topo = -1, quando a pilha está vazia*/
     TipoDoElemento elementos[_MAX_];
} Pilha;

void InicializaPilha (Pilha *S){
  S->topo = -1;
}
/* Procedimento para inserir um elemento x na pilha S */

void OVERFLOW(){
  printf("Capacidade da pilha ultrapassada !!");
  exit(1);
}

void Underflow(){
  printf("Na sequencia desejada existem elementos repetidos !!");
  exit(1);
}

void Empilha( Pilha *S, TipoDoElemento x){
  S->topo++;
  if( S->topo == _MAX_ )
     OVERFLOW(); /* a pilha já está cheia*/
  else  
     S->elementos[S->topo] = x;
}

/* Procedimento para remover um elemento na pilha S */

void Desempilha( Pilha *S, TipoDoElemento *x ){
  if( S->topo == -1 )
     Underflow(); /* a pilha está vazia*/
  else  
    *x = S->elementos[S->topo--];
}

int main(){
  int proximo=1; /* proximo elemento a empilhar/ retirar */
  int n=1;
  int dapilha, /* elemento tirado da pilha */
	el; /* elementos lidos pelo teclado */
  Pilha p;
  InicializaPilha(&p);
  printf("Qual a quantidade de elementos ");
  scanf("%d",&n);
  printf("Digite %d numeros de 1 a %d\n",n,n);
  while ((proximo<=n)||(p.topo!=-1)){
	printf("Entre com um elemento: ");
	scanf("%d",&el);
	if (el==proximo) /* pega o elemento e ja o retira */
	  proximo++;
	else 
	  if (el<proximo){ /* o elemento tem que estar na pilha */
		Desempilha(&p,&dapilha);
		if (dapilha!=el) { /* nao deu certo */
		  printf("Sequencia impossivel\n");
		  exit(0);
		}
	  }
	  else{ /* el > n, empilho até n */
		while (proximo<el){
		  Empilha(&p,proximo);
		  proximo++;
		}
		proximo++; /* o elemento el ja sai direto */
	  }
  }
  printf("Sequencia Ok\n");
}


3) Exercícios para eliminar recursão:
a)
int Comb(int n,int m){
   if ((n==1) || (m==0) || (m==m))
     return 1;
   else
     return Comb(n-1,m) + Comb(n-1,m-1);
}

/* Pseudo código:
   Supoe-se que existe uma pilha com os seguintes prototipos definidos*/

void InicializaPilha();
void Empilha(int a, int b);
void Desempilha(int *a, int *b); 
int PilhaVazia(); /* volta 1 se a pilha estiver vazia, 0 caso contrario*/
int CombR(int n,int m){
   Soma=0;
   InicializaPilha();
   Empilha(n,m);
   while (!PilhaVazia()){
     Desempilha(&n,&m);
     if ((n==1) || (m==0) || (m==m))
       Soma = Soma + 1;
     else{
       Empilha(n-1,m);
       Empilha(n-1,m-1);
     }
   }
   return Soma;
}


b)
int Fib(int n){
   if ((n==1) || (n==2) )
     return 1;
   else
     return Fib(n-1)+Fib(n-2);
}

/* Pseudo código:
   Supoe-se que existe uma pilha com os seguintes prototipos definidos*/

void InicializaPilha();
void Empilha(int a);
void Desempilha(int *a); 
int PilhaVazia(); /* volta 1 se a pilha estiver vazia, 0 caso contrario*/
int FibR(int n){
   Soma=0;
   InicializaPilha();
   Empilha(n);
   while (!PilhaVazia()){
     Desempilha(&n);
     if ((n==1) || (n==2))
       Soma = Soma + 1;
     else{
       Empilha(n-1);
       Empilha(n-2);
     }
   }
   return Soma;
}

c)
void Bool(int i,int b1,int b2,int b3){
   if (i==1) {
     Bool(2,0,0,0); Bool(2,1,0,0); Bool(2,2,0,0);
   }
   else if (i==2) {
     Bool(3,b1,0,0); Bool(3,b1,1,0); Bool(3,b1,2,0);
   }
   else if (i==3) {
     Bool(4,b1,b2,0); Bool(4,b1,b2,1); Bool(4,b1,b2,2);
   }
   else
     printf("%d%d%d\n",b1,b2,b3);
}

/* Pseudo código:
   Supoe-se que existe uma pilha com os seguintes prototipos definidos*/

void InicializaPilha();
void Empilha(int a, int b, int c, int d);
void Desempilha(int *a, int *b, int *c, int *d); 
int PilhaVazia(); /* volta 1 se a pilha estiver vazia, 0 caso contrario*/
void BoolR(int i,int b1,int b2,int b3){
   InicializaPilha();
   Empilha(i,b1,b2,b3);
   while (!PilhaVazia()){
     Desempilha(&i,&b1,&b2,&b3);
     if (i==1){
	Empilha(2,0,0,0);
	Empilha(2,1,0,0);
	Empilha(2,2,0,0);
     }
     else if (i==2) {
        Empilha(3,b1,0,0);
	Empilha(3,b1,1,0);
	Empilha(3,b1,2,0);
     } 
     else if (i==3){
        Empilha(4,b1,b2,0);
	Empilha(4,b1,b2,1);
	Empilha(4,b1,b2,2);
     }
     else
        printf("%d%d%d\n",b1,b2,b3);
   }
}

5) Faça as seguintes funções para a seguinte estrutura de lista ligada:
typedef struct no1{
           int info;
           struct no1 *prox;
        } node, *apontnode;


#include <stdio.h>
#include <malloc.h>

typedef struct no1{
           int info;
           struct no1 *prox;
        } No, *apontNo;

/* Leitura de uma sequencia terminada por zero */
void Leitura(apontNo *p){
  int num;
  apontNo paux;
  *p=NULL;
  Printf("Digite uma sequencia de numeros terminada por zero \n");
  scanf("%d",&num);
  while (num!=0){
	paux = (apontNo) malloc (sizeof(No));
	paux->info=num;
	paux->prox=*p;
	*p=paux;
	scanf("%d",&num);
  }
}
/* Faça uma função que insere um elemento no início da lista */
void Insere(apontNo *p, int x){
  int num;
  apontNo paux;
  paux = (apontNo) malloc (sizeof(No));
  paux->info= x;
  paux->prox= *p;
  *p=paux;
}

/* Faça uma função que dados $p$ remove o elemento na posição $p$
   (a partir do primeiro elemento) da lista; */
void Remove(apontNo *p, int pos, int *x){
  int i=1;
  apontNo ant,atual;
  atual=*p;
  if (pos==1){
	if (atual==NULL){
	   printf("Elemento inexistente\n");
	   *x=0;
	}
     else{
	*p=(*p)->prox;
	*x=atual->info;
	free(atual);
     }
  }
  else{
	while ((i<pos)&&(atual!=NULL)){
	  i++;
	  if (i==pos)
		ant=atual; /* elemento anterior ao prox */
	  atual=atual->prox;
	}
	if (atual==NULL){
	  printf("Elemento inexistente\n");
	  *x=0;
	}
	else {
	  *x = atual->info;
	  ant->prox=atual->prox;
	  free(atual);
	}
  }
}
/* Faça uma função onde dadas duas listas de números ordenadas
   retorna uma única lista também ordenada */
apontNo ordena(apontNo p1, apontNo p2){
  apontNo aux=NULL;
  while ((p1!=NULL)&&(p2!=NULL)){
	if (p1->info<p2->info){
	  insere(&aux,p1->info);
	  p1=p1->prox;
	}
	else {
	  insere(&aux,p2->info);
	  p2=p2->prox;
	}
  }
  while(p1!=NULL){
	insere(&aux,p1->info);
	p1=p1->prox;
  }
  while(p2!=NULL){
	insere(&aux,p2->info);
	p2=p2->prox;
  }
  return aux;
}
/* Faça uma função que dada uma lista remove o seu nó com o maior valor */
void removeMaior(apontNo *p,int *x){
  apontNo paux, pmaior;
  int maior, onde, i;
  if (*p!=NULL){
	pmaior=*p;
	maior=(*p)->info;
	paux=pmaior;
	onde = 1;
	i = 1;
	while(paux!=NULL){
	  if (paux->info>maior){
		maior = paux->info;
		onde = i;
	  }
	  i++;
	  paux=paux->prox;
	}
	Remove(p,onde,x);
  }
}
	
		
/* Faça uma função que ordena uma lista */
void Ordena(apontNo *p){
   apontNo paux=NULL;
   int maiorAtual;
   while (*p!=NULL){
     removeMaior(p, &maiorAtual);
     Insere(&paux, maiorAtual);
   }         
   *p = paux;
}


/* Faça uma função que remove o primeiro elemento da
   lista*/
void RemovePrimeiro(apontNo *p, int *x){
     Remove(p, 1, x);
}

/* Faça uma função onde dada uma lista retorna duas listas, uma com
   os números pares e outra com os ímpares */
void ParImpar(apontNo p, apontNo *pimp, apontNo *ppar){
     *pimp=*ppar=NULL;
     while (p!=NULL){
	if (p->info%2==0) /* par */
	  Insere(ppar, p->info);
	else
	  Insere(pimp, p->info);
	p=p->prox;
     }
}   

/* Faça uma função que dada uma lista, inverte a mesma */
void Inverte(apontNo *p){
  apontNo aux1, aux2, aux3;
  if ((*p!=NULL)&&((*p)->prox!=NULL)){ /* se a lista tiver ao menos 2 elementos */
    aux1 = *p;
    aux2 = aux1->prox;
    aux3 = aux2->prox;
    while (aux3!=NULL){
       aux2->prox = aux1;
       aux1 = aux2;
       aux2 = aux3;
       aux3 = aux3->prox;
    }
    aux2->prox = aux1;
    *p = aux2;
  }
}	

/* Faça uma função que dada uma lista ordenada, e um novo elemento x,
   insere x na posição certa da lista */
void InsereOrdenado(apontNo *p, int x){
  int num;
  apontNo paux, ant, prox;
  paux = (apontNo) malloc (sizeof(No));
  paux->info= x;
  if (*p==NULL){ /* lista vazia */
    paux->prox= *p;
    *p=paux;
  }
  else {
    ant= *p;
    prox= ant->prox;
    while (prox!=NULL){
      if (prox->info<x){ /* ainda nao encontrou a posição */
        ant = prox;
	prox = prox->prox;
      }
      else { /* encontrou a posição */
        break; /* forca a saida do laço */
      }
    }
    ant->prox = paux;
    paux->prox = prox;
  }
}