Estrutura de Dados: Univesp

Page 1

Iniciando

Um primeiro Programa

Em Java:

cod.:

public class HelloWorld{

public static void main( String[] args) {

System.out.println( " Hello World");

}

}

Em C:

#include < stdio.h> // nome da importação

int main{

printf( " Hello World \n"); // imprimir na tela

return 0; // Implementação de retorno de inteiro.

}

Java e C possuem pradigmas diferentes.

fonte: https://youtu.be/y0B-vQI6Tiw ( Norton T. Roman).

Page 2

Criando uma primeira estrutura simples

O que é uma Estrutura ?

É uma maneira de organizar dados. Guardar e modelar informações.

Como modelamos essa estrutura?

Como instaciamos essa estrutura ?

Como acessamos esses campos para mudar ou para busca-los?

Exemplo de código em Java:

cod.:

public class PesoAltura{

int peso; // atributo

int altura; // atributo

}

public class EstruturaSimples{

public static final int alturaMaxima = 225; // atributo

public static void main( String[] args) {

PesoAltura pessoa1 = new PesoAltura();

pessoa1.peso = 80;

pessoa1.altura = 185;

System.out.println( " O pese da pessoa1 é "+ pessoa1.peso + " , a Altura da pessoa1 é " + altura );

if ( pessoa1.altura > alturaMaxima) System.out.println ( " Altura máxima excedida") else System.out.println( " Abaixo da altura máxima");

}

}

Em C a sintaxe é diferente:

cod.:

typedef struct {

int peso; // campo

int altura; // campo

}PesoAltura;

A sintaxe struct{ ... } define uma estrutura com campos definido dentro de chaves.

typedef define o tipo , dando o nome a estrutura.

typeof int CHAVE; Nesse caso aqui permitimos que a palavra CHAVE represente no código o tipo int ( inteiro).

Em C , public static final int aturaMaxima = 225; é semelhante à #define alturaMaxima 225 ;

Em C, public static void main( String[] args) {} é semelhante à int main(){ .... } return 0;

Em Java instaciamos nosso objeto com o contrutor da classe empregando:

PesoAltura pessoa1 = new PesoAltura() ;

Essa variável pessoa1 guarda o endereço;

Em C,

PesoAltura pessoa1; // declaração de tipo estrutura

pessoa1.peso = 80;

pessoa1.altura = 185;

No caso do C já cria uma estrutura, não vai criar um ponteiro de instanciação;

if( pessoa1.altura> alturaMaxima) printf( "Altura acima da máxima \n");

else printf( Altura abaixo da máxima \n");

return 0;

}

Uso de memória

Por que uso de memório é tão diferente? # analisar e inserir figuras posteriormente

Um dos motivo é que nossa implementação em C não corresponder totalmente à implementação em Java.

Ponteiros e Locação da memória

Em C há uma distinção bem explicita entre um tipo ( ou uma estrutura) e um endereço:

int x : significa que x é um variável do tipo inteira.

int* y : significa que y é uma variável que corresponde ao endereço para o inteiro;

cod.:

#include

int main(){

int x = 25;

int* y = &x; // & direciona o valor dado do endereço x.

*y = 30; // Vá na memória referenciada ( apontada) por y.

print( " O valor de x: %i \n", x );

return 0;

}

O & indica que desejamos o endereço de uma variável.

Se quizer alocar uma certa quantidade de memória utilizamos um função chamada malloc ( memory allocation) que possui como parâmetro a quantidade de bytes queremos alocar.

Como saber quantos bytes queremos alocar ?

Usamos um operador chamado sizeof .

cod.:

#include stdio.h

#include malloc.h #Biblioteca nova, lembrar do uso do dimond. O malloc aloca uma quantidade de memório do tamanho de um tipo inteiro

int main() {

int* y = (int*) malloc ( sizeof(int)) ; // Olha, foi feito um casting para tipo inteiro, retorna um ponteiro para inteiro.

*y = 20; // memória apontada

int z = sizeof( int ); // Tamanho do tipo inteiro.

printf( " *y = %i z =%i \n ", *y, z);

return 0;

}

Segunda Implementação

#include stdio.h

#include malloc.h

#define alturaMaxima 225

typedef struct{

int peso;

int altura;

} PesoAltura;

int main() {

PesoAltura* pessoa1 = ( PesoAltura*) malloc( sizeof( PesoAltura)); // Criando um ponteiro para estrutura

pessoa1->peso = 80; // Como acessar um ponteiro ? -> ( seta )

pessoa1->altura = 185;

printf( " Peso: %i , Altura: %i" , pessoa1->peso, pessoa1->altura);

if( pessoa1->altura > alturaMaxima) printf( "Limite ultrapassado \n"); else ( "Ainda no limite \n");

}

Page 3

