C++ Listas simplesmente encadeadas exercícios

Leonardo Naressi · 18 de março de 2019

a) Um procedimento para inserir um nodo após
o nodo K;

b) Uma função para remover o nodo após o
nodo K;
c) Uma função para remover o nodo K.

Eu montei as funções mas no momento de chamar elas não estão sendo executadas, se alguém poder dar uma ajuda agradeço!

/* ================================================= */
/* Exemplo de implementacao Listas Simplesmente Enc. */
/* Exercicios da apostila                            */
/* Profa Fabiana Lorenzi                             */
/* Estruturas de Dados I                             */
/* ================================================= */

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

/* estrutura da Lista Simplesmente Encadeada...*/
struct nodo {
 int dados;
 struct nodo *proximo;
};

void insere_esquerda(struct nodo **inicio, struct nodo **fim, int valor, int *sinal);
void insere_antes_de_k (struct nodo **inicio, struct nodo *k, int valor , int *sinal);
void insere_antes_do_quarto (struct nodo **inicio, int valor , int *sinal);
void insere_apos_de_k (struct nodo **inicio, struct nodo **fim, struct nodo *k, int valor, int *sinal);
void remove_apos_de_k (struct nodo **inicio, struct nodo **fim, struct nodo *k, int *sinal);
void remove_o_k (struct nodo **inicio, struct nodo **fim, struct nodo *k, int *sinal);
int conta (struct nodo *lista);

/*-------------------------------------------------*/
			/* Insere antes do quarto */
/*------------------------------------------------*/
void insere_antes_do_quarto (struct nodo **inicio, int valor, int *sinal)
{
	int x;
	struct nodo *p, *aux;
	
	    
	    if (conta(*inicio)<4){
		printf("Erro... lista não possui 4 nodos!!!");
		*sinal=0;
	}
	    else
	    {
	    p=(struct nodo*)malloc(sizeof(struct nodo));
	    if(p)
	    p->dados=valor;
	    aux=*inicio;
		for (x=2;x<3;x++){
			aux=aux->proximo;
			p->proximo=aux->proximo;
		    aux->proximo=p;
		    *sinal=1;
		  }
	    }
	}
	
/*===========================Fim do meu============================================*/
/* ================================================================================*/

/*===================================================================================*/
/*========================Insere apos o K o maior elemento============================================*/

void insere_apos_de_k (struct nodo **inicio, struct nodo **fim, struct nodo *k, int valor, int *sinal)
{

  struct nodo *aux, *p;
   
  if (*inicio) 		//Se a lista nÃ£o estÃ¡ vazia
  {	  p= (struct nodo *) malloc (sizeof(struct nodo));
 	  if (p == NULL)     //Se nÃ£o foi possÃvel alocar espaÃ§o em memÃ³ria 
             *sinal = 0;
        else 
        {
    	    p->dados = valor;
            aux = *inicio;
          	while (aux!=k && aux != NULL )
			  {
	          	aux = aux->proximo;
			  }
		 if (aux != NULL)//testa se encontro o K
		 {
			if(k==*fim)	
			{
			 p->proximo=*fim;
			 *fim=p; 
			}
			 else
			{ 
		  	 p->proximo=k->proximo;
  		     k=p->proximo; 	
			   *sinal = 1; 	
	 		}
		 	 
		}
	    else
	    { *sinal=0;
	    	free (p);
		}
	}
 }else
 	*sinal=0;
}
/*=============================fim=============================*/

/*======================Remover o k============================*/

void remove_o_k (struct nodo **inicio, struct nodo **fim, struct nodo *k, int *sinal)
{
	  struct nodo *aux, *p;
   
  if (*inicio==NULL) 		//Se a lista estiver vazia
  {	  
    *sinal = 0;	
  }
        else 
        {	
         aux = *inicio;	
            p=*inicio;
		do{
        	p=aux;
        	aux=aux->proximo;
          	}while (aux!=k && aux != NULL );
          	
        	if(aux==*fim){//aux esta com valor de k
        		p=aux->proximo;//p esta com o valor que anterior de k
        		free(aux);
			}
			else {
				p->proximo=aux->proximo;
				free(p);
			}
			*sinal=1;
			}
	}
	
