实现判别一个分解的无损连接分解课程设计文档.doc

资源描述

山东科技大学学生课程设计目录一设计目的……………………………………………………………..(3) 二设计要求……………………………………………………………..(4) 三设计说明……………………………………………………………..(5) 四运算结果与分析……………………………………………………...(11) 五总结…………………………………………………………………..(16) 摘要为了实现判别一个分解的无损连接分解，而编写的程序，此文档为解说此程序而编写。主要有设计目的，设计要求，设计说明，运行结果分析，和总结。以便更好的了解此程序，内容、作用、使用方法和不足。此程序因时间关系，写得较短，只在一定程度上完成了这种功能，应有不足和缺陷。只要严格按照说明使用，此程序已达到要求。为求精简，是程序不会过于复杂，对错误输入不作处理，请谨慎使用。为了节省存储空间，减少计算量，提高运算按速率，对关系的内容要求精简，属性名只许一个字母。此程序完成粗略，但至今未出现问题，关于设计，内容很容易理解。此文档对程序做了尽可能的解说。有例子说明，更易懂。关键词：无损连接分解数据存储函数设计功能测试设计总结一、设计目的 a) 用一种高级语言实现判别一个分解的无损连接性：二、设计要求 a) 按算法5.2和定理5.4实现(P190)； b) 能给出根据模式的分解形成初始表格； c) 给出根据每一个函数依赖表格的变化情况；三、设计说明 a) 数据结构设计 typedef struct Date//用于存储表格内的数据 { char name;//存储a或b int num;//存储下标，若下表为01、02等均省略0记为1、2 }; typedef struct Function//用于存储函数依赖 { char x[5],y[5]; struct Function *next; }; typedef struct Relation//用于存储关系 { char U[11];//用于存储属性组，属性名称必须为单个字母，属性组内不超过10个属性 Function F; }; Date d[10][10],d1[10][10];//用于存储n列k行的表 b) 函数设计 void showR();显示关系R的内容 void InitR();建立关系R void Initd(int n,int k);建立一张n列k行的表 int locate(char s[11],char m);查询字母m在字符串s中的位置 void showd(int n,int k);显示表中的内容 void dof(char x[5],char y[5],int k);函数依赖对表的操作 void copy(int n,int k);表的复制 int compare(int n,int k);表的比较 void InitR() { cout<<"输入U(例如'ABCDEF')"<<endl; //输入格式必须按照格式输入 cin>>R.U; char a; cout<<"输入F(例如'( AB -> C , D -> E )')"<<endl;cin>>a; //输入格式必须按照格式输入，每个单元必须用空格隔开 Function *q=&R.F; while(1) { cin>>q->x; cin>>a>>a; cin>>q->y; cin>>a; if(a==')')break; Function *p; p=new Function; q->next=p; q=q->next; } q->next=NULL; } void Initd(int n,int k) { cout<<"输入分解组(AB,AC,DEF,)"<<endl; //输入格式必须按照格式输入，最后一个‘，’不能省 int i,j; for(i=0;i<n;i++) { for(j=0;j<k;j++) { d[j][i].name='b'; d[j][i].num=j*10+i; } } char m; for(i=0;i<k;i++) { while(1) { //cout<<"====---========"<<endl; cin>>m; // cout<<"===...======="<<endl; if(m==',')break; // cout<<"======;;===="<<endl; j=locate(R.U,m); d[i][j].name='a'; d[i][j].num=j; } } } void dof(char x[5],char y[5],int k) { int a=strlen(x),b=strlen(y); int i,j,p,q; int m[5],n[5]; for(i=0;i<a;i++)m[i]=locate(R.U,x[i]);记录属性在表中的列 for(i=0;i<b;i++)n[i]=locate(R.U,y[i]); for(i=0;i<k-1;i++)寻找有相同分量的列， { for(j=i+1;j<k;j++) { for(p=0;p<a;p++){ if(d[i][m[p]].name!=d[j][m[p]].name||d[i][m[p]].num!=d[j][m[p]].num)break; } 对相同的项进行处理，若有ai则都为ai否则填上bij if(p==a) { for(q=0;q<b;q++) { if(d[i][n[q]].name=='a') {d[j][n[q]].name='a'; d[j][n[q]].num=d[i][n[q]].num; continue;} if(d[j][n[q]].name=='a') {d[i][n[q]].name='a'; d[i][n[q]].num=d[j][n[q]].num; continue;} d[j][n[q]].num=d[i][n[q]].num; } } } } } int compare(int n,int k)相同返回1否则为0 { int i,j; for(i=0;i<k;i++) { for(j=0;j<n;j++) { if(d[i][j].name!=d1[i][j].name||d[i][j].num!=d1[i][j].num)break; } if(j<n)break; } if(i<k)return 0; return 1; } c) 整体算法说明 1、建立一张n列k行的表，每一列对应一个属性，每一行对应分解中的一个关系模式。若属性Aj属于Ui，则在j列i行交叉处填上aj，否则填上bij. 2、对于每一个函数依赖做下列操作：找到Xi所对应的列中具有相同符号的那些行。考察这些行中li列的元素，若其中ai,有则全改为ai,否则全部改为blmi,m是这些行的行号最小值。应当注意的是，若某个btli被改动，那么该表的li列中凡是btli的符号均应作相应更改。对所有函数依赖都逐一进行这样的处置，称为对F一次扫描。 3、比较扫描前后，表有无变化，如有变化，返回2歩。否则算法终止。有一行成为a1a2….an。具有无损连接性，否则不具有。四、运行结果及分析例如R < U , F >, U ={ A , B , C , D , E }, F={AB->C,C->D,D->E},R的一个分解为R1( A , B , C ) , R2( C , D ) , R3( D , E ) 首先构造初始表，如表1； A B C D E a0 a1 a2 b3 b4 b10 b11 a2 a3 b14 b20 b21 b22 a3 a4 每一个函数对表进行处置得 A B C D E a0 a1 a2 a3 a4 b10 b11 a2 a3 a4 b20 b21 b22 a3 a4 输入关系的属性组U和关系的函数依赖F 图1 图2 图3 可见改变函数依赖顺序，虽然运行过程变长，但结果不变图4 此分解不是无损连接分解，最后结果中没有出现a1a2….an序列五、总结由于时间紧迫，设计内容减少，没有考虑一些边界问题，而且程序输入格式需要严格输入。而且存储空间申请很低，所以计算量很小，属性组过多不能计算。程序对错误输入和超标输入不作任何处理。但程序在一定程度上完成了判断一个分解是否为无损连接分解。 16

展开阅读全文