(→Outras Funções do ADT) |
|||
Line 27: | Line 27: | ||
== Outras Funções do ADT == | == Outras Funções do ADT == | ||
+ | |||
+ | * <code>STselect</code> - [[Selecção da k-ésima Menor Chave (BST)|selecção da k-ésima menor chave]] |
Dependências 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; }
STselect
- selecção da k-ésima menor chave