Baixe o app para aproveitar ainda mais
Prévia do material em texto
ESTRUTURA DE DADOS I Professor Me. Rogério de Leon Pereira GRADUAÇÃO Unicesumar Reitor Wilson de Matos Silva Vice-Reitor Wilson de Matos Silva Filho Pró-Reitor de Administração Wilson de Matos Silva Filho Pró-Reitor de EAD Willian Victor Kendrick de Matos Silva Presidente da Mantenedora Cláudio Ferdinandi NEAD - Núcleo de Educação a Distância Direção Operacional de Ensino Kátia Coelho Direção de Planejamento de Ensino Fabrício Lazilha Direção de Operações Chrystiano Mincoff Direção de Mercado Hilton Pereira Direção de Polos Próprios James Prestes Direção de Desenvolvimento Dayane Almeida Direção de Relacionamento Alessandra Baron Head de Produção de Conteúdos Rodolfo Encinas de Encarnação Pinelli Gerência de Produção de Conteúdos Gabriel Araújo Supervisão do Núcleo de Produção de Materiais Nádila de Almeida Toledo Coordenador de Conteúdo Daniello Xavier Saes Qualidade Editorial e Textual Daniel F. Hey, Hellyery Agda Design Educacional Nádila de Almeida Toledo Fernando Henrique Mendes Rossana Costa Giani Iconografia Isabela Soares Silva Projeto Gráfico Jaime de Marchi Junior José Jhonny Coelho Arte Capa André Morais de Freitas Editoração Fernando Henrique Mendes Thayla Daiany Guimarães Cripaldi Revisão Textual Jaquelina Kutsunugi, Keren Pardini, Maria Fernanda Canova Vasconcelos, Nayara Valenciano, Rhaysa Ricci Correa e Susana Inácio Ilustração Robson Yuiti Saito C397 CENTRO UNIVERSITÁRIO DE MARINGÁ. Núcleo de Educação a Distância; PEREIRA, Rogério de Leon. Estrutura de Dados I. Rogério de Leon Pereira. (Reimpressão revista e atualizada) Maringá-Pr.: UniCesumar, 2016. 156 p. “Graduação - EaD”. 1. Sistemas numéricos. 2. Vetores e matrizes. 3. Ponteiros. 4. EaD. I. Título. ISBN 978-85-8084-579-2 CDD - 22 ed. 005.73 CIP - NBR 12899 - AACR/2 Ficha catalográfica elaborada pelo bibliotecário João Vivaldo de Souza - CRB-8 - 6828 Viver e trabalhar em uma sociedade global é um grande desafio para todos os cidadãos. A busca por tecnologia, informação, conhecimento de qualidade, novas habilidades para liderança e so- lução de problemas com eficiência tornou-se uma questão de sobrevivência no mundo do trabalho. Cada um de nós tem uma grande responsabilida- de: as escolhas que fizermos por nós e pelos nos- sos fará grande diferença no futuro. Com essa visão, o Centro Universitário Cesumar – assume o compromisso de democratizar o conhe- cimento por meio de alta tecnologia e contribuir para o futuro dos brasileiros. No cumprimento de sua missão – “promover a educação de qualidade nas diferentes áreas do conhecimento, formando profissionais cidadãos que contribuam para o desenvolvimento de uma sociedade justa e solidária” –, o Centro Universi- tário Cesumar busca a integração do ensino-pes- quisa-extensão com as demandas institucionais e sociais; a realização de uma prática acadêmica que contribua para o desenvolvimento da consci- ência social e política e, por fim, a democratização do conhecimento acadêmico com a articulação e a integração com a sociedade. Diante disso, o Centro Universitário Cesumar al- meja ser reconhecida como uma instituição uni- versitária de referência regional e nacional pela qualidade e compromisso do corpo docente; aquisição de competências institucionais para o desenvolvimento de linhas de pesquisa; con- solidação da extensão universitária; qualidade da oferta dos ensinos presencial e a distância; bem-estar e satisfação da comunidade interna; qualidade da gestão acadêmica e administrati- va; compromisso social de inclusão; processos de cooperação e parceria com o mundo do trabalho, como também pelo compromisso e relaciona- mento permanente com os egressos, incentivan- do a educação continuada. Seja bem-vindo(a), caro(a) acadêmico(a)! Você está iniciando um processo de transformação, pois quan- do investimos em nossa formação, seja ela pessoal ou profissional, nos transformamos e, consequente- mente, transformamos também a sociedade na qual estamos inseridos. De que forma o fazemos? Criando oportunidades e/ou estabelecendo mudanças capa- zes de alcançar um nível de desenvolvimento compa- tível com os desafios que surgem no mundo contem- porâneo. O Centro Universitário Cesumar mediante o Núcleo de Educação a Distância, o(a) acompanhará durante todo este processo, pois conforme Freire (1996): “Os homens se educam juntos, na transformação do mundo”. Os materiais produzidos oferecem linguagem dialó- gica e encontram-se integrados à proposta pedagó- gica, contribuindo no processo educacional, comple- mentando sua formação profissional, desenvolvendo competências e habilidades, e aplicando conceitos teóricos em situação de realidade, de maneira a inse- ri-lo no mercado de trabalho. Ou seja, estes materiais têm como principal objetivo “provocar uma aproxi- mação entre você e o conteúdo”, desta forma possi- bilita o desenvolvimento da autonomia em busca dos conhecimentos necessários para a sua formação pes- soal e profissional. Portanto, nossa distância nesse processo de cres- cimento e construção do conhecimento deve ser apenas geográfica. Utilize os diversos recursos peda- gógicos que o Centro Universitário Cesumar lhe possi- bilita. Ou seja, acesse regularmente o AVA – Ambiente Virtual de Aprendizagem, interaja nos fóruns e en- quetes, assista às aulas ao vivo e participe das discus- sões. Além disso, lembre-se que existe uma equipe de professores e tutores que se encontra disponível para sanar suas dúvidas e auxiliá-lo(a) em seu processo de aprendizagem, possibilitando-lhe trilhar com tranqui- lidade e segurança sua trajetória acadêmica. Diretoria Operacional de Ensino Diretoria de Planejamento de Ensino Professor Me. Rogério de Leon Pereira Possui graduação em Tecnologia em Processamento de Dados pelo Centro de Ensino Superior de Maringá (1999) e mestrado em Ciência da Computação pela Universidade Estadual de Maringá (2006). Atualmente é analista de informática da Universidade Estadual de Maringá. Tem experiência na área de Ciência da Computação, com ênfase em desenvolvimento de sistemas Web. A U TO R SEJA BEM-VINDO(A)! Recebi a proposta de elaborar o material que você carrega em suas mãos sobre Estru- tura de Dados, conteúdo de extrema importância que liga o conhecimento obtido na matéria de algoritmos com as disciplinas técnicas de programação que você verá até o final do seu curso. Quando falamos em Estrutura de Dados, estamos falando da forma como os dados são armazenados e manipulados no computador. Falamos também das técnicas para inclu- são, acesso, alteração e exclusão destes dados. Na década de 1980, quando eu jogava videogame (ATARI 2600) com o meu irmão mais velho, Ricardo, ele sempre dizia: “Como é que um monte de 1s e 0s pode ser tão legal?”. Essa pergunta me intrigou por muito tempo, mas a resposta você encontrará neste li- vro. Como veremos nas páginas a seguir, de nada importa as sequências de 1s e 0s que o computador carrega na memória, seja na primária ou na secundária, elas não têm significado algum se não forem determinadas regras de como essas informações serão analisadas. Na Unidade I, veremos os principais sistemas numéricos utilizados na computação: deci- mal, binário e hexadecimal, conteúdo já visto na disciplina de Fundamentos e Arquitetu- ras de Computadores. Seu entendimento é de supraimportância para o aprendizado do conteúdo deste livro. Também serão revistas as definições de variáveis unidimensionais contidas na disciplina de Algoritmos e Lógica de Programação II e a forma como elas são estruturadas na memória do computador. Passando para a Unidade II, completaremos a revisão vendo as variáveis multidimensio- nais. Com esse conteúdo aprendido, já veremos as duas primeiras estruturas: a Fila e a Pilha.O próximo passo será estudar o conteúdo considerado, por muitos, um dos mais difíceis na área de programação, que é o conceito de Ponteiros. Em seguida, veremos a aplicação e o uso dos Ponteiros na criação de listas dinâmicas, que é uma alternativa muito interessante à forma estática criada com as variáveis mul- tidimensionais. Para o encerramento do conteúdo, foi reservado na Unidade V um espaço para falar sobre Grafos, uma estrutura muito utilizada em vários níveis de programação, e também sobre algumas técnicas para trabalhar com eles. Lembre-se que o curso de graduação é criado seguindo um processo lógico e estru- turado de formação do conhecimento. Você já aprendeu sobre os sistemas numéricos na disciplina de Fundamentos e Arquitetura de Computadores e sobre variáveis na de Algoritmos e Lógica de Programação. O que veremos aqui, neste livro, é uma sequência desse conteúdo e a sua aplicação, que servirá de base para as próximas disciplinas de cunho técnico do seu curso e para a sua formação como profissional de Tecnologia da Informação. APRESENTAÇÃO ESTRUTURA DE DADOS I 8 - 9 SUMÁRIO 8 - 9 UNIDADE I SISTEMAS NUMÉRICOS E ALOCAÇÃO DE MEMÓRIA 15 Introdução 16 Sistema Decimal 19 Sistema Binário 21 Representação de Decimal em Binário 23 Sistema Hexadecimal 26 Estrutura de Dados 28 Tipos De Variáveis E Alocação Na Memória 29 Números Inteiros 31 Números Reais 33 Considerações Finais UNIDADE II PILHAS E FILAS 39 Introdução 39 Estruturas Homogêneas e Heterogêneas 40 Vetores e Matrizes 41 Registros 42 Pilhas 53 Filas 62 Considerações Finais SUMÁRIO 10 - 11 UNIDADE III PONTEIROS 69 Introdução 69 Ponteiros 76 Propriedades de Ponteiros 77 Alocação Dinâmica na Memória 82 Criando Vetores Dinâmicos 84 Considerações Finais UNIDADE IV LISTAS DINÂMICAS 91 Introdução 91 Fundamentos de Listas Dinâmicas 94 Implementando uma Lista Dinâmica 101 Lista Dinâmica com Forma de Pilha 104 Lista Dinâmica com Forma de Fila 108 Considerações Finais SUMÁRIO 10 - 11 UNIDADE V GRAFOS 113 Introdução 113 Sete Pontes de Königsberg 116 Teoria dos Grafos 117 Grafos como Representação de Problemas 118 Representação Computacional de Grafos 122 Implementando Grafos em C 129 Considerações Finais 131 CONCLUSÃO 133 REFERÊNCIAS 135 GABARITO 155 ANEXO U N ID A D E I Professor Me. Rogério de Leon Pereira SISTEMAS NUMÉRICOS E ALOCAÇÃO DE MEMÓRIA Objetivos de Aprendizagem ■ Conhecer os principais sistemas numéricos utilizados na computação: decimal, binário e hexadecimal. ■ Aprender a relação e a conversão de valores entre diferentes sistemas numéricos. ■ Conhecer os principais tipos de variáveis. ■ Entender como os dados das variáveis são armazenados na memória. Plano de Estudo A seguir, apresentam-se os tópicos que você estudará nesta unidade: ■ Sistema decimal ■ Sistema binário ■ Representação de decimal em binário ■ Sistema hexadecimal ■ Estrutura de dados ■ Tipos de variáveis e alocação na memória ■ Números inteiros ■ Números reais 14 - 15 INTRODUÇÃO Números são sequências ordenadas de algarismos que têm seu valor determi- nado pela posição de seus elementos e de sua base numérica. Parece complicado, mas não é. Estamos acostumados a trabalhar em ape- nas uma base numérica, a Decimal. Nesta unidade veremos mais a fundo como funcionam diferentes sistemas numéricos como o Binário, o Hexadecimal e suas aplicações. Compreendendo melhor os sistemas numéricos, passaremos a estudar como os dados são armazenados na memória. Isso é importante para entender como funcionam as estruturas de dados mais simples, que são as variáveis. As informações estão armazenadas na memória do computador, mas para decifrá-las é preciso saber qual é a sua estrutura. Um grupo de bits pode ser inter- pretado de diversas maneiras diferentes. É como ler um livro em outro idioma sem o respectivo dicionário. Você até reconhece as letras, mas não sabe qual grupo forma qual vocábulo, qual o seu som e significado. Parte desse conteúdo não é novidade, já foi visto na disciplina de Fundamentos e Arquitetura de Computadores e na de Algoritmos e Lógica de Programação II. E você não irá parar por aí, porque o que aprendermos agora será utilizado mais à frente no seu curso em outras disciplinas correlatas. ©shutterstock 14 - 15 Introdução Re pr od uç ão p ro ib id a. A rt . 1 84 d o Có di go P en al e L ei 9 .6 10 d e 19 d e fe ve re iro d e 19 98 . SISTEMA DECIMAL Você pode até não ter ouvido falar do Sistema de Numeração de Base 10, ou Sistema Decimal, mas com certeza o conhece há muito tempo, pois é nesse sis- tema que aprendemos a contar os números e realizar as mais básicas operações algébricas: adição, subtração, multiplicação e divisão. Os algarismos no sistema decimal podem assumir apenas dez valores, do 0 ao 9, daí a origem de seu nome. Da mesma forma, é dito que é um sistema de base dez, pois todos os seus números são formados por algarismos que podem assumir apenas dez valores distintos. A representação formal de um número pode ser dada da seguinte forma: N = (An-1...Ap+2 Ap+1 Ap)B Onde: N = é o número a ser formado; A = são os algarismos que compõem o número N; p = posição do algarismo A no número N, iniciando-se em p = 0 na pri- meira posição à direita indo até p = n - 1, onde n é o número de algarismos que compõem o número; B = a base do número N, que no caso do sistema decimal é 10. O elemento A é uma variável e pode assumir diversos valores dentro do conjunto CD dos algarismos que compõem os números decimais, que pode ser representado na seguinte forma: ©shutterstock 16 - 17 SISTEMAS NUMÉRICOS E ALOCAÇÃO DE MEMÓRIA Reprodução proibida. A rt. 184 do Código Penal e Lei 9.610 de 19 de fevereiro de 1998. I ©shutterstock 16 - 17 Sistema Decimal Re pr od uç ão p ro ib id a. A rt . 1 84 d o Có di go P en al e L ei 9 .6 10 d e 19 d e fe ve re iro d e 19 98 . CD = (0,1,2,3,4,5,6,7,8,9) O valor de cada um dos algarismos tem a sua relevân- cia dada pela posição que ocupa no número. Como estamos trabalhando no sistema decimal, cada componente será mul- tiplicado por uma potência de base 10 com expoente relativo a sua posição no número. N=A*10n-1+...+A*10p+2+A*10p+1+A*10p Assim, podemos dizer que um número no sistema deci- mal é o somatório da multiplicação dos seus elementos por uma potência de base 10 elevada ao índice da sua posição de relevância. Por questões acadêmicas, faz-se necessário o uso da notação formal. Porém, por se tratar de um material especialmente preparado para o uso em autoestudo, é preciso que tal infor- mação seja abstraída para uma linguagem mais coloquial. A melhor forma de realizar isso é por meio de exemplos. Exemplo 1: calcule o valor do número 12345 na base decimal. Sabemos que a representação numérica de N é dada pelo número 12345, ou seja: N = 12345 Como já foi dito, o valor dele deverá ser calculado no sistema de base 10 (decimal). Assim: N = (12345)10 Pela definição apresentada, o valor de N é o somatório da multiplicação de seus elementos pela potência de base 10 elevada ao expoente p, onde p é a posição do algarismo no número, contando-se da direita para a esquerda inician- do-se com 0. N = 1*104 + 2*103 + 3*102 + 4*101 + 5*100 18 - 19 SISTEMAS NUMÉRICOS E ALOCAÇÃO DE MEMÓRIA Reprodução proibida. A rt. 184 do Código Penal e Lei 9.610 de 19 de fevereiro de 1998. I Calculandoas potências, temos: N = 1*10000 + 2*1000 + 3*100 + 4*10 + 5*1 Realizando as multiplicações: N = 10000 + 2000 + 300 + 40 + 5 E, por último, a soma dos elementos já calculados: N=12345 Exemplo 2: calcule o valor do número 54321 na base decimal. N = 54321 N = (54321)10 N = 5*104 + 4*103 + 3*102 + 2*101 + 1*100 N = 5*10000 + 4*1000 + 3*100 + 2*10 + 1*1 N = 50000+4000+300+20+1 N = 54321 Exemplo 3: calcule o valor do número 42 na base decimal. N = 42 N = (42)10 N = 4*101+2*100 N = 4*10+2*1 N = 40+2 N=42 Parece óbvio dizer que o número 42 na base decimal equivale a 42, mas isso se dá porque estamos trabalhando com um sistema numérico que já é utilizado diversas vezes durante o dia. O importante é saber como é realizado o cálculo de um número de forma posicional, o que será útil para entender o funciona- mento em sistemas que não utilizam a base 10. Dois números em bases diferentes podem ter valores distintos mesmo pos- suindo os mesmos algarismos nas mesmas posições. ©shutterstock 18 - 19 Sistema Binário Re pr od uç ão p ro ib id a. A rt . 1 84 d o Có di go P en al e L ei 9 .6 10 d e 19 d e fe ve re iro d e 19 98 . SISTEMA BINÁRIO Esse com certeza você já deve ter ouvido falar. Ele utiliza apenas dois valores, 0 e 1, e é amplamente utilizado tanto para o armazenamento físico das informa- ções quanto para os cálculos realizados dentro do núcleo do processador. Não importa o que você está vendo nesse exato momento: figuras, desenhos, letras ou números decimais, até mesmo ouvindo uma música no computador, celular ou MP3 player. Internamente é tudo representado por uma sequência de alga- rismos 0 e 1. Voltando à notação formal já utilizada na representação do sistema deci- mal, vamos aplicá-la agora para entender melhor a composição de um número no sistema binário. N = (An-1...Ap+2 Ap+1Ap)B Diferente do sistema decimal que possuía base 10, o sistema binário possui apenas dois valores (base 2). Assim o conjunto CD de elementos que represen- tam os possíveis valores do algarismo A é: CD = (0,1) 20 - 21 SISTEMAS NUMÉRICOS E ALOCAÇÃO DE MEMÓRIA Reprodução proibida. A rt. 184 do Código Penal e Lei 9.610 de 19 de fevereiro de 1998. I Como já apresentado anteriormente, o valor de cada um dos algarismos tem a sua relevância dada pela posição que ocupa no número. No caso do sistema binário, cada componente será multiplicado por uma potência de base 2 com expoente relativo a sua posição no número. N = A*2n-1 +...+ A*2p+2 + A*2p+1 + A*2p Novamente, podemos dizer que o valor de um número é o somatório da mul- tiplicação dos seus elementos por uma potência de base B elevada ao índice da sua posição de relevância. No caso do sistema binário, o valor de B = 2 (base 2): Note que a forma de encontrar o valor de um número no sistema binário é similar à utilizada para encontrar o valor de um número no sistema decimal, diferen- ciando-se apenas pelo valor da base B e do conjunto CD de possíveis valores do elemento A. Vamos ver agora alguns exemplos de como calcular o valor de um número representado no sistema binário. Exemplo 1: calcule o valor decimal do número 101010 na base binária. Sabemos que a representação numérica de N é dada pelo número 101010, ou seja: N=101010 Como já foi dito, o valor dele deverá ser calculado no sistema de base 2 (binário). Assim: N=(101010)2 Pela definição apresentada, o valor de N é o somatório da multiplicação de seus elementos pela potência de base 2 elevada ao expoente p, onde p é a posição do algarismo no número, contando-se da direita para a esquerda, iniciando-se com 0. N = 1*25 + 0*24 + 1*23 + 0*22 + 1*21 + 0*20 Calculando as potências, temos: N = 1*32+0*16+1*8+0*4+1*2+0*1 20 - 21 Representação de Decimal em Binário Re pr od uç ão p ro ib id a. A rt . 1 84 d o Có di go P en al e L ei 9 .6 10 d e 19 d e fe ve re iro d e 19 98 . Realizando as multiplicações: N = 32+8+2 E, por último, a soma dos elementos já calculados: N=42 Exemplo 2: calcule o valor decimal do número 1101 na base binária. N= 1101 N= (1101)2 N= 1*23 + 1*22 + 0*21 + 1*20 N= 1*8 + 1*4 + 0*2 + 1*1 N=8+4+1 N=13 REPRESENTAÇÃO DE DECIMAL EM BINÁRIO No sistema decimal, a quantidade de números inteiros únicos possíveis se dá pela forma 10n, onde n é a quantidade de algarismos presentes no número. Dessa forma, um número decimal com apenas um algarismo pode formar 101 números: 101 = (0,1,2,3,4,5,6,7,8,9) Um número decimal com dois algarismos forma 102 combinações possíveis, ou seja, 100 números: 102 = (00,01,02,03,...,97,98,99) Analogamente, a quantidade de números formados no sistema binário se dá pela fórmula Bn, onde n é a quantidade de símbolos (algarismos) no número Um número binário que termina com 1 será sempre um valor decimal ímpar, já que a primeira posição à direita equivale a 20 = 1, e como todas as demais potências de 2 são números pares, qualquer número par acrescido de 1 será um número ímpar. 22 - 23 SISTEMAS NUMÉRICOS E ALOCAÇÃO DE MEMÓRIA Reprodução proibida. A rt. 184 do Código Penal e Lei 9.610 de 19 de fevereiro de 1998. I e B é a base do sistema, que no caso do binário B = 2 (base 2). Desse modo, um número binário com dois algarismos formará quatro valores: 22=(00,01,10,11) Assim, caso seja necessário representar todos os valores de um número deci- mal inteiro positivo de apenas um dígito (101), seriam necessários pelo menos 4 dígitos binários (24), conforme a tabela abaixo: DECIMAL BINÁRIO 0 0000 1 0001 2 0010 3 0011 4 0100 5 0101 6 0110 7 0111 8 1000 9 1001 Fonte: o autor Note que a quantidade de combinações possíveis para um número com 4 dígitos binários são 16, porém, apenas 10 são necessários para a representação de um algarismo decimal. Os números 1010, 1011, 1100, 1101, 1110 e 1111 acabam não sendo utilizados. É importante entender que uma mesma combinação de valo- res pode ter diversos significados diferentes, de acordo com as regras utilizadas para a sua interpretação. Isso ficará mais claro quando abordarmos o conceito de variáveis ainda nesta unidade. ©shutterstock 22 - 23 Sistema Hexadecimal Re pr od uç ão p ro ib id a. A rt . 1 84 d o Có di go P en al e L ei 9 .6 10 d e 19 d e fe ve re iro d e 19 98 . SISTEMA HEXADECIMAL O sistema de base 16 é o último que veremos dentro da disciplina de estrutura de dados. Ele também é muito utilizado na computação para a representação numérica. Por ser um sistema de base 16, os números hexadecimais são compos- tos por algarismos que podem assumir 16 valores diferentes, conforme exposto no conjunto CD abaixo: CD = (0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F) Onde a letra A representa o valor 10, a letra B o valor 11, a letra C o valor 12, e assim por diante, até a letra F, que representa o valor 15. O sistema hexadecimal é muito utilizado porque é considerado um interme- diário entre aquilo que estamos habituados a ver (números decimais) e aquilo com o que o computador trabalha internamente em nível de hardware (núme- ros binários). Outra justificativa se dá pela possibilidade de representar todos os símbolos hexadecimais em um número binário de 4 dígitos, diferente do que acontece quando tentamos representar um dígito decimal em binário. DECIMAL BINÁRIO HEXADECIMAL 0 0000 0 1 0001 1 2 0010 2 3 0011 3 4 0100 4 24 - 25 SISTEMAS NUMÉRICOS E ALOCAÇÃO DE MEMÓRIA Reprodução proibida. A rt. 184 do Código Penal e Lei 9.610 de 19 de fevereiro de 1998. I DECIMAL BINÁRIO HEXADECIMAL 5 0101 5 6 01106 7 0111 7 8 1000 8 9 1001 9 10 1010 A 11 1011 B 12 1100 C 13 1101 D 14 1110 E 15 1111 F Fonte: o autor Para saber o valor de um número hexadecimal, basta converter cada um dos alga- rismos de base 16 para base 2 e o resultado final em base 10. Vamos ver agora alguns exemplos de como calcular o valor de um número representado no sis- tema hexadecimal. Exemplo 1: calcule o valor decimal do número F2 na base hexadecimal. Isolando cada um dos algarismos, podemos formar a seguinte tabela: HEXADECIMAL DECIMAL BINÁRIO F 15 1111 2 2 0010 24 - 25 Sistema Hexadecimal Re pr od uç ão p ro ib id a. A rt . 1 84 d o Có di go P en al e L ei 9 .6 10 d e 19 d e fe ve re iro d e 19 98 . Agrupando agora os valores binários dos dígitos hexadecimais, temos: N=(11110010)2 O valor de N é o somatório da multiplicação de seus elementos pela potên- cia de base 2 elevada ao expoente p, onde p é a posição do algarismo no número, contando-se da direita para a esquerda, iniciando-se com 0. N = 1*27 + 1*26 + 1*25 + 1*24 + 0*23 + 0*22 + 1*21 + 0*20 Calculando as potências, temos: N = 1*128 + 1*64 + 1*32 + 1*16 + 0*8 + 0*4 + 1*2 + 0*1 Realizando as multiplicações: N = 128 + 64 + 32 + 16 + 2 E, por último, a soma dos elementos já calculados: N = 242 Exemplo 2: calcule o valor decimal do número 1A na base hexadecimal. HEXADECIMAL DECIMAL BINÁRIO 1 1 0001 A 10 1010 N= (00011010)2 N= 0*27+0*26+0*25+1*24+1*23+0*22+1*21+0*20 N= 0*128 + 0*64 + 0*32 + 1*16 + 1*8 + 0*4 + 1*2 + 0*1 N= 16+8+2 N= 26 © sh ut te rs to ck 26 - 27 SISTEMAS NUMÉRICOS E ALOCAÇÃO DE MEMÓRIA Reprodução proibida. A rt. 184 do Código Penal e Lei 9.610 de 19 de fevereiro de 1998. I ESTRUTURA DE DADOS Digamos que você está acessando a memória do com- putador e encontra um agrupamento de 24 bits na seguinte configuração: 0011 1011 0010 1101 0010 1001 O que significa essa string binária (sequência de 1s e 0s)? A resposta correta é: qual a estrutura do dado? Você pode ter se perguntado por que fizemos uma revisão sobre os sistemas numéricos e outros conceitos já vistos em disciplinas anteriores. Também ficou curioso(a) em saber o que é a tão falada estrutura de dados que até agora não ficou claro. Prepare-se, pois em alguns minutos você dirá: “agora as coisas começam a fazer sentido”. Nós temos essa string binária, mas não sabemos como é a sua estrutura, então, esse mesmo dado pode ser lido de inúmeras maneiras diferentes. Vamos considerar que cada conjunto de 8 bits representa um valor decimal. 0011 1011 0010 1101 0010 1001 N1 N2 N3 Assim, para o primeiro grupo N1: N1= (0011 1011)2 N1= 0*27 + 0*26 + 1*25 + 1*24 + 1*23 + 0*22 + 1*21 + 1*20 N1= 0*128 + 0*64 + 1*32 + 1*16 + 1*8 + 0*4 + 1*2 + 1*1 N1= 32+16+8+2+1 N1= 59 Para o próximo grupo de 8 bits, N2: N2= (0010 1101)2 N2= 0*27+0*26+1*25+0*24+1*23+1*22+0*21+1*20 N2=0*128+0*64+1*32+0*16+1*8+1*4+0*2+1*1 N2= 32+8+4+1 N2= 45 26 - 27 Estrutura de Dados Re pr od uç ão p ro ib id a. A rt . 1 84 d o Có di go P en al e L ei 9 .6 10 d e 19 d e fe ve re iro d e 19 98 . E finalmente, para os últimos 8 bits, N3: N3= (0010 1001)2 N3= 0*27+0*26+1*25+0*24+1*23+0*22+0*21+1*20 N3= 0*128+0*64+1*32+0*16+1*8+0*4+0*2+1*1 N3= 32+8+1 N3= 41 Então, se interpretássemos a string de bits 0011 1011 0010 1101 0010 1001 como três agrupamentos de 8 bits, o resultado seria a sequência de números: 59, 45 e 41. Note que a sequência de números apresentados é diferente do número decimal 594541. Porém, como não sabemos qual é a estrutura do dado, podemos ler a mesma string de outras formas. E se cada grupo de 4 bits representar um número hexade- cimal? Qual seria o resultado? Vamos usar uma tabela para facilitar a conversão: BINÁRIO 0011 1011 0010 1101 0010 1001 DECIMAL 3 11 2 13 2 9 HEXADECIMAL 3 B 2 D 2 9 Temos que a string de bits 0011 1011 0010 1101 0010 1001 em hexadecimal equi- vale a 3B2D29, usando a regra de que cada 4 bits formam 1 caractere de base 16. Eu sei que cada dois caracteres hexadecimais podem formar 162 combinações possíveis, ou seja, 256 números, que é a quantidade de caracteres existentes na Tabela ASC II e sua extensão. Digamos então que eu deseje olhar na tabela e ver qual o caractere para cada grupo de dois dígitos em base 16. O resultado seria: HEXADECIMAL 3B 2D 29 TABELA ASC II ; - ) Vamos analisar agora todas as formas que encontramos para interpretar o mesmo valor. Lembre-se que como não sabemos como o dado foi estruturado na memó- ria, existem ainda outras possibilidades de análise. ©shutterstock 28 - 29 SISTEMAS NUMÉRICOS E ALOCAÇÃO DE MEMÓRIA Reprodução proibida. A rt. 184 do Código Penal e Lei 9.610 de 19 de fevereiro de 1998. I Binário 0011 1011 0010 1101 0010 1001 Decimal, em grupo de 8 bits 59 45 41 Hexadecimal, em grupo de 4 bits 3B 2D 29 Hexadecimal, convertido pela tabela ASC II ;-) Agora ficou claro que não basta apenas ler a memória, é preciso saber como as informações armazenadas foram estruturadas para então fazer a correta inter- pretação de seus valores. Você encontrará a Tabela ASC II e a sua extensão no final deste livro. TIPOS DE VARIÁVEIS E ALOCAÇÃO NA MEMÓRIA Para esta disciplina, escolhemos a Linguagem C, que foi a mesma adotada na disciplina de Algoritmos e Lógica de Programação II. Dessa forma, esperamos que o aluno possa entrar direto no entendimento do conteúdo sem muita neces- sidade de estudo aprofundado da sintaxe. O C é uma linguagem de tipagem forte, ou seja, todas as variáveis precisam ter um tipo definido. Outras linguagens como o Clipper e o PHP possuem tipagem fraca, as variáveis são criadas sem definição e podem assumir qualquer valor. Existem 7 tipos de variáveis na linguagem C e eles ainda permitem o uso de modificadores como signed, unsigned, short, long etc. Quando falamos em tipo, O número representado por 11 pode possuir diferentes significados. Se for na base hexadecimal, o número 11 equivale a 17 decimal. Se for na base binária, o número 11 representa o 3 decimal. 28 - 29 Números Inteiros Re pr od uç ão p ro ib id a. A rt . 1 84 d o Có di go P en al e L ei 9 .6 10 d e 19 d e fe ve re iro d e 19 98 . falamos da estrutura da variável. É o conjunto de regras que determina como ela deve ser lida e como as operações matemáticas são realizadas. Observe o seguinte trecho de código: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 #include <stdio.h> #include <stdlib.h> int i, j, k; float l, m, n; int main() { i = 1; j = 2; k = i + j; l = 1; m = 2; n = l + m; printf(“ k = %d\n n = %f\n”, k, n); system(“pause”); return(0); } Tanto o valor da variável k quanto o valor da variável n são obtidos por meio da atribuição de uma soma de duas outras variáveis. Apesar de ambos os casos utilizarem o mesmo símbolo de operação (+), a forma como o cálculo é reali- zado internamente é diferente. O compilador sabe que a estrutura de números inteiros é diferente da estrutura de números reais e que para cada caso a mesma operação (adição) precisa ser realizada de acordo com as regras definidas pelo tipo da variável. NÚMEROS INTEIROS Um número inteiro positivo utiliza todos os bits para compor seu valor. Assim, um número com n bits tem 2n valores possíveis. Para ficar mais fácil o entendi- mento, vamos imaginar um número inteiro positivo com 8 bits (n = 8). Aplicando 30 - 31 SISTEMAS NUMÉRICOS E ALOCAÇÃO DE MEMÓRIA Reprodução proibida. A rt. 184 do Código Penal e Lei 9.610 de19 de fevereiro de 1998. I a regra de 2n com n = 8, temos: 28= 256 Então o intervalo de números inteiros positivos válidos com 8 bits vai de 0 (0000 0000) a 255 (1111 1111). Segundo Tenenbaum (1995), existem várias formas de representar números inteiros negativos. As duas principais são o Complemento de 1 e o Complemento de 2. No Complemento de 1, o primeiro bit a partir da esquerda (a maior potência de 2) é reservado como identificador de sinal no número. Para um inteiro com n bits, os n - 1 bits restantes são usados para a representação de valor. Uma sequência de bits começando por 0 representa um número positivo e uma sequência de bits começando por 1 representa um valor negativo. O número negativo é obtido invertendo o valor de todos os bits. Exemplo: O número 42 é representado por: 0 0 1 0 1 0 1 0 Para encontrar o seu valor negativo (-42) usando o modo Complemento de 1 basta inverter o valor de todos os seus bits: 1 1 0 1 0 1 0 1 As possíveis representações de números vão de -(2n-1 - 1) a +(2n-1 - 1). Em um número inteiro com 8 bits, os valores variam de -127 a +127. Essa notação per- mite a existência de duas representações para o número 0. O zero positivo 0000 0000 e o zero negativo 1111 1111. Na notação Complemento de 2, o valor 1 é somado na notação Complemento de 1 de um número negativo. Por exemplo, o número 42 é representado por 0010 1010 e o seu Complemento de 1 é encontrado invertendo o valor de todos os bits ficando 1101 0101, representando -42. Na notação Complemento de 2 basta somar 1 ao número negativo encontrado no Complemento de 1, que é 1101 0110. Nessa notação, as possíveis representações variam de -(2n-1) a +(2n-1 - 1). Pensando em um número inteiro de 8 bits, os valores variam de -128 a +127. Isso acontece porque há apenas uma única representação para o número 0, que é 0000 0000. Achando o Complemento de 1 do número 0 encontramos 1111 30 - 31 Números Reais Re pr od uç ão p ro ib id a. A rt . 1 84 d o Có di go P en al e L ei 9 .6 10 d e 19 d e fe ve re iro d e 19 98 . 1111 e somando-se 1 a esse valor obtemos 1 0000 0000. Como o resultado tem 9 bits, o nono bit é descartado ficando apenas 0000 0000. NÚMEROS REAIS O conjunto dos números reais é formado por números com casas decimais além dos já conhecidos números inteiros. Assim, todo número inteiro é um número real, mas nem todo número real é um número inteiro. O 42 é um número inteiro e também um número pertencente ao conjunto dos números reais. O número 4,2 é um número real, mas não inteiro. Se em um programa for necessário controlar a quantidade de produtos em estoque e os produtos não são fracionados, usa-se um número inteiro. Para guar- dar o preço do produto, é indicado um número real, já que alguns preços podem ser quebrados com complemento em centavos de reais. Na computação, a forma mais utilizada para a representação de números reais é a notação de ponto flutuante. Segundo Tenenbaum (1995), existem vários tipos de notação de ponto flutuante, cada qual com características próprias. O conceito é que a representação de um número real se dá por um número, cha- mado mantissa (M), multiplicado por uma base (B) elevada a uma potência com expoente (E) inteiro. M * BE Vamos considerar, por exemplo, o número real 123,45 e que para represen- tá-lo como ponto flutuante a base seja fixada em 10 (B=10). A notação ficaria: 12345 * 10-2 Como 10-2 = 0,01, então 12345 * 0,01 = 123,45. Note que o número (mantissa) Quando o primeiro bit da esquerda de uma variável numérica for 1, significa que o número é negativo desde que a variável suporte valores menores do que zero (signed). 32 - 33 SISTEMAS NUMÉRICOS E ALOCAÇÃO DE MEMÓRIA Reprodução proibida. A rt. 184 do Código Penal e Lei 9.610 de 19 de fevereiro de 1998. I é fixo e que a casa decimal (vírgula) “flutua” no número uma quantidade de alga- rismos definida pela potência formada pela base elevada ao expoente. A notação de ponto flutuante pode variar de acordo com a arquitetura do hardware ou das regras definidas pelo compilador. O número 1000, por exemplo, pode ser escrito como 1000*100, 100 *101, 10*102 ou 1*103. O mais usualmente utilizado para representar um número real é uma string de 32 bits, sendo os pri- meiros 24 bits reservados para a mantissa e os últimos 8 para o expoente, com a base fixa em 10. A representação em binário de 24 bits do número decimal inteiro 12345 é 0000 0000 0011 0000 0011 1001, e a representação em complemento de 2 em 8 bits de -2 é 1111 1110. Seguindo esses conceitos, a representação de 123,45 se dá pela seguinte string de 32 bits: 0000 0000 0011 0000 0011 1001 1111 1110 Vejamos alguns exemplos de números em notação de ponto flutuante: 10 0000 0000 0000 0000 0000 1010 0000 0000 100 0000 0000 0000 0000 0110 0100 0000 0000 1000 0000 0000 0000 0011 1110 1000 0000 0000 0,001 0000 0000 0000 0000 0000 0001 1111 1101 10421,12 0000 1111 1110 0110 1100 0000 1111 1110 A vantagem da notação de ponto flutuante é que ela permite a representação de valores absolutos muito grandes ou muito pequenos. Na notação descrita nesta unidade, o maior número que pode ser representado é 223-1 *10127, que é um número muito grande, e o menor é 10-128, que é um número muito pequeno. O limitante com o qual os números podem ser escritos está diretamente rela- cionado à quantidade de bits significativos na mantissa. Nem todo número entre o intervalo do menor e do maior podem ser representados. No formato aqui utilizado, 24 bits são reservados para a mantissa, sendo o primeiro usado para identificar se ele é positivo ou negativo, restando apenas 23 bits significativos. Dessa forma, o número 10 milhões e 1 (que exige 24 dígitos binários significa- tivos na mantissa) precisa ser aproximado para 10 milhões, (1*107) que exige apenas um único dígito de significância. ©shutterstock 32 - 33 Considerações Finais Re pr od uç ão p ro ib id a. A rt . 1 84 d o Có di go P en al e L ei 9 .6 10 d e 19 d e fe ve re iro d e 19 98 . CONSIDERAÇÕES FINAIS A grande maioria dos profissionais que trabalham com computador tem uma visão de alto nível do que acontece, ou seja, veem e interagem apenas com o resultado do processo, sem ter acesso e conhecimento de como ele se desenvolve. Nesta unidade, você teve a oportunidade de observar melhor como as coi- sas acontecem em baixo nível, no nível em que o computador trabalha. Agora quando você for criar um programa e definir uma variável, você com certeza irá lembrar que ela não é só um espaço reservado na memória, ela é uma estrutura que define como aquelas informações serão lidas e trabalhadas. Para poder trabalhar com estruturas de dados mais complexos, precisamos primeiramente ver as estruturas mais simples, e para isso é necessário saber como as informações são representadas nos principais sistemas numéricos. Esse foi o objetivo desta unidade. Na próxima unidade começaremos fazendo um pequeno resumo sobre vari- áveis para armazenamento de valores múltiplos que são os vetores, matrizes e registros. Em seguida, aplicaremos o que foi visto até o momento e apresentare- mos duas das mais simples e mais importantes estrutura de dados: pilhas e filas. <http://youtube.com.br/watch?v=ntylzQWvzCA>. <http://youtube.com.br/watch?v=TsoXOQ8ZEa0>. <http://pontov.com.br/site/index.php/cpp/41-visual-c/59-como-utilizar-o-visual-c-parte-1>. <http://pontov.com.br/site/index.php/ cpp/41-visual-c/72-como-utilizar-o-visual-studio-c-parte-2>. <http://pontov.com.br/site/index.php/ cpp/41-visual-c/73-como-utilizar-o-visual-studio-c-parte-3>. 34 - 35 1. Uma string de 8 bits pode conter diversos tiposde dados diferentes. Conside- rando que as strings a seguir possuam um valor decimal inteiro positivo ou dois números em hexadecimal de 4 bits cada, efetue a conversão conforme o exem- plo da letra a: a) 1010 1010 Para encontrar o valor em decimal de uma sequência de bits, basta somar as potên- cias de 2 elevado à posição de relevância do bit, para os bits de valor 1. 1 * 2 7 1 * 128 128 0 * 2 6 0 * 64 0 1 * 2 5 1 * 32 32 0 * 2 4 0 * 16 0 1 * 2 3 1 * 8 8 0 * 2 2 0 * 4 0 1 * 2 1 1 * 2 2 0 * 2 0 0 * 1 0 Total 170 Para encontrar o valor hexadecimal, basta calcular o valor decimal de cada grupo de 4 bits e comparar com o conjunto de valores em hexadecimal (de 0 a F). BINÁRIO DECIMAL HEXADECIMAL 1010 10 A 1010 10 A Resposta: Binário = 1010 1010 Decimal = 170 Hexadecimal = AA a) 1100 0011 b) 1100 1100 c) 1101 1111 d) 0000 1000 34 - 35 2. Encontre o valor decimal, o número negativo em Complemento de 1 e Comple- mento de 2 das strings de bits a seguir, conforme o exemplo da letra a: a) 0010 1010 Para encontrar o valor em decimal de uma sequência de bits, basta somar as potên- cias de 2 elevado à posição de relevância do bit, para os bits de valor 1. 0 * 2 7 0 * 128 0 0 * 2 6 0 * 64 0 1 * 2 5 1 * 32 32 0 * 2 4 0 * 16 0 1 * 2 3 1 * 8 8 0 * 2 2 0 * 4 0 1 * 2 1 1 * 2 2 0 * 2 0 0 * 1 0 Total 42 Para encontrar o Complemento de 1 de uma string de bits, basta inverter o valor de todos os seus bits. 42 0 0 1 0 1 0 1 0 -42 (Complemento de 1) 1 1 0 1 0 1 0 1 Para encontrar o Complemento de 2, basta somar 1 ao Complemento de 1 do número. -42 (Complemento de 2) 1 1 0 1 0 1 1 0 a) 0111 1111 b) 0000 0000 c) 0110 0011 d) 0101 1010 36 - 37 3. Sempre que uma string de bits contiver o valor 1 no primeiro bit da direita o número será ímpar? Por quê? 4. Sempre que uma string de bits contiver o valor 1 no primeiro bit da esquerda o número será negativo? Por quê? 36 - 37 U N ID A D E II Professor Me. Rogério de Leon Pereira PILHAS E FILAS Objetivos de Aprendizagem ■ Relembrar o conceito de variáveis heterogêneas. ■ Revistar a estrutura de vetores e matrizes. ■ Criar novos tipos de estruturas usando registros. ■ Aprender sobre pilhas e filas. Plano de Estudo A seguir, apresentam-se os tópicos que você estudará nesta unidade: ■ Estruturas homogêneas e heterogêneas ■ Vetores e matrizes ■ Registros ■ Pilhas ■ Filas 38 - 39 INTRODUÇÃO Faremos agora uma pequena e breve revisão sobre estruturas homogêneas e hete- rogêneas. Isso se faz necessário porque elas são a base para a criação de estruturas mais complexas como as filas e pilhas. Tanto a fila como a pilha são conjuntos ordenados de itens, porém ambas se dife- renciam pelas regras de entrada e saída. Na pilha a entrada e a saída de dados se dão pela mesma extremidade, chamada de topo da pilha. Na fila a entrada e a saída ocor- rem em lugares opostos: a entrada acontece no final da fila e a saída no seu início. Apesar de simples, ambas as estruturas (fila e pilha) são amplamente utiliza- das em diversas áreas da computação. Um exemplo pode ser visto no problema de escalonamento do uso do processador descrito por Machado (2002, p. 138-141). A estrutura, a utilização e as regras de inserção e remoção em pilhas e filas são o foco de estudo desta unidade. ESTRUTURAS HOMOGÊNEAS E HETEROGÊNEAS A primeira estrutura que estudamos foi a variável. Ela é um local reservado na memória para armazenamento de dados. Cada variável pode armazenar ape- nas uma única informação. Porém, em alguns momentos é necessário guardar muitas informações e a primeira solução em vista seria declarar variáveis em quantidade suficiente para atender a toda a demanda. Isso tem muitas desvantagens. Para um programa que vai ler 5 entradas, não é algo muito trabalhoso, mas imagine ter que ler 50, 100 ou 1000 valores, seria necessário criar muitas variáveis, muito código destinado a leitura, pro- cessamento e saída. Para esses casos, a maioria das linguagens de programação traz estruturas prontas para armazenamento múltiplo em uma única variável. Elas são clas- sificadas em homogêneas, que armazenam um único tipo de informação, e heterogêneas, que podem armazenar informações de tipos diferentes. 38 - 39 Introdução Re pr od uç ão p ro ib id a. A rt . 1 84 d o Có di go P en al e L ei 9 .6 10 d e 19 d e fe ve re iro d e 19 98 . ©shutterstock 40 - 41 PILHAS E FILAS Reprodução proibida. A rt. 184 do Código Penal e Lei 9.610 de 19 de fevereiro de 1998. II VETORES E MATRIZES A declaração de um vetor na linguagem C é muito simples, basta declarar uma variável e colocar o seu tamanho entre colchetes logo após o nome. Pense no vetor como uma matriz de uma única linha e quantidade de colunas equivalente ao seu tamanho. O vetor é uma estrutura homogênea, por isso só pode armaze- nar um único tipo de dado. Exemplo da declaração em linguagem C de um vetor chamado dados com capacidade para armazenar 5 valores inteiros: int dados[5]; Na linguagem C o índice dos vetores e matrizes começa no valor 0 e vai até n - 1, onde n é o tamanho do vetor. No exemplo acima, para acessar a primeira posição da variável dados usa-se o índice 0 e a última o índice 4. dados[0]; // primeira posição do vetor dados dados[1]; // segunda posição dados[2]; dados[3]; dados[4]; // quinta e última posição As matrizes possuem pelo menos duas dimensões. A declaração é parecida com a de vetores, precisando indicar também a quantidade de linhas além da quantidade de colunas. Abaixo o exemplo da declaração de uma matriz de núme- ros reais com duas linhas e três colunas. float matriz[2][3]; 40 - 41 Registros Re pr od uç ão p ro ib id a. A rt . 1 84 d o Có di go P en al e L ei 9 .6 10 d e 19 d e fe ve re iro d e 19 98 . Lembre-se que são necessários dois índices para acessar os dados em uma matriz bidimensional. matriz[0][0]; // primeira linha, primeira coluna matriz[0][1]; // primeira linha, segunda coluna matriz[1][2]; // segunda e última linha, terceira e última coluna REGISTROS O registro é uma coleção de variáveis, e por ser uma estrutura heterogênea, per- mite o armazenamento de informações de tipos diferentes. Ele possibilita que o programador crie tipos de dados específicos e personalizados. A declaração de um registro se dá pela palavra reservada struct, seguida pelo conjunto de elementos que o compõem. Veja um exemplo de um registro cha- mado fraction que possui três elementos: numerator, denominator e value. struct fraction { int numerator; int denominator; float value; } Após declarado o registro o seu uso se dá como tipo de variável, assim como usado para inteiros, reais, caracteres etc. Cada elemento do registro é acessado por meio de uma referência composta pelo nome_da_variável.nome_do_elemento. fraction metade; // cria uma variável do tipo fraction metade.numerator = 1; // atribui valor ao elemento numerator metade.denominator = 2; // atribui valor ao elemento denominator metade.value = metade.numerator / metade.denominator É possível criar vetores e matrizes para acomodar múltiplos registros. Vamos definir um registro chamado livro para armazenar quatro notas e depois vamos criar um vetor para armazenar as notas de 40 alunos. © sh ut te rs to ck 42 - 43 PILHAS E FILAS Reprodução proibida. A rt. 184 do Código Penal e Lei 9.610 de 19 de fevereiro de 1998. II struct livro { float nota1; float nota2; float nota3; float nota4; } livro alunos_notas[40];PILHAS A Pilha é uma das estruturas mais simples e mais versáteis dentre as utilizadas na computação. Antes de entrar nas nuances técnicas sobre pilhas, vamos abstrair o seu con- ceito para uma situação real. Imagine estar trabalhando na construção civil. Existem inúmeros tijolos que precisam ser organizados e preparados para a edificação de um prédio. Você é orientado a empilhá- -los próximo do local da obra. O primeiro tijolo é colocado no chão, no local estipulado, em seguida o segundo tijolo é colocado em cima do primeiro e cada novo tijolo é colocado no topo da pilha. Na hora de levantar uma nova parede, os tijolos são retirados a partir do topo da pilha de tijolos. Os tijolos foram empilhados e depois desempilhados. Não faz sentido querer pegar o primeiro tijolo que está lá em baixo na base, mas sim o primeiro que está livre na parte de cima. Esse é o conceito principal de Pilha. É o mesmo para uma pilha de camisas, pilha de caixas de leite, pilha de papéis etc. ©shutterstock 42 - 43 Pilhas Re pr od uç ão p ro ib id a. A rt . 1 84 d o Có di go P en al e L ei 9 .6 10 d e 19 d e fe ve re iro d e 19 98 . Na informática, a pilha é uma estrutura onde os dados são inseridos e removidos no seu topo. São estruturas conheci- das como Last In, First Out (LIFO), que pode ser traduzido por Último a Entrar, Primeiro a Sair. Vamos agora pensar em um exemplo para facilitar o entendimento. Temos um vetor de 10 posições no qual serão inseridos os seguintes valores nessa ordem: 1, 5, 12 e 3. O vetor deve ficar com essa cara: 1 5 12 3 Agora serão inseridos mais dois números na sequência: 14 e 2. O vetor ficará com essa configuração: 1 5 12 3 14 2 Pensando que o valor mais à esquerda é o começo da pilha, o lado oposto é o seu final e todos os valores vão entrando na primeira casa livre à direita. Esse é o processo de empilhamento, onde cada novo valor é inserido “em cima” dos valores previamente inseridos (empilhados). Agora é preciso remover um valor. Qual será removido e por quê? O valor removido será o último valor da pilha, já que pela regra, o último valor que entra será o primeiro valor a sair (Last In, First Out). É o processo de desempilhamento. 1 5 12 3 14 Para se construir uma pilha, são necessários pelo menos três elementos: um vetor para armazenar os dados e dois números inteiros, um para marcar o início e outro o final da pilha. Veja o exemplo, a seguir em linguagem C da definição de uma estrutura para uma pilha: 44 - 45 PILHAS E FILAS Reprodução proibida. A rt. 184 do Código Penal e Lei 9.610 de 19 de fevereiro de 1998. II //Constantes #define tamanho 10 //Estrutura da Pilha struct tpilha { int dados[tamanho]; int ini; int fim; }; //Variáveis globais tpilha pilha; Optamos por criar uma constante chamada tamanho para guardar a capacidade máxima da pilha. Se houver necessidade de aumentar estaticamente o tama- nho da pilha, basta alterar o valor da constante sem precisar revisar o resto do código-fonte. Essa constante também será útil na hora de fazer verificações nos processos de empilhamento e desempilhamento. O vetor dados guardará os valores que forem sendo empilhados, o atributo ini marca o início da pilha e o atributo fim o seu final. Ambas as variáveis ini e fim são inicializadas com valor zero para indicar que a pilha está vazia. Em seguida, vamos criar três funções, uma para mostrar o conteúdo da pilha, que ajuda no entendimento e visualização do processo, uma para a entrada (empilhamento) e outra para a saída (desempilhamento). A função pilha_mostrar() é muito simples, beirando o trivial. Basta um laço de repetição para percorrer todas as posições do vetor e ir imprimindo seus valores na tela. Aqui já usamos a constante tamanho para saber quantos valo- res cabem na pilha. //Mostrar o conteúdo da Pilha void pilha_mostrar() { int i; printf(“[ “); for (i = 0; i < tamanho; i++) { printf(“%d “, pilha.dados[i]); } printf(“]\n\n”); } Para a entrada dos dados, criamos a função pilha_entrar(). Para o empilha- mento, é necessário ler o dado diretamente na primeira posição disponível, que representa o topo da pilha. Isso é possível utilizando o atributo fim criado na 44 - 45 Pilhas Re pr od uç ão p ro ib id a. A rt . 1 84 d o Có di go P en al e L ei 9 .6 10 d e 19 d e fe ve re iro d e 19 98 . estrutura da pilha. Depois da leitura, o valor de fim é atualizado para que ele aponte sempre para a primeira posição disponível. //Adicionar um elemento no final da Pilha void pilha_entrar(){ printf(“\nDigite o valor a ser empilhado: “); scanf(“%d”, &pilha.dados[pilha.fim]); pilha.fim++; } Do jeito que está, não há nenhum tipo de controle. Os valores são empilha- dos infinitamente, porém, sabemos que a nossa pilha tem um tamanho finito. É necessário criar mecanismos que evitem o estouro da pilha. Vamos escrever novamente a função pilha_entrar() adicionando agora um desvio condicional para verificar se existe espaço disponível para o novo empilhamento. //Adicionar um elemento no final da Pilha void pilha_entrar(){ if (pilha.fim == tamanho) { printf(“\nA pilha está cheia, impossível empilhar um novo elemento!\n\n”); system(“pause”); } else { printf(“\nDigite o valor a ser empilhado: “); scanf(“%d”, &pilha.dados[pilha.fim]); pilha.fim++; } } Agora faremos uma pequena simulação do funcionamento da função de empilhamento de uma pilha com 5 posições. O vetor dados e as variáveis de controle ini e fim são inicializados com 0. ÍNDICE = 0 1 2 3 4 DADOS = 0 0 0 0 0 ini = 0 fim = 0 tamanho = 5 46 - 47 PILHAS E FILAS Reprodução proibida. A rt. 184 do Código Penal e Lei 9.610 de 19 de fevereiro de 1998. II Vamos inserir o número 42 no final da pilha. A primeira coisa que a função pilha_entrar() faz é verificar se a pilha atingiu o seu limite. Isso se dá compa- rando o atributo fim com a constante tamanho. Como fim (0) é diferente de tamanho (5), o algoritmo passa para a leitura do dado que será guardado na posição fim do vetor dados. Em seguida, o atributo fim sofre o incremento de 1. ÍNDICE = 0 1 2 3 4 DADOS = 42 0 0 0 0 ini = 0 fim = 1 tamanho = 5 Vamos inserir mais 3 valores: 33, 22 e 13. Para cada entrada será feita a veri- ficação do atributo fim com a constante tamanho; o valor será inserido no vetor dados na posição fim e o valor de fim será incrementado em 1. ÍNDICE = 0 1 2 3 4 DADOS = 42 33 22 13 0 ini = 0 fim = 4 tamanho = 5 Note que o atributo fim possui valor 4, mas não há nenhum valor inserido nessa posição do vetor dados. O atributo fim está apontando sempre para a pri- meira posição disponível no topo da pilha. Ele também representa a quantidade de valores inseridos (4) e que atualmente ocupam as posições 0 a 3 do vetor. Vamos inserir um último número: 9. ÍNDICE = 0 1 2 3 4 DADOS = 42 33 22 13 9 46 - 47 Pilhas Re pr od uç ão p ro ib id a. A rt . 1 84 d o Có di go P en al e L ei 9 .6 10 d e 19 d e fe ve re iro d e 19 98 . ini = 0 fim = 5 tamanho = 5 Agora a pilha está completa. Se tentarmos inserir qualquer outro valor, a comparação de fim (5) com tamanho (5) fará com que seja impresso na tela uma mensagem informando que a pilha já se encontra cheia, evitando assim o seu estouro. O atributo fim contém o valor 5, indicando que existem 5 valores no vetor e ele aponta para uma posição inválida, já que um vetor de 5 posições tem índice que começa em 0 e vai até 4. Para o desempilhamento,vamos criar a função pilha_sair(). A remoção se dá no elemento fim -1 do vetor dados, lembrando que o atributo fim aponta para a primeira posição livre, e não é esse o valor que queremos remover, mas sim o valor diretamente anterior. Após a remoção do item, o valor de fim deve ser atu- alizado para apontar corretamente para o final da pilha que acabou de diminuir. /Retirar o último elemento da Pilha void pilha_sair() { pilha.dados[pilha.fim-1] = 0; pilha.fim--; } O que acontece quando o vetor dados está vazio? E se removermos mais ele- mentos do que existem na pilha? Nesse caso, não haverá um estouro na pilha, mas você pode considerar que seria um tipo de implosão. Os vetores não tra- balham com índice negativo, e se muitos elementos fossem removidos além da capacidade do vetor, o valor de fim iria diminuindo até passar a ser um valor negativo. Na hora da inclusão de um novo valor, o mesmo seria adicionado em uma posição inválida e seria perdido. É preciso fazer um controle antes da remoção para verificar se a pilha está vazia. Vamos comparar então o valor de ini com fim. Se forem iguais, significa que a pilha está vazia e que nenhum valor pode ser removido. 48 - 49 PILHAS E FILAS Reprodução proibida. A rt. 184 do Código Penal e Lei 9.610 de 19 de fevereiro de 1998. II //Retirar o último elemento da Pilha void pilha_sair() { if (pilha.ini == pilha.fim) { printf(“\nA pilha está vazia, não há nada para desempi- lhar!\n\n”); system(“pause”); } else { pilha.dados[pilha.fim-1] = 0; pilha.fim--; } } Vamos resgatar agora a estrutura que carinhosamente empilhamos nas pági- nas anteriores. ÍNDICE = 0 1 2 3 4 DADOS = 42 33 22 13 9 ini = 0 fim = 5 tamanho = 5 Precisamos remover um número. Como não se trata de um vetor qualquer, mas sim de uma estrutura em pilha, a remoção começa sempre do último para o primeiro (Last In, First Out). O primeiro passo da função pilha_sair() é a com- paração dos atributos ini (0) e fim (5), para verificar se a pilha não está vazia. Como os valores são diferentes, o algoritmo segue para a linha de remoção. É muito comum encontrar na literatura os termos push para o processo de empilhar e pop para o de desempilhar. 48 - 49 Pilhas Re pr od uç ão p ro ib id a. A rt . 1 84 d o Có di go P en al e L ei 9 .6 10 d e 19 d e fe ve re iro d e 19 98 . Lembrando que o atributo fim aponta para a primeira posição livre (ou seja, o fim da pilha), então temos que remover o valor do vetor dados na posição fim subtraindo-se 1, que é a última posição preenchida (topo da pilha). Por último, atualizamos o valor de fim para que aponte para a posição recém-liberada do vetor dados. ÍNDICE = 0 1 2 3 4 DADOS = 42 33 22 13 0 ini = 0 fim = 4 tamanho = 5 Vamos agora remover os outros valores: 13, 22, 33 e 42. A pilha irá ficar desse jeito: ÍNDICE = 0 1 2 3 4 DADOS = 0 0 0 0 0 ini = 0 fim = 0 tamanho = 5 Se tentarmos agora remover mais algum item da pilha, o programa escre- verá uma mensagem de erro na tela, já que o atributo fim (0) está com o mesmo valor de ini (0), que significa que a pilha está vazia. A seguir, você encontrará o código-fonte completo de uma pilha em linguagem C. Logo após coloquei comentários sobre cada bloco do código. Digite o exemplo no seu compilador e execute o programa. 50 - 51 PILHAS E FILAS Reprodução proibida. A rt. 184 do Código Penal e Lei 9.610 de 19 de fevereiro de 1998. II 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 //Bibliotecas #include <stdio.h> #include <stdlib.h> #include <locale.h> //Constantes #define tamanho 5 //Estrutura da Pilha struct tpilha { int dados[tamanho]; int ini; int fim; }; //Variáveis globais tpilha pilha; int op; //Protipação void pilha_entrar(); void pilha_sair(); void pilha_mostrar(); void menu_mostrar(); //Função principal int main(){ setlocale(LC_ALL, "Portuguese"); op = 1; pilha.ini = 0; pilha.fim = 0; while (op != 0) { system("cls"); pilha_mostrar(); menu_mostrar(); scanf("%d", &op); switch (op) { case 1: pilha_entrar(); break; 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 case 2: pilha_sair(); break; } } return(0); } //Adicionar um elemento no final da Pilha void pilha_entrar(){ if (pilha.fim == tamanho) { printf("\nA pilha está cheia, impossível empilhar!\n\n"); system("pause"); } else { printf("\nDigite o valor a ser empilhado: "); scanf("%d", &pilha.dados[pilha.fim]); pilha.fim++; } } //Retirar o último elemento da Pilha void pilha_sair() { if (pilha.ini == pilha.fim) { printf("\nA pilha está vazia, impossível desempilhar!\n\n"); system("pause"); } else { pilha.dados[pilha.fim-1] = 0; pilha.fim--; } } //Mostrar o conteúdo da Pilha void pilha_mostrar() { int i; printf("[ "); for (i = 0; i < tamanho; i++) { printf("%d ", pilha.dados[i]); } printf("]\n\n"); } 50 - 51 Pilhas Re pr od uç ão p ro ib id a. A rt . 1 84 d o Có di go P en al e L ei 9 .6 10 d e 19 d e fe ve re iro d e 19 98 . 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 case 2: pilha_sair(); break; } } return(0); } //Adicionar um elemento no final da Pilha void pilha_entrar(){ if (pilha.fim == tamanho) { printf("\nA pilha está cheia, impossível empilhar!\n\n"); system("pause"); } else { printf("\nDigite o valor a ser empilhado: "); scanf("%d", &pilha.dados[pilha.fim]); pilha.fim++; } } //Retirar o último elemento da Pilha void pilha_sair() { if (pilha.ini == pilha.fim) { printf("\nA pilha está vazia, impossível desempilhar!\n\n"); system("pause"); } else { pilha.dados[pilha.fim-1] = 0; pilha.fim--; } } //Mostrar o conteúdo da Pilha void pilha_mostrar() { int i; printf("[ "); for (i = 0; i < tamanho; i++) { printf("%d ", pilha.dados[i]); } printf("]\n\n"); } 83 84 85 86 87 88 89 90 91 //Mostrar o menu de opções void menu_mostrar() { printf("\nEscolha uma opção:\n"); printf("1 - Incluir na Pilha\n"); printf("2 - Excluir da Pilha\n"); printf("0 - Sair\n\n"); } Linhas 1 a 4 Inclusão de bibliotecas necessárias para o funcionamento do programa. Linhas 6 e 7 Definição de constante para o tamanho da pilha. 52 - 53 PILHAS E FILAS Reprodução proibida. A rt. 184 do Código Penal e Lei 9.610 de 19 de fevereiro de 1998. II Linhas 9 a 14 Registro de estrutura para criar o “tipo pilha” contando com um vetor para armazenar os dados e dois números inteiros para controlar o início e fim da pilha. Linhas 16 a 18 Definições de variáveis. Linhas 20 a 24 Prototipação das funções. Para mais detalhes sobre prototipação, consulte o livro de Algoritmos e Estrutura de Dados II. Linhas 26 a 47 Função principal (main), a primeira que será invocada na execução do programa. Linha 28 Chamada de função para configurar o idioma para português, permitindo o uso de acentos (não funciona em todas as versões do Windows). Linhas 29 a 31 Inicialização das variáveis. Linhas 32 a 45 Laço principal, que será executado repetidamente até que o usuário decida finalizar o programa. Linha 33 Chamada de comando no sistema operacional para limpar a tela. Linha 34 Chamada da função que mostra o conteúdo da Pilha na tela. Linha 35 Chamada da função que desenha o menu de opções. Linha 36 Lê a opçãoescolhida pelo usuário. Linhas 37 a 44 Desvio condicional que faz chamada de acordo com a opção escolhida pelo usuário. Linhas 49 a 60 Função pilha_entrar(), que faz checagem do topo da pilha e insere novos valores no vetor dados. © sh ut te rs to ck 52 - 53 Filas Re pr od uç ão p ro ib id a. A rt . 1 84 d o Có di go P en al e L ei 9 .6 10 d e 19 d e fe ve re iro d e 19 98 . Linhas 62 a 72 Função pilha_sair(), que verifica se existem elementos na pilha e remove o último inserido. Linhas 74 a 82 Função pilha_mostrar(), que lê o conteúdo e desenha o vetor dados na tela. Linhas 84 a 90 Função menu_mostrar(), que desenha na tela as opções permitidas para o usuário. FILAS As filas também são estruturas muito utilizadas, porém suas particularidades fazem com seu que seu funcionamento seja um pouco menos simples do que o das pilhas. Voltemos ao exercício de abstração e pensemos como as filas estão presentes no nosso dia a dia. Isso é fácil, o brasileiro adora uma fila e às vezes se encon- tra em uma sem saber para quê. Fila no supermercado, fila no cinema, fila no banco e assim por diante. Chegando a uma agência bancária, para ser atendido pelo caixa, um cida- dão honesto se dirige para o final da fila. Quando um caixa fica livre, aquele que está na fila há mais tempo (primeiro da fila) é atendido. Esse é conceito básico de toda fila FIFO (First In, First Out), ou na tradu- ção, o Primeiro que Entra é o Primeiro que Sai. Vamos agora simular uma fila em uma casa lotérica, imaginando que existe lugar apenas para 5 pessoas e que o restante dos apostadores esperam fora do edi- fício. O primeiro a chegar é João, mas ele ainda não é atendido porque os caixas estão contando o dinheiro e se preparando para iniciar os trabalhos. 54 - 55 PILHAS E FILAS Reprodução proibida. A rt. 184 do Código Penal e Lei 9.610 de 19 de fevereiro de 1998. II João Em seguida, dois clientes entram praticamente juntos, Maria e José, e como todo cavalheiro, José deixa que Maria fique à frente na fila. João Maria José Um dos funcionários está pronto para iniciar o atendimento e chama o cliente. Qual deles será atendido? O João, porque ele ocupa o primeiro lugar na fila, já que em teoria o Primeiro que Entra é o Primeiro que sai. Maria José Maria passa automaticamente a ser a primeira da fila, ocupando o lugar que era de João, tendo logo atrás de si José aguardando a sua vez de ser atendido. Maria José Agora que está claro o funcionamento de uma fila, vamos programá-la em linguagem C. A primeira coisa que precisamos é definir a sua estrutura. Usaremos um vetor para armazenar os valores que serão enfileirados e dois números intei- ros para fazer o controle de início e fim da fila. Usaremos também uma constante para definir a capacidade de armazenamento. //Constantes #define tamanho 5 //Estrutura da Fila struct tfila { int dados[tamanho]; int ini; int fim; }; //Variáveis globais tfila fila; Vamos criar uma função chamada fila_entrar() para controlar a entrada de novos valores na fila. A primeira coisa a se fazer é verificar se há espaço. Isso 54 - 55 Filas Re pr od uç ão p ro ib id a. A rt . 1 84 d o Có di go P en al e L ei 9 .6 10 d e 19 d e fe ve re iro d e 19 98 . pode ser feito comparando o atributo fim com a constante tamanho. Caso haja uma posição livre, o valor será inserido no vetor dados na posição fim e final- mente o valor de fim é incrementado em um. //Adicionar um elemento no final da Fila void fila_entrar(){ if (fila.fim == tamanho) { printf(“\nA fila está cheia, impossível adicionar um novo va- lor!\n\n”); system(“pause”); } else { printf(“\nDigite o valor a ser inserido: “); scanf(“%d”, &fila.dados[fila.fim]); fila.fim++; } } Até agora, a fila e a pilha estão muito parecidas na sua definição e modo de entrada de dados. A principal diferença entre as duas estruturas está na forma de saída. Na pilha sai sempre o elemento mais recente, na fila sai sempre o mais antigo. Assim como na pilha, é necessário fazer uma verificação na fila para saber se ainda existe algum elemento a ser removido. //Retirar o primeiro elemento da Fila void fila_sair() { if (fila.ini == fila.fim) { printf(“\nA fila está vazia, não há nada para remover!\n\n”); system(“pause”); } } Como o primeiro elemento da fila será removido, os demais precisam andar em direção ao início, assim como acontece em uma fila de verdade. Em seguida, atualizamos o valor do atributo fim para apontar corretamente para o final da fila. int i; for (i = 0; i < tamanho; i++) { fila.dados[i] = fila.dados[i+1]; } fila.dados[fila.fim] = 0; fila.fim--; 56 - 57 PILHAS E FILAS Reprodução proibida. A rt. 184 do Código Penal e Lei 9.610 de 19 de fevereiro de 1998. II A função fila_sair() completa fica com essa cara: //Retirar o primeiro elemento da Fila void fila_sair() { if (fila.ini == fila.fim) { printf(“\nA fila está vazia, não há nada para remover!\n\n”); system(“pause”); } else { int i; for (i = 0; i < tamanho; i++) { fila.dados[i] = fila.dados[i+1]; } fila.dados[fila.fim] = 0; fila.fim--; } } Para finalizar agora, falta apenas a função fila_mostrar(), que possui um laço de repetição que percorre todo o vetor dados e imprime os valores na tela. //Mostrar o conteúdo da Fila void fila_mostrar() { int i; printf(“[ “); for (i = 0; i < tamanho; i++) { printf(“%d “, fila.dados[i]); } printf(“]\n\n”); } A principal regra para uma fila é que o primeiro que entra é o primeiro que sai. Esse exemplo não é a única forma de implementação de fila. No nosso caso, cada vez que alguém sai da fila, todos os outros clientes precisam se mover para a pri- meira posição que ficou livre a sua esquerda. 56 - 57 Filas Re pr od uç ão p ro ib id a. A rt . 1 84 d o Có di go P en al e L ei 9 .6 10 d e 19 d e fe ve re iro d e 19 98 . Existem outras formas de fila, por exemplo, a fila cíclica. Ao invés de mover os dados para a esquerda sempre que uma posição fica livre, move-se o atributo que marca o início da fila para a direita. Essa é uma alternativa interessante para quando se tem filas muito grandes e não se pode perder tempo movendo todo o resto dos dados em direção ao começo da fila. Vamos voltar ao exemplo da fila anterior com o João, a Maria e o José. João Maria José ini = 0 fim = 3 tamanho = 5 Quando o João deixa a fila, não é a Maria que anda em direção à posição ocupada por João, mas é o início da fila que se move em direção a Maria. Maria José ini = 1 fim = 3 tamanho = 5 Nesse exemplo, para saber o tamanho da fila, é necessário subtrair o valor do atributo fim (3) do atributo ini (1). 58 - 59 PILHAS E FILAS Reprodução proibida. A rt. 184 do Código Penal e Lei 9.610 de 19 de fevereiro de 1998. II Apesar de ser implementado de forma diferente, o conceito ainda é o mesmo: o primeiro que entra é o primeiro que sai. Ninguém gosta de fura-fila, não é verdade? Segue agora o código-fonte completo de uma fila em linguagem C. Fiz comen- tários explicando cada bloco do código. Digite o exemplo no seu compilador e execute o programa. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 //Bibliotecas #include <stdio.h> #include <stdlib.h> #include <locale.h> //Constantes #define tamanho 5 //Estrutura da Filastruct tfila { int dados[tamanho]; int ini; int fim; }; //Variáveis globais tfila fila; int op; //Protipação void fila_entrar(); void fila_sair(); void fila_mostrar(); void menu_mostrar(); //Função principal int main(){ setlocale(LC_ALL, "Portuguese"); op = 1; fila.ini = 0; fila.fim = 0; while (op != 0) { system("cls"); fila_mostrar(); menu_mostrar(); scanf("%d", &op); switch (op) { case 1: fila_entrar(); break; É comum na literatura o uso do termo enqueue para indicar a inserção e dequeue para a remoção em filas. 58 - 59 Filas Re pr od uç ão p ro ib id a. A rt . 1 84 d o Có di go P en al e L ei 9 .6 10 d e 19 d e fe ve re iro d e 19 98 . 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 //Bibliotecas #include <stdio.h> #include <stdlib.h> #include <locale.h> //Constantes #define tamanho 5 //Estrutura da Fila struct tfila { int dados[tamanho]; int ini; int fim; }; //Variáveis globais tfila fila; int op; //Protipação void fila_entrar(); void fila_sair(); void fila_mostrar(); void menu_mostrar(); //Função principal int main(){ setlocale(LC_ALL, "Portuguese"); op = 1; fila.ini = 0; fila.fim = 0; while (op != 0) { system("cls"); fila_mostrar(); menu_mostrar(); scanf("%d", &op); switch (op) { case 1: fila_entrar(); break; 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 case 2: fila_sair(); break; } } return(0); } //Adicionar um elemento no final da Fila void fila_entrar(){ if (fila.fim == tamanho) { printf("\nA fila está cheia, volte outro dia!\n\n"); system("pause"); } else { printf("\nDigite o valor a ser inserido: "); scanf("%d", &fila.dados[fila.fim]); fila.fim++; } } //Retirar o primeiro elemento da Fila void fila_sair() { if (fila.ini == fila.fim) { printf("\nFila vazia, mas logo aparece alguém!\n\n"); system("pause"); } else { int i; for (i = 0; i < tamanho; i++) { fila.dados[i] = fila.dados[i+1]; } fila.dados[fila.fim] = 0; fila.fim--; } } 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 //Mostrar o conteúdo da Fila void fila_mostrar() { int i; printf("[ "); for (i = 0; i < tamanho; i++) { printf("%d ", fila.dados[i]); } printf("]\n\n"); } //Mostrar o menu de opções void menu_mostrar() { printf("\nEscolha uma opção:\n"); printf("1 - Incluir na Fila\n"); printf("2 - Excluir da Fila\n"); printf("0 - Sair\n\n"); } 60 - 61 PILHAS E FILAS Reprodução proibida. A rt. 184 do Código Penal e Lei 9.610 de 19 de fevereiro de 1998. II 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 //Mostrar o conteúdo da Fila void fila_mostrar() { int i; printf("[ "); for (i = 0; i < tamanho; i++) { printf("%d ", fila.dados[i]); } printf("]\n\n"); } //Mostrar o menu de opções void menu_mostrar() { printf("\nEscolha uma opção:\n"); printf("1 - Incluir na Fila\n"); printf("2 - Excluir da Fila\n"); printf("0 - Sair\n\n"); } Linhas 1 a 4 Inclusão de bibliotecas necessárias para o funcionamento do programa. Linhas 6 e 7 Definição de constante para o tamanho da fila. Linhas 9 a 14 Registro de estrutura para criar o “tipo fila” contando com um vetor para armazenar os dados e dois números inteiros para controlar o início e fim da fila. Linhas 16 a 18 Definições de variáveis. Linhas 20 a 24 Prototipação das funções. Para mais detalhes sobre prototipação, consulte o livro de Algoritmos e Estrutura de Dados II. Linhas 26 a 47 Função principal (main), a primeira que será invocada na execução do programa. Linha 28 Chamada de função para configurar o idioma para português, permitindo o uso de acentos (não funciona em todas as versões do Windows). 60 - 61 Filas Re pr od uç ão p ro ib id a. A rt . 1 84 d o Có di go P en al e L ei 9 .6 10 d e 19 d e fe ve re iro d e 19 98 . Linhas 29 a 31 Inicialização das variáveis. Linhas 32 a 45 Laço principal, que será executado repetidamente até que o usuário decida finalizar o programa. Linha 33 Chamada de comando no sistema operacional para limpar a tela. Linha 34 Chamada da função que mostra o conteúdo da Fila na tela. Linha 35 Chamada da função que desenha o menu de opções. Linha 36 Lê a opção escolhida pelo usuário. Linhas 37 a 44 Desvio condicional que faz chamada de acordo com a opção escolhida pelo usuário. Linhas 49 a 60 Função fila_entrar(), que faz checagem do fim da fila e insere novos valo- res no vetor dados. Linhas 62 a 76 Função fila_sair(), que verifica se existem elementos na fila e remove o ele- mento mais antigo. Linhas 78 a 86 Função fila_mostrar(), que lê o conteúdo e desenha o vetor dados na tela. Linhas 88 a 94 Função menu_mostrar(), que desenha na tela as opções permitidas para o usuário. 62 - 6362 - 63 PILHAS E FILAS Reprodução proibida. A rt. 184 do Código Penal e Lei 9.610 de 19 de fevereiro de 1998. II CONSIDERAÇÕES FINAIS Na unidade anterior, vimos uma pequena revisão sobre os tipos de variáveis e aprendemos como elas são alocadas na memória. Isso é muito importante, por- que uma sequência de bits nada mais é do que um monte de números 1 e 0 sem sentido algum. É a estrutura de dados que determina como ela deve ser lida e qual o seu significado. Agora foi a vez de revisarmos as estruturas homogêneas e heterogêneas. Elas são fundamentais para que possamos estudar estruturas mais complexas, como as pilhas e as filas. Os vetores e matrizes permitem que tenhamos em uma única variável uma coleção grande de dados agrupados. Com os registros podemos criar nova tipa- gem de variáveis e usá-las para definir estruturas capazes de conter informações de diferentes tipos. Tanto as pilhas como as filas são tipos de listas, ou seja, coleção de dados agrupados. A diferença é que tanto a pilha como a fila possuem regras de entrada e saída, diferente das listas simples. As pilhas são usadas em problemas onde é mais importante resolver o pro- blema mais recente, ou mais oneroso, ou mais próximo. Já as filas têm função contrária e são aplicadas na solução de casos onde é proibido que questões mais recentes recebam atenção antes de questões mais antigas. Até o momento, trabalhamos com estruturas estáticas. Depois de definido o tamanho da pilha ou da fila, ele permanecerá o mesmo até o final da execução do programa. Na próxima unidade, aprenderemos sobre ponteiros e a sua utili- zação na criação de estruturas dinâmicas sem tamanho ou limite pré-definido. <http://www.mlaureano.org/livro/livro_estrutura_conta.pdf> (Capítulos 3 e 4). 62 - 63 ©shutterstock 62 - 63 1. Quando um livro é devolvido na Biblioteca do CESUMAR, o funcionário respon- sável pelo recebimento coloca o livro em cima de uma pilha de livros na mesa ao lado da recepção. O auxiliar de bibliotecário pega o livro do topo da pilha, verifica o seu código e leva-o para o seu devido local no acervo. No atual sistema de informação, é possível verificar se o livro está disponível ou se está emprestado. Porém, o livro que acabou de ser devolvido ainda não se encontra na prateleira, pois existe um intervalo de tempo entre a devolução do mesmo e o momento em que ele é guardado na estante. A sugestão do departamento de TI é de criar um programa que faça o controle na pilha, assim, pode-se verificar se o livro ainda não foi guardado e qual a sua posição dentro da pilha de livros que aguardam ao lado da recepção. a) Crie uma estrutura para a pilha de livros.
Compartilhar