(→Outras Funções do ADT) |
m (Implementação do ADT Tabela de SÃmbolos (BST) moved to Implementação do ADT Tabela de Símbolos (BST)) |
||
(One intermediate revision by the same user not shown) | |||
Line 1: | Line 1: | ||
− | + | Dependncias da implementação do ADT tabela de símbolos baseado em BSTs. A árvore está ancorada em <code>head</code> e as folhas são nãs vazios (representados por <code>z</code>): assim, os algoritmos apenas manipulam nós internos da árvore. | |
#include <stdlib.h> | #include <stdlib.h> | ||
Line 28: | Line 28: | ||
== Outras Funções do ADT == | == Outras Funções do ADT == | ||
− | * <code>STinsert</code> - [[Inserção numa BST|inserção]] de um elemento na tabela de | + | * <code>STinsert</code> - [[Inserção numa BST|inserção]] de um elemento na tabela de símbolos |
* <code>STsearch</code> - [[Procura numa BST|pesquisa]] um elemento dada a sua chave | * <code>STsearch</code> - [[Procura numa BST|pesquisa]] um elemento dada a sua chave | ||
* <code>STdelete</code> - | * <code>STdelete</code> - | ||
* <code>STselect</code> - [[Selecção da k-ésima Menor Chave (BST)|selecção]] da k-ésima menor chave | * <code>STselect</code> - [[Selecção da k-ésima Menor Chave (BST)|selecção]] da k-ésima menor chave | ||
* <code>STsort</code> - | * <code>STsort</code> - |
Dependncias da implementação do ADT tabela de símbolos baseado em BSTs. A árvore está ancorada em head
e as folhas são nãs vazios (representados por z
): assim, os algoritmos apenas manipulam nós internos da árvore.
#include <stdlib.h> #include "Item.h" typedef struct STnode* link; struct STnode { Item item; link l, r; int N }; static link head, z;
Esta função não faz parte da interface do ADT. A ideia subjacente é isolar procedimentos repetitivos da criação de novas entradas da BST.
link NEW(Item item, link l, link r, int N) { link x = (link)malloc(sizeof *x); x->item = item; x->l = l; x->r = r; x->N = N; return x; }
void STinit() { head = z = NEW(NULLitem, 0, 0, 0); } int STcount() { return head->N; }