terça-feira, novembro 27, 2007

DQTimer - Um timer e cronômetro para Windows - Parte 2


Neste segundo post vou dar algumas explicações sobre o código do utilitário que eu descrevi na primeira parte.

C e WinAPI

Este tipo de utilitário é bem apropriado para ser desenvolvido em C usando a API do Windows, pois basicamente envolve o desenho simples na tela. Como ferramenta usei o velho e confiável Visual C++ 6.

Uma série (incompleta) sobre este tipo de programação pode ser vista aqui e aqui.

Os Estados do Programa

A variável modo indica o estado atual do programa:
  • ANDANDO: o relógio está andando.
  • PARADO: o relógio está parado e ainda não foi decidido se ele funcionará como timer ou cronômetro.
  • PAUSADO: o relógio está parado no meio de uma operação como timer ou cronômetro.
  • ALARME: o relógio está apresentando a indicação de final da contagem regressiva do timer.
Uma janela de Classe

No Windows, uma classe de janela é algo semelhante a uma classe em uma linguagem orientada a objeto: uma espécie de "forma" utilizada para criar as instâncias ou objetos propriamente ditos (no caso as janelas).

A definição de classe utilizada não tem nada de muito especial. O comportamento das janelas desta classe será governado pela Rotina de Janela que veremos adiante.

Na criação da janela são usados dois flags mais incomuns: WS_EX_TOPMOST deixa a janela por cima das demais e WS_EX_TOOLWINDOW cria uma janela sem moldura, sem barra de título e que não aparece na barra de tarefas.

A Rotina de Janela

A interface com operador no Windows funciona através de mensagens. Ocorrências como a movimentação do mouse e o pressionamento dos seus botões ou das teclas do teclado geram mensagens que são passadas para a Rotina de Janela.

No nosso caso, a Rotina de Janela trata as seguintes mensagens (as demais são passadas para DefWindowProc que faz o tratamento padrão do Windows):
  • WM_CREATE: gerada quando a janela está sendo criada, é usada para posicionar a janela e criar um timer de 0,5 segundo.
  • WM_TIMER: na medida do possível, o Windows irá gerar esta mensagem na frequência que solicitamos. Ela é usada para solicitar a atualização da tela.
  • WM_ERASEBKGND: gerada pelo Windows quando toda a janela tem que ser redesenhada, desenha a parte fixa da janela.
  • WM_PAINT: gerada pelo Windows para solicitar a atualização da janela.
  • WM_NCHITTEST: uma mensagem que normalmente é tratada por DefWindowProc, é gerada pelo Windows para identificar a região da janela em que o cursor do mouse está posicionado. No nosso caso, usamos esta mensagem para definir a nossa barra de título e permitir arrastar a janela.
  • WM_LBUTTONUP: gerada quando o botão esquerdo mouse é solto. Usada para detectar os apertões nos botões do programa.
  • WM_DESTROY: gerada quando a janela é destruída, é usada para desligar o timer do Windows e gerar a mensagem WM_QUIT que encerra o programa principal.
A rotina DesenhaT

O desenho do fundo é feito escrevendo o bitmap do fundo por sobre a janela. No Windows isto é feito pela rotina BitBlt, com o auxilio de um "memory device context".

A rotina DesenhaM

Esta rotina é o coração da atualização da contagem. Uma vez que a geração de WM_TIMER não é garantida, a função timer() é usada para obter a data e hora atual em segundos.

Quando a contagem zero é atingida no timer, passa para o modo ALARME e dispara o sinal sonoro através da função PlaySound().

A atualização da tela em si é feita através de BitBlts entre um bitmap com os dígitos e indicações e a janela.

As demais Rotinas
  • Encerra trata o pressionamento do botão Close, destruindo a janela.
  • BotaoHora, BotaoMinuto e BotaoSegundo tratam o pressionamento dos respectivos botões, mudando o valor no mostrador.
  • BotaoClear limpa o mostrador e volta o programa para o estado PARADO.
  • BotaoSS: atualiza o estado conforme o estado atual.
Conclusão

Embora bastantes simples, o DQTimer já é um programa bastante útil. Os mais aventureiros, com experiência em programação Windows, podem incluir funções mais avançadas, como permitir escolher um arquivo WAV para o sinal de alarme.

segunda-feira, novembro 26, 2007

DQTimer - Um timer e cronômetro para Windows - Parte 1

Nestes posts vamos ver o desenvolvimento de um pequeno utilitário para Windows: um timer e cronômetro.

Introdução

Tudo começou com um post no blog Efetividade.net, ilustrado com um timer de cozinha. Nos comentários, alguém mencionou utilitários para PC com esta finalidade e daí surgiu a idéia de fazer um.

A interface com operador

Após algumas idéias mais mirabolantes, decidi me basear no formato de um 'finado' timer digital para cozinha:


Uma vez que este é o tipo de programa que eu pretendo deixar sempre visível na tela do micro, um tamanho pequeno me pareceu mais adequado. Para isto eu preferi abandonar o formato tradicional das janelas Windows (o que permite mostrar algumas técnicas menos comuns no programa). A tela do programa ficou assim:


Uma idéia que tive logo no início foi permitir que o programa pudesse ser usado como timer (contagem de tempo decrescente) ou cronômetro (contagem de tempo crescente). A operação ficou da seguinte forma:

Cronômetro
  • O pressionamento do botão Start/Stop com o mostrador em 0:00:00 inicia a contagem. Pressionamentos seguintes deste botão pausam e retomam a contagem.
  • O botão Clear, com o cronômetro pausado, zera a contagem voltando à condição inicial.
Timer
  • Os botões H, M e S são usados para programar o tempo de espera. O pressionamento do botão Start/Stop inicia a contagem regressiva. Pressionamentos seguintes deste botão pausam e retomam a contagem.
  • O botão Clear, com o cronômetro pausado, zera a contagem voltando à condição inicial.
  • Ao atingir a contagem 0:00:00 o timer pisca a tela e soa um sinal sonoro até que o botão Clear ou Start/Stop seja apertado.
Mostrador

Normalmente mostra a contagem atual em horas, minutos e segundos. Um C é apresentado quando operando como cronômetro e um T quando operando como timer. O C ou T pisca quando o relógio está andando e fica fixo quando o relógio está em pausa.

O executável pode ser baixado daqui. Os fontes estão aqui, no próximo post vou dar algumas explicacões sobre o código.

quinta-feira, novembro 22, 2007

Design Paterns na POG

Nos últimos meses andei dando manutenção em vários programas antigos. Embora não tenha encontrado muitos exemplos dignos do Worse Than Failure, de vez em quando um trecho fica atravessado na garganta.

Aviso: o post a seguir é irônico, quem preferir um texto mais sério dê uma olhada aqui.

Para felicidade de muitos e desespero de um grupo cada vez menor, a POG (Programação Orientada a Gambiarras) vem ganhando cada vez mais adeptos. Embora um dos pilares da POG seja o improviso, é possível detectar uma série de padrões de projeto nas criações dos praticantes desta metodologia.

Seguindo uma tradição não oficial da POG, os exemplos serão apresentados em Visual Basic (que muito consideram a linguagem perfeita para a POG). Seguindo outra tradição, os exemplos não forma testados e nenhuma referência foi consultada.

Constantes

As constantes devem ser preferialmente colocadas diretamente no código. Para maior otimização, quando elas estiverem envolvidas em cálculos deve ser colocado diretamente o valor final.

Estruturas de Dados

Uma das vantagens no VB é a não obrigatoriedade de declaração das variáveis. Isto permite realizar todo o potencial de improviso da metodologia POG.

No caso dos chatos implicarem com as declarações implícitas e obrigarem o uso de "Option Explicit", é essencial o uso de tipos genéricos como variants, strings e ints para garantir a máxima flexibilidade. Com um pouco de engenhosidade uma variável string pode substituir todos os demais tipos, inclusive matrizes.

Validação de Entrada

Infelizmente os usuários insistem em entrar com valores absurdos e em considerar como bug quando o programa retorna valores também absurdos.

A maneira mais adotada na POG para implementar a validação de entrada é fazer testes diretos contra valores ilegais, à medida em que os usuários os forem inventando. Ao detectar um valor ilegal, um valor legal deve ser silenciosamente adotado.

Se isto gerar reclamações, apresente uma mensagem de erro com um texto humilhante e obrige o usuário a refazer uma grande quantidade de passos. Isto terá um efeito disciplinador, fazendo com que o usuário seja cuidadoso na entrada de dados.

Por exemplo, uma construção típica na POG é o teste de um campo vazio:

If Text1 = "" Or Text1 = " " Or Text1 = " " Or Text1 = " " Then
Text1 = "(vazio)"

Tratamento de Erros

Tratamento de erros é para maricas e a POG desaconcelha o seu uso. Entretanto, os gerentes tendem a ficar do lado dos chorões dos usuários e os praticantes da POG se vem obrigados a implementar tratamentos de erros.

O cálice sagrado do tratamento de erro está disponível no VB:

On Error Resume Next

Uma alternativa menos eficaz é o tratamento específico aos erros:

arq$ = "xis"
On Error GoTo DeuCaca
Apaga:
Delete arq$
GoTo Apagou
DeuCaca:
If Error = -123 Then
Begin
If arq$ = "xis" Then arq = "yps" Else arq = "ze"
GoTo Apaga
End
Apagou:

Subrotinas

Os adeptos da POG costumam evitar as subrotinas, preferindo criar trechos imensos de código. No caso de uma mesma funcionalidade ser necessária em mais de um ponto, aplica-se a técnica C&P (Cut and Paste). Além do ganho em desempenho, isto confere a flexibilidade de ter versões ligeiramente diferentes.

Mensagens

Na POG as mensagens apresentadas ao operador seguem sempre a nomenclatura do programa. Por exemplo, é preferível "Código inputado não passou no teste de Módulo 11" ao invés de "Código incorreto, verifique o valor digitado". Neologismos (como o 'inputado' acima) contam pontos extras.

Controle de Fluxo

