[Apostila]Estrutura de Dados - Waldemar Celes e José Lucas Rangel

Apostila de Estruturas de Dados

Profs. Waldemar Celes e Jos Lucas Rangel PUC-RIO - Curso de Engenharia - 2002

ApresentaoA disciplina de Estruturas de Dados (ED) est sendo ministrada em sua nova verso desde o segundo semestre de 1998. Trata-se da segunda disciplina de informtica oferecida no curso de Engenharia da PUC-Rio. Na primeira disciplina, Introduo Cincia da Computao (ICC), so apresentados os conceitos fundamentais de programao. ICC, em sua verso mais nova, utiliza a linguagem Scheme, de fcil aprendizado, o que permite a discusso de diversos conceitos de programao num curso introdutrio. Isso acontece porque Scheme, como a linguagem LISP da qual descende, uma linguagem funcional, baseada em conceitos familiares aos alunos, como a definio de funes e sua aplicao em expresses que devem ser avaliadas. O enfoque do curso de Estruturas de Dados diferente. Discutem-se tcnicas de programao e estruturao de dados para o desenvolvimento de programas eficientes. Adota-se a linguagem de programao C. Apesar de reconhecermos as dificuldades na aprendizagem da linguagem C, optamos por sua utilizao neste curso simplesmente porque C a linguagem bsica da programao do UNIX, da Internet, do Windows, do Linux. Alm de C, usam-se nestes sistemas e em aplicaes desenvolvidas para eles linguagens derivadas de C, como C++ e Java. Um ponto adicional a favor da escolha de C que o estudo de vrias disciplinas posteriores a ED ser facilitado se os alunos j puderem programar com desenvoltura nessa linguagem. Este curso foi idealizado e montado pelo Prof. Jos Lucas Rangel. Neste semestre, estamos reformulando alguns tpicos, criando outros e alterando a ordem de apresentao. Esta apostila foi reescrita tendo como base a apostila do Prof. Rangel, utilizada nos semestres anteriores. O curso est dividido em trs partes. A Parte I apresenta os conceitos fundamentais da linguagem C e discute formas simples de estruturao de dados; a Parte II discute as estruturas de listas e rvores, e suas aplicaes; e a Parte III discute algoritmos e estruturas de dados para ordenao e busca. A apostila apresenta todos os tpicos que sero discutidos em sala de aula, mas recomendamos fortemente que outras fontes (livros, notas de aula, etc.) sejam consultadas. Rio de Janeiro, 19 de fevereiro de 2002 Waldemar Celes

ndice1. Conceitos fundamentais........................................................................ 1-11.1. Introduo ........................................................................................................... 1-1 1.2. Modelo de um computador .................................................................................. 1-1 1.3. Interpretao versus Compilao ....................................................................... 1-3 1.4. Exemplo de cdigo em C .................................................................................... 1-4 1.5. Compilao de programas em C.......................................................................... 1-6 1.6. Ciclo de desenvolvimento .................................................................................... 1-8

2. Expresses ............................................................................................. 2-12.1. Variveis............................................................................................................... 2-1 2.2. Operadores .......................................................................................................... 2-4 2.3. Entrada e sada bsicas....................................................................................... 2-8

3. Controle de fluxo.................................................................................... 3-13.1. Decises com if .................................................................................................... 3-1 3.2. Construes com laos ........................................................................................ 3-4 3.3. Seleo ................................................................................................................ 3-8

4. Funes .................................................................................................. 4-14.1. Definio de funes............................................................................................ 4-1 4.2. Pilha de execuo ................................................................................................ 4-3 4.3. Ponteiro de variveis............................................................................................ 4-6 4.4. Recursividade....................................................................................................... 4-10 4.5. Variveis estticas dentro de funes ................................................................ 4-11 4.6. Pr-processador e macros .................................................................................. 4-12

5. Vetores e alocao dinmica ................................................................ 5-15.1. Vetores ................................................................................................................. 5-1 5.2. Alocao dinmica ............................................................................................... 5-3

6. Cadeia de caracteres ............................................................................. 6-16.1. Caracteres............................................................................................................ 6-1 6.2. Cadeia de caracteres (strings) ............................................................................. 6-3 6.3. Vetor de cadeia de caracteres ............................................................................. 6-11

7. Tipos estruturados................................................................................. 7-17.1. O tipo estrutura..................................................................................................... 7-1 7.2. Definio de "novos" tipos.................................................................................... 7-4 7.3. Vetores de estruturas ........................................................................................... 7-6 7.4. Vetores de ponteiros para estruturas ................................................................... 7-7 7.5. Tipo unio............................................................................................................. 7-9 7.6. Tipo enumerao ................................................................................................ 7-10

8. Matrizes ................................................................................................... 8-18.1. Alocao esttica versus dinmica ...................................................................... 8-1 8.2. Vetores bidimensionais Matrizes....................................................................... 8-2 8.3. Matrizes dinmicas............................................................................................... 8-4 8.4. Representao de matrizes ................................................................................. 8-6 8.5. Representao de matrizes simtricas ................................................................ 8-9

9. Tipos Abstratos de Dados ..................................................................... 9-1

9.1. Mdulos e Compilao em Separado .................................................................. 9-1 9.2. Tipo Abstrato de Dados........................................................................................ 9-3

10. Listas Encadeadas ............................................................................... 10-110.1. Lista encadeada ................................................................................................. 10-2 10.2. Implementaes recursivas ............................................................................... 10-9 10.3. Listas genricas ................................................................................................. 10-10 10.4. Listas circulares.................................................................................................. 10-15 10.5. Listas duplamente encadeadas.......................................................................... 10-16

11. Pilhas..................................................................................................... 10-111.1. Interface do tipo pilha ......................................................................................... 10-2 11.2. Implementao de pilha com vetor .................................................................... 10-2 11.3. Implementao de pilha com lista ...................................................................... 10-3 11.4. Exemplo de uso: calculadora ps-fixada............................................................ 10-5

12. Filas ....................................................................................................... 11-112.1. Interface do tipo fila ............................................................................................ 11-1 12.2. Implementao de fila com vetor ....................................................................... 11-2 12.3. Implementao de fila com lista ......................................................................... 11-5 12.4. Fila dupla............................................................................................................ 11-7 12.5. Implementao de fila dupla com lista ............................................................... 11-8

13. rvores.................................................................................................. 12-113.1. rvores binrias ................................................................................................. 12-2 13.2. rvores genricas .............................................................................................. 12-9

14. Arquivos ................................................................................................ 13-114.1. Funes para abrir e fechar arquivos ................................................................ 13-2 14.2. Arquivos em modo texto..................................................................................... 13-3 14.3. Estruturao de dados em arquivos textos........................................................ 13-4 14.4. Arquivos em modo binrio.................................................................................. 13-11

15. Ordenao ............................................................................................ 14-115.1. Ordenao bolha................................................................................................ 14-1 15.2. Ordenao Rpida ............................................................................................. 14-9

16. Busca .................................................................................................... 16-116.1. Busca em Vetor.................................................................................................. 16-1 16.2. rvore binria de busca ..................................................................................... 16-7

17. Tabelas de disperso........................................................................... 17-117.1. Idia central........................................................................................................ 17-2 17.2. Funo de disperso.......................................................................................... 17-3 17.3. Tratamento de coliso........................................................................................ 17-4 17.4. Exemplo: Nmero de Ocorrncias de Palavras ................................................. 17-8 17.5. Uso de callbacks ................................................................................................ 17-13

1. Conceitos fundamentaisW. Celes e J. L. Rangel

1.1. IntroduoO curso de Estruturas de Dados discute diversas tcnicas de programao, apresentando as estruturas de dados bsicas utilizadas no desenvolvimento de software. O curso tambm introduz os conceitos bsicos da linguagem de programao C, que utilizada para a implementao das estruturas de dados apresentadas. A linguagem de programao C tem sido amplamente utilizada na elaborao de programas e sistemas nas diversas reas em que a informtica atua, e seu aprendizado tornou-se indispensvel tanto para programadores profissionais como para programadores que atuam na rea de pesquisa. O conhecimento de linguagens de programao por si s no capacita programadores necessrio saber us-las de maneira eficiente. O projeto de um programa engloba a fase de identificao das propriedades dos dados e caractersticas funcionais. Uma representao adequada dos dados, tendo em vista as funcionalidades que devem ser atendidas, constitui uma etapa fundamental para a obteno de programas eficientes e confiveis. A linguagem C, assim como as linguagens Fortran e Pascal, so 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 memria em que os dados com que queremos trabalhar esto armazenados e, freqentemente, considerar os endereos de memria em que os dados se situam, o que faz com que o processo de programao envolva detalhes adicionais, que podem ser ignorados quando se programa em uma linguagem como Scheme. Em compensao, temos um maior controle da mquina quando utilizamos uma linguagem convencional, e podemos fazer programas melhores, ou seja, menores e mais rpidos. A linguagem C prov as construes fundamentais de fluxo de controle necessrias para programas bem estruturados: agrupamentos de comandos; tomadas de deciso (if-else); laos com testes de encerramento no incio (while, for) ou no fim (do-while); e seleo de um dentre um conjunto de possveis casos (switch). C oferece ainda acesso a apontadores e a habilidade de fazer aritmtica com endereos. Por outro lado, a linguagem C no prov operaes para manipular diretamente objetos compostos, tais como cadeias de caracteres, nem facilidades de entrada e sada: no h comandos READ e WRITE. Todos esses mecanismos devem ser fornecidos por funes explicitamente chamadas. Embora a falta de algumas dessas facilidades possa parecer uma deficincia grave (deve-se, por exemplo, chamar uma funo para comparar duas cadeias de caracteres), a manuteno da linguagem em termos modestos tem trazido benefcios reais. C uma linguagem relativamente pequena e, no entanto, tornou-se altamente poderosa e eficiente.

1.2. Modelo de um computadorExistem diversos tipos de computadores. Embora no seja nosso objetivo estudar hardware, identificamos, nesta seo, os elementos essenciais de um computador. OEstruturas de Dados PUC-Rio 1-1

conhecimento da existncia destes elementos nos ajudar a compreender como um programa de computador funciona.Canal de comunicao (BUS)

CPUCentral de processamento Armazenamento secundrio Dispositivos de entrada/sada

Memria

Figura 1.1: Elementos bsicos de um computador tpico.

