//***********************************************//
// 程序編寫者：wentrue
// 編譯環境：VC7.0，控制臺程序
// 關于本程序的任何問題或意見，可聯系本人：wentrue@mail.ustc.edu.cn
//***********************************************//
#pragma once

#include "resource.h"

typedef struct tagDBLink{     //數據庫元組數據鏈表
	CString datastr;          //關鍵字記錄串元組
	struct tagDBLink *next;   //下一串指針
}DBLink;

typedef struct tagSearchTree{    //1-項集搜索樹
	CString datastr;             //節點存儲的關鍵字
	WORD count;                  //該關鍵字出現次數
	struct tagSearchTree *left;  //左子樹指針
	struct tagSearchTree *right; //右子樹指針
}SearchTree;

typedef struct tagItemSet{    //K-項集鏈表
	CString datastr;          //節點存儲的關鍵字
	WORD count;               //該關鍵字出現的次數
	struct tagItemSet *next;  //下一節點的指針
}ItemSet,ItemSetLink,ItemSetNode;

SearchTree* find_frequent_1_itemset(DBLink* D,int min_count);   //從數據庫元組數據鏈表中，發現頻繁1-項集 
ItemSet* find_frequent_k_itemset(DBLink* D,ItemSet* IS,int k,int min_count);    //掃描數據集發現k-項集
ItemSetLink* apriori_gen(ItemSet* IS,int k);    //根據頻繁k-1項集鏈表IS產生候選k-項集鏈表
BOOL has_infrequent_subset(CString str,ItemSet* IS);    //搜索候選k-項集中k-1項集不頻繁的元素
BOOL FindInTree(SearchTree* ST,CString str);    //在二叉搜索樹中搜索指定關鍵字
ItemSetNode* GetDataLink(SearchTree* ST);     //把二叉搜索樹中的結點按升序讀取出來組成鏈表
SearchTree* SearchAndAddInTree(SearchTree* ST,CString str,int k);    //在給定的搜索二叉樹中搜索指定的字符串(中序)，并增加計數
ItemSet* SearchAndAddIn_kLink(ItemSetLink* IS,CString str);   //生成k-項頻繁集候選集的搜索二叉樹
SearchTree* SearchAndDelInTree(SearchTree* ST,int min_count);    //在給定的搜索二叉樹中剔除掉出現次數低于min_count的結點
SearchTree* FindMin(SearchTree* ST);      //在ST中搜索最小的元素
SearchTree* DeleteNode(SearchTree* ST,CString str);     //在ST中搜索關鍵字為str的節點并刪除
CString GetLine(CFile* const f);    //從文件中讀出一行字符
DBLink* ReadDataFromText(CString filename,int *RC);     //從TXT文件中讀入數據
void PrintResult(ItemSet* IS,int k,CString exstr1);     //輸出頻繁集結果
//BOOL CompareKeyInStr(CString str1,CString str2);    //在str1的關鍵字組中尋找str2的關鍵字是否都出現
ItemSetLink* CreatePreItemSet(ItemSetLink* preIS,CString str,int k);     //構建候選頻繁k項集鏈表
ItemSetLink* DeleteLink(ItemSetLink* IS);    //釋放鏈表IS的內存空間
ItemSet* Del_k_ItemSet(ItemSet* IS,int min_count);     //在已計數好的ItemSet中刪除非頻繁節點
SearchTree* DeleteTree(SearchTree* ST);    //釋放二叉樹節點