Na POG o controle de fluxo é obtido através de IFs e GOTOs. Como alternativa aos GOTOs podem ser usados flags e mais IFs. Neste segundo caso existem dois padrões comuns: usar uma única variável para todos os testes ou um nova variável para cada teste. Pontos de bonus para nomes criativos como 'flag', 'teste', 'flag33', etc.

O uso de SWITCH / CASE é desaconselhado pelos puristas na POG.

Traces e Logs

Os traces e logs são fundamentais na POG como o intrumento exclusivo para a depuração. Mensagens típicas de trace e log são "passei por aqui", "ponto 1", "i = 1", "não devia passar por aqui!".

Uma vez forçado o funcionamento do programa, existem duas técnicas comumente usadas: comentar todas as instruções de traces e logs ou deixá-las na execução normal. É considerado um desvio grave da filosofia POG a existência de um controle do nível de log ou trace, principalmente em tempo de execução.

segunda-feira, novembro 19, 2007

Para quem trabalhou sozinho na sexta...

Para quem trabalhou sozinho na sexta (ou hoje em SP)

http://www.bugbash.net/comic/129.html

Obs.: eu trabalhei, mas desta vez a empresa não emendou. Mas a sensação não me é estranha!

sexta-feira, novembro 16, 2007

Pilha e Fila - Os Algorítmos Clássicos

Na série sobre Listas Ligadas, mencionei dois tipos especializados de listas lineares: Pilha e Fila. Neste post vou apresentar os algorítmos clássicos de implementação destes tipos usando alocação sequencial.

Pilha

Uma pilha é uma lista onde as inserções e remoções são sempre feitas na mesma ponta. Desta forma, o item removido primeiro é o que foi inserido por último (LIFO - Last In First Out). As pilhas são úteis quando queremos armazenar temporariamente uma informação que vamos usar logo depois. Por exemplo, a maioria dos processadores utiliza uma pilha para armazenar os endereços de retorno de subrotinas, permitindo que subrotinas sejam chamadas dentro de subrotinas. Algorítmos recursivos (como o quicksort) também costumam usar pilhas.

É costume chamar a operação de inserção na pilha de Push e a inserção de remoção de Pop (na inserção estamos 'empurrando' um elemento no alto da pilha e na remoção o elemento no topo 'pula' para fora da pilha).

A implementação de uma pilha é muito simples. Temos um vetor de N posições para armazenar os elementos e um índice (ou ponteiro) para indicar o topo. Algumas variações são possíveis:
  • Podemos empilhar os itens no sentido de índices (ou endereços) crescentes ou decrescentes.
  • O índice do topo pode apontar para a posição de remoção ou para a posição de inserção.
Duas situações de erro devem ser previstas: tentar inserir um item em uma pilha cheia (overflow) e tentar remover um item de uma pilha vazia (underflow).

Segue um exemplo de implementação em C, empilhando no sentido de índices crescentes e com o índice de topo apontando para a posição de inserção. Neste exemplo a pilha contém ponteiros e o valor NULL é usado para indicar underflow.
#define N 10 // número de elementos na pilha
void *pilha[N]; // a pilha
int topo = 0; // índice para o topo da pilha

// Coloca um elemento no topo da pilha
// Retorna FALSE se pilha cheia
int Push (void *elemento)
{
if (topo == N)
return FALSE;
pilha [topo++] = elemento
return TRUE;
}

// Retira o elemento no topo da pilha
// Retorna NULL se pilha vazia
void *Pop ()
{
if (topo == 0)
return NULL;
return pilha [--topo];
}
(Esta implementação é também um exemplo clássico do uso dos operadores de pós incremento e pré decremento do C).

Fila

Uma fila é uma lista onde as inserções são sempre feitas em uma ponta e as remoções são sempre feitas na outra. Desta forma remove-se sempre o item mais antigo (FIFO - First In First Out). AS filas são úteis para sincronizar duas tarefas assíncronas, armazenado temporariamente dados produzidos por uma delas até serem consumidos pela outra.

Quando examinamos as listas genéricas sequenciais , verificamos que era preciso mover os elementos após uma inserção ou remoção. No caso específico da fila isto pode ser evitado implementando uma fila circular, na qual os ponteiros voltam ao início quando passam do final.

A forma mais convencional de implementar uma fila circular é ter um vetor de N+1 elementos e dois índices (ou ponteiros), um apontando para onde será feita a próxima inserção e outro apontando para onde será feita a próxima remoção. A fila vazia é indicada pela igualdade dos índices (ou ponteiros). Para não confundir fila cheia com fila vazia, deixa-se sempre pelo menos uma posição livre no vetor (daí ele ter N+1 posições para armazenar N elementos).
#define N 10  // número máximo de elementos na fila
void *fila [N+1]; // a fila
int iPoe = 0; // indice para onde inserir
int iTira = 0; // indice para onde retirar

// Coloca um elemento na fila
// Retorna FALSE se fila cheia
int Poe (void *elemento)
{
int aux;

// calcula o valor de pPoe após a inserção
aux = iPoe + 1;
if (aux > N)
aux = 0; // circula

// Testa fila cheia
if (aux == iTira)
return FALSE;

// Coloca na fila
fila [iPoe] = elemento
iPoe = aux;
}