A Figura 1.1 identifica os elementos bsicos de um computador tpico. O canal de comunicao (conhecido como BUS) representa o meio para a transferncia de dados entre os diversos componentes. Na memria principal so armazenados os programas e os dados no computador. Ela tem acesso randmico, o que significa que podemos enderear (isto , acessar) diretamente qualquer posio da memria. Esta memria no permanente e, para um programa, os dados so armazenados enquanto o programa est sendo executado. Em geral, aps o trmino do programa, a rea ocupada na memria fica disponvel para ser usada por outras aplicaes. A rea de armazenamento secundrio , em geral, representada por um disco (disco rgido, disquete, etc.). Esta memria secundria tem a vantagem de ser permanente. Os dados armazenados em disco permanecem vlidos aps o trmino dos programas. Esta memria tem um custo mais baixo do que a memria principal, porm o acesso aos dados bem mais lento. Por fim, encontram-se os dispositivos de entrada e sada. Os dispositivos de entrada (por exemplo, teclado, mouse) permitem passarmos dados para um programa, enquanto os dispositivos de sada permitem que um programa exporte seus resultados, por exemplo em forma textual ou grfica usando monitores ou impressoras. Armazenamento de dados e programas na memria A memria do computador dividida em unidades de armazenamento chamadas bytes. Cada byte composto por 8 bits, que podem armazenar os valores zero ou um. Nada alm de zeros e uns pode ser armazenado na memria do computador. Por esta razo, todas as informaes (programas, textos, imagens, etc.) so armazenadas usando uma codificao numrica na forma binria. Na representao binria, os nmeros so representados por uma seqncia de zeros e uns (no nosso dia a dia, usamos a representao decimal, uma vez que trabalhamos com 10 algarismos). Por exemplo, o nmero 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 posio da memria (byte) tem um endereo nico. No possvel enderear diretamente um bit. Se s podemos armazenar nmeros na memria do computador, como fazemos para armazenar um texto (um documento ou uma mensagem)? Para ser possvel armazenar uma seqncia de caracteres, que representa o texto, atribui-se a cada caractere um cdigoEstruturas de Dados PUC-Rio 1-2

numrico (por exemplo, pode-se associar ao caractere 'A' o cdigo 65, ao caractere 'B' o cdigo 66, e assim por diante). Se todos os caracteres tiverem cdigos associados (inclusive os caracteres de pontuao e de formatao), podemos armazenar um texto na memria do computador como uma seqncia de cdigos numricos. Um computador s pode executar programas em linguagens de mquina. Cada programa executvel uma seqncia de instrues que o processador central interpreta, executando as operaes correspondentes. Esta seqncia de instrues tambm representada como uma seqncia de cdigos numricos. Os programas ficam armazenados em disco e, para serem executados pelo computador, devem ser carregados (transferidos) para a memria principal. Uma vez na memria, o computador executa a seqncia de operaes correspondente.

1.3. Interpretao versus CompilaoUma diferena importante entre as linguagens C e Scheme que, via de regra, elas so implementadas de forma bastante diferente. Normalmente, Scheme interpretada e C compilada. Para entender a diferena entre essas duas formas de implementao, necessrio lembrar que os computadores s executam realmente programas em sua linguagem de mquina, que especfica para cada modelo (ou famlia de modelos) de computador. Ou seja, em qualquer computador, programas em C ou em Scheme no podem ser executados em sua forma original; apenas programas na linguagem de mquina ( qual vamos nos referir como M) podem ser efetivamente executados. No caso da interpretao de Scheme, um programa interpretador (IM), escrito em M, l o programa PS escrito em Scheme e simula cada uma de suas instrues, modificando os dados do programa da forma apropriada. No caso da compilao da linguagem C, um programa compilador (CM), escrito em M, l o programa PC, escrito em C, e traduz cada uma de suas instrues para M, escrevendo um programa PM cujo efeito o desejado. Como conseqncia deste processo, PM, por ser um programa escrito em M, pode ser executado em qualquer mquina com a mesma linguagem de mquina M, mesmo que esta mquina no possua um compilador. Na prtica, o programa fonte e o programa objeto so armazenados em arquivos em disco, aos quais nos referimos como arquivo fonte e arquivo objeto. As duas figuras a seguir esquematizam as duas formas bsicas de implementao de linguagens de programao.Execuo PS Programa Fonte

IM Interpretador

Sada

Dados de Entrada

Figura 1.2: Execuo de programas com linguagem interpretada.

Estruturas de Dados PUC-Rio

1-3

Compilao PC Programa Fonte PM Programa Objeto

CM Compilador

Execuo Dados de Entrada PM Programa Objeto

Sada

Figura 1.3: Execuo de programas com linguagem compilada.

Devemos notar que, na Figura 1.2, o programa fonte um dado de entrada a mais para o interpretador. No caso da compilao, Figura 1.3, identificamos duas fases: na primeira, o programa objeto a sada do programa compilador e, na segunda, o programa objeto executado, recebendo os dados de entrada e gerando a sada correspondente. Observamos que, embora seja comum termos linguagens funcionais implementadas por interpretao e linguagens convencionais por compilao, h excees, no existindo nenhum impedimento conceitual para implementar qualquer linguagem por qualquer dos dois mtodos, ou at por uma combinao de ambos. O termo mquina usado acima intencionalmente vago. Por exemplo, computadores idnticos com sistemas operacionais diferentes devem ser considerados mquinas, ou plataformas, diferentes. Assim, um programa em C, que foi compilado em um PC com Windows, no dever ser executado em um PC com Linux, e vice-versa.

1.4. Exemplo de cdigo em CPara exemplificar cdigos escritos em C, consideremos um programa que tem a finalidade de converter valores de temperatura dados em Celsius para Fahrenheit. Este programa define uma funo principal que captura um valor de temperatura em Celsius, fornecido via teclado pelo usurio, e exibe como sada a temperatura correspondente em Fahrenheit. Para fazer a converso, utilizada uma funo auxiliar. O cdigo C deste programa exemplo mostrado abaixo./* Programa para converso de temperatura */ #include float converte (float c) { float f; f = 1.8*c + 32; return f; }


1-4

int main (void) { float t1; float t2; /* mostra mensagem para usuario */ printf("Digite a temperatura em Celsius: "); /* captura valor entrado via teclado */ scanf("%f",&t1); /* faz a conversao */ t2 = converte(t1); /* exibe resultado */ printf("A temperatura em Fahrenheit : %f\n", t2); return 0; }

Um programa em C, em geral, constitudo de diversas pequenas funes, que so independentes entre si no podemos, por exemplo, definir uma funo dentro de outra. Dois tipos de ambientes so caracterizados em um cdigo C. O ambiente global, externo s funes, e os ambientes locais, definidos pelas diversas funes (lembrando que os ambientes locais so independentes entre si). Podem-se inserir comentrios no cdigo fonte, iniciados com /* e finalizados com */, conforme ilustrado acima. Devemos notar tambm que comandos e declaraes em C so terminados pelo caractere ponto-e-vrgula (;). Um programa em C tem que, obrigatoriamente, conter a funo principal (main). A execuo de um programa comea pela funo principal (a funo main automaticamente chamada quando o programa carregado para a memria). As funes auxiliares so chamadas, direta ou indiretamente, a partir da funo principal. Em C, como nas demais linguagens convencionais, devemos reservar rea de memria para armazenar cada dado. Isto feito atravs da declarao de variveis, na qual informamos o tipo do dado que iremos armazenar naquela posio de memria. Assim, a declarao float t1;, do cdigo mostrado, reserva um espao de memria para armazenarmos um valor real (ponto flutuante float). Este espao de memria referenciado atravs do smbolo t1. Uma caracterstica fundamental da linguagem C diz respeito ao tempo de vida e visibilidade das variveis. Uma varivel (local) declarada dentro de uma funo "vive" enquanto esta funo est sendo executada, e nenhuma outra funo tem acesso direto a esta varivel. Outra caracterstica das variveis locais que devem sempre ser explicitamente inicializadas antes de seu uso, caso contrrio contero lixo, isto , valores indefinidos. Como alternativa, possvel definir variveis que sejam externas s funes, isto , variveis globais, que podem ser acessadas pelo nome por qualquer funo subseqenteEstruturas de Dados PUC-Rio 1-5

(so visveis em todas as funes que se seguem sua definio). Alm do mais, devido s variveis externas (ou globais) existirem permanentemente (pelo menos enquanto o programa estiver sendo executado), elas retm seus valores mesmo quando as funes que as acessam deixam de existir. Embora seja possvel definir variveis globais em qualquer parte do ambiente global (entre quaisquer funes), prtica comum defini-las no incio do arquivo-fonte. Como regra geral, por razes de clareza e estruturao adequada do cdigo, devemos evitar o uso indisciplinado de variveis globais e resolver os problemas fazendo uso de variveis locais sempre que possvel. No prximo captulo, discutiremos variveis com mais detalhe.

1.5. Compilao de programas em CPara desenvolvermos programas em uma linguagem como C, precisamos de, no mnimo, um editor e um compilador. Estes programas tm finalidades bem definidas: com o editor de textos, escrevemos os programas fontes, que so salvos em arquivos1; com o compilador, transformamos os programas fontes em programas objetos, em linguagem de mquina, para poderem ser executados. Os programas fontes so, em geral, armazenados em arquivos cujo nome tem a extenso .c. Os programas executveis possuem extenses que variam com o sistema operacional: no Windows, tm extenso .exe; no Unix (Linux), em geral, no tm extenso. Para exemplificar o ciclo de desenvolvimento de um programa simples, consideremos que o cdigo apresentado na seo anterior tenha sido salvo num arquivo com o nome prog.c. Devemos ento compilar o programa para gerarmos um executvel. Para ilustrar este processo, usaremos o compilador gcc. Na linha de comando do sistema operacional, fazemos:> gcc o prog prog.c

Se no houver erro de compilao no nosso cdigo, este comando gera o executvel com o nome prog (prog.exe, no Windows). Podemos ento executar o programa:> prog Digite a temperatura em Celsius: 10 A temperatura em Fahrenheit vale: 50.000000 >

Em itlico, representamos as mensagens do programa e, em negrito, exemplificamos um dado fornecido pelo usurio via teclado. Programas com vrios arquivos fontes Os programas reais so, naturalmente, maiores. Nestes casos, subdividimos o fonte do programa em vrios arquivos. Para exemplificar a criao de um programa com dois arquivos, vamos considerar que o programa para converso de unidades de temperatura1

Podemos utilizar qualquer editor de texto para escrever os programas fontes, exceto editores que incluem caracteres de formatao (como o Word do Windows, por exemplo).