/*========================FIM=========================*/	
	
/*===============Excluir apos o K o maior elemento==================*/
void remove_apos_de_k (struct nodo **inicio, struct nodo **fim, struct nodo *k, int *sinal)
{

  struct nodo *aux, *p;
   
  if (*inicio==NULL) 		//Se a lista estiver vazia
  {	  
    *sinal = 0;	
  }
    if (*fim==k) 		//Se o k for o fim da lista
  	{	  
             *sinal = 0;
	}
        else 
        {	
            aux = *inicio;	
            p=*inicio;
		do{
        	aux=p;
        	p=p->proximo;
          	}while (aux!=k && aux != NULL );
        		
        	if(*fim==p){//aux esta com valor de k
        		k=*fim;
        		free(p);
			}
			else {
				k->proximo=aux->proximo;
				free(p);
			}
			*sinal=1;
			}
	}
	


/*==========================FIM=============================*/

/* Insere um nodo a esquerda (no inicio)*/
/* ==================================== */
void insere_esquerda(struct nodo **inicio, struct nodo **fim, int valor, int *sinal)
{
  struct nodo *p;

     p = (struct nodo *) malloc (sizeof(struct nodo));
     if (p)
     {
	p->dados=valor;
	p->proximo=*inicio;
	*inicio = p;
        if (fim==NULL)
   	    *fim = p;
        *sinal=1;
     }
     else
	*sinal=0;
}

/* =============================== */
/* Insere um nodo antes do nodo K; */

void insere_antes_de_k (struct nodo **inicio, struct nodo *k, int valor , int *sinal)
{
  struct nodo *ant, *aux, *p;
   
  if (*inicio) 		//Se a lista nÃ£o estÃ¡ vazia
  {	  p= (struct nodo *) malloc (sizeof(struct nodo));
 	  if (p == NULL)     //Se nÃ£o foi possÃvel alocar espaÃ§o em memÃ³ria 
             *sinal = 0;
          else 
          {
    	    p->dados = valor;
            aux = *inicio;
            while (aux != k && aux != NULL)  //Percorre a lista atÃ© achar o nodo k  ou atÃ© chegar ao fim da lista.
		    {   ant = aux;
		        aux = aux->proximo;
            }
            if (aux != NULL)
            {
	           if (k==*inicio)
               {
   		         p->proximo=*inicio;
 		         *inicio=p;
                 *sinal = 1;
		       }
               else
		       {
		         ant->proximo = p;
  		         p->proximo = k;
       	       }
       	        *sinal = 1;
	        } 
            else   		//nÃ£o encontrou k
		    {  *sinal= 0;
		       free(p);
   	        }
           }  //se reservou memoria para p
   } else
	*sinal= 0;  //nao existe lista
}

/* ====================================================================== */
/* funcao que conta quantos elementos tem a lista simplesmente encadeada. */
/* ====================================================================== */
int conta (struct nodo *lista)
{
  int cont=0;

  while (lista != NULL)
  {
      cont = cont+1;
      lista=lista->proximo;
  }
  return cont;
}

/* ====================================================================== */
/* funcao que retorna o nodo com maior elemento da lista simp. encadeada. */
/* ====================================================================== */
struct nodo *maior_valor (struct nodo *lista)
{
  int ma=0;
  struct nodo *p, *ant;

  if (lista == NULL)
  {
    p=NULL;
  }
  else
  {
     ma=lista->dados;
     p=lista; /* guarda o end. do nodo, caso o maior seja o 1o. nodo da lista */
     ant=lista;
     lista=lista->proximo;
     while (lista != NULL)
     {
	   if (lista->dados > ma) /* procura o maior valor da lista... */
       {
	     ma = lista->dados; /* guarda o valor em MA */
  	     p = ant->proximo;  /* guarda o endereco do maior valor em P */
       }
       ant=lista;
       lista=lista->proximo;
     }
  }
  return p; /* funcao sempre retorna valor. */
}

/* =============================================== */
/* Procedimento para mostrar o conteudo da lista.  */
/* =============================================== */
void mostra_lista (struct nodo *lista)
{
  struct nodo *aux;

  aux=lista;
  while (aux != NULL) /* Enquanto nao for final da lista... */
  {
    printf("Valores-> %i\n",aux->dados);
    aux=aux->proximo;
  }
}

