Aula 6 - Estruturas de Dados I: Explorando o C

Aula de Rogério Júnior

 

Até agora vimos estruturas de dados simples, como vetores e matrizes. Nesta aula, vamos aprender a usar um vetor e alguma variáveis  auxiliares para construirmos estruturas de dados mais complexas.

Pilha

A primeira estrutura que vamos ver é a pilha, pois só precisa de uma única variável auxiliar. Em uma pilha, o último elemento inserido é o primeiro a sair e, para implementar essa estrutura em C, só precisamos de um vetor e uma varável inteira $tam$ que guardará o tamanho do vetor. Uma pilha tem a função "push", que coloca um elemento no topo da pilha, a função "pop", que retira o elemento do topo da pilha, a função top, que diz qual é o elemento no topo e a clear, que tira todos os elementos da pilha. Para implementarmos as funções vamos logo declarar as variáveis que usaremos. Vamos definir que o tamanho máximo da pilha, MAXT, será 1000100. Vamos criar uma pilha de inteiros e, para isso, vamos declarar o vetor "int pilha[MAXT];" e a variável "int tam;". Declare tam global para que ela comece com o valor zero. Vamos indexar o vetor pilha de 1 a n, assim, o elemento do topo sempre será "pilha[tam]". Para excluir o elemento do topo, basta que façamos a redução da variável tam em 1 unidade, pois agora, o tamanho da pilha realmente será uma unidade menor e o termo "pilha[tam]" agora se refere a um elemento uma posição atrás do antigo topo, que é o que ocorre quando tiramos o topo de uma pilha: o novo topo será o elemento abaixo do antigo. Para inserirmos o elemento x na pilha, basta que aumentemos tam em 1 unidade, com o comando "tam++;", e depois façamos o topo da pilha receber x, com o comando "pilha[tam]=x;". Para limparmos a pilha, basta zerarmos a variável tam, com o comando "tam=0;".

É bom saber que podemos reduzir esses dois comando a uma única linha: "pilha[++tam]=x;". Note que como o operador "++" vem antes de "tam", primeiro o computador adiciona 1 unidade a tam e depois realiza o comando "pilha[tam]=x;". Se invertermos a ordem e escrevermos "pilha[tam++]=x;", primeiro o computador irá executar o comando "pilha[tam]=x;" e só então o comando "tam++;". Essa regra de precedência de operadores se aplica em qualquer ocasião. Escrever "int n = i++;" irá fazer primeiro n receber o valor de i para só então aumentar i em uma unidade. O comando "int n = ++i;" aumentará primeiro o valor de i para só então fazer n receber seu valor.

Segue um código com uma pilha e suas três funções já implementadas. Note que, por precaução, a função pop só elimina o topo da pilha se houver algum elemento nela (tam > 0), para que não corramos o risco de ter uma pilha com tamanho negativo:

Agora que você já sabe implementar um pilha, tente resolver o problema Trilhos. Se não conseguir, segue a solução explicada, mas realmente tente fazê-lo sozinho antes de lê-la.

Note que quando os vagões entram na estação, ficam todos enfileirados em cima dos trilhos, e apenas o último vagão que entrou tem liberdade para sair, ou seja, é como se empilhássemos os vagões. Para resolver o problema basta que façamos um for que quer percorrerá toda a sequência dos vagões que devem sair, que estará salva no vetor saida. Olhando qual o próximo vagão que deve sair, verifico se ele está no topo da pilha. Se ele não estiver, vou empilhando os vagões que ainda faltam entrar, até que chegue o vagão esperado. Quando o vagão chega, eu o tiro da pilha (dou um pop), passo para o próximo vagão que deve sair e continuo o algoritmo. Se em algum momento eu precisar empilhar mais um vagão e não houver mais nenhum esperando para entrar, então é impossível que eles saiam na ordem desejada. Segue o código para melhor entendimento. Vale lembrar que o operador "!" representa negação, ou seja, (!condicao) retorna o oposto de condicao: se condicao for verdadeira, !condicao seria falsa, e vice-versa.