1-6

apresentado anteriormente seja dividido em dois fontes: o arquivo converte.c e o arquivo principal.c. Teramos que criar dois arquivos, como ilustrado abaixo: Arquivo converte.c:/* Implementao do mdulo de converso */ float converte (float c) { float f; f = 1.8*c + 32; return f; }

Arquivo principal.c:/* Programa para converso de temperatura */ #include float converte (float c); int main (void) { float t1; float t2; /* mostra mensagem para usuario */ printf("Entre com temperatura em Celsius: "); /* captura valor entrado via teclado */ scanf("%f",&t1); /* faz a conversao */ t2 = converte(t1); /* exibe resultado */ printf("A temperatura em Fahrenheit vale: %f\n", t2); return 0; }

Embora o entendimento completo desta organizao de cdigo no fique claro agora, interessa-nos apenas mostrar como geramos um executvel de um programa com vrios arquivos fontes. Uma alternativa compilar tudo junto e gerar o executvel como anteriormente:> gcc o prog converte.c principal.c

No entanto, esta no a melhor estratgia, pois se alterarmos a implementao de um determinado mdulo no precisaramos re-compilar os outros. Uma forma mais eficiente compilarmos os mdulos separadamente e depois ligar os diversos mdulos objetos gerados para criar um executvel.> gcc c converte.c > gcc c principal.c > gcc o prog converte.o principal.o


1-7

A opo c do compilador gcc indica que no queremos criar um executvel, apenas gerar o arquivo objeto (com extenso .o ou .obj). Depois, invocamos gcc para fazer a ligao dos objetos, gerando o executvel.

1.6. Ciclo de desenvolvimentoProgramas como editores, compiladores e ligadores so s vezes chamados de ferramentas, usadas na Engenharia de Software. Exceto no caso de programas muito pequenos (como o caso de nosso exemplo), raro que um programa seja composto de um nico arquivo fonte. Normalmente, para facilitar o projeto, os programas so divididos em vrios arquivos. Como vimos, cada um desses arquivos pode ser compilado em separado, mas para sua execuo necessrio reunir os cdigos de todos eles, sem esquecer das bibliotecas necessrias, e esta a funo do ligador. A tarefa das bibliotecas permitir que funes de interesse geral estejam disponveis com facilidade. Nosso exemplo usa a biblioteca de entrada/sada padro do C, stdio, que oferece funes que permitem a captura de dados a partir do teclado e a sada de dados para a tela. Alm de bibliotecas preparadas pelo fornecedor do compilador, ou por outros fornecedores de software, podemos ter bibliotecas preparadas por um usurio qualquer, que pode empacotar funes com utilidades relacionadas em uma biblioteca e, dessa maneira, facilitar seu uso em outros programas. Em alguns casos, a funo do ligador executada pelo prprio compilador. Por exemplo, quando compilamos o primeiro programa prog.c, o ligador foi chamado automaticamente para reunir o cdigo do programa aos cdigos de scanf, printf e de outras funes necessrias execuo independente do programa. Verificao e Validao Outro ponto que deve ser observado que os programas podem conter (e, em geral, contm) erros, que precisam ser identificados e corrigidos. Quase sempre a verificao realizada por meio de testes, executando o programa a ser testado com diferentes valores de entrada. Identificado um ou mais erros, o cdigo fonte corrigido e deve ser novamente verificado. O processo de compilao, ligao e teste se repete at que os resultados dos testes sejam satisfatrios e o programa seja considerado validado. Podemos descrever o ciclo atravs da Figura 1.4.

Editar

Compilar

Ligar

Testar

Figura 1.4: Ciclo de desenvolvimento.


1-8

Este ciclo pode ser realizado usando programas (editor, compilador, ligador) separados ou empregando um ambiente integrado de desenvolvimento (integrated development environment, ou IDE). IDE um programa que oferece janelas para a edio de programas e facilidades para abrir, fechar e salvar arquivos e para compilar, ligar e executar programas. Se um IDE estiver disponvel, possvel criar e testar um programa, tudo em um mesmo ambiente, e todo o ciclo mencionado acima acontece de maneira mais confortvel dentro de um mesmo ambiente, de preferncia com uma interface amigvel.


1-9

2. ExpressesW. Celes e J. L. Rangel Em C, uma expresso uma combinao de variveis, constantes e operadores que pode ser avaliada computacionalmente, resultando em um valor. O valor resultante chamado de valor da expresso.

2.1.

Variveis

Podemos dizer que uma varivel representa um espao na memria do computador para armazenar determinado tipo de dado. Na linguagem C, todas as variveis devem ser explicitamente declaradas. Na declarao de uma varivel, obrigatoriamente, devem ser especificados seu tipo e seu nome: o nome da varivel serve de referncia ao dado armazenado no espao de memria da varivel e o tipo da varivel determina a natureza do dado que ser armazenado. Tipos bsicos A linguagem C oferece alguns tipos bsicos. Para armazenar valores inteiros, existem trs tipos bsicos: char, short int, long int. Estes tipos diferem entre si pelo espao de memria que ocupam e conseqentemente pelo intervalo de valores que podem representar. O tipo char, por exemplo, ocupa 1 byte de memria (8 bits), podendo representar 28 (=256) valores distintos. Todos estes tipos podem ainda ser modificados para representarem apenas valores positivos, o que feito precedendo o tipo com o modificador sem sinal unsigned. A tabela abaixo compara os tipos para valores inteiros e suas representatividades.Tipo char unsigned char short int unsigned short int long int unsigned long int Tamanho 1 byte 1 byte 2 bytes 2 bytes 4 bytes 4 bytes Representatividade -128 a 127 0 a 255 -32 768 a 32 767 0 a 65 535 -2 147 483 648 a 2 147 483 647 4 294 967295

Os tipos short int e long int podem ser referenciados simplesmente com short e long, respectivamente. O tipo int puro mapeado para o tipo inteiro natural da mquina, que pode ser short ou long. A maioria das mquinas que usamos hoje funcionam com processadores de 32 bits e o tipo int mapeado para o inteiro de 4 bytes (long).1 O tipo char geralmente usado apenas para representar cdigos de caracteres, como veremos nos captulos subseqentes.

1

Um contra-exemplo o compilador TurboC, que foi desenvolvido para o sistema operacional DOS mas ainda pode ser utilizado no Windows. No TurboC, o tipo int mapeado para 2 bytes.2-1


A linguagem oferece ainda dois tipos bsicos para a representao de nmeros reais (ponto flutuante): float e double. A tabela abaixo compara estes dois tipos.Tipo float double Tamanho 4 bytes 8 bytes Representatividade -38 38 10 a 10 -308 308 10 a 10

Declarao de variveis Para armazenarmos um dado (valor) na memria do computador, devemos reservar o espao correspondente ao tipo do dado a ser armazenado. A declarao de uma varivel reserva um espao na memria para armazenar um dado do tipo da varivel e associa o nome da varivel a este espao de memria.int a; int b; float c; a = 5; b = 10; c = 5.3; /* declara uma varivel do tipo int */ /* declara outra varivel do tipo int */ /* declara uma varivel do tipo float */ /* armazena o valor 5 em a */ /* armazena o valor 10 em b */ /* armazena o valor 5.3 em c */

A linguagem permite que variveis de mesmo tipo sejam declaradas juntas. Assim, as duas primeiras declaraes acima poderiam ser substitudas por:int a, b; /* declara duas variveis do tipo int */

Uma vez declarada a varivel, podemos armazenar valores nos respectivos espaos de memria. Estes valores devem ter o mesmo tipo da varivel, conforme ilustrado acima. No possvel, por exemplo, armazenar um nmero real numa varivel do tipo int. Se fizermos:int a; a = 4.3; /* a varivel armazenar o valor 4 */

ser armazenada em a apenas a parte inteira do nmero real, isto , 4. Alguns compiladores exibem uma advertncia quando encontram este tipo de atribuio. Em C, as variveis podem ser inicializadas na declarao. Podemos, por exemplo, escrever:int a = 5, b = 10; float c = 5.3; /* declara e inicializa as variveis */

Valores constantes Em nossos cdigos, usamos tambm valores constantes. Quando escrevemos a atribuio:a = b + 123;


2-2

sendo a e b variveis supostamente j declaradas, reserva-se um espao para armazenar a constante 123. No caso, a constante do tipo inteiro, ento um espao de quatro bytes (em geral) reservado e o valor 123 armazenado nele. A diferena bsica em relao s variveis, como os nomes dizem (variveis e constantes), que o valor armazenado numa rea de constante no pode ser alterado. As constantes tambm podem ser do tipo real. Uma constante real deve ser escrita com um ponto decimal ou valor de expoente. Sem nenhum sufixo, uma constante real do tipo double. Se quisermos uma constante real do tipo float, devemos, a rigor, acrescentar o sufixo F ou f. Alguns exemplos de constantes reais so:12.45 1245e-2 12.45F constante real do tipo double constante real do tipo double constante real do tipo float

Alguns compiladores exibem uma advertncia quando encontram o cdigo abaixo:float x; ... x = 12.45;

pois o cdigo, a rigor, armazena um valor double (12.45) numa varivel do tipo float. Desde que a constante seja representvel dentro de um float, no precisamos nos preocupar com este tipo de advertncia. Variveis com valores indefinidos Um dos erros comuns em programas de computador o uso de variveis cujos valores ainda esto indefinidos. Por exemplo, o trecho de cdigo abaixo est errado, pois o valor armazenado na varivel b est indefinido e tentamos us-lo na atribuio a c. comum dizermos que b tem lixo.int a, b, c; a = 2; c = a + b;

/* ERRO: b tem lixo */

Alguns destes erros so bvios (como o ilustrado acima) e o compilador capaz de nos reportar uma advertncia; no entanto, muitas vezes o uso de uma varivel no definida fica difcil de ser identificado no cdigo. Repetimos que um erro comum em programas e uma razo para alguns programas funcionarem na parte da manh e no funcionarem na parte da tarde (ou funcionarem durante o desenvolvimento e no funcionarem quando entregamos para nosso cliente!). Todos os erros em computao tm lgica. A razo de o programa poder funcionar uma vez e no funcionar outra que, apesar de indefinido, o valor da varivel existe. No nosso caso acima, pode acontecer que o valor armazenado na memria ocupada por b seja 0, fazendo com que o programa funcione. Por outro lado, pode acontecer de o valor ser 293423 e o programa no funcionar.


2-3

2.2.

Operadores

