apriori.cpp

自己的课程作业

#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;
}