java內(nèi)的Collections類自帶了一個shuffle洗牌算法。
創(chuàng)新互聯(lián)建站是一家專業(yè)提供嘉善企業(yè)網(wǎng)站建設(shè),專注與成都網(wǎng)站設(shè)計(jì)、成都做網(wǎng)站、外貿(mào)網(wǎng)站建設(shè)、HTML5、小程序制作等業(yè)務(wù)。10年已為嘉善眾多企業(yè)、政府機(jī)構(gòu)等服務(wù)。創(chuàng)新互聯(lián)專業(yè)網(wǎng)站建設(shè)公司優(yōu)惠進(jìn)行中。
static void shuffle(List? list)
使用默認(rèn)隨機(jī)源對指定列表進(jìn)行置換。
static void shuffle(List? list, Random rnd)
使用指定的隨機(jī)源對指定列表進(jìn)行置換。
現(xiàn)在你可以把52張牌放進(jìn)一個List里，調(diào)用他的shuffle算法打亂順序。
import java.awt.*;
import java.awt.event.*;
import javax.swing.*;
import java.io.*;
import java.security.*;
import javax.crypto.*;
import javax.crypto.spec.*;
/**
文件名：FileEncrypter.java
JDK：1.40以上
說明：文件加密
加密方法：三重DES加密
加密過程：對選中的文件加密后在同文件夾下生成一個增加了".tdes"
擴(kuò)展名的加密文件
解密過程：對選中的加密文件（必須有".tdes"擴(kuò)展名）進(jìn)行解密
*/
public class FileEncrypter extends JFrame{
public static final int WIDTH = 550;
public static final int HEIGHT = 200;
public static void main(String args[]) {
FileEncrypter fe = new FileEncrypter();
fe.show();
}
FileEncrypter(){
this.setSize(WIDTH,HEIGHT);
this.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
this.setResizable(false);
Toolkit tk = Toolkit.getDefaultToolkit();
Dimension screenSize = tk.getScreenSize();
this.setLocation((screenSize.width - WIDTH)/2,
(screenSize.height - HEIGHT)/2);
this.setTitle("文件加密器(TriDES)");
Container c = this.getContentPane();
c.setLayout( new FlowLayout());
final FilePanel fp = new FilePanel("文件選擇");
c.add(fp);
final KeyPanel pp = new KeyPanel("密碼");
c.add(pp);
JButton jbE = new JButton("加密");
c.add(jbE);
jbE.addActionListener(new ActionListener(){
public void actionPerformed(ActionEvent event){
File file = new File(fp.getFileName());
if (file.exists())
encrypt(file.getAbsoluteFile(),pp.getKey());
else
JOptionPane.showMessageDialog(
null,"請選擇文件！","提示",JOptionPane.OK_OPTION);
}
});
JButton jbD = new JButton("解密");
c.add(jbD);
jbD.addActionListener(new ActionListener(){
public void actionPerformed(ActionEvent event){
File file = new File(fp.getFileName());
if (file.exists())
decrypt(file.getAbsoluteFile(),pp.getKey());
else
JOptionPane.showMessageDialog(
null,"請選擇文件！","提示",JOptionPane.OK_OPTION);
}
});
}
/**
加密函數(shù)
輸入：
要加密的文件，密碼（由0-F組成，共48個字符，表示3個8位的密碼）如：
AD67EA2F3BE6E5ADD368DFE03120B5DF92A8FD8FEC2F0746
其中：
AD67EA2F3BE6E5AD DES密碼一
D368DFE03120B5DF DES密碼二
92A8FD8FEC2F0746 DES密碼三
輸出：
對輸入的文件加密后，保存到同一文件夾下增加了".tdes"擴(kuò)展名的文件中。
*/
private void encrypt(File fileIn,String sKey){
try{
if(sKey.length() == 48){
byte[] bytK1 = getKeyByStr(sKey.substring(0,16));
byte[] bytK2 = getKeyByStr(sKey.substring(16,32));
byte[] bytK3 = getKeyByStr(sKey.substring(32,48));
FileInputStream fis = new FileInputStream(fileIn);
byte[] bytIn = new byte[(int)fileIn.length()];
for(int i = 0;iFILEIN.LENGTH();I++){
bytIn[i] = (byte)fis.read();
}
//加密
byte[] bytOut = encryptByDES(encryptByDES(
encryptByDES(bytIn,bytK1),bytK2),bytK3);
String fileOut = fileIn.getPath() + ".tdes";
FileOutputStream fos = new FileOutputStream(fileOut);
for(int i = 0;iBYTOUT.LENGTH;I++){
fos.write((int)bytOut[i]);
}
fos.close();
JOptionPane.showMessageDialog(
this,"加密成功！","提示",JOptionPane.OK_OPTION);
}else
JOptionPane.showMessageDialog(
this,"密碼長度必須等于48！","錯誤信息",JOptionPane.ERROR_MESSAGE);
}catch(Exception e){
e.printStackTrace();
}
}
/**
解密函數(shù)
輸入：
要解密的文件，密碼（由0-F組成，共48個字符，表示3個8位的密碼）如：
AD67EA2F3BE6E5ADD368DFE03120B5DF92A8FD8FEC2F0746
其中：
AD67EA2F3BE6E5AD DES密碼一
D368DFE03120B5DF DES密碼二
92A8FD8FEC2F0746 DES密碼三
輸出：
對輸入的文件解密后，保存到用戶指定的文件中。
*/
private void decrypt(File fileIn,String sKey){
try{
if(sKey.length() == 48){
String strPath = fileIn.getPath();
if(strPath.substring(strPath.length()-5).toLowerCase().equals(".tdes"))
strPath = strPath.substring(0,strPath.length()-5);
else{
JOptionPane.showMessageDialog(
this,"不是合法的加密文件！","提示",JOptionPane.OK_OPTION);
return;
}
JFileChooser chooser = new JFileChooser();
chooser.setCurrentDirectory(new File("."));
chooser.setSelectedFile(new File(strPath));
//用戶指定要保存的文件
int ret = chooser.showSaveDialog(this);
if(ret==JFileChooser.APPROVE_OPTION){
byte[] bytK1 = getKeyByStr(sKey.substring(0,16));
byte[] bytK2 = getKeyByStr(sKey.substring(16,32));
byte[] bytK3 = getKeyByStr(sKey.substring(32,48));
FileInputStream fis = new FileInputStream(fileIn);
byte[] bytIn = new byte[(int)fileIn.length()];
for(int i = 0;iFILEIN.LENGTH();I++){
bytIn[i] = (byte)fis.read();
}
//解密
byte[] bytOut = decryptByDES(decryptByDES(
decryptByDES(bytIn,bytK3),bytK2),bytK1);
File fileOut = chooser.getSelectedFile();
fileOut.createNewFile();
FileOutputStream fos = new FileOutputStream(fileOut);
for(int i = 0;iBYTOUT.LENGTH;I++){
fos.write((int)bytOut[i]);
}
fos.close();
JOptionPane.showMessageDialog(
this,"解密成功！","提示",JOptionPane.OK_OPTION);
}
}else
JOptionPane.showMessageDialog(
this,"密碼長度必須等于48！","錯誤信息",JOptionPane.ERROR_MESSAGE);
}catch(Exception e){
JOptionPane.showMessageDialog(
this,"解密失敗，請核對密碼！","提示",JOptionPane.OK_OPTION);
}
}
/**
用DES方法加密輸入的字節(jié)
bytKey需為8字節(jié)長，是加密的密碼
*/
private byte[] encryptByDES(byte[] bytP,byte[] bytKey) throws Exception{
DESKeySpec desKS = new DESKeySpec(bytKey);
SecretKeyFactory skf = SecretKeyFactory.getInstance("DES");
SecretKey sk = skf.generateSecret(desKS);
Cipher cip = Cipher.getInstance("DES");
cip.init(Cipher.ENCRYPT_MODE,sk);
return cip.doFinal(bytP);
}
/**
用DES方法解密輸入的字節(jié)
bytKey需為8字節(jié)長，是解密的密碼
*/
private byte[] decryptByDES(byte[] bytE,byte[] bytKey) throws Exception{
DESKeySpec desKS = new DESKeySpec(bytKey);
SecretKeyFactory skf = SecretKeyFactory.getInstance("DES");
SecretKey sk = skf.generateSecret(desKS);
Cipher cip = Cipher.getInstance("DES");
cip.init(Cipher.DECRYPT_MODE,sk);
return cip.doFinal(bytE);
}
/**
輸入密碼的字符形式，返回字節(jié)數(shù)組形式。
如輸入字符串：AD67EA2F3BE6E5AD
返回字節(jié)數(shù)組：{173,103,234,47,59,230,229,173}
*/
private byte[] getKeyByStr(String str){
byte[] bRet = new byte[str.length()/2];
for(int i=0;iSTR.LENGTH()
Integer itg =
new Integer(16*getChrInt(str.charAt(2*i)) + getChrInt(str.charAt(2*i+1)));
bRet[i] = itg.byteValue();
}
return bRet;
}
/**
計(jì)算一個16進(jìn)制字符的10進(jìn)制值
輸入：0-F
*/
private int getChrInt(char chr){
int iRet=0;
if(chr=="0".charAt(0)) iRet = 0;
if(chr=="1".charAt(0)) iRet = 1;
if(chr=="2".charAt(0)) iRet = 2;
if(chr=="3".charAt(0)) iRet = 3;
if(chr=="4".charAt(0)) iRet = 4;
if(chr=="5".charAt(0)) iRet = 5;
if(chr=="6".charAt(0)) iRet = 6;
if(chr=="7".charAt(0)) iRet = 7;
if(chr=="8".charAt(0)) iRet = 8;
if(chr=="9".charAt(0)) iRet = 9;
if(chr=="A".charAt(0)) iRet = 10;
if(chr=="B".charAt(0)) iRet = 11;
if(chr=="C".charAt(0)) iRet = 12;
if(chr=="D".charAt(0)) iRet = 13;
if(chr=="E".charAt(0)) iRet = 14;
if(chr=="F".charAt(0)) iRet = 15;
return iRet;
}
}
/**
文件選擇組件。
*/
class FilePanel extends JPanel{
FilePanel(String str){
JLabel label = new JLabel(str);
JTextField fileText = new JTextField(35);
JButton chooseButton = new JButton("瀏覽...");
this.add(label);
this.add(fileText);
this.add(chooseButton);
clickAction ca = new clickAction(this);
chooseButton.addActionListener(ca);
}
public String getFileName(){
JTextField jtf = (JTextField)this.getComponent(1);
return jtf.getText();
}
private class clickAction implements ActionListener{
clickAction(Component c){
cmpt = c;
}
public void actionPerformed(ActionEvent event){
JFileChooser chooser = new JFileChooser();
chooser.setCurrentDirectory(new File("."));
int ret = chooser.showOpenDialog(cmpt);
if(ret==JFileChooser.APPROVE_OPTION){
JPanel jp = (JPanel)cmpt;
JTextField jtf = (JTextField)jp.getComponent(1);
jtf.setText(chooser.getSelectedFile().getPath());
}
}
private Component cmpt;
}
}
/**
密碼生成組件。
*/
class KeyPanel extends JPanel{
KeyPanel(String str){
JLabel label = new JLabel(str);
JTextField fileText = new JTextField(35);
JButton chooseButton = new JButton("隨機(jī)產(chǎn)生");
this.add(label);
this.add(fileText);
this.add(chooseButton);
clickAction ca = new clickAction(this);
chooseButton.addActionListener(ca);
}
//返回生成的密碼（48個字符長度）
public String getKey(){
JTextField jtf = (JTextField)this.getComponent(1);
return jtf.getText();
}
private class clickAction implements ActionListener{
clickAction(Component c){
cmpt = c;
}
public void actionPerformed(ActionEvent event){
try{
KeyGenerator kg = KeyGenerator.getInstance("DES");
kg.init(56);
Key ke = kg.generateKey();
byte[] bytK1 = ke.getEncoded();
ke = kg.generateKey();
byte[] bytK2 = ke.getEncoded();
ke = kg.generateKey();
byte[] bytK3 = ke.getEncoded();
JPanel jp = (JPanel)cmpt;
JTextField jtf = (JTextField)jp.getComponent(1);
jtf.setText(getByteStr(bytK1)+getByteStr(bytK2)+getByteStr(bytK3));
}catch(Exception e){
e.printStackTrace();
}
}
private String getByteStr(byte[] byt){
String strRet = "";
for(int i=0;iBYT.LENGTH;I++){
//System.out.println(byt[i]);
strRet += getHexValue((byt[i]240)/16);
strRet += getHexValue(byt[i]15);
}
return strRet;
}
private String getHexValue(int s){
String sRet=null;
switch (s){
case 0: sRet = "0";break;
case 1: sRet = "1";break;
case 2: sRet = "2";break;
case 3: sRet = "3";break;
case 4: sRet = "4";break;
case 5: sRet = "5";break;
case 6: sRet = "6";break;
case 7: sRet = "7";break;
case 8: sRet = "8";break;
case 9: sRet = "9";break;
case 10: sRet = "A";break;
case 11: sRet = "B";break;
case 12: sRet = "C";break;
case 13: sRet = "D";break;
case 14: sRet = "E";break;
case 15: sRet = "F";
}
return sRet;
}
private Component cmpt;
}
}
挖掘頻繁模式前首先要構(gòu)造FP-Tree，算法為碼如下：
輸入:一個交易數(shù)據(jù)庫DB和一個最小支持度threshold.
輸出:它的FP-tree.
步驟:
1.掃描數(shù)據(jù)庫DB一遍.得到頻繁項(xiàng)的集合F和每個頻繁項(xiàng)的支持度.把F按支持度遞降排序,結(jié)果記為L.
2.創(chuàng)建FP-tree的根節(jié)點(diǎn),記為T,并且標(biāo)記為’null’.然后對DB中的每個事務(wù)Trans做如下的步驟.
根據(jù)L中的順序,選出并排序Trans中的事務(wù)項(xiàng).把Trans中排好序的事務(wù)項(xiàng)列表記為[p|P],其中p是第一個元素,P是列表的剩余部分.調(diào)用insert_tree([p|P],T).
函數(shù)insert_tree([p|P],T)的運(yùn)行如下.
如果T有一個子結(jié)點(diǎn)N,其中N.item-name=p.item-name,則將N的count域值增加1;否則,創(chuàng)建一個新節(jié)點(diǎn)N,使它的count為1,使它的父節(jié)點(diǎn)為T,并且使它的node_link和那些具有相同item_name域串起來.如果P非空,則遞歸調(diào)用insert_tree(P,N).
注：構(gòu)造FP-Tree的算法理解上相對簡單，所以不過多描述 對FP-Tree進(jìn)行挖掘，算法如下：
輸入:一棵用算法一建立的樹Tree
輸出:所有的頻繁集
步驟:
調(diào)用FP-growth(Tree,null).
procedure FP-Growth ( Tree, x)
{
(1)if (Tree只包含單路徑P) then
(2) 對路徑P中節(jié)點(diǎn)的每個組合（記為B）
(3) 生成模式B并x，支持?jǐn)?shù)=B中所有節(jié)點(diǎn)的最小支持度
(4) else 對Tree頭上的每個ai，do
{
(5) 生成模式B= ai 并 x，支持度=ai.support；
(6) 構(gòu)造B的條件模式庫和B的條件FP樹TreeB；
(7)if TreeB != 空集
(8)then call FP-Growth ( TreeB , B )
}
}
#includestdio.h
#includestdlib.h
#includestring.h
#include"malloc.h"
#define LEN 20
#define L_size 100
typedef struct Nodeone
{ char a[2];
struct Nodeone *next;
}Nodeone,*TNodeone;
struct
{
char rA[20];
char ra[20];
}rule[20];
struct
{
char mA[20];
char ma[20];
}mean[20];
/////////////////////////////////////////////
//棧的操作//////
typedef struct node
{
char data;
struct node * next;
}LinkStackNode,* LinkStack;
void InitStack(LinkStack * top)
{
(* top)=(LinkStack)malloc(sizeof(LinkStackNode));
(* top)-next=NULL;
}
//用頭插法建棧
void Push(LinkStack top,char a)
{
LinkStackNode * temp;
temp=(LinkStackNode *)malloc(sizeof(LinkStackNode));
temp-data=a;
temp-next=top-next;
top-next=temp;
}
//刪除棧頂元素
void Pop(LinkStack top,char *x)
{
LinkStackNode * temp;
temp=top-next;
top-next=temp-next;
*x=temp-data;
free(temp);
}
//////////////////////////////////////////////////////////////
////隊(duì)列的操作////
typedef struct Node
{
char data;
struct Node * next;
}LinkQueueNode;
typedef struct
{
LinkQueueNode * front;
LinkQueueNode * rear;
}LinkQueue;
//鏈隊(duì)列初始化
void InitQueue(LinkQueue *Q)
{
Q-front=(LinkQueueNode *)malloc(sizeof(LinkQueueNode));
if(Q-front!=NULL)
{
Q-rear=Q-front;
Q-front-next=NULL;
}
}
//鏈隊(duì)列入隊(duì)操作
void EnterQueue(LinkQueue *Q,char x)
{
LinkQueueNode * NewNode;
NewNode=(LinkQueueNode *)malloc(sizeof(LinkQueueNode));
if(NewNode!=NULL)
{
NewNode-data=x;
NewNode-next=NULL;
Q-rear-next=NewNode;
Q-rear=NewNode;
}
}
//鏈隊(duì)列出隊(duì)操作
void DeleteQueue(LinkQueue *Q,char *x)
{
LinkQueueNode * p;
p=Q-front-next;
Q-front-next=p-next;
if(Q-rear==p)
Q-rear=Q-front;
*x=p-data;
free(p);
}
//讀取文件
void read_rulefile()
{
FILE * fp;
char filename[LEN];
int i=0;
printf("請輸入要打開規(guī)則文件的完整路徑及其文件名：\n"); //1. 讀取文本文件(rule.txt), 將具體規(guī)則的對應(yīng) 關(guān)系讀入數(shù)組或鏈表中
gets(filename);
fp=fopen(filename,"rt");
if(fp==NULL)
{
printf("\n打開文件失敗,%s文件可能不存在\n",filename);
return ;
}
while(fscanf(fp,"%s %s",rule[i].rA,rule[i].ra)!=EOF)
{
printf("%s %s\n",rule[i].rA,rule[i].ra);
i++;
}
return ;
}
void read_meanfile()
{
FILE * fp;
char filename[LEN];
int i=0;
printf("請輸入要打開mean文件的完整路徑及其文件名：\n"); //2. 讀取文本文件(mean.txt), 將小寫字母及其 對應(yīng)的含義讀入數(shù)組或鏈表中
gets(filename);
fp=fopen(filename,"rt");
if(fp==NULL)
{
printf("\n打開文件失敗，%s文件可能不存在\n",filename);
return ;
}
while(fscanf(fp,"%s %s",mean[i].mA,mean[i].ma)!=EOF)
{
printf("%s %s\n",mean[i].mA,mean[i].ma);
i++;
}
return ;
}
///////////////////////////////////////////////////////////////////////
//思想：當(dāng)沒遇到閉括號時，一直壓棧（top棧）。一旦遇到閉括號，首先找到與這個閉括號最近的匹配的開括號
//找到這兩個括號“（” “）”之間的第一個 字符
//利用隊(duì)列（Q 入隊(duì)）以及（top棧 出棧）完成轉(zhuǎn)換，再把轉(zhuǎn)換后的隊(duì)列，添加到（top棧中）把剩余的字符 原樣添加到top棧中
//在把top棧 逆置到 top1棧中
//再利用top1棧出棧，給L重新賦值。
//遞歸，看L中是否還有括號
void tackle_2(LinkStackNode * top,LinkStackNode * top1,LinkQueue * Q,char L[])
{
int i=0,j;
char * a;
char first;
a=(char *)malloc(sizeof(char));
InitStack(top);
InitQueue(Q);//輔助用來輸出括號內(nèi)的內(nèi)容
InitStack(top1);
while(L[i]!=')'L[i]!='\0')
{
Push(top,L[i]);//當(dāng)不等于‘）’時，往top棧中壓。
i++;
}
if(L[i]==')') //當(dāng)?shù)扔?）'時
{
j=i;
while(L[j]!='(')
{ j--;
if(L[j]=='(')
{
j++;break;
}
}
first=L[j];//找到當(dāng)前‘（ ’內(nèi)的第一個字符
for(;ji-1;j++)
{
EnterQueue(Q,first);
Pop(top,a);
EnterQueue(Q,*a);
}
Pop(top,a); //這個是括號內(nèi)的第一個字符
EnterQueue(Q,*a);
Pop(top,a);//把‘（’刪掉
while(Q-front-next!=NULL)
{
DeleteQueue(Q,a);
Push(top,*a);
}
}// if
i++;//跳過‘）’
while(L[i]!=NULL)
{ Push(top,L[i]);
i++;
}
while(top-next!=NULL)
{
Pop(top,a);
Push(top1,*a);
}
i=0;
while(top1-next!=NULL)
{
Pop(top1,a);
L[i]=*a;
i++;
}
L[i]=NULL;
i=0;j=0;
while(L[i]!=NULL)
{
i++;
if(L[i]=='(' || L[i]==')')
j++;
}
if(j==0) return;
else tackle_2(top,top1,Q,L);
}
//////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////
//實(shí)現(xiàn)提示： 處理規(guī)則形式（1） 問題并沒有規(guī)定具體規(guī)則的數(shù)量，
//比如增加 一條具體規(guī)則 C→eB 那么對魔王語言就要多處理一次，
//因此處理 規(guī)則形式（1）時需要遞歸處理，當(dāng)語言中沒有 大寫字母后遞歸結(jié)束。
void tackle_1(char L[],LinkQueue * Q)
{
int i=0,j,z;
int k=0;
char * a;
a=(char *)malloc(sizeof(char));
while(L[i]!=NULL)
{ z=0;
for(j=0;j20;j++)
{
if(L[i]==rule[j].rA[0])
{ k=0;
z=1;
while(rule[j].ra[k]!=NULL)
{
EnterQueue(Q,rule[j].ra[k]);
k++;
}
}
}
if(z==1)
i++;
else
{
EnterQueue(Q,L[i]);
i++;
}
}
i=0;
while(Q-front-next!=NULL)
{
DeleteQueue(Q,a);
L[i]=(*a);
i++;
}
L[i]=NULL;
i=0; j=0;
while(L[i]!=NULL)
{
if(L[i]='A' L[i]='Z')
j++;
i++;
}
if(j==0)return;
else tackle_1(L,Q);
}
TNodeone tackle_12(char L[])
{ TNodeone head,r,s;
int i=0;
int j;
head=(Nodeone*)malloc(sizeof(Nodeone));
head-next=NULL;
r=head;
while(L[i]!=NULL)
{
for(j=0;j20;j++)
{
if(L[i]==mean[j].mA[0])
printf("%s",mean[j].ma);
s=(Nodeone*)malloc(sizeof(Nodeone));
strcpy(s-a,mean[j].ma);
r-next=s;
r=s;
}
i++;
}
r-next=NULL;
return head;
}
void savefile(TNodeone head)
{ FILE *fp;
TNodeone h;
h=head-next;
fp=fopen("c:/result.txt","wb");
if(fp==NULL)
{ printf("讀文件失敗，按任意鍵退出！");
getchar();
exit(1);
}
for(;h;h=h-next)
fprintf(fp,"%s",h-a);
fclose(fp);
printf("\n");
printf("保存文件成功！");
}
void main()
{ TNodeone head;
read_rulefile();
read_meanfile();
char L[L_size]; //魔王說的話
printf("請輸入魔王語言：\n");
scanf("%s",L);
LinkStackNode * top, * top1;
top=(LinkStackNode * )malloc(sizeof(LinkStackNode));
top1=(LinkStackNode * )malloc(sizeof(LinkStackNode));
LinkQueue *Q;
Q=(LinkQueue *)malloc(sizeof(LinkQueue));
tackle_2(top,top1,Q,L);
printf("魔王要說的話是：%s\n",L);
tackle_1(L,Q);
printf("魔王要說的話是（轉(zhuǎn)換成小寫后）：%s\n",L);
head=tackle_12(L);
savefile(head);
}
FP—tree由標(biāo)記為“null”的一個根節(jié)點(diǎn)(root)、作為根節(jié)點(diǎn)之子節(jié)點(diǎn)的項(xiàng)前綴子樹(item prefix subtrees)的集合、和—個頻繁項(xiàng)頭表(frequent item header table)所組成。
項(xiàng)前綴子樹中的每個節(jié)點(diǎn)包含3個域：item_name,count和node_link。item _name記錄了該節(jié)點(diǎn)所代表的項(xiàng)的名字。count記錄了所在路徑代表的事務(wù)中達(dá)到此節(jié)點(diǎn)的事務(wù)個數(shù)。 node_link指向下一個具有同樣的item_name域的節(jié)點(diǎn)，如果沒有這樣一個節(jié)點(diǎn)，則其值被置為null。
頻繁項(xiàng)頭表包含兩個域：Item_name和head of node_link. head of node_link指向FP—tree中具有相同Item_name的第一個節(jié)點(diǎn)。
根據(jù)FP_tree 的定義，我們得到FP_tree的構(gòu)造方法
2 FP—tree的生成
FP—tree是通過兩次掃描事務(wù)集建立的.
(1)掃描事務(wù)集D，獲得D中所包含的全部頻繁項(xiàng)集合F，及它們各自的支持度。對F中的頻繁項(xiàng)按其支持度降序排序,結(jié)果記為L；
(2)創(chuàng)建FP—tree的根節(jié)點(diǎn)T，以“null”標(biāo)(3) 記；然后對D中的每個事務(wù)Trans進(jìn)行如下操作：根據(jù)L中的順序，選出并排序Trans的頻繁項(xiàng)．設(shè)排序后的頻繁項(xiàng)表為[x|P]，其中x是第一個頻繁項(xiàng)。而P是剩余的頻繁項(xiàng):調(diào)用insert—tree([x|P]，T)：insert—tree([x|P]，T)過程執(zhí)行情況如下：如果T有子女N并使得N.item_name=x.item_name，則N的計(jì)數(shù)增加1；否則創(chuàng)建一個新節(jié)點(diǎn)N，將其計(jì)數(shù)設(shè)置為1，鏈接到它的父節(jié)點(diǎn)T、、并且通過節(jié)點(diǎn)鏈結(jié)構(gòu)將其鏈接到具有相同item_name的節(jié)點(diǎn)；如果P非空，遞歸地調(diào)用INSERT—tree(P，N)。在事務(wù)集再次掃描完畢時，一個完全的FP—tree就建成了。
3 頻繁模式的挖掘
FP—tree被建立后，頻繁模式是采用下面的FP—growth方法對FP—tree進(jìn)行挖掘得到的. Procedure FP_growth(Tree，α)／／tree為α的條件模式樹，α為后綴項(xiàng)(集)
{ if Tree 僅含一條路徑P then
for 路徑P中節(jié)點(diǎn)的每個組合(記作?) do
產(chǎn)生模式?Uα、并且把它的支持度supcoun指定為?中節(jié)點(diǎn)的最小支持度
else for 對Tree的頭表從表尾到表頭的每一個表項(xiàng)（記為α1）do {
產(chǎn)生一個模式?＝α1Uα，其支持度計(jì)數(shù)supcount=α1．supcount：
創(chuàng)建?的條件模式基，然后構(gòu)造?的條件模式樹FP—tree? ；
if FP—tree ?= !Φ then 調(diào)用FP_growth(FP—tree?、?)}
從算法2、3中，我們可以看出FP—growth挖掘過程是一種分而治之的過程。而且，即使數(shù)據(jù)庫可能產(chǎn)生指數(shù)級大量的頻繁模式，F(xiàn)P—tree的規(guī)模還是很小，不會呈指數(shù)級增長。例如，對于一個長度為100的頻繁模式“a1，…，a100”，F(xiàn)P—tree只會生成唯一一條長度為100的路徑，如“a1a2…a100”。而且，F(xiàn)P—growth算法可以導(dǎo)出所有的大約1030個頻繁模式(如果時間允許的話)，如“a1, a2,..，a1a2，…，a1a2a3：，…，a1…a100”。
3.程序?qū)崿F(xiàn)
程序在定義數(shù)據(jù)結(jié)構(gòu)和實(shí)現(xiàn)算法的時候主要考慮一下因素。
首先速度。速度問題在頻繁集產(chǎn)生的算法中應(yīng)該是比較重要的.因?yàn)樗鼈兂３Ｉ婕按罅繑?shù)據(jù)的處理.因此在程序中許多需要排序的數(shù)據(jù)結(jié)構(gòu)都使用了平衡樹,這是一種高效的對全序元素的組織方式。
其次,空間。同樣因?yàn)橐幚泶罅康臄?shù)據(jù),所以對內(nèi)存的管理要尤其嚴(yán)格,如果出現(xiàn)內(nèi)存泄漏將是很麻煩的事情。
第三，編程風(fēng)格的考慮.要盡量采用通用化的代碼.因?yàn)閷τ谝粋€比較大的系統(tǒng)來說，任何一個小的部分都應(yīng)該清楚明白,便于別人閱讀和修改。
基于上面三點(diǎn)，在對程序的數(shù)據(jù)結(jié)構(gòu)的定義和算法的實(shí)現(xiàn)的時候大量采用了C++的標(biāo)準(zhǔn)模板庫(STL,Standard Template Library).這是基于以下的事實(shí),關(guān)聯(lián)規(guī)則的挖掘所涉及到的數(shù)據(jù)結(jié)構(gòu)和基本算法都是以往的常用數(shù)據(jù)結(jié)構(gòu)和算法,如向量類,集合類,快速排序算法等.而STL正是包含了這樣許多通用的數(shù)據(jù)結(jié)構(gòu)和基本算法的庫。
例如,在STL中有一大類模板叫容器模板(container),簡單的說就是包含了許多元素的類的模板,象vector,array,set等就屬于容器模板.對于這些模板中的元素的訪問都可以通過它們的遍歷子,用完全一致的方式進(jìn)行.請看下面兩段程序清單：
void print(FreqSet* pSet){
FreqSet_Iter fit;
for(fit=pSet-begin();fit!=pSet-end();fit++){
printf("%s %d \n",(*fit).second.name,(*fit).second.count);
}
}
void print(Table* pTable){
Table_Iter tit;
for(tit=pTable-begin();tit!=pTable-end();tit++){
printf("%s %d \n",(*tit).name,(*tit).count);
}
}
這兩個函數(shù)的作用是在調(diào)試的時候分別打印出頻繁集pSet和頭表pTable中的元素。
盡管pSet的類FreqSet是由map模板生成的,pTable的類Table是由multiset生成的,但對它們的元素的訪問形式幾乎一模一樣都是利用相應(yīng)的遍歷子.涉及的函數(shù)名也很相似.其實(shí),所有的容器模板都定義了函數(shù)begin()和end()代表元素列表的起始和結(jié)束.另外還有大量的具有相同名字和類似功能的函數(shù),方便了我們對數(shù)據(jù)結(jié)構(gòu)的管理。
在選擇數(shù)據(jù)庫訪問方式的時候,用了最近比較流行的ADO方式,它比ODBC更加靈活,速度也有改善.對網(wǎng)絡(luò)數(shù)據(jù)庫的支持也很好。
對應(yīng)于算法描述中所出現(xiàn)的各個對象分別定義了一些數(shù)據(jù)結(jié)構(gòu)，僅以trans為例說明
class Trans:public std::vectorItem
{
public:
int TID;
Trans(){TID=0;};
Trans(int t){
TID=t;
}
bool operator==(const Trans right);
bool operator(const Trans right);
}
typedef Trans::iterator Trans_Iter;
Trans類對應(yīng)于交易對象(Transaction).對它的定義利用了STL中的vector模板,把它定義為一個以Item為元素的向量.把它定義為向量,是因?yàn)楹髞硇枰獙ζ渲械脑剡M(jìn)行排序,向量可以使用快速排序。
這個Trans 類身肩兩任,它不僅代表事務(wù)對象,還在最后的結(jié)果輸出中還被用來存放頻繁集。
Trans_Iter是Trans類的遍歷子.在以后使用STL容器模板定義的類都會有一個與之相對應(yīng)的遍歷子,不再贅述。
作者根據(jù)算法用 Vsual C++編寫了程序，程序己在機(jī)器上調(diào)試通過（運(yùn)行環(huán)境為： Windows Xp、Vsual C++ 6．0）．為節(jié)約篇幅，并且方便用戶閱讀，作者列出了部分關(guān)鍵程序清單
//根據(jù)條件模式庫來生成用于構(gòu)建條件樹的頻繁項(xiàng)
void FPTree::BuildCPTree(long p_Frequnce)
{
std::vectorstd::vectorassociate ::iterator it_CPBase=m_CPBase.begin();
std::vectorassociate::iterator it_vector,it_temp1;
std::mapstd::string,int Item_include;//包含非頻繁的項(xiàng)的集合
std::mapstd::string,int::iterator it_map,it_temp;
std::string l_string;
long Frequnce=p_Frequnce;
bool flag=true;
int l_test;
//統(tǒng)計(jì)每個項(xiàng)目的頻繁度
for (;it_CPBase!=m_CPBase.end();it_CPBase++)
{
it_vector=(*it_CPBase).begin();
while (it_vector!=(*it_CPBase).end())
{
l_string=(*it_vector).chr;
l_test=(*it_vector).num;
if (Item_include.count(l_string))
{
Item_include[l_string]+=(*it_vector).num;
l_test=Item_include[l_string];
}
else
Item_include[l_string]=(*it_vector).num;
it_vector++;
}
}
//除去map中的非頻繁項(xiàng)
bool flag1=true;
it_map=Item_include.begin();
while ((it_map!=Item_include.end()) flag1)
{
l_string=it_map-first;
l_test=it_map-second;
if (it_map-second Frequnce)
{
it_temp=it_map;
it_map++;
Item_include.erase(it_temp);
if (it_map==Item_include.end())
flag1=false; }
else
it_map++;
}
if (!Item_include.empty())
{
重慶分公司
重慶分公司