// Retira elemento da fila
// Retorna NULL se fila vazia
void *Tira ()
{
void *aux;

// Testa fila vazia
if (iPoe == iTira)
return NULL;

// Pega o elemento a retirar
aux = fila [iTira];

// Avanca iTira
iTira = iTira + 1;
if (iTira > N)
iTira = 0; // circula

return aux;
}
Um truque comum é usar uma potência de pois para N+1 e fazer o índice dar a volta através de um AND. Por exemplo, Se N+1 for 16, o avanço de iTira no final da rotina Tira pode ser simplificado para
iTira = (iTira+1) & 15;

quarta-feira, novembro 14, 2007

Patch Tuesday - Curiosidades

Para quem ainda não percebeu, a Microsoft disponibiliza as correções do "Automatic Update" sempre na segunda terça de cada mês. É o chamado Patch Tuesday.

Devido à forma como é feito o download dos updates normalmente recebemos o aviso ao ligar o micro na quarta feita (no meu caso, agora a pouco). É comum os updates envolverem trechos do Windows que estão normalmente em execução. Por este motivo é frequente ser necessário reinicar o Windows ao final da atualização (vide MoveFileEx).

O mecanismo usado pelo Automatic Update para baixar as atualizações é chamado de BITS (Background Intelligent Transfer Service), que procura reduzir a interferência do download nas demais operações do micro, utilizando os momentos em que a rede está livre. O BITS pode ser usado por qualquer aplicação, informações sobre ele pode ser vista em

http://blogs.msdn.com/larryosterman/archive/2007/08/20/applet-mitigations-updaters.aspx
http://en.wikipedia.org/wiki/Background_Intelligent_Transfer_Service
http://msdn2.microsoft.com/en-us/library/aa362827.aspx
http://msdn.microsoft.com/library/default.asp?url=/library/en-us/dnwxp/html/WinXP_BITS.asp

terça-feira, novembro 13, 2007

Listas Ligadas - Parte 7

Com este post vamos encerrar esta passada rápida sobre as listas ligadas, falando sobre a implementação na linguagem C++.

Listas Ligadas em C++

O código apresentado anteriormente pode, é claro, ser utilizado diretamente em um programa C++. Entretanto, é mais elegante criar uma classe que encapsule as estruturas e rotinas. Por exemplo, o destrutor da classe pode percorrer a lista liberando a memória alocada para os nós. As situações de erro, indicadas através de um retorno FALSE nas rotinas anteriores, podem ser sinalizadas através de exceções.

Uma desvantagem do código apresentado anteriormente é que ele é específico para um determinado tipo de elemento (nos exemplos a lista armazenava sempre inteiros). Se precisarmos, por exemplo, de uma lista para inteiros e uma lista para números de ponto flutuante, será preciso duplicar a maior parte do código e das estruturas de dados.

Uma solução, que pode também ser usada em C, é armazenar no nó um ponteiro para a informação ao invés da própria informação. Se este ponteiro for do tipo void *, ele poderá apontar para qualquer tipo de informação. Isto permite, inclusive, guardar em uma lista elementos de tipo diferente. A desvantagem desta solução é que ela é pouco robusta quanto ao controle dos tipos. Além disso, a alocação e liberação das áreas que contém as informações precisa ser feita por uma camada externa à de controle da lista (já que a lista desconhece o formato e tamanho da área de informações).

A linguagem C++ possui um recurso justamente para os casos em que se deseja definir uma função ou classe de forma independente dos tipos dos dados a serem manipulados: os templates.

Um template é uma espécie de macro cujo parâmetro é um tipo ou uma classe. Por exemplo, vamos definir um template de uma função para somar dois números:
template  T Soma (T a, T b)
{
return a+b;
}
Podemos usar este template com qualquer classe que suporte o operador +, o C++ verificará se os parâmetros são do mesmo tipo:
int a,b,c;
double x,y,z;

c = Soma (a,b); // soma dois inteiros
z = Soma (x,y); // soma dois doubles
z = Soma (a,y); // erro, tipos diferentes
Podemos usar templates também na definição de classes:
template  class NO
{
T valor; // dado do elemento
NO *prox; // ponteiro para o elemento seguinte

// ...
};
Portanto podemos criar um template capaz de criar uma classe de lista para cada tipo que precisarmos.

Melhor ainda, isto já foi feito. O Visual C++ possui dois templates para criação de listas duplamente ligadas:
  • CList, que faz parte da MFC; e
  • list, que faz parte da STL (Standard Template Library).
Referências
  • The Art of Computer Programming, Volume 1 Fundamental Algorithms – Donald E. Knuth
  • An Introduction To Data Structures With Applications – Jean-Paul Tremblay & Paul G. Sorenson
  • The C Programming Language – Brian W. Kernighan & Dennis M. Ritchie.

segunda-feira, novembro 12, 2007

Listas Ligadas - Parte 6

Listas Duplamente Ligadas

Uma desvantagem da lista ligada simples é que podemos seguir os links apenas em uma direção. Por exemplo, nas rotinas de inserção tivemos que usar duas variáveis, uma para guardar o endereço do nó atual e outra para guardar o endereço do nó anterior.

