exchange (i, j, size); j -= size; i += size;

4.5 Коды для хеш-таблиц

typedef int T;/* type of item to be sorted */

#define compEQ(a,b) (a == b)

typedef struct Node {

struct Node *next;

T data; } Node;

typedef int hashTableIndex;

Node **hashTable; int hashTableSize;

hashTableIndex hash(T data) {

/***********************************

* hash function applied to data * ***********************************/

return (data % hashTableSize);

Node *insertNode(T data) { Node *p, *p0; hashTableIndex bucket;

/* next node */

/* data stored in node */

/* pivot belongs in A[j] */ exchange (lb, j, size); m = j;

/* keep processing smallest segment, and stack largest */

if (m - lb <= ub - m) {

if (m + size < ub) {

lbStack[sp] = m + size; ubStack[sp++] = ub;

ub = m - size; } else {

if (m - size > lb) { lbStack[sp] = lb; ubStack[sp++] = m - size;

lb = m + size;

/************************************************

*allocate node for data and insert in table * ************************************************/

/* insert node at beginning of list */ bucket = hash(data);

if ((p = malloc(sizeof(Node))) == 0) {

fprintf (stderr, "out of memory (insertNode)\n"); exit(1);

p0 = hashTable[bucket]; hashTable[bucket] = p; p->next = p0; p->data = data; return p;

void deleteNode(T data) { Node *p0, *p; hashTableIndex bucket;

/********************************************

*delete node containing data from table * ********************************************/

/* find node */

p0 = 0;

bucket = hash(data); p = hashTable[bucket];

while (p && !compEQ(p->data, data)) {

p0 = p;

p = p->next;

if (!p) return;

/* p designates node to delete, remove it from list */

if (p0)

/* not first node, p0 points to previous node */ p0->next = p->next;

/* first node on chain */ hashTable[bucket] = p->next;

free (p);

Node *findNode (T data) {

Node *p;

/*******************************

*find node containing data * *******************************/

p = hashTable[hash(data)];

while (p && !compEQ(p->data, data))

p = p->next; return p;

4.6 Коды для бинарных деревьев

typedef int T;/* type of item to be sorted */

#define compLT(a,b) (a < b) #define compEQ(a,b) (a == b)

typedef struct Node {

struct Node *left;/*left child */

struct Node *right;/*right child */

struct Node *parent;/*parent */

T data;/*data stored in node */

} Node;

Node *root = NULL;/* root of binary tree */

Node *insertNode(T data) {

Node *x, *current, *parent;

/***********************************************

* allocate node for data and insert in tree * ***********************************************/

/* find xs parent */ current = root; parent = 0; while (current) {

if (compEQ(data, current->data)) return (current);

parent = current;

current = compLT(data, current->data) ? current->left : current->right;

/* setup new node */

if ((x = malloc (sizeof(*x))) == 0) {

fprintf (stderr, "insufficient memory (insertNode)\n");

exit(1);

x->data = data; x->parent = parent;

x->left = NULL; x->right = NULL;

/* insert x in tree */ if(parent)

if(compLT(x->data, parent->data)) parent->left = x;

parent->right = x;

root = x;