Ｃ言語で連想配列を自作してみました。
※今回は、キーは文字列とします。

やりたいこと

map.h

#ifndef MAP_H_
#define MAP_H_

/* 連想配列構造体 */
typedef struct map* Map;

/* コンストラクタ */
Map newMap();

/* キーと値をセット（キーが既に存在していればupdate, 無ければinsertの役割） */
void setValue(Map map, const char* key, void* value);

/* 値を取得 */
void* getValue(Map map, const char* key);

/* 連想配列内の全てのキー、値に対して処理 */
void foreach(Map map, void (*func)(const char* key, const void* value));

/* 連想配列内のキーを削除 */
void* erase(Map map, const char* key);

/* 連想配列を初期化（プログラム終了時に忘れない!!） */
void clear(Map map, int flag);

#endif /* MAP_H_ */

二分探索木を用いる

今回はAVL木の考え方を用います。

連想配列構造体

map.c

#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include "map.h"

typedef struct node{
	char* key; //キー
	void* value; //値
	struct node* child[2]; //child[0]:左の子(キーが親より小さい)、child[1]:右の子(キーが親より大きい)
}Node;

struct map{
	Node* root; //根ノード
};

コンストラクタ

/*
 * コンストラクタ
 */
Map newMap(){
    //メモリ確保
    Map map=(Map)malloc(sizeof(struct map));
    if(!map){//メモリ確保失敗
        abort();
    }
    //根ノードをNULLにセット
    map->root=NULL;

    return map;
}

キーと値をセット

/*
 * キーと値をセットする
 */
void setValue(Map map, const char* key, void* value){
	//辿ったノードを格納しておくための配列
	Node* nodes[64];

	//辿ったノードの左右を格納しておくための配列(左がfalse、右がtrue)
	bool flag[64];

	//辿ったノードの深さ
	int depth=0;

	//0番目に根ノードを格納しておく
	nodes[depth]=map->root;

	//配列にNULLが格納されるまで子ノードを辿る
	while(nodes[depth]){
		int cmp=strcmp(key,nodes[depth]->key);
		if(cmp==0){//一致したキーが存在する場合
			/* update処理 */
			nodes[depth]->value=value;
			return;
		}

		//辞書順比較。新キーが早ければ0(左)、後ならば1(右)
		flag[depth]=(cmp>0);

		//配列に子ノードを格納する（流石にnodes[++depth]=nodes[depth]->child[flag]は乱暴すぎる）
		nodes[depth+1]=nodes[depth]->child[flag[depth]];
		depth++;
	}

	/* insert処理 */
	//新しいノードのメモリを確保
	Node* node=(Node*)malloc(sizeof(Node));
	if(!node){//メモリ確保失敗
		abort();
	}

	//乱暴な初期化をしてみる（keyもvalueもchild[i]（i=0,1）もNULL）
	memset(node,0,sizeof(Node));

	//キーのメモリ確保
	node->key=(char*)malloc(strlen(key)+1);
	if(!node->key){//メモリ確保失敗
		abort();
	}

	//キーをセット
	strcpy(node->key,key);

	//値をセット
	node->value=value;

	//最初に用意した配列に新ノードを格納（実は、後で使わない）
	nodes[depth]=node;
	if(depth){
		//一つ前のノードが親ノード。親ノードに子ノードを紐づける。左右フラグは先程のwhile文の内部で回している。
    	nodes[depth-1]->child[flag[depth-1]]=node;
	}else{
		//要素数が0だった場合、根ノードにセットする。
		map->root=node;
	}

	//一応、これで挿入もしくは更新できたのだが、挿入の場合、二分探索木の平衡性を保つことにする。
	//（その為に、`nodes`に根から辿っていったノードを格納しておいた）
	take_balance(map, depth, nodes, flag);
}

以下のtake_balance関数及びそれに関連する関数は、上記のソースコードの前に記述する。（Ｃ言語の記述の仕方に倣って、下の関数から読んだほうが処理が追いかけやすい）
詳細は「AVL木」等で検索していただきたい。

/*
 * 部分木としての高さ
 */
int height(Node* node){
	if(!node){//NULLなら0を返す
		return 0;
	}

	//再帰的に、左部分木と右部分木の高さを取得する。
	int left=height(node->child[0]);
	int right=height(node->child[1]);

	//左部分木と右部分木の高い方の高さ+1を返す
	return (left>right?left:right)+1;
}

/*
 * 平衡係数。
 * 今回は、左部分木の高さ－右部分木の高さで定義する。
 */
int balance(Node* node){
	return height(node->child[0])-height(node->child[1]);
}

/*
 * 部分木の「回転」
 * node: 付け替え対象となるノードの親ノード
 * flag: 左回転=0, 右回転=1
 */