A linguagem C oferece uma gama variada de operadores, entre binrios e unrios. Os operadores bsicos so apresentados a seguir. Operadores Aritmticos Os operadores aritmticos binrios so: +, -, *, / e o operador mdulo %. H ainda o operador unrio -. A operao feita na preciso dos operandos. Assim, a expresso 5/2 resulta no valor 2, pois a operao de diviso feita em preciso inteira, j que os dois operandos (5 e 2) so constantes inteiras. A diviso de inteiros trunca a parte fracionria, pois o valor resultante sempre do mesmo tipo da expresso. Conseqentemente, a expresso 5.0/2.0 resulta no valor real 2.5 pois a operao feita na preciso real (double, no caso). O operador mdulo, %, no se aplica a valores reais, seus operandos devem ser do tipo inteiro. Este operador produz o resto da diviso do primeiro pelo segundo operando. Como exemplo de aplicao deste operador, podemos citar o caso em que desejamos saber se o valor armazenado numa determinada varivel inteira x par ou mpar. Para tanto, basta analisar o resultado da aplicao do operador %, aplicado varivel e ao valor dois.x % 2 x % 2 se resultado for zero se resultado for um nmero par nmero mpar

Os operadores *, / e % tm precedncia maior que os operadores + e -. O operador unrio tem precedncia maior que *, / e %. Operadores com mesma precedncia so avaliados da esquerda para a direita. Assim, na expresso:a + b * c /d

executa-se primeiro a multiplicao, seguida da diviso, seguida da soma. Podemos utilizar parnteses para alterar a ordem de avaliao de uma expresso. Assim, se quisermos avaliar a soma primeiro, podemos escrever:(a + b) * c /d

Uma tabela de precedncia dos operadores da linguagem C apresentada no final desta seo. Operadores de atribuio Na linguagem C, uma atribuio uma expresso cujo valor resultante corresponde ao valor atribudo. Assim, da mesma forma que a expresso:5 + 3

resulta no valor 8, a atribuio:a = 5


2-4

resulta no valor 5 (alm, claro, de armazenar o valor 5 na varivel a). Este tratamento das atribuies nos permite escrever comandos do tipo:y = x = 5;

Neste caso, a ordem de avaliao da direita para a esquerda. Assim, o computador avalia x = 5, armazenando 5 em x, e em seguida armazena em y o valor produzido por x = 5, que 5. Portanto, ambos, x e y, recebem o valor 5. A linguagem tambm permite utilizar os chamados operadores de atribuio compostos. Comandos do tipo:i = i + 2;

em que a varivel esquerda do sinal de atribuio tambm aparece direita, podem ser escritas de forma mais compacta:i += 2;

usando o operador de atribuio composto +=. Analogamente, existem, entre outros, os operadores de atribuio: -=, *=, /=, %=. De forma geral, comandos do tipo:var op= expr;

so equivalentes a:var = var op (expr);

Salientamos a presena dos parnteses em torno de expr. Assim:x *= y + 1;

equivale ax = x * (y + 1)

e no ax = x * y + 1;

Operadores de incremento e decremento A linguagem C apresenta ainda dois operadores no convencionais. So os operadores de incremento e decremento, que possuem precedncia comparada ao - unrio e servem para incrementar e decrementar uma unidade nos valores armazenados nas variveis. Assim, se n uma varivel que armazena um valor, o comando:n++;


2-5

incrementa de uma unidade o valor de n (anlogo para o decremento em n--). O aspecto no usual que ++ e -- podem ser usados tanto como operadores pr-fixados (antes da varivel, como em ++n) ou ps-fixados (aps a varivel, como em n++). Em ambos os casos, a varivel n incrementada. Porm, a expresso ++n incrementa n antes de usar seu valor, enquanto n++ incrementa n aps seu valor ser usado. Isto significa que, num contexto onde o valor de n usado, ++n e n++ so diferentes. Se n armazena o valor 5, ento:x = n++;

atribui 5 a x, mas:x = ++n;

atribuiria 6 a x. Em ambos os casos, n passa a valer 6, pois seu valor foi incrementado em uma unidade. Os operadores de incremento e decremento podem ser aplicados somente em variveis; uma expresso do tipo x = (i + 1)++ ilegal. A linguagem C oferece diversas formas compactas para escrevermos um determinado comando. Neste curso, procuraremos evitar as formas compactas pois elas tendem a dificultar a compreenso do cdigo. Mesmo para programadores experientes, o uso das formas compactas deve ser feito com critrio. Por exemplo, os comandos:a = a + 1; a += 1; a++; ++a;

so todos equivalentes e o programador deve escolher o que achar mais adequado e simples. Em termos de desempenho, qualquer compilador razovel capaz de otimizar todos estes comandos da mesma forma. Operadores relacionais e lgicos Os operadores relacionais em C so:< > = == != menor que maior que menor ou igual que maior ou igual que igual a diferente de

Estes operadores comparam dois valores. O resultado produzido por um operador relacional zero ou um. Em C, no existe o tipo booleano (true ou false). O valor zero interpretado como falso e qualquer valor diferente de zero considerado verdadeiro. Assim, se oEstruturas de Dados PUC-Rio 2-6

resultado de uma comparao for falso, produz-se o valor 0, caso contrrio, produz-se o valor 1. Os operadores lgicos combinam expresses booleanas. A linguagem oferece os seguintes operadores lgicos:&& || ! operador binrio E (AND) operador binrio OU (OR) operador unrio de NEGAO (NOT)

Expresses conectadas por && ou || so avaliadas da esquerda para a direita, e a avaliao pra assim que a veracidade ou falsidade do resultado for conhecida. Recomendamos o uso de parnteses em expresses que combinam operadores lgicos e relacionais. Os operadores relacionais e lgicos so normalmente utilizados para tomada de decises. No entanto, podemos utiliz-los para atribuir valores a variveis. Por exemplo, o trecho de cdigo abaixo vlido e armazena o valor 1 em a e 0 em b.int a, b; int c = 23; int d = c + 4; a = (c < 20) || (d > c); b = (c < 20) && (d > c); /* verdadeiro */ /* falso */

