データ構造とアルゴリズム

http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-087-practical-programming-in-c-january-iap-2010/lecture-notes/ でC言語を学習中。

例題をいくつかやってみた。

バイナリツリー

#include <stdlib.h>
#include <stdio.h>

struct tnode
{
    int data;
    struct tnode* left;
    struct tnode* right;
};

struct tnode* talloc(int data);
struct tnode* addnode(struct tnode* root, int data);
struct tnode* findnode(struct tnode* root, int data);
void          printnode(struct tnode* node);


int main(int argc, char* argv[])
{
    struct tnode* t = NULL;
    t = addnode(t,3);
    t = addnode(t,1);
    t = addnode(t,2);
    t = addnode(t,4);

    printnode( findnode(t,1) );
    printnode( findnode(t,2) );
    printnode( findnode(t,5) ); // not found
    
    exit(0);
}

/*
 * Implementation
 */
struct tnode* talloc(int data)
{
    struct tnode* p = (struct tnode*)malloc(sizeof(struct tnode));
    if ( p!=NULL )
    {
        p->data = data;
        p->left = NULL;
        p->right = NULL;
    }
    return p;
}

struct tnode* addnode(struct tnode* root, int data)
{
    if (root == NULL)
        root = talloc(data);
    else if ( data < root->data )
        root->left = addnode(root->left, data);
    else
        root->right = addnode(root->right, data);

    return root;
}

struct tnode* findnode(struct tnode* root, int data)
{
    struct tnode* found;

    if ( root == NULL )
        found = NULL;
    else if ( data == root->data )
        found = root;
    else if ( data < root->data )
        found = findnode(root->left, data);
    else
        found = findnode(root->right, data);

    return found;
}

void printnode(struct tnode* node)
{
    if ( node != NULL )
        printf("%d\n", node->data);
}

スタック

#include <stdlib.h>
#include <stdio.h>

struct stack {
    int element;
    struct stack* next;
};

void push(struct stack** bp, int element)
{
    struct stack *new_node = (struct stack*)malloc(sizeof(struct stack));

    new_node->element = element;
    new_node->next    = *bp; 
    *bp = new_node;
}

int pop(struct stack** bp)
{
    struct stack *node;
    int element;

    if ( *bp ) {
        node = *bp;
        element = node->element;
        *bp = node->next;
        free(node);
        return element;
    }
    else {
        return 0;
    }
}

int main(int argc, char* argv[])
{
    struct stack* buffer = NULL;

    push(&buffer, 2);
    push(&buffer, 3);
    push(&buffer, 4);
    printf("%d\n", pop(&buffer));
    printf("%d\n", pop(&buffer));
    printf("%d\n", pop(&buffer));

    exit(0);
}

キュー

#include <stdlib.h>
#include <stdio.h>

struct s_listnode {
    float element;
    struct s_listnode* pnext;
};

struct s_listnode *queue_buffer = NULL;
struct s_listnode *prear = NULL;

void enqueue(float element)
{
    struct s_listnode *newnode = (struct s_listnode*)malloc(sizeof(struct s_listnode)); 
    newnode->element = element;
    newnode->pnext   = NULL;
    
    if ( prear ) {
        prear->pnext = newnode; 
    }
    else {
        queue_buffer = newnode;
    }
    prear = newnode;
}

float dequeue(void)
{
    struct s_listnode *pfront;
    float element;

    if ( queue_buffer ) {
        pfront = queue_buffer;
        element = pfront->element;
        queue_buffer = pfront->pnext;

        if ( pfront == prear ) {
            prear = NULL;
        }
        free(pfront);
        return element;
    }
    else {
        return 0;
    }
}

int main(int argc, char* argv[])
{
    int i;
    for ( i = 0; i < 10; i++ ) {
        enqueue(0.1 * i);
    }

    for ( i = 0; i < 10; i++ ) {
        printf("%f\n", dequeue());
    }

    exit(0);
}

ハッシュテーブル（チェイン法）

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

#define MAX_BUCKETS 1000
#define MULTIPLIER 31

struct wordrec
{
    char* word;
    struct wordrec* pnext;
};

struct wordrec* table[MAX_BUCKETS];

unsigned long hashstring(const char* str)
{
    unsigned long hash = 0;
    while (*str) {
        hash = hash * MULTIPLIER + *str;
        str++;
    }

    return hash % MAX_BUCKETS;
}

struct wordrec* lookup(const char* str, int create)
{
    struct wordrec* curr = NULL;
    unsigned long hash = hashstring(str);
    char strnew[1024];

    struct wordrec* wp = table[hash];

    for ( curr = wp; curr != NULL; curr = curr->pnext ) {
        if ( strcmp(curr->word, str) == 0 ) {
            return curr;
        }
    }

    if ( create ) {
        strcpy(strnew, str);

        curr = (struct wordrec*)malloc(sizeof(struct wordrec*));
        curr->word  = strnew;
        curr->pnext = NULL;

        if (wp == NULL) {
            table[hash] = curr;
        }

        return curr;
    }
    
    return NULL;
}

int main(int argc, char* argv[])
{
    struct wordrec* found = (struct wordrec*)malloc(sizeof(struct wordrec*));
    lookup("foo", 1);
    found = lookup("foo", 0);
    if ( found !=NULL )
        printf("%s\n", found->word);

    lookup("bar", 1);
    found = lookup("bar", 0);
    if ( found !=NULL )
        printf("%s\n", found->word);

    exit(EXIT_SUCCESS);
}