void rotate(Node** node, int flag){
	Node* pivot=(*node)->child[1-flag];
	(*node)->child[1-flag]=pivot->child[flag];
	pivot->child[flag]=*node;
	*node=pivot;
}

/*
 * 連想配列を構成する二分木の平衡性を保つ処理
 * map: 連想配列
 * depth: 挿入ノードまたは削除ノードの深さ
 * nodes: 根ノードから挿入または削除ノードまで辿ったノード
 * （nodes[0]が根ノード、nodes[depth]が挿入されたノードまたは削除されたノード※削除された場合は既にNULLになっている）
 * flag: node[i+1](子)がnode[i](親)に対して左にあるか右にあるか
 * （flag[i]=0ならnode[i+1]はnode[i]の左の子、flag[i]=1ならnode[i+1]はnode[i]の右の子）
 */
void take_balance(Map map, int depth, Node* nodes[], bool flag[]){
    //対象ノードの親から根に向かって進む
	for(int i=depth-1;i>=0;i--){
        //平衡係数（左部分木の高さ－右部分木の高さ）
        int bal=balance(nodes[i]);
		if(bal>1){//左部分木の高さ－右部分木の高さ≧２の場合（平衡性が崩れているので修正）
			if(balance(nodes[i]->child[0])<0){//左の子について、右部分木の高さが左のそれより高い場合
                //左の子をつけかえる
				rotate(&(nodes[i]->child[0]),0);
			}
            //平衡係数を計算したノードの親に対する子ノードを繋ぎかえる
			if(i){
				rotate(&(nodes[i-1]->child[flag[i-1]]),1);
			}else{
				rotate(&(map->root),1);
			}
		}else if(bal<-1){//右部分木の高さ－左部分木の高さ≧２の場合（平衡性が崩れているので修正）
			if(balance(nodes[i]->child[1])>0){//右の子について、左部分木の高さが右のそれより高い場合
                //右の子をつけかえる
				rotate(&(nodes[i]->child[1]),1);
			}
            //平衡係数を計算したノードの親に対する子ノードを繋ぎかえる
			if(i){
				rotate(&(nodes[i-1]->child[flag[i-1]]),0);
			}else{
				rotate(&(map->root),0);
			}
		}
	}
}

値を取得

/*
 * 値を取得する
 * map : 連想配列
 * key : 探索キー
 */
void* getValue(Map map, const char* key){
	Node* node=map->root;
	while(node){
		int cmp=strcmp(key,node->key);
		if(cmp==0){//キーがヒットした場合、値を返す。
			return node->value;
		}
        //引数キーがノードキーより早ければ左、後ならば右の子を探索していく
		node=node->child[cmp>0];
	}

	//キーが無ければNULL
	return NULL;
}

上記の関数を用いてNULLが返却された場合、当該キーに設定された値がNULLなのか、キーが存在しなかったのかの区別できない。

連想配列内の全てのキー、値に対して処理を適用

/*
 * ノード内のキー・値に対して通りがけ順（左⇒親⇒右）で処理
 */
void _foreach(void (*func)(const char* key, const void* value), Node* node){
	if(node){//node==NULLの場合はスキップ
		//左の子に対して処理
		_foreach(func, node->child[0]);

		//自分自身に対して処理
		func(node->key, node->value);

		//右の子に対して処理
		_foreach(func, node->child[1]);
	}
}

void foreach(Map map, void (*func)(const char* key, const void* value)){
	//根ノードから再帰的に処理
	_foreach(func, map->root);
}

連想配列内のキーを削除

/*
 * 連想配列内のキーを削除
 * 注意：返却値について、mallocでメモリ確保していた場合、関数呼び出し元で責任をもって解放すること!!
 */
