C 中类似映射的结构：使用 int 和 struct 来确定值

问题描述 投票：0回答：2

我以前用 C++ 编码，现在我尝试用 C 编程。

假设我已经定义了一个结构体

struct point{
    int x;
    int y;
}


A
中是否有任何数据结构
c
可以支持以下功能： 给定两个整数，例如 
i
和 
j
，以及两个点，例如 
p1
和 
p2
。 
A[i][j][p1][p2]
可以唯一确定一个值。

听起来像一个 4 维数组。但是，索引不再是 int，而是用户定义的 

struct
。

c dictionary indexing struct
2个回答
57
投票

您可能必须制作自己的结构。 Kernighan 和 Ritchie 的《C 编程语言》 有一个用 c 语言制作关联映射的示例，下面我将根据我所记得的内容详细介绍。

基本上，您需要一个包含结构体Key和结构体Value的结构体Map。

struct Map {
    struct Key key;
    struct Value value;
};

struct Key 包含确定值的元素（在您的情况下为 2 个点和 2 个整数）

struct Key {
    struct point p1;
    struct point p2;
    int i;
    int j;
};

struct Value 是您希望密钥指向的任何内容（您没有说）

您现在有一个结构体 Map 将您的四个输入与一个值关联起来，但单个映射并没有那么有用。你会想要一整套。

struct Map map[SIZE_OF_MAP];

如果您不想在数组中线性搜索要查找的 Map 结构，您可以创建一个哈希函数，直接找到它。只需定义一个函数，该函数接受键并使用其值为其分配数组中的索引。使用哈希将 Map 放入数组中并从数组中检索它。 （注意：我不确定这是否是正确的哈希示例，如果完全错误，请更正）

int get_hash(Key *key)
{
    int result;
    /* combine all inputs in some way */
    result = key->i * key->i + (key->p1.x * key->p1.x) - (key->p2.x * key->p2.x)
    /* make sure result isn't out of bounds of the array */
    return (result % SIZE_OF_MAP);
}

如果您使用哈希函数，则必须考虑冲突（当两个键为 get_hash 提供相同结果时会发生什么）。当您使用地图数组时，您将需要某种形式的碰撞解决方案。

0
投票

我已经积极从事 C++ 和 C 编程一年多了。最近，我对用 C 实现类似地图的结构的想法很感兴趣，并且我发现了一种解决这一挑战的方法。该策略涉及利用一组二叉搜索树 (BST) 来创建映射结构：

struct Map{ struct Tree **t; };

在该方法中，树的定义如下：

struct Pair{
    char *first;
    int second;
};
struct Pair *make_pair(char *a,int b){
struct Pair *x=(struct Pair *)malloc(sizeof(struct Pair));
x->first=strdup(a);
x->second=b;
return x;
};
struct Nod{
struct Pair *val;
struct Nod *dr,*st;
};
struct Tree{
struct Nod *top;
};

此外，还需要一个 make_hash 函数来为 char* 生成哈希值，以及一个用来“比较”两个“字符串”的 Compare 函数：

//create the hash
int make_hash(char *s,int size){
//use unsigned long long because it starts from 0 after going past the limit.
unsigned long long hash=5813;
for(int i=0;s[i];i++) hash=hash*33+s[i];
return (hash%size);
};
//compare two "strings"
//note: my compare function returns -1 if both "strings" are equal 
int compare(char *a,char *b){
int i=0,x=0;
for(;a[i]&&b[i];i++){
    if(b[i]>a[i]) return 0;
    if(b[i]==a[i])x++;
}
if(a[i]&&!b[i])
return 1;
if(!a[i]&&b[i])
return 0;
if(!a[i]&&!b[i]&&x==i)
return -1;
};

最后，实现需要在我们的程序中添加和查找 char* 及其对应值的函数：

