Lista lineares e encadeadas

Categories: Trabalhos

0

SISTEMA DE ENSINO PRESENCIAL CONECTADO TECNOLOGIA EM ANALISE E DESENVOLVIMENTO DE SISTEMAS PAULO HENRIQUE KUNDE ATIVIDADE PORTFOLIO PRODUÇÃO TEXTUAL INTERDISCIPLINAR santa cruz do SUI 2011 ATIVIDADE PORTFOLI PRODUÇÃO TEXTUAL Trabalho de Produçã terceiro semestre do PACE 1 ar 8 to view nut*ge – Individual ividual Individual do ologia em Análise e Desenvolvimento de Sistemas da Universidade Norte do Paraná – UNOPAR prof. Marcio Chiaveli Merris Mozer Roberto Nishimura Simone Tanaka santa cruz do sul 2011 SUMARIO 1 INTRODUÇAO. .. S 2. 2 FILO… ENCADEADA…. … 3 2 LISTAS LINEARES………. . 1 ….. 5 2. 3 ALOCAÇAO SIMPLESMEN E … 6 24 ALOCAÇÃO DUPLAMENTE 6 3 PROPRIEDADES ACID DE UM BANCO DE 3 1 INTRODUÇÃO Trabalho de produção textual sobre listas lineares e seus conceitos de fila FIFO e FILO e seus métodos de manipulação, definição de conceitos de alocação de listas simplesmente e duplamente encadeadas, definição das propriedades ACID de uma transação diagrama de classe. m Banco de Dados, vantagens da Orientação a Objetos, da utilização de polimorfismo e sua representação no 4 2 LISTAS LINEARES Listas lineares são estruturas de dados e tamanho variável que correspondem a uma sequência ordenada ou desordenada de elementos, são classificadas de acordo com o tipo de armazenamento em listas lineares sequenciais e listas lineares e encadeadas. Permitem representar um conjunto de dados afins de forma a preservar a relação de ordem linear de seus elementos.

Esses elementos, denominados nós, podem conter, cada um, um dado primitivo ou um dado composto, consistem de um conjunto de n > 0 nós XI ,X2, ….. Xn, organizados estruturalmente de forma a refletir as posições relativas dos mesmos: se n > 0, então XI é o primeiro nó; para < k < n, o nó Xk é precedido pelo nó Xk-l e seguido do Xk+l; e Xn é o último nó. Quando diz-se que a lista é vazia. Como tipos mais comuns de listas lineares temos as filas, pilhas e deques, nas quais a principal diferença à a forma pela qual as informações são acessadas.

As listas lineares sequenciais utilizam alocação sequencial, neste tipo de alocação deve-se estabelecer previamente o tamanho definitivo da lista, nas linguagens de programação a maneira mais utilizada para implementar este tipo de lista é o vetor. Os espaços da lista são ocupados sequencialmente na m ara implementar este tipo de lista é o vetor. Os espaços da lista são ocupados sequencialmente na memória. A identificação dos registros ocupados é gerenciado pela linguagem ou pelo próprio programador.

As listas lineares encadeadas utllizam alocação dinâmica de memória, este tipo de alocação é ideal quando não pode-se definir previamente o tamanho da lista, neste caso são utilizados registros distribuídos aleatoriamente na memória e interligados através de ponteiro para o endereço do próximo elemento de forma a organizar-se como um conjunto linear. As operações mais frequentes em listas lineares são: – Acessar o k-ésimo elemento. Inserir nodo antes ou após o k- ésimo elemento. Retirar o k-ésimo elemento. Contar o numero de nodos. pesqusar por um valor. Combinar duas ou mais listas, de forma ordenada ou não. Dividir uma lista em duas ou mais, de acordo com um critério prédefinido. Classificar os elementos de uma lista segundo algum critério prédefinido. 2. 1 FIFO FIFO é um acrônimo para “First In, First Out’ ou seja, primeiro a entrar, primeiro a sair, mais comumente conhecido e chamado de fila. São muito usadas em programação para implementar filas de espera , na prática pode ser exemplificado com a fila de processos do sistema operacional ou uma fila de impressão, na vida real exemplificamos com uma fila de clientes para serem atendidos em um caixa de banco, em ambos os casos o atendimento é feito conforme a ordem de chegada.

