second.cpp

创建FP-Tree树的过程。从.txt文件中读取字符型数据

//#include<iostream.h>
#include<stdio.h>
#include<fstream.h>
#include<istream.h>
#include<stdlib.h>
#include <vector>
#include<iostream>
using namespace std;

int count=0;
char  *trans[10];

typedef struct BSTNode
{
	char name;
	int count;
	BSTNode *lchild,*rchild;
} BSTNode;
typedef struct FPTNode
{
	char name;
	int count;
	FPTNode *next;
	FPTNode	*parent;
} FPTNode;
typedef struct node
{
	char name;
	int count;
	FPTNode *link;
} TNode;

vector<TNode> T;
vector<TNode> N;	//存储排序后的频繁一项集

typedef vector<char> Tran;		//存储排序后的频繁一项集

//vector<Tran> VecDB;		//存储整个排序后的数据库
//vector<char> trans;



/*
typedef struct HTNode
{
	char name;
	int count;
	int length;
	FPTNode *link;
} HTNode;

*/
void InsertBST(BSTNode *&Tptr,char ch)
{                                                  //若二叉排序树 *Tptr中没有关键字为ch，则插入，否则直接返回
	BSTNode *p;
	
	if (Tptr == NULL) 
	{
		p= new BSTNode;//(BSTNode *)malloc(sizeof(BSTNode));
        p->name = ch; 
		p->count=1;
		p->lchild=p->rchild=NULL;
		Tptr = p;
		
	}//p的初值指向根结点
	else if (Tptr->name == ch) 
	{
		Tptr->count++;  
		
	}
	else if(Tptr->name < ch)
	{
		InsertBST(Tptr->lchild,ch);
	}
	else
	{
		InsertBST(Tptr->rchild,ch);
	}
	
} 


void Input(char *name,BSTNode *&p)
{
	FILE *f;
	char ch;
	
	int row=0;
	f = fopen(name,"r");
	if(f == NULL)
	{
		std::cout<<"打开文件错误"<<endl;
	}
	else
	{
		ch=fgetc(f);
		while (ch != EOF)//!feof(f))
		{
			
			printf("%c",ch); 
			
			if('\n' == ch)row++;			
			else InsertBST(p,ch);
			ch=fgetc(f);
			
		}
		printf("\n");
		
	}
	fclose(f);
	
}
//InsertBST

/*重新扫描数据库，对一项频繁集按照支持度降序排列*/

void sort(vector<TNode> & T)	
{
	TNode temp;
	TNode tmp;
	for(int i = 0;i < T.size()-1;i++)
		for(int j = i+1;j < T.size();j++)
		{			
			if(T[j].count > T[i].count)
			{
				temp = T[i];
				T[i] = T[j];
				T[j] = temp;
			}
		}
		
		for( i = 0;i < T.size();i++)
		{
			T[i].link =NULL;
			tmp.name =	T[i].name;
			tmp.count = T[i].count;
			tmp.link =T[i].link ;
			N.push_back(tmp);             //一项集排序后存储在 TNode N
		//	N[i].num = i;
			printf("%c %d\n",N[i].name,N[i].count);
		//	
		}
		//	printf("%c ",s[0][i]);
		printf("\n");
}

	
	

//中序遍历排序二叉树，输出每个节点的支持度
void DispBST(BSTNode *bt)   //输出排序二叉树节点的支持度
{
	
	if (bt != NULL)
	{ 
		TNode tmp;		
		DispBST(bt->lchild);     //递归处理左子树
		
		printf("%c,%d\n",bt->name,bt->count);
		tmp.name = bt->name;
		tmp.count = bt->count;
		T.push_back(tmp);
	//	List(bt->name,bt->count);
		//	if (bt->rchild!=NULL)	
		DispBST(bt->rchild);    //递归处理右子树
		//	}
	}
}


//对整个数据库进行排序
char *sortf(vector<TNode> & N,char * trans)
{
	FILE *f;
	f = fopen("a.txt","w");
	if (f == NULL)
	{
		printf("f输入错误");
	}

	char *result=new char;	
	int k=0;
	for(int j = 0; j < N.size (); j++)
	{
		int i=0 ,flag=0;
		
		while (trans[i] != NULL)
		{
			if (N[j].name == trans[i]) 
			{
				flag=1;
				break;
			}
			else
			{
				i++;
			}
		}
		if (flag == 1)
		{	
		
			result[k]=trans[i];
		//	printf("%c",result[k]);
		//	fputc(result[k],f);
			k++;
		
		}	
	}
	result[k]='\0';
	return result;
}	
/*	
	char t;
	int b[10];
	for(int i = 0;i < trans.size () ;i++)
		for(int j = 0;j < N.size ();j++)
	{ 
		if(trans[i] == N[j].name)b[i] = N[j].num;
		}
		for(i = 0;i < trans.size ()-1;i++)
			for(int j = i+1;j < trans.size ();j++)
			{
				if(b[i] > b[j])
				{
					t = b[i];
					b[i] = b[j];
					b[j] = t;
				}
			}
			for(i = 0;i < trans.size ();i++)
					for( int j = 0;j < N.size ();j++)
					{
						if(b[i] == N[j].num)
							printf("c%",N[j].name);
					}	
*/

