fp-growth.cpp

FP-TREE算法

#include"stdio.h"
#include"stdlib.h"
#include "string.h"
//#define N 5 
#include <vector>
#include <iostream.h>
#include <algorithm>
using namespace std;                       //总共字符个数
typedef struct node
{
	char ch;
	int count;
	struct node *left,*right;
}node,*bitree;
typedef struct tnode
{
	char name;
	int count;
}Tnode;
vector <Tnode> T1;
//vector <Tnode> T2;
//int sort[2][N],counter=0;         //排序使用

int search(bitree root,char ch,bitree *p)//在二叉排序数中(*root指向树的根节点)，若找到令p指向该节点并返回0
{//否则令p指向该节点并返回-1
	int compress=0;
	bitree ptr;
	*p=NULL;
	ptr=root;
	while(ptr)
	{
		compress=(ptr->ch)-ch;
		if(compress==0)
		{
			*p=ptr;
			return 0;
		}//查找成功，令p指向该节点，返回0
		else 
		{
			*p=ptr;
			ptr=compress>0?ptr->left:ptr->right;
			
		}
		
	}//while
	return -1;//查找失败
	
}//search
int insert(bitree *t,char ch)
{
	bitree p,s;
	if(search(*t,ch,&p)==-1)
	{//找不到ch
		s=(node *)malloc(sizeof(node));
		if(!s)
		{
			printf("储存分配失败！\n");
			return -1;
		}
		s->left=NULL;
		s->right=NULL;
		s->ch=ch;
		s->count=1;
		if(p==NULL)
			*t=s;//ch是第一个出现的字符，令s作为根节点
		else if(p->ch<ch)
			p->right=s;
		else p->left=s;
	}//end if
	else p->count++;
	return 0;
}
void inorder(bitree &root)//中序遍历root指向根的二叉树
{
	Tnode temp;
	if(root)
	{
		inorder(root->left);
		{
			printf(" %c (%d)\n",root->ch,root->count);
			temp.name=root->ch;
			temp.count=root->count;
			T1.push_back(temp);
		}
		inorder(root->right);
	}
	
}
bool comp(const Tnode &p1,const Tnode &p2)
{
	return p1.count>p2.count;
}

sort1()//将A文件的按count的将序排序并写入B文件
{
	int temp,k=0;

	char c,bb[5];
//	Tnode pre;
/*	for(int i=0;i<N;i++)      //将其按count排序
		for(int j=i+1;j<N;j++)
			if(sort[1][i]<sort[1][j]){temp=sort[1][i];sort[1][i]=sort[1][j];sort[1][j]=temp;temp=sort[0][i];sort[0][i]=sort[0][j];sort[0][j]=temp;}
			printf("The order is:\n");//将排序好的输出(隐含着编码过程即count最大的编码为1次大的为2依类推...)
			for(i=0;i<N;i++) printf(" %c (%d) \n",sort[0][i],sort[1][i]);*/
			FILE *fp,*fp1;            //定义文件指针(包括读与写)
			fp=fopen("a.txt","r");
			if(!fp) 
			{printf("open file error\n");return -1;}
			fp1=fopen("b.txt","w");   //打开B文件,准备将结果写入
			if(!fp1) 
			{printf("open file error\n");return -1;}
			while(!feof(fp))
			{
				c=fgetc(fp);
				if(c>='a'&&c<='z')	
				{
					for(int j=0;j<T1.size();j++) 
						if(c==T1[j].name) 
							bb[k++]=j;
				}//编码
				if(c=='\n') {
					for(int i=0;i<k;i++)//将编码后的数据排序
						for(int j=i+1;j<k;j++)
							if(bb[i]>bb[j]){temp=bb[i];bb[i]=bb[j];bb[j]=temp;}
							for(i=0;i<k;i++) fputc(T1[bb[i]].name,fp1);//反编码,并写入文件
							fputc('\n',fp1);
							k=0;
				}
				
			}			
			fclose(fp);
			fclose(fp1);
			return 0;
}

int main()
{
				FILE* fp;
				char c;
				int row=0;
				bitree root=NULL;
				int N=T1.max_size();
			//	int bb[N];
			//	char s[T1.size]=NULL;
				fp=fopen("a.txt","r");
				if(!fp) 
				{printf("open file error\n");return -1;}
				while(!feof(fp))
				{
					c=fgetc(fp);
					if(c=='\n') row++;
					printf("%c",c);
					if(c>='a'&&c<='z')	insert(&root,c);
				
				}
				row=row+1;
				fclose(fp);
				printf("\nrow = %d\n",row);
				inorder(root);
				sort (T1.begin(),T1.end(),comp);
				printf("按出现的次数排列为：\n");
				for(int i=0;i<T1.size();i++)
				{
					printf(" %c <%d>\n",T1[i].name,T1[i].count);
				
				}
				sort1();     //调用文件正序函数
				FILE *fp2;
				fp2=fopen("b.txt","r");
				while(!feof(fp2))
				{
					c=fgetc(fp2);
					printf("%c",c);	
				}
				fclose(fp2);
				
				return 0;
}