Em uma fila só podemos inserir elementos no final e retirar do início da fila. 2. 2 FILO FILO que significa “First In Last Out”, ou seja o primeiro a entrar é o último a sair co hecido como pilha, “First In, Last Out”, ou seja o primeiro a entrar é o último a sair omumente conhecido como pilha, que é uma lista linear onde todas as operações são feitas por um único extremo denominado de topo. ? uma estrutura amplamente utilizada na informática, como exemplo podemos citar os valores de retorno de uma função recursiva que ficam armazenados em uma pilha para posteriormente após o final do procedimento processar estes dados resultantes, ca vida real podemos exemplificar com uma pilha de pratos onde pegamos o primeiro prato de cima, e ao colocarmos um prato de volta o colocamos novamente em cima da pilha. O processo de incluir um elemento é conhecido como mpilhamento, e de retirada de desempilhamento. 6 2. 3 ALOCAÇÃO SIMPLESMENTE ENCADEADA Neste tipo de lista cada nó possui uma referência apenas para o próximo nó.

O endereço de memória não é determinado matematicamente, e sim por uma ponteiro. Cada nó e composto por uma variável “dado” que contêm a informação, e uma variável “próximo” (tipo ponteiro) utilizado para fazer referencia ao próximo nó desta lista. Como vantagem este tipo de lista ocupa menos espaço na memória em relação ao modelo duplamente encadeado. Exemplo de uma lista simplesmente encadeada aberta: Onde o último nó ão aponta para nenhum outro, determinando o final da lista. Exemplo de uma lista simplesmente encadeada fechada: Onde o último nó faz referência ao primeiro, fechando a cadeia de nós. . 4 ALOCAÇÃO DUPLAMENTE ENCADEADA Neste tipo de lista cada nó aponta para o próximo nó e para o nó anterior,possibilitando que a lista seja percorrida nos dois sentidos . Cada nó é composto por uma variável “dado” que contêm a informação, u PAGF percorrida nos dois sentidos . Cada nó é composto por uma variável “dado” que contêm a informação, uma variável “próximo” (tipo ponteiro) utilizada para fazer referencia ao róxmo nó desta lista e uma variável “anterior’ (tipo ponteiro) utilizada para fazer referencia ao nó anterior desta lista.

Sendo assim, podemos a partir de um ponteiro para um nodo qualquer da lista, alcançar as suas duas extremidades, onde podemos nos deslocar tanto do início para o final, quanto do final para o início da lista , isto representa uma 7 vantagem em relação a alocação simplesmente encadeada. Exemplo de uma lista duplamente encadeada. 8 3 PROPRIEDADES ACID DE UM BANCO DE DADOS propriedades ACID de um banco de dados são as quatro propriedades undamentais de um SG3D(Sistema Gerenciador de Banco de Dados) e se referem a Atomicidade, Consistência, Isolamento e Durabilidade.

Atomicidade – na execução de uma operação é um tudo ou nada: se houver alguma falha durante a execução, a transação é desfeita. Segundo RAMEZ Elsmari e NAVATHE Shamkant “uma transação é uma unidade atômica de processamento; ou ela será executada em sua totalidade ou não será de modo algum”. O subsistema de restauração de transações do SGBD é o responsável pela atomicidade. Consistência – imagine que seja tirada uma fotografia dos dados e um banco de dados. Este é o estado do BD. Após a fotografia, é feita uma transação neste BD e retira-se uma nova foto.

Se na primeira o BD estava consistente, então na segunda ele tem que estar também. Citando a bibliografia, “uma transação será preservadora de consistência se a sua execução completa fizer o banco de dados passar de um estado consistente para consistência se a sua execução completa fizer o banco de dados passar de um estado consistente para outro. Um estado do banco de dados é a coleção de todos os itens de dados armazenados no banco de dados em determinado momento. A responsabilidade aqui é dupla, sendo tanto do programador quanto do módulo do SGBD que garante as restrições de integridade.

Isolamento – é o cada um por si: “uma transaçao deve ser executada como se estivesse isolada das demais. Isto é, a execução de uma transação não deve sofrer interferência de quaisquer outras transações concorrentes. (… ) É imposto pelo subsistema de controle de concorrência do SGBD. ” O chamado nível de isolamento verdadeiro (nível 3) não permite atualizações perdidas, leitura de sujeira nem leituras repetíveis. Durabilidade se fez, está feito – “as mudanças aplicadas ao banco de dados por uma transação efetivada devem persistir no banco de dados.

