Fila Dupla em Alocação Sequencial  

Os acessos são feitos pelas duas extremidades.

               0                    (MAX -1)
               ______________________
Fila Dupla -> |_|...|_|x|x|x|_|..._|_|
                     î     î
                    esq   dir

#define MAX ...

typedef ... TipoDoElemento;

int esquerda, direita;

TipoDoElemento FilaDupla[MAX];

void InicializaFilaDupla()
{
  esquerda = direita = MAX/2;
}

void InsereDireitaFilaDupla( TipoDoElemento x )
{
  if( direita == (MAX - 1)  )
    Overflow();

  FilaDupla[++direita] = x;
}

void InsereEsquerdaFilaDupla( TipoDoElemento x )
{
  if( esquerda == -1 )
    Overflow();

  FilaDupla[esquerda--] = x;
}


void RemoveDireitaFilaDupla( TipoDoElemento *x )
{
  if( direita == esquerda )
    Underflow();
  else
  {
    *x = FilaDupla[direita--];
    if( esquerda == direita)
      InicializaFilaDupla();
  }
}

void RemoveEsquerdaFilaDupla( TipoDoElemento *x )
{
  if( direita == esquerda )
    Underflow();
  else
  {
    *x = FilaDupla[++esquerda];
    if( esquerda == direita)
      InicializaFilaDupla();
  }
}

Exercício: Escreva as funções para a manipulação de uma fila dupla em
alocação circular.

Existem também as filas duplas com restrição de acesso.
Fila dupla com saída restrita - a retirada de elementos só pode ser feita
em uma das extremidades;
Fila dupla com entrada restrita - a inserção de elementos só pode ser feita
em uma das extremidades.


Estruturas Dinâmicas: podem ser alteradas durante a execução do programa.

Alocação dinâmica: alocamos a priori apenas o espaço para guardar o
                   endereço dos dados e não seu conteúdo.


Queremos alocar uma célula p do tipo T: Alocar(p,tam(T)) faz com que p
contenha o endereço de um espaço de memória do tamanho de um elemento
do tipo T.

               +-------+
  +----+       |       |
p:|  *-|------>|       |
  +----+       |       |
               +-------+

um exemplo, dados n e n números inteiros imprimí-los em ordem inversa:

#include <stdio.h>
#include <stdlib.h>
int main() {
  int *p;
  int i, n, num;
  scanf("%d",&n);
  p = malloc (n * sizeof(int));
  if (p == NULL) {
	printf("Memoria insuficiente\n");
	exit(0);
  }
  for (i = 0; i < n; i++)
	scanf("%d", &p[i]);
  for (i = n - 1; i >=0; i--)
	printf("%d\n", p[i]);
}



 

    Alocação Ligada para Listas Lineares

  A sequência dos elementos de uma lista linear é dada através de ligações. 
Assim cada nó da lista contém dois campos:
  _
 |  info: informação do nó
<
 |_ prox: "endereço"do próximo elemento da lista


  Representação Gráfica:

          ___     ___     ___     ___
lista -> |_|_|-> |_|_|-> |_|_|-> |_|_|-|
                                       ~

Vantagens sobre alocação seqüencial:

- Permite que só o número de elementos necessários seja alocado.
- Para inserir um elemento em uma lista ligada, entre os elementos i e i+1,
  temos apenas de modificar as ligações destes elementos. O mesmo ocorre
  quando removemos um elemento.
- Para concatenar duas listas, basta ligá-las.

Desvantagens:

- Cada elemento tem um campo extra para apontar para o próximo.
- Para acessar um nó intermediário, devemos percorrer a lista até ele.



Alguns exemplos

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

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

/* Leitura de uma sequencia de inteiros terminada por zero 
 * e criação da lista ligada correspondente
 */
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);
  }
}

/* Imprime os elementos de uma lista */
void Imprime(apontNo p) {
  if (p == NULL)
    printf("Lista vazia\n");
  else {
    while (p != NULL) {
      printf("%d -> ", p->info);
      p = p->prox;
    }
    printf("fim\n");
} 


/* Insere um elemento no início da lista */
void Insere( apontNo *p, int x){
  paux = (apontNo) malloc (sizeof(No));
  paux->info = x;
  paux->prox = *p;
  *p = paux;
}



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