Embed Size (px)
Citation preview
AEDAlgoritmos e Estruturas de Dados
LEEC/LEE - 2006/2007
Estrutura de Dados e Operações
AED (IST/DEEC) 2
Dados e Algoritmos: o que são?• Dados
– Conjunto de valores, que representam elementos informativos (ex: o valor inteiro 74 pode indicar o peso de uma pessoa, o ano da revolução do 25 de Abril, ...)
– Os valores podem estar armazenados de forma permanente - constantes(ex:π), ou podem ser substituídos em localizações – variáveis (ex: saldo da conta bancária, luz do semáforo, ...)
• Algoritmo– Sequência de instruções que, a partir de vários dados (previamente
armazenados, ou indicados por entidades externas ao programa como utilizadores ou ficheiros), calcula novos dados.Ex: cálculo do maior divisor comum, determinação do valor das compras num supermercado, ...
AED (IST/DEEC) 3
Tipologia de dados [1]• Simples
– Inteiros (int Index);– Reais (float Stock, double Income);– Caracteres (char Answer)
• Estruturados– Tabelas (‘‘array’’) - estáticas ou dinâmicas: vários elementos do mesmo
tipo• Unidimensionais (Array1[N])• Multidimensionais (Array2[N1]...[Nk] ou Array2[N1,...,Nk])• Acervos (Heap[N])
– Estruturas (‘‘struct’’): elementos de tipos possivelmente distintos
AED (IST/DEEC) 4
Tipologia de dados [2]• Dinâmicos: volume dos dados pode ser modificado durante a
execução do algoritmo– Listas
• Lista simples• Pilha (“stack”), Fila (“queue”), Fila Prioritária (“priority queue”)• Duplamente ligadas, anéis
– Árvores– Grafos
• Composições– listas de listas, listas de estruturas, lista de tabelas, tabelas de listas, ...
AED (IST/DEEC) 5
Que estrutura de dados escolher?• A escolha da forma como se armazenam os dados depende de
– Operações que sejam mais frequentes no algoritmo a implementar:• Quando o acesso e modificação são a base do algoritmo, as tabelas deverão
ser escolhidas• Quando a inserção e remoção são mais frequentes
– Usar listas simples, se estas operações ocorrem sempre no início (“STACK”)– Usar listas simples com ponteiro adicional para o fim da lista, se a inserção se
fizer no fim e a remoção no início (“QUEUE”)
– Previsibilidade sobre a memória necessária:• O uso de tabelas pressupõe que se saiba que memória é suficiente, ou que se
defina um valor suficientemente alto que comporte todas as instâncias de interesse.
• Quando tal valor é incomportável, o único recurso razoável consiste em gerir a memória dinamicamente.
AED (IST/DEEC) 6
Tipos básicos [1]
• Def: Um tipo de dados define os valores e as operações possíveis sobre esses valores.– Inteiros
• int (valores dependem da máquina: 16 bits entre -32768 e 32767, 32 bits entre -215 e 215-1) : o mais usado
• short (2 Bytes entre -32768 e 32767)• long (32 bits)
Os literais podem ter base decimal (ex: 27, -15), octal (iniciados por 0, ex: 031) ou hexadecimal (iniciados por 0x ou 0X, ex: 0x1f5, 0XFF).
AED (IST/DEEC) 7
Tipos básicos [2]
– Reais• double (precisão dupla) : o mais usado• float (precisão simples)
Os literais possuem duas partes– inteira e fraccionária, separadas por ponto (ex: -27.3, 9.5) ou– base e expoente, separadas por E (ex: 2.3E-2, 4E3).
– Nota: Os inteiros e reais podem conter apenas valores positivos, se o tipo contiver qualificador unsigned.
AED (IST/DEEC) 8
Tipos básicos [3]
– Caracteres• char
Os literais são delimitados por “plicas”– carácter impresso (ex: 'a', '}')– caracteres especiais formados por ‘\letra’
'\n' : mudança de linha (``newline´´)'\t' : tabulador'\\' : barra à esquerda (``backslash´´)
– código ASCII em base octal'\0' : carácter nulo (``NULL´´)
AED (IST/DEEC) 9
Conversão de tipos
• Conversão implícita:int Numb; float Inflation;Inflation = Numb / 3.5;O operador / converte Numb para real antes de efectuar a divisão.
• Conversão explícita (‘‘casting’’):int Numb1, Numb2;float Price;Price = ((float) Numb1) / Numb2;
AED (IST/DEEC) 10
Organização em C das definições de tipos
A definição dos tipos, no C, é dividida em dois ficheiros:• A interface, num ficheiro «header» (.h):
– Definição do tipo.– Protótipos das funções usadas para manipular objectos deste tipo, na forma
tipo-retorno nome(tipo par1, tipo par2,...);• A implementação, num ficheiro com extensão «.c»:
– Código das funções
Cada utilização do tipo é feita num ficheiro «cliente» onde o header é incluído:#include <stdio.h> /*biblioteca*/#include “ficheiro.h” /*declarações de projecto, no próprio directório*/
AED (IST/DEEC) 11
Ficheiro Num.h :typedef float Number;
Ficheiro Point.h :#include “Num.h”typedef struct {
Number x; Number y;
} Point;
Number distance(Point pA,Point pB);
Point create_point(Number x,Number y);
Definição de tipo: exemplo [1]
Ficheiro Point.c:#include <math.h>#include “Point.h”Number distance(Point pA, Point pB){
Number dx = pA.x – pB.x;Number dy = pA.y – pB.y;return(sqrt(dx*dx + dy*dy));
}
Point create_point(Number x, Number y){
Point pt;pt.x = x; pt.y = y;return pt;
}
AED (IST/DEEC) 12
Definição de tipo: exemplo [2]
Ficheiro principal:
#include “Point.h”main () {
Point Pt1, Pt2;Number Numb;Pt1 = create_point(1.0, 2.0);Pt2 = create_point(3.7, 4.5);Numb = distance(Pt1, Pt2);...
}
AED (IST/DEEC) 13
Ponteiros [1]
• A linguagem C permite aceder a posições de memória específicas por meio de ponteiros;
• Para cada um dos tipos básicos é possível criar ponteiros;• Exemplo:
int N1;• Reserva uma posição de memória onde a variável “N1” irá morar;• &N1 é o endereço de memória onde o valor de “N1” é armazenado;
int *N2;• Reserva uma posição de memória, de nome “N2”, onde se poderá
colocar o endereço de um inteiro, ou do primeiro inteiro de uma tabela de inteiros;
AED (IST/DEEC) 14
Ponteiros [2]
• Exemplo (continuação):int N1;
N13
N1 = 3;
&N1
N1??
N13
&N1
AED (IST/DEEC) 15
Ponteiros [3]
• Exemplo (continuação):int *N2; N2
??
N2=&N1;
N2 = (int *) malloc(3*sizeof(int));
N2&N1
&N1
N2?? ?? ??
&N2[0]
&N2[0]
A alocação de memória ocor-re em qualquer sítio, podendo ser acima ou a-baixo do local onde “mora” o ponteiro.
3
N1
AED (IST/DEEC) 16
printf(“%d”, *(N2+1));• 5• porque N2+1 é &N2[1]: quando a variável for de tipo ponteiro para tabela, + adiciona espaço de cada célula
printf(“%d”, *N2+1);• ??+1• porque *N2 é o conteúdo de N2[0] que contém ??.
Ponteiros [4]
• Exemplo (continuação)N2[1] = 5; N2
?? 5 ??
&N2[1]
&N2[0]
AED (IST/DEEC) 17
• Introdução aos Dados e Algoritmos
• Listagem de tipos de dados mais vulgares e critérios de escolha
• Tipos básicos, conversão de tipos
• Organização em C das definições de tipos
• Ponteiros
Síntese da Aula 1 de Tipologia e Operações
AED (IST/DEEC) 18
Tabelas [1]• Def: Uma tabela (“array”) é uma série de localizações, todas do
mesmo tipo, acedidas por índices numéricos a partir de 0.– Sintaxe: após a declaração base inserir uma das opções
• {[Dimensão]}+
– Restrições:• as dimensões são inteiros positivos.
ex: int Tab1[4]; /* tabela de 4 inteiros */char Tab2[3][2]; /* tabela de char 3 por 2 */char Tab3[5][14][2]; /* tabela de char 5 por 14 por 2 */
Tab1[0] Tab1[1] Tab1[2] Tab1[3]
AED (IST/DEEC) 19
Tabelas [2]• Os índices são valores entre 0 e largura-1, para cada dimensão.
ex: Tab1[0]=0; /*correcto*/Tab1[4]=-25; /*incorrecto: limite máximo é 3 */Tab2[2][0]='?'; /*correcto*/
É responsabilidade do programador garantir que os índices estão dentro dos limites!!!
AED (IST/DEEC) 20
Tabelas [3]
As tabelas são inicializadas por ciclos de varrimento ou lista de valores delimitada por { }.
ex: /* tabela Tab1 inicializada com inteiros */– for(Idx=0; Idx<4; Idx++) Tab1[Idx]=Idx;– Tab1 = {0,1,2,3};
/* inicialização de Tab2 */– for(Idx1=0; Idx1<3; Idx1++)
for (Idx2=0; Idx2<2; Idx2++)Tab2[Idx1][Idx2] = 'a'+2*Idx1+Idx2;
– Tab2 = { {'a','b'}, {'c','d'}, {'e','f'} };
AED (IST/DEEC) 21
Tabelas [4]
Em C, existe uma correspondência entre tabelas e ponteiros:*Array ⇔ Array[0]*(Array + 1) ⇔ Array[1]*(Array + Idx) ⇔ Array[Idx]
As instruções seguintes:int Array[10]; int *Ptr;Array[2] = 3;Ptr = Array + 2;printf(“%d\n”, *Ptr);
escrevem 3 no terminal.
AED (IST/DEEC) 22
Tabelas [5]
Quando o tamanho da tabela é conhecido apenas na altura da execução deve-se alocar a memória de maneira dinâmica (ver também acetato 15):
#include <stdlib.h>#include <stdio.h>main (int pArgc, char *pArgv[]){
int Numb = atoi(pArgv[1]);int *Space = (int *) malloc(Numb * sizeof (int));if (Space == NULL)
fprintf(stderr, “Memória insuficiente.\n”);…
AED (IST/DEEC) 23
Tabelas multidimensionais [1]
• Declaração:float Vect[10][20];Declara um vector de 10 elementos, cada elemento sendo um vector de 20
elementos de float.
• Alocação dinâmica:float ** Newmatrix(int pRows, int pColumns) {int Idx;float **mat; /* mat é um apontador para uma
tabela que contém float ! */mat = (float **)malloc(pRows * sizeof (float *));for (Idx=0; Idx<pRows; Idx++)
mat[Idx]=(float *)malloc(pColumns * sizeof(float));return mat;
}
AED (IST/DEEC) 24
Tabelas multidimensionais [2]
• Exemplo:float ** mat;
mat??
mat[0] = (float *) malloc(4*sizeof(float));
&mat[0] ?? ?? ??
&mat[0]
&mat[0] &mat[0][0] ?? ?? ?? ?? ?? ??
&mat[0][0]
– há que fazer malloc para mat[1] e mat[2] como acima.
mat = (float **) malloc(3*sizeof(float *));
AED (IST/DEEC) 25
Tabelas multidimensionais [3]
• Exemplo (continuação):– Depois de se usar a matriz “mat” pode ser necessário libertar a memória.– Tal faz-se pela ordem inversa da alocação– Liberta-se “mat[0]”, “mat[1]” e “mat[2]” e só depois se liberta
“mat”– A sequência
free(mat[0]);free(mat[1]);free(mat[2]);free(mat);
• para efeitos de posterior utilização de memória, produz
mat??
AED (IST/DEEC) 26
Tabelas multidimensionais [4]
• O que aconteceria se, depois de alocar “mat[0]” se fizesse a libertação de “mat”? – Ou seja,
mat = (float **) malloc(3*sizeof(float *));mat[0] = (float *) malloc(4*sizeof(float));free(mat);
Como fica a memória?
?? ?? ?? ?? ??mat
– O espaço de memória que foi reservado para “mat[0][0-3]”permanece, nunca mais podendo ser usado por outras alocações.
AED (IST/DEEC) 27
Tabelas multidimensionais [5]
• Exemplo: multiplicação de matrizes:float **Mult(float **pA, float **pB,
unsigned pLA, unsigned pCB, unsigned pS){int IdxI,IdxJ,IdxK;float **Res = Newmatrix(pLA,pCB);for (IdxI=0; IdxI < pLA; IdxI++)
for (IdxJ=0; IdxJ < pCB; IdxJ++)for (IdxK=0; IdxK < pS; IdxK++)
Res[IdxI][IdxJ] += pA[IdxI][IdxK] * pB[IdxK][IdxJ];return(Res);}
uso da função:#define LINEA 10#define COLB 15#define SIZE 20 float **ArrA = Newmatrix(LINEA,SIZE),
**ArrB = Newmatrix(SIZE,COLB), **ArrC;ArrC = Mult(ArrA, ArrB, LINEA, COLB, SIZE);
AED (IST/DEEC) 28
Cadeias de caracteres [1]
• Def: Uma cadeia de caracteres (“string”) é uma tabela de caracteres, sendo obrigatoriamente '\0' o último carácter.– Uma cadeia pode ser indicada entre aspas (ex: “perigo!”
é uma cadeia de 8 caracteres).– Numa tabela inicializada, o compilador de C determina a
dimensão.ex: char Msg[]=“texto”; /*tabela 6 caracteres*/
int Tab[]={-4,17,5}; /*tabela 3 inteiros*/
Os ponteiros e a gestão dinâmica de memória facilitam o tratamento de cadeias de caracteres.
AED (IST/DEEC) 29
Cadeias de caracteres [2]
• Processamento de cadeias de caracteresExemplo: procura numa cadeia de caracteres
char * Procura (char C, char *pString){int Idx;for (Idx=0; (pString[Idx] != ‘\0’) &&
(pString[Idx] != C); Idx++);return pString+Idx; /* retorna uma cadeia de
caracteres que começa pelosímbolo contido em C ou por uma cadeia vazia. */
}
AED (IST/DEEC) 30
Cadeias de caracteres [3]A biblioteca do C string.h oferece um conjunto de funções
para manipular cadeias de caracteres:• Função para copiar o conteúdo de uma cadeira de caracteres:
char *strcpy(char *dest, char *src);O ponteiro dest deve ter a memória alocada suficiente para conter a cadeia src.
• Função que devolve uma cópia da cadeia de caracteres:char *strdup(char *s);
• Função que compara duas cadeias de caracteres:int strcmp(char *s1, char *s2);devolve um inteiro maior, igual ou menor do que 0 consoante a cadeia s1 for menor, igual ou maior do que s2.
AED (IST/DEEC) 31
Estruturas [1]• As tabelas apenas permitem alocar, estática ou dinamicamente,
“caixas” de memória para objectos do mesmo tipo;– Só inteiros, só reais, só caracteres...
• Para agrupar objectos de tipos diferentes numa mesma variável existem as estruturas– Exemplo:
#define SIZE 80struct {
char nome[SIZE];int idade;float altura;
} pessoa;
pessoa? ?????? ... ???
AED (IST/DEEC) 32
Estruturas [2]
• A partir do momento que se definem estruturas, mais ou menos complexas, podem definir-se novos tipos– Exemplo:
• typedef struct {char nome[SIZE];int idade;float altura;
} pessoa;
– Podem-se declarar variáveis do tipo “pessoa”pessoa aluno, *aed, ip[400];
como já se fazia com os tipos básicos
AED (IST/DEEC) 33
Estruturas [3]• Uma estrutura pode ter qualquer número de campos e cada
campo pode ser qualquer um dos tipos definidos e/ou ponteiros para esses tipos.– struct {
int numero;pessoa aluno;float *notas_de_cadeiras;
} aluno_IST;• Inclusivamente pode-se fazer o seguinte
• typedef struct _no_elementar{unsigned int numero;pessoa aluno;struct _no_elementar * proximo;
} no;
AED (IST/DEEC) 34
Estruturas [4]
• Fazerno *aed;
equivale a fazer
• E fazeraed = (no *) malloc(1*sizeof(no));
equivale a fazer
??
aed
aed
&aed.numero ? ? ?
numero aluno proximo
AED (IST/DEEC) 35
Estruturas [5]
• E fazeraed->proximo = (no *) malloc(1*sizeof(no));
equivale a
 ? ?
