Estrutura de Dados Com Algoritmos e C - Marcos Laureano

Estrutura de Dados com Algoritmos e C

)WGVIZIVYQPMZVSRSYQEXEVIJEJGMPRYRGEJSM8SQEXIQTSI\MKITIWUYMWEIHIHMGES'SQSEWIHMXSVEWRSHIWINEQQEMWTYFPMGEVIWXIXXYPSREHEQEMWREXYVEPUYIXIRXEVGSQIVGMEPM^EPSREJSVQEHIEVUYMZSWIQIPLERXIEYQIFSSO1EWIWXEEXMZMHEHIXEQFQXSQEXIQTSII\MKIHIHMGES

4IRWERHSEWWMQVIWSPZMPMFIVEVIWXIPMZVSTEVEGSRWYPXETFPMGEWIZSGEGLEUYIIWXIPMZVSXIENYHSYIUYMWIVGSPEFSVEVGSQMKSTEWWIRYQEPSXVMGEIHITSWMXISZEPSVUYIEGLEVUYIHIZI

8IVQMRSYHITEKEVEGSRXEHIPY^XIPIJSRISYKYEIWSFVSYXVSGSZSGTSHIHITSWMXEVREQMRLEGSRXE)YEGVIHMXSUYIRWHSMWTSHIQSWWEMVKERLERHSZSGTSVUYIXIZIEGIWWSEYQFSQQEXIVMEPUYIXIENYHSYIIYGSQSMRGIRXMZSEGSRXMRYEVIWGVIZIRHSPMZVSW'EWSHIGIVXSXEPZI^SWTV\MQSWPMZVSWRIQWINEQTYFPMGEHSWTSVYQEIHMXSVEIIWXINEQPMFIVEHSWHMVIXEQIRXITEVEWYEGSRWYPXE

5YEPUYIVZEPSVHITSWMXEHSWIVHMVIGMSREHSTEVEEGSRXETSYTEREHSQIYPLSTEVEUYERHSIPIIWXMZIVREQEMSVMHEHIXIVVIGYVWSWTEVEGSQIEVYQRIKGMSTVTVMSRERGMEVWIYWIWXYHSWIXG

