operacoes.md

Operações

Lista sequencial

• Inicialização, destruição e metadados

  • Inicializa lista
  • Destrói lista
  • Número de elementos na lista
  • Número de nodos disponíveis
  • Lista vazia?
  • Lista cheia?

• Recuperação de informação

  • Mostrar a lista
  • Recupera chave em posição específica (getter)
  • Obter chave do primeiro nó
  • Obter chave do último nó
  • Obter posição da chave

• Inserção de chaves

  • Insere chave em posição específica
  • Insere chave ordenado
  • Insere chave no início da lista
  • Insere chave no final da lista
  • Definir o valor da chave de uma posição específica (setter)

• Remoção de chaves

  • Remove nodo em posição específica
  • Remove nodo com determinada chave
  • Remove o início da lista
  • Remove o final da lista

Lista encadeada com alocações estática e dinâmica

• Inicialização, destruição e metadados

  • Inicializa lista
  • Destrói lista
  • Inicializa nodo de lista
  • Destrói nodo de lista
  • Número de elementos na lista
  • Número de nodos disponíveis
  • Lista vazia?
  • Lista cheia?

• Recuperação de informação

  • Mostrar a lista (simples e debug)
  • Recupera chave em posição específica
  • Busca por chave em lista e retorna o nodo
  • Obtém nodo sucessor de nodo
  • Obtém nodo início de lista
  • Obter o valor da chave em um nó específico

• Inserção de chaves

  • Insere chave em posição específica
  • Insere chave ordenado
  • Insere chave antes de um nodo
  • Insere chave no início da lista
  • Insere chave no final da lista
  • Definir o valor da chave em um nó específico

• Remoção de chaves

  • Remove nodo em posição específica
  • Remove nodo com determinada chave
  • Remove nodo indicado
  • Remove o início da lista
  • Remove o final da lista

Lista duplamente encadeada com alocação dinâmica

• Inicialização, destruição e metadados

  • Inicializa lista
  • Destrói lista
  • Inicializa nodo de lista
  • Destrói nodo de lista
  • Número de elementos na lista
  • Lista vazia?
  • Lista cheia?

• Recuperação de informação

  • Mostrar a lista (simples e debug)
  • Recupera chave em posição específica
  • Busca por chave em lista e retorna o nodo
  • Obtém nodo sucessor de nodo
  • Obtém nodo predecessor de nodo
  • Obtém nodo início de lista
  • Obtém nodo final de lista
  • Obter o valor da chave em um nó específico

• Inserção de chaves

  • Insere chave em posição específica
  • Insere chave ordenado
  • Insere chave antes de um nodo
  • Insere chave no início da lista
  • Insere chave no final da lista
  • Definir o valor da chave em um nó específico

• Remoção de chaves

  • Remove nodo em posição específica
  • Remove nodo com determinada chave
  • Remove nodo indicado
  • Remove o início da lista
  • Remove o final da lista

Lista encadeada circular com alocação dinâmica

• Inicialização, destruição e metadados

  • Inicializa lista
  • Destrói lista
  • Inicializa nodo de lista
  • Destrói nodo de lista
  • Número de elementos na lista
  • Avança início da lista em sentido horário ( shift right )
  • Avança início da lista em sentido anti-horário ( shift left )

• Recuperação de informação

  • Mostrar a lista (simples e debug)
  • Recupera chave em posição específica
  • Busca por chave em lista e retorna o nodo
  • Obtém nodo sucessor de nodo
  • Obtém nodo inicial de lista
  • Obtém nodo final de lista
  • Obter o valor da chave em um nó específico

• Inserção de chaves

  • Insere chave em posição específica
  • Insere chave ordenado
  • Insere chave antes de um nodo
  • Insere chave no início da lista
  • Insere chave no final da lista
  • Definir o valor da chave em um nó específico

• Remoção de chaves

  • Remove nodo em posição específica
  • Remove nodo com determinada chave
  • Remove nodo indicado
  • Remove o início da lista
  • Remove o final da lista

Lista duplamente encadeada circular com alocação dinâmica

• Inicialização, destruição e metadados

  • Inicializa lista
  • Destrói lista
  • Inicializa nodo de lista
  • Destrói nodo de lista
  • Número de elementos na lista
  • Avança início da lista em sentido horário
  • Avança início da lista em sentido anti-horário

• Recuperação de informação

  • Mostrar a lista (simples e debug)
  • Recupera chave em posição específica
  • Busca por chave em lista e retorna o nodo
  • Obtém nodo sucessor de nodo
  • Obtém nodo predecessor de nodo
  • Obtém nodo início de lista
  • Obtém nodo final de lista

• Inserção de chaves

  • Insere chave em posição específica
  • Insere chave ordenado
  • Insere chave antes de um nodo
  • Insere chave no início da lista
  • Insere chave no final da lista

