/*
* 题目:给定一个全部由字符串组成的字典,字符串全部由大写字母构成。其中为每个字符串编写密码,编写的
* 方式是对于 n 位字符串,给定一个 n 位数,大写字母与数字的对应方式按照电话键盘的方式:
* 2: A,B,C 5: J,K,L 8: T,U,V
* 3: D,E,F 6: M,N,O 9: W,X,Y,Z
* 4: G,H,I 7: P,Q,R,S
* 题目给出一个1--12位的数,找出在字典中出现且密码是这个数的所有字符串。字典中字符串的个数不超过5000。
*
* 思路:1.回溯法找出所有可能的字符串
* 2.在字典中查找此字符串是否存在。(字典存储采用哈希表存储)
*
*/
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define HASHTABLE_LENGTH 5001 //哈希表长度
#define STRING_LENGTH 13 //单词最大长度
//字符串
typedef struct
{
char str[STRING_LENGTH];
int length;
}HString;
HString string={'\0',0}; //暂存可能的字符串
HString hashTable[HASHTABLE_LENGTH]; //哈希表
//hash函数,构造哈希表
void createHashTable(char *str)
{
int i,key,step=1;
i=key=0;
while(str[i]){
key+=str[i++]-'A';
}
key%=HASHTABLE_LENGTH;
while(1){
if(hashTable[key].length==0){
hashTable[key].length=strlen(str);
strcpy(hashTable[key].str,str);
break;
}
key=(key+step+HASHTABLE_LENGTH)%HASHTABLE_LENGTH;
//处理冲突,线性探测再散列
if(step>0)
step=-step;
else{
step=-step;
step++;
}
}
}
//从文件中读字典
void readString()
{
int i;
char str[STRING_LENGTH];
char ch;
FILE *fp;
if((fp=fopen("document/dictionary.txt","r"))==NULL){
printf("can not open file!\n");
exit(0);
}
i=0;
while((ch=getc(fp))!=EOF){
if(ch=='\n'){//读完一个字符串
str[i]='\0';
createHashTable(str);
i=0;
continue;
}
str[i++]=ch;
}
if(fclose(fp)){
printf("can not close file!\n");
exit(0);
}
}
//在哈希表中查找是否存在该字符串,存在返回1,不存在返回0
int search(char *str)
{
int i,key,step=1;
i=key=0;
while(str[i]){
key+=str[i++]-'A';
}
key%=HASHTABLE_LENGTH;
while(1){
if(hashTable[key].length==0)
return 0;
if(strcmp(hashTable[key].str,str)==0){
return 1;
}
key=(key+step+HASHTABLE_LENGTH)%HASHTABLE_LENGTH;
//处理冲突,线性探测再散列
if(step>0)
step=-step;
else{
step=-step;
step++;
}
}
return 0;
}
//求所有可能的字符串
void getString(char* num)
{
int i,digit,max;
if(*num==0){//递归出口,字符串已到末尾
string.str[string.length]='\0';
if(search(string.str))//这个字符串存在于字典中,输出
puts(string.str);
return;
}
digit=*num-'0';//取第一位字符,转成数字
if(digit>=2&&digit<=6){
i=(digit-2)*3+'A';
max=(digit-2)*3+'A'+3;
}
else if(digit==7){
i='P';
max='P'+4;
}
else if(digit==8){
i='T';
max='T'+3;
}
else if(digit==9){
i='W';
max='W'+4;
}
for(i;i<max;i++){
string.str[string.length++]=i;
getString(num+1); //递归
string.length--;
}
}
void main()
{
char num[STRING_LENGTH]; //由于输入的数字超出了unsigned long的范围,所以用字符串来存储
readString(); //把字典从文件中读入内存
printf("please inputer an number(1--12位,不能有0或1)\n");
scanf("%s",num);
getString(num);
}
分享到:
相关推荐
任务:针对某个集体(比如你所在的班级)中的“姓名”设计一个哈希表,使得平均查找长度不超过R,完成相应的建表和查表程序。 要求:假设人名为中国人姓名的汉语拼音形式。待填入哈希表的人名共有30个,取平均查找长度的...
这是我买的一本课程设计案例书上的源代码,上面的案例很经典,特别适合于作 毕业设计的学生使用,当然了,也可以做为做课程设计的学生以参考,希望能给 大家提供帮助!!
C语言设计哈希表实现图书查找系统,完成相应的建表和查表程序。从键盘输入各图书相关信息,分别以图书编号为关键字建立散列表。待填入哈希表的书号至少30个;构造合适的哈希函数。 1) 记录由外部输入。 2) 将生成...
假设人名为中国人姓名的汉语拼音形式。待填入哈希表的人名共有30个,取平均查找长度的上限为2。哈希函数用除留余数法构造,用线性探测再散列法或链地址法处理冲突。
////采用除留余数法定义哈希表,哈希表长度为10,哈希函数为H(key)=key%13。产生冲突时采用线性探测法...////(2)在哈希表中查找元素 ////(3)在哈希表中插入元素 ////(4)输出哈希表中所有元素 ////(5)建立Hash表
在windows环境下,使用codeblocks进行哈希表的创建、增添、删除、寻找、打印
这个小程序实现了哈希表的主要内容。有哈希函数、冲突避免,实现了插入和查找。主要是作为一个教学的例子存在。 本程序用Visual Studio 2005实现。
设计哈希表实现图书查找系统,完成相应的建表和查表程序。从键盘输入各图书相关信息,分别以图书编号为关键字建立散列表。待填入哈希表的书号至少30个;构造合适的哈希函数。 (1)记录由外部输入。 (2)生成的哈希...
代码如下:/* 数据结构C语言版 哈希表 */#include <stdio>#include <malloc>#define NULLKEY 0 // 0为无记录标志 #define N 10 // 数据元素个数 typedef int KeyType;// 设关键字域为整型 typedef struct{ Key...
哈希表算法实现的C语言源程序 数据结构课程设计用
利用C++哈希表的方法实现电话号码查询系统 如何运用哈希表的算法 深刻理解哈希表 利用C++哈希表的方法实现电话号码查询系统 如何运用哈希表的算法 深刻理解哈希表
哈希表节点结构 struct Node:表示哈希表中的一个节点,包含键、值以及指向下一个节点的指针。 哈希表结构 struct HashTable:表示哈希表,包含一个存储节点指针的数组。 创建哈希表函数 createHashTable:动态...
用c语言写的哈希表的设计,以通讯录来作为哈希表的实现 冲突处理H(key)=krey%20
数据结构里哈希表的实验报告 构造二叉树,构造哈希表等 c语言版
本文为大家分享了C语言基于哈希表实现通讯录的具体代码,供大家参考,具体内容如下 1.需求分析 本演示程序用C语言编写,完成哈希表的生成,电话号码的插入、以及查找等功能。 (1)按提示输入相应的联系人的相关...
输入:待哈希数据序列 功能要求:输出哈希方法和解决冲突的方法(文字输出),输出哈希表
C语言课程设计报告-基于哈希表的二叉树优化,利用哈希表的查找性能优化二叉树的操作(比平衡二叉树性能更高),需要的小伙伴私信我,直接发链接给你。不用在CSDN上下载哈(你有VIP的话当我没说)。课程中不仅仅设计...
资源包括:源代码,可执行文件。 1.问题描述 设计散列表实现电话...6)输出相应的哈希表,计算平均查找长度; 7)设计一个菜单,上述操作要求都作为菜单中的主要菜单项。 3.测试数据 取所在班级的 n(n>=20)个同学记录。