terça-feira, 16 de abril de 2013

Lista Encadeada


Ao utilizar vetores e pilhas até o momento, tem-se feito uso de armazenamento sequencial, cuja principal desvantagem é quantidade fixa que se reserva para seu uso, ao delimitar sua área permite-se a possibilidade de estouro, ou manter ocupado todo um bloco de memória quando em alguns momentos pode estar usando uma quantidade menor ou mesmo nenhum dado.

                Numa representação sequencial temos um item q[x] e implicitamente sabemos que o próximo elemento será q[x+1], para tornar explicita essa relação, o item irá ter dois campos, primeiro com a informação e o segundo com o endereço para o item seguinte, assim temos a estrutura de dados conhecida como lista encadeada, aonde cada item será chamada de nó.

                Com nó tendo um campo informação com o real elemento da lista e o campo endereço contendo um ponteiro para o próximo elemento, a lista encadeada é acessada a partir de um ponteiro externo (não incluído dentro do nó) lista que aponta para o primeiro nó da lista, o campo endereço para o ultimo nó irá ter o valor nulo, sendo invalido e indicando o final de uma lista.



info
next

info
next

info
next

info
next
lista













>


>


>


>

nulo















nó

nó

nó

nó














Por ser tratar de uma estrutura de dados dinâmica, o numero de nós na lista pode variar consideravelmente à medida que são inseridos e removidos. Basicamente existem duas maneiras de construir uma lista encadeada. A primeira consiste em adicionar o novo item sempre no inicio ou fim da lista. A outra é acrescentar itens em posições especificas da lista, podendo seguir a ordem crescente por exemplo.

A forma de armazenar os dados da lista dependerá do aplicativo, com três situações que podem ocorrer quando se insere um item na lista encadeada, como reflexo da inserção, quando se remove um item na lista encadeada, as três sequencias de operação se invertem:

                INSERIR

1.        Item pode se tornar o primeiro da lista;

info
next








































info
next

Info
next






lista













>


>

nulo
















·         Novo item copia o endereço de próximo que está em Lista.
·         Lista aponta para o novo item.

info
next











lista















>


>

















info
next

info
next



























>

nulo



















2.       Inserir entre dois outros itens;






info
next












































info
next








Info
next



lista

















>


>








nulo




















·         Novo item copia o endereço de próximo que está no item anterior.
·         Item anterior atualiza o endereço para o novo item.






info
next


































>









info
next








info
next



lista

















>


>








nulo





















3.       Ser o ultimo item da lista;

info
next

Info
next

info
next



lista













>


>

nulo



















·         Troca o Nulo pelo endereço do novo item no ultimo item da lista.
·         Indicar Nulo para o endereço de próximo no novo item.

info
next

info
next

info
next



lista













>


>


>

nulo


















EXCLUIR

1.       Excluir o primeiro da lista

info
next

Info
next

info
next



lista













>


>


>

nulo
















·         Copia o endereço de próximo no primeiro item para lista




Info
next

info
next



lista













>





>

nulo

















2.       Elimina numa posição intermediaria

info
next

Info
next

info
next



lista













>


>


>

nulo
















·         Copia no item anterior ao que vai ser excluído o endereço de próximo.

info
next




info
next



lista













>


>




nulo

















3.       Excluir o ultimo item

info
next

info
next

info
next



lista













>


>


>

nulo
















·         Troca o endereço que aponta para o item a ser excluído por nulo

info
next

info
next






lista













>


>

nulo





















Um modelo simples e didático de código em linguagem C para uma lista encadeada está incluído na próxima postagem “Exemplo de lista encadeada” e serve como complemento prático mostrando a programação completa das rotinas para inserir, excluir e percorrer.

Postado por às Nenhum comentário:
Marcadores: , ,

quinta-feira, 4 de abril de 2013

Rotinas para infixa

CÓDIGO-FONTE: https://github.com/r-bauer/infix/archive/master.zip


