`

0805: 判断字符串 b 的所有字符是否都在字符串 a 中出现过

阅读更多

编程题
判断字符串 b 的所有字符是否都再字符串 a 中出现过,a,b都是可能包含汉字的字符串。b中重复出现的汉字,那么a中也要至少出现相同的次数。
汉字使用gbk编码(简单的所,用两个字节表示一个汉字,高字节最高位为1的代表汉字,低字节最高位可以不为1)。
int is_include(char *a  ,  char *b)
返回0 表示没有都出现过,返回1表示都出现过。

#include <stdio.h>
#include <windows.h>
#include <string.h>

typedef struct node{
	char key[2];
	int count;
	int tag;
}hnode;

/*--------------------------hash设计--------------------------------
/*本部分的哈希表采用二次探查闭散列算法*/

/* int hash(hnode item,int m)
 * 功能: 哈希函数
 * item: 字符结构体
 * m: 散列质数
*/
int hash(hnode item,int m){
	int ret;
	char key[2];
	key[0]=item.key[0];
	key[1]=item.key[1];

	if(item.tag==0){// 英文字符
		ret=key[0]%m;
	}else{ //中文字符
		ret=((key[0])*key[1])%m;
		if(ret<0){
			ret=-ret;
		}
	}

	return ret;
}


/* int p(hnode item,int i,int m2)
 * 功能: 第i次探查函数
 * item: 字符结构体
 * i:第i次探查
 * m2: 第二质数
*/
int p(hnode item,int i,int m2){
	return i*hash(item,m2);
}



/* insert_node(hnode *item,hnode *table,int hlen,int m1,int m2)
 * 功能: 将字符结构体插入一个哈希表中
 * item: 需要检查的字符结构体
 * table: 待检索的哈希表
 * hlen: 带检索的哈希表的大小
 * m1: 第一质数
 * m2: 第二质数
*/
void insert_node(hnode item,hnode *table,int m1,int m2){
	int index=hash(item,m1);
	int i=1;
	while(true){
		hnode node=*(table+index);
		if(node.tag==2){
			item.count=1;
			*(table+index)=item;    //出错点!!!
			break;
		}else{
			if(node.tag==item.tag){
				if(node.key[0]==item.key[0] && node.key[1]==item.key[1] ){   
						(*(table+index)).count=node.count+1;    //出错点!!!
						break;
				}
			}else{
					index=(index+p(item,i++,m2))%m1;
			}
		}
	}

}



/* 功能: 为一个字符串创建哈希表
 * list: 字符串
 * len: 字符串的长度
 * m1: 质数1
 * m2: 质数2
*/
hnode* create_hash(char *list,int len,int m1,int m2){
/* 新建hashtable,长度为字符串长度的两倍 */
   hnode *htable=new hnode[len*2];
   for(int k=0;k<len*2;k++){
	   hnode node;
	   node.tag=2;
	   *(htable+k)=node;
   }
   
   /* 为list中的每个字符创建hashnode */
   /* 将每个hashnode insert到 hashtable中 */
   /* 返回 hashtable的指针 */
   for(int i=0;i<len;i++){
	   hnode *node=new hnode();
	   if(list[i]>0){
		   node->key[0]=list[i];
		   node->key[1]='#';
		   node->tag=0;
	   }else{
		   node->key[0]=list[i];
		   node->key[1]=list[i++];
		   node->tag=1;	   
	   }

	   insert_node(*node,htable,m1,m2);
   }

   return htable;

}


/* 求比n小的最大质数 */
int getZhiShu(int n){
	int tag=0;
	int ret=-1;
    for(int i=n;i>=2;i--){
		for(int j=2;j<i;j++){
			if(i%j==0){
				tag=1;
				break;
			}
		}
		if(tag==0){
			ret=i;
			break;
		}
		tag=0;
			
	}
	return ret;

}




/*----------判断字串函数 int is_include(char *a  ,  char *b)-----------------*/

/*
 *功能: 判断字符串包含关系
 *a, b: 待判断的两个字符串
*/
int is_include(char *a  ,  char *b){
 /*求得a、b的字符数目*/
	int len1=strlen(a);
	int len2=strlen(b);
	int hashlen1=len1*2;
	int hashlen2=len2*2;
 //获得第一和第二质数
	int m11=getZhiShu(hashlen1);
	int m12=getZhiShu(m11-1);
	int m21=getZhiShu(hashlen2);
	int m22=getZhiShu(m21-1);
 //创建两个哈希表,哈希表的大小为字符数的两倍
	hnode *htable2=create_hash(b,len2,m21,m22);
	hnode *htable1=create_hash(a,len1,m11,m12);


 //hashb中的每个元素在 hasha中进行查找
	// 如果没找到,则退出 return -1
	// 如果找到了
	    //如果b中的个数比a中少,则查找下一个
	    //退出 return -1
	for(int i=0;i<hashlen2;i++){
		hnode node2=*(htable2+i);
		if(node2.tag!=2){
			int index=hash(node2,m11);  //出错点!!!!!!
			hnode node1=*(htable1+index);
			int n=0;
			while(node1.tag!=2){
				if(node1.tag==node2.tag){
					if(node1.key[0]==node2.key[0] &&node1.key[1]==node2.key[1]){
						if(node1.count>=node2.count){
					
							break;
						}else{
							return 0;
						}
					}
				}
				else{
					index=(index+p(node2,n++,m12))%m11;
					node1=*(htable1+index);
				}
			}
			if(node1.tag==2){
				return 0;
			}
		}
		
	}
	return 1;       

}

void main(){
	char *a="aabbcc黄老师";
	char *b="abc黄宇";

	int ret=is_include(a, b);
	printf("result is :%d\n",ret);


}


 

分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics