模式识别c语言ISODATA算法

c语言编写的ISODATA程序

#include

#include

#include

#include

#include

#include

#define MAXNUM 100 //最大模式个数

#define MAXDIM 10 //最大模式维数

#define K 0.5 //分裂时使用的比值

#define MAXDOUBLE 1.0e20 //最大双精度值

#define N 10 //实际模式个数

#define DIM 2 //实际模式维数

struct Pattern //模式结构体

{

int n; //模式序号

float s[MAXDIM]; //模式数据

};

struct Cluster //类结构体

{

struct Pattern z; //类中心

int n; //类中包含的模式数目

float avg_d; //模式到类心的平均距离

struct Pattern y[MAXNUM]; //模式

float sigma[MAXDIM]; //分量的标准差

int max; //用于记录类内距离标准差矢量最大的分量下标

float sigma_max; //类内分量距离标准差最大值

};

struct Pattern InitPattern(int i,float a,float b) //对样本模式进行初始化

{

struct Pattern temp;

temp.n=i;

temp.s[0]=a;

temp.s[1]=b;

return temp;

}

//以下为各参数声明

int c=3; //预期的类数

int Nc=1; //初始聚类中心个数

int ON=1; //每一类中允许的最少模式数（小于此数不可单独成类）

float OS=1; //类内分量分布的标准差上限（大于此数就分裂）

float OC=4; //两类中心间的最小距离下限（小于此数两类合并）

int L=1; //在每次迭代中可以合并的类的最大对数

int I=8; //最多迭代次数

struct Pattern x[N]; //全部模式

struct Cluster w[N]; //全部类

float D[MAXNUM][MAXNUM]; //各类对中心间的距离

float dis; //总体平均距离

int iter=1; //记录迭代次数

int i,j; //循环变量

//以下为程序用到的调用函数

void Init();

void ISODATA();

void InitCenter();

void Clustering();

float Distance(struct Pattern x1,struct Pattern x2);

struct Cluster Insert(struct Pattern a,struct Cluster

b);

int CheckAndUnion();

void CalParameter();

struct Pattern CalCenter(struct Cluster a);

float Cal_D(int i);

void CalSigma();

int divide();

void CalCenterDis();

int UnionByOC();

void Union(int a,int b);

void PrintCluster();

void main()