numero aluno proximo
? ? ?
aluno proximo

numero
• Notar que qualquer campo de uma estrutura que seja um ponteiro apenas reserva o espaço para o ponteiro aquando da alocação;• Compete ao programador estar consciente de que tem ponteiros como campos das estruturas. Tem de reservar posteriormente memória para guardar os objectos apontados por esse ponteiro, assim como lembrar-se de libertar essa memória.
aed
AED (IST/DEEC) 36
Estruturas [6]
• Como se liberta a memória dos objectos criados atrás– Correctamente
free(aed->proximo);free(aed);
??
aed
– Incorrectamentefree(aed);
?? ? ? ?
aluno proximonumero

aed
AED (IST/DEEC) 37
• Tabelas
– Unidimensionais– Multidimensionais– Alocação dinâmica e estática
• Cadeias de Caracteres
• Estruturas– Conceito base e construção– Definição de novos tipos– Exemplos de manipulação dinâmica de memória
Síntese da Aula 2 de Tipologia e Operações
AED (IST/DEEC) 38
• Definição: uma lista é uma sequência de nós compostos por• um item, contendo informação específica do nó.• um apontador para o nó seguinte.
• Um nó é uma estrutura recorrente (“recursive”)– Último elemento (terminal) aponta para vazio (NULL)– Os restantes elementos (recorrentes, ou indutivos), entre o primeiro e o
penúltimo, contêm um apontador para um elemento do mesmo tipo.
Listas [1]
AED (IST/DEEC) 39
Listas [2]
• Estrutura conceptual
item item itemCabeça
(‘‘head’’)
“head”
  NULL