Na lista duplamente ligada armazenamos em cada nó dois ponteiros, um para o próximo nó e outro para o anterior. Ficamos com algo assim:
// estrutura de um elemento (nó) da lista
typedef struct no_lista
{
int valor; // dado do elemento
no_lista *prox; // ponteiro para o elemento seguinte
no_lista *ant; // ponteiro para o elemento anterior
} NO;

// variavel que aponta para o início da lista
NO inicio; // inicio.prox aponta para o primeiro elemento

// Insere um valor na lista na posição pos
int Insere (int pos, int valor)
{
NO *pno, *p;
int i;

// procura o ponto a inserir
for (i = 0, p = &inicio;
(i <>prox != NULL); i++)
{
p = p->prox;
}
if (i != pos)
return FALSE; // posicao invalida

// Insere
pno = malloc (sizeof (NO));
if (pno == NULL)
return FALSE; // faltou memoria
pno->valor = valor;
pno->prox = p->prox;
pno->ant = p;
if (p->prox != NULL)
p->prox->ant = pno;
p->prox = pno;

return TRUE; // sucesso
}

sexta-feira, novembro 09, 2007

Listas Ligadas - Parte 5

Listas Ligadas

As listas ligadas são uma alternativa às listas sequenciais. Como os elementos não estão em posições sequenciais é necessário acrescentar aos elementos informações que permitam percorrer a lista sequencialmente. Desta forma os elementos são ligados uns aos outros.

Obs.: A forma mais comum de fazer as ligações é através de ponteiros. Entretanto, nada impede de implementar uma lista ligada sobre um vetor alocado estaticamente, usando como link o índice do elemento.

Listas Ligadas Simples

Na sua forma mais simples, uma lista ligada é implementada através de:
  • Um ponteiro para o primeiro elemento da lista
  • Um ponteiro em cada elemento da lista apontando para o próximo elemento
Um valor especial (em C, tipicamente NULL e mais raramente –1) é utilizado para indicar o fim da lista.

As listas ligadas são normalmente representadas graficamente como retângulos (os elementos ou nós), interligados através de setas:

A direção da seta neste diagrama é importante, a origem da seta é um ponteiro que armazena o endereço do elemento na outra ponta. Portanto, é possível percorrer o link apenas no sentido da seta.

O símbolo no final da seta que sai do item 3 (símbolo de aterramento em circuitos elétricos) indica o fim da lista. Em outras palavras, o ponteiro possui o valor especial de fim de lista.

Uma lista vazia é simplesmente

A inserção de um novo item consiste apenas em alterar ponteiros:

Idem para a remoção de um item:

O código abaixo mostra uma implementação simples de lista ligada em C:
// estrutura de um elemento (nó) da lista
typedef struct no_lista
{
int valor; // dado do elemento
struct no_lista *prox; // ponteiro para o elemento seguinte
} NO;

// variavel que aponta para o início da lista
NO *inicio;

// Inicia a lista
void IniciaLista ()
{
inicio = NULL;
}

// Insere um valor na lista na posição pos
int Insere (int pos, int valor)
{
NO *pno, *p;
NO **pant;
int i;

// procura o ponto a inserir
for (i = 0, pant = &inicio, p = inicio;
(i < pos) && (p != NULL); i++)
{
pant = &p->prox;
p = p->prox;
}
if (i != pos)
return FALSE; // posicao invalida
// Insere
pno = malloc (sizeof (NO));
if (pno == NULL)
return FALSE; // faltou memoria
pno->valor = valor;
pno->prox = p;
*pant = pno;
return TRUE; // sucesso
}

// Remove elemento na posição pos
int Remove (int pos)
{
NO *p;
NO **pant;
int i;

// procura o elemento a remover
for (i = 0, pant = &inicio, p = inicio;
(i < pos) && (p != NULL); i++)
{
pant = &p->prox;
p = p->prox;
}
if ((i != pos) || (p == NULL))
return FALSE; // posicao invalida

// Remove
*pant = p->prox;
free (p);
return TRUE; // sucesso
}

// Soma os elementos da lista
int Soma ()
{
int total;
NO *p;

for (p = inicio, total = 0; p != NULL; p = p->prox)
total += p->valor;
return total;
}
As rotinas de inserção e remoção utilizam um ponteiro (pant) para guardar o endereço da variável que contém o endereço do nó atual. Isto dispensa tratar de forma diferente o caso em que o ponteiro a ser atualizado é o ponteiro para o inicio da lista. Uma forma de melhorar a legibilidade, desperdiçando um pouco de memória, é usar um nó para guardar o ponteiro de início:
NO inicio; // inicio.prox aponta para o primeiro elemento