void createFP(char *s,vector<TNode> & N,FPTNode *root)
{
	FPTNode *croot,*p,*q;
	int index = 0; 
//	root = new FPTNode;
//	root = NULL;
	croot = root;
	while(s[index] != '\0')
	{
		for(int i = 0;i < N.size ();i++)
		{
			if(N[i].name == s[index])
			{
				p = N[i].link;
				//		p->next = NULL;
				break;
			}
		}
		
		if (p == NULL)//头节点链为空，创建新节点，并更新当前根节点
		{
			p = new FPTNode;
			p->name = s[index];
			p->count = 1;
			p->next = NULL;
			p->parent = croot;
			N[i].link = p;
			croot = p;
			index++;
		}
		else
		{
			while(p->parent != croot && p->next != NULL)//节点链不为空，指向节点链next
			{
				p = p->next ;
			}
			if(p->parent == croot)//父节点与当前根节点相同，则个数增加1，且更新当前根结点
			{ 
				p->count++;
				croot = p ;
				index++;
//				continue;
			}
			else           //父节点与当前根节点不同则创建新的节点指向当前根节点，并更新当前根节点
			{
				q = new FPTNode;
				q->parent = croot;
				q->next = NULL;
				q->count = 1;
				q->name = s[index] ;
				p->next = q;
				croot = q;	
				index++;		
			}
		}
	}
}



void Transaction(	char **str)
{
	FILE *f;
    int i = 0;
	char temp[10];
//FPTNode *fp;
	//	char tmp;
	//	char ch;
	f = fopen("test.txt","r");
	if (f == NULL)
	{
		printf("排序打开文件错误");
	}
	else
	{ 
		while(!feof(f))
		{
			fgets(temp,10,f);
			// printf("\n");
			//if(temp[i] == '\n'){}
		   str[i] = sortf(N,temp);
		  
		   printf("%s\n",str[i]);
			//printf("\n");	
		    FPTNode *root;
			root = NULL;
		   	createFP(str[i],N,root);
			i++;
		
		}
	}
	fclose(f);
}
void Output()
{
	FPTNode *fp,*n;
	for(int i = 0;i < N.size ();i++)
	{
		n = N[i].link;
		while (n!=NULL) 
		{
			fp=n;
			while (fp != NULL)
			{
				printf("%c,支持度：%d\n",fp->name,fp->count);
				fp=fp->parent;
				
			}printf("\n");
		n=n->next;
		}
	}
}
/*

void Transaction()
{
	FILE *stream;
	FILE *f;
	//	char **str;
	f = fopen("a.txt","w");
	if (f == NULL)
	{
		printf("f输入错误");
	}
	stream = fopen("test.txt","r");
	if (stream == NULL)
	{
		printf("输入错误");
	}
	else
	{ 
		int i = 0; 
		int j = 0;
		int k = 0;
		int temp;	  //	char *temp=new char;
		char ch;
		char b[6];
		while(!feof(stream))
		{
			
			ch = fgetc(stream);	
			if(ch >= 'a' && ch <= 'z')
			{
				for(int j = 0;j < 6;j ++) 
					if(ch == s[0][j]) 
					{
						
						b[k] = j;
						k++;
					}
					
			}
			if(ch == '\n')
			{
				std::cout<<endl;
				for(int i = 0;i < k;i++)
					for(int j = i+1;j < k;j++)
						if(b[i] > b[j])
						{
							temp = b[i];
							b[i] = b[j];
							b[j] = temp;
						}
						for(i = 0;i < k;i++) 
						{
							fputc(s[0][b[i]],f);							
						}
						k = 0;
						fputc('\n',f);
			}//	sort(T,temp);
		}
		//	Creatfp();
		
	}
	fclose(stream);		
	fclose(f);	
	
}



void Insertfp(char ch)
{
	FPTNode *p,*croot;
	HTNode *h;
	h=new HTNode;
	croot = new FPTNode;
	for(int i = 0;i < 6;i++)
	{
		//	std::cout<<s[0][i];
		if( s[0][i] == ch )
		{
			h->name = ch;
			p = h->link ;
			break;
		}
	}
	if(p == NULL)
	{
		p = new FPTNode;
		p->name = s[0][i] ;
		p->count = 1;
		p->next = NULL;
		p->parent = croot;
		h->link = p ;
	}
	else
	{
		FPTNode *pre,*current;
		current = croot;
		while(p != NULL)
				
		{
			if(p->parent->name == croot->name && p->parent->name != NULL)  //根节点与当前根节点相同且根节点不为空，
			{
				p->parent = p->parent->parent;
				croot = croot->parent ;
				p->count++;
			}
			else if(p->parent->name == croot->name && p->parent->name == NULL)
			{ 
				p->count++;
				break;
			}
			else 
			{
			pre = p;
			p = p->next;
			}
		}
		if(p == NULL)
		{
			p = new FPTNode;
			p->name = ch;
			p->count = 1;
			p->parent = current;
			p->next = NULL;
			pre->next = p;
		}
	}
}

*/
			


	



void main()
{
	BSTNode *Bt;
   
	Bt = NULL;//(BSTNode*)malloc(sizeof(BSTNode));
			 /*Bt->name=NULL;
			 Bt->count=0;
			 Bt->lchild=NULL;
	Bt->rchild=NULL;*/
	Input("test.txt",Bt);
	
    DispBST(Bt);
	printf("\n");
	
	sort(T);

//	char *temp;
//	temp = new char[];
   Transaction(trans);
//	std::cout<<s[0][2];
//	creatFP();
 
   Output();


	

}