C语言 字典/Map/键值对数据结构

k3bvogb1  于 11个月前  发布在  其他
关注(0)|答案(5)|浏览(108)

如何在C中构造和访问一组键值对？举一个简单的例子，假设我想创建一个在整数和它的平方根之间转换的表。
如果我在写JavaScript，我可以这样做：

var squareRoots = {
   4: 2,
   9: 3,
   16: 4,
   25: 5
}

字符串
然后像这样访问它们：

var squareRootOf25 = squareRoots[5]

型
如果我想使用一种类型的枚举作为键，另一种类型的枚举作为值，该怎么办？

c

5条答案

按热度按时间
y3bcpkx1

y3bcpkx11#

你可以考虑在C语言中实现哈希来实现这一点。有关哈希的基础知识，请参阅Wikipedia。请参阅此问题以了解更多细节和链接。
这个link提供了很好的概述和实现细节。

赞(0）分享  回复(0）举报  11个月前
eyh26e7m

eyh26e7m2#

没有内置的方法可以做到这一点，除非你在C99中这样初始化一个数组：

double squareRoots[] =
{
     [4] = 2.0,
     [9] = 3.0,
    [16] = 4.0,
    [25] = 5.0,
};

字符串
但是，这会在数组中分配26个元素;其他值都是零。
假设你不是这个意思，那么看看D R Hanson的C Interfaces and Implementations;它展示了一种实现关联数组（也称为哈希或字典）的方法。

赞(0）分享  回复(0）举报  11个月前
oalqel3c

oalqel3c3#

你也可以使用libghthash作为通用哈希。它们非常容易使用，并且可以集成到你的应用程序中。然而，它是第三方API -所以如果这是一个问题，你必须实现自己的。
C中没有内置的关联数组/哈希表。
数组初始化（C99）可能是最好的方法，除非你有非数字键：

T hash[] = {
    [1] = tObj,
    [255] = tObj2,
};

字符串

赞(0）分享  回复(0）举报  11个月前
yb3bgrhw

yb3bgrhw4#

您可以使用作为clib库的一部分实现的map

赞(0）分享  回复(0）举报  11个月前
balp4ylt

balp4ylt5#

这个问题可以用map来解决。不幸的是，C中没有与map非常相似的数据结构**（map是一个以键值对方式存储元素的容器。每个元素都有一个唯一的键，用于访问对应的值。map通常被实现为平衡二叉搜索树，提供高效的查找和插入操作）**。这意味着你应该自己实现它。虽然这可能不是应对这个挑战的最佳方法，但我已经实现了一个使用二叉搜索树结构的Map，这并不保证最坏的时间复杂度不是线性的。另一种保证最坏的时间复杂度仍然是O（log2（n））的数据结构是自平衡红黑树。接下来我将介绍我在实现所要求的所谓Map方面的尝试。

#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);
}
int compare(char *a,char *b){
    //Hello! I am the compare function and I:
    // return -1, if a and b are the same.
    // return 0, if a "<" b.
    // return 1, if a ">" 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]&&x==i)
    return -1;
    if(!a[i]&&b[i])
    return 0;
    return 1;
};
struct Nod{
    struct Pair *val;
    struct Nod *st,*dr;
};
struct Tree{
    struct Nod *top;
};
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;
            }
        }
        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;
            }
        }
        if(x==-1){
            nod->val->second=val;
            return;
        }
    }
}
void poptotree(struct Tree *t,char *s){
    if(!t->top) return;
    int u=0;
    struct Nod *nod=t->top,*p=NULL,*te=NULL;
    while(nod){
        te=nod;
        int x=compare(s,nod->val->first);
        if(x==1) nod=nod->dr,u=1;
        if(x==0) nod=nod->st,u=0;
        if(x==-1){
            if(nod->st&&nod->dr){
                struct Nod *search=nod->st,*pa=NULL;
                while(search->dr) pa=search,search=search->dr;
                if(pa){
                    pa->st=search->st;
                    pa->dr=NULL;
                    nod->val=make_pair(search->val->first,search->val->second);
                    free(search->val);
                    free(search);
                }
                else{
                    nod->st=nod->st->st;
                    nod->val=make_pair(search->val->first,search->val->second);
                    free(search->val);
                    free(search);
                }
                return;
            }
            else if(!nod->st&&nod->dr){
                if(p){
                    if(u){
                        p->dr=nod->dr;
                        free(nod->val);
                        free(nod);
                    }
                    else{
                        p->st=nod->dr;
                        free(nod->val);
                        free(nod);
                    }
                }
                else{
                    t->top=nod->dr;
                    free(nod->val);
                    free(nod);
                }
                return;
            }
            else if(nod->st&&!nod->dr){
                if(p){
                    if(u){
                        p->dr=nod->st;
                        free(nod->val);
                        free(nod);
                    }
                    else{
                        p->st=nod->st;
                        free(nod->val);
                        free(nod);
                    }
                    return;
                }
                else{
                    t->top=nod->st;
                    free(nod->val);
                    free(nod);
                    return;
                }
            }
            else{
                if(p){
                    if(u){
                        p->dr=NULL;
                        free(nod->val);
                        free(nod);
                    }
                    else{
                        p->st=NULL;
                        free(nod->val);
                        free(nod);
                    }
                }
                else{
                    free(t->top->val);
                    free(t->top);
                    t->top=NULL;
                }
            }
            return;
            }
        p=te;
    }
}
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;
        if(x==0)nod=nod->st;
        if(x==-1){
            return nod;
        }
    }
    return NULL;
}
struct Map{
    struct Tree **t;
    int size;
};
struct Map *createMap(int size){
    if(size<=0) return NULL;
    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);
};
void pop(struct Map *m,char *s){
    int hash=make_hash(s,m->size);
    if(!m->t[hash]) return;
    poptotree(m->t[hash],s);
};
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 nod->val->second;
    return 0;
};
int main()
{
    return 0;
}

字符串

赞(0）分享  回复(0）举报  11个月前
我来回答

相关问题

    查看更多

    热门标签

    更多
    JavaquerypythonNode开发语言requestUtil数据库Table后端算法LoggerMessageElementParser

    最新问答

    更多
    • 蜀ICP备2022004421号-2 NULL123 https://www.null123.com © All rights reserved
    • 本站内容来源互联网,如果侵犯您的权益请联系我们删除, 联系方式：448109455@qq.com