• Disposição em memória
AED (IST/DEEC) 40
Listas [3]
• Definição em C:Cada nó da lista é composto por :– Um item, que contém a informação específica ao elemento,
normalmente definido por declaração tipo:typedef xxx Item;
– Um apontador para o próximo elemento da lista.
typedef struct _list {Item item;struct _list * next;
} list;
O último elemento da lista tem o seu campo next inicializado com NULL .
AED (IST/DEEC) 41
Listas [4]
• Declaração:uma lista é representada por um apontador para uma estrutura de tipo list:list *l;
• Alocação de um elemento de lista:
l = (list *) malloc(sizeof(list));if (l == NULL) {fprintf(stderr, “Não há mais memória...!\n”);
}
AED (IST/DEEC) 42
Listas [5]
• Acesso a informação:list *l;(*l).item e (*l).next permitem aceder aos dois campos da
estrutura.Mais simplesmente, podemos usar o operador -> e escrever:
l->item, l->next
• Elementos seguintes na lista:l->item: item do primeiro elemento da lista,l->next->item: item do segundo elemento da lista,l->next->next->item: item do terceiro elemento da lista
AED (IST/DEEC) 43
Tabela de listas
• Como se cria uma tabela de listas?list **tlst;tlst = (list **) malloc(4*sizeof(list *));
tlst
&tlst[0]&tlst[0] ?? ?? ?? ??
&tlst[2]&tlst[1]
&tlst[3]
– Cada “tlst[i]”, com i=0,1,2,3, é um ponteiro para uma variável do tipo “list”
– Notar que “tlst” é um ponteiro para apontadores de “list”.
AED (IST/DEEC) 44
Lista de listas [1]
• Como se cria uma lista de listas?typedef struct _l_of_l_ {
list *lista; /* ponteiro para sub-lista */struct _l_of_l_ *seguinte;
} lst_lst;
lst_lst *exemplo;
A variável “exemplo” é um apontador para um tipo que é uma estrutura.Essa estrutura possui dois campos
§ apontador para o próximo elemento da lista de listas.§ apontador para variáveis do tipo list;
AED (IST/DEEC) 45
Lista de listas [2]
• A instruçãolst_lst * exemplo;
produz apenasexemplo
??
lista seguinte
exemplo
?? 00...00
• E as instruçõesexemplo = (lst_lst *) malloc(sizeof(lst_lst));exemplo->seguinte = NULL;
produzem
AED (IST/DEEC) 46
Lista de listas [3]
• Supor que de seguida se fazexemplo->seguinte = (lst_lst *) malloc(sizeof(lst_lst));exemplo->seguinte->seguinte = NULL;
lista seguinte
exemplo
?? 
lista seguinte
?? 00...00