Devemos salientar que, na avaliao da expresso atribuda varivel b, a operao (d>c) no chega a ser avaliada, pois independente do seu resultado a expresso como um todo ter como resultado 0 (falso), uma vez que a operao (c . ! ~ ++ -- - (tipo) * & sizeof(tipo) * / % + > < >= == != & ^ | && || ?: = += -= etc. , Associatividade esquerda para direita direita para esquerda esquerda para direita esquerda para direita esquerda para direita esquerda para direita esquerda para direita esquerda para direita esquerda para direita esquerda para direita esquerda para direita esquerda para direita direita para esquerda direita para esquerda esquerda para direita

2.3.

Entrada e sada bsicas

A linguagem C no possui comandos de entrada e sada do tipo READ e WRITE encontrados na linguagem FORTRAN. Tudo em C feito atravs de funes, inclusive as operaes de entrada e sada. Por isso, j existe em C uma biblioteca padro que possui as funes bsicas normalmente necessrias. Na biblioteca padro de C, podemos, por exemplo, encontrar funes matemticas do tipo raiz quadrada, seno, cosseno, etc., funes para a manipulao de cadeias de caracteres e funes de entrada e sada. Nesta seo, sero apresentadas as duas funes bsicas de entrada e sada disponibilizadas pela biblioteca padro. Para utiliz-las, necessrio incluir o prottipo destas funes no


2-8

cdigo. Este assunto ser tratado em detalhes na seo sobre funes. Por ora, basta saber que preciso escrever:#include

no incio do programa que utiliza as funes da biblioteca de entrada e sada. Funo printf A funo printf possibilita a sada de valores (sejam eles constantes, variveis ou resultado de expresses) segundo um determinado formato. Informalmente, podemos dizer que a forma da funo :printf (formato, lista de constantes/variveis/expresses...);

O primeiro parmetro uma cadeia de caracteres, em geral delimitada com aspas, que especifica o formato de sada das constantes, variveis e expresses listadas em seguida. Para cada valor que se deseja imprimir, deve existir um especificador de formato correspondente na cadeia de caracteres formato. Os especificadores de formato variam com o tipo do valor e a preciso em que queremos que eles sejam impressos. Estes especificadores so precedidos pelo caractere % e podem ser, entre outros:%c %d %u %f %e %g %s especifica um char especifica um int especifica um unsigned int especifica um double (ou float) especifica um double (ou float) no formato cientfico especifica um double (ou float) no formato mais apropriado (%f ou %e) especifica uma cadeia de caracteres

Alguns exemplos:printf ("%d %g\n", 33, 5.3);

tem como resultado a impresso da linha:33 5.3

Ou:printf ("Inteiro = %d Real = %g\n", 33, 5.3);

com sada:Inteiro = 33 Real = 5.3


2-9

Isto , alm dos especificadores de formato, podemos incluir textos no formato, que so mapeados diretamente para a sada. Assim, a sada formada pela cadeia de caracteres do formato onde os especificadores so substitudos pelos valores correspondentes. Existem alguns caracteres de escape que so freqentemente utilizados nos formatos de sada. So eles:\n \t \r \" \\ caractere de nova linha caractere de tabulao caractere de retrocesso o caractere " o caractere \

Ainda, se desejarmos ter como sada um caractere %, devemos, dentro do formato, escrever %%. possvel tambm especificarmos o tamanho dos campos:%4d 4 %7.2f 5 . 3 0 2 7 3 3

A funo printf retorna o nmero de campos impressos. Salientamos que para cada constante, varivel ou expresso listada devemos ter um especificador de formato apropriado. Funo scanf A funo scanf permite capturarmos valores fornecidos via teclado pelo usurio do programa. Informalmente, podemos dizer que sua forma geral :scanf (formato, lista de endereos das variveis...);

O formato deve possuir especificadores de tipos similares aos mostrados para a funo printf. Para a funo scanf, no entanto, existem especificadores diferentes para o tipo float e o tipo double:


2-10

%c %d %u %f,%e,%g %lf, %le, %lg %s

especifica um char especifica um int especifica um unsigned int especificam um float especificam um double especifica uma cadeia de caracteres

A principal diferena que o formato deve ser seguido por uma lista de endereos de variveis (na funo printf passamos os valores de constantes, variveis e expresses). Na seo sobre ponteiros, este assunto ser tratado em detalhes. Por ora, basta saber que, para ler um valor e atribu-lo a uma varivel, devemos passar o endereo da varivel para a funo scanf. O operador & retorna o endereo de uma varivel. Assim, para ler um inteiro, devemos ter:int n; scanf ("%d", &n);

Para a funo scanf, os especificadores %f, %e e %g so equivalentes. Aqui, caracteres diferentes dos especificadores no formato servem para cercar a entrada. Por exemplo:scanf ("%d:%d", &h, &m);

obriga que os valores (inteiros) fornecidos sejam separados pelo caractere dois pontos (:). Um espao em branco dentro do formato faz com que sejam "pulados" eventuais brancos da entrada. Os especificadores %d, %f, %e e %g automaticamente pulam os brancos que precederem os valores numricos a serem capturados. A funo scanf retorna o nmero de campos lidos com sucesso.


2-11

3.

Controle de fluxoW. Celes e J. L. Rangel

A linguagem C prov as construes fundamentais de controle de fluxo necessrias para programas bem estruturados: agrupamentos de comandos, tomadas de deciso (if-else), laos com teste de encerramento no incio (while, for) ou no fim (do-while), e seleo de um dentre um conjunto de possveis casos (switch).

3.1. Decises com ifif o comando de deciso bsico em C. Sua forma pode ser:if (expr) { bloco de comandos 1 ... }

ouif ( expr ) { bloco de comandos 1 ... } else { bloco de comandos 2 ... }

Se expr produzir um valor diferente de 0 (verdadeiro), o bloco de comandos 1 ser executado. A incluso do else requisita a execuo do bloco de comandos 2 se a expresso produzir o valor 0 (falso). Cada bloco de comandos deve ser delimitado por uma chave aberta e uma chave fechada. Se dentro de um bloco tivermos apenas um comando a ser executado, as chaves podem ser omitidas (na verdade, deixamos de ter um bloco):if ( expr ) comando1; else comando2;

A indentao (recuo de linha) dos comandos fundamental para uma maior clareza do cdigo. O estilo de indentao varia a gosto do programador. Alm da forma ilustrada acima, outro estilo bastante utilizado por programadores C :if ( expr ) { bloco de comandos 1 ... } else { bloco de comandos 2 ... }Estruturas de Dados PUC-Rio 3-1

Podemos aninhar comandos if. Um exemplo simples ilustrado a seguir:#include int main (void) { int a, b; printf("Insira dois numeros inteiros:"); scanf("%d%d",&a,&b); if (a%2 == 0) if (b%2 == 0) printf("Voce inseriu dois numeros pares!\n"); return 0; }

Primeiramente, notamos que no foi necessrio criar blocos ( {...} ) porque a cada if est associado apenas um comando. Ao primeiro, associamos o segundo comando if, e ao segundo if associamos o comando que chama a funo printf. Assim, o segundo if s ser avaliado se o primeiro valor fornecido for par, e a mensagem s ser impressa se o segundo valor fornecido tambm for par. Outra construo para este mesmo exemplo simples pode ser:int main (void) { int a, b; printf("Digite dois numeros inteiros:"); scanf("%d%d",&a,&b); if ((a%2 == 0) && (b%2 == 0)) printf ( "Voce digitou dois numeros pares!\n"); return 0; }

produzindo resultados idnticos. Devemos, todavia, ter cuidado com o aninhamento de comandos if-else. Para ilustrar, consideremos o exemplo abaixo./* temperatura (versao 1 - incorreta) */ #include int main (void) { int temp; printf("Digite a temperatura: "); scanf("%d", &temp); if (temp < 30) if (temp > 20) printf(" Temperatura agradavel \n"); else printf(" Temperatura muito quente \n"); return 0; }

A idia deste programa era imprimir a mensagem Temperatura agradvel se fosse fornecido um valor entre 20 e 30, e imprimir a mensagem Temperatura muito quente se fosse fornecido um valor maior que 30. No entanto, vamos analisar o caso deEstruturas de Dados PUC-Rio 3-2

ser fornecido o valor 5 para temp. Observando o cdigo do programa, podemos pensar que nenhuma mensagem seria fornecida, pois o primeiro if daria resultado verdadeiro e ento seria avaliado o segundo if. Neste caso, teramos um resultado falso e como, aparentemente, no h um comando else associado, nada seria impresso. Puro engano. A indentao utilizada pode nos levar a erros de interpretao. O resultado para o valor 5 seria a mensagem Temperatura muito quente. Isto , o programa est INCORRETO. Em C, um else est associado ao ltimo if que no tiver seu prprio else. Para os casos em que a associao entre if e else no est clara, recomendamos a criao explcita de blocos, mesmo contendo um nico comando. Reescrevendo o programa, podemos obter o efeito desejado./* temperatura (versao 2) */ #include int main (void) { int temp; printf ( "Digite a temperatura: " ); scanf ( "%d", &temp ); if ( temp < 30 ) { if ( temp > 20 ) printf ( " Temperatura agradavel \n" ); } else printf ( " Temperatura muito quente \n" ); return 0; }

Esta regra de associao do else propicia a construo do tipo else-if, sem que se tenha o comando elseif explicitamente na gramtica da linguagem. Na verdade, em C, construmos estruturas else-if com ifs aninhados. O exemplo abaixo vlido e funciona como esperado./* temperatura (versao 3) */ #include int main (void) { int temp; printf("Digite a temperatura: "); scanf("%d", &temp); if (temp < 10) printf("Temperatura muito fria \n"); else if (temp < 20) printf(" Temperatura fria \n"); else if (temp < 30) printf("Temperatura agradavel \n"); else printf("Temperatura muito quente \n"); return 0;

}


3-3

Estruturas de bloco Observamos que uma funo C composta por estruturas de blocos. Cada chave aberta e fechada em C representa um bloco. As declaraes de variveis s podem ocorrer no incio do corpo da funo ou no incio de um bloco, isto , devem seguir uma chave aberta. Uma varivel declarada dentro de um bloco vlida apenas dentro do bloco. Aps o trmino do bloco, a varivel deixa de existir. Por exemplo:... if ( n > 0 ) { int i; ... } ...

/* a varivel i no existe neste ponto do programa */

A varivel i, definida dentro do bloco do if, s existe dentro deste bloco. uma boa prtica de programao declarar as varveis o mais prximo possvel dos seus usos. Operador condicional C possui tambm um chamado operador condicional. Trata-se de um operador que substitui construes do tipo:... if ( a > b ) maximo = a; else maximo = b; ...

Sua forma geral :condio ? expresso1 : expresso2;

se a condio for verdadeira, a expresso1 avaliada; caso contrrio, avalia-se a expresso2. O comando:maximo = a > b ? a : b ;

substitui a construo com if-else mostrada acima.

3.2. Construes com laos muito comum, em programas computacionais, termos procedimentos iterativos, isto , procedimentos que devem ser executados em vrios passos. Como exemplo, vamos considerar o clculo do valor do fatorial de um nmero inteiro no negativo. Por definio:

n != n (n 1) (n 2)...3 2 1, onde 0 != 1


3-4

Para calcular o fatorial de um nmero atravs de um programa de computador, utilizamos tipicamente um processo iterativo, em que o valor da varivel varia de 1 a n. A linguagem C oferece diversas construes possveis para a realizao de laos iterativos. O primeiro a ser apresentado o comando while. Sua forma geral :while (expr) { bloco de comandos ... }

Enquanto expr for avaliada em verdadeiro, o bloco de comandos executado repetidamente. Se expr for avaliada em falso, o bloco de comando no executado e a execuo do programa prossegue. Uma possvel implementao do clculo do fatorial usando while mostrada a seguir./* Fatorial */ #include int main (void) { int i; int n; int f = 1; printf("Digite um nmero inteiro nao negativo:"); scanf("%d", &n); /* calcula fatorial */ i = 1; while (i

1.0 5 5

f n fat > r n main >

120.0 0 5

main >

r n

120.0 5

Figura 4.2: Execuo do programa passo a passo.

Isto ilustra por que o valor da varivel passada nunca ser alterado dentro da funo. A seguir, discutiremos uma forma para podermos alterar valores por passagem de parmetros, o que ser realizado passando o endereo de memria onde a varivel est armazenada. Vale salientar que existe outra forma de fazermos comunicao entre funes, que consiste no uso de variveis globais. Se uma determinada varivel global visvel em duas funes, ambas as funes podem acessar e/ou alterar o valor desta varivel diretamente. NoEstruturas de Dados PUC-Rio 4-5

entanto, conforme j mencionamos, o uso de variveis globais em um programa deve ser feito com critrio, pois podemos criar cdigos com uma alto grau de interdependncia entre as funes, o que dificulta a manuteno e o reuso do cdigo.

4.3. Ponteiro de variveisA linguagem C permite o armazenamento e a manipulao de valores de endereos de memria. Para cada tipo existente, h um tipo ponteiro que pode armazenar endereos de memria onde existem valores do tipo correspondente armazenados. Por exemplo, quando escrevemos:int a;

declaramos uma varivel com nome a que pode armazenar valores inteiros. Automaticamente, reserva-se um espao na memria suficiente para armazenar valores inteiros (geralmente 4 bytes). Da mesma forma que declaramos variveis para armazenar inteiros, podemos declarar variveis que, em vez de servirem para armazenar valores inteiros, servem para armazenar valores de endereos de memria onde h variveis inteiras armazenadas. C no reserva uma palavra especial para a declarao de ponteiros; usamos a mesma palavra do tipo com os nomes das variveis precedidas pelo caractere *. Assim, podemos escrever:int *p;

Neste caso, declaramos uma varivel com nome p que pode armazenar endereos de memria onde existe um inteiro armazenado. Para atribuir e acessar endereos de memria, a linguagem oferece dois operadores unrios ainda no discutidos. O operador unrio & (endereo de), aplicado a variveis, resulta no endereo da posio da memria reservada para a varivel. O operador unrio * (contedo de), aplicado a variveis do tipo ponteiro, acessa o contedo do endereo de memria armazenado pela varivel ponteiro. Para exemplificar, vamos ilustrar esquematicamente, atravs de um exemplo simples, o que ocorre na pilha de execuo. Consideremos o trecho de cdigo mostrado na figura abaixo.

/*varivel inteiro */

int a;

/*varivel ponteiro p/ inteiro */

int *p;

p a

-

112 108 104

Figura 4.3: Efeito de declaraes de variveis na pilha de execuo.


4-6

Aps as declaraes, ambas as variveis, a e p, armazenam valores "lixo", pois no foram inicializadas. Podemos fazer atribuies como exemplificado nos fragmentos de cdigo da figura a seguir:

/* a recebe o valor 5 */

a = 5;

p a

5

112 108 104

