новости  материалы  справочник  форум  гостевая  ссылки Поиск с Яндексом  
Новости
Материалы
  Логические подходы
  Нейронные сети
  Генетические алгоритмы
  Разное
  Публикации
  Алгоритмы
  Применение
Справочник
Форум
Гостевая книга
Ссылки
О сайте
 

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


4.1. Коды для сортировки вставками

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;
    }
}


4.2. Коды для сортировки Шелла

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;
    }
}


4.3. Коды для быстрого поиска (функции Quicksort)

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;
        }
    }
}


4.4. Коды для стандартной реализации быстрого поиска

#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;
            }
        }
    }
}


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

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;
}


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 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);
}


4.7. Коды для красно-черных деревьев

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);
}


4.8. Коды для разделенных списков

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;
}


Предыдущая Оглавление Следующая