(EHSWTEVEHITWMXS

1EVGSW%YVIPMS4GLIO0EYVIERS&ERGS'EM\E)GSRQMGE*IHIVEP%KRGME3TIVES'SRXE

'YVMXMFEHIQEVSHI


Marcos Laureano

BRASPORT Livros e Multimdia Ltda.Rua Pardal Mallet, 23 Tijuca20270-280 Rio de Janeiro-RJTels. Fax: (21) 2568.1415/2568.1507/2569.0212/2565.8257e-mails: [email protected] [email protected] [email protected]: www.brasport.com.br

FilialAv. Paulista, 807 conj. 91501311-100 So Paulo-SPTel. Fax (11): 3287.1752HPDLO OLDOVS#EUDVSRUWFRPEU

Copyright 2008 por Brasport Livros e Multimdia Ltda.

Todos os direitos reservados. Nenhuma parte deste livro poder ser reproduzida, sob qualquer

meio, especialmente em fotocpia (xerox), sem a permisso, por escrito, da Editora.

Editor: Sergio Martins de Oliveira

Diretora Editorial: Rosa Maria Oliveira de Queiroz

Assistente de Produo: Marina dos Anjos Martins de Oliveira

Reviso de Texto: Maria Helena A. M. Oliveira

Editorao Eletrnica: Abreus System LTDA.

Capa: Use Design

Tcnica e muita ateno foram empregadas na produo deste livro. Porm, erros de digitao e/ou impresso podem

ocorrer. Qualquer dvida, inclusive de conceito, solicitamos enviar mensagem para [email protected],

para que nossa equipe, juntamente com o autor, possa esclarecer. A Brasport e o(s) autor(es) no assumem qualquer

responsabilidade por eventuais danos ou perdas a pessoas ou bens, originados do uso deste livro.

Dados Internacionais de Catalogao na Publicao (CIP)

(Cmara Brasileira do Livro, SP, Brasil)

Aos meus genitores Luiz Otvio (in memoriam) e Natlia.

Agradecimentos

Agradeo Brasport por mais esta oportunidade de publicar um livro sobre um tema em que vrios autores j trabalharam ( claro que este livro tem um diferencial em relao aos demais).

Aos meus colegas professores e alunos que ajudaram a evoluo deste ma-terial nos ltimos anos.

E para uma linda flor, que, alm de alegrar os meus dias, corrigiu os assas-sinatos lngua portuguesa.

Sobre o autor

Marcos Laureano tecnlogo em Processamento de Dados pela ESEEI, Ps-graduado em Administrao pela FAE Business School e Mestre em Infor-mtica Aplicada pela Pontifcia Universidade Catlica do Paran. Doutorando em Informtica Aplicada pela Pontifcia Universidade Catlica do Paran.

Trabalha com programao em C no ambiente Unix (AIX/HP-UX) desde 1997 e Linux desde 2000, sendo especialista em segurana de sistemas operacio-nais.

professor de graduao e ps-graduao, tendo lecionado em vrias ins-tituies nos ltimos anos.

autor de vrios guias de utilizao/configurao de aplicativos para os ambientes Unix e Linux. Possui artigos e livros publicados sobre programao, sistemas operacionais e segurana de sistemas. Dentre eles, Programando em C para Linux, Unix e Windows, tambm publicado pela Brasport.

Atualmente leciona disciplinas relacionadas segurana, programao, re-des de computadores e sistemas operacionais em cursos de graduao e ps-gra-duao do Centro Universitrio Franciscano (UNIFAE) e atua como consultor na rea de projetos de desenvolvimento e segurana de sistemas.

O autor pode ser contactado pelo e-mail [email protected] ou atra-vs de sua pgina www.laureano.eti.br, onde est disponvel vasto material so-bre programao, segurana de sistemas e sistemas operacionais.

Sobre o Livro

O crescimento dos cursos tecnolgicos especficos e com curta durao (2 a 3 anos) gerou uma demanda de livros que tratam diretamente o assunto de maneira clara e eficiente.

Este livro indicado aos cursos tecnolgicos, para estudantes e profissionais que precisem dominar os conceitos e os algoritmos de forma rpida e precisa.

O material foi preparado com a experincia do autor em lecionar a discipli-na, somada sua experincia profissional. Outros professores e coordenadores de cursos foram consultados; com isto, este material tem os assuntos pertinentes rea e pode ser adotado tranqilamente em cursos de 40 ou 80 horas de Estru-tura de Dados ou Programao de Computadores.

Os algoritmos podem ser aplicados e convertidos para qualquer linguagem de programao, e os programas em C so simples e objetivos, facilitando o entendimento dos estudantes e profissionais que no dominam totalmente esta linguagem.

Sumrio

1. Estrutura de Dados ................................................................................ 11.1 Dados Homogneos ................................................................................2

1.1.1 Vetor ...........................................................................................21.1.2 Matriz ..........................................................................................51.1.3 Ponteiros ...................................................................................11

1.2 Dados Heterogneos .............................................................................161.3 Exerccios ...............................................................................................18

2. Uso de Memria ................................................................................... 192.1 Alocao de memria Esttica x Dinmica ...........................................192.2 Alocao dinmica de memria .............................................................202.3 Funes para alocao de memria .......................................................20

2.3.1 Funo malloc ...........................................................................212.3.2 Funo calloc ............................................................................212.3.3 Funo realloc ...........................................................................212.3.4 Funo free ...............................................................................22

2.4 Utilizando as funes para alocao de memria .................................222.5 Alocao de memria e estruturas em C ...............................................252.6 Ponteiros para ponteiros mistrio ou no ..........................................272.7 Mais alocao de vetores e matrizes como ponteiros ...........................29

2.7.1 Controle de agenda com ponteiros de estruturas e vetores .....33

3. Pilha ...................................................................................................... 403.1 Representao das Operaes com Pseudo-cdigo ..............................423.2 Pilhas em C ............................................................................................423.3 Exerccios ...............................................................................................47

XIV Estrutura de Dados com Algoritmos e C

4. Fila ........................................................................................................ 484.1 Representao de Filas com Pseudo-cdigos........................................494.2 Filas em C ..............................................................................................514.3 Exerccios ...............................................................................................59

5. Recursividade ....................................................................................... 605.1. Funo para clculo de Fatorial ..........................................................615.2 Nmero triangular ................................................................................635.3 Nmeros de Fibonacci ..........................................................................665.4 Algoritmo de Euclides ...........................................................................685.5 Torres de Hanoi .....................................................................................715.6 Curiosidades com Recursividade...........................................................745.7 Cuidados com Recursividade ................................................................765.8 Vantagens ...............................................................................................775.9 Exerccios ...............................................................................................77

6. Lista ...................................................................................................... 796.1 Vetores ou alocao dinmica? ..............................................................826.2 Listas em C ............................................................................................846.3 Exerccios ...............................................................................................93

7. Pesquisa ................................................................................................ 947.1 Pesquisa Seqencial ...............................................................................947.2 Pesquisa Binria .....................................................................................977.3 Exerccios ...............................................................................................99

8. Ordenao ........................................................................................... 1008.1 BubbleSort ...........................................................................................1008.2 Ordenao por Seleo ........................................................................1048.3 Ordenao por Insero ......................................................................1078.4 QuickSort ............................................................................................1118.5 MergeSort ............................................................................................1158.6 Exerccios .............................................................................................124

9. rvores Binrias ................................................................................. 1259.1 Analogia entre rvores .........................................................................1259.2 rvore binria ......................................................................................126

9.2.1 Relaes ..................................................................................127

Sumrio XV

9.2.2 rvore Binria Completa .......................................................1289.3 rvores de Busca Binria .....................................................................1299.4 Operaes em rvores Binrias ..........................................................130

9.4.1 Insero ...................................................................................1309.4.2 Pesquisa ...................................................................................1329.4.3 Excluso ..................................................................................1339.4.4 Maior elemento ......................................................................1369.4.5 Menor elemento .....................................................................1369.4.6 Percorrendo uma rvore .........................................................136

9.5 Representaes de rvores em C .........................................................1389.6 Implementao em C ..........................................................................1399.7 Exerccio ..............................................................................................148

Referncias Bibliogrficas ....................................................................... 149

ndice Remissivo ..................................................................................... 151

Lista de Programas

1.1: Declarao de vetor em C .............................................................................4

1.2: Exemplo de uso de vetores ............................................................................5

1.3: Exemplo de uso de matrizes ..........................................................................9

1.4: Exemplo de uso de matrizes com vrias dimenses ....................................10

1.5: Exemplo de uso de ponteiros ......................................................................12

1.6: Ponteiros como referncia em funes .......................................................13

1.7: Aritmtica com ponteiros ............................................................................14

1.8: Vetor como ponteiro ...................................................................................15

1.9: Exemplo de estrutura ..................................................................................17

1.10: Exemplo de uso de estruturas com vetores ...............................................17

2.1: Declarao de vetor como ponteiro ............................................................22

2.2: Declarao de matriz como ponteiro ..........................................................22

2.3: Exemplo de uso do malloc e realloc ............................................................23

2.4: Exemplo de uso do calloc ............................................................................24

2.5: Exemplo de uso de estruturas com ponteiros .............................................25

2.6: Ponteiro para ponteiro ................................................................................28

2.7: Exemplo de uso de alocao de matrizes ....................................................30

2.8: Exemplo de uso de alocao de matrizes dentro de funes ......................32

XVIII Estrutura de Dados com Algoritmos e C

2.9: Exemplo completo de uso de vetor (ponteiros) de estruturas ....................33

3.1: Exemplo de manipulao de pilha ...............................................................44

3.2: Exemplo de manipulao de pilha com estrutura .......................................45

4.1: Exemplo de manipulao de fila em C ........................................................51

4.2: Reajuste da fila .............................................................................................53

4.3: Declarao de estrutura circular .................................................................54

4.4: Manipulao de fila circular em C ..............................................................55

5.1: Fatorial (verso iterativa) .............................................................................61

5.2: Fatorial (verso recursiva) ...........................................................................62

5.3: Descobrindo o nmero triangular (iterativo) .............................................65

5.4: Descobrindo o nmero triangular (recursivo) ............................................65

5.5: Clculo do n-simo termo de Fibonacci (verso iterativa) .........................67

5.6: Clculo do n-simo termo de Fibonacci (verso recursiva)........................67

5.7: Clculo do MDC iterativo ..........................................................................69

5.8: Clculo do MDC recursivo .........................................................................69

5.9: Clculo do MDC recursivo .........................................................................70

5.10: Torre de Hanoi recursivo ..........................................................................73

5.11: Natori - Imprimindo as fases da lua ..........................................................74

5.12: Dhyanh - Saitou, aku, soku e zan ..............................................................75

6.1: Exemplo de manipulao de lista simples em C .........................................84

6.2: Exemplo de manipulao de lista encadeada em C ....................................86

6.3: Funes para manipulao de listas ............................................................88

7.1: Funo para pesquisa seqencial .................................................................96

7.2: Funo para pesquisa binria ......................................................................99

8.1: Funo BubbleSort ....................................................................................102

8.2: Funo BubbleSort melhorado .................................................................103

8.3: Funo Select .............................................................................................106

Lista de Programas XIX

8.4: Funo Insert .............................................................................................109

8.5: Ordenao QuickSort ...............................................................................113

8.6: Ordenao MergeSort ...............................................................................117


9.1: Representao com vetor de filhos ............................................................138

9.2: Representao dinmica ............................................................................138

9.3: Representao dinmica de uma rvore binria ........................................139

9.4: Implementao das operaes ...................................................................139

Lista de Tabelas

2.1: Operaes com ponteiros ............................................................................28

2.2: Operaes com ponteiros de ponteiros ......................................................29

5.1: Clculo de fatorial de 6 ...............................................................................62

7.1: Entradas e freqncias para clculo de comparaes mdias .....................96

8.1: BubbleSort - primeira varredura ...............................................................101

8.2: BubbleSort - segunda varredura ................................................................101

8.3: Seleo - o que ocorre em cada passo .......................................................105

8.4: Insero - o que ocorre em cada passo ......................................................109

9.1: Comparaes para busca de um elemento ................................................130

Lista de Algoritmos

1.1: Clculo da posio de ndices de um vetor na memria ...............................4

1.2: Clculo da posio de ndices de uma matriz na memria ...........................6

3.1: Verificao se a pilha est vazia (funo EMPTY(S)) .................................42

3.2: Colocar um item na pilha (funo PUSH(S,x)) ..........................................43

3.3: Retirada de um item da pilha (funo POP(S)) ..........................................43

3.4: Pega o item do topo da pilha mas no desempilha (funo STACKPOP(S)) .......................................................................................43

3.5: Tamanho da pilha (funo SIZE(S)) ...........................................................44

4.1: Incluso de dados na fila (ENQUEUE(Q,x)) .............................................50

4.2: Retirada de dados na fila (DEQUEUE(Q)) ................................................50

4.3: Verificao se a fila est vazia (funo EMPTY(Q)) ...................................50

4.4: Tamanho da fila (funo SIZE(Q)) .............................................................51

4.5: Prximo elemento da fila (funo FRONT(Q)) .........................................51

5.1: Algoritmo de Euclides .................................................................................69

5.2: Passar n peas de uma torre (A) para outra (C) ..........................................72

6.1: Insero numa lista duplamente encadeada ................................................82

6.2: Remoo numa lista duplamente encadeada ...............................................83

7.1: Pesquisa seqencial ......................................................................................95

7.2: Pesquisa seqencial com ajuste de freqncia ............................................97

XXII Estrutura de Dados com Algoritmos e C

7.3: Pesquisa binria ...........................................................................................98

8.1: Ordenao Bubble .....................................................................................102

8.2: Ordenao por Seleo ..............................................................................106

8.3: Ordenao por Insero ............................................................................111

8.4: QuickSort ..................................................................................................113

8.5: Particiona - Diviso do vetor ....................................................................115

8.6: MergeSort ..................................................................................................121

8.7: Intercala .....................................................................................................122

8.8: MergeSort ..................................................................................................123

9.1: Inserir elemento na rvore - iterativo .......................................................131

9.2: Inserir elemento na rvore - recursivo ......................................................131

9.3: Pesquisar elemento na rvore - iterativo ...................................................132

9.4: Pesquisar elemento na rvore - recursivo .................................................133

9.5: Excluso na rvore .....................................................................................135

9.6: Sucessor .....................................................................................................135

9.7: Maior elemento da rvore .........................................................................136

9.8: Menor elemento da rvore ........................................................................137

9.9: Operao Percorre - Pr-ordem ...............................................................137

9.10: Operao Percorre - Ps-ordem .............................................................137

9.11: Operao Percorre - Em-ordem .............................................................137

Lista de Figuras

1.1: Exemplo de Vetor ..........................................................................................3

1.2: Representao de um vetor na memria .......................................................4

1.3: Matriz 2x2 - Clculo de posio na memria ...............................................6

1.4: Clculo de posio na memria ....................................................................7

1.5: Exemplo de Matriz ........................................................................................7

1.6: Uma matriz de duas dimenses vista como dois vetores ..............................8

1.7: Chamada de funo com ponteiros .............................................................13

1.8: Vetor como Ponteiro em C .........................................................................15

1.9: Registro de funcionrio ...............................................................................17

2.1: Matriz como vetor de ponteiros ..................................................................20

2.2: Exemplo de ponteiro na memria ...............................................................27

2.3: Exemplo de ponteiro para ponteiro na memria ........................................29

3.1: Exemplo de Pilha .........................................................................................40

3.2: Operaes em uma pilha .............................................................................42

4.1: Operaes numa fila ....................................................................................49

4.2: Operaes numa fila circular .......................................................................55

5.1: Nmeros triangulares ..................................................................................64

5.2: Descobrindo o quinto elemento triangular ................................................64

5.3: Descobrindo o quinto elemento triangular de forma recursiva .................65

XXIV Estrutura de Dados com Algoritmos e C

5.4: O que ocorre a cada chamada .....................................................................66

5.6: Torre de Hanoi ............................................................................................71

5.7: Movimentos conforme algoritmo ...............................................................73

6.1: Exemplo de lista simplesmente encadeada .................................................80

6.2: Exemplo de lista duplamente encadeada .....................................................81

6.3: Incluso de novo elemento ..........................................................................81

6.4: Excluso de elemento ..................................................................................82

6.5: Problemtica do crescimento do vetor .......................................................83

6.6: Crescimento de uma lista sem utilizar vetor ...............................................84

7.1: Processo de pesquisa seqencial ..................................................................95

7.2: Busca binria ................................................................................................98

8.1: Exemplo de Ordenao por Seleo com nmeros inteiros .....................105

8.2: Exemplo de Ordenao por Insero com nmeros inteiros ...................108

8.3: Seqncia de ordenao por insero .......................................................109

8.4: Algoritmo da ordenao por insero .......................................................110

8.5: Ordenao QuickSort ...............................................................................112



9.1: Analogia entre rvores ...............................................................................126

9.2: Representao de uma rvore ....................................................................127

9.3: rvore Binria completa de nvel 3 ...........................................................129

9.4: rvore de busca binria - duas organizaes diferentes ...........................129

9.5: Excluso de folha .......................................................................................133

9.6: Excluso de um n com um filho ..............................................................134

9.7: Excluso de um n com dois filhos ...........................................................134

9.8: Representao com vetores .......................................................................138

9.9: Representao dinmica ............................................................................139

1. Estrutura de Dados

No existe vitria sem sacrifcio!

Filme Transformers

Um computador uma mquina que manipula informaes. O estudo da cincia da computao inclui o exame da organizao, manipulao e utilizao destas informaes num computador. Conseqentemente, muito importante entender os conceitos de organizao e manipulao de informaes.

A automatizao de tarefas um aspecto marcante da sociedade moderna, e na cincia da computao houve um processo de desenvolvimento simultneo e interativo de mquinas (hardware) e dos elementos que gerenciam a execuo automtica (software) de uma tarefa.

Nesta grande evoluo do mundo computacional, um fator de relevante im-portncia a forma de armazenar as informaes, j que, informtica a cincia da informao. Ento de nada adiantaria o grande desenvolvimento do hardware e do software se a forma de armazenamento e tratamento da informao no acompanhasse esse desenvolvimento. Por isso a importncia das estruturas de da-dos, que nada mais so do que formas otimizadas de armazenamento e tratamento das informaes eletronicamente.

As estruturas de dados, na maioria dos casos, baseiam-se nos tipos de ar-mazenamento vistos dia a dia, ou seja, nada mais so do que a transformao de uma forma de armazenamento j conhecida e utilizada no mundo real adaptada para o mundo computacional. Por isso, cada tipo de estrutura de dados possui vantagens e desvantagens e cada uma delas tem sua rea de atuao (massa de dados) otimizada.


Os dados manipulados por um algoritmo podem possuir natureza distinta, isto , podem ser nmeros, letras, frases etc. Dependendo da natureza de um dado, algumas operaes podem ou no fazer sentido quando aplicadas a eles. Por exemplo, no faz sentido falar em somar duas letras - algumas linguagens de programao permitem que ocorra a soma dos valores ASCII correspondentes de cada letra.

Para poder distinguir dados de naturezas distintas e saber quais operaes podem ser realizadas com eles, os algoritmos lidam com o conceito de tipo de dados. O tipo de um dado deine o conjunto de valores que uma varivel pode assumir, bem como o conjunto de todas as operaes que podem atuar sobre qualquer valor daquela varivel. Por exemplo, uma varivel do tipo inteiro pode assumir o conjunto de todos os nmeros e de todas as operaes que podem ser aplicadas a estes nmeros.

Os tipos de dados manipulados por um algoritmo podem ser classiicados em dois grupos: atmicos e complexos ou compostos. Os tipos atmicos so aqueles cujos elementos do conjunto de valores so indivisveis, por exemplo: o tipo inteiro, real, caractere e lgico. Por outro lado, os tipos complexos so aqueles cujos elementos do conjunto de valores podem ser decompostos em par-tes mais simples. Se um tipo de dado pode ser decomposto, ento o tipo de dado dito estruturado, e a organizao de cada componente e as relaes entre eles constituem a disciplina de Estrutura de Dados.

1.1 Dados Homogneos

Uma estrutura de dados, que utiliza somente um tipo de dado, em sua dei-nio conhecida como dados homogneos. Variveis compostas homogneas cor-respondem a posies de memria, identiicadas por um mesmo nome, individu-alizado por ndices e cujo contedo composto do mesmo tipo. Sendo os vetores (tambm conhecidos como estruturas de dados unidimensionais) e as matrizes (estruturas de dados bidimensionais) os representantes dos dados homogneos.

1.1.1 Vetor

O vetor uma estrutura de dados linear que necessita de somente um ndice para que seus elementos sejam endereados. utilizado para armazenar uma lista de valores do mesmo tipo, ou seja, o tipo vetor permite armazenar mais de um valor em uma mesma varivel. Um dado vetor deinido como tendo um

Estrutura de Dados

nmero ixo de clulas idnticas (seu contedo dividido em posies). Cada clula armazena um e somente um dos valores de dados do vetor. Cada uma das clulas de um vetor possui seu prprio endereo, ou ndice, atravs do qual pode ser referenciada. Nessa estrutura todos os elementos so do mesmo tipo, e cada um pode receber um valor diferente [, 1, 4].

Algumas caractersticas do tipo vetor([10]):

Alocao esttica (deve-se conhecer as dimenses da estrutura no momento da declarao)

Estrutura homognea

Alocao seqencial (bytes contguos)

Insero/Excluso

Realocao dos elementos

Posio de memria no liberada

Figura 1.1: Exemplo de Vetor

A partir do endereo do primeiro elemento possvel determinar a loca-lizao dos demais elementos do vetor. Isso possvel porque os elementos do vetor esto dispostos na memria um ao lado do outro e cada elemento tem o seu tamanho ixo (algoritmo 1.1 [10]).

A partir do algoritmo 1.1 possvel deduzir a frmula genrica para clculo de posio na memria de um elemento qualquer. Sendo n o elemento, a frmu-la se d por Pos

n = endereo Inicial + ( (n - 1) * tamanho do tipo do elemento).

4 Estrutura de Dados com Algoritmos e C

Algoritmo 1.1: Clculo da posio de ndices de um vetor na memria

A igura 1.1 mostra um vetor de notas de alunos, a referncia NOTA[4] indica o valor 4.6 que se encontra na coluna indicada pelo ndice 4.

A deinio de um vetor em C se d pela sintaxe:

tipo_do_dado nome_do_vetor[ tamanho_do_vetor ]

O programa 1.1 contm um exemplo de declarao de um vetor na lingua-gem C. A igura 1. apresenta a representao deste vetor na memria do compu-tador (lembrando que um vetor guardado na memria de forma seqencial).

Programa 1.1: Declarao de vetor em C1 int i[];

i[0]=1; i[1]=; i[]=4;

6 char c[4];c[0]=a;c[1]=b; c[]=c; c[]=d;

Figura 1.2: Representao de um vetor na memria

Estrutura de Dados

Programa 1.2: Exemplo de uso de vetores

/* programa_vetor_01.c */

#include

#deine TAMANHO

10

int main (void) {

int iIndice;int iValorA;int iSoma; int aVetor [TAMANHO]; loat fMedia;

1

0

for (iIndice = 0; iIndice < TAMANHO; iIndice++) {

printf("Entre com o valor %d:", iIndice + 1); scanf("%d", &iValorA); aVetor[iIndice] = iValorA;

}

0

iSoma = 0; for (iIndice=0; iIndice < TAMANHO; iIndice++) { iSoma += aVetor[iIndice]; } fMedia = (loat) iSoma/TAMANHO; printf ("Media : %f\n", fMedia); return 0; }

Lembrete: Caso seja colocada num programa a instruo a[2]++ est sen-do dito que a posio do vetor a ser incrementada.

1.1.2 Matriz

Uma matriz um arranjo bidimensional ou multidimensional de alocao esttica e seqencial. A matriz uma estrutura de dados que necessita de um ndice para referenciar a linha e outro para referenciar a coluna para que seus elementos sejam endereados. Da mesma forma que um vetor, uma matriz de-inida com um tamanho ixo, todos os elementos so do mesmo tipo, cada clula contm somente um valor e os tamanhos dos valores so os mesmos (em C, um char ocupa 1 byte e um int 4 bytes) [, 1, 4].


Os elementos ocupam posies contguas na memria. A alocao dos ele-mentos da matriz na memria pode ser feita colocando os elementos linha-por-linha ou coluna-por-coluna.

Para uma matriz de 2x2 (igura 1.) o algoritmo para calcular as posies da memria listado em 1. [10].

Figura 1.3: Matriz x - Clculo de posio na memria

No algoritmo 1., sendo C a quantidade de colunas por linhas, i o nmero da linha e j a posio do elemento dentro linha, possvel deinir a frmula ge-nrica para acesso na memria, onde Pos

ij = endereo inicial + ((i-1) * C * tamanho

do tipo do elemento) + ((j-1) * tamanho do tipo do elemento). A igura 1.4 demonstra a aplicao da frmula.

A matriz LETRAS (igura 1.) composta de 18 elementos ( linhas e 6 colunas), a referncia a MATRIZ[3][3] (onde o primeiro indica a linha e o segundo indica a coluna) retorna o elemento N; no caso de MATRIZ[2][5] (segunda linha e terceira coluna) ir retornar o elemento E. Como uma ma-triz de strings (linguagem C), a chamada a MATRIZ[3] ir reproduzir o valor DONALD.

Algoritmo 1.2: Clculo da posio de ndices de uma matriz na memria

Estrutura de Dados

Figura 1.4: Clculo de posio na memria

Uma matriz consiste de dois ou mais vetores deinidos por um conjunto de elementos. Cada dimenso de uma matriz um vetor (igura 1.6). O primeiro conjunto (dimenso) considerado o primeiro vetor, o segundo conjunto o se-gundo vetor e assim sucessivamente [4].

A deinio de uma matriz em C se d pela sintaxe:

tipo_do_dado nome_da_matriz[ quantidade_linhas ] [ quantidade_colunas ]

O programa 1. apresenta um exemplo de declarao e utilizao de matri-zes bidimensionais na linguagem C.

Figura 1.5: Exemplo de Matriz


Figura 1.6: Uma matriz de duas dimenses vista como dois vetores

A linguagem C permite ainda trabalhar com matrizes de vrias dimenses (matrizes n-dimensionais), embora o seu uso ique mais restrito em aplicaes cienticas face sua pouca praticidade de uso.

A deinio de uma matriz de vrias dimenses em C se d pela sintaxe:

tipo_do_dado nome_da_matriz[tamanho_dimenso_1] [tamanho_

dimenso_2]

[tamanho_dimenso_3] ... [tamanho_dimenso_n]

Estrutura de Dados

Programa 1.3: Exemplo de uso de matrizes

/* programa_matriz_01.c */

#include

4 #deine DIMENSAO

int main (void) {

int iLinha, iColuna;int iDeterminante;

int iValorA; int aMatriz [DIMENSAO][DIMENSAO

14/* Uma regra que se pode sempre levar em considerao:

para cada dimenso de uma matriz, sempre haver um lao (normalmente um for). Se houver duas dimenses, ento haver dois laos. */

1

4

for (iLinha=0; iLinha < DIMENSAO; iLinha++) {

for (iColuna=0; iColuna < DIMENSAO; iColuna++) {

printf ("Entre item %d %d:", iLinha + 1, iColuna + 1); scanf ("%d", &iValorA); matriz [iLinha][iColuna] = iValorA;

} } iDeterminante = aMatriz[0][0] * aMatriz [1][1] - aMatriz[0][1] * aMatriz [1][0]; printf ("Determinante : %d\n", iDeterminante);

return 0; }

O programa 1.4 um exemplo de deinio e utilizao de matrizes multi-dimensionais na linguagem C.


Programa 1.4: Exemplo de uso de matrizes com vrias dimenses

4

/* programa_matriz_02.c */

#include #deine DIM_1 #deine DIM_ #deine DIM_ #deine DIM_4 4

int main (void) { int i,j,k,l; int aMatriz [DIM_1][DIM_][DIM_][DIM_4];

14 /* Cdigo para zerar uma matriz de quatro dimenses */for (i=0; i < DIM_1; i++)

1

4

{ for (j=0; j < DIM_; j++) {

for (k=0; k < DIM_; k++) {

for (l=0; l < DIM_4; l++) {

aMatriz [i][j][k][l] = i+j+k+l; }

} }

}

4

44

/* Uma regra que se pode sempre levar em considerao: para cada dimenso de uma matriz, sempre haver um lao (normalmente um for). Se houver quatro dimensoes ento haver quatro laos */ For (i=0; i < DIM_1; i++) {

for (j=0; j < DIM_; j++) {

for (k=0; k < DIM_; k++) {

for (l=0; l < DIM_4; l++) {

printf("\nValor para matriz em [%d] [%d] [%d] [%d] = %d", i,j,k,l, aMatriz[i][j][k][l]);

} }

} } return 0;

}

Estrutura de Dados 11

1.1.3 Ponteiros

A linguagem C implementa o conceito de ponteiro. O ponteiro um tipo de dado como int, char ouRDW. A diferena do ponteiro em relao aos outros tipos de dados que uma varivel que seja ponteiro guardar um endereo de memria [, ].

Por meio deste endereo pode-se acessar a informao, dizendo que a vari-vel ponteiro aponta para uma posio de memria. O maior problema em relao ao ponteiro entender quando se est trabalhando com o seu valor, ou seja, o endereo, e quando se est trabalhando com a informao apontada por ele.

Operador & e *

O primeiro operador de ponteiro &. Ele um operador unrio que devol-ve o endereo na memria de seu operando. Por exemplo: m = &count; pe o endereo na memria da varivel count em m. Esse endereo a posio interna da varivel na memria do computador e no tem nenhuma relao com o valor de count. O operador & tem como signiicado o endereo de. O segundo operador *, que o complemento de &. O * um operador unrio que devolve o valor da varivel localizada no endereo que o segue. Por exemplo, se m con-tm o endereo da varivel count: q = *m; coloca o valor de count em q. O operador * tem como signiicado no endereo de.

Lembrete: Cuide-se para no confundir o operador de ponteiros (*) como multiplicao na utilizao de ponteiros e vice-versa.

A declarao de uma varivel ponteiro dada pela colocao de um aste-risco (*) na frente de uma varivel de qualquer tipo. Na linguagem C, possvel deinir ponteiros para os tipos bsicos ou estruturas. A deinio de um ponteiro no reserva espao de memria para o seu valor e sim para o seu contedo. Antes de utilizar um ponteiro, o mesmo deve ser inicializado, ou seja, deve ser colocado um endereo de memria vlido para ser acessado posteriormente.

Um ponteiro pode ser utilizado de duas maneiras distintas. Uma maneira trabalhar com o endereo armazenado no ponteiro e outro modo trabalhar com a rea de memria apontada pelo ponteiro. Quando se quiser trabalhar com o en-dereo armazenado no ponteiro, utiliza-se o seu nome sem o asterisco na frente. Sendo assim qualquer operao realizada ser feita no endereo do ponteiro.

Como, na maioria dos casos, se deseja trabalhar com a memria apontada pelo ponteiro, alterando ou acessando este valor, deve-se colocar um asterisco


antes do nome do ponteiro. Sendo assim, qualquer operao realizada ser feita no endereo de memria apontado pelo ponteiro. O programa 1. demostra a utilizao de ponteiros para acesso memria.

Programa 1.5: Exemplo de uso de ponteiros

1 /* programa_matriz_02.c */

#include

6

int main (void) {

int *piValor; /* ponteiro para inteiro */

int iVariavel = 11

piValor = &iVariavel; /* pegando o endereo de memria da varivel */

11

printf ("Endereco: %d\n", piValor); printf ("Valor : %d\n", *piValor);

16*piValor = 180118;printf ("Valor alterado: %d\n", iVariavel);printf ("Endereco : %d\n", piValor);

return 0;}

Passando variveis para funes por referncia

O ponteiro utilizado para passar variveis por referncia, ou seja, variveis que podem ter seu contedo alterado por funes e mantm este valor aps o trmino da funo.

Na declarao de uma funo, deve-se utilizar o asterisco antes do nome do parmetro, indicando que est sendo mudado o valor naquele endereo passado como parmetro. No programa 1.6 visto um exemplo de uma varivel sendo alterada por uma funo (igura 1.).


Figura 1.7: Chamada de funo com ponteiros

Programa 1.6: Ponteiros como referncia em funes

/* programa_ponteiro_02.c */

#include

4

void soma (int, int, int *);

int main (void) {

int iValorA; int iValorB; int iResultado;

printf ("Entre com os valores:");

14

scanf ("%d %d", &iValorA, &iValorB);

printf("Endereco de iResultado = %d\n", &iResultado);

1

soma (iValorA, iValorB, &iResultado);/* est sendo passado o endereo de memria da varivel, qualquer alterao estar sendo realizada na memria */ printf ("Soma : %d\n", iResultado);

4

return 0; }

4

void soma (int piValorA, int piValorB, int * piResultado) {

printf("Endereco de piResultado = %d\n", piResultado); /* o valor est sendo colocado diretamente na memria */ *piResultado = piValorA + piValorB; return;

}


Aritmtica com ponteiros

Com uma varivel do tipo ponteiro, possvel realizar operaes de soma e subtrao. Ser somada ou diminuda no ponteiro a quantidade de endereos de memria relativos ao tipo do ponteiro. Por exemplo, um ponteiro para int ocupa 4 bytes, uma operao de soma neste ponteiro ir acrescentar 4 posies (unidades) na memria. O programa 1. visto como os endereos de memria so manipulados atravs de aritmtica de ponteiros, e a diferena entre o tipo char - que ocupa 1 byte de memria - e o tipo int - que ocupa 4 bytes.

Programa 1.7: Aritmtica com ponteiros

/* programa_ponteiro_03.c */

#include

10

int main (void) {

int *piValor; int iValor; char *pcValor; char cValor;

piValor = &iValor; pcValor = &cValor;

1 printf ("Endereco de piValor = %d\n", piValor); printf ("Endereco de pcValor = %d\n", pcValor);

piValor++; /* somando uma unidade (4 bytes) na memria */ pcValor++; /* somando uma unidade (1 byte) na memria */

0

printf ("Endereco de piValor = %d\n", piValor); printf ("Endereco de pcValor = %d\n", pcValor);

return 0;

}

Vetores e matrizes como ponteiros em C

Vetores nada mais so do que ponteiros com alocao esttica de memria, logo, todo vetor na linguagem C um ponteiro, tal que o acesso aos ndices do ve-tor podem ser realizados atravs de aritmtica de ponteiros. Observe a igura 1.8:


Figura 1.8: Vetor como Ponteiro em C

Existem formas para se obter o endereo (ponteiro) do incio do vetor ou matriz:

&t[0];

t

Sendo a segunda opo (t) a melhor, por ser mais simples. O endereo (pon-teiro) para o primeiro elemento do vetor ou matriz dado pelo nome do vetor sem colchetes.

O programa 1.8 mostra a utilizao de um vetor com aritmtica de ponteiros.

Programa 1.8: Vetor como ponteiro

/* programa_vetor_02.c */

4#include #include

int main(void) {

char t[];

strcpy(t,abcde);

4

printf("\n%ld %c", t, *t); printf("\n%ld %c", t+1, *(t+1)); printf("\n%ld %c", t+, *(t+));


printf("\n%ld %c", t+, *(t+)); printf("\n%ld %c", t+4, *(t+4)); return 0;

}

1.2 Dados Heterogneos

Uma estrutura de dados chamada de heterognea quando envolve a utili-zao de mais de um tipo bsico de dado (inteiro ou caractere, por exemplo) para representar uma estrutura de dados. Normalmente, este tipo de dado chamado de registro.

Um registro uma estrutura de dados que agrupa dados de tipos distintos ou, mais raramente, do mesmo tipo. Um registro de dados composto por certo nmero de campos de dados, que so itens de dados individuais. Registros so conjuntos de dados logicamente relacionados, mas de tipos diferentes (numri-cos, lgicos, caractere etc) [, 1, 4].

O conceito de registro visa facilitar o agrupamento de variveis que no so do mesmo tipo, mas que guardam estreita relao lgica. Registros corres-pondem a conjuntos de posies de memria conhecidos por um mesmo nome e individualizados por identiicadores associados a cada conjunto de posies. O registro um caso mais geral de varivel composta na qual os elementos do conjunto no precisam ser, necessariamente, homogneos ou do mesmo tipo. O registro constitudo por componentes. Cada tipo de dado armazenado em um registro chamado de campo.

A igura 1. um exemplo de registro de um funcionrio: composto de nome, departamento, data de nascimento e salrio.

Na varivel composta homognea, a individualizao de um elemento fei-ta atravs de seus ndices, j no registro cada componente individualizado pela explicitao de seu identiicador.

A linguagem C utiliza as estruturas para representar um registro. Com a es-trutura deinida pode-se fazer atribuio de variveis do mesmo tipo de maneira simpliicada. Veja o programa exemplo 1. (representao da igura 1.):


Figura 1.9: Registro de funcionrio

Programa 1.9: Exemplo de estrutura

struct Funcionario {

char nome [40];

1

struct {

int dia; int mes; int ano;

} dataNasc; char departamento[10]; loat salario;

};

Para se fazer o acesso de um nico campo deve-se utilizar o nome da estrutu-ra seguido de um ponto e do nome do campo desejado da estrutura. A linguagem C tambm permite que seja criado um vetor de estruturas (programa 1.10).

Programa 1.10: Exemplo de uso de estruturas com vetores

/* programa_estrutura_01.c */ #include

8

struct DADO {

char sNome[40]; int iIdade;

};


int main(void) {

struct DADO sDados[];

1

18

/* A estrutura dividida em duas partes por um ponto (.). Tem-se o nome da estrutura esquerda e o nome do campo direita. Neste exemplo, como est sendo manipulado um vetor de estruturas, tambm tem ndice para cada linha do vetor. */ for(iIndice=0;iIndice

2. Uso de Memria

Nada traz de volta os bons e velhos tempos quanto uma memria fraca.

Franklin P. Adams

2.1 Alocao de memria Esttica x Dinmica

A alocao esttica ocorre em tempo de compilao, ou seja, no momento em que se deine uma varivel ou estrutura necessrio que se deinam seu tipo e tamanho. Nesse tipo de alocao, ao se colocar o programa em execuo, a memria necessria para utilizar as variveis e estruturas estticas precisa ser reservada e deve icar disponvel at o trmino do programa (rotina ou funo).

A alocao dinmica ocorre em tempo de execuo, ou seja, as variveis e estruturas so declaradas sem a necessidade de se deinir seu tamanho, pois ne-nhuma memria ser reservada ao colocar o programa em execuo. Durante a execuo do programa, no momento em que uma varivel ou parte de uma estru-tura precise ser utilizada, sua memria ser reservada e, no momento em que no for mais necessria, deve ser liberada. Isso feito com o auxlio de comandos ou funes que permitem, por meio do programa, reservar e/ou liberar memria.

Pode-se dizer que os vetores e matrizes so estruturas estticas e, por esse motivo, devemos deinir seu nmero de posies. Algumas linguagens permitem criar vetores dinmicos por meio do uso de ponteiros e sua memria reservada durante a execuo do programa.

Mesmo vetores dinmicos devem ter o seu tamanho conhecido no momen-to da alocao da memria, pois um vetor deve ter toda sua memria alocada


antes da sua utilizao. Estruturas encadeadas dinmicas possuem tamanho vari-vel, pois diferentemente de vetores dinmicos, sua memria reservada por ele-mento e no para toda a estrutura.

2.2 Alocao dinmica de memria

Vrias linguagens de programao possibilitam manipular dinamicamente a memria das suas estruturas de dados. Algumas linguagens como o Java possibi-litam que uma estrutura de dados cresa ou diminua quase que sem interferncia do programador. Outras linguagens como o C exigem que o trabalho de aloca-o de memria seja feito antecipadamente pelo programador.

Na linguagem C, uma matriz na prtica um vetor de ponteiros, onde cada coluna um ponteiro para uma linha. Na igura .1 pode ser visualizada a repre-sentao de uma matriz como um vetor com ponteiros.

2.3 Funes para alocao de memria

Na linguagem C, a alocao dinmica de memria pode ser realizada com apenas quatro chamadas a funes:

Figura 2.1: Matriz como vetor de ponteiros

Uso de Memria 1

void * malloc(int qty_bytes_alloc);

void * calloc(int qty, int size);

void * realloc(void * pointer, int new_size);

free( void * pointer);

A funo malloc permite que seja feita a alocao de uma nova rea de memria para uma estrutura. A funo calloc tem a mesma funcionalidade de malloc, exceto que devem ser fornecidos o tamanho da rea e a quantidade de elementos. A funo realloc permite que uma rea previamente alocada seja au-mentada ou diminuda e a funo free libera uma rea alocada previamente com a funo malloc, calloc ou realloc.

2.3.1 Funo malloc

a funo malloc que realiza a alocao de memria. Deve-se informar para a funo a quantidade de bytes para alocao. A funo ir retornar, se exis-tir memria suiciente, um endereo que deve ser colocado em uma varivel do tipo ponteiro.

Como a funo retorna um ponteiro para o tipo void, deve-se utilizar o typecast, transformando este endereo para o tipo de ponteiro desejado.

2.3.2 Funo calloc

Em vez de se alocar uma quantidade de bytes atravs da funo malloc, pode-se usar a funo calloc e especiicar a quantidade de bloco de um determi-nado tamanho. Funcionalmente a alocao ir ocorrer de maneira idntica.

A nica diferena entre o malloc e o calloc que a ltima funo, alm de alocar o espao, tambm inicializa o mesmo com zeros.

2.3.3 Funo realloc

s vezes necessrio expandir uma rea alocada. Para isto deve-se usar a funo realloc. Deve-se passar para ela o ponteiro retornado pelo malloc e a indicao do novo tamanho. A realocao de memria pode resultar na troca de blocos na memria.


2.3.4 Funo free

Quando no se deseja mais uma rea alocada, deve-se liber-la atravs da funo free. Deve ser passado para a funo o endereo, que se deseja liberar, que foi devolvido quando a alocao da memria ocorreu.

2.4 Utilizando as funes para alocao de memria

Um vetor nada mais do que um ponteiro com alocao esttica de mem-ria. A declarao int aVetor[10]; equivalente:

Programa 2.1: Declarao de vetor como ponteiro

1 int *aVetor; aVetor = (int *) malloc(10 * sizeof(int *));

Quando se quer criar estruturas com dois ndices (matrizes), trs ndices (tijolos) etc. A declarao da matriz seria algo como int aMatriz[2][3];, utilizando ponteiros para declarar uma matriz deve-se usar:

Programa 2.2: Declarao de matriz como ponteiro

int **aMatriz; aMatriz = (int **) malloc( * sizeof(int *)); /* linhas */ for( i=0; i

Uso de Memria

Programa 2.3: Exemplo de uso do malloc e realloc

/* programa_memoria_01.c */ #include #include

4

int main(void) {

int *p; int i,k, n; printf("\nDigite a quantidade de numeros que serao digitados ->"); scanf("%d", &i);

14

/* A funo malloc reserva espao suiciente para um vetor de inteiros. Caso sejam digitados 5 elementos, sero reservados 20 bytes, pois cada inteiro ocupa 4 bytes na memria */ p = (int *)(malloc(i*sizeof(int))); if( p == NULL ) {

printf("\nErro de alocacao de memoria"); exit(1);

}

4

for( k=0;k


4

{ printf("Digite o numero para o indice %d ->", k); scanf("%d", &p[k]);

} for( k=0;k

Uso de Memria

8 printf("\nErro de alocacao de memoria"); exit(1);

} }

8

for( k=0;k


8 loat salario;

1

/* estrutura dentro de uma estrutura */ struct nascimento {

int ano; int mes; int dia;

} dt_nascimento; };

18

int main(void) {

/* ponteiro para a estrutura */ struct ST_DADOS * p;

/* alocao de memria para o ponteiro da estrutura */ p = (struct ST_DADOS *) malloc(sizeof(struct ST_DADOS));

8 /* string (vetor de caracteres) um ponteiro, por isto a ausncia do & */ printf("\nEntre com o nome ->"); scanf("%s", p->nome);

printf("Entre com o salario ->"); scanf("%f", &p->salario);

8

/* O -> chamado de pointer member (apontador de membro). Ele usado para referenciar um campo da estrutura no lugar do ponto (.) */ printf("Entre com o nascimento ->"); scanf("%d%d%d", &p->dt_nascimento.dia, &p->dt_nascimento.mes, &p->dt_nascimento.ano);

48

printf("\n===== Dados digitados ===="); printf("\nNome = %s", p->nome); printf("\nSalario = %f", p->salario); printf("\nNascimento = %d/%d/%d\n", p->dt_nascimento.dia, p->dt_nascimento.mes, p->dt_nascimento.ano); free(p);

}

Uso de Memria

2.6 Ponteiros para ponteiros mistrio ou no

O uso de ponteiros confunde os iniciantes nas disciplinas de programao. Quando vem ponteiros para ponteiros, at proissionais mais experientes tm diiculdades [].

A referncia para uma varivel int iVariavel obtida atrves do uso do & no caso funcao(&iVariavel), ou seja, passado o endereo da memria da varivel em uso. A varivel recebida como um ponteiro na funo (void funcao(int * piVariavel)).

Quando se quer alocar um vetor ou uma matriz dentro de uma funo, deve-se passar a referncia do ponteiro (por causa da alocao dinmica). Ou seja, uma varivel declarada como ponteiro (int * piVariavel) vai ter sua referncia passada para uma funo (funcao(&piVariavel)) e recebida como um ponteiro na funo em questo. Como regra pode ser adotada a adio de um * sempre no incio de uma varivel, logo, a funo seria declarada como void funcao(int **piVariavel) .

Considere a declarao de um ponteiro para inteiro (int *piVariavel), esta declarao gera uma alocao esttica de memria para o ponteiro (vamos considerar o endereo 1 na memria (a)). Os segmentos e da memria esto sendo utilizados por outras variveis de tal forma que o comando *piVaria-vel = (int *) malloc(sizeof(int)) retorna o endereo 4 da me-mria (b), isto signiica que o valor 4 vai ser armazenado (c) dentro do ponteiro *piVariavel (endereo 1). A instruo *piVariavel = 20 (d) ir colocar o valor 0 no endereo apontado por *piVariavel (o endereo apontado 4). A igura . exempliica a operao.

Figura 2.2: Exemplo de ponteiro na memria


A tabela .1 demonstra as operaes com ponteiro (pegando o endereo de memria do ponteiro, o endereo armazenado no ponteiro e o contedo coloca-do no endereo indicado pelo ponteiro).

Tabela 2.1: Operaes com ponteiros

Operao Resultadoprintf("%d\n",&piVariavel) 1printf("%d\n",piVariavel) 4printf("%d\n",*piVariavel) 0

A passagem de um ponteiro por referncia a uma funo gera um pontei-ro para ponteiro. Considere a declarao de uma funo int funcao(int **piParametro) (programa .6), esta declarao gera uma declarao es-ttica de memria para o ponteiro **piParametro (vamos considerar o en-dereo de memria 6 (a)). A chamada a funo funcao(&piVariavel)) ser interpretada como passando endereo de piVariavel para o ponteiro piParametro (b). Desta forma criado um ponteiro para o ponteiro (c). A igura . (continuao da igura .) exempliica a operao.

Programa 2.6: Ponteiro para ponteiro

10

#include #include int funcao(int **piParametro) {

printf("%d\n",&piParametro); printf("%d\n",piParametro); printf("%d\n",*piParametro); printf("%d\n",**piParametro); return 0;

}

int main( void ) {

int *piVariavel; *piVariavel = (int *) malloc(sizeof(int); *piVariavel = 0; printf("%d\n",&piVariavel); printf("%d\n",piVariavel); printf("%d\n",*piVariavel);

0

funcao( &piVariavel );

Uso de Memria

return 0; }

A tabela . demonstra as operaes com ponteiro (pegando o endereo de memria do ponteiro, o endereo armazenado no ponteiro e o contedo coloca-do no endereo indicado pelo ponteiro).

Figura 2.3: Exemplo de ponteiro para ponteiro na memria

Tabela 2.2: Operaes com ponteiros de ponteiros

Operao Resultado Signiicadoprintf("%d\n",&piParametro) 6 Endereo de piParametroprintf("%d\n",piParametro) 1 Contedo de piParametroprintf("%d\n",*piParametro) 4 Contedo do endereo

apontado por piParametro (piVariavel)

printf("%d\n",**piParametro) 0 Valor do endereo apontado por piParametro (*piVariavel)

2.7 Mais alocao de vetores e matrizes como ponteiros

No programa . so utilizadas vrias funes para a alocao de memria e manipulao de uma matriz; nestes casos, uma matriz deve ser declarada utili-zando o formato de ponteiro. Ao alocar dinamicamente uma matriz utilizando o formato de ponteiros, o ponteiro que representa uma matriz pode ser utilizado no formato matriz[linha][coluna] para referenciar uma posio da ma-


triz (mesmo formato de utilizao caso a matriz tivesse sido declarada estatica-mente no programa).

Programa 2.7: Exemplo de uso de alocao de matrizes

1 1/* programa_memoria_04.c */ #include #include

6int ** aloca(int i, int j); void libera(int **p, int i, int j); void leitura(int **p, int i, int j); void imprime(int **p, int i, int j);

11int main(void) {

int **p; int **p1;

16p = aloca(,); leitura(p, , );

p1 = aloca(,); leitura(p1,,);

1 imprime(p,,); imprime(p1,,);

libera(p,,); libera(p1,,);

6

return 0; }

1

6

/* 2 asteriscos (*) indicam que ser retornada uma matriz */ int ** aloca(int i, int j) {

/* ponteiro de ponteiro. Indica que ser alocada uma matriz de 2 dimenses */ int **p; int x;p = calloc(i,sizeof(int)); /* alocao de linhas... */ if( p == NULL ) {

printf("\nErro de alocacao"); exit(-1);

Uso de Memria 1

41

46

1

} for(x=0;x


1

}free(p); /* libera as linhas */

}

Finalmente, o programa .8 realiza a alocao de matrizes de uma forma diferente. No programa . a funo aloca retorna o ponteiro para uma matriz alocada, no programa .8 a funo aloca recebe um ponteiro j deinido e deve alocar a memria solicitada pelo programador. Sempre que uma funo precisa alocar memria para um ponteiro recebido, esta funo deve receber o ponteiro do ponteiro. A notao de uso de ponteiro para ponteiro normalmente confunde os proissionais menos experientes. Pode-se tomar como regra a utilizao do ponteiro precedido de um * e entre parnteses para cada dimenso que se deseja manipular. A partir da segunda dimenso possvel utilizar a notao de coluna para manipulao da matriz.

Programa 2.8: Exemplo de uso de alocao de matrizes dentro de funes

1/* programa_memoria_05.c */ #include #include

void aloca(int ***p, int x, int y);

8

1

/* a funo recebe um ponteiro para uma matriz */ void aloca(int ***p, int x, int y) {

int i; *p = (int **)malloc(sizeof(int) * x); if( *p == NULL ) {

printf("\nErro de alocacao de memoria!"); exit(1);

}

18

8

for( i = 0; i

Uso de Memria

int main(void) {

int **p; /* declarao de uma matriz com duas dimenses */ int i,k;

aloca(&p,4,); /* passando para a funo o endereo de memria do ponteiro */

8

4

for( i=0;i


10 #include #endif

1

typedef struct agenda {

char nome[40]; char email[40]; int telefone;

} AGENDA;

0 void aloca( AGENDA **pAgenda, int *piEntradas ); void consulta( AGENDA *pAgenda, int iEntradas);

void qs_ordena(AGENDA pAgenda[], int left, int right ); void ordena( AGENDA pAgenda[], int iEntradas );

void excluir(AGENDA **pAgenda, int *piEntradas); void pesquisar(AGENDA *pAgenda, int iEntradas); void alterar(AGENDA *pAgenda, int iEntradas);

0 int main(void) {

AGENDA * pAgenda;

int iEntradas, op; iEntradas=0;

40

pAgenda = (AGENDA *) malloc(sizeof(AGENDA)); /* alocando espao para a posio 0 do vetor */ if( pAgenda == NULL ) {

printf("\nErro de alocacao de memoria."); exit(1);

}

4

0

do {

flush(stdin); printf("\n1 - Inclusao"); printf("\n2 - Alteracao"); printf("\n3 - Consulta"); printf("\n4 - Excluir"); printf("\n5 - Pesquisar"); printf("\n9 - Sair"); printf("\nEntre com uma opcao -> "); scanf("%d", &op);

Uso de Memria

60

if( op == 1 ) { /* farei aqui para ilustrar algumas formas de manipular ponteiros */ flush(stdin);

/* alocao de ponteiros em funes requer trabalhar com ponteiros para ponteiros */ aloca(&pAgenda, &iEntradas);

6

0

printf("*** Inclusao ***"); printf("\nEntre com o Nome:"); /* forma 1 - endereo ponteiro inicial + x posies na memria quando se trabalhar com o endereo, deve-se usar -> */ gets((pAgenda+iEntradas)->nome); flush(stdin);

printf("Entre com o email:"); /* forma 2 - endereo ponteiro inicial + x posies na memria quando se trabalhar com ponteiro (contedo do endereo ou *), deve-se usar o . (ponto) */ gets((*(pAgenda+iEntradas)).email); flush(stdin);

80 printf("Entre com o telefone:"); /* forma 3 - trabalhando como vetor */ scanf(%d, &pAgenda[iEntradas].telefone); flush(stdin);

8

0

100

iEntradas++; } else if( op == ){

alterar(pAgenda, iEntradas); } else if( op == ) {

/* se o vetor de estruturas vai ser somente lido no preciso passar ponteiro para ponteiro */ ordena(pAgenda, iEntradas); consulta(pAgenda, iEntradas);

} else if( op == 4) { ordena(pAgenda, iEntradas); excluir(&pAgenda, &iEntradas); }else if( op ==


10{

ordena(pAgenda, iEntradas); pesquisar(pAgenda,iEntradas);

} } while(op!=);

}

110

11

10

void consulta(AGENDA *pAgenda, int iEntradas) {

int i; for(i=0;i= iEntradas ) {

printf("\nRegistro nao encontrado"); } else {

printf("\n\tRegistro %d", i); printf("\n\tNome : %s", pAgenda[i].nome ); printf("\n\tEmail : %s", pAgenda[i].email ); printf("\n\tFone : %d", pAgenda[i].telefone ); printf(?Q?W&RQUPDDDOWHUDFDR"); op = getch(); if( op == S || op == s ) {

flush(stdin); printf("\nEntre com o Nome:"); /* forma 1 - endereo ponteiro inicial + x posies na memria quando se trabalhar com o endereo, deve-se usar -> */

Uso de Memria

gets((pAgenda+i)->nome); flush(stdin);

1

160

printf("Entre com o email:"); /* forma 2 - endereo ponteiro inicial + x posies na memria quando se trabalhar com ponteiro (contedo do endereo ou *), deve-se usar o . (ponto) */ gets((*(pAgenda+i)).email); flush(stdin);

16

printf("Entre com o telefone:"); /* forma 3 - trabalhando como vetor */ scanf("%d", &pAgenda[i].telefone); flush(stdin);

} }

}

10

1

180

18

10

1

void excluir(AGENDA **pAgenda, int *piEntradas) {

char op; int i=0; char nome[40]; printf("\n\tDigite o Nome:"); flush(stdin); gets(nome); /* Uso a sintaxe (*pAgenda)[i].nome pelo fato de ser ponteiro de ponteiro. Os parnteses neste caso servem para ixar a primeira posio da memria, pois a linguagem C tende a trabalhar com ponteiros de ponteiros como se fossem matrizes (que na prtica so ponteiros para ponteiros) */ for(i=0; i < *piEntradas && strncmp( (*pAgenda)[i].nome, nome, strlen(nome))!=0;i++); if( i>= *piEntradas ) {

printf(\nRegistro no encontrado); } else {

flush(stdin); printf("\n\tRegistro %d", i); printf("\n\tNome : %s", (*pAgenda)[i].nome ); printf("\n\tEmail : %s", (*pAgenda)[i].email ); printf("\n\tFone : %d", (*pAgenda)[i].telefone ); printf(?Q?W&RQUPDDH[FOXVDR");op = getch(); if( op == S || op == s ) {

/* copio o ltimo elemento para o elemento corrente */ (*pAgenda)[i] = (*pAgenda)[(*piEntradas)-1];


00

0

(*piEntradas)--; /* excluo o ltimo elemento com realoc */ aloca(pAgenda, piEntradas);

} }

}

10

1

void aloca( AGENDA **pAgenda, int *piEntradas ) {

(*pAgenda) = (AGENDA *)(realloc(*pAgenda, (*piEntradas+1)*sizeof(AGENDA))); if( *pAgenda == NULL ) {

printf("\nErro de re-alocacao de memoria"); exit(1);

} }

0

void pesquisar(AGENDA *pAgenda, int iEntradas) {

char op; int i=0; char nome[40]; printf("\n\tDigite o Nome:"); flush(stdin); gets(nome);

0

40

4

for(i=0; i < iEntradas && strncmp( pAgenda[i].nome, nome, strlen(nome))!=0;i++); if( i>= iEntradas ) {

printf("\nRegistro nao encontrado"); } else {

do {

flush(stdin); printf("\n\n\tRegistro %d", i); printf("\n\tNome : %s", pAgenda[i].nome ); printf("\n\tEmail : %s", pAgenda[i].email ); printf("\n\tFone : %d", pAgenda[i].telefone ); printf(?Q?W3UR[LPR" );op = getch(); i++; if(i>=iEntradas) {

i = 0; }

Uso de Memria

0

} while( op == S || op == s); }

}

void ordena( AGENDA pAgenda[], int iEntradas ) {

qs_ordena(pAgenda, 0, iEntradas-1 ); }

60

void qs_ordena(AGENDA pAgenda[], int left, int right ) {

register int i, j; char * x; AGENDA t;

6

i = left; j = right; x = pAgenda[(left+right)/].nome;

0

80

do {

while(strcmp(pAgenda[i].nome,x)left) j --; if( i

3. Pilha

A tecnologia dominada por aqueles que gerenciam o que no entendem.

Arthur Bloch

Uma pilha um conjunto ordenado de itens, no qual novos itens podem ser inseridos e a partir do qual podem ser eliminados itens de uma extremidade, cha-mada topo da pilha. Tambm chamada de lista linear, onde todas as inseres e eliminaes so feitas em apenas uma das extremidades, chamada topo. A igura .1 mostra a representao de uma pilha.

Figura 3.1: Exemplo de Pilha

A estrutura de dados do tipo pilha tem como caracterstica que a ltima informao a entrar a primeira a sair (LIFO - last in irst out). A estrutura em pilha tem os seguintes mtodos ou funes:

Pilha 41

push - coloca uma informao na pilha (empilha).

pop - retira uma informao da pilha (desempilha).

size - retorna o tamanho da pilha.

stackpop - retorna o elemento superior da pilha sem remov-lo (equi-valente s operaes de pop e um push).

empty - veriica se a pilha est vazia.

A aplicao da estrutura de pilhas mais freqente em compiladores e sis-temas operacionais, que a utilizam para controle de dados, alocao de variveis na memria etc.

O problema no uso de pilhas controlar o inal da pilha. Isto pode ser feito de vrias formas, sendo a mais indicada criar um mtodo para veriicar se existem mais dados na pilha para serem retirados.

Tomando a pilha da igura . como exemplo, a operao push(H) ir acrescentar um novo elemento ao topo da pilha sendo, em seguida, executado um conjunto de operaes sobre a pilha:

- push(I) - Coloca o elemento I no topo da Pilha

- pop() - Retorna o elemento I

4 - pop() - Retorna o elemento H

- pop() - Retorna o elemento F

6 - pop() - Retorna o elemento E

- pop() - Retorna o elemento D

8 - push(D) - Coloca o elemento D no topo da Pilha

- push(E) - Coloca o elemento E no topo da Pilha


Figura 3.2: Operaes em uma pilha

3.1 Representao das Operaes com Pseudo-cdigo

As operaes de pilha podem ser representadas com algumas linhas de pseu-do-cdigo. Os algoritmos empty (.1), push (.), pop (.), stackpop (.4) e size (.) demonstram as operaes numa pilha. Estes cdigos podem ser adap-tados para qualquer linguagem de programao [].

Algoritmo 3.1: Veriicao se a pilha est vazia (funo EMPTY(S))

3.2 Pilhas em C

Antes de programar a soluo de um problema que usa uma pilha, ne-cessrio determinar como representar uma pilha usando as estruturas de dados existentes na linguagem de programao. Uma pilha um conjunto ordenado de itens, e a linguagem C j contm um tipo de dado que representa um conjunto ordenado de itens: o vetor. Ento, sempre que for necessrio utilizar a estrutura

Pilha 4

de pilhas para resolver um problema pode-se utilizar o vetor para armazenar esta pilha. Mas a pilha uma estrutura dinmica e pode crescer ininitamente, enquanto um vetor na linguagem C tem um tamanho ixo; contudo, pode-se de-inir este vetor com um tamanho suicientemente grande para conter esta pilha.

Algoritmo 3.2: Colocar um item na pilha (funo PUSH(S,x))

Algoritmo 3.3: Retirada de um item da pilha (funo POP(S))

Algoritmo 3.4: Pega o item do topo da pilha mas no desempilha (funo STACKPOP(S))


Algoritmo 3.5: Tamanho da pilha (funo SIZE(S))

O programa .1 apresenta um exemplo de programa em C para manipula-o de pilhas.

Programa 3.1: Exemplo de manipulao de pilha

/* programa_pilha_01.c */

#include

8

void push(int valor); int pop(void); int size(void); int stacktop(void);

int pilha[0]; int pos=0;

1 void push(int valor) {

pilha[pos]=valor; /* Empilha um novo elemento. No veriicada a capacidade mxima da pilha.*/ pos++; return;

}

int pop() {

/* Retorna o elemento do topo da ilha. No veriicado o inal da pilha. */ return (pilha[--pos]);

}

8

int size() {

return pos; /* retorna o topo da pilha */ }

Pilha 4

int stacktop() /* retorna o topo da pilha sem desempilhar */ { return pilha[pos]; }

8

4

int main(int argc, char ** argv ) { printf("\nColocados dados na pilha"); push(1); push(); push();

printf("\nTamanho da pilha %d", size());

48 printf("\nPegando dado da pilha: %d", pop()); printf("\nPegando dado da pilha: %d", pop()); printf("\nPegando dado da pilha: %d", pop());

printf("\nTamanho da pilha %d", size()); return 0; }

Uma pilha em C pode ser declarada como uma estrutura contendo dois ob-jetos: um vetor para armazenar os elementos da pilha e um inteiro para indicar a posio atual do topo da pilha (programa .).

Programa 3.2: Exemplo de manipulao de pilha com estrutura

/* programa_pilha_02.c */

#include #include #deine TAMANHO_PILHA 100

10

/* Estrutura que ir conter a pilha de informaes */ struct pilha {

int topo; int itens[TAMANHO_PILHA];

};

1int empty(struct pilha *p) {

if( p->topo == -1


0

{ return 1;

} return 0;

}

0

int pop(struct pilha *p) {

if( empty(p) ) {

printf("\nPilha vazia"); exit(1);

} /* retorna o item da pilha atual e diminui a posio da pilha */ return (p->itens[p->topo--]);

}

40

4

void push(struct pilha *p, int e) {

if( p->topo == (TAMANHO_PILHA - 1)) {

printf("\nEstouro da pilha"); exit(1);

} /* aps veriicar se no haveria estouro na capacidade da pilha, criada uma nova posio na pilha e o elemento armazenado */ p->itens[++(p->topo)] = e; return;

}

0

int size(struct pilha *p) {

/* sempre lembrando que na linguagem C o ndice de um vetor comea na posio 0 */ return p->topo+1;

}

int stackpop(struct pilha *p) {

return p->itens[p->topo]; }

60int main(void) {

struct pilha x; x.topo = -1;

push(&x,1);

Pilha 4

6 push(&x,); push(&x,);

printf("\nTamanho da pilha %d", size(&x)); printf(?Q(OHPHQWRGRWRSRGDODG, stackpop(&x));

0

printf("\n%d", pop(&x)); printf("\n%d", pop(&x)); printf("\n%d", pop(&x)); printf("\n%d", pop(&x)); return 0; }

3.3 Exerccios

Dada uma pilha P, construir uma funo que inverte a ordem dos ele-mentos dessa pilha, utilizando apenas uma estrutura auxiliar. Deinir adequadamente a estrutura auxiliar e prever a possibilidade da pilha estar vazia.

Construir uma funo que troca de lugar o elemento que est no topo da pilha com o que est na base da pilha. Usar apenas uma pilha como auxiliar.

Dada uma pilha contendo nmeros inteiros quaisquer, construir uma funo que coloca os pares na base da pilha e os mpares no topo da pilha. Usar duas pilhas como auxiliares.

1.

.

.

4. Fila

A sutileza do pensamento consiste em descobrir a semelhana das coisas diferentes

e a diferena das coisas semelhantes.Charles de Montesquieu

Uma ila um conjunto ordenado de itens a partir do qual se podem elimi-nar itens numa extremidade - incio da ila - e no qual se podem inserir itens na outra extremidade - inal da ila.

Ela uma prima prxima da pilha, pois os itens so inseridos e removidos de acordo com o princpio de que o primeiro que entra o primeiro que sai - irst in, irst out (FIFO).

O conceito de ila existe no mundo real, vide exemplos como ilas de banco, pedgios, restaurantes etc. As operaes bsicas de uma ila so:

insert ou enqueue - insere itens numa ila (ao inal).

remove ou dequeue - retira itens de uma ila (primeiro item).

empty - veriica se a ila est vazia.

size - retorna o tamanho da ila.

front - retorna o prximo item da ila sem retirar o mesmo da ila.

A operao insert ou enqueue sempre pode ser executada, uma vez que teoricamente uma ila no tem limite. A operao remove ou dequeue s pode ser aplicado se a ila no estiver vazia, causando um erro de underlow ou ila vazia se esta operao for realizada nesta situao.

Fila 4

Tomando a ila da igura 4.1 como exemplo, o item a apresenta a ila no seu estado inicial e executado o conjunto de operaes:

dequeue() - Retorna o item A (a ila resultante representada pelo item B)

enqueue(F) - O item F armazenado ao inal da ila (a ila resultante representada pelo item C)

dequeue() - Retirado o item B da ila

enqueue(G) - Colocado o item G ao inal da ila (item D)

Figura 4.1: Operaes numa ila

4.1 Representao de Filas com Pseudo-cdigos

As operaes em ila podem ser representados com os seguintes blocos de cdigo: a operao enqueue (4.1), dequeue (4.), empty (4.), size (4.4) e front (4.). Estes cdigos podem ser adaptados para qualquer linguagem de progra-mao [].


Algoritmo 4.1: Incluso de dados na ila (ENQUEUE(Q,x))

Algoritmo 4.2: Retirada de dados na ila (DEQUEUE(Q))

Algoritmo 4.3: Veriicao se a ila est vazia (funo EMPTY(Q))

Fila 1

Algoritmo 4.4: Tamanho da ila (funo SIZE(Q))

Algoritmo 4.5: Prximo elemento da ila (funo FRONT(Q))

4.2 Filas em C

A exemplo do que ocorre com estrutura em pilha, antes de programar a soluo de um problema que usa uma ila, necessrio determinar como repre-sentar uma ila usando as estruturas de dados existentes na linguagem de pro-gramao. Novamente na linguagem C podemos usar um vetor. Mas a ila uma estrutura dinmica e pode crescer ininitamente, enquanto que um vetor na linguagem C tem um tamanho ixo. Contudo, pode-se deinir este vetor com um tamanho suicientemente grande para conter a ila. No programa 4.1 apresen-tado um exemplo para manipulao de ilas.

Programa 4.1: Exemplo de manipulao de ila em C

/* programa_ila_01.c */ #include #include

#deine TAMANHO_MAXIMO 100

8struct queue {

int itens[TAMANHO_MAXIMO]; int front,rear;

};

1 int empty(struct queue * pq)


18

8

{ /* se o incio da ila for igual ao inal da ila, a ila est vazia */ if( pq->front == pq->rear ) {

return 1; } return 0;

} void enqueue(struct queue * pq, int x) {

if( pq->rear + 1 >= TAMANHO_MAXIMO ) {

printf(?Q(VWRXURGDFDSDFLGDGHGDOD); exit(1);

} pq->itens[ pq->rear++ ] = x; return;

}

int size(struct queue * pq) {

return (pq->rear + 1); }

8 int front(struct queue * pq) {

/* o primeiro elemento sempre est no incio do vetor */ return pq->itens[0];

}

4

48

8

int dequeue(struct queue * pq) {

int x, i; if( empty(pq) ) {

printf("\nFila vazia"); exit(1);

} /* Salva o primeiro elemento e refaz o arranjo dos itens, puxando o segundo elemento para o primeiro, o terceiro para o segundo e assim sucessivamente. */ x = pq->itens[0]; for( i=0; i < pq->rear; i++) {

pq->itens[i] = pq->itens[i+1]; } pq->rear--; return x;

}

Fila

6

68

int main(void) {

struct queue q; q.front = 0; q.rear = 0; enqueue(&q,1); enqueue(&q,); enqueue(&q,); enqueue(&q,4);

8

printf("\nFila vazia %d", empty(&q)); printf(?Q7DPDQKRGDODG, size(&q)); printf(?Q3UR[LPRGDODG, front(&q)); printf(?Q7LUDQGRGDODG, dequeue(&q)); printf(?Q7LUDQGRGDODG, dequeue(&q)); printf(?Q7LUDQGRGDODG, dequeue(&q)); printf(?Q3UR[LPRGDODG, front(&q)); printf(?Q7LUDQGRGDODG, dequeue(&q));

printf("\nFila vazia %d", empty(&q));

8 printf("\n"); }

No programa 4.1, o vetor foi deinido para comportar apenas 100 elemen-tos, caso fosse inserido um 1010 elemento, haveria o estouro da pilha mesmo aps vrias operaes de dequeue. Para resolver este problema, na operao dequeue foi implementada uma tcnica de redistribuio dos elementos na ila, de tal forma que nunca se chegue a estourar a ila caso haja vrias operaes de insero ou remoo (exceto se realmente houver 100 elementos da ila e houve uma tentativa de insero de um novo elemento). O programa 4. o trecho que implementa a tcnica comentada:

Programa 4.2: Reajuste da ila

x = pq->itens[0]; for( i=0; i < pq->rear; i++) {

pq->itens[i] = pq->itens[i+1]; } pq->rear--;

Esta tcnica ineiciente, pois cada eliminao da ila envolve deslocar cada elemento restante na ila. Se uma ila contiver 1000 ou 000 elementos, cada ele-mento retirado da ila provocar o deslocamento de todos os demais elementos. A operao de remoo de um item na ila deveria logicamente trabalhar somen-


te com aquele elemento, permanecendo os demais elementos em suas posies originais.

A soluo para o problema deinir o vetor como um crculo, em vez de uma linha reta. Neste caso, os elementos so inseridos como numa ila reta, e a remoo de um elemento da ila no altera os demais elementos da ila. Com o conceito de ila circular, ao chegar ao inal da ila, o ponteiro de controle da ila vai imediatamente para o incio da ila novamente (se este estiver vago). As seguintes operaes exempliicam a explicao (acompanhar o desenvolvimento da ila na igura 4.), sendo o caso 1 o estado inicial da ila:

Estado inicial enqueue(D) - O item D armazenado ao inal da ila enqueue(E) - O item D armazenado ao inal da ila dequeue() - Retirado o item A da ila enqueue(F) - O item F armazenado ao inal da ila enqueue(G) - O item G armazenado ao inal da iladequeue() - Retirado o item B da ila enqueue(H) - O item H armazenado ao inal da ila. Neste momento, o ponteiro da ila chegou ao inal do vetor que contm a implementao da ila. dequeue() - Retirado o item C da ila enqueue(I) - O item I armazenado ao inal da ila (mas no incio do vetor)enqueue(K) - O item K armazenado ao inal da ila (mas na segunda posio do vetor)

O programa 4. mostra a declarao da estrutura para uma ila circular.

Programa 4.3: Declarao de estrutura circular


4

struct queue {

int itens[TAMANHO_MAXIMO]; int front,rear;

}; struct queue q; q.front = q.rear = -1

1...4..

6..

8.

.

Fila

Figura 4.2: Operaes numa ila circular

Desta forma, as funes de manipulao de ila (empty, enqueue, dequeue, size e front) devem sofrer modiicaes para reletir a nova condio de ila cir-cular (programa 4.4):

Programa 4.4: Manipulao de ila circular em C

/* programa_ila_02.c */ #include #include


10

struct queue { int itens[TAMANHO_MAXIMO]; int front,rear; };


1

0

int empty(struct queue * pq) {

if( pq->front == pq->rear ) {

return 1; } return 0;

}

0

40

void enqueue(struct queue * pq, int x) {

/* Inverso das posies dos ponteiros. Se o inal do vetor j foi alcanado, ento retorna-se ao incio do vetor */

if( pq->rear == TAMANHO_MAXIMO-1) {

pq->rear = 0; } else {

pq->rear++; } if( pq->rear == pq->front ) {

printf(?Q(VWRXURGDOD); exit(1);

} pq->itens[pq->rear] = x; return;

}

4

0

int size(struct queue * pq) {

/* se o inal da ila ainda no alcanou o inal do vetor... */ if( pq->front rear) {

return pq->rear - pq->front; /* ... ento o tamanho da ila o inal da ila menos o incio da ila... */ }

/* ... se no, quer dizer que o ponteiro de inal da ila j alcanou o inal do vetor e foi reposicionado para o incio do vetor, ento o tamanho da ila a quantidade de itens que ainda restam at chegar ao inal do vetor somando itens que esto no incio do vetor */ return pq->rear + pq->front;

}

60int front(struct queue * pq) {

Fila

return pq->itens[pq->front+1]; }

6

0

int dequeue(struct queue * pq) {

int x, i; if( empty(pq) ) {

printf("\nFila vazia"); exit(1);

}

80

/* Inverso das posies dos ponteiros. Se o inal do vetor j foi alcanado, ento retorna-se ao incio do vetor */ if( pq->front == TAMANHO_MAXIMO - 1) {

pq->front = 0; } else {

pq->front++; } return (pq->itens[ pq->front ]);

}

8

0

int main(void) {

struct queue q; q.front = -1; q.rear = - 1; enqueue(&q,1); enqueue(&q,); enqueue(&q,); enqueue(&q,4);

100

10

printf(?Q7DPDQKRGDODG, size(&q)); printf(?Q3UR[LPRGDODG, front(&q)); printf(?Q7LUDQGRGDODG, dequeue(&q)); printf(?Q7LUDQGRGDODG, dequeue(&q)); printf(?Q7LUDQGRGDODG, dequeue(&q)); printf(?Q3UR[LPRGDODG, front(&q)); printf(?Q7LUDQGRGDODG, dequeue(&q)); printf(?Q7DPDQKRGDODG, size(&q));enqueue(&q,); enqueue(&q,6); enqueue(&q,); enqueue(&q,8);


110

11

enqueue(&q,); printf(?Q7DPDQKRGDODG, size(&q)); printf(?Q3UR[LPRGDODG, front(&q)); printf(?Q7LUDQGRGDODG, dequeue(&q)); printf(?Q7LUDQGRGDODG, dequeue(&q)); printf(?Q7LUDQGRGDODG, dequeue(&q)); printf(?Q7LUDQGRGDODG, dequeue(&q)); printf(?Q3UR[LPRGDODG, front(&q)); printf(?Q7LUDQGRGDODG, dequeue(&q)); printf(?Q7DPDQKRGDODG, size(&q));

10

1

10

1

140

enqueue(&q,10); enqueue(&q,11); enqueue(&q,1); enqueue(&q,1); enqueue(&q,14); enqueue(&q,1); enqueue(&q,16); enqueue(&q,1); enqueue(&q,18); printf(?Q7DPDQKRGDODG, size(&q)); printf(?Q3UR[LPRGDODG, front(&q)); printf(?Q7LUDQGRGDODG, dequeue(&q)); printf(?Q7LUDQGRGDODG, dequeue(&q)); printf(?Q7LUDQGRGDODG, dequeue(&q)); printf(?Q7LUDQGRGDODG, dequeue(&q)); printf(?Q7LUDQGRGDODG, dequeue(&q)); printf(?Q3UR[LPRGDODG, front(&q)); printf(?Q7LUDQGRGDODG, dequeue(&q)); printf(?Q7LUDQGRGDODG, dequeue(&q)); printf(?Q7LUDQGRGDODG, dequeue(&q)); printf(?Q7DPDQKRGDODG, size(&q)); printf(?Q7LUDQGRGDODG, dequeue(&q)); printf(?Q7DPDQKRGDODG, size(&q));

printf("\nFila vazia %d", empty(&q));

10

1

enqueue(&q,0); enqueue(&q,1); enqueue(&q,); enqueue(&q,); enqueue(&q,4); enqueue(&q,); printf(?Q7DPDQKRGDODG, size(&q)); printf(?Q3UR[LPRGDODG, front(&q)); printf(?Q7LUDQGRGDODG, dequeue(&q)); printf(?Q3UR[LPRGDODG, front(&q)); printf(?Q7LUDQGRGDODG, dequeue(&q));

Fila

160

Documents

Estrutura de Dados Com Algoritmos e C - Marcos Laureano