关键字算法
❶ 候选关键字的一般的求候选码的算法
已知关系模式R(U）属性集是A1A2...An及R的函数依赖集F，求R(U）的一个候选码。
算法：
KEY(X,F)
K=A1A2…An;
For i=1 to n
{求K-Ai相对于F的属性闭包（K-Ai)F+;
if (K-Ai)F + =U then K=K-Ai
else then K=K; }
return K;
利用此算法求R(U）的候选码时，只能求出一个，并不能保证求出所有的码。但可以用同样的方法调整属性的删除次序而把所有的候选码都求解出来。
如此题设关系R(ABCD）及R上成立的函数依赖集为F,F={AB→C,C→D,D→A},求R的所有码。
按照上面的算法具体步骤如下：
设K={ABCD},当K=BCD时，由于KF+=ABCD，所以根据算法可删除A;
K=CD，由于KF+=ACD又因KF+不等于ABCD，所以根据算法，B不可删除；
K=BD，由于KF+=ABCD且因KF+=AB-CD，所以根据算法C可删除；
K=B，由于KF+=B又因KF+不等于ABCD,
所以根据算法，D不可删除；最后可求出KEY=BD，用同样的方法调整属性的删除次序，还可以得到另外的一个候选码AB，所以最后可以得到R的码为BD和AB。
一般求解算法适用于在判断了所有的属性均是属于在函数依赖的左部和右部都出现且在后面的几种算法都不适合的情况下采用的。
简而言之：算法概述——有N个属性，从1到N循环。K初始为全部属性，每次循环时减去第N个属性，如果KF+包含全部属性，则K的值重新附值为K减去第N个属性后的值；否则K仍为上次循环后的值。（算法适于所有属性皆为LR类且其他算法不合适时，实际算时要更换删除顺序后反复计算）
❷ 用哈希表实现C语言关键字的算法
#include <iostream.h>
#include<fstream.h>
#include <string>
#include <iomanip.h>
using namespace std;
const int TOTAL=32;
const int MAXLEN=10;
const int HASHLEN=41;
int cont=0;
class HashTable
{
public:
char keyword[MAXLEN];
int count;
int num;
};
HashTable HS[HASHLEN];
char KeyWords[TOTAL][MAXLEN]= {
"char", "double", "enum", "float", "int", "long", "short", "signed",
"struct", "union", "unsigned", "void", "break", "case", "continue",
"default", "do", "else", "for", "goto", "if", "return", "switch", "while",
"auto", "extern", "register", "static", "const", "sizeof", "typedef", "volatile"
};
template<class T>
class HASH
{
public:
void Show(int key);
int CreatHX(char *keyword);
int GetFreePos(int key);
void ResetHX();
int GetKey(char *keyword);
int isKeyWords(char *word);
int Read(char *filename);
int isLetter(char ch);
int FindHX(char *keyword);
private:
int key;
char *keyword;
char *word;
char ch;
};
template<class T>
void HASH<T>::Show(int key)
{
if(key<0||key>=HASHLEN)
{
cout<<"关键字不存在!"<<endl;
return;
}
if(strlen(HS[key].keyword)==0)
{
cout<<"哈希表位置："<<key<<" 记录是空的"<<endl;
return ;
}
cout<<"哈希表位置: "<<key<<" 关键字: "
<<HS[key].keyword<<" 出现次数 "<<HS[key].count<<endl;
cont++;
}
template<class T>
int HASH<T>::CreatHX(char *keyword)
{
int key;
if(!isKeyWords(keyword)) return -1;
key=GetKey(keyword);
if(strlen(HS[key].keyword)>0)
{
if(strcmp(HS[key].keyword,keyword)==0)
{
HS[key].count++;
return 1;
}
key=FindHX(keyword);
if(key<0)
{
key=GetFreePos(GetKey(keyword));
if(key<0) return -1;
strcpy(HS[key].keyword,keyword);
}
if(key<0) return -1;
HS[key].count++;
}
else
{
strcpy(HS[key].keyword,keyword);
HS[key].count++;
}
return 1;
}
template<class T>
int HASH<T>::GetFreePos(int key)
{
int find,tem=0;
if(key<0||key>=HASHLEN) return -1;
for(find=key+1;find<HASHLEN;find++)
{
tem++;
if(strlen(HS[find].keyword)==0){
HS[find].num=tem;
return find; }
}
for(find=0;find<key;find++)
{
tem++;
if(strlen(HS[find].keyword)==0){
HS[find].num=tem;
return find; }
}
return -1;
}
template<class T>
void HASH<T>::ResetHX()
{
int i;
for(i=0;i<HASHLEN;i++)
{
strcpy(HS[i].keyword,"");
HS[i].count=0;
HS[i].num=0;
}
}
template<class T>
int HASH<T>::GetKey(char *keyword)
{
return ( keyword[0]*100+keyword[strlen(keyword)-1] ) % 41;
}
template<class T>
int HASH<T>::isKeyWords(char *word)
{
int i;
for(i=0;i<TOTAL;i++)
if(strcmp(word,KeyWords[i])==0) return 1;
return 0;
}
template<class T>
int HASH<T>::isLetter(char ch)
{
if( (ch>='a'&&ch<='z')||(ch>='A'&&ch<='Z') ) return 1;
else return 0;
}
template<class T>
int HASH<T>::FindHX(char *keyword)
{
int key,find,tem=0;
if(!isKeyWords(keyword)) return -1;
key=GetKey(keyword);
if(strcmp(HS[key].keyword,keyword)==0) return key;
for(find=key+1;find<HASHLEN;find++)
{
tem++;
if(strcmp(HS[find].keyword,keyword)==0){
HS[find].num=tem;
return find; }
}
for(find=0;find<key;find++)
{
tem++;
if(strcmp(HS[find].keyword,keyword)==0){
HS[find].num=tem;
return find; }
}
return -1;
}
template<class T>
int HASH<T>::Read(char *filename)
{
char word[MAXLEN],ch;
int i;
FILE *read;
fstream myfile;
myfile.open("filename");
if(!myfile)
{
cout<<"文件不存在,请确认好再输入!"<<endl;
return -1;
}
ResetHX();
while(!feof(read))
{
i=0;
ch=fgetc(read);
while(isLetter(ch)==0 && feof(read)==0 )
ch=fgetc(read);
while(isLetter(ch)==1 && feof(read)==0 )
{
if(i==MAXLEN)
{
while(isLetter(ch)==1&& feof(read)==0)
{
ch=fgetc(read);
}
i=0;
break;
}
else
{
word[i++]=ch;
ch=fgetc(read);
}
}
word[i]='\0';
if(isKeyWords(word))
{
CreatHX(word);
}
}
fclose(read);
cout<<"读取成功，文件中关键字已经存入hash表，请继续操作"<<endl;
return 1;
}
void main()
{
HASH<char> hash;
char filename[128],word[MAXLEN];
int i=0,count=0;
int key;
char j,y;
cout<<"请输入要读取的文件名:";
cin>>filename;
cout<<endl;
hash.Read(filename);
for(i=0;i<HASHLEN;i++)
{
hash.Show(i);
getchar();
}
cout<<"关键字总数为："<<cont<<endl;
cout<<"请输入你想要查找的关键字： ";
cin>>word;
cout<<endl;
hash.Show(hash.FindHX(word));
cout<<" C语言中的关键字和其在哈希表的位置:"<<endl;
for(i=0;i<TOTAL;i++)
{
cout<<setiosflags(ios::left)<<"["<<setw(2)<<hash.GetKey(KeyWords[i])<<"]"
<<setiosflags(ios::left)<<setw(11)<<KeyWords[i];
if((i+1)%4==0) cout<<endl;
}
cout<<"是否显示冲突关键字列表？y(是) 其它（否）:";
cin>>j;
if(j=='y')
{
cout<<"冲突关键字列表"<<endl;
for(i=0;i<HASHLEN;i++)
{
if(strlen(HS[i].keyword)>0)
{
key=hash.GetKey(HS[i].keyword);
if(key!=i)
{
count++;
cout<<setiosflags(ios::left)<<setw(14)<<
"\t[关键 字]:"<<HS[i].keyword<<setiosflags(ios::left)<<
setw(20)<<"\t[哈希表当前位置]: "<<i<<setiosflags(ios::left)<<
setw(20)<<"\t[冲突次数]: "<<HS[i].num<<endl;
}
}
}
if(count==0)
cout<<"没有冲突"<<endl;
else
cout<<"\t冲突关键字共:"<<count<<"个"<<endl;
}
else
cout<<"不显示冲突关键字列表，但已存在！"<<endl;
return;
}
❸ 基于关键字比较的排序算法有哪些
1.插入排序：直接插入、希尔排序
2.选择排序：简单选择排序、堆排序
3.交换排序：冒泡排序、快速排序
4.归并排序
❹ java关键字查询算法
import java.io.FileReader;
import java.io.BufferedReader;
import java.io.File;
public class search
{
//查找方法，参数，文件绝对路径，查找关键字
public static boolean search(String filepath,String key)
{
try
{
File f = new File(filepath);
FileReader fr = new FileReader(f);
BufferedReader br = new BufferedReader(fr);
String s = "";
//int i = 1;
while((s = br.readLine()) != null)
{
if(s.indexOf(key) != -1)
{
return true;
}
}
return false;
}
catch(Exception e)
{
e.printStackTrace();
return false;
}
}
public static void main(String args[])
{
System.out.println(search.search("d://t.txt","l2"));
}
}
修改了下，加两个变量，可以指出查找的位置。
import java.io.FileReader;
import java.io.BufferedReader;
import java.io.File;
public class search
{
//查找方法，参数，文件绝对路径，查找关键字
public static String search(String filepath,String key)
{
try
{
File f = new File(filepath);
FileReader fr = new FileReader(f);
BufferedReader br = new BufferedReader(fr);
String s = "";
int i = 1;
int m = 0;
while((s = br.readLine()) != null)
{
if((m = s.indexOf(key)) != -1)
{
return "第"+i+"段,第"+m+"处";
}
i++;
}
return null;
}
catch(Exception e)
{
e.printStackTrace();
return null;
}
}
public static void main(String args[])
{
System.out.println(search.search("d://t.txt","asd"));
}
}
这个，查汉字是没有问题的。
另外，你要全文检索的话，indexOf（）还有个方法，indexOf(int start,String key),指定开始查找的位置跟关键字，你查到一处后，将这个数值加1，做为继续查找的开始位置就可以了。