Fila

Agora que você já viu como funciona uma pilha, pense em como implementar um fila. Em uma fila, o primeiro que entra é o primeiro que sai, ou seja, na fila a função push não coloca um novo elemento no topo, como na pilha, mas no final da fila. A função pop não tira o último elemento que foi inserido, mas o que está na fila há mais tempo. Não temos a função top, mas as funções front, que retorna o primeiro elemento na fila, e back, que retorna o último elemento da fila. Como não teremos mais a variável tam, podemos implementar, também, a função size, que retorna o tamanho da fila. Para implementar a fila, precisarmos novamente de um vetor que a guardará, que chamaremos de fila, e as variáveis inteiras ini e fim, que guardam em qual índice do vetor estão o primeiro e o último elemento da fila, respectivamente. É fácil ver que a função front deve retornar fila[ini] e a função back deve retornar fila[last]. A função pop deve excluir o elemento do começo, fazendo com que o próximo elemento da fila se torne o primeiro, logo, ela deve aumentar o valor de ini em uma unidade. A função push deve receber o elemento x, que será inserido, e então aumentar o tamanho da fila, fazendo com que seu fim seja uma posição depois da que ele era ("fim++;") e lá colocar o valor a ser inserido ("fila[fim]=x;"). Logo, ela deve realizar o comando "fila[++fim]=x;". O tamanho da fila será o a quantidade de elementos entre ini e fim, ou seja, deve retornar fim-ini+1. Note que a fila deve começar com ini=1 e fim=0, para que todas as funções funcionem com os comandos aqui mostrados, logo, para zerarmos a fila, basta fazermos essas duas variáveis assumirem esses valores. Segue um código com a implementação de uma fila de inteiros. Note que a função pop só retira o elemento se ele estiver lá (size()>0), para não corrermos o risco de termos uma fila de tamanho negativo. Na implementação, definimos o tamanho máximo da fila, novamente, como 1000100.

Agora que você já sabe implementar um pilha, tente resolver o problema Jogando Cartas Fora. Se não conseguir, segue a solução explicada, mas realmente tente fazê-lo sozinho antes de lê-la.

A pilha de cartas será representada por uma fila, pois as cartas são inseridas no fim dela (primeira que entra é a primeira que sai). A primeira coisa a se fazer é limpar a fila ("clear();") e inserir nela, ordenadamente, todas as cartas de 1 a n, com um for: ("for(int i=1; i<=n; i++) push(i);"). No começo da saída vamos imprimir a linha "Discarded Cards:". Vamos abrir um while que rodará enquanto ainda houver duas ou mais cartas na fila ("size()>=2"). Agora, dentro do loop, basta que façamos estritamente o que manda o problema: vamos imprimir a carta que está em cima do monte (a primeira da fila, pois foi a primeira a ser inserida) precedida de espaço em branco, com o comando "printf(" %d", front());"; depois retiramos essa carta da fila ("pop();"); depois colocamos a nova carta que está no topo na parte de trás da fila ("push(front());") e, novamente, a tiremos do começo da fila. Por fim, se inda houver mais de uma carta na fila ("if(size()>=2)") imprima a vírgula que separa os números. No fim de cada caso de teste, imprimiremos, em outra linha, a carta que ficou na pilha, seguida da quebra de linha, com o comando "printf("\nRemaining card: %d\n", front());". Segue o código para melhor entendimento:

Um ponto a ser ressaltado, em filas e pilhas e em qualquer outro programa é que chamar uma função é um pouco lento. Até agora, realmente implementei as funções das filas e pilhas, mas somente por ser mais didático que vejamos as chamadas das funções push, pop, size, ... mas é muito melhor simplesmente executar, na linha em que chamávamos a função, o comando que ela realiza ao invés de chamá-la. É mais rápido, por exemplo, usar o comando "tam--;" em uma pilha do que o comando "pop;". Para melhor compreensão, segue o código do problema anterior sem a implementação das funções da fila:

