Drf AFW QFWE

WEGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGAFGAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA1. Conceitos fundamentais

1.1.Introdução

O curso de Estruturas de Dados discute diversas técnicas de programação, apresentando as estruturas de dados básicas utilizadas no desenvolvimento de software. O curso também introduz os conceitos básicos da linguagem de programação C, que é utilizada para a implementação das estruturas de dados apresentadas. A linguagem de programação C tem sido amplamente utilizada na elaboração de programas e sistemas nas diversas áreas em que a informática atua, e seu aprendizado tornou-se indispensável tanto para programadores profissionais como para programadores que atuam na área de pesquisa.

O conhecimento de linguagens de programação por si só não capacita programadores – é

necessário saber usá-las de maneira eficiente. O projeto de um programa engloba a fase de identificação das propriedades dos dados e características funcionais. Uma representação adequada dos dados, tendo em vista as funcionalidades que devem ser atendidas, constitui uma etapa fundamental para a obtenção de programas eficientes e confiáveis.

A linguagem C, assim como as linguagens Fortran e Pascal, são ditas linguagens

“convencionais”, projetadas a partir dos elementos fundamentais da arquitetura de von

Neuman, que serve como base para praticamente todos os computadores em uso. Para

programar em uma linguagem convencional, precisamos de alguma maneira especificar as áreas de memória em que os dados com que queremos trabalhar estão armazenados e, freqüentemente, considerar os endereços de memória em que os dados se situam, o que faz com que o processo de programação envolva detalhes adicionais, que podem ser ignorados quando se programa em uma linguagem como Scheme. Em compensação, temos um maior controle da máquina quando utilizamos uma linguagem convencional, e podemos fazer programas melhores, ou seja, menores e mais rápidos.

A linguagem C provê as construções fundamentais de fluxo de controle necessárias para

programas bem estruturados: agrupamentos de comandos; tomadas de decisão (if-else);

laços com testes de encerramento no início (while, for) ou no fim (do-while); e seleção de

um dentre um conjunto de possíveis casos (switch). C oferece ainda acesso a apontadores e a habilidade de fazer aritmética com endereços. Por outro lado, a linguagem C não provê operações para manipular diretamente objetos compostos, tais como cadeias de caracteres, nem facilidades de entrada e saída: não há comandos READ e WRITE. Todos esses mecanismos devem ser fornecidos por funções explicitamente chamadas. Embora a falta de algumas dessas facilidades possa parecer uma deficiência grave (deve-se, por exemplo, chamar uma função para comparar duas cadeias de caracteres), a manutenção da linguagem em termos modestos tem trazido benefícios reais. C é uma linguagem relativamente pequena e, no entanto, tornou-se altamente poderosa e eficiente.

1.2.Modelo de um computador

Existem diversos tipos de computadores. Embora não seja nosso objetivo estudar

hardware, identificamos, nesta seção, os elementos essenciais de um computador. O conhecimento da existência destes elementos nos ajudará a compreender como um

programa de computador funciona.

O canal de comunicação (conhecido como BUS) representa o meio para a transferência de dados entre os diversos componentes. Na memória principal são armazenados os programas e os dados no computador. Ela tem acesso randômico, o que significa que podemos endereçar (isto é, acessar) diretamente qualquer posição da memória. Esta memória não é permanente e, para um programa, os dados são armazenados enquanto o programa está sendo executado. Em geral, após o término do programa, a área ocupada na memória fica disponível para ser usada por outras aplicações. A área de armazenamento secundário é, em geral, representada por um disco (disco rígido, disquete, etc.). Esta memória secundária tem a vantagem de ser permanente. Os dados armazenados em disco permanecem válidos após o término dos programas. Esta memória tem um custo mais baixo do que a memória principal, porém o acesso aos dados é bem mais lento. Por fim, encontram-se os dispositivos de entrada e saída. Os dispositivos de entrada (por exemplo, teclado, mouse) permitem passarmos dados para um programa, enquanto os dispositivos de saída permitem que um programa exporte seus resultados, por exemplo em forma textual ou gráfica usando monitores ou impressoras.

Armazenamento de dados e programas na memória.A memória do computador é dividida em unidades de armazenamento chamadas bytes.

Cada byte é composto por 8 bits, que podem armazenar os valores zero ou um. Nada além de zeros e uns pode ser armazenado na memória do computador. Por esta razão, todas as informações (programas, textos, imagens, etc.) são armazenadas usando uma codificação numérica na forma binária. Na representação binária, os números são representados por uma seqüência de zeros e uns (no nosso dia a dia, usamos a representação decimal, uma vez que trabalhamos com 10 algarismos). Por exemplo, o número decimal 5 é representado por 101, pois 1*22 + 0*21 + 1*20 é igual a 5 (da mesma forma que, na base decimal 456=4*102 + 5*101 + 6*100). Cada posição da memória (byte) tem um endereço único. Não é possível endereçar diretamente um bit.

Se só podemos armazenar números na memória do computador, como fazemos para armazenar um texto (um documento ou uma mensagem)? Para ser possível armazenar uma seqüência de caracteres, que representa o texto, atribui-se a cada caractere um código numérico (por exemplo, pode-se associar ao caractere 'A' o código 65, ao caractere 'B' o código 66, e assim por diante). Se todos os caracteres tiverem códigos associados (inclusive os caracteres de pontuação e de formatação), podemos armazenar um texto na memória do computador como uma seqüência de códigos numéricos. Um computador só pode executar programas em linguagens de máquina. Cada programa executável é uma seqüência de instruções que o processador central interpreta, executando as operações correspondentes. Esta seqüência de instruções também é representada