|
4. Тексты программ |
typedef int T;
typedef int tblIndex;
#define compGT(a,b) (a > b)
void insertSort(T *a, tblIndex lb, tblIndex ub) {
T t;
tblIndex i, j;
for (i = lb + 1; i <= ub; i++) {
t = a[i];
for (j = i-1; j >= lb && compGT(a[j], t); j--)
a[j+1] = a[j];
a[j+1] = t;
}
}
|
typedef int T;
typedef int tblIndex;
#define compGT(a,b) (a > b)
void shellSort(T *a, tblIndex lb, tblIndex ub) {
tblIndex n, h, i, j;
T t;
n = ub - lb + 1;
h = 1;
if (n < 14)
h = 1;
else if (sizeof(tblIndex) == 2 && n > 29524)
h = 3280;
else {
while (h < n) h = 3*h + 1;
h /= 3;
h /= 3;
}
while (h > 0) {
for (i = lb + h; i <= ub; i++) {
t = a[i];
for (j = i-h; j >= lb && compGT(a[j], t); j -= h)
a[j+h] = a[j];
a[j+h] = t;
}
h /= 3;
}
}
|
typedef int T;
typedef int tblIndex;
#define CompGT(a,b) (a > b)
tblIndex partition(T *a, tblIndex lb, tblIndex ub) {
T t, pivot;
tblIndex i, j, p;
p = lb + ((ub - lb)>>1);
pivot = a[p];
a[p] = a[lb];
i = lb+1;
j = ub;
while (1) {
while (i < j && compGT(pivot, a[i])) i++;
while (j >= i && compGT(a[j], pivot)) j--;
if (i >= j) break;
t = a[i];
a[i] = a[j];
a[j] = t;
j--; i++;
}
a[lb] = a[j];
a[j] = pivot;
return j;
}
void quickSort(T *a, tblIndex lb, tblIndex ub) {
tblIndex m;
while (lb < ub) {
if (ub - lb <= 12) {
insertSort(a, lb, ub);
return;
}
m = partition (a, lb, ub);
if (m - lb <= ub - m) {
quickSort(a, lb, m - 1);
lb = m + 1;
} else {
quickSort(a, m + 1, ub);
ub = m - 1;
}
}
}
|
#include <limits.h>
#define MAXSTACK (sizeof(size_t) * CHAR_BIT)
static void exchange(void *a, void *b, size_t size) {
size_t i;
for (i = sizeof(int); i <= size; i += sizeof(int)) {
int t = *((int *)a);
*(((int *)a)++) = *((int *)b);
*(((int *)b)++) = t;
}
for (i = i - sizeof(int) + 1; i <= size; i++) {
char t = *((char *)a);
*(((char *)a)++) = *((char *)b);
*(((char *)b)++) = t;
}
}
void qsort(void *base, size_t nmemb, size_t size,
int (*compar)(const void *, const void *)) {
void *lbStack[MAXSTACK], *ubStack[MAXSTACK];
int sp;
unsigned int offset;
lbStack[0] = (char *)base;
ubStack[0] = (char *)base + (nmemb-1)*size;
for (sp = 0; sp >= 0; sp--) {
char *lb, *ub, *m;
char *P, *i, *j;
lb = lbStack[sp];
ub = ubStack[sp];
while (lb < ub) {
offset = (ub - lb) >> 1;
P = lb + offset - offset % size;
exchange (lb, P, size);
i = lb + size;
j = ub;
while (1) {
while (i < j && compar(lb, i) > 0) i += size;
while (j >= i && compar(j, lb) > 0) j -= size;
if (i >= j) break;
exchange (i, j, size);
j -= size;
i += size;
}
exchange (lb, j, size);
m = j;
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;
}
}
}
}
|
typedef int T;
#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) {
return (data % hashTableSize);
}
Node *insertNode(T data) {
Node *p, *p0;
hashTableIndex bucket;
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;
p0 = 0;
bucket = hash(data);
p = hashTable[bucket];
while (p && !compEQ(p->data, data)) {
p0 = p;
p = p->next;
}
if (!p) return;
if (p0)
p0->next = p->next;
else
hashTable[bucket] = p->next;
free (p);
}
Node *findNode (T data) {
Node *p;
p = hashTable[hash(data)];
while (p && !compEQ(p->data, data))
p = p->next;
return p;
}
|
typedef int T;
#define compLT(a,b) (a < b)
#define compEQ(a,b) (a == b)
typedef struct Node_ {
struct Node_ *left;
struct Node_ *right;
struct Node_ *parent;
T data;
} Node;
Node *root = NULL;
Node *insertNode(T data) {
Node *x, *current, *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;
}
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;
if(parent)
if(compLT(x->data, parent->data))
parent->left = x;
else
parent->right = x;
else
root = x;
return(x);
}
void deleteNode(Node *z) {
Node *x, *y;
if (!z || z == NULL) return;
if (z->left == NULL || z->right == NULL)
y = z;
else {
y = z->right;
while (y->left != NULL) y = y->left;
}
if (y->left != NULL)
x = y->left;
else
x = y->right;
if (x) x->parent = y->parent;
if (y->parent)
if (y == y->parent->left)
y->parent->left = x;
else
y->parent->right = x;
else
root = x;
if (y != z) {
y->left = z->left;
if (y->left) y->left->parent = y;
y->right = z->right;
if (y->right) y->right->parent = y;
y->parent = z->parent;
if (z->parent)
if (z == z->parent->left)
z->parent->left = y;
else
z->parent->right = y;
else
root = y;
free (z);
} else {
free (y);
}
}
Node *findNode(T data) {
Node *current = root;
while(current != NULL)
if(compEQ(data, current->data))
return (current);
else
current = compLT(data, current->data) ?
current->left : current->right;
return(0);
}
|
typedef int T;
#define compLT(a,b) (a < b)
#define compEQ(a,b) (a == b)
typedef enum { BLACK, RED } nodeColor;
typedef struct Node_ {
struct Node_ *left;
struct Node_ *right;
struct Node_ *parent;
nodeColor color;
T data;
} Node;
#define NIL &sentinel
Node sentinel = { NIL, NIL, 0, BLACK, 0};
Node *root = NIL;
void rotateLeft(Node *x) {
Node *y = x->right;
x->right = y->left;
if (y->left != NIL) y->left->parent = x;
if (y != NIL) y->parent = x->parent;
if (x->parent) {
if (x == x->parent->left)
x->parent->left = y;
else
x->parent->right = y;
} else {
root = y;
}
y->left = x;
if (x != NIL) x->parent = y;
}
void rotateRight(Node *x) {
Node *y = x->left;
x->left = y->right;
if (y->right != NIL) y->right->parent = x;
if (y != NIL) y->parent = x->parent;
if (x->parent) {
if (x == x->parent->right)
x->parent->right = y;
else
x->parent->left = y;
} else {
root = y;
}
y->right = x;
if (x != NIL) x->parent = y;
}
void insertFixup(Node *x) {
while (x != root && x->parent->color == RED) {
if (x->parent == x->parent->parent->left) {
Node *y = x->parent->parent->right;
if (y->color == RED) {
x->parent->color = BLACK;
y->color = BLACK;
x->parent->parent->color = RED;
x = x->parent->parent;
} else {
if (x == x->parent->right) {
x = x->parent;
rotateLeft(x);
}
x->parent->color = BLACK;
x->parent->parent->color = RED;
rotateRight(x->parent->parent);
}
} else {
Node *y = x->parent->parent->left;
if (y->color == RED) {
x->parent->color = BLACK;
y->color = BLACK;
x->parent->parent->color = RED;
x = x->parent->parent;
} else {
if (x == x->parent->left) {
x = x->parent;
rotateRight(x);
}
x->parent->color = BLACK;
x->parent->parent->color = RED;
rotateLeft(x->parent->parent);
}
}
}
root->color = BLACK;
}
Node *insertNode(T data) {
Node *current, *parent, *x;
current = root;
parent = 0;
while (current != NIL) {
if (compEQ(data, current->data)) return (current);
parent = current;
current = compLT(data, current->data) ?
current->left : current->right;
}
if ((x = malloc (sizeof(*x))) == 0) {
printf ("insufficient memory (insertNode)\n");
exit(1);
}
x->data = data;
x->parent = parent;
x->left = NIL;
x->right = NIL;
x->color = RED;
if(parent) {
if(compLT(data, parent->data))
parent->left = x;
else
parent->right = x;
} else {
root = x;
}
insertFixup(x);
return(x);
}
void deleteFixup(Node *x) {
while (x != root && x->color == BLACK) {
if (x == x->parent->left) {
Node *w = x->parent->right;
if (w->color == RED) {
w->color = BLACK;
x->parent->color = RED;
rotateLeft (x->parent);
w = x->parent->right;
}
if (w->left->color == BLACK && w->right->color == BLACK) {
w->color = RED;
x = x->parent;
} else {
if (w->right->color == BLACK) {
w->left->color = BLACK;
w->color = RED;
rotateRight (w);
w = x->parent->right;
}
w->color = x->parent->color;
x->parent->color = BLACK;
w->right->color = BLACK;
rotateLeft (x->parent);
x = root;
}
} else {
Node *w = x->parent->left;
if (w->color == RED) {
w->color = BLACK;
x->parent->color = RED;
rotateRight (x->parent);
w = x->parent->left;
}
if (w->right->color == BLACK && w->left->color == BLACK) {
w->color = RED;
x = x->parent;
} else {
if (w->left->color == BLACK) {
w->right->color = BLACK;
w->color = RED;
rotateLeft (w);
w = x->parent->left;
}
w->color = x->parent->color;
x->parent->color = BLACK;
w->left->color = BLACK;
rotateRight (x->parent);
x = root;
}
}
}
x->color = BLACK;
}
void deleteNode(Node *z) {
Node *x, *y;
if (!z || z == NIL) return;
if (z->left == NIL || z->right == NIL) {
y = z;
} else {
y = z->right;
while (y->left != NIL) y = y->left;
}
if (y->left != NIL)
x = y->left;
else
x = y->right;
x->parent = y->parent;
if (y->parent)
if (y == y->parent->left)
y->parent->left = x;
else
y->parent->right = x;
else
root = x;
if (y != z) z->data = y->data;
if (y->color == BLACK)
deleteFixup (x);
free (y);
}
Node *findNode(T data) {
Node *current = root;
while(current != NIL)
if(compEQ(data, current->data))
return (current);
else
current = compLT (data, current->data) ?
current->left : current->right;
return(0);
}
|
typedef int T;
#define compLT(a,b) (a < b)
#define compEQ(a,b) (a == b)
#define MAXLEVEL 15
typedef struct Node_ {
T data;
struct Node_ *forward[1];
} Node;
typedef struct {
Node *hdr;
int listLevel;
} SkipList;
SkipList list;
#define NIL list.hdr
Node *insertNode(T data) {
int i, newLevel;
Node *update[MAXLEVEL+1];
Node *x;
x = list.hdr;
for (i = list.listLevel; i >= 0; i--) {
while (x->forward[i] != NIL
&& compLT(x->forward[i]->data, data))
x = x->forward[i];
update[i] = x;
}
x = x->forward[0];
if (x != NIL && compEQ(x->data, data)) return(x);
newLevel = 0;
while (rand() < RAND_MAX/2) newLevel++;
if (newLevel > MAXLEVEL) newLevel = MAXLEVEL;
if (newLevel > list.listLevel) {
for (i = list.listLevel + 1; i <= newLevel; i++)
update[i] = NIL;
list.listLevel = newLevel;
}
if ((x = malloc(sizeof(Node) +
newLevel*sizeof(Node *))) == 0) {
printf ("insufficient memory (insertNode)\n");
exit(1);
}
x->data = data;
for (i = 0; i <= newLevel; i++) {
x->forward[i] = update[i]->forward[i];
update[i]->forward[i] = x;
}
return(x);
}
void deleteNode(T data) {
int i;
Node *update[MAXLEVEL+1], *x;
x = list.hdr;
for (i = list.listLevel; i >= 0; i--) {
while (x->forward[i] != NIL
&& compLT(x->forward[i]->data, data))
x = x->forward[i];
update[i] = x;
}
x = x->forward[0];
if (x == NIL || !compEQ(x->data, data)) return;
for (i = 0; i <= list.listLevel; i++) {
if (update[i]->forward[i] != x) break;
update[i]->forward[i] = x->forward[i];
}
free (x);
while ((list.listLevel > 0)
&& (list.hdr->forward[list.listLevel] == NIL))
list.listLevel--;
}
Node *findNode(T data) {
int i;
Node *x = list.hdr;
for (i = list.listLevel; i >= 0; i--) {
while (x->forward[i] != NIL
&& compLT(x->forward[i]->data, data))
x = x->forward[i];
}
x = x->forward[0];
if (x != NIL && compEQ(x->data, data)) return (x);
return(0);
}
void initList() {
int i;
if ((list.hdr = malloc(sizeof(Node) + MAXLEVEL*sizeof(Node *))) == 0) {
printf ("insufficient memory (initList)\n");
exit(1);
}
for (i = 0; i <= MAXLEVEL; i++)
list.hdr->forward[i] = NIL;
list.listLevel = 0;
}
|
|
|
|
|
|