Lista Linear

[Tens de ter uma conta e sessão iniciada para poderes visualizar esta imagem]

Faça um programa utilizando funções que contenha o seguinte menu de opções:

1. Inserir elementos na lista
2. Remover elemento da Lista
3. Buscar um elemento da lista
4. Listar toda a lista
5. Sair

Usar as funções que estão abaixo.

Declarar

Código:

const int N = 5; // máximo de elementos (nós)
struct tNo{
int chave;
char nome[30];
char endereco[100];
};
void main()
{
tNo L[N]; // Lista de nós
int k=0; //número de elementos inseridos na lista
}

Função insere Obs: usar busca comun e ordenar após inserção.

Código:

int insere (tNo y, tNo L[N], int &k)
{
if (k < N)
{
if(busca(L, k, y.chave) == -1) // não encontrou
{
L[k] = y;
k++;
return 1; // sucesso na inserção
}
return -1; // Elemento existente!
}
else
return 0; // overflow: limite máximo alcançado
}

Função remove

Código:

int remove(tNo y, tNo L[N], int &k)
{
int j, pos;
if (k == 0) // underflow: lista vazia
return 0;
pos = busca(L, k, y.chave);
if (pos == -1) // não encontrou a chave
return -1;
for (j=pos; j < k-1; j++)
vet[j] = vet[j+1];
k--; // decrementa a quantidade de elementos
return 1; // sucesso na remoção
}

Função busca Obs: passar a função busca, para busca com sentinela.

Código:

// Retorna o índice do nó cuja chave foi encontrada, ou
// -1 se não encontrou nó com a chave procurada
int busca(tNo L[N], int k, int x)
{
int i=0;
while ( i < k )
if (L[i].chave == x)
return i; // retorna o índice
else
i++;
return -1; // não encontrou
}

Função busca binária Obs: só funciona com elementos ordenados, utilizar na opção 2.

Código:

int busca_bin(tNo L[N], int k, int x)
{
   int inferior=0, superior=k-1, busca=-1, meio;
   while(inferior <= superior)
   {
      meio=(inferior + superior)/2;
      if(L[meio].chave < x)
         inferior=meio+1;
      else
         if(L[meio].chave > x)
            superior= meio-1;
         else
         {
            inferior= superior+1;
            busca=meio;
         }
   }
   return busca;
}

1- Inserir elemento >> inserir já ordenando a lista, e usando busca comun para checar chaves repetidas.
2- Busca binaria de elemento
3- Remover elemento

Função busca utilizar busca com sentinela.

Código:

#include <iostream>
#include <string>
using namespace std;

const int N=6; // máximo de elementos (nós)
struct tNo{
         int chave;
         char nome[30];
         char endereco[100];
        };

int menu();
int insere(tNo y, tNo L[N], int &k);
int remove(tNo y, tNo L[N], int &k);
int busca(tNo L[N], int k, int x);
int busca_bin(tNo L[N], int k, int x);
void troca(tNo L[N], int k);
//void lista(tNo L[N], int k);

void main()
{
   tNo L[N], y; // Lista de nós
   int k=0; //número de elementos inseridos na lista
   int op, retorno=0;

   do{
      op=menu();
      if(op == 1)
      {
         system("cls");
         cout<< "=================================================\n";
         cout<< "\t\tInsercao\n";
         cout<< "=================================================\n";
         cout<< "\n\tDigite o codigo\n\t";
         cin>> y.chave;
         cout<< "\n\tDigite o nome\n\t";
         fflush(stdin);
         gets_s(y.nome);
         cout<< "\n\tDigite o endereco\n\t";
         fflush(stdin);
         gets_s(y.endereco);
         system("cls");
         cout<< "\n\n\tAguarde...\n\n";
         retorno=insere(y, L, k);
         system("cls");
         if(retorno == 1)
            cout<< "\n\nInsercao concluida com sucesso!\n\n";
         else
            if(retorno == -1)
               cout<< "\n\nErro...\n\n" << "Codigo ja existente\n\n";
            else
               cout<< "\n\nLimite maximo de cadastro excedido\n\n";
         system("pause");
      }
      else
         if(op == 2)
         {
            system("cls");
            cout<< "=================================================\n";
            cout<< "\t\tBusca\n";
            cout<< "=================================================\n";
            cout<< "\n\tDigite o codigo para buscar\n\t";
            cin>> y.chave;
            retorno=busca_bin(L, k, y.chave);
            system("cls");
            if(retorno >= 0)
            {
               cout<< "=================================================\n";
               cout<< "\t\tEncontrado\n";
               cout<< "=================================================\n";
               cout<< "Indice: " << retorno << endl;
               cout<< "Codigo: " << L[retorno].chave << endl;
               cout<< "Nome: " << L[retorno].nome << endl;
               cout<< "Endereco: "<< L[retorno].endereco << endl;
               cout<< "=================================================\n";
            }
            else
               cout<< "\n\n\tNao encontrado.\n\n";
            system("pause");
         }
         else
            if(op == 3)
            {
               system("cls");
               cout<< "\n\tDigite o codigo para remover\n\t";
               cin>> y.chave;
               system("cls");
               cout<< "\n\n\tAguarde...\n\n";
               retorno=remove(y,L, k);
               system("cls");
               if(retorno == 1)
                  cout<< "\n\n\tRemovido com sucesso\n\n";
               else
                  if(retorno == -1)
                     cout<< "\n\n\tNao encontrado\n\n";
                  else
                     cout<< "\n\n\tNem um cadastro feito ainda\n\n";
               system("pause");
            }
   }while(op != 4);
}

