Lista simplesmente encadeada

[ena]

Olá,

Tenho um exercicio de Lista simplesmente encadeada. Estou com dificuldade na matéria. Se alguém puder me ajuda. Agradeço.

Utilizando o TAD lista com ponteiros (alocação dinâmica) e considerando uma lista de números inteiros, acrescente a este TAD as seguintes operações:

-Retorna posição p que o elemento de menor valor x se encontra na lista; caso não encontre, retorna p igual a zero

-Retorna posição p que o elemento de maior valor x se encontra na lista; caso não encontre, retorna p igual a zero

Faça testes para verificar o funcionamento das suas novas operações neste TAD.

Tenho que utilizar o programa abaixo para chegar ao exercicio.

#include <stdlib.h>
#include <stdio.h>
#define MAX 10

/* ========================================================================= */



typedef struct {
  int Chave;
  /* outros componentes */
} TipoItem;

typedef struct TipoCelula *TipoApontador;

typedef struct TipoCelula {
  TipoItem Item;
  TipoApontador Prox;
} TipoCelula;

typedef struct {
  TipoApontador Primeiro, Ultimo;
} TipoLista;

/* ========================================================================= */

void FLVazia(TipoLista *Lista)
{ Lista -> Primeiro = (TipoApontador) malloc(sizeof(TipoCelula));
  Lista -> Ultimo = Lista -> Primeiro;
  Lista -> Primeiro -> Prox = NULL;
}

int Vazia(TipoLista Lista)
{ return (Lista.Primeiro == Lista.Ultimo);
}

void Insere(TipoItem x, TipoLista *Lista)
{ Lista -> Ultimo -> Prox = (TipoApontador) malloc(sizeof(TipoCelula));
  Lista -> Ultimo = Lista -> Ultimo -> Prox;
  Lista -> Ultimo -> Item = x;
  Lista -> Ultimo -> Prox = NULL;
}

void Retira(TipoApontador p, TipoLista *Lista, TipoItem *Item)
{ /*  ---   Obs.: o item a ser retirado e  o seguinte ao apontado por  p --- */
  TipoApontador q;
  if (Vazia(*Lista) || p == NULL || p -> Prox == NULL) 
  { printf(" Erro: Lista vazia ou posicao não existe\n");
    return;
  }
  q = p -> Prox;
  *Item = q -> Item;
  p -> Prox = q -> Prox;
  if (p -> Prox == NULL) Lista -> Ultimo = p;
  free(q);
}

void Imprime(TipoLista Lista)
{ TipoApontador Aux;
  Aux = Lista.Primeiro -> Prox;
  while (Aux != NULL) 
    { printf("%d\n", Aux -> Item.Chave);
      Aux = Aux -> Prox;
    }
}

/* ========================================================================== */

int main(int argc, char *argv[])
{ 

  TipoLista lista;
  TipoItem item;
  int vetor[MAX];
  TipoApontador p;
  int i;
  float  tamanho=0;

  FLVazia(&lista);

  

  /*Insere cada chave na lista */
  for (i = 0; i < MAX; i++){
      item.Chave = i;
      Insere(item, &lista);
      tamanho++;
      printf("Inseriu: %d \n", item.Chave);
    }
  Imprime(lista);

  /*Retira cada chave da lista */
  for(i = 0; i < MAX; i++){
      p = lista.Primeiro;
      /*retira chave apontada */
      Retira(p, &lista, &item);
      tamanho--;
      printf("Retirou: %d\n", item.Chave);
    }
  Imprime (lista);
  
  system("PAUSE");
  return(0);
}

Editado Dezembro 11, 2010 por kuroi
Adicionar tag CODE

[OSJunior]

Olá, ena.

Para fazer os dois exercícios, você deve percorrer toda a lista em busca desses valores, caso ela não esteja ordenada. Caso esteja, você poderá:

a - pegar o primeiro/último item da lista, se a sua lista tiver uma cabeça/cauda; ou

b - utilizar a busca binária;

Editado Dezembro 10, 2010 por OSJunior