当前位置：文档库 › Apriori算法C语言源代码实现

Apriori算法C语言源代码实现

#ifndef APRIRORI_H

#define APRIRORI_H

#include

using namespace std;

#define MAXIMAL

#include

#include "tract.h"

#include "istree.h"

#include "Application.h"

/*---------------------------------------------------------------------- Preprocessor Definitions

----------------------------------------------------------------------*/

#define PRGNAME "fim/apriori"

#define DESCRIPTION "frequent item sets miner for FIMI 2003" #define VERSION "version 1.7 (2003.12.02) " \

/* --- error codes --- */

#define E_OPTION (-5) /* unknown option */

#define E_OPTARG (-6) /* missing option argument */

#define E_ARGCNT (-7) /* too few/many arguments */

#define E_SUPP (-8) /* invalid minimum support */

#define E_NOTAS (-9) /* no items or transactions */

#define E_UNKNOWN (-18) /* unknown error */

#ifndef QUIET /* if not quiet version */

#define MSG(x) x /* print messages */

#else /* if quiet version */

#define MSG(x) /* suppress messages */

#endif

#define SEC_SINCE(t) ((clock()-(t)) /(double)CLOCKS_PER_SEC)

#define RECCNT(s) (tfs_reccnt(is_tfscan(s)) \

+ ((tfs_delim(is_tfscan(s)) == TFS_REC) ? 0 : 1)) #define BUFFER(s) tfs_buf(is_tfscan(s))

/*----------------------------------------------------------------------

Constants

----------------------------------------------------------------------*/

#ifndef QUIET /* if not quiet version */

/* --- error messages --- */

static const char *errmsgs[] = {

/* E_NONE 0 */ "no error\n",

/* E_NOMEM -1 */ "not enough memory\n",

/* E_FOPEN -2 */ "cannot open file %s\n",

/* E_FREAD -3 */ "read error on file %s\n",

/* E_FWRITE -4 */ "write error on file %s\n",

/* E_OPTION -5 */ "unknown option -%c\n",

/* E_OPTARG -6 */ "missing option argument\n",

/* E_ARGCNT -7 */ "wrong number of arguments\n",

/* E_SUPP -8 */ "invalid minimal support %d\n",

/* E_NOTAS -9 */ "no items or transactions to work on\n",

/* -10 to -15 */ NULL, NULL, NULL, NULL, NULL, NULL,

/* E_ITEMEXP -16 */ "file %s, record %d: item expected\n",

/* E_DUPITEM -17 */ "file %s, record %d: duplicate item %s\n",

/* E_UNKNOWN -18 */ "unknown error\n"

};

#endif

/*----------------------------------------------------------------------

Global Variables

----------------------------------------------------------------------*/

#ifndef QUIET

static char *prgname; /* program name for error messages */

#endif

static ITEMSET *itemset = NULL; /* item set */

static TASET *taset = NULL; /* transaction set */

static TATREE *tatree = NULL; /* transaction tree */

static ISTREE *istree = NULL; /* item set tree */

static FILE *in = NULL; /* input file */

static FILE *out = NULL; /* output file */

extern "C" TATREE * apriori( char*fn_in, char*fn_out, int supp, int & level,

Trie * bdPapriori, Trie * bdn, set * relist, double ratioNfC, double & eps, int ismax,

vector< unsigned int > * stat, int & maxBdP, bool & generatedFk, bool verbose ) ;

#endif

============================================

/*----------------------------------------------------------------------

File : apriori.c

Contents: apriori algorithm for finding frequent item sets

(specialized version for FIMI 2003 workshop)

Author : Christian Borgelt

History : 15.08.2003 file created from normal apriori.c

16.08.2003 parameter for transaction filtering added

18.08.2003 dynamic filtering decision based on times added

21.08.2003 transaction sort changed to heapsort

20.09.2003 output file made optional

----------------------------------------------------------------------*/

Modified by : Frédéric Flouvat

Modifications : store the positive and negative border into an

an input trie for ABS

process stastical informations on dataset to stop

the apriori classical iterations

Author : Frédéric Flouvat

----------------------------------------------------------------------*/

#include "apriori.h"

/*----------------------------------------------------------------------

Main Functions

----------------------------------------------------------------------*/

static void error (int code, ...)

{ /* --- print an error message */ #ifndef QUIET /* if not quiet version */

va_list args; /* list of variable arguments */ const char *msg; /* error message */

assert(prgname); /* check the program name */ if (code < E_UNKNOWN) code = E_UNKNOWN;

if (code < 0) { /* if to report an error, */

msg = errmsgs[-code]; /* get the error message */

if (!msg) msg = errmsgs[-E_UNKNOWN];

fprintf(stderr, "\n%s: ", prgname);

va_start(args, code); /* get variable arguments */

vfprintf(stderr, msg, args);/* print error message */

va_end(args); /* end argument evaluation */ }

#endif

#ifndef NDEBUG /* if debug version */

if (istree) ist_delete(istree);

if (tatree) tat_delete(tatree);

if (taset) tas_delete(taset, 0);

if (itemset) is_delete(itemset);

if (in) fclose(in); /* clean up memory */

if (out) fclose(out); /* and close files */

#endif

exit(code); /* abort the program */

} /* error() */

/*--------------------------------------------------------------------*/

TATREE * apriori( char*fn_in, char*fn_out, int supp, int & level, Trie * bdPapriori,

Trie * bdn , set * relist , double ratioNfC, double & eps,int ismax,

vector< unsigned int > * stat, int & maxBdP, bool & generatedFk, bool verbose )