Agora que você já sabe tudo iss, tente fazer o problema Banco. Se não conseguir, segue a resposta abaixo, mas realmente tente fazê-lo sozinho antes de lê-la.

Este é um problema da segunda fase da P2 da OBI 2012, mas precisaremos apenas de uma fila e três vetores auxiliares para resolvê-lo. Vamos definir MAXC como o limite de c, MAXN como o limite de n e MAXF como o tempo máximo que o banco levará para finalizar todos os atendimentos (o número máximo de pessoas multiplicado pelo tempo máximo de atendimento e somado ao instante máximo de chegada (1000 x 10 + 300 = 10300)). Como MAXF é pequeno ($MAXF << 10^6$), podemos declará-lo com sobra e definir MAXF como 20000. O dois primeiros vetores auxiliares que vamos precisar são o int chegada[MAXN], que guardará o minuto em que cada pessoa da fila chegou (a pessoa $i$ chega no minuto $chegada[i]$), e o int tempo[MAXN], que guardará a duração do atendimento de cada pessoa (o atendimento da pessoa $i$ terá duração de $tempo[i]$ minutos). O terceiro é o int livre[MAXC], que vai guardar em qual minuto cada caixa vai ficar livre (o caixa $i$ ficará livre no instante $livre[i]$). Vamos guardar também uma variável auxiliar prox que guarda qual é a próxima pessoa que vai entrar na fila e a variável resposta, que guardará quantas pessoas vão esperar mais de 20 min na fila. No começo do programa vamos preencher os vetores chegada e tempo com as informações da entrada, indexando-os de 1 a n. O vetor livre deve ter todos os seus valores zerados (podemos declará-lo como global, por exemplo) pois, no começo, todos os caixas estarão livres no tempo 0. O valor de prox será 1, pois a primeira pessoa será a próxima a entrar na fila.

Para simular o andamento da fila, usaremos um for que representará a passagem do tempo, fazendo uma variável min variar de 0 até o tempo máximo que o banco levará para atender todos os clientes (MAXF). Para cada repetição do for, vamos simular o que acontece durante o minuto min. Vamos olhar quem é a próxima pessoa que vai chegar ao banco (prox) e verificar se ela já chega neste minuto, ou seja, se chegada[prox]==min. Se for, a insiro na fila com a função push e digo que a próxima pessoa que chegará será prox+1 (comando "prox++;"). Se prox for maior que n, então já chegaram todas as pessoas e não devo inserir ninguém. Vamos usar um while para repetir essa operação até que todas as pessoas que chegarão no minuto min entrem na fila. Feito isso, vou verificar se tem alguém na fila. Se tiver, vou procurar se já tem algum caixa vago, ou seja, percorrerei o vetor livre em busca de um caixa $i$ que está ficando livre agora ou que já ficou livre em um tempo anterior (livre[i]<=min). Se houver caixa livre, então essa pessoa será atendida, então devo olhar o tempo que ela esperou, que será o minuto atual subtraído do minuto em que ela chegou (min - chegada[front()]). Se esse tempo de espera for maior que 20 min, então adiciono uma pessoa a resposta (resposta++). Além disso, o instante em que o caixa $i$, que irá atender esse cliente, ficará livre será o minuto atual somado da duração do atendimento do cliente ("livre[i]=tempo[front()];"). Feito isso, vamos tirar a primeira pessoa da fila com o comando "pop();" e executar o comando "break;" para sairmos do for que procurava um caixa livre. Novamente, usaremos um while para repetir o procedimento de atender uma pessoa enquanto houver caixas livres. Para isso, usaremos uma bool vaga, que indicará se há algum caixa vago. Ela sempre começará false, mas, se após percorrermos o vetor livre encontrarmos algum caixa vago, ela receberá true, fazendo com que ela somente termine o while como false se tivermos percorrido todos os caixas e nenhum deles estiver livre. Vale lembrar que se não houver ninguém mais na fila ("if(size()==0)") e ninguém mais for chegar ao banco ("if(prox>n)"), podemos acabar o for agora com um break, executando o comando "if(size()==0 && prox>n) break;". Ao final do programa, imprimimos o valor de resposta, seguido da quebra de linha. Segue o código para melhor entendimento. Note que nele não há a implementação das funções, mas apenas os comandos que elas devem executar.

