4. Тексты программ

typedef int T; /* type of item to be sorted */ typedef int tblIndex; /* type of subscript */ #define compGT(a,b) (a > b) void insertSort(T *a, tblIndex lb, tblIndex ub) { T t; tblIndex i, j; /************************** * sort array a[lb..ub] * **************************/ for (i = lb + 1; i <= ub; i++) { t = a[i]; /* Shift elements down until */ /* insertion point found. */ for (j = i-1; j >= lb && compGT(a[j], t); j--) a[j+1] = a[j]; /* insert */ a[j+1] = t; } }

typedef int T; /* type of item to be sorted */ typedef int tblIndex; /* type of subscript */ #define compGT(a,b) (a > b) void shellSort(T *a, tblIndex lb, tblIndex ub) { tblIndex n, h, i, j; T t; /************************** * sort array a[lb..ub] * **************************/ /* compute largest increment */ 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) { /* sort-by-insertion in increments of h */ 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; } /* compute next increment */ h /= 3; } }

typedef int T; /* type of item to be sorted */ typedef int tblIndex; /* type of subscript */ #define CompGT(a,b) (a > b) tblIndex partition(T *a, tblIndex lb, tblIndex ub) { T t, pivot; tblIndex i, j, p; /******************************* * partition array a[lb..ub] * *******************************/ /* select pivot and exchange with 1st element */ p = lb + ((ub - lb)>>1); pivot = a[p]; a[p] = a[lb]; /* sort lb+1..ub based on pivot */ 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++; } /* pivot belongs in a[j] */ a[lb] = a[j]; a[j] = pivot; return j; } void quickSort(T *a, tblIndex lb, tblIndex ub) { tblIndex m; /************************** * sort array a[lb..ub] * **************************/ while (lb < ub) { /* quickly sort short lists */ if (ub - lb <= 12) { insertSort(a, lb, ub); return; } /* partition into two segments */ m = partition (a, lb, ub); /* sort the smallest partition */ /* to minimize stack requirements */ 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; /****************** * exchange a,b * ******************/ 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) { /* select pivot and exchange with 1st element */ offset = (ub - lb) >> 1; P = lb + offset - offset % size; exchange (lb, P, size); /* partition into two segments */ 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; } /* 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; } } } }

typedef int T; /* type of item to be sorted */ #define compEQ(a,b) (a == b) typedef struct Node_ { struct Node_ *next; /* next node */ T data; /* data stored in node */ } 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; /************************************************ * 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; else /* 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; }

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 x's 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; else parent->right = x; else root = x; return(x); } void deleteNode(Node *z) { Node *x, *y; /***************************** * delete node z from tree * *****************************/ /* y will be removed from the parent chain */ if (!z || z == NULL) return; /* find tree successor */ if (z->left == NULL || z->right == NULL) y = z; else { y = z->right; while (y->left != NULL) y = y->left; } /* x is y's only child */ if (y->left != NULL) x = y->left; else x = y->right; /* remove y from the parent chain */ 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; /* y is the node we're removing */ /* z is the data we're removing */ /* if z and y are not the same, replace z with y. */ 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) { /******************************* * find node containing 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; /* type of item to be sorted */ #define compLT(a,b) (a < b) #define compEQ(a,b) (a == b) /* Red-Black tree description */ typedef enum { BLACK, RED } nodeColor; typedef struct Node_ { struct Node_ *left; /* left child */ struct Node_ *right; /* right child */ struct Node_ *parent; /* parent */ nodeColor color; /* node color (BLACK, RED) */ T data; /* data stoRED in node */ } Node; #define NIL &sentinel /* all leafs are sentinels */ Node sentinel = { NIL, NIL, 0, BLACK, 0}; Node *root = NIL; /* root of Red-Black tree */ void rotateLeft(Node *x) { /************************** * rotate node x to left * **************************/ Node *y = x->right; /* establish x->right link */ x->right = y->left; if (y->left != NIL) y->left->parent = x; /* establish y->parent link */ 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; } /* link x and y */ y->left = x; if (x != NIL) x->parent = y; } void rotateRight(Node *x) { /**************************** * rotate node x to right * ****************************/ Node *y = x->left; /* establish x->left link */ x->left = y->right; if (y->right != NIL) y->right->parent = x; /* establish y->parent link */ 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; } /* link x and y */ y->right = x; if (x != NIL) x->parent = y; } void insertFixup(Node *x) { /************************************* * maintain Red-Black tree balance * * after inserting node x * *************************************/ /* check Red-Black properties */ while (x != root && x->parent->color == RED) { /* we have a violation */ if (x->parent == x->parent->parent->left) { Node *y = x->parent->parent->right; if (y->color == RED) { /* uncle is RED */ x->parent->color = BLACK; y->color = BLACK; x->parent->parent->color = RED; x = x->parent->parent; } else { /* uncle is BLACK */ if (x == x->parent->right) { /* make x a left child */ x = x->parent; rotateLeft(x); } /* recolor and rotate */ x->parent->color = BLACK; x->parent->parent->color = RED; rotateRight(x->parent->parent); } } else { /* mirror image of above code */ Node *y = x->parent->parent->left; if (y->color == RED) { /* uncle is RED */ x->parent->color = BLACK; y->color = BLACK; x->parent->parent->color = RED; x = x->parent->parent; } else { /* uncle is BLACK */ 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; /*********************************************** * allocate node for data and insert in tree * ***********************************************/ /* find where node belongs */ 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; } /* setup new node */ 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; /* insert node in tree */ 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) { /************************************* * maintain Red-Black tree balance * * after deleting 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; /***************************** * delete node z from tree * *****************************/ if (!z || z == NIL) return; if (z->left == NIL || z->right == NIL) { /* y has a NIL node as a child */ y = z; } else { /* find tree successor with a NIL node as a child */ y = z->right; while (y->left != NIL) y = y->left; } /* x is y's only child */ if (y->left != NIL) x = y->left; else x = y->right; /* remove y from the parent chain */ 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) { /******************************* * find node containing 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; /* type of item to be sorted */ #define compLT(a,b) (a < b) #define compEQ(a,b) (a == b) /* * levels range from (0 .. MAXLEVEL) */ #define MAXLEVEL 15 typedef struct Node_ { T data; /* user's data */ struct Node_ *forward[1]; /* skip list forward pointer */ } Node; typedef struct { Node *hdr; /* list Header */ int listLevel; /* current level of list */ } SkipList; SkipList list; /* skip list information */ #define NIL list.hdr Node *insertNode(T data) { int i, newLevel; Node *update[MAXLEVEL+1]; Node *x; /*********************************************** * allocate node for data and insert in list * ***********************************************/ /* find where data belongs */ 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); /* determine level */ 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; } /* make new node */ if ((x = malloc(sizeof(Node) + newLevel*sizeof(Node *))) == 0) { printf ("insufficient memory (insertNode)\n"); exit(1); } x->data = data; /* update forward links */ 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; /******************************************* * delete node containing data from list * *******************************************/ /* find where data belongs */ 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; /* adjust forward pointers */ for (i = 0; i <= list.listLevel; i++) { if (update[i]->forward[i] != x) break; update[i]->forward[i] = x->forward[i]; } free (x); /* adjust header level */ while ((list.listLevel > 0) && (list.hdr->forward[list.listLevel] == NIL)) list.listLevel--; } Node *findNode(T data) { int i; Node *x = list.hdr; /******************************* * find node containing data * *******************************/ 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; /************************** * initialize skip list * **************************/ 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; }

Предыдущая

Оглавление

Следующая