/* p recebe o endereo de a (diz-se p aponta para a) */

p = &a;/* contedo de p recebe o valor 6 */

p a

104 5

112 108 104

*p = 6;

p a

104 6

112 108 104

Figura 4.4: Efeito de atribuio de variveis na pilha de execuo.

Com as atribuies ilustradas na figura, a varivel a recebe, indiretamente, o valor 6. Acessar a equivalente a acessar *p, pois p armazena o endereo de a. Dizemos que p aponta para a, da o nome ponteiro. Em vez de criarmos valores fictcios para os endereos de memria no nosso esquema ilustrativo da memria, podemos desenhar setas graficamente, sinalizando que um ponteiro aponta para uma determinada varivel.

p a 6

Figura 4.5: Representao grfica do valor de um ponteiro.

A possibilidade de manipular ponteiros de variveis uma das maiores potencialidades de C. Por outro lado, o uso indevido desta manipulao o maior causador de programas que "voam", isto , no s no funcionam como, pior ainda, podem gerar efeitos colaterais no previstos.


4-7

A seguir, apresentamos outros exemplos de uso de ponteiros. O cdigo abaixo:int main ( void ) { int a; int *p; p = &a; *p = 2; printf(" %d ", a); return; }

imprime o valor 2. Agora, no exemplo abaixo:int main ( void ) { int a, b, *p; a = 2; *p = 3; b = a + (*p); printf(" %d ", b); return 0; }

cometemos um ERRO tpico de manipulao de ponteiros. O pior que esse programa, embora incorreto, s vezes pode funcionar. O erro est em usar a memria apontada por p para armazenar o valor 3. Ora, a varivel p no tinha sido inicializada e, portanto, tinha armazenado um valor (no caso, endereo) "lixo". Assim, a atribuio *p = 3; armazena 3 num espao de memria desconhecido, que tanto pode ser um espao de memria no utilizado, e a o programa aparentemente funciona bem, quanto um espao que armazena outras informaes fundamentais por exemplo, o espao de memria utilizado por outras variveis ou outros aplicativos. Neste caso, o erro pode ter efeitos colaterais indesejados. Portanto, s podemos preencher o contedo de um ponteiro se este tiver sido devidamente inicializado, isto , ele deve apontar para um espao de memria onde j se prev o armazenamento de valores do tipo em questo. De maneira anloga, podemos declarar ponteiros de outros tipos:float *m; char *s;

Passando ponteiros para funes Os ponteiros oferecem meios de alterarmos valores de variveis acessando-as indiretamente. J discutimos que as funes no podem alterar diretamente valores de variveis da funo que fez a chamada. No entanto, se passarmos para uma funo os valores dos endereos de memria onde suas variveis esto armazenadas, a funo pode alterar, indiretamente, os valores das variveis da funo que a chamou.


4-8

Vamos analisar o uso desta estratgia atravs de um exemplo. Consideremos uma funo projetada para trocar os valores entre duas variveis. O cdigo abaixo:/* funcao troca (versao ERRADA) */ #include void troca (int x, int y ) { int temp; temp = x; x = y; y = temp; } int main ( void ) { int a = 5, b = 7; troca(a, b); printf("%d %d \n", a, b); return 0; }

no funciona como esperado (sero impressos 5 e 7), pois os valores de a e b da funo main no so alterados. Alterados so os valores de x e y dentro da funo troca, mas eles no representam as variveis da funo main, apenas so inicializados com os valores de a e b. A alternativa fazer com que a funo receba os endereos das variveis e, assim, alterar seus valores indiretamente. Reescrevendo:/* funcao troca (versao CORRETA) */ #include void troca (int *px, int *py ) { int temp; temp = *px; *px = *py; *py = temp; } int main ( void ) { int a = 5, b = 7; troca(&a, &b); /* passamos os endereos das variveis */ printf("%d %d \n", a, b); return 0; }

A Figura 4.6 ilustra a execuo deste programa mostrando o uso da memria. Assim, conseguimos o efeito desejado. Agora fica explicado por que passamos o endereo das variveis para a funo scanf, pois, caso contrrio, a funo no conseguiria devolver os valores lidos.


4-9

1 -Declarao das variveis: a, b

2 - Chamada da funo: passa endereos120

main

b a >

7 5

112 108 104

troca main

py px >b a >

108 104 7 5

116 112 108 104

3 - Declarao da varivel local: temptemp py troca main px > b a > 108 104 7 5 120 116 112 108 104

4 - temp recebe contedo de pxtemp py px troca >b a main > 5 108 104 7 5 120 116 112 108 104

5 -Contedo de px recebe contedo de pytemp py px troca >b main > a 5 108 104 7 7 120 116 112 108 104

6 -Contedo de py recebe temptemp py px troca >b main > a 5 108 104 5 7 120 116 112 108 104

Figura 4.6: Passo a passo da funo que troca dois valores.

4.4. RecursividadeAs funes podem ser chamadas recursivamente, isto , dentro do corpo de uma funo podemos chamar novamente a prpria funo. Se uma funo A chama a prpria funo A, dizemos que ocorre uma recurso direta. Se uma funo A chama uma funo B que, por sua vez, chama A, temos uma recurso indireta. Diversas implementaes ficam muito mais fceis usando recursividade. Por outro lado, implementaes no recursivas tendem a ser mais eficientes. Para cada chamada de uma funo, recursiva ou no, os parmetros e as variveis locais so empilhados na pilha de execuo. Assim, mesmo quando uma funo chamada recursivamente, cria-se um ambiente local para cada chamada. As variveis locais de chamadas recursivas so independentes entre si, como se estivssemos chamando funes diferentes.Estruturas de Dados PUC-Rio 4-10

As implementaes recursivas devem ser pensadas considerando-se a definio recursiva do problema que desejamos resolver. Por exemplo, o valor do fatorial de um nmero pode ser definido de forma recursiva:

1, se n = 0 n!= n (n 1)!, se n > 0 Considerando a definio acima, fica muito simples pensar na implementao recursiva de uma funo que calcula e retorna o fatorial de um nmero./* Funo recursiva para calculo do fatorial */ int fat (int n) { if (n==0) return 1; else return n*fat(n-1); }

4.5. Variveis estticas dentro de funes**Podemos declarar variveis estticas dentro de funes. Neste caso, as variveis no so armazenadas na pilha, mas sim numa rea de memria esttica que existe enquanto o programa est sendo executado. Ao contrrio das variveis locais (ou automticas), que existem apenas enquanto a funo qual elas pertencem estiver sendo executada, as estticas, assim como as globais, continuam existindo mesmo antes ou depois de a funo ser executada. No entanto, uma varivel esttica declarada dentro de uma funo s visvel dentro dessa funo. Uma utilizao importante de variveis estticas dentro de funes quando se necessita recuperar o valor de uma varivel atribuda na ltima vez que a funo foi executada. Para exemplificar a utilizao de variveis estticas declaradas dentro de funes, consideremos uma funo que serve para imprimir nmeros reais. A caracterstica desta funo que ela imprime um nmero por vez, separando-os por espaos em branco e colocando, no mximo, cinco nmeros por linha. Com isto, do primeiro ao quinto nmero so impressos na primeira linha, do sexto ao dcimo na segunda, e assim por diante.void imprime ( float a ) { static int n = 1; printf(" %f ", a); if ((n % 5) == 0) printf(" \n "); n++; }

Se uma varivel esttica no for explicitamente inicializada na declarao, ela automaticamente inicializada com zero. (As variveis globais tambm so, por default, inicializadas com zero.)Estruturas de Dados PUC-Rio 4-11

4.6. Pr-processador e macros**Um cdigo C, antes de ser compilado, passa por um pr-processador. O pr-processador de C reconhece determinadas diretivas e altera o cdigo para, ento, envi-lo ao compilador. Uma das diretivas reconhecidas pelo pr-processador, e j utilizada nos nossos exemplos, #include. Ela seguida por um nome de arquivo e o pr-processador a substitui pelo corpo do arquivo especificado. como se o texto do arquivo includo fizesse parte do cdigo fonte. Uma observao: quando o nome do arquivo a ser includo envolto por aspas ("arquivo"), o pr-processador procura primeiro o arquivo no diretrio atual e, caso no o encontre, o procura nos diretrios de include especificados para compilao. Se o arquivo colocado entre os sinais de menor e maior (), o pr-processador no procura o arquivo no diretrio atual. Outra diretiva de pr-processamento que muito utilizada e que ser agora discutida a diretiva de definio. Por exemplo, uma funo para calcular a rea de um crculo pode ser escrita da seguinte forma:#define PI 3.14159

float area (float r) { float a = PI * r * r; return a; }

Neste caso, antes da compilao, toda ocorrncia da palavra PI (desde que no envolvida por aspas) ser trocada pelo nmero 3.14159. O uso de diretivas de definio para representarmos constantes simblicas fortemente recomendvel, pois facilita a manuteno e acrescenta clareza ao cdigo. C permite ainda a utilizao da diretiva de definio com parmetros. vlido escrever, por exemplo:#define MAX(a,b) ((a) > (b) ? (a) : (b))

assim, se aps esta definio existir uma linha de cdigo com o trecho:v = 4.5; c = MAX ( v, 3.0 );

o compilador ver:v = 4.5; c = ((v) > (4.5) ? (v) : (4.5));

Estas definies com parmetros recebem o nome de macros. Devemos ter muito cuidado na definio de macros. Mesmo um erro de sintaxe pode ser difcil de ser detectado, pois oEstruturas de Dados PUC-Rio 4-12

compilador indicar um erro na linha em que se utiliza a macro e no na linha de definio da macro (onde efetivamente encontra-se o erro). Outros efeitos colaterais de macros mal definidas podem ser ainda piores. Por exemplo, no cdigo abaixo:#include #define DIF(a,b) a - b

int main (void) { printf(" %d ", 4 * DIF(5,3)); return 0; }

o resultado impresso 17 e no 8, como poderia ser esperado. A razo simples, pois para o compilador (fazendo a substituio da macro) est escrito:printf(" %d ", 4 * 5 - 3);

e a multiplicao tem precedncia sobre a subtrao. Neste caso, parnteses envolvendo a macro resolveriam o problema. Porm, neste outro exemplo que envolve a macro com parnteses:#include #define PROD(a,b) (a * b)

int main (void) { printf(" %d ", PROD(3+4, 2)); return 0; }

o resultado 11 e no 14. A macro corretamente definida seria:#define PROD(a,b) ((a) * (b))