// Insere um valor na lista na posição pos
int Insere (int pos, int valor)
{
NO *pno, *p;
NO *pant;
int i;

// procura o ponto a inserir
for (i = 0, pant = &inicio, p = inicio.prox;
(i < pos) && (p != NULL); i++)
{
pant = p;
p = p->prox;
}
if (i != pos)
return FALSE; // posicao invalida

// Insere
pno = malloc (sizeof (NO));
if (pno == NULL)
return FALSE; // faltou memoria
pno->valor = valor;
pno->prox = p;
pant->prox = pno;
return TRUE; // sucesso
}
Comparando uma lista sequencial a uma lista ligada, temos:
  • A lista ligada consome memória adicional para os links;
  • É fácil e rápido inserir e remover elementos, pois basta alterar ponteiros;
  • O acesso a um elemento qualquer da lista (acesso randômico) é mais trabalhoso e lento na lista ligada, pois é preciso percorrer os links;
  • O acesso sequencial para frente tem velocidade bastante semelhante;
  • É fácil quebrar e juntar listas, pois basta alterar ponteiros;
  • A estrutura de links da lista ligada leva facilmente a estruturas mais complexas, como uma lista onde os elementos são listas.
Portanto uma lista ligada é apropriada quando são esperadas várias inserções e/ou remoções e o acesso é essencialmente sequencial. Um exemplo é quando se deseja manter ordenada uma lista que sofre seguidas inserções e é pesquisada por busca sequencial.

No próximo post vamos ver as listas duplamente ligadas.

quinta-feira, novembro 08, 2007

Lista Ligadas - Parte 4

Neste post vamos examinar as Listas Lineares, com destaque para as Pilhas e Filas.
Listas Lineares

Definição

Listas Lineares são listas que apresentam somente uma relação de adjacência. Em uma lista linear existe um primeiro elemento e um último elemento, todos os demais elementos possuem um elemento anterior e um elemento seguinte.

Operações Básicas

As operações básicas que vamos examinar são:
  • Inserir um elemento em uma lista
  • Remover um elemento de uma lista
  • Percorrer os elementos de uma lista
Listas Lineares Especializadas

Existem dois tipos especializados de listas lineares que são encontrados com freqüência:
  • Uma pilha é uma lista onde todas as inserções e remoções são sempre feitas na mesma ponta. Desta forma, o item removido é sempre o que foi inserido mais recentemente. Por isso, as pilhas são à vezes chamadas de LIFO (last in first out, último a entrar primeiro a sair). Você pode visualizar este tipo de lista como uma pilha de caixas:

  • Uma fila é uma lista onde todas as inserções são sempre feitas em uma ponta e as remoções são sempre feitas na outra ponta. Desta forma, o item removido é sempre o que foi inserido a mais tempo. Por isso, as filas são à vezes chamadas de FIFO (first in first out, primeiro a entrar primeiro a sair). Você pode visualizar este tipo de lista como uma fila de pessoas:

Alocação Seqüencial

A maneira mais simples e óbvia de implementar uma lista é mantendo os elementos seqüencialmente na memória. Podemos fazer isto tanto usando um vetor alocado estaticamente como uma área alocada dinamicamente.

Um exemplo de alocação sequencial estática para uma lista genérica:
int lista [10];  // área para guardar a lista
// lista pode ter até 10 elementos
int tamlista; // número de elementos atualmente na lista

// inicia lista
void IniciaLista ()
{
tamlista = 0; // lista está vazia
}

// Insere um elemento na lista na posição pos
// (as posições são numeradas de 0 a tamlista-1)
int Insere (int pos, int elemento)
{
int i;

if (tamlista == (sizeof(lista)/sizeof(int)))
return FALSE; // lista cheia
if ((pos <> tamlista))
return FALSE; // posicao invalida
if (pos == tamlista)
{
// inserir no final
lista[tamlista++] = elemento;
}
else
{
// inserção no meio, mover os elementos seguintes
for (i = tamlista; i > pos; i--)
lista [i] = lista [i-1];
lista[pos] = elemento;
tamlista++;
}
return TRUE;
}
A rotina de inserção acima mostra uma desvantagem da alocação sequencial: é preciso mover os elementos na memória quando é feita uma inserção ou remoção.

Obs: no caso de filas e pilhas, onde as inserções e remoções são feitas nos extremos, é possível evitar a movimentação dos elementos.

Por outro lado, o acesso aleatório as elementos é muito simples. A rotina abaixo calcula a soma de todos os elementos da lista:
int Soma ()
{
int i, total;
for (i = total = 0; i < tamlista; i++)
total += lista[i];
return total;
}

No próximo post vamos examinar as Listas Ligadas Simples.

quarta-feira, novembro 07, 2007

Listas Ligadas - parte 3

Prosseguindo em nossa série, vamos concluir a introdução falando sobre o armazenamento de estruturas cujo tamanho varia durante a execução do programa.

Alocação Dinâmica de Memória em C

As declarações de variáveis em C que apresentamos até agora são o que chamamos de alocação estática: as posições de memória para armazenar as variáveis são definidas no momento da sua declaração e não se alteram mais.

A alocação estática é muito prática, segura e eficiente, porém impõem que o tamanho alocado será fixo durante toda a execução do programa. No caso de vetores, matrizes e listas isto pode não ser apropriado.

