這是一個古老的線程，但我認爲這可能對任何尋找實現的人都有用。它不需要太多的代碼;我在沒有任何額外的圖書館的情況下做了100行。我將它稱爲字典，因爲它與python數據類型相似（有點類似）。這裏是我的代碼：
#include <stdlib.h>
#include <stdio.h>
#include <stdbool.h>
typedef struct hollow_list hollow_list;
struct hollow_list{
unsigned int size;
void *value;
bool *written;
hollow_list *children;
};
//Creates a hollow list and allocates all of the needed memory
hollow_list hollow_list_create(unsigned int size){
hollow_list output;
output = (hollow_list) {.size = size, .value = (void *) 0, .written = calloc(size, sizeof(bool)), .children = calloc(size, sizeof(hollow_list))};
return output;
}
//Frees all memory of associated with a hollow list and its children
void hollow_list_free(hollow_list *l, bool free_values){
int i;
for(i = 0; i < l->size; i++){
hollow_list_free(l->children + i, free_values);
}
if(free_values){
free(l->value);
}
free(l);
}
//Reads from the hollow list and returns a pointer to the item's data
void *hollow_list_read(hollow_list *l, unsigned int index){
if(index == 0){
return l->value;
}
unsigned int bit_checker;
bit_checker = 1<<(l->size - 1);
int i;
for(i = 0; i < l->size; i++){
if(bit_checker & index){
if(l->written[i] == true){
return hollow_list_read(l->children + i, bit_checker^index);
} else {
return (void *) 0;
}
}
bit_checker >>= 1;
}
}
//Writes to the hollow list, allocating memory only as it needs
void hollow_list_write(hollow_list *l, unsigned int index, void *value){
if(index == 0){
l->value = value;
} else {
unsigned int bit_checker;
bit_checker = 1<<(l->size - 1);
int i;
for(i = 0; i < l->size; i++){
if(bit_checker & index){
if(!l->written[i]){
l->children[i] = hollow_list_create(l->size - i - 1);
l->written[i] = true;
}
hollow_list_write(l->children + i, bit_checker^index, value);
break;
}
bit_checker >>= 1;
}
}
}
typedef struct dictionary dictionary;
struct dictionary{
void *value;
hollow_list *child;
};
dictionary dictionary_create(){
dictionary output;
output.child = malloc(sizeof(hollow_list));
*output.child = hollow_list_create(8);
output.value = (void *) 0;
return output;
}
void dictionary_write(dictionary *dict, char *index, unsigned int strlen, void *value){
void *hollow_list_value;
dictionary *new_dict;
int i;
for(i = 0; i < strlen; i++){
hollow_list_value = hollow_list_read(dict->child, (int) index[i]);
if(hollow_list_value == (void *) 0){
new_dict = malloc(sizeof(dictionary));
*new_dict = dictionary_create();
hollow_list_write(dict->child, (int) index[i], new_dict);
dict = new_dict;
} else {
dict = (dictionary *) hollow_list_value;
}
}
dict->value = value;
}
void *dictionary_read(dictionary *dict, char *index, unsigned int strlen){
void *hollow_list_value;
dictionary *new_dict;
int i;
for(i = 0; i < strlen; i++){
hollow_list_value = hollow_list_read(dict->child, (int) index[i]);
if(hollow_list_value == (void *) 0){
return hollow_list_value;
} else {
dict = (dictionary *) hollow_list_value;
}
}
return dict->value;
}
int main(){
char index0[] = "hello, this is a test";
char index1[] = "hello, this is also a test";
char index2[] = "hello world";
char index3[] = "hi there!";
char index4[] = "this is something";
char index5[] = "hi there";
int item0 = 0;
int item1 = 1;
int item2 = 2;
int item3 = 3;
int item4 = 4;
dictionary d;
d = dictionary_create();
dictionary_write(&d, index0, 21, &item0);
dictionary_write(&d, index1, 26, &item1);
dictionary_write(&d, index2, 11, &item2);
dictionary_write(&d, index3, 13, &item3);
dictionary_write(&d, index4, 17, &item4);
printf("%d\n", *((int *) dictionary_read(&d, index0, 21)));
printf("%d\n", *((int *) dictionary_read(&d, index1, 26)));
printf("%d\n", *((int *) dictionary_read(&d, index2, 11)));
printf("%d\n", *((int *) dictionary_read(&d, index3, 13)));
printf("%d\n", *((int *) dictionary_read(&d, index4, 17)));
printf("%d\n", ((int) dictionary_read(&d, index5, 8)));
}
可惜你不能複製列表[X]語法，但是這是我想出了最好的選擇。
是的，你是對的。加密狗中的數據處理功能處理單個數據。我真的覺得我需要實現一個簡單的關聯數組，其中包含8個字符長度索引和一個線性索引搜索算法！我只是認爲不要重新發明輪子，並詢問是否有人已經實施它。 – ezpresso 2011-02-01 18:25:54