O arquivo stackapp.h terá suporte para três pilhas distintas, a primeira pilha utilizada para checagem de parênteses (programa exemplo da pilha genérica), uma segunda pilha usada na conversão de infixa para pós-fixa e a terceira pilha que calcula a expressão pós-fixa (rotinas para pós-fixa), atendendo assim a proposta de reaproveitar o trabalho feito.


typedef struct tagDATA
{
    char    cOpener;
} SDATA;

typedef struct tagDATAPOST
{
    float     fVal;
} SDATAPOST;

typedef struct tagDATAIN
{
    char     cOpr;
} SDATAIN;

               A rotina de conversão de infixa para pós-fixa discutida na postagem anterior segue abaixo. Dentro do laço principal da rotina que irá acessar cada argumento guardado na variável strInfix, montando o resultado na memória alocada em strPostfix, através dos passos:
1.      Sendo operando (numero), a ordem se mantém, devendo ser inserido na string
2.      Sendo operador, caso o símbolo seja:
a.      Fechar parênteses ‘)’, esvazia a pilha até encontrar ‘(‘
b.      Abrir parênteses ‘(‘, insere na pilha
c.      ‘-+*/$’, verifica qual a precedência entre o topo da pilha e o atual
                                                              i.     topo maior ou igual, insere topo e empilha atual
                                                             ii.     topo menor, empilha atual
3.      Terminado de percorrer os símbolos, esvazia a pilha, inserindo na string.

LOCAL int MakeStrPostfix(char **strInfix, char **strPostfix)
{
    int argc, iCnt;
    char **argv, *ptrP;
    SSTACK *stkIn;
    SDATAIN sdEl, *sdTop;

    *strPostfix = malloc(strlen(*strInfix) + 1);
    ptrP = *strPostfix;
    *ptrP = '\0';

    argc = CreateTableArg(*strInfix, &argv);

    stkIn = inCreateStack(argc);      

    for (iCnt = 0; iCnt < argc; ++iCnt)
    {
        if ( IsNumber(argv[iCnt]) )
        {
            if (*ptrP == '\0')
                sprintf(ptrP, "%s", argv[iCnt]);
            else
                sprintf(ptrP, "%s %s", ptrP, argv[iCnt]);
        }
        else //IsOperator
        {
            sdTop = inViewTopData(stkIn);

            if (sdTop == NULL) //IsEmpty
            {
                inPushData(stkIn, &argv[iCnt][0]);
            }
            else
            {
                if (argv[iCnt][0] == ')')
                {
                    while( inPopData(stkIn, &sdEl) &&
                           sdEl.cOpr != '(')
                    {
                        sprintf(ptrP, "%s %c", ptrP, sdEl.cOpr);
                    }
                }
                else if (argv[iCnt][0] == '(')
                {
                            inPushData(stkIn, &argv[iCnt][0]);
                }
                else if (Prcd(sdTop->cOpr, argv[iCnt][0]))
                {
                    inPopData(stkIn, &sdEl);
                    sprintf(ptrP, "%s %c", ptrP, sdEl.cOpr);
                    inPushData(stkIn, &argv[iCnt][0]);
                }
                else
                {
                    inPushData(stkIn, &argv[iCnt][0]);
                }                 
            }
        }
    }

    while (inPopData(stkIn, &sdEl) && sdEl.cOpr != '(')
    {
        sprintf(ptrP, "%s %c", ptrP, sdEl.cOpr);
    }

    return (EXIT_SUCCESS);
}

A função resultante é simples e pequena, devido a dois processos feitos em separados, com uma verificação de erro garantindo uma entrada valida e o uso de um vetor que permite acessar cada símbolo individualmente.

Alguns dos programas usados como exemplo neste blog, têm feito uso das variáveis argc e argv, quando programa em C é executado dentro de um SO (Sistema Operacional), este pode passar parâmetros ao programa através destas duas variáveis, argc é um inteiro que representa o numero de textos separados por espaços em branco e argv é um vetor de ponteiros de string. Se o usuário digitar INFIXA 1 + 2 * 3, resultaria em:

argv
--->
[0]
--->
I
N
F
I
X
A
\0


[1]
--->
1
\0







[2]
--->
+
\0







[3]
--->
2
\0







[4]
--->
*
\0







[5]
--->
3
\0






O nome do programa executado fica incluído no parâmetro de entrada junto da expressão a ser analisada, como feito no programa que calculava pós-fixa, em que ficava a cargo do usuário digitar corretamente a entrada, garantindo o funcionamento esperado da rotina.

Entretanto até um erro simples de digitação como escrever 1+2*3 sem espaços para separar os elementos irá gerar um comportamento indesejado, para melhorar a robustez do programa foi incluída a rotina VerifyStrInfix, que formata a string inserindo espaço entre os elementos e verifica se a entrada é valida através das seguintes regras:
1.      Apenas será aceito parênteses, dígitos e operadores
2.      operadores '+-/*$' precisam estar entre dígitos
3.      parênteses '()' tem que estar sempre em pares respeitando a posição
4.      digito não pode ser seguido de outro digito, ex.: 12 + 34   56 * 78 / 90
5.      operadores '+-/*$' não podem estar à esquerda de ')'
6.      operadores '+-/*$' não podem estar à direita de '('

1
if (!( IsOperator(argv[iCnt][jCnt]) ||
       IsBracket(argv[iCnt][jCnt]) ||
       IsDigit(argv[iCnt][jCnt]) ))
{
      return (EXIT_FAILURE);
}

2, 4, 5 e 6
if ((*(ptr-1) == '(' && IsOperator(*(ptr+1))) ||
      (IsOperator(*(ptr-1)) && *(ptr+1) == ')') ||
      (IsOperator(*(ptr-1)) && IsOperator(*(ptr+1))) ||
      (IsDigit(*(ptr-1)) && IsDigit(*(ptr+1))))
{
      return (EXIT_FAILURE);
}

3
if (VerifyBrackets(*strInfix))
      return (EXIT_SUCCESS);
else
      return (EXIT_FAILURE);

               Com VerifyStrInfix garantindo a validade e separando cada elemento com um espaço, a rotina MakeStrPostfix precisa apenas analisar cada elemento. Para facilitar o acesso a cada dado se utiliza a rotina CreateTableArg para montar um vetor de ponteiros, apontando individualmente cada informação, emulando a entrada de dados do SO feita com argc e argv, criando uma tabela de ponteiros e apontando para cada elemento na string com a expressão, substituindo os espaços pelo caractere nulo, a chamada da rotina irá gerar o resultado indicado abaixo.


argc = CreateTableArg(*strInfix, &argv);

ENTRADA
SAIDA






‘1’

‘1’
<---
[0]
<---
argv



‘  ‘

‘\0’







‘+’

‘+’
<---
[1]





‘  ‘

‘\0’







‘2’

‘2’
<---
[2]





‘  ‘

‘\0’







‘*’

‘*’
<---
[3]

argc
= 5


‘  ‘

‘\0’







‘3’

‘3’
<---
[4]





‘\0’

‘\0’








               Fechando a avaliação de expressão infixa usamos a função CalcInfix que agrega as demais sub-rotinas, fazendo a validação da entrada, convertendo infixa em pós-fixa, calculando à pós-fixa e apresentando o resultado final.

int CalcInfix(int argc, char *argv[])
{
      char *strInfix, *strPostfix;
      float fRes;
      int i;

      i = VerifyStrInfix(argc, argv, &strInfix);

      if (i == EXIT_SUCCESS)
      {
            MakeStrPostfix(&strInfix, &strPostfix);
            CalcPostfix(&strPostfix, &fRes);
            printf("%f\n", fRes);
      }

      return (i);
}

               Esta versão apresenta uma série de melhorias contendo a verificação de erros e suporte a exponenciação com inteiro negativo, porem continua a falta de suporte a números fracionários na entrada, facilmente contornado, como exemplo substitua a expressão 8 * 0.5 com 8 * (1/2) na entrada.

               Todos os arquivos do projeto podem ser encontrados no github.
Postado por às Nenhum comentário:
Marcadores: , , , , , , ,
Assinar: Postagens (Atom)