Universidade Regional Integrada do Alto Uruguai e das Missões Campus Frederico Westphalen Departamento de Engenharias e Ciência da Computação Algoritmos e Estrutura de Dados I informática I
|
|  Yüklə 0.52 Mb.
|
7.5Estruturas de Controle Encadeadas ou AninhadasUm aninhamento ou encadeamento é o fato de se ter qualquer um dos tipos de construção apresentados anteriormente dentro do conjunto de comandos (comando composto) de uma outra construção. Em qualquer tipo de aninhamento é necessário que a construção interna esteja completamente embutida na construção externa. A 8.Estruturas de Dados HomogêneasAs estruturas de dados homogêneas permitem agrupar diversas informações dentro de uma mesma variável. Este agrupamento ocorrerá obedecendo sempre ao mesmo tipo de dado, e é por esta razão que estas estruturas são chamadas homogêneas. A utilização deste tipo de estrutura de dados recebe diversos nomes, como: variáveis indexadas, variáveis compostas, variáveis subscritas, arranjos, vetores, matrizes, tabelas em memória ou arrays. Os nomes mais usados e que utilizaremos para estruturas homogêneas são: matrizes (genérico) e vetores (matriz de uma linha e várias colunas). 8.1Matrizes de Uma Dimensão ou VetoresEste tipo de estrutura em particular é também denominado por profissionais da área como matrizes unidimensionais. Sua utilização mais comum está vinculada à criação de tabelas. Caracteriza-se por ser definida uma única variável vinculada dimensionada com um determinado tamanho. A dimensão de uma matriz é constituída por constantes inteiras e positivas. Os nomes dados às matrizes seguem as mesmas regras de nomes utilizados para indicar as variáveis simples. A sintaxe do comando de definição de vetores é a seguinte: Var <nome_da_variável> : MATRIZ [ <coluna_inicial> .. <coluna_final> ] DE <tipo_de_dado> Ex.: Var m : Matriz [1 .. 10] De Inteiro 8.1.1Operações Básicas com Matrizes do Tipo VetorDo mesmo modo que acontece com variáveis simples, também é possível operar com variáveis indexadas (matrizes). Contudo não é possível operar diretamente com o conjunto completo, mas com cada um de seus componentes isoladamente. O acesso individual a cada componente de um vetor é realizado pela especificação de sua posição na mesma por meio do seu índice. No exemplo anterior foi definida uma variável M capaz de armazenar 10 número inteiros. Para acessar um elemento deste vetor deve-se fornecer o nome do mesmo e o índice do componente desejado do vetor (um número de 1 a 10, neste caso). Por exemplo, M[1] indica o primeiro elemento do vetor, M[2] indica o segundo elemento do vetor e M[10] indica o último elemento do vetor. Portanto, não é possível operar diretamente sobre vetores como um todo, mas apenas sobre seus componentes, um por vez. Por exemplo, para somar dois vetores é necessário somar cada um de seus componentes dois a dois. Da mesma forma as operações de atribuição, leitura e escrita de vetores devem ser feitas elemento a elemento. 8.1.1.1Atribuição de Uma Matriz do Tipo VetorNo capítulo sobre as instruções primitivas, o comando de atribuição foi definido como: <nome_da_variável> := <expressão> No caso de vetores (variáveis indexadas), além do nome da variável deve-se necessariamente fornecer também o índice do componente do vetor onde será armazenado o resultado da avaliação da expressão. Ex.: m[1] := 15
8.1.1.2Leitura de Dados de Uma Matriz do Tipo VetorA leitura de um vetor é feita passo a passo, um de seus componentes por vez, usando a mesma sintaxe da instrução primitiva da entrada de dados, onde além do nome da variável, deve ser explicitada a posição do componente lido: LEIA <nome_da_variável> [ <índice> ] Uma observação importante a ser feita é a utilização da construção Para a fim de efetuar a operação de leitura repetidas vezes, em cada uma delas lendo um determinado componente do vetor. De fato esta construção é muito comum quando se opera com vetores, devido à necessidade de se realizar uma mesma operação com os diversos componentes dos mesmos. Na verdade, são raras as situações que se deseja operar isoladamente com um único componente do vetor. O algoritmo a seguir exemplifica a operação de leitura de um vetor:
numeros : matriz[1..10] de inteiro i : inteiro
8.1.1.3Escrita de Dados de Uma Matriz do Tipo VetorA escrita de um vetor obedece à mesma sintaxe da instrução primitiva de saída de dados e também vale lembrar que, além do nome do vetor, deve-se também especificar por meio do índice o componente a ser escrito: ESCREVA <nome_da_variável> [ <índice> ] O algoritmo a seguir exemplifica a operação de leitura e escrita de um vetor, utilizando a construção Para: Algoritmo exemplo_escrita_de_vetor Var numeros : matriz[1..10] de inteiro i : inteiro
Um exemplo mais interessante é mostrado a seguir, onde um vetor de dez números é lido e guardado no vetor numeros. Paralelamente, a soma destes números é calculada e mantida na variável soma, que posteriormente é escrita. Algoritmo exemplo_escrita_de_vetor_com_soma Var numeros : matriz[1..10] de inteiro i : inteiro soma : inteiro Início soma := 0 Para i de 1 até 10 faça Início Leia numeros[i] soma := soma + numeros[i] Fim Para i de 1 até 10 faça Início Escreva numeros[i] Fim Escrever “Soma = ”, soma Fim. 8.1.2Exemplos de Aplicação de VetoresO espectro de aplicação de vetores em algoritmos é muito extenso, mas normalmente os vetores são usados em duas tarefas muito importantes no processamento de dados: pesquisa e classificação. A pesquisa consiste na verificação da existência de um valor dentro de um vetor. Trocando em miúdos, pesquisar um vetor consiste em procurar dentre seus componentes um determinado valor. A classificação de um vetor consiste em arranjar seus componentes numa determinada ordem, segundo um critério específico. Por exemplo, este critério pode ser a ordem alfabética de um vetor de dados caracter, ou então a ordem crescente ou decrescente para um vetor de dados numéricos. Há vários métodos de classificação, mas o mais conhecido é o método da bolha de classificação (Bubble Sort).
8.1.2.1O Método da Bolha de ClassificaçãoEste método não é o mais eficiente, mas é um dos mais populares devido à sua simplicidade. A filosofia básica deste método consiste em “varrer” o vetor, comparando os elementos vizinhos entre si. Caso estejam fora de ordem, os mesmos trocam de posição entre si. Procede-se assim até o final do vetor. Na primeira “varredura” verifica-se que o último elemento do vetor já está no seu devido lugar (no caso de ordenação crescente, ele é o maior de todos). A segunda “varredura” é análoga à primeira e vai até o penúltimo elemento. Este processo é repetido até que seja feito um número de varreduras igual ao número de elementos a serem ordenados menos um. Ao final do processo o vetor está classificado segundo o critério escolhido. O exemplo a seguir ilustra o algoritmo bubble sort para ordenar 50 número inteiros em ordem crescente:
numeros : matriz [1..50] de inteiros aux, i, j: inteiro
j := 50
Enquanto j > 1 faça Início Para i de 1 até j-1 faça Início Se numeros[i] > numeros[i+1] Então Início aux := numeros[i]; numeros[i] := numeros[j]; numeros[j] := aux; Fim Fim j:=j-1;
Fim Escreva “vetor ordenado: ” Para i de 1 até 50 faça Início Escrever numeros[i] Fim Fim. Uma outra variação deste algoritmo, com as mesmas características utiliza duas construções Para, fazendo a comparação iniciando do primeiro elemento até o penúltimo, comparando com o imediatamente seguinte até o último elemento: Algoritmo Variação_do_Bubble_Sort Var numeros : matriz [1..50] de inteiros aux, i, j: inteiro
aux := numeros[i]; numeros[i] := numeros[j]; numeros[j] := aux; Fim Fim Fim Escreva “vetor ordenado: ” Para i de 1 até 50 faça Início Escrever numeros[i] Fim Fim. Podemos observar também que para ordenar o vetor em ordem decrescente basta inverter o sinal de comparação no teste da condição lógica Se numeros[i] > numeros[j], para: Se numeros[i] < numeros[j] |
figura 7.1 a seguir ilustra aninhamentos válidos e inválidos.