Conclumos, portanto, que, como regra bsica para a definio de macros, devemos envolver cada parmetro, e a macro como um todo, com parnteses.


4-13

5. Vetores e alocao dinmicaW. Celes e J. L. Rangel

5.1. VetoresA forma mais simples de estruturarmos um conjunto de dados por meio de vetores. Como a maioria das linguagens de programao, C permite a definio de vetores. Definimos um vetor em C da seguinte forma:int v[10];

A declarao acima diz que v um vetor de inteiros dimensionado com 10 elementos, isto , reservamos um espao de memria contnuo para armazenar 10 valores inteiros. Assim, se cada int ocupa 4 bytes, a declarao acima reserva um espao de memria de 40 bytes, como ilustra a figura abaixo.144

v

104

Figura 5.1: Espao de memria de um vetor de 10 elementos inteiros.

O acesso a cada elemento do vetor feito atravs de uma indexao da varivel v. Observamos que, em C, a indexao de um vetor varia de zero a n-1, onde n representa a dimenso do vetor. Assim:v[0] v[1] ... v[9] acessa o primeiro elemento de v acessa o segundo elemento de v acessa o ltimo elemento de v

Mas:v[10] est ERRADO (invaso de memria)


5-1

Para exemplificar o uso de vetores, vamos considerar um programa que l 10 nmeros reais, fornecidos via teclado, e calcula a mdia e a varincia destes nmeros. A mdia e a varincia so dadas por:x m= , N

(x m ) v=N

2

Uma possvel implementao apresentada a seguir./* Clculo da media e da varincia de 10 nmeros reais */ #include int main ( void ) { float v[10]; float med, var; int i;

/* declara vetor com 10 elementos */ /* variveis para armazenar a mdia e a varincia */ /* varivel usada como ndice do vetor */ /* faz ndice variar de 0 a 9 */ /* l cada elemento do vetor */ /* inicializa mdia com zero */ /* acumula soma dos elementos */ /* calcula a mdia */

/* leitura dos valores */ for (i = 0; i < 10; i++) scanf("%f", &v[i]); /* clculo da mdia */ med = 0.0; for (i = 0; i < 10; i++) med = med + v[i]; med = med / 10;

/* clculo da varincia */ var = 0.0; /* inicializa varincia com zero */ for ( i = 0; i < 10; i++ ) var = var+(v[i]-med)*(v[i]-med); /* acumula quadrado da diferena */ var = var / 10; /* calcula a varincia */ printf ( "Media = %f return 0; Variancia = %f \n", med, var );

}

Devemos observar que passamos para a funo scanf o endereo de cada elemento do vetor (&v[i]), pois desejamos que os valores capturados sejam armazenados nos elementos do vetor. Se v[i] representa o (i+1)-simo elemento do vetor, &v[i] representa o endereo de memria onde esse elemento est armazenado. Na verdade, existe uma associao forte entre vetores e ponteiros, pois se existe a declarao:int v[10];

a varivel v, que representa o vetor, uma constante que armazena o endereo inicial do vetor, isto , v, sem indexao, aponta para o primeiro elemento do vetor.


5-2

A linguagem C tambm suporta aritmtica de ponteiros. Podemos somar e subtrair ponteiros, desde que o valor do ponteiro resultante aponte para dentro da rea reservada para o vetor. Se p representa um ponteiro para um inteiro, p+1 representa um ponteiro para o prximo inteiro armazenado na memria, isto , o valor de p incrementado de 4 (mais uma vez assumindo que um inteiro tem 4 bytes). Com isto, num vetor temos as seguintes equivalncias:v+0 v+1 v+2 ... v+9 aponta para o primeiro elemento do vetor aponta para o segundo elemento do vetor aponta para o terceiro elemento do vetor aponta para o ltimo elemento do vetor

Portanto, escrever &v[i] equivalente a escrever (v+i). De maneira anloga, escrever v[i] equivalente a escrever *(v+i) ( lgico que a forma indexada mais clara e adequada). Devemos notar que o uso da aritmtica de ponteiros aqui perfeitamente vlido, pois os elementos dos vetores so armazenados de forma contnua na memria. Os vetores tambm podem ser inicializados na declarao:int v[5] = { 5, 10, 15, 20, 25 };

ou simplesmente:int v[] = { 5, 10, 15, 20, 25 };

Neste ltimo caso, a linguagem dimensiona o vetor pelo nmero de elementos inicializados.

Passagem de vetores para funes Passar um vetor para uma funo consiste em passar o endereo da primeira posio do vetor. Se passarmos um valor de endereo, a funo chamada deve ter um parmetro do tipo ponteiro para armazenar este valor. Assim, se passarmos para uma funo um vetor de int, devemos ter um parmetro do tipo int*, capaz de armazenar endereos de inteiros. Salientamos que a expresso passar um vetor para uma funo deve ser interpretada como passar o endereo inicial do vetor. Os elementos do vetor no so copiados para a funo, o argumento copiado apenas o endereo do primeiro elemento.Para exemplificar, vamos modificar o cdigo do exemplo acima, usando funes separadas para o clculo da mdia e da varincia. (Aqui, usamos ainda os operadores de atribuio += para acumular as somas.)/* Clculo da media e da varincia de 10 reais (segunda verso) */ #include /* Funo para clculo da mdia */ float media (int n, float* v) { int i;Estruturas de Dados PUC-Rio 5-3

float s = 0.0; for (i = 0; i < n; i++) s += v[i]; return s/n; } /* Funo para clculo da varincia */ float variancia (int n, float* v, float m) { int i; float s = 0.0; for (i = 0; i < n; i++) s += (v[i] - m) * (v[i] - m); return s/n; } int main ( void ) { float v[10]; float med, var; int i; /* leitura dos valores */ for ( i = 0; i < 10; i++ ) scanf("%f", &v[i]); med = media(10,v); var = variancia(10,v,med); printf ( "Media = %f return 0; Variancia = %f \n", med, var);

}

Observamos ainda que, como passado para a funo o endereo do primeiro elemento do vetor (e no os elementos propriamente ditos), podemos alterar os valores dos elementos do vetor dentro da funo. O exemplo abaixo ilustra:/* Incrementa elementos de um vetor */ #include void incr_vetor ( int n, int *v ) { int i; for (i = 0; i < n; i++) v[i]++; } int main ( void ) { int a[ ] = {1, 3, 5}; incr_vetor(3, a); printf("%d %d %d \n", a[0], a[1], a[2]); return 0; }

A sada do programa 2 4 6, pois os elementos do vetor sero incrementados dentro da funo.


5-4

5.2. Alocao dinmicaAt aqui, na declarao de um vetor, foi preciso dimension-lo. Isto nos obrigava a saber, de antemo, quanto espao seria necessrio, isto , tnhamos que prever o nmero mximo de elementos no vetor durante a codificao. Este pr-dimensionamento do vetor um fator limitante. Por exemplo, se desenvolvermos um programa para calcular a mdia e a varincia das notas de uma prova, teremos que prever o nmero mximo de alunos. Uma soluo dimensionar o vetor com um nmero absurdamente alto para no termos limitaes quando da utilizao do programa. No entanto, isto levaria a um desperdcio de memria que inaceitvel em diversas aplicaes. Se, por outro lado, formos modestos no pr-dimensionamento do vetor, o uso do programa fica muito limitado, pois no conseguiramos tratar turmas com o nmero de alunos maior que o previsto. Felizmente, a linguagem C oferece meios de requisitarmos espaos de memria em tempo de execuo. Dizemos que podemos alocar memria dinamicamente. Com este recurso, nosso programa para o clculo da mdia e varincia discutido acima pode, em tempo de execuo, consultar o nmero de alunos da turma e ento fazer a alocao do vetor dinamicamente, sem desperdcio de memria.

Uso da memria Informalmente, podemos dizer que existem trs maneiras de reservarmos espao de memria para o armazenamento de informaes. A primeira delas atravs do uso de variveis globais (e estticas). O espao reservado para uma varivel global existe enquanto o programa estiver sendo executado. A segunda maneira atravs do uso de variveis locais. Neste caso, como j discutimos, o espao existe apenas enquanto a funo que declarou a varivel est sendo executada, sendo liberado para outros usos quando a execuo da funo termina. Por este motivo, a funo que chama no pode fazer referncia ao espao local da funo chamada. As variveis globais ou locais podem ser simples ou vetores. Para os vetores, precisamos informar o nmero mximo de elementos, caso contrrio o compilador no saberia o tamanho do espao a ser reservado.A terceira maneira de reservarmos memria requisitando ao sistema, em tempo de execuo, um espao de um determinado tamanho. Este espao alocado dinamicamente permanece reservado at que explicitamente seja liberado pelo programa. Por isso, podemos alocar dinamicamente um espao de memria numa funo e acess-lo em outra. A partir do momento que liberarmos o espao, ele estar disponibilizado para outros usos e no podemos mais acess-lo. Se o programa no liberar um espao alocado, este ser automaticamente liberado quando a execuo do programa terminar. Apresentamos abaixo um esquema didtico que ilustra de maneira fictcia a distribuio do uso da memria pelo sistema operacional1.

1

A rigor, a alocao dos recursos bem mais complexa e varia para cada sistema operacional.5-5


Cdigo do Programa

Variveis Globais e Estticas Memria Alocada Dinamicamente

Memria Livre

Pilha

Figura 5.2: Alocao esquemtica de memria.

Quando requisitamos ao sistema operacional para executar um determinado programa, o cdigo em linguagem de mquina do programa deve ser carregado na memria, conforme discutido no primeiro captulo. O sistema operacional reserva tambm os espaos necessrios para armazenarmos as variveis globais (e estticas) existentes no programa. O restante da memria livre utilizado pelas variveis locais e pelas variveis alocadas dinamicamente. Cada vez que uma determinada funo chamada, o sistema reserva o espao necessrio para as variveis locais da funo. Este espao pertence pilha de execuo e, quando a funo termina, desempilhado. A parte da memria no ocupada pela pilha de execuo pode ser requisitada dinamicamente. Se a pilha tentar crescer mais do que o espao disponvel existente, dizemos que ela estourou e o programa abortado com erro. Similarmente, se o espao de memria livre for menor que o espao requisitado dinamicamente, a alocao no feita e o programa pode prever um tratamento de erro adequado (por exemplo, podemos imprimir a mensagem Memria insuficiente e interromper a execuo do programa).