Lista Linear Sequencial

São estruturas no qual cada elemento tem um predecessor e um sucessor. ( Exceto o primeiro elemento e o último).

No caso da lista Linear Sequencial temos uma condição a mais a ordem física dos elementos ( "visto" na memória) é a mesma ordem lógica dos elementos ( "vista" pelo usuário) .

Modelagem:

Modelaremos usando um arranjo.

Registros conterão os dados de interesse do usuário. ( Basicamente são os elementos ).

Nosso arranjo terá um tamanho fixo e controlaremos o número de elementos com uma variável adicional. ( Busca do elemento, inserção e exclusão).

Funções de Gerenciamento

Inicializar a estrutura.

Retornar a quantidade de elementos válidos.

Exibir todos elementos da estrutura.

Buscar por elemento na estrutura.

Inserir elemento na estrutura.

Excluir elemento da estrutura.

Reinicializar a estrutura.

Inicializar

Criação do arranjo,

cod.:

void inicializarLista (LISTA l ){ // l é um parâmetro passado pelo usuário

l.nroElem = 0;

}

void inicializarLista( LISTA*l) {

l->nroElem = 0; // neste caso passamos o endereço de uma lista

}

Na primeira função a lista original não foi modificada pois estamos trabalhando em cima de uma cópia. Já na segunda implementação a lista foi modificada, como passamos o endereço da estrutura original.

Retornar número de elementos dessa lista

Retornaremos o campo de nroElem.

cod.:

int tamanho( LISTA*l){

return l-> nroElem;

}

Exibir todos elementos da estrutura.

cod.:

void exibirLista( LISTA*l){

int i;

printf( "LISTA \" ");

for( int i = 0; i < l->nroElem; i++){

printf( " %i ", l ->A[i].chave); // chave é cada um dos elementos ( aparentemente o index tenho de confirmar)

printf( "\" \n");

}

}

Busca por elemento na estrutura.

A função de busca deverar:

Receber uma chave do usuário.

Retornar a posição em que este elemento se encontra na lista( caso seja encontrado).

Retorna -1 caso não haja um registro com essa chave na lista. Posição inválida do arranjo.

cod.:

int buscaSequenciaLinear( LISTA l, TIPOCHAVE ch ){

int i = 0;

while( i < l->nroElemento ) {

if( ch ==l->A[i].chave) {

return i;

else i++;

}

return -1; // Se saiu do laço

}

Inserção de elemento

cod.:

bool inserirElemList( LISTA*l, REGISTRO reg, int i) {

int j;

if( ( l->nroElem == MAX) || (i < 0) || (i > l->nroElem) ) {

return false;

}

for( j = l-> nroElem ; j > i ; j--) l->A[j]= l->A[j-1];

l-> A[i] = reg;

l-> nroElem++;

return true;

}

Exclusão de elemento

O usuário passa a chave do elemento que ele quer excluir. Se houver um elemento com esta chave na lista, "excluir este elemento", desloca todos os elementos posteriores uma posição para esquerda , diminui em um campo o nroElem e retorne true.

Caso contrário, retorne false.

bool excluirElemLista( TIPOCHAVE ch, LISTA*l) { // o tipo de chave na realidade o valor.

int pos, j;

pos = buscaSequenciaLinear( l, ch );

if( pos == -1) return false;

for( j = pos; j< l->nroElem - 1 ; j++) l->[j] = l->[j+1];

l->nroElem --;

return true;

}

Reinicialização da Lista

Deixar a estrutura pronta para usuário como ela não tivesse sido usada antes, zera-la. Como o arranjo é prealocado, quando o usuário cria a estrutura já define uma lista com MAX registro.

void reinicializa( LISTA*l){

l->nroElem = 0;

}

Uma observação é que quando o usuária cria a estrutura já cria o arranjo, então há um grande espaço de memória que não é utilizada já que inicialmente não há nenhum elemento inserido.

fonte: https://youtu.be/g_nbG7L5ou0?list=PLxI8Can9yAHf8k8LrUePyj0y3lLpigGcl

Page 4

Lista Sequencial ( continuação)

Otimização da busca por elemento.

Mudanças na ordem de inserção dos elementos.

Busca por elementos

O usuário qual elemento será buscado (chave) e a função retorna a posição desse elemento.

As chaves dos elementos não estão em ordem crescente;

Se o elemento não existir retorna -1;

int buscaSequenciaLinear( LISTA l, TIPOCHAVE ch ){

int i = 0;

while( i < l->nroElemento ) {

if( ch ==l->A[i].chave) {

return i;

else i++;

}

return -1; // Se saiu do laço

}

Nesse algoritmo são feitos 2 testes. Iremos otimizar essas comparações.

Busca por elementos ( Sentinela )

Criação de um elemento extra( um registro) adicionado a lista para auxiliar alguma operação;

Será inserido no final da lista( após o último elemento válido) durante as buscas;

Conterá a chave do elemento buscado.

cod.:

int bucaSentinela( LISTA*l , TIPOCHAVE ch){

int i=0;

l->A[ l->nroElem] = ch;

while( l->A[i].chave != ch) i++; // Temos apenas um teste

if( i == l->nroElem) return -1;

else return i;

}

Agora qual o problema dessa implementação ?

Se a lista já estiver cheia como podemos inserir a sentinela ? Temos criar um lista nova no qual MAX é acrescentado em um elemento.

Um registro a mais para garantir que haverá espaço para a sentinela.

Modelagem

#define MAX 50

typedef int TIPOCHAVE;

typedef struct {

TIPOCHAVE chave;

// outros campos;

} REGISTRO;

typedef struct{

REGISTRO[ MAX +1];

int nroElem;

} LISTA;

Necessitamos que os elementos estejam ordenados.

A função seguirá a lógica de insertion sort.

Inserção de elemento em lista ordenada

bool inserirElemOrd( LISTA*l, REGISTRO reg) {

if( l->nroElem >= MAX) return false;

int pos = l->nroElem;

while( pos > 0 && l->A[pos-1].chave > reg.chave ){

l->A[pos] = l->A[pos-1];

pos--;

}

l->A[pos] = reg;

l->nroElem ++;

}

Busca binária

Com ordenação dos elemento pela chave:

- Busca ficou mais eficiente ( busca binária ).

- Não precisamos da sentinela.

cod.:

int buscaBinaria( LISTA*l , TYPECHAVE ch){

int esq, dir , meio;

esq = 0;

dir = l-> nroElem -1;

while( esq<=dir){

meio = ( ( esq + dir ) / 2);

if( l->A[maio].chave == ch) return meio;

else{ if( l->A[meio].chave < ch) esq = meio+1;

else dir = meio-1;

}

return -1;

}

bool excluirElemLista( TIPOCHAVE ch, LISTA*l) { // o tipo de chave na realidade o valor.

int pos, j;

pos = buscaSequenciaLinear( l, ch );

if( pos == -1) return false;

for( j = pos; j< l->nroElem - 1 ; j++) l->[j] = l->[j+1]; // etapa mais custosa na exclusão o que não reduz muita a complexidade do problema.

l->nroElem --;

return true;

}

Concluímos que as funções de inserção e exclusão são custosas já que temos de deslocar vários ou todos os elementos.

fonte: https://youtu.be/iBoWPFDQC_I?list=PLxI8Can9yAHf8k8LrUePyj0y3lLpigGcl

Page 5

Lista Ligada ( implementação estática )

Estrutura em que os elementos estão espalhados na memória possuindo alguma forma de indicar o próximo elemento.

Então qual a diferença da lista linear sequencial e lista ligada ? Ter de ficar deslocando elemento era algo que na lista sequencial tornava nosso código mais custoso durante a inserção e remoção. Só que a lista ligada não há essa necessidade. Ainda trata-se de uma estrutura linear ( cada elemento possui um sucessor e predecessor ).

A ordem lógica, vista pelo usuário, não é a mesma ordem física dos elementos na memória principal.

Cada elemento tem de indicar quem é seu sucessor.

[ 5 ] [ 9] [ 7 ] [ 8] [ 0 ]

3 -1 4 1 2

Analisando:

O primeiro elemento 5 aponta para seu próximo que 8 ( index 3 ).

O segundo elemento 9 não aponta para nenhum elemento, ou seja, não tem sucessor.

O terceiro elemento 7 aponta para o seu próximo elemento 0 ( index 4 ).

O quarto elemento 8 aponta para o seu próximo elemento 9 ( index 1 ).

O quinto elemento 0 aponta para o seu próximo elemento 7 ( index 2).

Este index aponta uma chave.

Temos um arranjo de elementos.

Cada elemento indica seu sucessor.

Como excluir o elemento 8.

[ 5 ] [ 9] [ 7 ] [ 0 ]

1 -1 4 2

Agora o antecessor de 8 aponta para o index 1.

Ideia geral

Precisamos saber onde está o primeiro elemento

Precisamos saber quais elementos estão disponíveis.

E onde eles estão.

Modelagem

cod.:

#define MAX 50 // definindo constante

#define INVALIDO -1 // definindo constante

typedef int TIPOCHAVE;

typedef struct{

TIPOCHAVE chave;

//

}REGISTRO;

typedef struct{ // Agora temos um arranjo de elemento com uma adição de onde está o próximo elemento ;

REGISTRO reg;

int prox;

}ELEMENTO;

typedef struct{

ELEMENTO A[ MAX ];

int inicio;

int dispo;

} LISTA;