/* =============================================== */
/* Procedimento que libera todo conteudo da lista  */
/* =============================================== */
void libera_lista (struct nodo **lista)
{
  struct nodo *aux, *p;

  aux=*lista;
  while (aux != NULL) /* Enquanto nao for final da lista... */
  { 
    p=aux;
    aux=aux->proximo;
    free(p);
  }
}


/* Programa principal */
int main()
{
  int num, ok;  // variavel global que representa o sinal 

  struct nodo *l1i=NULL, *l1f=NULL, *lk=NULL;

  // l1i = inicio da lista
  // l1f = final da lista
  // lk = lista que armazena o endereco do nodo K

  /* Este trecho do programa serve para que o usuario digite varios valores (ate digitar 0)
     que serao armazenados na lista (insercao no inicio da lista).
  */
  printf("\nPara encerrar a insercao digite 0 !");
  do {
       printf("\nInforme um valor. : ");
       scanf("%d",&num);
       if (num != 0)
       {
      	 insere_esquerda(&l1i, &l1f, num, &ok);
         if (ok == 0)
           printf("\nErro de alocacao de memoria...");
       }
     }
  while (num != 0);

  /* O procedimento mostra_lista serve para mostrar o conteudo da lista
     que está sendo passada como parametro.
  */
  mostra_lista(l1i);
  getch();

  /* Este trecho do programa serve para que o valor digitado pelo usuario seja
     inserido ANTES do nodo que tem o maior valor.
  */
  printf("\nInforme outro valor: (insercao antes o maior elemento da lista(K)): ");
  scanf("%d",&num);
  if (num != 0)
  {
   /* a variável global lk representa o K.
      a funcao maior_valor é chamada e o endereco do nodo com o maior valor é
      armazenado na variavel global lk (K).
   */
   lk=maior_valor(l1i);

   /* Chamada do procedimento Insere_antes_de_k
      =========================================
     Neste exemplo, o valor digitado pelo usuario sera incluido antes do nodo que tem 
     o maior valor (ou seja, a posicao K eh a posicao do nodo que armazena o maior valor
     da lista.
   */
   insere_antes_de_k(&l1i, lk, num, &ok);
   if (ok == 0)       // se deu erro de alocacao de memoria...
     printf("\nErro de alocacao de memoria...");
     
   mostra_lista(l1i);
   getch();
   
   
   printf("Informe um numero para ser inserido antes do  4 nodo:");
   scanf("%d",&num);
   if (num != 0)
   {
      insere_antes_do_quarto(&l1i, num, &ok);    
   if (ok == 0)       // se deu erro de alocacao de memoria...
     printf("\nErro de alocacao de memoria...");
     mostra_lista(l1i);
  }
   /*
     Neste exemplo, o valor digitado pelo usuario sera incluido apos o nodo que tem 
     o maior valor (ou seja, a posicao K eh a posicao do nodo que armazena o maior valor
     da lista.
   */
 printf("\nInforme outro valor: (insercao apos o maior elemento da lista(K)): ");
  scanf("%d",&num);
  if (num != 0)
  {
  	lk=maior_valor(l1i);
   
   insere_apos_de_k(&l1i, &l1f, lk, num, &ok);
   if (ok == 0)       // se deu erro de alocacao de memoria...
     printf("\nErro de alocacao de memoria...");
	   mostra_lista(l1i);
	}
	//Seria para excluir o maior elemento e mostrar a lista
printf("Valor apos o maior elemento (k)excluido!!");
      remove_apos_de_k (&l1i, &l1f, lk, &ok); 
	  if (ok==0) {
	  printf("\nLista não pussui 2 elementos...");  
     mostra_lista(l1i);
	}
	//Para remover o nodo K
	printf("Maior elemento (k)excluido!!");
		remove_o_k(&l1i, &l1f, lk, &ok);
	 if (ok==0) {
		printf("\nLista esta vazia...");  
     mostra_lista(l1i);
	}
   libera_lista(&l1i);
   getch();
  }
}