Essas mudanças não devem ser perdidas em razão de uma falha”. g 4 VANTAGEM DE SE UTILIZAR ORIENTAÇAO A OBJETOS O paradigma da Orientação a Objetos no desenvolvimento d uma sistema possui várias vantagens como: O uso de objetos na modelagem torna mais fácil descrever as estruturas e o comportamento existente no mundo real fazendo com que problemas sejam mais facilmente identificados. Possibilita a utilização de herança, onde um objeto pode herdar ropriedades e métodos de outro objeto, ou de vários objetos.

O encapsulamento do conhecimento em componentes isola o comportamento em partes, o que permite que as mudanças nos requisitos possam ser isoladas em cada componente sem afetar o sistema como um todo. O uso de classes e objetos facilita a Integraça componente sem afetar o sistema como um todo. O uso de classes e objetos facilita a integração das fases do processo de desenvolvimento, já que o mesmo paradigma é conduzido da análise à construção. O encapsulamento favorece o teste dos sistemas de software, que pode ser isolado para cada omponente resultando na melhora da qualidade do sistema.

A reutilização que a orientação a objetos proporciona redução de custos e dos prazos no desenvolvimento de software, possibilitando que o mesmo componente seja usado em vários projetos. 10 5 POLIMORFISMO NO DIAGRAMA DE CLASSE polimorfismo(muitas formas) é o principio pelo qual duas ou mais classes derivadas de uma mesma superclasse podem invocar métodos que têm a mesma identificação (assinatura) mas comportamentos distintos, especializados para cada classe derivada, usando para tanto uma referência a um objeto do tipo da superclasse. ?? necessário que os métodos tenham exatamente a mesma identificação, sendo utilizado o mecanismo de redefinição de métodos. Esse mecanismo de redefinição não deve ser confundido com o mecanismo de sobrecarga de métodos. Como principais vantagens temos a clareza e manutenção do código, aplicações flexíveis que possibilitem a criação de plugins, as boas práticas de programação baseiam se padrões Template Method e outros. Podemos exemplificar com o exemplo da classe Pessoa e suas classes filhas, as classes Física e Jur[dica. e projetos de software que envolvem o polimorfismo, omo os padrões Abstract Factory, Composite, Observer, Strategy, Neste caso ambas as classes Jurídico e Fislca implementam e sobrescrevem o método “validarDocumento” implementado na classe pai, que deve implementam e sobrescrevem o método “validarDocumento” implementado na classe pai, que deve ser redefinido em cada classe filha de forma a atender e executar a validação para cada tipo de dados, cpf ou cnpj. 1 6 CONCLUSÃO Ao apresentar os conceitos em relação a listas lineares e suas aplicações em listas e filas, vemos como atividades cotidianas se apresentam no contexto da informática, da manipulação de ados e programação, sendo sua compreensão fundamental para desenvolvimento de atividades tanto cotidianas quanto em projetos de software.

O entendimento das propriedades de um SGBD é fundamental para a segurança, disponibilidade e acessibilidade dos dados em um banco de dados, observando as propriedades ACID temos uma fundamento básico e essencial para definir e qualificar este SGBD , auxiliando na definição de qual é a melhor solução para uma determinada aplicação. O polimorfismo possibilita agilidade no desenvolvimento de sistemas, com a sobreposição de métodos diminui- e a quantidade de código e aumenta-se a segurança de operações,permitindo que referências de tipos de classes mais abstratas representem o comportamento das classes concretas que referenciam.

Assim, é possível tratar vários tipos de maneira homogênea através da interface do tipo mais abstrato. 12 REFERÊNCIA BIBLIOGRÁFICA http:mmvw. icrnc. usp. br,’ -sce 1 82/1circ. html. http://pt. scribd. com/doc/52762377/4/Lista -Duplamente-Encadeada. Sistemas de Bancos de Dados, de RAMEZ,Elsmari e SHAMKANT, Navathe, 4a edição. Desevolvimento orientado a Objetos – ALMEIDA E SILVA, Flavio – Unipar Virtual. PAGF8rl(F8

Trivinos

0

Questões preliminares básicas Situa necessidade de disciplina intelectual em relação à escolha de um pólo teórico- metodológico, entendendo como indisciplina

Read More

Estudante

0

ASSOCIAÇAO DE ENSINO JULIAN CARVALHO FACULDADE SANTA BÁRBARA – FAESB CURSO DE ADMINISTRAÇAO MICHELE DE CÁSSIA MORAES ET AL. ANÁLISE

Read More