Resumo: Estrutura de Dados

...

Uso de Memória

Alocação estática= ocorre em tempo de compilação,é necessário que se definam seu tipo e tamanho.

Alocação dinâmica= ocorre em tempo de execução, ou seja, as variáveis e estruturas são declaradas sem a necessidade de se definir seu tamanho, pois nenhuma memória será reservada ao colocar o programa em execução.No momento em que uma variável ou parte de uma estrutura precise ser utilizada, sua memória será reservada e, no momento em que não for mais necessária, deve ser liberada.

Pode ser realizada com apenas quatro chamadas a funções:

Malloc= permite que seja feita a alocação de uma nova área de memória para uma estrutura. Deve-se informar para a função a quantidade de bytes para alocação. A função irá retornar, se existir memória suiciente, um endereço que deve ser colocado em uma variável do tipo ponteiro. Como a função retorna um ponteiro para o tipo void, deve-se utilizar o typecast, transformando este endereço para o tipo de ponteiro desejado.

Calloc= tem a mesma funcionalidade de malloc, exceto que devem ser fornecidos o tamanho da área e a quantidade de elementos. O espaço inicializa com zeros.

Realloc= permite que uma área previamente alocada seja aumentada ou diminuída. Expandir uma área alocada.

Free= libera uma área alocada previamente com a função malloc, calloc ou realloc. Deve ser passado para a função o endereço, que se deseja liberar.

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, chamada topo da pilha.

Inserções e eliminações são feitas em apenas uma das extremidades, a última informação a entrar é a primeira a sair.

Sua estrutura contém dois objetos: um vetor para armazenar os elementos da pilha e um inteiro para indicar a posição atual do topo.

Funções:

push - coloca uma informação na pilha (empilha).

pop - retira uma informação da pilha (desempilha).

size - retorna o tamanho da pilha.

stackpop - retorna o elemento superior da pilha sem removê-lo (equivalente às operações de pop e um push).

empty - veriica se a pilha está vazia.

Sua estrutura contém dois objetos: um vetor para armazenar os elementos da pilha e um inteiro para indicar a posição atual do topo.

Fila= Uma fila é um conjunto ordenado de itens a partir do qual se podem eliminar itens numa extremidade - início da fila - e no qual se podem inserir itens na outra extremidade - final da fila.

Funções:

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

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

empty - veriica se a fila está vazia.

size - retorna o tamanho da fila.

front - retorna o próximo item da fila sem retirar o mesmo da fila.

A operação remove ou dequeue só pode ser aplicado se a fila não estiver vazia, causando um erro de underflow ou fila vazia.

Recursividade= Recursão é o processo de definir algo em termos de si mesmo e é, algumas

vezes, chamado de definição circular. Assim, pode-se dizer que o conceito de algo recursivo está dentro de si. A função é recursiva se um comando no corpo da função a chama.

Cuidados com Recursividade

Ao escrever funções recursivas, deve-se ter um comando if em algum lugar para forçar a função a retornar sem que a chamada recursiva seja executada. Se não existir, a função nunca retornará quando chamada (equivalente a um loop ininito). Todo programa deve ter uma condição de parada não recursiva.

A principal vantagem das funções recursivas

É a possibilidade de utilizá-las para criar versões mais claras e simples de vários algoritmos.

Lista= É uma estrutura de dados similar a um pilha ou fila. Uma pilha ou fila tem um tamanho fixo na memória, e o acesso a um elemento da estrutura destrói o item selecionado (operação dequeue e pop). Na lista, cada elemento contém um elo (endereço) para o próximo elemento da lista. Desta forma a lista pode ser acessada de maneira randômica, podendo ser retirados, acrescidos ou inseridos elementos no meio da lista dinamicamente.

Simplesmente ligada= omitimos o ponteiro anterior em cada elemento.

Ordenada= a ordem linear da lista corresponde à ordem linear de chaves armazenadas em elementos da lista; o elemento minímo é o início da lista e o elemento máximo é o fim.

Não ordenada= os elementos podem aparecer em qualquer ordem.

Circular= o ponteiro anterior do início da lista aponta para o fim, e o ponteiro próximo do fim da lista aponta para o início.

Simplesmente encadeada= contém um elo (endereço) com o próximo item da lista. A representação de uma lista simplesmente encadeada é dada por um endereço (nó). Pode ser utilizada para representar uma pilha ou fila de dados dinamicamente.

Lista duplamente encadeada= contém elos (endereços) com o elemento anterior e com o elemento posterior a ele.

O último elemento da lista pode ter o endereço para um endereço nulo (caracterizando o final da lista) ou o endereço para o primeiro item lista (caracterizando uma lista circular).

Uma lista sem endereços (também conhecida como nós) é chamada de lista vazia ou lista nula. Uma observação importante:

O fato de haver dois nós tem duas vantagens principais: a lista pode ser lida em ambas as direções, o que simplifica o gerenciamento da lista. E, no caso de alguma falha de equipamento, onde uma das extremidades seja perdida, a lista pode ser reconstruída a partir da outra extremidade.