Funes da biblioteca padro Existem funes, presentes na biblioteca padro stdlib, que permitem alocar e liberar memria dinamicamente. A funo bsica para alocar memria malloc. Ela recebe como parmetro o nmero de bytes que se deseja alocar e retorna o endereo inicial da rea de memria alocada.Para exemplificar, vamos considerar a alocao dinmica de um vetor de inteiros com 10 elementos. Como a funo malloc retorna o endereo da rea alocada e, neste exemplo, desejamos armazenar valores inteiros nessa rea, devemos declarar um ponteiro de inteiro para receber o endereo inicial do espao alocado. O trecho de cdigo ento seria:int *v; v = malloc(10*4);

Aps este comando, se a alocao for bem sucedida, v armazenar o endereo inicial de uma rea contnua de memria suficiente para armazenar 10 valores inteiros. Podemos,Estruturas de Dados PUC-Rio 5-6

ento, tratar v como tratamos um vetor declarado estaticamente, pois, se v aponta para o inicio da rea alocada, podemos dizer que v[0] acessa o espao para o primeiro elemento que armazenaremos, v[1] acessa o segundo, e assim por diante (at v[9]). No exemplo acima, consideramos que um inteiro ocupa 4 bytes. Para ficarmos independentes de compiladores e mquinas, usamos o operador sizeof( ).v = malloc(10*sizeof(int));

Alm disso, devemos lembrar que a funo malloc usada para alocar espao para armazenarmos valores de qualquer tipo. Por este motivo, malloc retorna um ponteiro genrico, para um tipo qualquer, representado por void*, que pode ser convertido automaticamente pela linguagem para o tipo apropriado na atribuio. No entanto, comum fazermos a converso explicitamente, utilizando o operador de molde de tipo (cast). O comando para a alocao do vetor de inteiros fica ento:v = (int *) malloc(10*sizeof(int));

A figura abaixo ilustra de maneira esquemtica o que ocorre na memria:1 - Declarao: int *v Abre-se espao na pilha para o ponteiro (varivel local) Cdigo do Programa Variveis Globais e Estticas 2 - Comando: v = (int *) malloc (10*sizeof(int)) Reserva espao de memria da rea livre e atribui endereo varivel Cdigo do Programa Variveis Globais e Estticas40 bytes

504

Livre

Livre v 504

v

-

Figura 5.3: Alocao dinmica de memria.

Se, porventura, no houver espao livre suficiente para realizar a alocao, a funo retorna um endereo nulo (representado pelo smbolo NULL, definido em stdlib.h). Podemos cercar o erro na alocao do programa verificando o valor de retorno da funo malloc. Por exemplo, podemos imprimir uma mensagem e abortar o programa com a funo exit, tambm definida na stdlib.


5-7

v = (int*) malloc(10*sizeof(int)); if (v==NULL) { printf("Memoria insuficiente.\n"); exit(1); /* aborta o programa e retorna 1 para o sist. operacional */ }

Para liberar um espao de memria alocado dinamicamente, usamos a funo free. Esta funo recebe como parmetro o ponteiro da memria a ser liberada. Assim, para liberar o vetor v, fazemos:free (v);

S podemos passar para a funo free um endereo de memria que tenha sido alocado dinamicamente. Devemos lembrar ainda que no podemos acessar o espao na memria depois que o liberamos. Para exemplificar o uso da alocao dinmica, alteraremos o programa para o clculo da mdia e da varincia mostrado anteriormente. Agora, o programa l o nmero de valores que sero fornecidos, aloca um vetor dinamicamente e faz os clculos. Somente a funo principal precisa ser alterada, pois as funes para calcular a mdia e a varincia anteriormente apresentadas independem do fato de o vetor ter sido alocado esttica ou dinamicamente./* Clculo da mdia e da varincia de n reais */ #include #include ... int main ( void ) { int i, n; float *v; float med, var; /* leitura do nmero de valores */ scanf("%d", &n); /* alocao dinmica */ v = (float*) malloc(n*sizeof(float)); if (v==NULL) { printf("Memoria insuficiente.\n); return 1; } /* leitura dos valores */ for (i = 0; i < n; i++) scanf("%f", &v[i]); med = media(n,v); var = variancia(n,v,med); printf("Media = %f Variancia = %f \n", med, var); /* libera memria */ free(v); return 0;

}


5-8

6. Cadeia de caracteresW. Celes e J. L. Rangel

6.1. CaracteresEfetivamente, a linguagem C no oferece um tipo caractere. Os caracteres so representados por cdigos numricos. A linguagem oferece o tipo char, que pode armazenar valores inteiros pequenos: um char tem tamanho de 1 byte, 8 bits, e sua verso com sinal pode representar valores que variam de 128 a 127. Como os cdigos associados aos caracteres esto dentro desse intervalo, usamos o tipo char para representar caracteres1. A correspondncia entre os caracteres e seus cdigos numricos feita por uma tabela de cdigos. Em geral, usa-se a tabela ASCII, mas diferentes mquinas podem usar diferentes cdigos. Contudo, se desejamos escrever cdigos portteis, isto , que possam ser compilados e executados em mquinas diferentes, devemos evitar o uso explcito dos cdigos referentes a uma determinada tabela, como ser discutido nos exemplos subseqentes. Como ilustrao, mostramos a seguir os cdigos associados a alguns caracteres segundo a tabela ASCII. Alguns caracteres que podem ser impressos (sp representa o branco, ou espao): 0 30 40 50 60 70 80 90 100 110 120( 2 < F P Z d n x

1) 3 = G Q [ e o y

2sp * 4 > H R \ f p z

3! + 5 ? I S ] g q {

4" , 6 @ J T ^ h r |

5# 7 A K U _ i S }

6$ . 8 B L V ` j t ~

7% / 9 C M W a k u

8& 0 : D N X b l v

9' 1 ; E O Y c m w

Alguns caracteres de controle: 0 7 8 9 10 13 1271

nul bel bs ht nl cr del

null: nulo bell: campainha backspace: voltar e apagar um caractere tab ou tabulao horizontal newline ou line feed: mudana de linha carriage return: volta ao incio da linha delete: apagar um caractere

Alguns alfabetos precisam de maior representatividade. O alfabeto chins, por exemplo, tem mais de 256 caracteres, no sendo suficiente o tipo char (alguns compiladores oferecem o tipo wchar, para estes casos).6-1


Em C, a diferena entre caracteres e inteiros feita apenas atravs da maneira pela qual so tratados. Por exemplo, podemos imprimir o mesmo valor de duas formas diferentes usando formatos diferentes. Vamos analisar o fragmento de cdigo abaixo:char c = 97; printf("%d %c\n",c,c);

Considerando a codificao de caracteres via tabela ASCII, a varivel c, que foi inicializada com o valor 97, representa o caractere a. A funo printf imprime o contedo da varivel c usando dois formatos distintos: com o especificador de formato para inteiro, %d, ser impresso o valor do cdigo numrico, 97; com o formato de caractere, %c, ser impresso o caractere associado ao cdigo, a letra a. Conforme mencionamos, devemos evitar o uso explcito de cdigos de caracteres. Para tanto, a linguagem C permite a escrita de constantes caracteres. Uma constante caractere escrita envolvendo o caractere com aspas simples. Assim, a expresso 'a' representa uma constante caractere e resulta no valor numrico associado ao caractere a. Podemos, ento, reescrever o fragmento de cdigo acima sem particularizar a tabela ASCII.char c = 'a'; printf("%d %c\n", c, c);

Alm de agregar portabilidade e clareza ao cdigo, o uso de constantes caracteres nos livra de conhecermos os cdigos associados a cada caractere. Independente da tabela de cdigos numricos utilizada, garante-se que os dgitos so codificados em seqncia. Deste modo, se o dgito zero tem cdigo 48, o dgito um tem obrigatoriamente cdigo 49, e assim por diante. As letras minsculas e as letras maisculas tambm formam dois grupos de cdigos seqenciais. O exemplo a seguir tira proveito desta seqncia dos cdigos de caracteres. Exemplo. Suponhamos que queremos escrever uma funo para testar se um caractere c um dgito (um dos caracteres entre '0' e '9'). Esta funo pode ter o prottipo:int digito(char c);

e ter como resultado 1 (verdadeiro) se c for um dgito, e 0 (falso) se no for. A implementao desta funo pode ser dada por:int digito(char c) { if ((c>='0')&&(cnome); printf("Matrcula: %d\n, tab[i]->mat); printf("Endereo: %s\n, tab[i]->end); printf("Telefone: %s\n, tab[i]->tel); } }

Por fim, podemos implementar uma funo que imprima os dados de todos os alunos da tabela:void imprime_tudo (void) { int i; for (i=0; i) para acess-los atravs de um ponteiro da unio. Assim, dada a declarao acima, podemos escrever:v.i = 10;

ouv.c = 'x';

Salientamos, no entanto, que apenas um nico elemento de uma unio pode estar armazenado num determinado instante, pois a atribuio a um campo da unio sobrescreve o valor anteriormente atribudo a qualquer outro campo.

7.6. Tipo enumerao**Uma enumerao um conjunto de constantes inteiras com nomes que especifica os valores legais que uma varivel daquele tipo pode ter. uma forma mais elegante de organizar valores constantes. Como exemplo, consideremos a criao de um tipo booleano. Variveis deste tipo podem receber os valores 0 (FALSE) ou 1 (TRUE). Poderamos definir duas constantes simblicas dissociadas e usar um inteiro para representar o tipo booleano:#define FALSE #define TRUE 0 1

typedef int Bool;

Desta forma, as definies de FALSE e TRUE permitem a utilizao destes smbolos no cdigo, dando maior clareza, mas o tipo booleano criado, como equivalente a um inteiro qualquer, pode armazenar qualquer valor inteiro, no apenas FALSE e TRUE, que seria mais adequado. Para validarmos os valores atribudos, podemos enumerar os valores constantes que um determinado tipo pode assumir, usando enum:enum bool { FALSE, TRUE }; typedef enum bool Bool;


7-10

Com isto, definimos as constantes FALSE e TRUE. Por default, o primeiro smbolo representa o valor 0, o seguinte o valor 1, e assim por diante. Poderamos explicitar os valores dos smbolos numa enumerao, como por exemplo:enum bool { TRUE = 1, FALSE = 0, };

No exemplo do tipo booleano, a numerao default coincide com a desejada (desde que o smbolo FALSE preceda o smbolo TRUE dentro da lista da enumerao). A declarao de uma varivel do tipo criado pode ser dada por

Documents

[Apostila]Estrutura de Dados - Waldemar Celes e José Lucas Rangel