Estrutura de Dados: Univesp

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).

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"); }          

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

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

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;