• Remoção de chaves

  • Remove nodo em posição específica
  • Remove nodo com determinada chave
  • Remove nodo indicado
  • Remove o início da lista
  • Remove o final da lista

Pilha com alocações estática e dinâmica

• Inicialização, destruição e metadados

  • Inicializa pilha
  • Destrói pilha
  • Pilha vazia?
  • Pilha cheia?
  • Número de elementos na pilha
  • Topo da pilha

• Inserção de chaves

  • Push chave

• Remoção de chaves

  • Pop chave

Fila com alocações estática e dinâmica

• Inicialização, destruição e metadados

  • Inicializa fila
  • Destrói fila
  • Inicializa nodo de fila
  • Destrói nodo de fila
  • Número de elementos na fila
  • Número de nodos disponíveis
  • Fila vazia?
  • Fila cheia?

• Recuperação de informação

  • Mostrar a fila (simples e debug)
  • Obtém cabeça da fila
  • Obtém cauda da fila

• Inserção de chaves

  • Enfileira chave
  • Enfileira com prioridade

• Remoção de chaves

  • Desenfileira chave

Heap

• Inicialização, destruição e metadados

  • Inicializa heap
  • Destrói heap
  • Constrói heap
  • Número de elementos na heap
  • Inverte heap
  • Heap vazia?
  • Heap cheia?
  • Qual o tipo da heap?

• Recuperação de informação

  • Encontrar maior/menor elemento
  • Extrair maior/menor elemento, mantendo a heap

• Inserção de chaves

  • Insere chave, mantendo a heap
  • Trocar raíz por nova chave, mantendo a heap

• Remoção de chaves

  • Remove chave, mantendo a heap

Grafo (representado como matriz de adjacência)

• Inicialização, destruição e metadados

  • Inicializa grafo
  • Destrói grafo
  • Mostra grafo
  • Gera arquivo graphviz do grafo
  • Existe aresta entre dois vertices?
  • Obter peso da aresta
  • Obter grau de vértice
  • Obter lista de adjacencias (e detruir a lista)

• Inserção

  • Insere vértice
  • Insere aresta

• Remoção

  • Remove vertice
  • Remove aresta

• Percursos

  • Percurso em largura (e destruir percurso)
  • Percurso em profundidade (e destruir percurso)

• Ordenação topológica

  • A partir do percurso em profundidade
  • Algoritmo de Kahn

• Árvore geradora mínima

  • Prim
  • Kruskal

• Melhor caminho

  • Dijkstra

• Diversos

  • Colorir grafo (Welsh-Powell)
  • Complexidade ciclomática

Hash (tratamento de colisao por encadeamento)

• Inicialização, destruição e metadados

  • Inicializar tabela
  • Destrói tabela
  • Obter fator de carga

• Recuperação de informação

  • Consultar chave

• Inserção de chaves

  • Inserir chave

• Remoção de chaves

  • Remover chave

Filtro de Bloom

• Inicialização, destruição e metadados

  • Inicializar tabela
  • Destrói tabela
  • Obter fator de carga

• Recuperação de informação

  • Consultar chave

• Inserção de chaves

  • Inserir chave

• Remoção de chaves

  • Remover chave

Ordenação

• Memória interna

  • Bubble sort
  • Select sort
  • Insert sort
  • Quick sort
  • Heap short
  • Shell short
  • Radix sort
  • Bucket sort

• Memória externa

  • Merge sort

Arvores-B

• Inicialização, destruição e metadados
• Recuperação de informação
• Inserção de chaves
• Remoção de chaves

Arvores AVL

• Inicialização, destruição e metadados

  • Inicializa árvore
  • Destrói árvore
  • Inicializa nodo de árvore
  • Destrói nodo de árvore
  • Altura da árvore
  • Numero de nodos
  • Rotação R
  • Rotação L

• Recuperação de informação

  • Busca por chave

• Inserção de chaves

  • Inserção de chave

• Remoção de chaves

  • Remoção de chave

Arvores binarias (de busca)

• Inicialização, destruição e metadados

  • Inicializa árvore
  • Destrói árvore
  • Inicializa nodo de árvore
  • Destrói nodo de árvore
  • Altura da árvore
  • Numero de nodos
  • Nivel de nodo com valor
  • Nivel de determinado nodo

• Recuperação de informação

  • Imprimir árvore
  • Busca por chave

• Inserção de chaves

  • Inserção de chave

• Remoção de chaves

  • Remoção de chave

• Percursos

  • Percurso em pre-ordem
  • Percurso em in-ordem
  • Percurso em pos-ordem
  • Percurso em largura
  • Destrói percurso

Aplicacoes

• Codigo de Huffman