多个字符串数组里面找出为输入字符串数组匹配的数组
时间：2009-08-14 来源：ubuntuer
1. 如果有多个“字符串数组”，我输入一个字符串数组，请问有什么算法可以很快的找到那多个数组里面和它匹配的数组出来呢？（数组中顺序可能不一样）
老规矩,先说说我个人的主观的理解
char* str1[3] = {"aaa","bbb","ccc"};
char* str2[4] = {"aaa","bbb","ccc","ddd"};
如果输入为{"aaa","bbb","ccc"},则str1和str2都是匹配的,当然这都是细话,说重点了
字符串,无序,匹配!!!!聪明的你已经知道是hash了....
typedef struct hash
{
char str[MAX_STR]; //字符串数组的最大长度为MAX_STR
struct hash* next; //这就表示是链表解决冲突了,说实话hash冲突解决自己写程序我还只会这个
}HASH;
HASH** H;
这样一个字符串数组就搞定了....但是要把所有的H链接起来
typedef struct list
{
HASH** H;
struct list* next;
}LIST;
LIST* L;
结构定义就这么多了...
开始伪码:
INIT_LIST(&L);
while(get string array)
{
INIT_HASH(&H);
while(get string)
CHAIN_HASH_ADD(H, string)
LIST_ADD_HASH(L,H);
}
这样hash链表就ok了,接下来就是匹配了
FIND_MATH(L,INPUTED STRING ARRAY)
{
LIST* p = L->next;//我的习惯是写带头的链表
while(p!=NULL)
{
HASH** h = p->H;
while(get string from string array)
{
FIND_STRING_IN_HASH(H, STRING)
if(FINDED)
get next string;
else
break;
}
if(string in string array total mathed)
{
如果只是找一个匹配的,这里就可以break了
如果是找全部匹配的,这里就保存这个p,也就是链表的一个节点
}
p = p->next;
}
}
打完收工,发现自己还是不会写伪码,也不知道各位看不看得懂,这个思路在这里,根据这个写代码,也很easy的.
相关阅读 更多 +