int menu()
{
   int op;
   
   do{
      system("cls");
      cout<< "=============================================\n";
      cout<< "\t1- Cadastrar\n";
      cout<< "\t2- Buscar\n";
      cout<< "\t3- Remover\n";
      cout<< "\t4- Sair\n";
      cout<< "=============================================\n\n";
      cout<< "\tDigite a opcao desejada.\n\t";
      cin>> op;
      if(op < 1 || op > 4)
      {
         system("cls");
         cout<< "\n\n\tOpcao invalida, opcao valida de 1 a 4\n\n";
         system("pause");
      }
   }while(op < 1 || op > 4);
   return op;
}

int insere(tNo y, tNo L[N], int &k)
{
   if (k < N-1)
   {
      if(busca(L, k, y.chave) == -1) // não encontrou
      {
         L[k] = y;
         k++;
         /*lista(L, k);      // Testa a função troca.
         system("pause"); 
         system("cls");*/
         if(k > 1)
            troca(L, k);
         /*lista(L, k);    //Testa a função troca.
         system("pause");*/
         return 1; // sucesso na inserção
      }
      return -1; // Elemento existente!
   }
   else
      return 0; // overflow: limite máximo alcançado
}

int remove(tNo y, tNo L[N], int &k)
{
   int j, pos;
   if (k == 0) // underflow: lista vazia
      return 0;
   pos = busca(L, k, y.chave);
   if (pos == -1) // não encontrou a chave
      return -1;
   for (j=pos; j < k-1; j++)
      L[j] = L[j+1];
   k--; // decrementa a quantidade de elementos
   return 1; // sucesso na remoção
}

// Retorna o índice do nó cuja chave foi encontrada, ou
// -1 se não encontrou nó com a chave procurada
/*int busca(tNo L[N], int k, int x)
{
   int i=0;
   while ( i < k )
      if (L[i].chave == x)
         return i; // retorna o índice
      else
         i++;
   return -1; // não encontrou
}*/

int busca(tNo L[N], int k, int x)
{
   int i=0;
   L[k].chave = x;
   while(L[i].chave != x) // busca com sentinela
      i++;

   if(i != k)
      return i; // retorna o nídice

   return -1; // não encontrou
}

int busca_bin(tNo L[N], int k, int x)
{
   int inferior=0, superior=k-1, busca=-1, meio;
   while(inferior <= superior)
   {
      meio=(inferior + superior)/2;
      if(L[meio].chave < x)
         inferior=meio+1;
      else
         if(L[meio].chave > x)
            superior= meio-1;
         else
         {
            inferior= superior+1;
            busca=meio;
         }
   }
   return busca;
}

void troca(tNo L[N], int k)
{
   int i=0;
   tNo hold;
   while(i < k)
   {
      if(L[k-1].chave < L[i].chave)
      {
         hold=L[k-1];
         L[k-1]=L[i];
         L[i]=hold;
      }
      i++;
   }
}

/*void lista(tNo L[N], int k)
{
   int i;
   for(i=0; i<k; i++)
   {
      cout<< "=====================================\n";
      cout<< "Indice: " << i << endl;
      cout<< "Codigo: " << L[i].chave << endl;
      cout<< "Nome: " << L[i].nome << endl;
      cout<< "Endereco: " << L[i].endereco << endl;
      cout<< "=====================================\n\n";
   }
}*/

Complemento: Lista_de_Exercícios_de_Listas_Lineares.doc