Question

C++和C语言的转换

C++中的map【string】【int】这种结构C中有没有最好的替换啊，还要能随时插入新的量，非常急！！！

Answer 1

全部手工编写的，按照的是string和int的键值对插入的。 c++内置的stl map为红黑树实现的，insert和查找时间复杂度均为logn，一般来说c语言实现红黑树太过复杂，而且就论查找来说hashtable的时间复杂度查找为O1级别的常数级别，最快速度的。insert也是O1级别。所以是一种最好的替代方案。 由于本人水平有限，测试不算太完美，有可能会有疏漏还请见谅，测试数据存储在test.txt中

helloworld 1

helloworad 2

helloworla 3

chinadododo 23

nihao 33

dadadadada 31

changge 33333

meizi 2222111

shax 22334

fengzi 333

wangzi 4

nvxia 98

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<assert.h>
#define MAXSIZE 30011//one big prime
#define MAXLEN 80//string maxsize
typedef struct hashnode hashnode;
struct hashnode{
    char *str;
    int value;
    struct hashnode *next;
};
//hashtable and hashtable length
hashnode *hashtable[MAXSIZE];
int len=0;
unsigned int hash(char *s)
{
    int i;
    unsigned int key=0;
    for(i=0;s[i];i++)
    {
        key=(key<<3)+s[i]-'0';
        key%=MAXSIZE;
    }
    //printf("%u\n",key);
    return key;
}
hashnode* createnode(char *s,int v)
{
    hashnode *p=(hashnode*)malloc(sizeof(hashnode*));
    p->value=v;
    p->str=(char*)malloc(MAXLEN*sizeof(char));
    strcpy(p->str,s);
    p->next=NULL;
    return p;
}
hashnode* insert(char *s,int v)
{
    ++len;
    unsigned int key=hash(s);
    if(strlen(s)<3)
        return NULL;
    if(hashtable[key]==NULL)
    {
        hashtable[key]=createnode(s,v);
        printf("insert success!hash key is %u \n",key);
        return hashtable[key];
    }else
    {
        hashnode *p=createnode(s,v);
        p->next=hashtable[key];
        hashtable[key]=p;
        printf("insert success!hash key is %u \n",key);
        return p;
    }

}
hashnode* lookup(char *s)
{
    unsigned int key=hash(s);
    hashnode *tmp=hashtable[key];

    while(tmp!=NULL)
    {
        if(strcmp(tmp->str,s)==0)
        {
            return tmp;
        }
        else
            tmp=tmp->next;
    }
    return NULL;

}
void freehash()//free the hashtable
{
    hashnode *p,*tmp;
    int i;
    for(i=0;i<MAXSIZE;i++)
    {
        p=hashtable[i];
        while(p!=NULL)
        {
            tmp=p;
            p=p->next;
            free(p);
        }
    }
}
int main()
{
    FILE *fin=fopen("test.txt","r");
    assert(fin);
    char str[MAXLEN];
    int value;
    while(!feof(fin))
    {
        memset(str,0,MAXLEN);
        fscanf(fin,"%s %d",str,&value);
        insert(str,value);
    }
    printf("the table length is %d \n",len);
    while(1)
    {
        printf("input the string you want the look up:\n");
        scanf("%s",str);
        hashnode *p;
        p=lookup(str);
        if(p!=NULL)
            printf("the %s's value is %d!\n",str,p->value);
        else
            printf("no found!!\n");
    }
    freehash();
    fclose(fin);
    return 0;
}

Answer 2

stl库无法在C语言中使用, 因为C语言不支持模板