void* erase(Map map, const char* key){
	//辿ったノードを格納しておくための配列
	Node* nodes[64];

	//辿ったノードの左右を格納しておくための配列(左がfalse、右がtrue)
	bool flag[64];

	//辿ったノードの深さ
	int depth=0;

	//0番目に根ノードを格納しておく
	nodes[depth]=map->root;

	while(nodes[depth]){
		int cmp=strcmp(key,nodes[depth]->key);
		if(cmp){//キーが一致しなかった場合
			//辞書順比較。新キーが早ければ0(左)、後ならば1(右)
			flag[depth]=(cmp>0);

			//配列に子ノードを格納する
			nodes[depth+1]=nodes[depth]->child[flag[depth]];
			depth++;
			continue;
		}

		//削除対象ノード
		Node* node=nodes[depth];

		//返却値を退避
		void* value=node->value;

        //削除ノードの、キーを格納するために確保したメモリを解放する。
        free(node->key);

		/* delete処理 */
		if(node->child[0] && node->child[1]){//削除対象ノードの左右の子が存在
			//削除対象ノードの左の右の右の…右のノード（末端ノード）を取得
			flag[depth]=0;
			nodes[depth+1]=node->child[0];
			depth++;
			while(nodes[depth]->child[1]){
				flag[depth]=1;
				nodes[depth+1]=nodes[depth]->child[1];
				depth++;
			}

			//末端ノードのキーと値を削除対象ノードに移す
			node->key=nodes[depth]->key;
			node->value=nodes[depth]->value;

			//末端ノードの親の右を付け替える
			nodes[depth-1]->child[flag[depth-1]]=nodes[depth]->child[0];

			//末端ノードの解放
			free(nodes[depth]);
		}else{
			if(node->child[0]){//削除対象ノードの左の子が存在
				//親が自分に指していたポインタを、自分の左に付け替える
				if(depth){
					nodes[depth-1]->child[flag[depth-1]]=node->child[0];
				}else{
					map->root=node->child[0];
				}
			}else if(node->child[1]){//削除対象ノードの右の子が存在
				//親が自分に指していたポインタを、自分の右に付け替える
				if(depth){
					nodes[depth-1]->child[flag[depth-1]]=node->child[1];
				}else{
					map->root=node->child[1];
				}
			}else{
				//親が自分に指していたポインタを、NULLに付け替える
				if(depth){
					nodes[depth-1]->child[flag[depth-1]]=NULL;
				}else{
					map->root=NULL;
				}
			}
			//削除ノードの解放
			free(node);
		}

		//nodes[depth]は解放された領域を指しているので、NULLにする。
		nodes[depth]=NULL;

		//末端ノードの前から根に向かって平衡性を保つように処理
		take_balance(map, depth, nodes, flag);

		//対象キーに対応していた値を返す（mallocでメモリ確保した場合、呼び出し元で解放せよ）
		return value;
	}

	//キーが存在しなかった場合、NULLを返却する。
	return NULL;
}

連想配列を初期化 （プログラム終了時に忘れない!!）

/*
 * 連想配列のノードを解放
 * 右⇒左⇒親の順で解放（左⇒右⇒親でも構わない）
 */
void _clear(Node* node, int flag){
	if(node){//ノードがNULLでない場合
		//右を解放する
		_clear(node->child[1],flag);

		//左を解放する
		_clear(node->child[0],flag);

		//mallocでメモリ確保した場合、解放
		if(flag)free(node->value);

		//キーを格納するために確保したメモリを解放
		free(node->key);

		//ノードを解放
		free(node);
	}
}

/*
 * 連想配列を初期化
 */
void clear(Map map, int flag){
	//根ノードから再帰的に解放
	_clear(map->root,flag);

    //根ノードをNULLにセット
	map->root=NULL;
}

サンプルプログラム

連想配列と優先度付きキューを使ってpaizaラーニングの「文字と整数の組のソート2」を解いてきました。

sort_add_9.c

/* 文字（キー）と数値のペア */
typedef struct pair{
    char key[2];//文字（1つの半角英文字）
    int value;//数値
}pair;

/*
 * 優先度付きキュー比較関数
 * 今回は、数値の大きい方が先に取り出されるようにする。
 */
int compare(const void* a, const void* b){
    pair p=*(pair*)a;
    pair q=*(pair*)b;
    if(p.value<q.value)return 1; //「左」が「小さい」場合に正の値を返却（通常は逆）
    else if(p.value>q.value)return -1;
    else return 0; //問題の制約（まとめた数値は重複しない）より、返却値は0でよい。
}

/* 連想配列から優先度付きキューに格納 */
PriorityQueue Q;
void func(const char* key, const void* value){
    pair* p=(pair*)malloc(sizeof(pair));
    strcpy(p->key,key);
    p->value=*(int*)value;
    push(Q,p);
}

int main(void){
    //1行目に行数を表す整数が入力されます。
    int n;
    scanf("%d\n",&n);

    //連想配列初期化
    Map map=newMap();

    //続くn行の各行で「文字」と「整数」の組が空白区切りで入力されます。
    for(int i=0;i<n;i++){
        char s[2];//文字（1つの半角英文字）
        int d;//整数

        //文字と整数値を取り出す。
        scanf("%s %d\n",s,&d);

        //「文字」の値が同じ組同士の数値を足しあわせてまとめる。
        int* p=getValue(map,s);
        if(!p){
            //新規の場合は0で初期化
            p=(int*)malloc(sizeof(int));//...(*)
            *p=0;
            setValue(map,s,p);
        }
        *p+=d;
    }

    //優先度付きキューに格納する
    Q=newPriorityQueue(compare);
    foreach(map,func);

    //まとめた数値の降順で、文字とまとめた数値の組を出力する
    pair* q=NULL;
    while((q=pop(Q))!=NULL){
        printf("%s %d\n",q->key,q->value);
        free(q);
    }

    //メモリ解放
    free(Q);
    clear(map,1);//「値」を(*)でmallocしているので、「値」のメモリも解放する
    free(map);

    //終了コードを返す
    return 0;
}