Existem duas funções básicas em C para alocar e liberar memória dinamicamente: malloc e free. A rotina malloc reserva uma determinada quantidade de bytes e retorna o ponteiro para a primeira posição. A rotina free libera uma região de memória, deixando-a disponível para alocações futuras. Uma vez que a rotina malloc enxerga a memória simplemente como uma sequência de bytes, cabe ao programador determinar quantos bytes são necessários para armazenar a informação e usar um cast para informar para que tipo de dado o ponteiro irá apontar.

Começando com um exemplo simples, a sequência abaixo aloca dinamicamente uma variável do tipo inteiro e armazena zero nela:
int *p;

p = (int *) malloc (sizeof (int));
*p = 0;
Reparar o uso de sizeof para determinar o tamanho em bytes da variável, o cast (int *) para informar que o ponteiro retornado por malloc será usado para apontar para um inteiro e *p para acessar a variável apontada por p.

Uma sequencia semelhante pode ser usada para alocar uma estrutura:
struct circulo *pc;

pc = (struct circulo *) malloc (sizeof (struct circulo));
pc->raio = 10;
A alocação de um vetor de 10 inteiros também é semelhante:
int *pv;

pv = (int *) malloc (10 * sizeof (int));
*pv = 0;
pv[9] = 1; // ultimo elemento do vetor alocado
Por último, um exemplo de alocação de um vetor de estruturas
struct circulo *pvc;

pvc = (struct circulo *) malloc (7 * sizeof (struct circulo));
(*(pvc+2)).raio = 10; // raio do 3o elemento
(pvc+2)->raio = 10; // idem
pvc[2].raio = 10; // idem

Note, mais uma vez, como a semelhança de notação para ponteiros e vetores na última linha do exemplo.

No próximo post vamos começar a examinar as listas, vendo as Listas Lineares.

terça-feira, novembro 06, 2007

Listas Ligadas - Parte 2

Continuando a nossa série, vamos continuar a falar sobre estruturas de dados, vendo dois exemplos importantes de como as estruturas de dados primitivas podem ser combinadas para gerar estruturas mais complexas.

Estruturas

O termo estrutura é usado para indicar uma estrutura não-primitiva composta por uma conjunto estruturado de dados primitivos. Por exemplo, podemos representar um ponto na tela por uma sequencia de dois inteiros contendo as duas coordenadas do ponto. Em C:
struct ponto
{
int x;
int y;
};
Neste exemplo, x e y são os campos da estrutura ponto. Na linguagem C utiliza-se a notação a.b para indicar o campo b da variável a. Por exemplo:
struct ponto pt;
pt.x = 10;
pt.y = 20;
Um campo de uma estrutura pode ser uma outra estrutura, criando um conjunto hierarquizado. Por exemplo, vamos definir uma estrutura para representar um círculo, composta por um ponto (centro) e um valor inteiro (raio):
struct circulo
{
struct ponto centro;
int raio;
};

struct circulo c;
c.centro.x = 20;
Repare no exemplo a notação c.centro.x para indicar o campo x do campo centro da variável c.

A linguagem C permite o uso de ponteiros com estruturas. Por exemplo:
struct circulo *pc;
struct circulo c;
int r, xis;

pc = &c;
r = (*pc).raio;
xis = (*pc).centro.x;
Para simplificar a codificação, a linguagem C permite substituir a notação “(*p).” por “p->” :
r = pc->raio;
xis = pc->centro.x;
Ao definir estruturas mais complexas (como as listas ligadas), pode surgir a necessidade de colocar dentro da estrutura um ponteiro para uma estrutura do mesmo tipo.Em C:
struct circulo
{
struct ponto centro;
int raio;
struct circulo *pc;
};
É importante entender que nessa declaração não estamos colocando uma estrutura dentro dela mesma (o que geraria uma recursão infinita). A linha “struct circulo *pc;” acima simplesmente acrescenta à estrutura circulo uma variável que conterá o endereço de uma outra variável do tipo círculo.

Vetores e Matrizes

Matrizes são conjuntos ordenados com um número fixo de elementos, não é possível acrescentar (inserir) ou retirar (remover) elementos. Um elemento de uma matriz é referenciado através de um conjunto de números inteiros sequenciais, os índices. A quantidade de índices usados para acessar uma matriz é a sua dimensão, uma matriz com dimensão um é um vetor.

Esta definição formal fica mais simples se examinarmos alguns exemplos. Comecemos examinando um vetor com 10 inteiros. Na linguagem C, podemos declará-lo da seguinte forma:
int v[10];
O vetor v é um conjunto com 10 elementos. Os elementos individuais são acessados através dos números 0, 1, 2, 3, 4, 5, 6, 7, 8 e 9, usando a seguinte notação:
v[5] = 3;
Este comando coloca o valor 3 no elemento de índice 5, que é o sexto elemento do vetor v.

Obs.: Na linguagem C os índices começam sempre de 0. Desta forma, um vetor com “n” elementos é acessado por índices de 0 a n-1. O elemento de índice “i” é o elemento “(i+’)-ésimo” do vetor.

Uma forma de visualizar um vetor é como uma sequência de elementos consecutivos:

v[0]v[1]v[2]v[3]v[4]v[5]v[6]v[7]v[8]v[9]

