返回 登录
6

Apriori算法的C/C#实现

阅读355

数据结构的选取,还做得不太好,会继续改进,请大牛多多指点。

之后我会比较C#与C的Apriori程序,总结一些区别,谈谈面向对象编程在这个算法上的体现与数据结构的选择问题。

  1 #include <dos.h>
  2 #include <conio.h>
  3 #include <math.h>
  4 #include <stdio.h>
  5 #include <stdlib.h>
  6 
  7 #define ItemNumSize 2
  8 #define TranNumSize 100
  9 #define LISTINCREMENT 1
 10 #define OK 1
 11 #define TRUE 1
 12 #define FASLE 0
 13 #define ERROR 0
 14 #define MAX_ARRAY_DIM 100
 15 #define MAXSIZE  100
 16 typedef char ItemType;
 17 typedef int ElemType;
 18 float  minSupport,minConfidence;
 19 //动态内存分配,item用什么数据结构 动态数组,线性表好:数组是整体创建,整体删除的
 20 typedef struct  
 21 {
 22     ItemType *item;//项目
 23     int length;//当前项目个数
 24     int listsize;//当前分配的存储容量
 25 }SqList;
 26 //事务数组集合
 27 typedef struct
 28 {
 29     SqList r[MAXSIZE+1];
 30     int Length;
 31 }TranList;
 32 
 33 //初始化项目的线性表
 34 int InitListSq(SqList &L)
 35 {
 36     L.item=(ItemType * )malloc(ItemNumSize *sizeof(ItemType));
 37     if (!L.item)exit(OVERFLOW);//存储分配失败
 38     L.length=0;//空表长度为0
 39     L.listsize=ItemNumSize;//初始化存储容量
 40     return OK;
 41 }
 42 //初始化事务的线性表
 43 int InitListTran(TranList &TranL)//还有更好的动态分配方式初始化
 44 {
 45     for (int i=1;i<=TranNumSize;i++)
 46     {
 47         InitListSq(TranL.r[i]);
 48     }
 49     return OK;
 50 }
 51 //插入项目线性表
 52 int listInsertSq(SqList &L,int i,ItemType e)
 53 {
 54     //在线性表L中第i个位置之前插入新元素e
 55     //i的合法值为1<=i<=l.listlength+1
 56     ItemType *newbase,*q,*p;
 57     if(i<1||i>L.length+1)return ERROR;//i值不合法
 58     if (L.length>=L.listsize)//当前存储空间已满,添加分配
 59     {
 60         //重新分配内存空间
 61        newbase=(ItemType *)realloc(L.item,(L.listsize+LISTINCREMENT)*sizeof(ItemType));
 62        if (!newbase)exit(OVERFLOW);
 63        L.item=newbase;//新基址
 64        L.listsize+=LISTINCREMENT;//增加存储容量
 65     }
 66     q=&(L.item[i-1]);//q为插入位置
 67     for(p=&(L.item[L.length-1]);p>=q;--p)
 68         *(p+1)=*p;//插入位置,及之后的元素右移
 69     *q=e;
 70     ++L.length;
 71     return OK;
 72 }
 73 void main()
 74 {
 75     int c;
 76     ItemType e;
 77     SqList L;
 78     int sn;
 79     int ItemNum; //项目个数
 80     int trannum[20]={0}; //事务数量
 81     char b2[100][10]; 
 82     char b21[100][10]; 
 83     TranList TranL;
 84     SqList L1;
 85     InitListSq(L);
 86     InitListTran(TranL);
 87     printf ("链表长度:%d\n", L.length);  // 线性表当前的元素个数
 88     printf ("链表大小:%d\n", L.listsize); // 线性表最多可存放元素的个数
 89     while (1)
 90     {
 91         system("cls");
 92         printf_s("\n          Apriori算法的C语言实现\n");
 93         printf_s("           1        输入项目集合\n");
 94         printf_s("           2        添加事务\n");
 95         printf_s("           3        设定最小支持度与最小置信度\n");
 96         printf_s("           4        输出结果\n");
 97         printf_s("           5        退出\n");    
 98         printf_s("请输入:\n");    
 99         scanf_s("%d",&c);
100         switch (c)
101         {
102         case 1://构造项目集
103             {
104                 int it;
105                 char ItemValue;
106                 system("cls");
107                 printf_s("构造项目集\n");
108                 printf_s("请输入项目个数:\n");//项目个数
109                 scanf_s("%d",&ItemNum);
110                 for (it=1;it<=ItemNum;it++)//依次输入每个项目集
111                 {
112                     fflush(stdin);
113                     printf_s("\n请输入第%d个项目的字母(a,b,c,d,e,f,……):\n",it);
114                     scanf("%c",&ItemValue);
115                     listInsertSq(L,it,ItemValue);
116                 }
117                 printf_s("\n初始化后,项目集各元素值:\n");
118                 for (int i=0;i<L.length;i++)
119                 {
120                     printf_s("%c\n",L.item[i]);
121                 }
122                 _getch();
123                 break;
124             }
125         case 2:
126             {
127                 system("cls");
128                 //事务的数据结构,动态数组
129                 int i,j;
130                 char tranvalue;
131                 printf_s("请输入要添加的事务个数:\n");//事务个数
132                 scanf_s("%d",&sn);
133                 for (i=1;i<=sn;i++)//依次输入每个事务所包含的项目,i应当从0开始
134                 {
135                     printf_s("请输入第%d个事务包含的项目数:",i);
136                     scanf_s("%d",&trannum[i]);
137                     fflush(stdin);
138                     for (j=1;j<=trannum[i];j++)
139                     {
140                         fflush(stdin);
141                         printf_s("输入事务的第%d个项目:\n",j);
142                         scanf_s("%c",&tranvalue);
143                         //动态分配内存,插入事务数组集合
144                         listInsertSq(TranL.r[i],j,tranvalue);
145                     }
146                 }
147                 printf_s("\n各事务的项目如下:\n");
148                 for (i=1;i<=sn;i++)
149                 {
150                     printf_s("\n第%d个事务\n",i);
151                     for (j=0;j<=trannum[i];j++)
152                     {
153                         printf_s("%c",TranL.r[i].item[j]);
154                     }
155                 }
156                 _getch();
157                 break;
158             }
159         case 3://设定最小支持度与最小置信度
160             {
161                 system("cls");
162                 printf_s("请输入最小支持度与最小置信度(空格隔开):");
163                 fflush(stdin);//最好在每个scanf前加上fflush( stdin );
164                 scanf_s("%f%f",&minSupport,&minConfidence);
165                 printf_s("\n最小支持度为:%2.2f\n",minSupport);
166                 printf_s("最小置信度为:%2.2f\n",minConfidence);
167                 _getch();
168                 break;
169             }
170         case 4://Apriori算法
171             {
172                 InitListSq(L1);
173                 char generatedCandidate[10];
174                 int c[20]={0};
175                 int f[20]={0};
176                 int jj=1;
177                 //得到C1,算法第一行
178                 for (int i=0;i<ItemNum;i++)//算法太复杂了,以后改为二叉树
179                 {
180                     for (int j=1;trannum[j]!=0;j++)
181                     {
182                         for (int k=0;TranL.r[j].item[k]!=0;k++)
183                         {
184                             if (L.item[i]==TranL.r[j].item[k])
185                             {
186                                 c[i]++;
187                             }
188                         }
189                     }
190                     //计算F1支持度
191                     if (c[i]>=minSupport*trannum[i+1])//两个整数相除得到整数
192                     {
193                         f[i]=c[i];
194                         listInsertSq(L1,jj,L.item[i]);//L1
195                         jj++;
196                     }
197                 }
198                 printf_s("F1集合为:\n");
199                 int temp1=0;
200                 for (int i=0;i<ItemNum;i++)
201                 {
202                     printf_s("{%c}=%d  ",L.item[i],f[i]);
203                     if ((temp1+1)%3==0)
204                         printf_s("\n");
205                     temp1++;
206                 }
207                 printf_s("\n");
208                 //排序TranL.r[j].item[k]
209                 int t;
210                 for (int i=1;i<=sn;i++)//每个事务
211                 {
212                     for (int j=0;j<trannum[j+1];j++)//每个项目
213                     {
214                         if (TranL.r[i].item[j]>TranL.r[i].item[j+1])
215                         {
216                             t=TranL.r[i].item[j];
217                             TranL.r[i].item[j]=TranL.r[i].item[j+1];
218                             TranL.r[i].item[j]=t;
219                         }
220                     }
221                 }
222                 //GenerateCandidates函数
223                 int j1;
224                 j1=L1.length;
225                 //把L1->b2[i][]
226                 for (int i=0;i<j1;i++)
227                 {
228                     b2[i][0]=L1.item[i];
229                 }
230                 int kk=0;
231                 for (int i=0;i<L1.length;i++)
232                 {
233                     generatedCandidate[kk]=L1.item[i];
234                     kk++;
235                     for (int j=i+1;j<L1.length;j++)
236                     {
237                         generatedCandidate[kk]=L1.item[i+1];
238                         if (generatedCandidate!=0)
239                         {
240                             char temp;
241                             //排序
242                             for (int i=0;generatedCandidate[i+1]!=0;i++)
243                             {
244                                 if (generatedCandidate[i]>generatedCandidate[i+1])
245                                 {
246                                     temp=generatedCandidate[i];
247                                     generatedCandidate[i]=generatedCandidate[i+1];
248                                     generatedCandidate[i+1]=temp;
249                                 }
250                             }
251                         }
252                     }
253                 }
254                 int u=0;
255                 int v=1;//用V来进行输出各种组合的标识数V=1表示正在进行输出
256                 int c2[100]={0};
257                 int flag1=1;
258                 int counter=0;
259                 int temp;
260                 //getsupport
261                 for (int k=2;b2[0][0]!='\0';k++)
262                 {
263                     u=0;v=1;
264                     for (int i=0;i<100;i++)
265                     {
266                         c2[i]=0;
267                     }
268                     for (int i=0;i<j1;i++)
269                     {
270                         for (int i1=i+1;i1<j1;i1++)
271                         {
272                             for (int j=0;j<k-2;j++)
273                             {
274                                 if (b2[i][j]!=b2[i1][j])
275                                 {
276                                     flag1=0;
277                                     break;
278                                 }
279                             }
280                             //进行组合的部分
281                             if (flag1==1&&b2[i][k-2]!=b2[i1][k-2])
282                             {
283                                 for (int j2=0;j2<k-1;j2++)
284                                 {
285                                     b21[u][j2]=b2[i][j2];
286                                 }
287                                 b21[u][k-1]=b2[i1][k-2];
288                                 u++;
289                             }
290                             flag1=1;
291                         }
292                     }
293                     counter=0;
294                     for (int i=0;i<sn;i++)
295                     {
296                         for (int i1=0;i1<u;i1++)
297                         {
298                             for (int j1=0;j1<k;j1++)
299                             {
300                                 for (int j=0;TranL.r[i+1].item[j]!='\0';j++)
301                                 {
302                                     if (TranL.r[i+1].item[j]==b21[i1][j1])
303                                         counter++;
304                                 }
305                             }
306                             if (counter==k)
307                                 c2[i1]++;
308                             counter=0;
309                         }
310                     }
311                     j1=0;
312                     temp=0;
313                     //对U中情况进行选择,选出支持度计数大于2314                     for (int i=0;i<u;i++)
315                     {
316                         if (c2[i]>=minSupport)
317                         {
318                             if (v==1)
319                             {
320                                 printf_s("\nF%d集合为:\n",k);
321                                 v=0;
322                             }
323                             printf_s("{");
324                             for (int j=0;j<k;j++)
325                             {
326                                 b2[j1][j]=b21[i][j];
327                                 printf_s("%c,",b2[j1][j]);
328                             }
329                             j1++;
330                             printf_s("\b}");
331                             printf_s("=%d  ",c2[i]);
332                             if ((temp+1)%3==0)
333                                 printf_s("\n");
334                             temp++;
335                         }
336                     }
337                     b2[j1][0]='\0';
338                     if (b2[0][0]!='0')
339                     {
340                         printf_s("\b \n");
341                     }
342                 }
343                 _getch();
344                 break;
345             }
346         case 5:
347             {
348                 return;
349                 _getch();
350                 system("cls");
351                 break;
352             }
353         default:
354             {
355                 printf_s("输入有误请重新输入!\n");
356                 _getch();
357                 system("cls");
358             }
359         }
360 
361     }
362 }

如果有想要交流的欢迎加本人的学习交流群494052584和我们一起交流经验一起进步

评论