apr.rar_ APRIORI_apriori c++_apriori算法C_作业_简单Apriori

#include<iostream.h> #include<stdio.h> #include<string.h> #include<fstream.h> #include<stdlib.h> #define NULL 0 #define LEN sizeof(struct nod) struct nod { char element[9]; int count; struct nod *next; }; struct nod * apriori_gen(struct nod *head,int flag); int qjflag=0; void main() { int flag; //项集个数 char tid[9][8]={{'f','a','c','d','g','i','m','p'},{'a','b','c','f','l','m','o',0},{'b','f','h','j','o',0,0,0},{'b','c','k','s','p',0,0,0},{'a','f','c','e','l','p','m','n'}}; int sup=2; int k=0; int n=16; struct nod *head[2]; struct nod *p1,*p2; p1=(struct nod *) malloc(LEN); //开辟一个单元 p2=p1; p1->element[0]='a'; p1->count=0; head[0]=NULL; while (n!=0) { n--; if(n==15) head[0]=p1; else p2->next=p1; p2=p1; p1=(struct nod *)malloc(LEN); p1->element[0]=p2->element[0]+1; p1->count=0; } p2->next=NULL; int i; int j; for (i=0;i<9;i++) /////////////////////// { for (j=0;j<8;j++) { struct nod *p; p=head[0]; if(head[0]!=NULL) do { if(tid[i][j]==p->element[0]) p->count++; p=p->next; }while(p!=NULL); } } cout<<endl; cout<<"c1:"<<endl; cout<<"项集"<<" "<<"支持度"<<endl; struct nod *p; p=head[0]; if(head[0]!=NULL) do { cout<<p->element[0]<<" "<<p->count<<endl; p=p->next; }while(p!=NULL); p=head[0]; if(head[0]!=NULL) { if(head[0]->count<sup) head[0]=head[0]->next; do { if((p->next->count)<sup) p->next=p->next->next; else p=p->next; }while(p->next!=NULL); } cout<<endl; cout<<"L1:"<<endl; cout<<"项集"<<" "<<"支持度"<<endl; p=head[0]; if(head[0]!=NULL) do { cout<<p->element[0]<<" "<<p->count<<endl; p=p->next; }while(p!=NULL); int fg=1; flag=2; while(head[(flag%2)]!=NULL)//fg!=0&&qjflag==0) { fg=0; head[!(flag%2)]=apriori_gen(head[flag%2],flag); if(head[!(flag%2)]==NULL) break; p=head[!(flag%2)]; do { for(j=0;j<9;j++) //j是Tid的行数//////////////////////////// { k=0; for(k=0;k<flag;k++) //k是候选k项集 { for(i=0;i<8;i++) //i是tid的列数 { if(p->element[k]==tid[j][i]) i=9; //如果找到置i为9,否则i为8 } if(i==8) k=flag+1; } if(k==flag) p->count++; } p=p->next; }while(p!=NULL); cout<<endl; cout<<"c"<<flag<<":"<<endl; cout<<"候选集"<<" "<<"支持度"<<endl; p=head[!(flag%2)]; if(head[!(flag%2)]!=NULL) do { for(i=0;i<flag;i++) { cout<<p->element[i]<<" "; } cout<<" "<<p->count<<endl; p=p->next; }while(p!=NULL); p=head[!(flag%2)]; //-------------------------从候选集中获得频繁项集-------------------------- if(head[!(flag%2)]!=NULL) { if(head[!(flag%2)]->count<sup) head[!(flag%2)]=head[!(flag%2)]->next; do { if((p->next->count)<sup) p->next=p->next->next; else {fg=1; p=p->next; } }while(p->next!=NULL); /////////////// cant loose ->next } cout<<endl; cout<<"L"<<flag<<endl; cout<<"项集"<<" "<<"支持度"<<endl; p=head[!(flag%2)]; if(head[!(flag%2)]!=NULL) do { for(i=0;i<flag;i++) { cout<<p->element[i]<<" "; } cout<<" "<<p->count<<endl; p=p->next; }while(p!=NULL); flag++; } ; } struct nod * apriori_gen(struct nod *head,int flag) { int i,j; struct nod *headnew; //新的准备返回的头节点 struct nod *q1,*q2; //用来比较的两个项集 q1=head; struct nod *p1,*p2; //新的节点的指针 p1=(struct nod *) malloc(LEN); //开辟一个单元 p2=p1; headnew=p1; //新的头节点置好 do { q2=q1->next; do { int m=0; for(m=0;m<flag-2;m++) //比较q1 and q2中的元素 { if(q1->element[m]==q2->element[m]) ; else m=flag+1; } char element1,element2; element1=q1->element[flag-2]; element2=q2->element[flag-2]; int l; l=element1-element2; if(flag==2||(m==(flag-2)&&(l<0))) //若满足相等条件，连接q1 q2 { int i=0; for(i=0;i<flag-1;i++) { p1->element[i]=q1->element[i]; p1->count=0; } p1->element[flag-1]=q2->element[flag-2]; } q2=q2->next; p1=(struct nod *)malloc(LEN); p2->next=p1; p2=p1; p2->next=NULL; }while (q2!=NULL); q1=q1->next; }while (q1->next!=NULL); //－－－－－－－－－－－开始剪枝－－－－－－－－－－－－－－－－－－－－－－ q1=q2=headnew; do { i=0; for( i=0;i<flag&&q2!=NULL;i++) //比较时去掉的元素 { p1=head; //p1指向老head for(j=0;j<flag&&p1!=NULL;j++) { if(j<i) { if(p1->element[j]==q2->element[j]) ; else { p1=p1->next; j=0;} } else if(j==i) ; else if(j>i) { if(p1->element[j-1]!=q2->element[j]) {p1=p1->next; j=0; } } } if((p1==NULL)||(j!=flag)) { i=0; if(q2==headnew) { headnew=headnew->next; q1=headnew; q2=headnew; } else { q1->next=q2->next; q2=q2->next; } } } if((p1!=NULL)&&(i==flag)) { if(q2==headnew) { q2=q2->next;} else { q1=q1->next; q2=q2->next; } } }while (q2!=NULL); cout<<endl; cout<<"c"<<flag<<":"<<endl; cout<<"剪枝后项集"<<" "<<endl; struct nod *p; p=headnew; if(headnew==NULL) return NULL; else { do { i=0; for(i=0;i<flag;i++) { cout<<p->element[i]<<" "; } cout<<endl; p=p->next; }while(p!=NULL); } return headnew; }