{

int i, k, n; /* loop variables, counters */

int tacnt = 0; /* number of transactions */

int max = 0; /* maximum transaction size */

int empty = 1; /* number of empty item sets */

int *map, *set; /* identifier map, item set */

char *usage; /* flag vector for item usage */

clock_t t, tt, tc, x; /* timer for measurements */

double actNfC = 1 ;

double avgNfC = 0 ;

int nbgen = 0 ;

int nbfreq = 0 ;

level = 1 ;

bool endApriori = false ; // boolean to stop the initial classial apriori approach

int bdnsize = 0 ; // number of itemsets found infrequent

/* --- create item set and transaction set --- */

itemset = is_create(); /* create an item set and */

if (!itemset) error(E_NOMEM); /* set the special characters */

taset = tas_create(itemset); /* create a transaction set */

if (!taset) error(E_NOMEM); /* to store the transactions */

if( verbose ) MSG(fprintf(stderr, "\n")); /* terminate the startup message */

/* --- read transactions --- */

if( verbose )MSG(fprintf(stderr, "reading %s ... ", fn_in));

t = clock(); /* start the timer and */

in = fopen(fn_in, "r"); /* open the input file */

if (!in) error(E_FOPEN, fn_in);

for (tacnt = 0; 1; tacnt++) { /* transaction read loop */

k = is_read(itemset, in); /* read the next transaction */

if (k < 0) error(k, fn_in, RECCNT(itemset), BUFFER(itemset));

if (k > 0) break; /* check for error and end of file */

k = is_tsize(itemset); /* update the maximal */

if (k > max) max = k; /* transaction size */

if (taset && (tas_add(taset, NULL, 0) != 0))

error(E_NOMEM); /* add the loaded transaction */

} /* to the transaction set */

fclose(in); in = NULL; /* close the input file */

n = is_cnt(itemset); /* get the number of items */

if( verbose ) MSG(fprintf(stderr, "[%d item(s),", n));

if( verbose ) MSG(fprintf(stderr, " %d transaction(s)] done ", tacnt));

if( verbose ) MSG(fprintf(stderr, "[%.2fs].\n", SEC_SINCE(t)));

/* --- sort and recode items --- */

if( verbose ) MSG(fprintf(stderr, "sorting and recoding items ... "));

t = clock(); /* start the timer */

map = (int*)malloc(is_cnt(itemset) *sizeof(int));

if (!map) error(E_NOMEM); /* create an item identifier map */

n = is_recode(itemset, supp, 2, map); /* 2: sorting mode */

tas_recode(taset, map, n); /* recode the loaded transactions */ max = tas_max(taset); /* get the new maximal t.a. size */

// use in the other part of the implementation to have the corresponding // identifiant to an internal id

stat->reserve( n+2 ) ;

stat->push_back( 0 ) ;

for(int j= 0; j< n ; j++ )

{

stat->push_back( 0 ) ;

relist->insert( Element( atoi( is_name( itemset, j ) ) ,j) );

}

if( verbose ) MSG(fprintf(stderr, "[%d item(s)] ", n));

if( verbose ) MSG(fprintf(stderr, "done [%.2fs].\n", SEC_SINCE(t)));

/* --- create a transaction tree --- */

if( verbose ) MSG(fprintf(stderr, "creating transaction tree ... "));

t = clock(); /* start the timer */

tatree = tat_create(taset,1); /* create a transaction tree */

if (!tatree) error(E_NOMEM); /* (compactify transactions) */

tt = clock() -t; /* note the construction time */

if( verbose ) MSG(fprintf(stderr, "done [%.2fs].\n", SEC_SINCE(t)));

/* --- create an item set tree --- */

if( verbose ) MSG(fprintf(stderr, "checking subsets of size 1"));

t = clock(); tc = 0; /* start the timer and */

istree = ist_create(n, supp); /* create an item set tree */

if (!istree) error(E_NOMEM);

for (k = n; --k >= 0; ) /* set single item frequencies */

ist_setcnt(istree, k, is_getfrq(itemset, k));

ist_settac(istree, tacnt); /* set the number of transactions */

usage = (char*)malloc(n *sizeof(char));

if (!usage) error(E_NOMEM); /* create a item usage vector */

/* --- check item subsets --- */

while (ist_height(istree) < max && ( ( ismax == -1 && endApriori == false )

|| ist_height(istree) < ismax )

)

{

nbgen = 0 ;

nbfreq = 0 ;

level ++ ;

i = ist_check(istree,usage);/* check current item usage */

if (i < max) max = i; /* update the maximum set size */

if (ist_height(istree) >= i) break;

k = ist_addlvl(istree, nbgen); /* while max. height is not reached, */

if (k < 0) error(E_NOMEM); /* add a level to the item set tree */

if (k != 0) break; /* if no level was added, abort */

if( verbose ) MSG(fprintf(stderr, " %d", ist_height(istree)));

if ((i < n) /* check item usage on current level */

&& (i *(double)tt < 0.1 *n *tc)) {

n = i; x = clock(); /* if items were removed and */

tas_filter(taset, usage); /* the counting time is long enough, */

tat_delete(tatree); /* remove unnecessary items */

tatree = tat_create(taset, 1);

if (!tatree) error(E_NOMEM);

tt = clock() -x; /* rebuild the transaction tree and */

} /* note the new construction time */

x = clock(); /* start the timer */

ist_countx(istree, tatree, nbfreq, istree->supp ); /* count the transaction tree */

tc = clock() -x; /* in the item set tree */

actNfC = 1-double(nbfreq)/double(nbgen) ;

avgNfC = avgNfC + actNfC ;

if( verbose )

{

cout<<" \t Fk : "<

}

bdnsize += nbgen - nbfreq ;

if( level >=4 && ( bdnsize / nbgen < 1.5 ) && ( bdnsize > 100 ) )

{

if( actNfC < ratioNfC )

{

eps = 0 ;

endApriori = true ;

}

else if( actNfC > 0.25 )

endApriori = true ;

}

} /* and note the new counting time */ if( verbose ) MSG(fprintf(stderr, " done [%.2fs].\n", SEC_SINCE(t)));

/* --- filter item sets --- */

t = clock(); /* start the timer */

#ifdef MAXIMAL /* filter maximal item sets */

if( verbose ) MSG(fprintf(stderr, "filtering maximal item sets ... "));

if( ratioNfC == 0 || nbgen < k+1 || ist_height(istree)>= max )

ist_filter2(istree, IST_MAXFRQ, 0);

else

ist_filter2(istree, IST_MAXFRQ, bdn);

if( verbose ) MSG(fprintf(stderr, " done [%.2fs].\n", SEC_SINCE(t))); empty = (n <= 0) ? 1 : 0; /* check whether the empty item set */ #endif /* is maximal */

#ifdef CLOSED /* filter closed item sets */

if( verbose ) MSG(fprintf(stderr, "filtering closed item sets ... "));

ist_filter(istree, IST_CLOSED);

if( verbose ) MSG(fprintf(stderr, " done [%.2fs].\n", SEC_SINCE(t)));

for (k = n; --k >= 0; ) /* check for an item in all t.a. */

if (is_getfrq(itemset, k) == tacnt) break;

empty = (k <= 0) ? 1 : 0; /* check whether the empty item set */ #endif /* is closed */

/* --- print item sets --- */

for (i = ist_height(istree); --i >= 0; )

map[i] = 0; /* clear the item set counters */

if( verbose ) MSG(fprintf(stderr, "writing %s ... ", (fn_out) ? fn_out : ""));

t = clock(); /* start the timer and */

if (fn_out) { /* if an output file is given, */

out = fopen(fn_out, "w"); /* open the output file */

if (!out) error(E_FOPEN, fn_out);

if (empty) fprintf(out, " (%d)\n", tacnt);

} /* report empty item set */

ist_init(istree); /* init. the item set extraction */

set = is_tract(itemset); /* get the transaction buffer */

for (n = empty; 1; n++) { /* extract item sets from the tree */

k = ist_set(istree, set, &supp);

if (k <= 0) break; /* get the next frequent item set */

map[k-1]++; /* count the item set */

if (fn_out) { /* if an output file is given */

for (i = 0; i < k; i++) { /* traverse the items */

fputs(is_name(itemset, set[i]), out);

fputc(' ', out); /* print the name of the next item */

} /* followed by a separator */ fprintf(out, "(%d)\n", supp);

} /* print the item set's support */ else

{

short unsigned * is = new short unsigned[k] ;

for (i = 0; i < k; i++) /* traverse the items */

{

is[i] = set[i] ;

}

if( k < level || nbgen < k+1 || ist_height(istree)>= max )

{

bdPapriori->insert(is, k ,supp ) ;

(*stat)[ 0 ] ++;

(*stat)[ k+1 ]++;

if( maxBdP < k )

maxBdP = k ;

}

else

{

generatedFk = true ;

}

delete[] is;

}

if (fn_out) { /* if an output file is given */

if (fflush(out) != 0) error(E_FWRITE, fn_out);

if (out != stdout) fclose(out);

out = NULL; /* close the output file */

}

if( verbose ) MSG(fprintf(stderr, "[%d set(s)] done ", n));

if( verbose ) MSG(fprintf(stderr, "[%.2fs].\n", SEC_SINCE(t)));

/* --- print item set statistics --- */

k = ist_height(istree); /* find last nonzero counter */

if ((k > 0) && (map[k-1] <= 0)) k--;

if( verbose ){

printf("%d\n", empty); /* print the numbers of item sets */ for (i = 0; i < k; i++) printf("%d\n", map[i]);

}

/* --- clean up --- */

#ifndef NDEBUG /* if this is a debug version */

free(usage); /* delete the item usage vector */ free(map); /* and the identifier map */

ist_delete(istree); /* delete the item set tree, */

if (taset) tas_delete(taset, 0); /* the transaction set, */

is_delete(itemset); /* and the item set */ #endif

return tatree ;

}

数据结构与算法C语言版期末复习题

《数据结构与算法》期末复习题一、选择题。 1．在数据结构中，从逻辑上可以把数据结构分为 C 。 A．动态结构和静态结构B．紧凑结构和非紧凑结构 C．线性结构和非线性结构D．内部结构和外部结构 2．数据结构在计算机内存中的表示是指 A 。 A．数据的存储结构B．数据结构C．数据的逻辑结构D．数据元素之间的关系 3．在数据结构中，与所使用的计算机无关的是数据的 A 结构。 A．逻辑B．存储C．逻辑和存储D．物理 4．在存储数据时，通常不仅要存储各数据元素的值，而且还要存储 C 。 A．数据的处理方法B．数据元素的类型 C．数据元素之间的关系D．数据的存储方法 5．在决定选取何种存储结构时，一般不考虑 A 。 A．各结点的值如何B．结点个数的多少 C．对数据有哪些运算D．所用的编程语言实现这种结构是否方便。 6．以下说法正确的是 D 。 A．数据项是数据的基本单位 B．数据元素是数据的最小单位 C．数据结构是带结构的数据项的集合 D．一些表面上很不相同的数据可以有相同的逻辑结构 7．算法分析的目的是 C ，算法分析的两个主要方面是 A 。（1）A．找出数据结构的合理性B．研究算法中的输入和输出的关系C．分析算法的效率以求改进C．分析算法的易读性和文档性（2）A．空间复杂度和时间复杂度B．正确性和简明性 C．可读性和文档性D．数据复杂性和程序复杂性 8．下面程序段的时间复杂度是O(n2) 。 s =0; for( I =0; i

非常全的C语言常用算法

一、基本算法 1．交换（两量交换借助第三者）例1、任意读入两个整数，将二者的值交换后输出。 main() {int a,b,t; scanf("%d%d",&a,&b); printf("%d,%d\n",a,b); t=a; a=b; b=t; printf("%d,%d\n",a,b);} 【解析】程序中加粗部分为算法的核心，如同交换两个杯子里的饮料，必须借助第三个空杯子。假设输入的值分别为3、7，则第一行输出为3，7；第二行输出为7，3。其中t为中间变量，起到“空杯子”的作用。注意：三句赋值语句赋值号左右的各量之间的关系！【应用】例2、任意读入三个整数，然后按从小到大的顺序输出。 main() {int a,b,c,t; scanf("%d%d%d",&a,&b,&c); /*以下两个if语句使得a中存放的数最小*/ if(a>b){ t=a; a=b; b=t; } if(a>c){ t=a; a=c; c=t; } /*以下if语句使得b中存放的数次小*/ if(b>c) { t=b; b=c; c=t; } printf("%d,%d,%d\n",a,b,c);} 2．累加累加算法的要领是形如“s=s+A”的累加式，此式必须出现在循环中才能被反复执行，从而实现累加功能。“A”通常是有规律变化的表达式，s在进入循环前必须获得合适的初值，通常为0。例1、求1+2+3+……+100的和。 main() {int i,s; s=0; i=1; while(i<=100) {s=s+i; /*累加式*/ i=i+1; /*特殊的累加式*/ } printf("1+2+3+...+100=%d\n",s);} 【解析】程序中加粗部分为累加式的典型形式，赋值号左右都出现的变量称为累加器，其中“i = i + 1”为特殊的累加式，每次累加的值为1，这样的累加器又称为计数器。

C语言经典算法100例(1---30)

2008-02-18 18:48 【程序1】题目：有1、2、3、4个数字，能组成多少个互不相同且无重复数字的三位数？都是多少？ 1.程序分析：可填在百位、十位、个位的数字都是1、2、3、4。组成所有的排列后再去掉不满足条件的排列。 2.程序源代码： main() { int i,j,k; printf("\n"); for(i=1;i<5;i++) ／*以下为三重循环*/ for(j=1;j<5;j++) for (k=1;k<5;k++) { if (i!=k&&i!=j&&j!=k) /*确保i、j、k三位互不相同*/ printf("%d,%d,%d\n",i,j,k); } } ============================================================== 【程序2】题目：企业发放的奖金根据利润提成。利润(I)低于或等于10万元时，奖金可提10%；利润高于10万元，低于20万元时，低于10万元的部分按10%提成，高于10万元的部分，可可提成7.5%；20万到40万之间时，高于20万元的部分，可提成5%；40万到60万之间时高于 40万元的部分，可提成3%；60万到100万之间时，高于60万元的部分，可提成1.5%，高于 100万元时，超过100万元的部分按1%提成，从键盘输入当月利润I，求应发放奖金总数？ 1.程序分析：请利用数轴来分界，定位。注意定义时需把奖金定义成长整型。 2.程序源代码： main() { long int i; int bonus1,bonus2,bonus4,bonus6,bonus10,bonus; scanf("%ld",&i); bonus1=100000*0.1;bonus2=bonus1+100000*0.75; bonus4=bonus2+200000*0.5; bonus6=bonus4+200000*0.3; bonus10=bonus6+400000*0.15; if(i<=100000)

C语言常用算法集合

1.定积分近似计算： /*梯形法*/ double integral(double a,double b,long n) { long i;double s,h,x; h=(b-a)/n; s=h*(f(a)+f(b))/2; x=a; for(i=1;i

} 3.素数的判断： /*方法一*/ for (t=1,i=2;i0;n/=10) k=10*k+n%10; return k; } /*求回文数*/ int f(long n) { long k,m=n; for(k=0;n>0;n/=10) k=10*k+n%10; if(m==k) return 1; return 0; } /*求整数位数*/ int f(long n) { int count; for(count=0;n>0;n/=10) count++; return count; }

c语言经典算法100例

60.题目:古典问题:有一对兔子,从出生后第3个月起每个月都生一对兔子,小兔子长到第三个月后每个月又生一对兔子,假如兔子都不死,问每个月的兔子总数为多少? _________________________________________________________________ _ 程序分析:兔子的规律为数列1,1,2,3,5,8,13,21.... _________________________________________________________________ __ 程序源代码: main() { long f1,f2; int i; f1=f2=1; for(i=1;i<=20;i++) { printf("%12ld %12ld",f1,f2); if(i%2==0) printf("\n");/*控制输出,每行四个*/

f1=f1+f2;/*前两个月加起来赋值给第三个月*/ f2=f1+f2;/*前两个月加起来赋值给第三个月*/ } } 上题还可用一维数组处理,you try! 61.题目:判断101-200之间有多少个素数,并输出所有素数。 _________________________________________________________________ _ 1 程序分析:判断素数的方法:用一个数分别去除2到sqrt(这个数),如果能被整除,则表明此数不是素数,反之是素数。 _________________________________________________________________ __ 程序源代码: #include "math.h" main() { int m,i,k,h=0,leap=1;

C语言常用排序算法

/* ===================================================================== ======== 相关知识介绍（所有定义只为帮助读者理解相关概念，并非严格定义）： 1、稳定排序和非稳定排序简单地说就是所有相等的数经过某种排序方法后，仍能保持它们在排序之前的相对次序，我们就说这种排序方法是稳定的。反之，就是非稳定的。比如：一组数排序前是a1,a2,a3,a4,a5，其中a2=a4，经过某种排序后为 a1,a2,a4,a3,a5，则我们说这种排序是稳定的，因为a2排序前在a4的前面，排序后它还是在a4的前面。假如变成a1,a4, a2,a3,a5就不是稳定的了。 2、内排序和外排序在排序过程中，所有需要排序的数都在内存，并在内存中调整它们的存储顺序，称为内排序；在排序过程中，只有部分数被调入内存，并借助内存调整数在外存中的存放顺序排序方法称为外排序。 3、算法的时间复杂度和空间复杂度所谓算法的时间复杂度，是指执行算法所需要的计算工作量。一个算法的空间复杂度，一般是指执行这个算法所需要的内存空间。 ===================================================================== =========== */ /* ================================================ 功能：选择排序输入：数组名称（也就是数组首地址）、数组中元素个数 ================================================ */ /* ==================================================== 算法思想简单描述：

C语言常用算法程序汇总

C程序设计的常用算法算法（Algorithm）：计算机解题的基本思想方法和步骤。算法的描述：是对要解决一个问题或要完成一项任务所采取的方法和步骤的描述，包括需要什么数据（输入什么数据、输出什么结果）、采用什么结构、使用什么语句以及如何安排这些语句等。通常使用自然语言、结构化流程图、伪代码等来描述算法。一、简单数值类算法此类问题都要使用循环，要注意根据问题确定循环变量的初值、终值或结束条件，更要注意用来表示计数、和、阶乘的变量的初值。 1、求阶乘：n!=1*2*384…..*n; n!= n*(n-1)!= 下列程序用于求n的阶乘.在累乘之前,一定要将用于存放乘积的变量的值初始化为1. long func(int n) { int i; long t=1; for(i=2;i<=n;i++) t*=i; return t; }

printf("\n"); } main() { int n; scanf("%d", &n); printf("n!=%ld\n", fac(n)); } 2、整数拆分问题：把一个整数各个位上的数字存到数组中 #define N 4 /* N代表整数位数*/ viod split(int n, int a[ ]） /* 1478: a[ 3]=8, a[2 ]=7, a[1 ]=4…*/ {int i; for(i=N-1;i!=0; i--) { a[i]=n%10; n=n/10; } } main() {int i,m=1478,b[N-1]; split(m, b）; for(i=0;i<4; i++) printf(“%5d”, b[i]);

(整理)C语言常用算法.

八、常用算法（一）考核知识要点 1．交换、累加、累乘、求最大（小）值 2．穷举 3．排序（冒泡、插入、选择） 4．查找（顺序、折半） 5．级数计算（递推法） 6．一元方程求解（牛顿迭代法、二分法） 7．矩阵（转置） 8．定积分计算（矩形法、梯形法） 9．辗转相除法求最大公约数、判断素数 10．数制转换（二）重点、难点精解教材中给出的算法就不再赘述了。 1．基本操作：交换、累加、累乘 1）交换交换算法的要领是“借助第三者”（如同交换两个杯子里的饮料，必须借助第三个空杯子）。例如，交换两个整型变量里的数值：int a=7,b=9,t; t=a; a=b; b=t; (不借助第三者，也能交换两个整型变量里的数值，但不通用，只是一个题目而已。例如：int a=7,b=9; a=a+b; b=a-b; a=a-b;) 2）累加累加算法的要领是形如“s=s+A”的累加式，此式必须出现在循环中才能被反复执行，从而实现累加功能。“A”通常是有规律变化的表达式，s在进入循环前必须获得合适的初值，通常为0。 3）累乘累乘算法的要领是形如“s=s*A”的累乘式，此式必须出现在循环中才能被反复执行，从而实现累乘功能。“A”通常是有规律变化的表达式，s在进入循环前必须获得合适的初值，通常为1。 2．非数值计算常用经典算法 1）穷举法也称为“枚举法”，即将可能出现的各种情况一一测试，判断是否满足条件，一般采用循环来实现。例如，用穷举法输出“将1元人民币兑换成1分、2分、5分硬币”的所有方法。 main() {int y,e,w; for(y=0;y<=100;y++) for(e=0;e<=50;e++) for(w=0;w<=20;w++)

数据结构(C语言版)实验报告-(内部排序算法比较)

《数据结构与算法》实验报告一、需求分析问题描述：在教科书中，各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶，或大概执行时间。试通过随机数据比较各算法的关键字比较次数和关键字移动次数，以取得直观感受。基本要求：（l）对以下6种常用的内部排序算法进行比较：起泡排序、直接插入排序、简单选择排序、快速排序、希尔排序、堆排序。（2）待排序表的表长不小于100000；其中的数据要用伪随机数程序产生；至少要用5组不同的输入数据作比较；比较的指标为有关键字参加的比较次数和关键字的移动次数（关键字交换计为3次移动）。（3）最后要对结果作简单分析，包括对各组数据得出结果波动大小的解释。数据测试：二．概要设计 1.程序所需的抽象数据类型的定义： typedef int BOOL; //说明BOOL是int的别名 typedef struct StudentData { int num; //存放关键字} Data; typedef struct LinkList { int Length; //数组长度 Data Record[MAXSIZE]; //用数组存放所有的随机数 } LinkList int RandArray[MAXSIZE]; //定义长度为MAXSIZE的随机数组void RandomNum() //随机生成函数

void InitLinkList(LinkList* L) //初始化链表 BOOL LT(int i, int j,int* CmpNum) //比较i和j 的大小 void Display(LinkList* L) //显示输出函数 void ShellSort(LinkList* L, int dlta[], int t,int* CmpNum, int* ChgNum) //希尔排序 void QuickSort (LinkList* L, int* CmpNum, int* ChgNum) //快速排序 void HeapSort (LinkList* L, int* CmpNum, int* ChgNum) //堆排序 void BubbleSort(LinkList* L, int* CmpNum, int* ChgNum) //冒泡排序 void SelSort(LinkList* L, int* CmpNum, int* ChgNum) //选择排序 void Compare(LinkList* L,int* CmpNum, int* ChgNum) //比较所有排序 2 .各程序模块之间的层次（调用）关系：

C语言常用算法2

打印金字塔和三角形使用 * 建立三角形 * * * * * * * * * * * * * * * 源代码： #include int main() { int i,j,rows; printf("Enter the number of rows: "); scanf("%d",&rows); for(i=1;i<=rows;++i) { for(j=1;j<=i;++j) { printf("* "); } printf("\n"); } return 0; } 如下图所示使用数字打印半金字塔 1 1 2 1 2 3 1 2 3 4 1 2 3 4 5 源代码： #include int main() { int i,j,rows; printf("Enter the number of rows: "); scanf("%d",&rows); for(i=1;i<=rows;++i) { for(j=1;j<=i;++j) { printf("%d ",j); } printf("\n"); } return 0; } 用 * 打印半金字塔 * * * * * * * * * * * * * * * 源代码： #include int main() { int i,j,rows; printf("Enter the number of rows: "); scanf("%d",&rows); for(i=rows;i>=1;--i) { for(j=1;j<=i;++j) { printf("* "); } printf("\n"); } return 0; } 用 * 打印金字塔 * * * * * * * * * * * * * * * * * * * * * * * * * 源代码： #include int main() { int i,space,rows,k=0; printf("Enter the number of rows: "); scanf("%d",&rows); for(i=1;i<=rows;++i) { for(space=1;space<=rows-i;++space) { printf(" "); } while(k!=2*i-1) { printf("* "); ++k; } k=0; printf("\n"); } return 0; } 用 * 打印倒金字塔 * * * * * * * * * * * * * * * * * * * * * * * * * 源代码： #include int main() { int rows,i,j,space; printf("Enter number of rows: "); scanf("%d",&rows); for(i=rows;i>=1;--i) { for(space=0;space int prime(int n); int main() { int n, i, flag=0; printf("Enter a positive integer: "); scanf("%d",&n); for(i=2; i<=n/2; ++i) { if (prime(i)!=0) { if ( prime(n-i)!=0) { printf("%d = %d + %d\n", n, i, n-i); flag=1; } } } if (flag==0) printf("%d can't be expressed as sum of two prime numbers.",n); return 0; } int prime(int n) /* Function to check prime number */ { int i, flag=1; for(i=2; i<=n/2; ++i) if(n%i==0) flag=0; return flag; } 用递归的方式颠倒字符串源代码： /* Example to reverse a sentence entered by user without using strings. */ #include void Reverse(); int main() { printf("Enter a sentence: "); Reverse(); return 0; } void Reverse() { char c; scanf("%c",&c); if( c != '\n') { Reverse(); printf("%c",c); } } 实现二进制与十进制之间的相互转换 #include #include int binary_decimal(int n); int decimal_binary(int n); int main() { int n; char c; printf("Instructions:\n"); printf("1. Enter alphabet 'd' to convert binary to decimal.\n"); printf("2. Enter alphabet 'b' to convert decimal to binary.\n"); scanf("%c",&c); if (c =='d' || c == 'D') { printf("Enter a binary number: "); scanf("%d", &n); printf("%d in binary = %d in decimal", n, binary_decimal(n)); } if (c =='b' || c == 'B') { printf("Enter a decimal number: "); scanf("%d", &n); printf("%d in decimal = %d in binary", n, decimal_binary(n)); } return 0; } int decimal_binary(int n) /* Function to convert decimal to binary.*/ { int rem, i=1, binary=0; while (n!=0) { rem=n%2; n/=2; binary+=rem*i; i*=10; } return binary; } int binary_decimal(int n) /* Function to convert binary to decimal.*/ { int decimal=0, i=0, rem; while (n!=0) { rem = n%10; n/=10; decimal += rem*pow(2,i); ++i; } return decimal;

C语言常考算法归纳

C语言常考算法归纳应当掌握的一般算法一、基本算法：交换、累加、累乘二、非数值计算常用经典算法：穷举、排序（冒泡，选择，插入，归并）、查找（顺序即线性，折半）三、数值计算常用经典算法：级数计算（直接、简接即递推）、一元非线性方程求根（牛顿迭代法、二分法）、定积分计算（矩形法、梯形法）、矩阵转置、矩阵相乘四、其他：迭代、进制转换、字符处理（统计、数字串、字母大小写转换、加密等）、整数各数位上数字的获取、辗转相除法求最大公约数（最小公倍数）、求最值、判断素数（各种变形）、数组元素的插入（删除）、二维数组的其他典型问题（方阵的特点、杨辉三角形）详细讲解一、基本算法 1．交换（两量交换借助第三者）例1、任意读入两个整数，将二者的值交换后输出。 main() {int a,b,t; scanf("%d%d",&a,&b); printf("%d,%d\n",a,b); t=a; a=b; b=t; printf("%d,%d\n",a,b);} 【解析】程序中加粗部分为算法的核心，如同交换两个杯子里的饮料，必须借助第三个空杯子。假设输入的值分别为3、7，则第一行输出为3，7；第二行输出为7，3。其中t为中间变量，起到“空杯子”的作用。注意：三句赋值语句赋值号左右的各量之间的关系！【应用】例2、任意读入三个整数，然后按从小到大的顺序输出。 main() {int a,b,c,t; scanf("%d%d%d",&a,&b,&c); /*以下两个if语句使得a中存放的数最小*/ if(a>b){ t=a; a=b; b=t; } if(a>c){ t=a; a=c; c=t; } /*以下if语句使得b中存放的数次小*/ if(b>c) { t=b; b=c; c=t; }

数据结构C语言版常用算法思想汇总

dijkstra 迪杰斯特拉单源最短路径，必须给出源点V0 邻接矩阵cost存储有向网；使用一个集合S存储那些已经找到最短路径的顶点，初始只包含源点v0；设置两个数组dis[n]、pre[n]，数组dist记录从源点到其余各顶点当前的最短路径，初始时dis[i]=cost[v0][i];数组pre存储最短路径上终点v之前的那个顶点，初始时pre[i]=v0;具体过程是从v-s中找一个w,使dis[w]最小，将w加入到s中，然后以w 作为新考虑的中间点，对s集合以外的每个顶点I,比较dis[w]+cost[w][j]与dis[i]的大小,若前者小于后者，表明加入了新的中间点w之后，从v0通过w到i的路径比原来的短，应该用它替换dis[i]的原值，使dis[i]始终保持目前为止最短的路径，若dis[w]+cost[w][j]所对应的权值，将其记为D（-1）,其数组元素不一定是vi到vj的最短路径，要想求得最短路径，还需进行n次试探。在矩阵D（-1）的基础上，对于要从顶点vi到vj的最短路径，首先考虑让路径经过顶点vo，比较和的路径长度，取其短者为当前求得的最短路径。对每一对顶点都做这样的试探，可求得矩阵D0。然后在D0的基础上，让路径通过v1，得到新的矩阵D1.以此类推，一般的，如果顶点vi到vj的路径经过顶点vk时的路径缩短，则修改Dk[i][j]=D(k-1)[i][k]+D(k-1)[k][j]，所以D(k)[i][j]就是当前求得的从顶点vi到vj 的最短路径，且其路径上的顶点，除了源点和终点外，序号都不大于k。这样经过n次试探，最后求得的矩阵D（n-1）就一定是各顶点间的最短路径。 floydputpath弗洛伊德算法floyd函数中用到的函数矩形path是用来存储最短路径上的顶点信息的。矩阵path初始时都赋值为-1，表示vi到vj 的最短路径是直接可达的，中间不需经过其他顶点。以后，当考虑路径经过某个顶点vk时，如果使路径更短，在修改D(k-1)[i][j]的同时修改path[i][j]为k，即path[i][j]中存放的是从vi 到vj路径上所经过的某个顶点(若path[i][j]!=-1)。经过n次探查后，path[i][j]=k,即从vi到vj 的最短路径经过顶点vk，该路径上还有哪些顶点呢，需要去查看path[i][j],以次类推，直到所查元素为-1为止。 prim 普里姆算法最小生成树算法，比如要在n个城市间建立通信网，则连接n个城市需要n-1条线路，如何在最节省经费的情况下建立这个通信网？基本思想：假设G=(V,E)是连通网，T=(U,TE)为欲构造的最小生成树（1）初始时令U={1}(即构造最小生成树时，从顶点1出发)，TE=空（2）从所有u属于U,v属于V-U的边中，选取具有最小权值的边(u,v)，将顶点v加入集合U中，将(u,v)加入集合TE中。（3）重复(2)，直到U=V为止。

快速幂算法C语言版(超详细)

快速幂取模算法在网站上一直没有找到有关于快速幂算法的一个详细的描述和解释，这里，我给出快速幂算法的完整解释，用的是C 语言，不同语言的读者只好换个位啦，毕竟读C 的人较多~ 所谓的快速幂，实际上是快速幂取模的缩写，简单的说，就是快速的求一个幂式的模(余)。在程序设计过程中，经常要去求一些大数对于某个数的余数，为了得到更快、计算范围更大的算法，产生了快速幂取模算法。[有读者反映在讲快速幂部分时有点含糊，所以在这里对本文进行了修改，作了更详细的补充，争取让更多的读者一目了然] 我们先从简单的例子入手：求c a b mod = 几。算法1.首先直接地来设计这个算法： int ans = 1; for (int i = 1;i<=b;i++) { ans = ans * a; } ans = ans % c; 这个算法的时间复杂度体现在for 循环中，为O （b ）.这个算法存在着明显的问题，如果a 和b 过大，很容易就会溢出。那么，我们先来看看第一个改进方案：在讲这个方案之前，要先有这样一个公式： c c a c a b b mod )mod (mod =.这个公式大家在离散数学或者数论当中应该学过，不过这里为了方便大家的阅读，还是给出证明：引理1： c c b c a c de c de c dk te tkc c e kc d tc c ab e kc b e c b d tc a d c a c c b c a c ab mo d )]mod ()mod [(mod mod ))((mod ))((mod mod mod mod )]mod ()mod [(mod )(:2?==+++=++=+=?=+=?=?=证明：公式上面公式为下面公式的引理，即积的取余等于取余的积的取余。 c a c c a c c c a c c a c c a c a b b b b b b mo d mod ])mod [() (mod ])mod )mod [((mod ])mod [(mod )mod (mod ===由上面公式的迭代证明：公式：证明了以上的公式以后，我们可以先让a 关于c 取余，这样可以大大减少a 的大小，于是不用思考的进行了改进：算法2： int ans = 1; a = a % c; //加上这一句

C语言常用算法程序汇总

C 程序设计的常用算法算法( Algorithm )：计算机解题的基本思想方法和步骤。算法的描述：是对要解决一个问题或要完成一项任务所采取的方法和步骤的描述，包括需要什么数据(输入什么数据、输出什么结果)、采用什么结构、使用什么语句以及如何安排这些语句等。通常使用自然语言、结构化流程图、伪代码等来描述算法。一、简单数值类算法此类问题都要使用循环，要注意根据问题确定循环变量的初值、终值或结束条件，更要注意用来表示计数、和、阶乘的变量的初值。 1、求阶乘：n!=1*2*384 …..*n; n!= n*(n-1)!= 下列程序用于求n 的阶乘.在累乘之前,一定要将用于存放乘积的变量的值初始化为1. long func(int n) { int i; long t=1; for(i=2;i<=n;i++) t*=i; return t; }

printf("\n"); } main() { int n; scanf("%d", &n); printf("n!=%ld\n", fac(n)); } 2、整数拆分问题：把一个整数各个位上的数字存到数组中 #define N 4 /* N 代表整数位数*/ viod split(int n, int a[ ] ) /* 1478: a[ 3]=8, a[2 ]=7, a[1 ]=4 …*/ {int i; for(i=N-1;i!=0; i--) { a[i]=n%10; n=n/10; } } main() {int i,m=1478,b[N-1]; split(m, b) ; for(i=0;i<4; i++) printf( “%5d”, b[i]); } 3、求整数的因子之和12=1*2*3*4 long factor(int n) {int i; long sum=0;

C语言经典算法100例

C 语言经典算法100 例(1) (2007-08-15 15:09:22) C 语言编程经典100 例【程序1】题目：有1、2、3、4 个数字，能组成多少个互不相同且无重复数字的三位数？都是多少？ 1. 程序分析：可填在百位、十位、个位的数字都是1、2、3、4。组成所有的排列后再去掉不满足条件的排列。 2. 程序源代码： main() { int i,j,k; printf( “\n “); for(i=1;i 〈5;i++) ／* 以下为三重循环*/ for(j=1;j 〈5;j++) for (k=1;k 〈5;k++) { if (i!=k&&i!=j&&j!=k) /* 确保i 、j 、k 三位互不相同*/ printf( “ %d,%d,%d\n“,i,j,k); } } 【程序2】题目：企业发放的奖金根据利润提成。利润(I)低于或等于10万元时，奖金可提10%利润高于10万元，低于20万元时，低于10万元的部分按10%提成，高于10 万元的部分，可可提成7.5%；20万到40万之间时，高于20万元的部分，可提成5%；40 万到60 万之间时高于40万元的部分，可提成3%；60万到100万之间时，高于60 万元的部分，可提成1.5%，高于100万元时，超过100万元的部分按19提成，从键盘输入当月利润I，求应发放奖金总数？ 1. 程序分析：请利用数轴来分界，定位。注意定义时需把奖金定义成长整型。 2. 程序源代码： main() { long int i; int bonus1,bonus2,bonus4,bonus6,bonus10,bonus; scanf( “%ld“ ,&i); bonus1=100000*0.1;bonus2=bonus1+100000*0.75; bonus4=bonus2+200000*0.5; bonus6=bonus4+200000*0.3; bonus10=bonus6+400000*0.15; if(i 〈=100000) bonus=i*0.1; else if(i 〈=200000) bonus=bonus1+(i-100000)*0.075; else if(i 〈=400000) bonus=bonus2+(i-200000)*0.05; else if(i 〈=600000) bonus=bonus4+(i-400000)*0.03; else if(i 〈=1000000) bonus=bonus6+(i-600000)*0.015; else bonus=bonus10+(i-1000000)*0.01; printf( “ bonus=%d“ ,bonus);

Apriori算法C语言源代码实现

数据结构与算法C语言版期末复习题

非常全的C语言常用算法

C语言经典算法100例(1---30)

C语言常用算法集合

最新C语言常用算法集合汇总

c语言经典算法100例

C语言常用排序算法

最新C语言常用算法归纳

C语言常用算法程序汇总

(整理)C语言常用算法.

数据结构(C语言版)实验报告-(内部排序算法比较)

C语言常用算法2

C语言常考算法归纳

数据结构C语言版常用算法思想汇总

快速幂算法C语言版(超详细)

C语言常用算法程序汇总

C语言经典算法100例