3NF的求解出错
#include "属性的头文件.h"Status rightSingle(LinkList &R)
{//把一个关系模式的分解右部分解成单属性
Link p=R.head->next;
HString nsub,fsub;//fsub,nsub分别表示函数依赖的前件和后件
HString Stemp;//用于表示每次分解nsub后的一个字符
HString Stemp2;//Stemp2表示函数依赖的前件和依赖符号的字符串
InitString(nsub);
InitString(fsub);
InitString(Stemp);
InitString(Stemp2);
int i;
while(p)
{
divide(p->data,fsub,nsub);//分割函数依赖字符串
if(StrLength(nsub)>=2)
{
Link q=p;
for(i=1;i<=StrLength(nsub);i++)
{//创建nsub.length个结点
Link s;
SubString(Stemp,nsub,i,1);//从函数依赖的右边取一个字符
//Stemp2表示函数依赖的前件和依赖符号的字符串
SubString(Stemp2,p->data,1,StrLength(fsub)+2);//依赖符号"->"占两个字节
connectString(Stemp2,Stemp);//连接字符,形成新的函数依赖字符串形式
MakeNode(s,Stemp2);//创建表结点
InitString(s->data);//初始表结点的data域
StrCopy(s->data,Stemp2);//给data域赋值
InsAfter(R,p,s);//在插入结点s,p指向插入新的结点
}//for
ListDelete_L(R,q);//删除依赖右边为多属性的结点
}//if
p=p->next;
}//while
return OK;
}
Status deleteFD(LinkList &R)
{//删除多余的函数依赖
Link p=R.head->next,q;
HString nsub,fsub;//fsub,nsub分别表示函数依赖的前件和后件
InitString(nsub);
InitString(fsub);
while(p)
{
q=PriorPos(R,p);//q指向p的前驱
ListDelete(R,p);//从关系模式R中移除结点p
divide(p->data,fsub,nsub);//分割函数依赖字符串
if(isSubGather(package(fsub,R),nsub))
{//判断函数依赖的后件是否属于前件属性集的闭包
//若成立则删除该结点 the key
free(p);
p=q;
}
else//不成立把该结点从新链回去
{p->next=q->next;
q->next=p;
R.len++;
}
p=p->next;
}
return OK;
}
Status deleteP(LinkList &R)
{//删除函数依赖右边的的多余属性
Link p=R.head->next;
HString nsub,fsub;//fsub,nsub分别表示函数依赖的前件和后件
HString Stemp,Stemp2;
InitString(nsub);
InitString(fsub);
InitString(Stemp);
InitString(Stemp2);
int i;
while(p)
{
divide(p->data,fsub,nsub);//分割函数依赖字符串
StrCopy(Stemp,fsub);
for(i=1;i<=StrLength(Stemp);i++)
{//依次检查函数依赖的右边属性是否多余
StrDelete(Stemp,i,1);
if(isSubGather(package(Stemp,R),nsub))
{
StrCopy(fsub,Stemp);
i=1;//i=1表示当删除右边的一个属性后又从头扫描右边的多余属性
}
else StrCopy(Stemp,fsub);
}
//Stemp2表示函数依赖的前件和依赖符号的字符串
HString op;
InitString(op);
StrAssign(op,"->");
connectString(Stemp,op); //连接函数以依赖的前件和函数依赖的符号
connectString(Stemp,nsub); //连接字符,形成新的函数依赖字符串形式
StrCopy(p->data,Stemp); //用新的函数依赖替代原来的函数依赖
p=p->next;
}
return OK;
}
Status minFD(LinkList &R)
{
if(!rightSingle(R)) return ERROR;
if(!deleteFD(R)) return ERROR;
if(!deleteP(R)) return ERROR;
return OK;
}
Status printRList(LinkList R)//输出R中的关系模式。
{
Link p=R.head->next;
while(p)
{
StrPrint(p->data);
p=p->next;
}
return OK;
}
//串的堆分配基本操作头文件.h
#include <string.h>
#include <ctype.h>
#include <malloc.h> //malloc()等
#include <limits.h> // INT_MAX等
#include <stdio.h> // EOF(=^Z或F6),NULL
#include <stdlib.h> // atoi()
#include <io.h> // eof()
#include <math.h> // floor(),ceil(),abs()
#include <process.h> // exit()
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
// #define OVERFLOW -2 因为在math.h中已定义OVERFLOW的值为3,故去掉此行
typedef int Status; // Status是函数的类型,其值是函数结果状态代码，如OK等
typedef int Boolean; // Boolean是布尔类型,其值是TRUE或FALSE
//串的堆分配存储
typedef struct
{ char *ch; // 若是非空串,则按串长分配存储区,否则ch为NULL
int length; // 串长度
}HString;
//串的堆分配基本操作
Status StrAssign(HString &T,char *chars)
{//生成一个其值等于串常量chars的串T
int i,j;
if(T.ch) free(T.ch); // 释放T原有空间
i=strlen(chars); // 求chars的长度i
if (!i) // chars的长度为0
{T.ch=NULL; T.length=0; }
else // chars的长度不为0
{ T.ch=(char*)malloc(i*sizeof(char)); //分配串空间
if (!T.ch) exit(OVERFLOW); // 分配串空间失败
for (j=0; j<i; j++) T.ch[j]=chars[j]; //拷贝串
T.length=i;
}
return OK;
}
Status StrCopy(HString &T,HString S)
{ // 初始条件:串S存在。操作结果: 由串S复制得串T
int i;
if (T.ch) free(T.ch); // 释放T原有空间
T.ch=(char*)malloc(S.length*sizeof(char)); // 分配串空间
if (!T.ch) exit(OVERFLOW); // 分配串空间失败
for (i=0; i<S.length; i++) T.ch[i]=S.ch[i]; //拷贝串
T.length=S.length;
return OK;
}
Status StrEmpty(HString S)
{ //初始条件: 串S存在。操作结果: 若S为空串,则返回TRUE,否则返回FALSE
if (S.length==0&&S.ch==NULL) return TRUE;
else return FALSE;
}
int StrCompare(HString S,HString T)
{ // 若S>T,则返回值>0;若S=T,则返回值=0;若S<T,则返回值<0
int i;
for (i=0; i<S.length&&i<T.length; ++i)
if (S.ch[i]!=T.ch[i]) return S.ch[i]-T.ch[i];
return S.length-T.length;
}
int StrLength(HString S)
{ // 返回S的元素个数,称为串的长度
return S.length;
}
Status ClearString(HString &S)
{ // 将S清为空串
if (S.ch)
{free(S.ch); S.ch=NULL; }
S.length=0;
return OK;
}
Status Concat(HString &T,HString S1,HString S2)
{ // 用T返回由S1和S2联接而成的新串
int i;
if (T.ch) free(T.ch); // 释放旧空间
T.length=S1.length+S2.length;
T.ch=(char *)malloc(T.length*sizeof(char));
if (!T.ch) exit(OVERFLOW);
for (i=0; i<S1.length; i++) T.ch[i]=S1.ch[i];
for (i=0; i<S2.length; i++) T.ch[S1.length+i]=S2.ch[i];
return OK;
}
Status SubString(HString &Sub, HString S,int pos,int len)
{ // 用Sub返回串S的第pos个字符起长度为len的子串
// 其中,1≤pos≤StrLength(S)且0≤len≤StrLength(S)-pos+1
int i;
if (pos<1||pos>S.length||len<0||len>S.length-pos+1) return ERROR;
if (Sub.ch) free(Sub.ch); // 释放旧空间
if (!len) // 空子串
{ Sub.ch=NULL; Sub.length=0; }
else // 完整子串
{ Sub.ch=(char*)malloc(len*sizeof(char));
if (!Sub.ch) exit(OVERFLOW);
for (i=0; i<=len-1; i++) Sub.ch[i]=S.ch[pos-1+i];
Sub.length=len;
}
return OK;
}
void InitString(HString &T)
{ // 初始化(产生空串)字符串T
T.ch=NULL; T.length=0;
}
int Index(HString S,HString T,int pos) // 算法4.1
{ // T为非空串。若主串S中第pos个字符之后存在与T相等的子串,
// 则返回第一个这样的子串在S中的位置,否则返回0
int n,m,i; HString sub;
InitString(sub);
if (pos>0)
{ n=StrLength(S); m=StrLength(T);
i=pos;
while (i<=n-m+1)
{ SubString(sub,S,i,m);
if (StrCompare(sub,T)!=0) ++i; else return i;
}
}
return 0;
}
Status StrInsert(HString &S,int pos,HString T) // 算法4.4
{ // 1≤pos≤StrLength(S)+1。在串S的第pos个字符之前插入串T
int i;
if (pos<1||pos>S.length+1) return ERROR; // pos不合法
if (T.length) // T非空,则重新分配空间,插入T
{ S.ch=(char*)realloc(S.ch,(S.length+T.length)*sizeof(char));
if (!S.ch) exit(OVERFLOW);
for (i=S.length-1; i>=pos-1; --i) // 为插入T而腾出位置
S.ch[i+T.length]=S.ch[i];
for(i=0;i<T.length;i++) S.ch[pos-1+i]=T.ch[i]; // 插入T
S.length+=T.length;
}
return OK;
}
Status StrDelete(HString &S,int pos,int len)
{ // 从串S中删除第pos个字符起长度为len的子串
int i;
if(S.length<pos+len-1) exit(ERROR);
for (i=pos-1; i<=S.length-len; i++) S.ch[i]=S.ch[i+len];
S.length-=len;
S.ch=(char*)realloc(S.ch,S.length*sizeof(char));
return OK;
}
Status Replace(HString &S,HString T,HString V)
{ /* 初始条件: 串S,T和V存在,T是非空串（此函数与串的存储结构无关） */
/* 操作结果: 用V替换主串S中出现的所有与T相等的不重叠的子串 */
int i=1; // 从串S的第一个字符起查找串T
if (StrEmpty(T)) return ERROR; // T是空串
do
{ i=Index(S,T,i); /* 结果i为从上一个i之后找到的子串T的位置 */
if (i) /* 串S中存在串T */
{StrDelete(S,i,StrLength(T)); /* 删除该串T */
StrInsert(S,i,V); /* 在原串T的位置插入串V */
i+=StrLength(V); /* 在插入的串V后面继续查找串T */
}
}while(i);
return OK;
}
void DestroyString()
{ /* 堆分配类型的字符串无法销毁 */ }
void StrPrint(HString T)
{ // 输出字符串T.
int i;
for (i=0; i<T.length; i++) printf("%c",T.ch[i]);
printf("\n");
}
#define TRUE 1
#define FALSE 0
#include<string.h>
#include<stdio.h>
#include<stdlib.h>
#include<iostream.h>
#include"串的头文件.h"
typedef HString ElemType;//定义链表的数据元素为HString类型
#include"表的头文件.h"
typedef int Status;
//关系模式用动态单链表表示
//链表的头结点的数据域存放关系模式的属性集
//表结点的数据域表示以一个函数依赖
Status CreateRMode(LinkList &L) //创建关系模式
{//创建关系模式的属性集和函数依赖集
//链表的头结点的数据域存放关系模式的属性集
HString Stemp;
InitString(Stemp);
char p[20];
int num;
cout<<"请输入关系模式的属性集"<<endl;
gets(p);
StrAssign(Stemp,p);
InitString(L.head->data);
StrCopy(L.head->data,Stemp);//头结点的数据域存放关系模式的属性集
cout<<"请输入关系模式函数依赖集的个数:";
cin>>num;
Link s,q=L.head;
for(int i=1;i<=num;i++)
{ //依次把函数依赖加入链表
cout<<"请输入第"<<i<<"个函数依赖(例A->B)"<<endl;
gets(p);
StrAssign(Stemp,p);
MakeNode(s,Stemp);//创建表结点
InitString(s->data);//初始表结点的data域
StrCopy(s->data,Stemp);//给data域赋值
InsAfter(L,q,s);//加入函数依赖结点,p已指向s.
}
return OK;
}
void printRMode(LinkList R)
{//显示关系模式的属性集和函数依赖集
Link p=R.head->next;
cout<<"关系模式的属性集为"<<endl;
StrPrint(R.head->data);
cout<<"关系模式的函数依赖集为"<<endl;
while(p)
{
StrPrint(p->data);
p=p->next;
}
}
Status isSubGather(HString str,HString substr)
{//判断substr字符串所包含的字符是否为str所包含字符的子集
//如果是则返回TRUE,否则返回FALSE
HString stemp;
InitString(stemp);
int k=StrLength(substr);//求substr的长度
int h=StrLength(str);
if(k>h) return FALSE;
int i=1;
for(;i<=k;)
{
SubString(stemp,substr,i,1);//从substr中取一个字符放到stemp中
//用stemp返回串Substr的第i个字符起长度为1的子串
if(Index(str,stemp,1))//从字符串substr的第一个字符起与字符串str比较
i++;
else
break;
}
if(i==k+1) //i==k+1表示substr每一个字符都在字符串str中
return TRUE;
else
return FALSE;
}
Status equal(HString str1,HString str2)
{//判断两个字符串所包含的字符集是否相同
if(isSubGather(str1,str2)&&isSubGather(str2,str1))
return TRUE;
else return FALSE;
}
Status connectString(HString &S1,HString S2)
{//把字符串S2连接到S1后面 ,用S1返回连接后的字符串
HString S;
InitString(S);
Concat(S,S1,S2);//连接字符串,用S返回S1和S2相连接的串
StrCopy(S1,S);//用S1表示连接后的字符串
return OK;
}
Status divide(HString S,HString &fsub,HString &nsub)//分割字符串函数
{//把S代表的函数依赖关系的字符串,分割成依赖关系的前件fsub字符
//和依赖关系的后件nsub字符
int i;
HString op;//op表示函数依赖的符号
InitString(op);
StrAssign(op,"->");//设函数依赖的符号op为"->"
i=Index(S,op,1);//取op在S中的位置
if(!SubString(fsub,S,1,i-1)) return ERROR;//分离函数依赖的前件
if(!SubString(nsub,S,i+op.length,S.length-(i+op.length)+1))//分离函数依赖的后件
return ERROR;
return OK;
}
HString package(HString S,LinkList R)
{//根据全局变量给出的关系模式的属性集和函数依赖集求出以S串代表的属性的闭包
HString Stemp,c,fsub,nsub;//fsub,nsub分别表示函数依赖前件，后件字符串的堆存储表示
int i,j;
InitString(Stemp);
InitString(c);
InitString(fsub);
InitString(nsub);
Link p=R.head->next;
int h=StrLength(R.head->data);//关系模式属性集合的长度
int k=StrLength(S);//待求属性集的长度
StrCopy(Stemp,S);
for (i=1;i<=(h-k)*R.len;i++)
{//重复扫描函数依赖扫描次数最多为(h-k)*R.len
divide(p->data,fsub,nsub); //分割函数依赖字符串
if(isSubGather(Stemp,fsub)) //如果字符串fsub是字符串Stemp的子集
for(j=1;j<=StrLength(nsub);j++)
{
SubString(c,nsub,j,1); //依次从后件中取一个元素
if(!isSubGather(Stemp,c)) //如果后件中一个元素不是Stemp的子集
connectString(Stemp,c); //则加入Stemp中
}
if(equal(Stemp,R.head->data)) break;//当S等于关系模式的全部集合退出循环
p=p->next;
if(!p) p=R.head->next;
}//for
return Stemp;
}
/*void main()
{ LinkList R;//定义关系模式R
HString S;
InitString(S);
InitList(R);
CreateRMode(R);
char p[20];
cout<<"请输入待求属性闭包的属性集"<<endl;
gets(p);
StrAssign(S,p);
cout<<"属性集"<<p<<"的闭包为";
StrPrint(package(S,R));
}*/
#include "属性的头文件.h"
Status rightSingle(LinkList &R)
{//把一个关系模式的分解右部分解成单属性
Link p=R.head->next;
HString nsub,fsub;//fsub,nsub分别表示函数依赖的前件和后件
HString Stemp;//用于表示每次分解nsub后的一个字符
HString Stemp2;//Stemp2表示函数依赖的前件和依赖符号的字符串
InitString(nsub);
InitString(fsub);
InitString(Stemp);
InitString(Stemp2);
int i;
while(p)
{
divide(p->data,fsub,nsub);//分割函数依赖字符串
if(StrLength(nsub)>=2)
{
Link q=p;
for(i=1;i<=StrLength(nsub);i++)
{//创建nsub.length个结点
Link s;
SubString(Stemp,nsub,i,1);//从函数依赖的右边取一个字符
//Stemp2表示函数依赖的前件和依赖符号的字符串
SubString(Stemp2,p->data,1,StrLength(fsub)+2);//依赖符号"->"占两个字节
connectString(Stemp2,Stemp);//连接字符,形成新的函数依赖字符串形式
MakeNode(s,Stemp2);//创建表结点
InitString(s->data);//初始表结点的data域
StrCopy(s->data,Stemp2);//给data域赋值
InsAfter(R,p,s);//在插入结点s,p指向插入新的结点
}//for
ListDelete_L(R,q);//删除依赖右边为多属性的结点
}//if
p=p->next;
}//while
return OK;
}
Status deleteFD(LinkList &R)
{//删除多余的函数依赖
Link p=R.head->next,q;
HString nsub,fsub;//fsub,nsub分别表示函数依赖的前件和后件
InitString(nsub);
InitString(fsub);
while(p)
{
q=PriorPos(R,p);//q指向p的前驱
ListDelete(R,p);//从关系模式R中移除结点p
divide(p->data,fsub,nsub);//分割函数依赖字符串
if(isSubGather(package(fsub,R),nsub))
{//判断函数依赖的后件是否属于前件属性集的闭包
//若成立则删除该结点 the key
free(p);
p=q;
}
else//不成立把该结点从新链回去
{p->next=q->next;
q->next=p;
R.len++;
}
p=p->next;
}
return OK;
}
Status deleteP(LinkList &R)
{//删除函数依赖右边的的多余属性
Link p=R.head->next;
HString nsub,fsub;//fsub,nsub分别表示函数依赖的前件和后件
HString Stemp,Stemp2;
InitString(nsub);
InitString(fsub);
InitString(Stemp);
InitString(Stemp2);
int i;
while(p)
{
divide(p->data,fsub,nsub);//分割函数依赖字符串
StrCopy(Stemp,fsub);
for(i=1;i<=StrLength(Stemp);i++)
{//依次检查函数依赖的右边属性是否多余
StrDelete(Stemp,i,1);
if(isSubGather(package(Stemp,R),nsub))
{
StrCopy(fsub,Stemp);
i=1;//i=1表示当删除右边的一个属性后又从头扫描右边的多余属性
}
else StrCopy(Stemp,fsub);
}
//Stemp2表示函数依赖的前件和依赖符号的字符串
HString op;
InitString(op);
StrAssign(op,"->");
connectString(Stemp,op); //连接函数以依赖的前件和函数依赖的符号
connectString(Stemp,nsub); //连接字符,形成新的函数依赖字符串形式
StrCopy(p->data,Stemp); //用新的函数依赖替代原来的函数依赖
p=p->next;
}
return OK;
}
Status minFD(LinkList &R)
{
if(!rightSingle(R)) return ERROR;
if(!deleteFD(R)) return ERROR;
if(!deleteP(R)) return ERROR;
return OK;
}
Status printRList(LinkList R)//输出R中的关系模式。
{
Link p=R.head->next;
while(p)
{
StrPrint(p->data);
p=p->next;
}
return OK;
}
#include"最小依赖集的头文件.h"
void Print3NF(LinkList R)
{
LinkList New[20];
Link p=R.head->next;
HString nsub,fsub;//fsub,nsub分别表示函数依赖的前件和后件
HString cmp_nsub,cmp_fsub;
InitString(nsub);
InitString(fsub);
Link cmpfirst=p->next;
Link q;
int i=0;
while(p)
{
divide(p->data,fsub,nsub);//分割i个函数依赖字符串
cmpfirst=p->next;
InitList(New[i]);
Link h=New[i].head;
while(cmpfirst)
{
divide(cmpfirst->data,cmp_fsub,cmp_nsub);//分割i后面的依赖字符。
if(equal(cmp_fsub,fsub))//若他们的前件相等。
{
q=cmpfirst;
ListDelete(R,q);//从链表中删除p指向的结点，并以p返回删除的结点
InsAfter(New[i],h,q);
free(q);
InitString(nsub);
InitString(fsub);
}
cmpfirst=cmpfirst->next;
}
i++;
ListDelete(R,q);
InsAfter(New[i],h,q);
free(q);
InitList(New[i]);
p=p->next;
}
for(int j=0;j<=i;j++)
printRList(New[i]);
}
void main()
{
LinkList R;
InitList(R);
CreateRMode(R);
printRMode(R);
minFD(R);
cout<<"与该关系模式等价的函数最小依赖集表示为:"<<endl;
printRList(R);
Print3NF(R);
}
为什么在链接时没有错，而在运行时会出现错误，请高手帮忙解决。跪求了！