• Para criar o primeiro nó da primeira lista, faz-seexemplo->list = (list *) malloc(sizeof(list));exemplo->list->next = NULL;
exemplo   ?? 00...00 00...00
next
item??
AED (IST/DEEC) 47
Lista de tabelas [1]• Como se cria uma lista de tabelas?
typedef struct _l_tab {Item * tabela;struct _l_tab * seguinte;
} ltab;• As instruções
ltab * xpto;xpto = (ltab *) malloc(sizeof(ltab));xpto->seguinte = NULL;
criamxpto
 ?? 00...00

AED (IST/DEEC) 48
Lista de tabelas [2]
• Para criar uma tabela no campo “xpto->tabela” basta usar o procedimento já descrito para a criação de uma tabelaxpto->tabela = (Item *) malloc(N*sizeof(Item));
• Para criar o próximo elemento da lista basta usar o procedimento já descrito para criação de um novo nó numa lista
xpto->seguinte = (ltab *) malloc(sizeof(ltab));xpto->seguinte->seguinte = NULL;
xpto


   00...00??
AED (IST/DEEC) 49
Listas duplamente ligadas [1]• Para criar uma lista com ponteiros para a frente e para trás
(anel)typedef struct _d_lst_ {
Item objecto;struct _d_lst_ * anterior;struct _d_lst_ * posterior;
} dlst;
dlst * frente_verso;frente_verso = (dlst *) malloc(sizeof(dlst));frente_verso->anterior = frente_verso->posterior = NULL;
frente_verso 00...00 00...00

??
objecto anterior posterior
AED (IST/DEEC) 50
Listas duplamente ligadas [2]
• Para acrescentar um novo elemento há que fazerfrente_verso->posterior = (dlst *) malloc(sizeof(dlst));frente_verso->posterior->anterior = frente_verso;frente_verso->posterior->posterior = NULL;
frente_verso 00...00 

??
objecto anterior posterior
 00...00??
objecto
anterior posterior
AED (IST/DEEC) 51
Interface para Listas [1]
• A interface do tipo list, é constituída por:– A definição do tipo list:
#include “defs.h”typedef struct _list {
Item item;struct _list *next;
} list;– Alocação de um novo elemento:
list * NewElement(Item); – Libertação da memória associada a um elemento:
void FreeElement(list *);
Ficheiro que define item
AED (IST/DEEC) 52
Interface para Listas [2]
– Inserção de um elemento a seguir a outro:void InsertNext(list *, list *);
– Remoção de um elemento a seguir a outro:void DeleteNext(list *);
– Função para aceder ao elemento seguinte:list * Next (list *); /* acessor */
– Função de acesso a um item:Item Item(list *); /* acessor */
AED (IST/DEEC) 53
Interface para Listas [3]
• No ficheiro “defs.h” define-se o item, por exemplo
typedef int Item;
AED (IST/DEEC) 54
Implementação para Listas [1]
Implementação do tipo list:– Alocação de um novo elemento:
list * NewElement(Item N) {list *El = malloc(sizeof(list));El ->next = NULL; El->item = N;return(El);
}
– Libertação da memória associada a um elemento:void FreeElement(list *pEl) {
free(pEl);}
AED (IST/DEEC) 55
Implementação para Listas [2]– Inserção de um elemento a seguir a outro:
void InsertNext(list *pEl1, list *pEl2) {pEl1->next = pEl2->next;pEl2->next = pEl1;
}
pEl2
pEl1
etc..
primeiro!depois!
pEl2
pEl1
etc..
AED (IST/DEEC) 56
Implementação para Listas [3]
– Remoção de um elemento a seguir a outro:void DeleteNext(list *pEl) {
list *Aux;Aux = pEl->next->next;FreeElement(pEl->next);pEl->next = Aux;
}
pEl
pEl
aux
primeiro!
depois!
AED (IST/DEEC) 57
Implementação para Listas [4]
– Função para aceder ao elemento seguinte:list * Next (list *pEl) {
return pEl->next;}
– Função de acesso a um item:Item Item(list *pEl) {
return pEl->item;}
AED (IST/DEEC) 58
Implementação para Listas [5]
Processamento de listas• Para percorrer uma lista:
for (Ptr = pFirst; Ptr != NULL; Ptr = Ptr ->next)pFirst aponta para o primeiro elemento da lista.Æ O último elemento da lista deve ter o seu campo next inicializado com
NULL.
• Exemplo: para imprimir todos os elementos da lista:for (Ptr = pFirst; Ptr != NULL; Ptr = Ptr ->next)
PrintItem(Ptr->item);
AED (IST/DEEC) 59
Implementação para Listas [6]
• Função para reverter uma lista:list *reverse (list *pL) {
list *Next = pL, *Cur = pL, *Res = NULL;while (Cur != NULL) {
Next = Cur->next;Cur ->next = Res;Res = Cur; Cur = Next;
}return Res;
}
AED (IST/DEEC) 60
• Listas– Lista simples– Tabelas de listas– Listas de listas– Listas de tabelas– Listas duplamente ligadas
• Interface para listas simples• Implementação para listas simples
Síntese da Aula 3 de Tipologia e Operações