Criando sua própria estrutura

Até agora você usou variáveis e funções apenas de tipos já salvos no C++, como int, double, char e bool. Entretanto, a linguagem permite que você crie o seu próprio "tipo", a sua própria struct. Uma struct é um objeto como outro qualquer, com suas próprios objetos salvos. Para declarar uma struct de nome objeto, usamos o comando "struct objeto{};". Entre as chaves, escrevemos os membros  de objeto. Se quisermos, por exemplo, que objeto tenha duas variáveis, o int a e o int b, escrevemos isso entre as chaves, da forma: "struct objeto{ int a, b; };". Lembre-se que objeto não é o nome de uma variável, mas de um tipo, como int ou char, por exemplo. Ou seja, vamos declarar uma variável do tipo objeto. Ela teria que ter um nome assim como se fôssemos declarar uma do tipo int. Para declararmos a variável var do tipo objeto, usamos o mesmo comando que usaríamos em qualquer outro tipo: "objeto var;". Agora temos uma variável de nome var e do tipo objeto. Vamos, então, declarar a struct assim:

Como faço para acessar um membro de uma struct? Escrevo o nome da variável do tipo que criei (no caso var) seguido de um ponto (".") e então escrevo o nome do membro.  Se quiséssemos acessar o valor de a do objeto var, escreveríamos "var.a". Se já tivermos declarado o objeto var e escrevermos os comandos "var.a=3; var.b=4;", então o valor da variável a de var receberá 3 e o de b receberá 4. Como atribuímos 4 ao valor de b, o comando "printf("%d", var.b);" imprimiria o inteiro 4 na tela.

Podemos usar uma struct para representar objetos que são definidos por mais de um valor, inclusive de tipos diferentes. Um ponto, por exemplo, no plano cartesiano, é determinado por dois valores: os das suas coordenadas x e y, respectivamente. Logo, poderíamos representá-lo como uma struct que contêm duas doubles, o coord_x e o coord_y. Veja:

Um aluno, por exemplo, pode ser representado por seu nome (um vetor de char) e sua nota (uma double). Veja:

Assim como em qualquer outro tipo, podemos declarar um vetor de uma struct. Para representar uma sala de aula, por exemplo, posso criar um vetor de aluno de 100 posições de nome classe, com o comando "aluno classe[100];". Para ordená-lo, posso usar a função sort, desde que use uma função de comparação para que o sort saiba ordenar os alunos, que será feita exatamente como vimos na aula de ordenação. Agora, entretanto, não acessaremos os elementos em um outro vetor, todos serão membros de um mesmo elemento do vetor classe. Além disso, a função de comparação não mais receberá inteiros como identificadores do alunos, para depois procurar os seus atributod, mas receberá estruturas que, sozinhas, contêm todos os dados dos estudantes: o tipo aluno. Segue o código para melhor compreensão:

Agora que você já sabe tudo isso, tente fazer os problemas abaixo. Se surgir alguma dúvida teórica ou você não conseguir fazer algum deles, vá para a página inicial do curso e preencha o formulário para nos enviar sua dúvida.

Problema 1 - Ferry Loading III

Problema 2 - Ferry Loading IV

Problema 3 - Balanço de Parênteses 1

Problema 4 - Infixa para Posfixa

Problema 5 - Diamantes e Areia

Problema 6 - Parentheses Blance

Problema 7 - Bora Bora

Problema 8 - Trilhos Novamente... Traçando Movimentos

Clique aqui para voltar para a aula de ordenação e tentar resolver os problemas criando sua própria struct

---

As aulas do Curso Noic de Informática são propriedade do Noic e qualquer reprodução sem autorização prévia é terminantemente proibida. Se você tem interesse em reproduzir algum material do Curso Noic de Informática para poder ministrar aulas, você pode nos contatar por esta seção de contato para que possamos fornecer materiais específicos para reprodução.