Uma matriz bi-dimensional pode ser visualizada como uma tabela. Por exemplo, considerando uma matriz de inteiros cujo primeiro índice varia de 0 a 2 e o segundo de 0 a 3:
int mat[3][4];

mat[0][0] = 3;
mat[2][3] = 2 * mat[0][0];
mat[0][0]mat[0][1]mat[0][2]mat[0][3]
mat[1][0]mat[1][1]mat[1][2]mat[1][3]
mat[2][0]mat[2][1]mat[2][2]mat[2][3]

A linguagem C trata de forma muito semelhante vetores e ponteiros:
  • as matrizes são armazenadas em posições sequênciais de memória.
  • O nome de uma váriavel do tipo matriz representa o endereço do primeiro elemento:
  • int vet[10];
    int *p;

    p = &vet[0]; // p recebe o endereço do primeiro
    // elemento de vet
    p = vet; // idem
  • Somar ou subtrair “n” a um ponteiro equivale a avançar ou recuar “n” elementos:
  • p = vet+2; // p aponta para o terceiro elemento

    p = vet; // p aponta para o primeiro elemento
    *(p+1) = 2; // (p+1) aponta para o 2o elemento
    // ou seja, equivale a vet[1] = 2
  • Expandindo o exemplo acima, o C considera p[n] equivalente a *(p+n). Ou seja, a última linha acima poderia ser escrita como
  • p[1] = 2;
  • Portanto, usa-se a mesma notação para acessar elementos apontados por um ponteiro (p) e elementos de um vetor (vet).

  • É importante lembrar que “int vet[10];” cria 10 variáveis do tipo inteiro, enquanto que “int *p;” cria apenas uma variável do tipo ponteiro para inteiro. A variável p só poderá ser utilizada para acessar elementos depois de ter sido inicializada.
No próximo post vamos encerrar esta introdução falando um pouco sobre a alocação dinâmica de memória no C.

segunda-feira, novembro 05, 2007

Listas Ligadas - Parte 1

Nesta nova série vou explicar o que são listas ligadas e apresentar os algorítmos envolvidos e algumas formas de implementação em C e C++.

Dê uma forma genérica poderíamos dizer que uma lista é um conjunto ordenado de um número variável de elementos, para a qual estão definidas funções de inserção e remoção de elementos. Para entendermos isto melhor, precisamos primeiro falar um pouco sobre estrutrua de dados.

Estrutura de Dados I

No nível mais baixo, as informações manipuladas por um computador consistem em conjuntos de itens elementares. As maneiras como estes item elementares se relacionam logicamente são as estruturas de dados. As formas como estas estruturas lógicas são implementadas fisicamente na memória de um computador são as estruturas de armazenamento.

Os itens elementares (ou estruturas primitivas de dados) são aqueles manipulados diretamente pelo computador ou linguagem de programação, tais como:
  • números inteiros
  • números reais (ponto fixo ou flutuante)
  • caracteres
  • valores lógicos
  • ponteiros
Obs.: Na maioria dos computadores atuais, os itens elementares são armazenados na memória como sequências de bytes. A distinção entre eles é consequência das instruções utilizadas para manipulá-los e não do conteúdo dos bytes. Por exemplo, um byte contendo o valar hexadecimal 0x30 pode ser interpretado como o número decimal 48 ou o caracter ‘0’, dependendo do código que o manipula. A linguagem C segue esta filosofia, permitindo misturar e re-interpretar (via cast) os tipos quase que livremente. Se por um lado isto dá uma imensa flexibiidade, por outro potencializa erros catastróficos.

Ponteiros

Do ponto de vista teórico, um ponteiro é uma referência a uma estrutura de dados. Do ponto de vista prático, um ponteiro é uma variável cujo conteúdo é o endereço de uma outra variável.

Vamos considerar a seguinte sequência de código C:
int a, b;
int *p;

a = 1;
p = &a;
b = *p;
*p = 5;
Nas duas primeiras linhas declaramos 3 variáveis (dois inteiros e um ponteiro para inteiro). O compilador irá reservar posições na memória para estas variáveis. Suponto que tanto um inteiro como um ponteiro ocupem 4 bytes na memória, podemos ter algo como:
Endereço  Conteúdo
2000 valor de a
2004 valor de b
2008 valor de p
A instrução “a = 1” coloca o valor 1 no endereço 2000. Quando escrevemos “&a” obtemos o endereço de a, portanto “p = &a” coloca o valor 2000 no endereço 2008. A notação “*p” no lado direito de uma atribuição significa:
  • pegue o valor da variavel p (2000 no nosso caso)
  • considere este valor como um endereço e pegue o valor contido neste endereço (1 no nosso caso)
portanto, “b = *p” coloca o valor 1 no endereço 2004.

Por último, “*p” no lado esquerdo de uma atribuição significa:
  • pegue o valor da variavel p (2000 no nosso caso)
  • considere este valor como um endereço e coloque o resultado do lado direito neste endereço (5 no nosso caso)
portanto, “*p = 5” coloca o valor 5 no endereço 2000.


No próximo post vamos ver um pouco mais sobre estrutura de dados, examinando estruturas, vetores e matrizes.