{

Init();

printf("\n****************** ISODATA 算法程序

**************************\n");

printf("本实验使用样本集如下：\n");

x[0]=InitPattern(0,0,0);

x[1]=InitPattern(1,3,8);

x[2]=InitPattern(2,2,2);

x[3]=InitPattern(3,1,1);

x[4]=InitPattern(4,5,3);

x[5]=InitPattern(5,4,8);

x[6]=InitPattern(6,6,3);

x[7]=InitPattern(7,5,4);

x[8]=InitPattern(8,6,4);

x[9]=InitPattern(9,7,5);

for(i=0;i

{

printf("\tX (%d): (",x[i].n);

for(j=0;j

printf("%3.2f,",x[i].s[j]);

printf("%3.2f);\n",x[i].s[j]);

}

ISODATA(); //ISODAT A聚类程序

system("pause");

}

void Init() //对两结构体变量初始化（赋零值）

{

int i,j,k,l;

for(i=0;i

{

x[i].n=0;

w[i].n=0;

w[i].avg_d=0;

w[i].max=0;

w[i].sigma_max=0;

w[i].z.n=0;

for(j=0;j

{

x[i].s[j]=0;

w[i].sigma[j]=0;

w[i].z.s[j]=0;

for(k=0;k

{

w[i].y[k].n=0;

for(l=0;l

w[i].y[k].s[l]=0;

}

}

for(i=0;i

for(j=0;j

D[i][j]=0;

}

void InitCenter() //按序号选定初始聚类中心

{

int i,j,k,l;

for(j=0;j

{

w[j].z=x[j];

w[j].z.n=0;

}

}

void Clustering() //依最小距离原则将全部模式归类

{

float temp=0.0,min=MAXDOUBLE;

int i,j,l=0;

for(j=0;j

{

w[j].n=0;

w[j].z.n=0;

}

for(i=0;i

{

min=MAXDOUBLE;

l=0;

for(j=0;j

{

temp=Distance(x[i],w[j].z);

if(min>temp)

{

min=temp;

l=j;

}

}

w[l]=Insert(x[i],w[l]);

}

}

float Distance(struct Pattern x1,struct Pattern x2) //计算两个模式距离的函数

{

int i;

float temp=0.0;

for(i=0;i

temp+=(x1.s[i]-x2.s[i])*(x1.s[i]-x2.s[i]);

return sqrt(temp);

}

struct Cluster Insert(struct Pattern a,struct Cluster b) //将某模式插入对应类

{

b.n++;

b.y[b.n-1]=a;

return b;

}

int CheckAndUnion() //依据ON判断合并，若类w[j]中模式数小于ON，取消类心，Nc=Nc-1,转至step2:

{

int j=0,k;

do

{

if(w[j].n

{

for(k=j;k

w[k].z=w[k+1].z;

Nc--;

return 1;

j++;

}while(j

return 0;

}

struct Pattern CalCenter(struct Cluster a) //计算类心

{

int i,j;

struct Pattern temp;

for(j=0;j

temp.s[j]=0;

temp.n=0;

for(i=0;i

{

for(j=0;j

temp.s[j]+=a.y[i].s[j];

}

for(i=0;i

{

temp.s[i]/=a.n;

}

return temp;

}

float Cal_D(int j) //计算各模式到类心的平均距离{

int i;

float avg_d=0.0;

for(i=0;i

avg_d+=Distance(w[j].y[i],w[j].z);

avg_d/=w[j].n;

w[j].avg_d=avg_d;

return avg_d;

}

void CalParameter() //计算分类后参数：各类中心、类内平均距离以及总体平均距离

{

int i;

struct Pattern temp;

dis=0.0;

for(i=0;i

{

dis+=w[i].n*Cal_D(i);

}

dis/=N;

}

void CalSigma() //计算各类类内距离的标准差矢量

{

int i,j,k;

for(j=0;j

{

for(k=0;k

{

float temp=0.0;

for(i=0;i

{

struct Pattern z;

//z=CalCenter(w[j]);

temp+=(w[j].y[i].s[k]-w[j].z.s[k])*(w[j].y[i].s[k]-w[j].z.s[k]); }

w[j].sigma[k]=sqrt(temp/w[j].n);

if(w[j].sigma_max

{

w[j].sigma_max=w[j].sigma[k];

w[j].max=k;

}

}

}

}

int divide() //判断分裂

{

int i,j,l;

for(j=0;j

{

float sigma_temp=w[j].sigma_max;

if((w[j].avg_d>dis)&&(w[j].n>2*(ON+1))||(Nc<=c/2))

{

i=w[j].max;

for(l=Nc;l>j;l--)

w[l].z=w[l-1].z;

w[j+1].z.s[i]-=K*sigma_temp;

w[j].z.s[i]+=K*sigma_temp;

Nc++;

return 1;

}

}

return 0;

}

void CalCenterDis() //计算各类对中心间的距离

{

int i,j;

for(i=0;i

for(j=i+1;j

D[i][j]=Distance(w[i].z,w[j].z);

}

void Union(int a,int b) //当两类未合并过时，进行合并

{

int i;

if((w[a].z.n<0)||(w[b].z.n<0))

return ;

for(i=0;i

w[a].z.s[i]=(1/(w[a].n+w[b].n))*(w[a].z.s[i]*w[a].n+w[b].n*w[b].z.s [i]);

w[a].z.n=-1;

w[b].z.n=-2;

}

int UnionByOC() //依据OC 判断合并

{

int i,j,k,l;

int num=0;

int flag=0;

struct

{

float d;

int i;

int j;

}Dmin[N];

for(i=0;i

{

Dmin[i].d=OC;

Dmin[i].i=-1;

Dmin[i].j=-1;

}

for(i=0;i

for(j=i+1;j

if(D[i][j]

for(k=0;k

if(D[i][j]

{

for(l=L-1;l>k;l--)

Dmin[l]=Dmin[l-1];

Dmin[k].d=D[i][j];

Dmin[k].i=i;

Dmin[k].j=j;

break;

}

for(i=0;i

if(Dmin[i].i>-1&&Dmin[i].j>-1) {

Union(Dmin[i].i,Dmin[i].j); flag=1;

}

for(j=0;j

{

if(w[j].z.n==-2)

{

for(k=j;k

w[k].z=w[k+1].z;

Nc--;

}

}

return flag;

}

void

PrintCluster() //打印当前模式分类情况

{

int i,j,k;

printf("---------------总共分为 %d 类------------------\n",Nc);

for(i=0;i

{

printf("\t第 %d 类类心为：(",i+1);

for(j=0;j

printf("%3.2f,",w[i].z.s[j]);

printf("%3.2f )\n",w[i].z.s[DIM-1]);

printf("包含的模式为：\n");

for(k=0;k

{

printf("\tX (%d):(",w[i].y[k].n);

for(j=0;j

printf("%3.2f,",w[i].y[k].s[j]);

printf("%3.2f)\n",w[i].y[k].s[DIM-1]);

}

printf("\n");

}

}

void ISODATA()

{

int changed=1;

int i;

start: //读入参数

printf("\n设定聚类分析控制参数：\n");

printf("预期的类数 c：");

scanf("%d",&c);

printf("初始聚类中心个数Nc（可不等于c）：");

scanf("%d",&Nc);

printf("每一类中允许的最少模式数目ON（小于此数不可单独成类）："); scanf("%d",&ON);

printf("类内各分量分布的标准差上限OS（大于此数就分裂）：");

scanf("%4f",&OS);

printf("两类中心间的最小距离下限OC（小于此数两类合并）：");

scanf("%4f",&OC);

printf("在每次迭代中可以合并的类的最多对数L： "); scanf("%d",&L);

printf("最多迭代次数I： ");

scanf("%d",&I);

printf("\n");

step1:

InitCenter();

step2:

changed=0;

Clustering();

if(iter==0)

printf("\n---------------选取初始聚类中心---------------\n");

else

printf("-----------------第 %d 次迭代-----------------\n ",iter); PrintCluster();

step3:

if(CheckAndUnion())

goto step2;

step4:

for(i=0;i

{

w[i].z=CalCenter(w[i]); //计算聚类中心

}

CalParameter(); //每个聚类的样本离开其中心的平均距离以及所有样本离开其相应聚类中心的平均距离

step5: //依据iter,Nc判断停止、分裂还是合并

if(iter==I)

{

OC=0;

goto step8;

}

if (Nc<=c/2)

goto step6;

if((Nc>=2*c)||iter%2==0)

goto step8;

step6:

CalSigma();

step7:

if(divide())

{

iter++;

goto step2;

}

step8:

CalCenterDis();

step9:

if(UnionByOC())

changed=1;

step10:

if(iter>=I) //判断循环还是退出 {

printf("---------------经过 %d 次迭代，达到迭代次数

--------------\n",iter);

return;

}

else

{

if(changed==1)

{

char ch;

iter++;

printf("本次迭代完成，是否需要改变参数（Y/N）？？：");

while(!isspace(ch=getchar()));

if(ch=='y'||ch=='Y')

goto start;

else goto step2;

}

else

{

iter++;

goto step2;

}

}

}

数据结构与算法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

数据结构课后作业答案

1. 画出下图所示的无向图的邻接表。列出深度优先和广度优先搜索 遍历该图所的顶点序列和边的序列。 邻接表： 深度优先搜索：顶点序列：1 -2 -3- 4- 5 -6 边的序列：（1，2） （2，3） （3，4） （4，5） （5，6） 广度优先搜索：顶点序列：1 -2 -3 -6 -5-4 边的序列：（1，2） （1，3） （1，6） （1，5） （5，4） 2 已知以二维数组表示的图的邻接矩阵如下图所示。试分别画出自顶点1出发进 行遍历所得的深度优先生成树和广度优先生成树。 1 2 3 4 5 6 7 8 9 10 1 0 0 0 0 0 0 1 0 1 0 2 0 0 1 0 0 0 1 0 0 0 3 0 0 0 1 0 0 0 1 0 0 4 0 0 0 0 1 0 0 0 1 0 5 0 0 0 0 0 1 0 0 0 1 6 1 1 0 0 0 0 0 0 0 0 7 0 0 1 0 0 0 0 0 0 1 1 5 2 4 6 3

8 1 0 0 1 0 0 0 0 1 0 9 0 0 0 0 1 0 1 0 0 1 10 1 0 0 0 0 1 0 0 0 0 解：邻接矩阵所表示的图如下： 自顶点1出发进行遍历所得的深度优先生成树： 自顶点1出发进行遍历所得的广度优先生成树：

3 请对下图的无向带权图 （1）写出它的邻接矩阵，并按普里母算法求其最小生成树。 （2）写出它的邻接表，并按克鲁斯卡尔算法求其最小生成树。 解：（1） 邻接矩阵： ∞ 4 3 ∞ ∞ ∞ ∞ ∞ 4 ∞ 5 5 9 ∞ ∞ ∞ 3 5 ∞ 5 ∞ ∞ ∞ 5 ∞ 5 5 ∞ 7 6 5 4 ∞ 9 ∞ 7 ∞ 3 ∞ ∞ ∞ ∞ ∞ 6 3 ∞ 2 ∞ ∞ ∞ ∞ 5 ∞ 2 ∞ 6 ∞ ∞ 5 4 ∞ ∞ 6 ∞ 普里母算法求得的最小生成树： 7 5 9 6 4 5 6 3 5 5 3 4 e d 2 5 c b h f g a

克鲁斯卡尔算法求最小生成树

目录 1.需求分析 (2) 1.1 设计题目 (2) 1.2 设计任务及要求 (2) 1.3课程设计思想 (2) 1.4 程序运行流程 (2) 1.5软硬件运行环境及开发工具 (2) 2.概要设计 (2) 2.1流程图 (2) 2.2抽象数据类型MFSet的定义 (3) 2.3主程序 (4) 2.4抽象数据类型图的定义 (4) 2.5抽象数据类型树的定义 (5) 3.详细设计 (7) 3.1程序 (7) 4.调试与操作说明 (10) 4.1测试结果 (10) 4.2调试分析 (11) 5.课程设计总结与体会 (11) 5.1总结 (11) 5.2体会 (11) 6. 致谢 (12) 7. 参考文献 (12)

1.需求分析 1.1 设计题目：最小生成树 1.2 设计任务及要求：任意创建一个图，利用克鲁斯卡尔算法，求出该图的最小生成树。 1.3 课程设计思想：Kruskal算法采用了最短边策略(设G=(V,E)是一个无向连通网，令T=(U，TE)是G的最小生成树。最短边策略从TE={}开始，每一次贪心选择都是在边集E中选择最短边(u,v)，如果边(u,v)加入集合TE中不产生回路，则将边(u,v)加入边集TE中，并将它在集合E中删去。)，它使生成树以一种任意的方式生长，先让森林中的树木随意生长，每生长一次就将两棵树合并，最后合并成一棵树。 1.4程序运行流程: 1)提示输入顶点数目； 2)接受输入，按照项目要求产生边权值的随机矩阵；然后求解最小生成树； 3)输出最小生成树并且退出； 1.5 软硬件运行环境及开发工具：VC 2.概要设计 2.1流程图

图1流程图 2.2抽象数据类型MFSet的定义： ADT MFSet { 数据对象：若设S是MFSet型的集合，则它由n(n>0)个子集Si（i = 1,2...,n）构成，每个子集的成员代表在这个子集中的城市。 数据关系：S1 U S2 U S3 U... U Sn = S, Si包含于S（i = 1,2,...n） Init (n): 初始化集合，构造n个集合，每个集合都是单成员，根是其本身。rank 数组初始化0 Find(x):查找x所在集合的代表元素。即查找根，确定x所在的集合，并路径压缩。 Merge(x, y):检查x与y是否在同一个集合，如果在同一个集合则返回假，否则按秩合并这两个集合并返回真。 }

非常全的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，这样的累加器又称为计数器。

(二)作业

说明： 上机作业3道，10分 平时作业13道，10分 上机时间：第4、6、7周周六6:00-9:00 综合楼机房412 交上机作业时间：第5、7、8周周五截止。 上机作业格式：主题输入学号+姓名+第X次上机作业 平时作业：必须提交手写板 10月7日提交1-10题 10月31日提交11-13题 所有作业请按时交纳，不收补交作业。 1.设计一个非递归算法，从一棵二叉树中查找出所有结点的最大值并返回。 2.设树采用定长结点的多重链表表示，设计算法实现树的按层次遍历。 3.阅读下列算法，若有错，改正之。 BiTree InSucc(BiTree q) { // 已知q是指向中序线索二叉树上某个结点的指针， // 本函数返回指向*q的后继的指针。 r = q->rchild; if (r -> rtag==0 ) while (!r -> rtag ) r = r->rchild return r; } 4.写出二叉树的先序遍历和后序遍历的非递归算法。 5.设计一个非递归算法，计算树的叶子结点数。（要求说明树的存储方式） 6.已知带权无向图如图所示： (1). 根据普里姆（Prim）算法，设计算法,求它的从顶点a出发的最小生成树； (2). 根据克鲁斯卡尔（Kruskal）算法，求该图的最小生成树,给出添加边次序。 7．已知带权有向图如图所示： (1). 画出该图的邻接矩阵存储结构； (2). 求从顶点a到其余各顶点之间的最短路经及最短路经长度，并给出计算过程。

8．列出图中全部可能的拓扑有序序列，并指出应用7.5.1节中算法Topological Sort算法求得的是哪一个序列？ 9．对下图所示AOE网络，计算各活动弧的e(ai)和l（ai）函数值，各事件（顶点）的ve(vi)和vl(vi)函数值，列出各条关键路径。 10．试利用Floyd算法求图中所示有向图中各顶点之间的最短路径。（求解过程）

Kruskal算法求最小生成树

荆楚理工学院 课程设计成果 学院:_______计算机工程学院__________ 班级: 14计算机科学与技术一班 学生姓名: 志杰学号: 2014407020137 设计地点（单位）_____B5101_________ ____________ 设计题目:克鲁斯卡尔算法求最小生成树__________________________________ 完成日期：2015年1月6日 指导教师评语: ______________ _________________________ ___________________________________________________________________________________ ___________________________________________________________________________________________ ___________________________ __________ _ 成绩(五级记分制):_____ _ __________ 教师签名:__________ _______________

注：介于A和C之间为B级，低于C为D级和E级。按各项指标打分后，总分在90～100为优，80～89为良，70～79为中，60～69为及格，60分以下为不及格。

目录 1 需求分析 (1) 1.1系统目标 (1) 1.2主体功能 (1) 1.3开发环境 (1) 2 概要设计 (1) 2.1功能模块划分 (1) 2.2 系统流程图 (2) 3 详细设计 (3) 3.1 数据结构 (3) 3.2 模块设计 (3) 4测试 (3) 4.1 测试数据 (3) 4.2测试分析 (4) 5总结与体会 (6) 5.1总结： (6) 5.2体会： (6) 参考文献 (7) 附录全部代码 (8)

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)

普里姆和克鲁斯卡尔算法

前言 从学习《数据结构》这门课程开始，我已发现了学习算法的乐趣，在学习这门课的过程中也学到了许多计算机应用基础知识，对计算机的机体也有了一个初步的了解，又在课余时间阅读了大量有关算法设计与分析的图书，在此基础上，利用贪心算法，编写了一个用prim 和kruskal算法求解最小生成树，也以此检验自己一学期所学成果，加深对算法设计与分析这门课程的理解，由于所学知识有限，难免有些繁琐和不完善之处，下面向大家介绍此程序的设计原理，方法，内容及设计的结果。 本程序是在windows 环境下利用Microsoft Visual C++ 6.0所编写的，主要利用贪心算法的思想，以及数组，for语句的循环，if语句的嵌套，运用以上所学知识编写出的prim和kruskal算法求解最小生成树，在输入其边的起始位置，种植位置以及权值后，便可分别输出此网的prim和kruskal算法最小生成树的边的起始位置，终止位置以及权值。 正文 2.1 设计方法和内容 一.软件环境：Microsoft Visual C++ 6.0 二.详细设计思想： 所谓贪心算法是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。 贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。 贪心算法的基本思路如下： 1.建立数学模型来描述问题。 2.把求解的问题分成若干个子问题。 3.对每一子问题求解，得到子问题的局部最优解。 4.把子问题的解局部最优解合成原来解问题的一个解。 1.Prim（普里姆）算法思想 无向网的最小生成树问题 此算法的思想是基于点的贪心，力求从源点到下一个点的距离最短，以此来构建临接矩阵，所以此算法的核心思想是求得源点到下一个点的最短距离，下面具体解释如何求此最短距离： 在图中任取一个顶点k作为开始点，令集合U={k},集合w=V-U,其中v为图中所

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; }

克鲁斯卡尔算法实验报告

实验报告 实验原理： Kruskal 算法是一种按照图中边的权值递增的顺序构造最小生成树的方法。其基本思想是：设无向连通网为G＝（V，E），令G 的最小生成树为T，其初态为T＝（V，{}），即开始时，最小生成树T 由图G 中的n 个顶点构成，顶点之间没有一条边，这样T 中各顶点各自构成一个连通分量。然后，按照边的权值由小到大的顺序，考察G 的边集E 中的各条边。若被考察的边的两个顶点属于T 的两个不同的连通分量，则将此边作为最小生成树的边加入到T 中，同时把两个连通分量连接为一个连通分量；若被考察边的两个顶点属于同一个连通分量，则舍去此边，以免造成回路，如此下去，当T 中的连通分量个数为1 时，此连通分量便为G 的一棵最小生成树。 如教材153页的图4.21(a)所示，按照Kruskal 方法构造最小生成树的过程如图 4.21 所示。在构造过程中，按照网中边的权值由小到大的顺序，不断选取当前未被选取的边集中权值最小的边。依据生成树的概念，n 个结点的生成树，有n－1 条边，故反复上述过程，直到选取了n－1 条边为止，就构成了一棵最小生成树。 实验目的： 本实验通过实现最小生成树的算法，使学生理解图的数据结构存储表示，并能理解最小生成树Kruskal 算法。通过练习，加强对算法的理解，提高编程能力。 实验内容： （1）假定每对顶点表示图的一条边，每条边对应一个权值； （2）输入每条边的顶点和权值； （3）输入每条边后，计算出最小生成树； （4）打印最小生成树边的顶点及权值。 实验器材（设备、元器件）： PC机一台，装有C语言集成开发环境。 数据结构与程序： #include #include #include using namespace std;

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

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

if(n==1||n==2) *s=1; else{ fib(n-1,&f1); fib(n-2,&f2); *s=f1+f2; } } 3.素数的判断： /*方法一*/ for (t=1,i=2;i0;n/=10) k=10*k+n%10; return k; } /*求回文数*/

Kruskal算法说明及图解

1.无向网图及边集数组存储示意图 vertex[6]= 2.Kruskal 方法构造最小生成树的过程 (a)一个图 (b)最小生成树过程1 V0 V1 V2 V3 V4 V5 下标 0 1 2 3 4 5 6 7 8 from 1 2 0 2 3 4 0 3 0 to 4 3 5 5 5 5 1 4 2 weight 12 17 19 25 25 26 34 38 46 V1 V0 V4 V5 V2 V3 V1 V0 V5 V2 V3 V4

(c)最小生成树过程2 （d)最小生成树过程3 (e)最小生成树过程4 3.伪代码 1）初始化辅助数组parent[vertexNum];num=0; 2) 依次考查每一条边for(i=0; i

课程设计---克鲁斯卡尔算法求最小生成树

课程设计报告 课程名称：数据结构课程设计 设计题目：克鲁斯卡尔算法求最小生成树 系别：计算机系 专业：软件技术 学生姓名：陈浩学号:2011304040133 日期: 2013年1月5日-2013年1月11日

目录 1. 需求分析 (2) 1.1 设计题目 (2) 1.2 设计任务及要求 (2) 1.3课程设计思想 (2) 1.4 程序运行流程: (2) 1.5软硬件运行环境及开发工具 (2) 2.概要设计 (2) 2.1流程图 (2) 2.2抽象数据类型MFSet的定义 (3) 2.3主程序 (3) 2.4抽象数据类型图的定义 (4) 2.5抽象数据类型树的定义 (6) 3. 详细设计 (8) 3.1程序 (8) 4.调试与操作说明 (11) 4.1测试结果 (11) 4.2调试分析 (12)

5.课程设计总结与体会 (12) 5.1总结 (12) 5.2体会 (12) 6. 致谢 (13) 7. 参考文献 (13) 1.需求分析 1.1 设计题目：最小生成树 1.2 设计任务及要求：任意创建一个图，利用克鲁斯卡尔算法，求出该图的最小生成树。 1.3 课程设计思想：Kruskal算法采用了最短边策略(设G=(V,E)是一个无向连通网，令T=(U，TE)是G的最小生成树。最短边策略从TE={}开始，每一次贪心选择都是在边集E中选择最短边(u,v)，如果边(u,v)加入集合TE中不产生回路，则将边(u,v)加入边集TE中，并将它在集合E中删去。)，它使生成树以一种任意的方式生长，先让森林中的树木随意生长，每生长一次就将两棵树合并，最后合并成一棵树。 1.4程序运行流程: 1)提示输入顶点数目； 2)接受输入，按照项目要求产生边权值的随机矩阵；然后求解最小生成树； 3)输出最小生成树并且退出； 1.5 软硬件运行环境及开发工具：VC 2.概要设计

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;

研究生数据结构作业2016(更新版)

说明： （1）平时作业共20分； （2）交纸质作业； （3）所有作业请按时交纳，不收补交作业。 栈、队列、数组 作业一： 1． 若进栈序列为ABCD ，请写出全部可能的出栈序列和不可能的出栈序列。 2． 简要说明循环队列如何判断队满和队空？ 3． 设A 为n 阶对称矩阵，采用压缩存储存放于一维数组F[n(n+1)/2]中（从F[0] 开始存放），请分别给出存放上三角阵时任一矩阵元素a ij （1≤i,j ≤n ）的地址计算公式和存放下三角阵时任一矩阵元素a ij （1≤i,j ≤n ）的地址计算公式。 4． 写出下面稀疏矩阵的三元组顺序表和十字链表表示。 树 作业二： 1． 请分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。 2． 已知二叉树的先序遍历序列是EABDCFHGIKJ ，中序遍历序列是ABCDEFGHIJK ， 请构造二叉树，并写出其层次遍历序列和后序遍历序列。 3． 假设用于通信的电文由7个字母{A,B,C,D,E,F,G}组成，字母在电文中出现 的频率分别为0.17、0.09、0.12、0.06、0.32、0.03、0.21。试为这7个字母设计哈夫曼编码（约定哈夫曼树中左孩子结点的权值小于等于右孩子结点的权值），并计算其带权路径长度WPL 。 4． 将下图所示的森林转换成一棵二叉树。 A B C D G H I J K E F L 5． 将下图所示的二叉树还原成树或森林。 4000005030080 00000000700200000A ?? ?????? =?? ??????

图Array作业三: 1．已知带权有向图如图所示。 (1) 画出该图的邻接矩阵存储结构； (2) 求从顶点a到其余各顶点之间的最短路经及 最短路经长度，并给出计算过程。 2．无向图邻接表存储结构如图所示： (1) 画出该无向图； (2) 写出在该邻接表上，从顶点1出发所得到的深度优先遍历(DFS)和广度优先 遍历(BFS)序列。 1 2 3 4 5 6 7 8 3. 已知带权无向图如图所示： （1）根据普里姆（Prim）算法，求它的从顶点a出发的最 小生成树(写出过程，即添加顶点、边次序)； （2）根据克鲁斯卡尔（Kruskal）算法，求该图的最小生 成树(写出过程，即添加边次序)。 查找、排序

Kruskal算法

Kruskal 算法构造最小生成树 构造赋权图(,,)G V E W =，其中12{,,,}n V v v v = 为顶点集合,其中i v 表示第i 个顶点，12{,,,,}i E e e e = 为边的集合，()ij n n W w ?=为邻接矩阵，其中 i j i j ij i j v v v v w v v ∈??=?∞??顶点与之间的距离，当（，） E ，与之间没有边时 科茹斯克尔（Kruskal ）算法如下： （1）选1e E ∈（E 为边的集合），使得1e 是权重最小的边。 （2）若12,,e i e e …，已选好，则从12{,,e }i E e e -…，中选取1i e +，使得 i ）121{,,e }i e e +…，中无圈，且 ii ）是1i e +是12{,,e }i E e e -…，中权重最小的边。 （3）直到选得1V e - 为止。(V 是集合V 中元素的个数) 例：已知9个村庄之间的两两距离见表5，要架设通讯线路把9个村庄连接起来，求所需要通讯线的最小长度。 表5 10个村庄的两两距离数据（单位：km ） (,,)G V E W =，其中129{,, ,}V v v v = 为顶点集合,其中i v 表示第i 个村庄，12{,,,,}i E e e e = 为边的集合，99()ij W w ?=为邻接矩阵，其中 i j i j ij i j v v v v w v v ∈??=?∞??村庄与之间的距离，当（，） E ，与之间没有通讯路线时 科茹斯克尔（Kruskal ）算法如下： （1）选1e E ∈（E 为边的集合），使得1e 是距离最小的边。

Prim算法和Kruskal算法的Matlab实现

Prim 算法和Kruskal 算法的Matlab 实现 连线问题应用举例： 欲铺设连接n 个城市的高速公路，若i 城与j 城之间的高速公路造价为ij C ，试设计一个线路图，使总的造价最低。 连线问题的数学模型就是图论中在连通的赋权图上求权最小的支撑树。试用Matlab 分别实现求最小支撑数的Prim 算法和Krusal 算法（避圈法）。 一.基本要求： （1） 画出程序流程图； （2） 对关键算法、变量和步骤进行解释说明； （3） 用如下两图对所写算法的正确性进行验证。即输入图的信息，输出对应图 的最小支撑树及其权值。 v 1 v 74 5 v 216 19 6 6 11 2183020 51514 9241 67 53 48 44 （4）分析两种算法的实现复杂度。 二.扩展要求： （1）提供对算法效率（复杂度）进行评估的方法，并通过举例验证，与分析得到的算法复杂度结果相对照； （2）从降低内存消耗、减少计算时间的角度，对算法进行优化。 三．实验步骤 I.用Prim 算法求最小生成树 i ．算法分析及需求分析，程序设计 prim 算法的基本思想是：设G=（V ，E ）是一个无向连通网，令T=（U ，TE ）是G 的最小生成树。T 的初始状态为U={v0}（v0 ）TE={}，然后重复执行下述操作：在所有u U ， v V-U 的边中找一条代价最小的边（u ，v ）并入集合TE ，同时v 并入U ，直至U=V 为止。 显然，Prim 算法的基本思想是以局部最优化谋求全局的最优化，而且，还涉及到起始结点的问题。 本程序完成的功能是：从图中的任意结点出发，都能够找出最小生成树

求最小生成树(Kruskal算法)实验报告

学生实验报告 学院：软件与通信工程学院 课程名称：离散数学（软件） 专业班级： 12软件2班 姓名：杨滨 学号： 0123707

学生实验报告（2） 一、实验综述 1、实验目的及要求 （1）了解求最优化问题的贪心算法，了解贪心法的基本要素，学会如何使用贪心策略设计算法； （2）掌握Prim 算法和Kruskal 算法的思想及两者之间的区别； （3）编写程序，分别利用Prim 算法和Kruskal 算法实现，求出最小代价生成树，输出构成最小代价生成树的边集。 实验要求： 给出如右图的边权图，求最小生成树。 认真完成实验题，能正确运行，提交实验报告并上 传程序，实验报告要求写出操作步骤、结果、问题、解 决方法、体会等。 2、实验仪器、设备或软件 计算机、VC++6.0、office 、相关的操作系统等。 二、实验过程（实验步骤、记录、数据、分析） #include #define VERTS 6 struct edge { int from,to; //起顶点，终顶点 int find,val; //标记,顶点间边长 struct edge *next; }; typedef struct edge node; node *find_min_cost(node *); void min_tree(node *); int v[VERTS+1]={0}; //记录顶点即下标，值即出现过的次数 void main() { int data[10][3]={{1,0,6},{0,3,5},{3,5,2},{5,4,6}, {4,1,3},{2,1,5},{2,0,1},{2,3,5},{2,5,4},{2,4,6}};

普里母算法和克鲁斯卡尔方法求最小生成树完整程序

#include #include "stdlib.h" #define MaxVertexNum 12 #define MaxEdgeNum 20 #define MaxValue 1000 typedef int VertexType; typedef VertexType vexlist[MaxVertexNum]; typedef int adjmatrix[MaxVertexNum][MaxVertexNum]; int visited[MaxVertexNum]={0}; struct edgeElem{ int fromvex; int endvex; int weight; }; typedef struct edgeElem edgeset[MaxVertexNum]; void OutputEdgeset(edgeset GE,int e) { int i; for(i=0;i

北京理工大学数据结构作业(全)

北理工数据结构作业 第二章作业 1、在什么情况下用顺序表比链表好？（题集2.3） 需要对线性表进行随机存取时，顺序表比链表好。 2、已知L是带表头结点的非空单链表，且P结点既不是首元结点，也不是尾元结点，试从 下列提供的答案中选择合适的语句序列。（题集2.7） a.删除P结点的直接后继结点的语句序列是11 3 14。 b.删除P结点的直接前驱结点的语句序列是10 12 8 3 14。 c.删除P结点的语句序列是10 12 7 3 14。 d.删除首元结点的语句序列是12 11 3 14。 e.删除尾元结点的语句序列是12 11 3 14。 (1)p = p->next; (2)p->next = p; (3)p->next = p->next->next; (4)p = p->next->next; (5)while ( p!=NULL ) p=p->next; (6)while ( q->next!=NULL ) { p=q; q=q->next; } (7)while ( p->next!=q ) p=p->next; (8)while ( p->next->next!=q ) p=p->next; (9)while ( p->next->next!=NULL ) p=p->next; (10)q=p; (11)q=p->next; (12)p=l; (13)l=l->next; (14)free(q); 3、算法设计。设顺序表va中的数据元素递增有序，请设计一算法，将x插入到顺序表的 适当位置，以保持该表的有序性。（题集2.11） typedef struct{ ElemType *elem; int length; int listsize; }Sqlist; Status ListInsert_Sq(Sqlist &va , ElemType x){ if(va.length==va.listsize) return ERROR; for(i=va.length-1;i>=0&&x

Kruskal算法的设计和C实现

实验三Kruskal算法的设计 一、设计目的 １.根据算法设计需要, 掌握连通网的灵活表示方法; ２.掌握最小生成树的Kruskal算法; ３.基本掌握贪心算法的一般设计方法; ４.进一步掌握集合的表示与操作算法的应用. 二、设计内容 1．主要数据类型与变量 typedef struct { int num; int tag; }NODE; typedef struct { int cost; int node1; int node2; }EDGE; NODE set[N]; /* 节点集*/ EDGE es[N]; /* 边集*/ EDGE st[N]; /* 最小生成树的边集*/ 2．算法或程序模块 int Find(NODE *set,int elem) 功能: 在数组set中顺序查找元素elem, 使用带压缩规则的查找算法,返回所在子集的根节点索引. int Union( NODE *set,int elem1, int elem2) 功能: 应用Find算法首先找到elem1和elem2所在的子集, 然后应用带加权规则的并运算算法合并两个子集. 不成功时, 返回-1; 否则, 返回并集的根节点索引. int InsertSort(EDGE *dat,int n) 功能: 用插入分类算法将连通图的边集按成本值的非降次序分类. int Kruskal(EDGE *es, NODE *set, int length, EDGE *st,int num) 功能: 对有length条权值大于0的边,最小生成树中有num条边的连通图, 应用Kruskal 算法生成最小生成树, 最小生成树的边存储在数组st中. void Output(EDGE *st, int n)