03-bheap.c, original

#include <stdio.h>
#include <stdlib.h>
 
//---------------------------------------------
typedef float DType;
int cmp(DType d1, DType d2);
char *toString(char *buf, DType d);
//-------------------------------------------------------
int cmp(float d1, float d2) {
    if (d1 == d2) return 0;
    return (d1 < d2) ? -1 : 1;
}
char *toString(char *buf, float d) {
    sprintf(buf, "%6.2f", d);
    return buf;
}
//-------------------------------------------------------
struct SBHeap {
    DType *data;
    int length;
    int size;
};
typedef struct SBHeap *BHeap;
//---------------------------------------------
BHeap newBHeap(int length) {
    BHeap h = (BHeap) malloc(sizeof(struct SBHeap));
    h->data = (DType *) malloc(length * sizeof(DType));
    h->length = length;
    h->size = 0;
    return h;
}
void freeBHeap(BHeap h) {
    free(h->data);
    free(h);
}
//---------------------------------------------
int sizeOfBHeap(BHeap h) {
    return h->size;
}
int isEmptyBHeap(BHeap h) {
    return h->size == 0;
}
int isFullBHeap(BHeap h) {
    return h->size == h->length;
}
//---------------------------------------------
void printBHeap(BHeap h) {
    printf("heap:[ ");
    int i;
    char buf[100];
    for (i=0; i<h->size; i++) {
        printf("%s ", toString(buf, h->data[i]));
    }
    printf("]\n");
}
//---------------------------------------------
void addBHeap(BHeap h, DType x) {
    if (isFullBHeap(h)) {
        printf("add : heap is full\n");
        exit(1);
    } else {
        int k = h->size;
        while( k > 0 ) {
            int p = (k-1)/2;
            if (cmp(h->data[p],x) <= 0) break;  // min heap
            h->data[k] = h->data[p];
            k = p;
        }
        h->data[k] = x;
        h->size++;
    }
}
// begin with an underscore -> private function
void _heapify(BHeap h, int k) {
    int c;
    while ( (c = 2*k+1) < h->size) {
        if (c+1 < h->size && cmp(h->data[c+1], h->data[geshifilter-c]) &lt; 0) c++;&#10;        if (cmp(h-&gt;data[c],h-&gt;data[k]) &gt;= 0) break;&#10;        DType t = h-&gt;data[k];&#10;        h-&gt;data[k] = h-&gt;data[c];&#10;        h-&gt;data[c] = t;&#10;        k = c;&#10;    }&#10;}&#10;DType removeMinBHeap(BHeap h) {  // min heap&#10;    if (isEmptyBHeap(h)) {&#10;        printf(&quot;heap is empty !\n&quot;);&#10;        exit(1);&#10;    } else {&#10;        DType min = h-&gt;data[0];&#10;        h-&gt;data[0] = h-&gt;data[h-&gt;size-1];&#10;        _heapify(h, 0);&#10;        h-&gt;size--;&#10;        return min;&#10;    }&#10;}&#10;//---------------------------------------------&#10;BHeap buildBHeap1(DType d[], int n) {&#10;    BHeap h = newBHeap(n);&#10;    int i;&#10;    for(i=0; i&lt;n; i++) {&#10;        h-&gt;data[i] = d[i];&#10;    }&#10;    h-&gt;length = n;&#10;    h-&gt;size = n;&#10;    for(i=n-1; i&gt;=0; i--) {&#10;        _heapify(h, i);&#10;    }&#10;    return h;&#10;}&#10;BHeap buildBHeap2(DType d[], int n) {&#10;    BHeap h = newBHeap(n);&#10;    int i;&#10;    for(i=0; i&lt;n; i++) {&#10;        addBHeap(h, d[i]);&#10;    }&#10;    return h;&#10;}&#10;//---------------------------------------------&#10;int main(int argc, char *argv[]) {&#10;    float d[] = {1,4,2,7,8,0,9};&#10;    int n = 7;&#10;    BHeap h = buildBHeap1(d, n);&#10;    int i;&#10;    printBHeap(h);&#10;    for (i=0; i&lt;n; i++) {&#10;        printf(&quot;removeMin : %6.2f : &quot;, removeMinBHeap(h));&#10;        printBHeap(h);&#10;    }&#10;    return 0;&#10;}&#10;

[/geshifilter-c]

02-queue.c, original

#include <stdio.h>
#include <stdlib.h>
 
//-------------------------------------------------------
typedef float DType;
int cmp(DType d1, DType d2);
char *toString(char *buf, DType d);
//-------------------------------------------------------
char *toString(char *buf, float d) {
    sprintf(buf, "%6.2f", d);
    return buf;
}
//-------------------------------------------------------
struct SQueue {
    DType *data;
    int length;
    int size;
    int front;
};
typedef struct SQueue *Queue;
//-------------------------------------
Queue newQueue(int length) {
    Queue q = (Queue) malloc(sizeof(struct SQueue));
    q->data = (DType *) malloc(length * sizeof(DType));
    q->length = length;
    q->size = 0;
    q->front = 0;
    return q;
}
void freeQueue(Queue q) {
    free(q->data);
    free(q);
}
//---------------------------------------------
int sizeOfQueue(Queue q) {
    return q->size;
}
int isEmptyQueue(Queue q) {
    return q->size == 0;
}
int isFullQueue(Queue q) {
    return q->size == q->length;
}
//---------------------------------------------
void printQueue(Queue q) {
    int i;
    printf("queue:[ ");
    int f = q->front;
    char buf[100];
    for (i=0; i<q->size; i++) {
        printf("%s ", toString(buf, q->data[f]));
        f = (f + 1) % q->length;
    }
    printf("]\n");
}
//---------------------------------------------
void enqueue(Queue q, DType x) {
    if (q->size == q->length) {
        int newlength = 2*q->length;
        DType *a = (DType *) malloc(newlength * sizeof(DType));
        int i;
        for (i=0; i<q->size; i++) {
            a[i] = q->data[q->front];
            q->front = (q->front + 1) % q->length;
        }
        free(q->data);
        q->data = a;
        q->length = newlength;
        q->front = 0;
    }
    int b = (q->front + q->size) % q->length;
    q->data[b] = x;
    q->size++;
}
DType dequeue(Queue q) {
    if (isEmptyQueue(q)) {
        printf("queue is empty !\n");
        exit(1);
    }
    DType x = q->data[q->front];
    q->front = (q->front + 1) % q->length;
    q->size--;
    return x;
}
//---------------------------------------------
int main(int argc, char *argv[]) {
    Queue q = newQueue(1);
    enqueue(q, 1);
    enqueue(q, 2);
    enqueue(q, 3);
    enqueue(q, 9);
    dequeue(q);
    enqueue(q, 11);
    enqueue(q, 12);
    dequeue(q);
    printQueue(q);
    return 0;
}