void addtotree(struct Tree *t,char *s,int val){
if(!t->top){
    t->top=(struct Nod *)malloc(sizeof(struct Nod));
    t->top->val=make_pair(s,val);
    t->top->st=NULL;
    t->top->dr=NULL;
    return;
}
struct Nod *nod=t->top;
while(nod){
    int x=compare(s,nod->val->first);
    if(x==1){
        if(nod->dr){
            nod=nod->dr;
        }
        else{
            nod->dr=(struct Nod *)malloc(sizeof(struct Nod));
            nod->dr->val=make_pair(s,val);
            nod->dr->dr=NULL;
            nod->dr->st=NULL;
            return;
        }
    }
    else if(x==0){
        if(nod->st){
            nod=nod->st;
        }
        else{
            nod->st=(struct Nod *)malloc(sizeof(struct Nod));
            nod->st->val=make_pair(s,val);
            nod->st->dr=NULL;
            nod->st->st=NULL;
            return;
        }
    }
    else if(x==-1){
        nod->val->second=val;
        return;
    }
}
}
struct Nod *findtotree(struct Tree *t,char *s){
struct Nod *nod=t->top;
while(nod){
    int x=compare(s,nod->val->first);
    if(x==1) nod=nod->dr;
    else if(x==0) nod=nod->st;
    else return nod;
}
return NULL;
};
void add(struct Map *m,char *s,int val){
int hash=make_hash(s,m->size);
if(!m->t[hash]){
    m->t[hash]=(struct Tree *)malloc(sizeof(struct Tree));
    m->t[hash]->top=NULL;
}
addtotree(m->t[hash],s,val);
};
int find(struct Map *m,char *s){
int hash=make_hash(s,m->size);
if(!m->t[hash]) return 0;
struct Nod *nod=findtotree(m->t[hash],s);
if(!nod) return 0;
return nod->val->second;
};

值得注意的是，这张地图的实现还有改进的空间。考虑到这一点，现在让我整合所有组件：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct Pair{
    char *first;
    int second;
};
struct Pair *make_pair(char *a,int b){
    struct Pair *x=(struct Pair *)malloc(sizeof(struct Pair));
    x->first=strdup(a);
    x->second=b;
    return x;
};
int make_hash(char *s,int size){
    unsigned long long hash=5813;
    for(int i=0;s[i];i++) hash=hash*33+s[i];
    return (hash%size);
};
struct Nod{
    struct Pair *val;
    struct Nod *dr,*st;
};
struct Tree{
    struct Nod *top;
};
int compare(char *a,char *b){
    int i=0,x=0;
    for(;a[i]&&b[i];i++){
        if(b[i]>a[i]) return 0;
        if(b[i]==a[i])x++;
    }
    if(a[i]&&!b[i])
    return 1;
    if(!a[i]&&b[i])
    return 0;
    if(!a[i]&&!b[i]&&x==i)
    return -1;
};
void addtotree(struct Tree *t,char *s,int val){
    if(!t->top){
        t->top=(struct Nod *)malloc(sizeof(struct Nod));
        t->top->val=make_pair(s,val);
        t->top->st=NULL;
        t->top->dr=NULL;
        return;
    }
    struct Nod *nod=t->top;
    while(nod){
        int x=compare(s,nod->val->first);
        if(x==1){
            if(nod->dr){
                nod=nod->dr;
            }
            else{
                nod->dr=(struct Nod *)malloc(sizeof(struct Nod));
                nod->dr->val=make_pair(s,val);
                nod->dr->dr=NULL;
                nod->dr->st=NULL;
                return;
            }
        }
        else if(x==0){
            if(nod->st){
                nod=nod->st;
            }
            else{
                nod->st=(struct Nod *)malloc(sizeof(struct Nod));
                nod->st->val=make_pair(s,val);
                nod->st->dr=NULL;
                nod->st->st=NULL;
                return;
            }
        }
        else if(x==-1){
            nod->val->second=val;
            return;
        }
    }
}
struct Nod *findtotree(struct Tree *t,char *s){
    struct Nod *nod=t->top;
    while(nod){
        int x=compare(s,nod->val->first);
        if(x==1) nod=nod->dr;
        else if(x==0) nod=nod->st;
        else return nod;
    }
    return NULL;
};
struct Map{
struct Tree **t;
int size;
};
struct Map *createMap(int size){
    struct Map *m=(struct Map *)malloc(sizeof(struct Map));
    m->size=size;
    m->t=(struct Tree **)calloc(size,sizeof(struct Tree *));
    for(int i=0;i<size;i++) m->t[i]=NULL;
    return m;
};
void add(struct Map *m,char *s,int val){
    int hash=make_hash(s,m->size);
    if(!m->t[hash]){
        m->t[hash]=(struct Tree *)malloc(sizeof(struct Tree));
        m->t[hash]->top=NULL;
    }
    addtotree(m->t[hash],s,val);
    };
    int find(struct Map *m,char *s){
        int hash=make_hash(s,m->size);
        if(!m->t[hash]) return 0;
        struct Nod *nod=findtotree(m->t[hash],s);
        if(!nod) return 0;
        return nod->val->second;
    };
最新问题
© www.soinside.com 2019 - 2024. All rights reserved.