最小生成树问题中北大学数据结构课程设计资料
中北大学
数据结构与算法课程设计
说明书
学院、系：软件学院
专业：软件工程
班级：
学生姓名：学号：
设计题目：最小生成树问题
起迄日期: 2015年1月12日- 2015年1月29日指导教师:王秀娟
2015 年1月 29 日
1需求分析
1.1已知一个无向连通网表示n个城市以及城市间可能设置的通信网络线路，其中网的顶点表示城市，边表示两个城市之间的线路，赋于边上的权值表示相应的代价。对于n个点的连通网能建立许多不同的生成树，每一棵生成树都可以是一个通信网。我们要选择一棵生成树，使总的耗费最小。
1.2该无向连通图的建立需要使用两种存储结构，即邻接表和邻接矩阵。
1.3实现最小生成树需要使用两种算法。即普里姆算法和克鲁斯卡尔。
1.4程序通过人机交互实现数据的输入和输出。
2选题要求
设计内容：
在n个城市之间建设网络，只需保证连通即可，求最经济的架设方法。存储结构采用（邻接表和邻接矩阵）两种，采用课本上的两种求解算法。
设计要求：
(1) 符合课题要求，实现相应功能；
(2) 要求界面友好美观，操作方便易行；
(3) 注意程序的实用性、安全性。
3程序设计方法及主要函数介绍
ADT Graph{
数据对象V;V是具有相同特性的数据元素的集合，成为顶点集。
数据关系R：
R = {VR}
VR = {（v,w）|v,w为V集合中的元素，（v,w）表示v和w之间存在的路径} 基本操作P;
CreateMGraph(MGraph *G)
初始条件：V是图的顶点集，VR是图的边的集合。
操作结果：按V和VR的定义构造图G，用邻接矩阵存储。
CreateALGraph(ALGraph *G)
初始条件：V是图的顶点集，VR是图的边的集合。
操作结果：按V和VR的定义构造图G，用邻接表存储。
LocateVex（G，u）
初始条件：图G存在，u和G中顶点有相同的特征。
操作结果：若G中存在顶点u，则返回该顶点在图中的位置；否则返回其他信息。
MiniSpanTree_PRIM（G, u)
初始条件：图G存在，u是图G中的一个顶点。
操作结果：用普利姆算法从第u个顶点出发构造网G的最小生成树T，输出T的各条边。
Kriuskal(G)
初始条件：图G存在
操作结果：用克鲁斯卡尔算法构造图G的最小生成树T，输出T的各条边。
ListToMat(MGraph *G1,ALGraph *G2)
初始条件：图G2存在
操作结果：把图的邻接表存储结构转换为邻接矩阵存储结构，用图G1表示。
MatToList(MGraph *G1,ALGraph *G2)
初始条件：图G1存在
操作结果：把图的邻接矩阵存储结构转换为邻接表存储结构，用图G2表示。
LocateVex(MGraph *G,VertexType u)
初始条件：图G存在，u和G中顶点有相同特征
操作结果：若G中存在顶点u，则返回该顶点在图中位置；否则返回-1
}ADT Graph
4程序源代码（包括注释）
#include
#include
#include
#define OK 1
#define ERROR 0
#define TURE 1
#define FALSE 0
#define INFEASIBLE -2
typedef int Status;
#define INFINITY 0
#define MAX_VERTEX_NUM 20
#define MAX_NAME 5
typedef char VertexType[MAX_NAME];
typedef int VRType;
typedef struct ArcCell
{
VRType adj;
/*顶点关系类型。对无权图，用1（是）或0(否）表示相邻否*/
/*对带权全图，则为权值类型*/
}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef struct MGraph
{
VertexType vexs[MAX_VERTEX_NUM];
/*顶点向量*/
AdjMatrix arcs;
/*邻接矩阵*/
int vexnum,arcnum;
/*图的当前顶点数和弧数*/
}MGraph;
/* 以下定义邻接表类型 */
typedef struct ANode /* 弧的结点结构类型 */
{ int end;
int begin; /* 该弧的终点位置 */
int weight; /* 该弧的相关信息,这里用于存放权值 */ struct ANode *nextarc; /* 指向下一条弧的指针 */
}ANode;
{ VertexType vertex; /* 顶点信息 */
int bianhao;
ANode *firstarc; /* 指向第一条弧 */
}VNode,AdjList[MAX_VERTEX_NUM]; /* AdjList是邻接表类型 */
typedef struct ALGraph
{ AdjList adjlist; /* 邻接表 */
int vexnum,arcnum; /* 图中顶点数n和边数 e */
}ALGraph; /* 图的邻接表类型 */
int LocateVex(MGraph *G,VertexType u)
{ /*初始条件：图G存在，u和G中顶点有相同特征*/
/*操作结果：若G中存在顶点u，则返回该顶点在图中位置；否则返回-1*/ int i;
for(i=0;i
if(strcmp(u,G->vexs[i])==0)
return i;
return -1;
}
图一
/* 建立无向图的邻接表算法 */
Status InitALGraph(ALGraph *G){
printf("请输入城市的数量及城市间的路径数目\n");
scanf("%d%d",&G->vexnum,&G->arcnum);
for(i=0;i
{/* 建立顶点表 */
printf("请输入第%d个城市的名称\n",i);
scanf("%s",&G->adjlist[i].vertex); /* 读入顶点信息 */
G->adjlist[i].firstarc=NULL;/* 边表置为空表 */
G->adjlist[i].bianhao = i;
}
printf("每个城市所对应的序号为\n");
for(i = 0;i
{
printf("序号：%d--->城
市：%s\n",G->adjlist[i].bianhao,&G->adjlist[i].vertex); //注意此处的& }
return OK;
}
Status PrintALGraph(ALGraph *G){
int i,end,begin,weight;
ANode *s;
for(i=0;i
printf("%s ------>",&G->adjlist[i].vertex);
s = G->adjlist[i].firstarc;
while(s!=NULL)
{
printf("( %s,%s ):%d
",&G->adjlist[s->end].vertex,&G->adjlist[s->begin].vertex,s->weight);
printf("\n");
}
return OK;
}
void CreateALGraph(ALGraph *G)
{
int i,j,k,weight;
ANode *s;
InitALGraph(G);
for(k=0;k< G-> arcnum;k++){ /* 建立边表 */
printf("\n请输入第%d条边的两个城市的编号及路径的架设费用:",k); scanf("%d",&i);
scanf("%d",&j);
scanf( "%d",&weight);/* 读入边(vi，vj)的顶点对序号 */
s=(ANode*)malloc(sizeof(ANode)); /* 生成边表结点 */
if(!s) {
printf("申请空间失败!\n");
exit(OVERFLOW);
}
s->begin=j; /* 邻接点序号为j */
s->end = i;
s->weight = weight;
s->nextarc= G->adjlist[i].firstarc;
G->adjlist[i].firstarc=s; /*将新结点*s插入顶点vi的边表头部 */
s=(ANode*)malloc(sizeof(ANode));
if(!s) {
exit(OVERFLOW);
}
s->begin=i; /* 邻接点序号为i */
s->end=j;
s->weight=weight;
s->nextarc=G->adjlist[j].firstarc;
G->adjlist[j].firstarc=s; /* 将新结点*s插入顶点vj的边表头部 */ }
PrintALGraph(G);
}/* CreateALGraph */
Status PrintMGraph(MGraph *G){
int a;
int i,j;
printf("邻接矩阵表示法为：\n");
printf("\t");
for(i=0;i
printf("\t%5s ",&G->vexs[i]);
printf("\n");
for ( i=0; i
{
printf("\t%5s ",&G->vexs[i]);
for ( j=0; j
{
printf("\t%5d ",G->arcs[i][j].adj);
}
printf("\n");
}
return OK;
图二
Status InitMGraph(MGraph *G){
int i,j;
printf("请输入城市的数量及城市间的路径数目：\n"); scanf("%d%d",&G->vexnum,&G->arcnum);
printf("\n请依次输入城市的名称，字符串类型\n"); for(i=0;i
{
/*构造顶点向量*/
scanf("%s",&G->vexs[i]);
}
for(i=0;i
/*初始化邻接矩阵*/
for(j=0;j
G->arcs[i][j].adj=INFINITY;
return OK;
}
Status CreateMGraph(MGraph *G)
{/*采用数组（邻接矩阵）表示法，构造无向网G*/
int i,j,k,weight,IncInfo;
VertexType va,vb;
InitMGraph(G);
for(k=0;k
{ printf("请输入第%d条路径的起点城市和终点城市的名称及路径的架设费用\n",k); scanf("%s %s %d",&va,&vb,&weight);
i=LocateVex(G,va);
j=LocateVex(G,vb);
G->arcs[i][j].adj=weight;
G->arcs[j][i].adj=weight;
}
PrintMGraph(G);
return OK;
}
typedef struct MINSIZE
{//记录从顶点集U到V-U的代价最小的边的辅助数组定义*
VertexType adjvex;
VRType lowcost;
}minside[MAX_VERTEX_NUM];
Status mininum(minside closedge,MGraph *G)
{/*求closedege,lowcost的最小正值*/
int i=0,j,k,min;
while(!closedge[i].lowcost)
i++;
min=closedge[i].lowcost;
k=i;
for(j=i+1;j
if(closedge[j].lowcost>0)
if(min>closedge[j].lowcost)
min=closedge[j].lowcost;
k=j;
}
return k;
}
图三
void MiniSpanTree_PRIM(MGraph *G,VertexType u)
{/*用普利姆算法从第u个顶点出发构造网G的最小生成树T，输出T的各条边*/ int i,j,k;
int qidian,zhongdian,weight;
VertexType va,vb;
minside closedge;
k=LocateVex(G,u);
for(j=0;j
/*辅助数组初始化*/
{
if(j!=k)
{
strcpy(closedge[j].adjvex,u);
closedge[j].lowcost=G->arcs[k][j].adj;
}
}
closedge[k].lowcost=0;
printf("最小代价生成树的各条边为:\n");
for(i=1;i
{/*选择其余G.vexnum-1个顶点*/
k=mininum(closedge,G);
/*求出T的下一个结点：第K顶点*/
strcpy( va,closedge[k].adjvex);
strcpy(vb ,G->vexs[k]);
qidian=LocateVex(G,va);
zhongdian=LocateVex(G,vb);
weight = G->arcs[qidian][zhongdian].adj;
printf("weight(%s,%s)=%d\n",va,vb,weight);
/*输出生成树的边*/
closedge[k].lowcost=0;
/*第K顶点并入U集*/
for(j=0;j
if(G->arcs[k][j].adj {/*新顶点并入U集后重新选择最小边*/ strcpy(closedge[j].adjvex,G->vexs[k]); closedge[j].lowcost=G->arcs[k][j].adj; } } } void InsertSort(ANode *E,int n) //对E[0...n-1]按权值递增有序的进行直接插入排序{ int i,j; ANode temp; for(i=1;i<=n;i++) { temp=E[i]; while(j>=0&&temp.weight { E[j+1]=E[j];/* 将w大于E[i].w的记录后移 */ j--; } E[j+1]=temp;/* 在j+1处插入E[i] */ } } 图四 void Kriuskal(ALGraph *G) { ANode *E; ANode *s; int i,j,end,begin,sn1,sn2,k,n; int vset[MAX_VERTEX_NUM]; n = 2*G->vexnum; E=(struct ANode*)malloc(n*sizeof(struct ANode)); k=0; for(i=0;i { /* 将各边存到E[0...n]数组中 */ for(j=0;j s = G->adjlist[i].firstarc; while(s!=NULL) { (E+k)->end = s->end; (E+k)->begin = s->begin; (E+k)->weight = s->weight ; s = s->nextarc; k++; } } InsertSort(E,k); /* 对E数组按w递增排序 */ for(i=0;i vset[i]=i; /* 初始化辅助数组 */ k=1; j=0; while(k { end=(E+j)->end; begin=(E+j)->begin; /* 取一条边的头尾顶点 */ sn1=vset[end]; sn2=vset[begin];/* 分别得到两个顶点所属的集合编号 */ if(sn1!=sn2) /* 两顶点属不同集合，则该边是最小生成树的一条边 */ { printf( "weight(%s %s) : %d\n",&(G->adjlist[end].vertex),&(G->adjlist[be gin].vertex),(E+j)->weight); k++; /* 生成边数增 1 */ for(i=0;i if(vset[i]==sn2) vset[i]=sn1; } j++; /* 扫描下一条边 */ } 图五Status ListToMat(MGraph *G1,ALGraph *G2){ int i,j; ANode *s; for(i = 0;i strcpy(G1->vexs[i], G2->adjlist[i].vertex); for(j = 0;j { G1->arcs[i][j].adj=INFINITY; } } for(i = 0;i { s = G2->adjlist[i].firstarc; while(s){ G1->arcs[s->end][s->begin].adj = s->weight; s =s->nextarc; } G1->vexnum = G2->vexnum; G1->arcnum = G2->arcnum; PrintMGraph(G1); return OK; } 图六 Status MatToList(MGraph *G1,ALGraph *G2) { int i,j; ANode *s,*temp; for(i = 0;i { strcpy(G2->adjlist[i].vertex ,G1->vexs[i]); G2->adjlist[i].firstarc = NULL; } for(i = 0;i { for(j = 0;j { if(G1->arcs[i][j].adj!=INFINITY) { s = (struct ANode*)malloc(sizeof(struct ANode)); s->end = i; s->begin = j; s->weight = G1->arcs[i][j].adj; s->nextarc=NULL; if(G2->adjlist[i].firstarc==NULL){ G2->adjlist[i].firstarc = s; }else{ s->nextarc = G2->adjlist[i].firstarc; G2->adjlist[i].firstarc = s; } } } } G2->vexnum = G1->vexnum; G2->arcnum = G1->arcnum; PrintALGraph(G2); return OK; } Status SelectSaveStructure(){ int c; printf("请选择一种算法存储无向图\n"); printf("*************************\n"); printf("| 1：邻接矩阵 2：邻接表|\n"); printf("请按键选择: "); while(1){ scanf("%d",&c); if(c==1||c==2) break; else { printf("输入的数字不符合要求，请从新输入\n"); } } getchar(); return c; } Status SelectSuanFa(){ int c; printf("请选择一种算法构建最小生成树\n"); printf("*****************************************************\n"); printf("| 1：普里姆算法（Prim） 2：克鲁斯卡尔算法（Kruskal）|\n"); printf("*****************************************************\n"); printf("请按键选择: "); while(1){ scanf("%d",&c); if(c==1||c==2) break; else { printf("输入的数字不符合要求，请从新输入\n"); } } getchar(); return c; } { MGraph *G1; ALGraph *G2; int choose; G2=(ALGraph *)malloc(sizeof(ALGraph)); choose = SelectSaveStructure(); switch(choose){ case 1: CreateMGraph(G1); printf("邻接矩阵转换为邻接表mat to list\n"); MatToList(G1,G2); break; case 2: G2=(ALGraph*)malloc(sizeof(ALGraph)); if(!G2) exit(OVERFLOW); CreateALGraph(G2); printf("邻接表转换为邻接矩阵list to mat\n"); ListToMat(G1,G2); break; } choose =SelectSuanFa(); switch(choose){ case 1: printf("采用Prim算法\n"); MiniSpanTree_PRIM(G1,G1->vexs[0]); break; case 2: printf("采用Kriuskal算法\n"); Kriuskal(G2); break; system("pause"); } 5程序运行界面 程序运行结果在所对应的的函数上方。 6程序的优点和不足 这是第二次做程序设计，相比上一次有了很多经验，难度也大了许多。我认为本次程序最大的缺陷之处是程序的健壮性不足，在输入数据的类型与预定义的类型不同时，不能进行判断和提示，直到对数据进行操作时，会出错并异常退出，没有达到预想的效果。 这次程序的优点是实现了图的两种存储方式（邻接矩阵和邻接表），并实现了两种存储方式的互相转换，Prim算法生成最小生成树时是在邻接矩阵方式上操作，Kruskal算法是在邻接表上操作。达到了以任意一种方式存储图类型时都可以用两种方式生成最小生成树。而不用进行选择。 7心得体会 该次所做题目为最小生成树问题，涵盖内容为图的邻接矩阵、邻接表的存储，普利姆算法、克鲁斯卡尔算法。通过算法的编写，我学到的最重要的方法是标记，从而减少算法的时 间复杂度。除了课内知识外，还学到了许多新东西。在做课程设计是要有信心，有耐心，切 勿浮躁；出现差错时要随机应变。 无论是邻接表（链式存储）或邻接矩阵（顺序存储）存储方式的差异，还是Prim或Kruscal 算法的不同思想，我都从中学到了许多方法。如用标记法求连通分量数是在几天没有进展后 突然冒出的新想法，其实是在几天的尝试和积累中才摸索出的规律；又如Prim算法中赋值时，0和无穷都有其特定的作用，不能随意交换；调试程序过程中也有许多及其不易发现的 错误，看似正确的语句仍存在漏洞，只有多次验证后才能找出问题核心，需要细心细心再细心、考虑的更全面才行。测试用例的选择也是至关重要的，如果选取不当则很难发现严重的 逻辑错误。 总之，只有专注的思考，不断的探求新方法，追求更小时间、空间复杂度的好算法，才 能设计出有自己独特风格的好程序。只有团队成员相互配合、共同探讨才能起到互补的作用，从而使算法更严谨、更完美。 1.一元稀疏多项式计算器 [问题描述] 设计一个一元稀疏多项式简单计算器。 [基本要求] 输入并建立多项式； 输出多项式，输出形式为整数序列：n, c1, e1, c2, e2,……, cn, en ，其中n是多项式的项数，ci, ei分别是第i项的系数和指数，序列按指数降序排序； 多项式a和b相加，建立多项式a+b; 多项式a和b相减，建立多项式a-b; [测试数据] (2x+5x8-3.1x11)+(7-5x8+11x9)=(-3.1x11+11x9+2x+7) (6x-3-x+4.4x2-1.2x9)-(-6x-3+5.4x2-x2+7.8x15)=(-7.8x15-1.2x9-x+12x-3) (1+x+x2+x3+x4+x5)+(-x3-x4)=(x5+x2+x+1) (x+x3)+(-x-x3)=0 (x+x2+x3)+0=(x3+x2+x) [实现提示] 用带头结点的单链表存储多项式，多项式的项数存放在头结点中。 2.背包问题的求解 [问题描述] 假设有一个能装入总体积为T的背包和n件体积分别为w1, w2, …,wn的物品，能否从n件物品中挑选若干件恰好装满背包，即使w1+w2+…+wn=T，要求找出所有满足上述条件的解。例如：当T=10，各件物品的体积为{1，8，4，3，5，2}时，可找到下列4组解：（1，4，3，2）、（1，4，5）、（8，2）、（3，5，2） [实现提示] 可利用回溯法的设计思想来解决背包问题。首先，将物品排成一列，然后顺序选取物品转入背包，假设已选取了前i件物品之后背包还没有装满，则继续选取第i+1件物品，若该件物品“太大”不能装入，则弃之而继续选取下一件，直至背包装满为止。但如果在剩余的物品中找不到合适的物品以填满背包，则说明“刚刚”装入背包的那件物品“不合适”，应将它取出“弃之一边”，继续再从“它之后”的物品中选取，如此重复，直至求得满足条件的解，或者无解。 由于回溯求解的规则是“后进先出”因此自然要用到栈。 3.完全二叉树判断 用一个二叉链表存储的二叉树，判断其是否是完全二叉树。 4.最小生成树求解（1人） 任意创建一个图，利用克鲁斯卡尔算法，求出该图的最小生成树。 5.最小生成树求解（1人） 任意创建一个图，利用普里姆算法，求出该图的最小生成树。 6.树状显示二叉树 编写函数displaytree(二叉树的根指针，数据值宽度，屏幕的宽度)输出树的直观示意图。输出的二叉树是垂直打印的，同层的节点在同一行上。 [问题描述] 假设数据宽度datawidth=2,而屏幕宽度screenwidth为64=26,假设节点的输出位置用 （层号，须打印的空格数）来界定。 第0层：根在（0，32）处输出； 数据结构课程设计报告题目：最小生成树问题 院（系）：计算机工程学院 学生姓名: 班级：学号: 起迄日期: 指导教师: 2011—2012年度第 2 学期 一、需求分析 1.问题描述： 在n个城市之间建设网络，只需保证连通即可，求最经济的架设方法。存储结构采用多种。求解算法多种。 2.基本功能 在n个城市之间建设网络，只需要架设n-1条线路，建立最小生成树即可实现最经济的架设方法。 程序可利用克鲁斯卡尔算法或prim算法生成最小生成树。 3.输入输出 以文本形式输出最小生成树，同时输出它们的权值。通过人机对话方式即用户通过自行选择命令来输入数据和生成相应的数据结果。 二、概要设计 1.设计思路： 因为是最小生成树问题，所以采用了课本上介绍过的克鲁斯卡尔算法和 prim算法两种方法来生成最小生成树。根据要求，需采用多种存储结构，所以我选择采用了邻接表和邻接矩阵两种存储结构。 2.数据结构设计： 图状结构： ADT Graph{ 数据对象V：V是具有相同特性的数据元素的集合，称为顶点集。 数据关系R：R={VR} VR={ 运筹学试题 Company Document number：WTUT-WT88Y-W8BBGB-BWYTT-19998 运筹学试题 一、填空题(本大题共8小题，每空2分，共20分) 1．线性规划闯题中，如果在约束条件中出现等式约束，我们通常用增加___的方法来产生初始可行基。 2．线性规划模型有三种参数，其名称分别为价值系数、___和___。 3．原问题的第1个约束方程是“=”型，则对偶问题相应的变量是___变量。 4．求最小生成树问题，常用的方法有：避圈法和 ___。 5．排队模型M／M／2中的M，M，2分别表示到达时间为___分布，服务时间服从负指数分布和服务台数为2。 6．如果有两个以上的决策自然条件，但决策人无法估计各自然状态出现的概率，那么这种决策类型称为____型决策。 7．在风险型决策问题中，我们一般采用___来反映每个人对待风险的态度。 8．目标规划总是求目标函数的___信，且目标函数中没有线性规划中的价值系数，而是在各偏差变量前加上级别不同的____。 二、单项选择题(本大题共l0小题，每小题3分，共30分)在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。多选无分。 9．使用人工变量法求解极大化线性规划问题时，当所有的检验数在基变量中仍含有非零的人工变量，表明该线性规划问题【】 A．有唯一的最优解 B．有无穷多最优解 C．为无界解 D．无可行解 10．对偶单纯形法解最大化线性规划问题时，每次迭代要求单纯形表中【】 A．b列元素不小于零 B．检验数都大于零 C．检验数都不小于零 D．检验数都不大于零 11．已知某个含10个结点的树图，其中9个结点的次为1，1，3，1，1，1，3，1，3，则另一个结点的次为【】 A．3 B．2 C．1 D．以上三种情况均有可能 12．如果要使目标规划实际实现值不超过目标值。则相应的偏离变量应满足【】 13．在运输方案中出现退化现象，是指数字格的数目【】 A．等于 m+n B．等于m+n-1 C．小于m+n-1 D．大于m+n-1 14．关于矩阵对策，下列说法错误的是【】 A．矩阵对策的解可以不是唯一的 C．矩阵对策中，当局势达到均衡时，任何一方单方面改变自己的策略，都将意味着自己更少的赢得和更大的损失 D．矩阵对策的对策值，相当于进行若干次对策后，局中人I的平均赢得或局中人Ⅱ的平均损失值 【】 A．2 8．—l C．—3 D．1 16．关于线性规划的原问题和对偶问题，下列说法正确的是【】 A．若原问题为元界解，则对偶问题也为无界解 课程设计说明书 课程名称：数据结构 专业：班级： 姓名：学号： 指导教师：成绩： 完成日期：年月日 任务书 题目：黑白棋系统 设计内容及要求： 1.课程设计任务内容 通过玩家与电脑双方的交替下棋，在一个8行8列的方格中，进行棋子的相互交替翻转。反复循环下棋，最后让双方的棋子填满整个方格。再根据循环遍历方格程序，判断玩家与电脑双方的棋子数。进行大小判断，最红给出胜负的一方。并根据y/n选项，判断是否要进行下一局的游戏。 2.课程设计要求 实现黑白两色棋子的对峙 开发环境：vc++6.0 实现目标： （1）熟悉的运用c语言程序编写代码。 （2）能够理清整个程序的运行过程并绘画流程图 （3）了解如何定义局部变量和整体变量； （4）学会上机调试程序，发现问题，并解决 （5）学习使用C++程序来了解游戏原理。 （6）学习用文档书写程序说明 摘要 本文的研究工作在于利用计算机模拟人脑进行下黑白棋，计算机下棋是人工智能领域中的一个研究热点，多年以来，随着计算机技术和人工智能技术的不断发展，计算机下棋的水平得到了长足的进步 该程序的最终胜负是由棋盘上岗双方的棋子的个数来判断的，多的一方为胜，少的一方为负。所以该程序主要运用的战术有削弱对手行动战术、四角优先战术、在游戏开局和中局时，程序采用削弱对手行动力战术，即尽量减少对手能够落子的位置；在游戏终局时则采用最大贪吃战术，即尽可能多的吃掉对手的棋子；而四角优先战术则是贯穿游戏的始终，棋盘的四角围稳定角，不会被对手吃掉，所以这里是兵家的必争之地，在阻止对手进角的同时，自己却又要努力的进角。 关键词：黑白棋；编程；设计 测控电路设计 专业：测控技术与仪器 班级：11050341 姓名： 学号： 五路呼叫器 1．设计思路 本次课程设计是基于DE2开发板的设计，因此本电路在总体设计的时候考虑了如下几个方面： （1）呼叫源的输入： 设计要求用五个输入键代替呼叫源。对于DE2板上产生触发脉冲的键，它保持原输入状态只是一瞬间。但在优先级判别过程中必须不断调用原输入状态，所以必须将输入量保存起来。 （2）呼叫源的过程处理： 在本设计要求中，当有多个呼叫同时发生时，用指示灯指明多个呼叫源在同时呼叫，并按优先级顺序由数码管显示多个呼叫源号码。1号呼叫源优先级最高，按顺序5号呼叫源优先级最低。 这次课程设计中我使用了计数器扫描的方式，从一号呼叫源(优先级最高)开始，对各个已经保存的输入量依次进行扫描。当遇到一个高电平，即有呼叫源呼叫时，便对相应的呼叫源进行编码、译码，送到输出端口显示其相应的呼叫号；延时一定时间后，再扫描下一个呼叫源。如果某一呼叫源没有呼叫，则跳过该呼叫源，对下一个呼叫源进行扫描。因此，在呼叫源间的显示不会间隔时间太久，而可以有快速的对应显示。这样由一号呼叫源到五号呼叫源不断地进行循环扫描，其扫描的个数由计数器进行控制。即对五个呼叫源都扫描一次后，对计数器清零，进行下一次扫描。如此不断的循环和显示呼叫源号。当任何一个呼叫源有输入时，扫描器再次从第一个呼叫源开始扫描，做到优先序扫描。 （3）输出处理： 按任务要求和根据DE2板的硬件设置，必须将呼叫源信号编制成对应的BCD码输出。输出的BCD码经DE2板的硬件设置，实现译码和显示。 2．设计方案 2.1设计原理框图 图1设计原理图 2.2主要模块介绍 计数扫描：利用74161进行计数扫描，保证呼叫可以插入。 信号保持：利用74112来保存开关量，把各路输入的信号一直保存到下一个呼叫信号到来为止，而且可以随时插入不同优先级别的呼叫信号。 指示灯显示：当有多个呼叫同时发生时，用指示灯指明多个呼叫源在同时呼叫。利用简单的门电路完成此功能。 选通及优先编码：利用门电路对计数和输入信号进行选通，再通过74148对选通后的信号进行编码，完成按优先级顺序由数码管显示多个呼叫源号码的功能。 3．单元电路设计 3.1输入信号的处理 由于DE2实验板上的触发脉冲按键产生的触发信号只是一瞬间，而在优先级判别和多输入判别的过程中需要多次调用源输入状态，所以需要一个具有锁存功能的的电路将输入信号保存起来。在设计初始，考虑使用SR 锁存器，但是考虑到改电路系统对输入信号要具有单独 选通 译码 计数扫描时钟脉冲信号保持 呼叫输入优先编码 指示灯显示多 个呼叫 译码显示呼叫号 黄冈师范学院 提高型实验报告 实验课题最小生成树的Prim算法 （实验类型：□综合性■设计性□应用性） 实验课程算法程序设计 实验时间 2010年12月24日 学生姓名周媛鑫 专业班级计科 0801 学号 200826140110 一．实验目的和要求 （1）根据算法设计需要, 掌握连通网的灵活表示方法; （2）掌握最小生成树的Prim算法; （3）熟练掌握贪心算法的设计方法; 二．实验条件 （1）硬件环境：实验室电脑一台 （2）软件环境：winTC 三．实验原理分析 （1）最小生成树的定义： 假设一个单位要在n个办公地点之间建立通信网，则连通n个地点只需要n-1条线路。可以用连通的无向网来表示n个地点以及它们之间可能设置的通信线路，其中网的顶点表示城市，边表示两地间的线路，赋于边的权值表示相应的代价。对于n个顶点的连通网可以建立许多不同的生成树，每一棵生成树都可以表示一个通信网。其中一棵使总的耗费最少，即边的权值之和最小的生成树，称为最小生成树。 （2）构造最小生成树可以用多种算法。其中多数算法利用了最小生成树的下面一种简称为MST的性质：假设N=(V,{E})是一个连通网，U是顶点集V的一个非空子集。若(u,v)是一条具有最小权值（代价）的边，其中u∈U，v∈V-U，则必存在一棵包含边 (u.v)的最小生成树。 （3）普里姆（Prim）算法即是利用MST性质构造最小生成树的算法。算法思想如下： 假设N=(V,{E})和是连通网，TE是N上最小生成树中边的集合。算法从U={u0}( u0∈V)，TE={}开始，重复执行下述操作：在所有u∈U，v∈V-U的边(u, v) ∈E 中找一条代价最小的边(u0, v0)并入集合TE，同时v0并入U，直到U=V为止。此时TE中必有n-1条边，则T=(V,{TE})为N的最小生成树。 四．实验步骤 （1）数据结构的设计： 采用邻接矩阵的存储结构来存储无向带权图更利于实现及操作： 邻接矩阵的抽象数据结构定义： #define INFINITY INT_MAX //最大值 #define MAX_ERTEX_NUM 20 //最大顶点数 typedef enum {DG,DN,UDG,UDN}GraphKind;//{有向图,有向网，无向网，无向图} typedef struct Arc Cell{ VRType adj ; // VRType 是顶点关系的类型。对无权图用1和0表示相邻否；InfoType * info; //该弧相关信息的指针 }ArcCell ，AdjMatrix [ MAX_VERTEX_NUM][MAX_VERTEX_NUM]； Typedef struct { VertexType vexs [ MAX_VERTEX_NUM] ; //顶点向量 算法与数据结构 课程设计报告 题目: A VLree的实现及分析 班级: 12计算机1 学号: 1200303132 姓名: 熊成毅 成绩: 2013年12月31日 一、AVLree的实现及分析 AVL 树是平衡的二元查找树。一株平衡的二元查找树就是指对其每一个节点，其左子树和右子树的高度只差不超过1. 编写程序实现AVL树的判别；并实现AVL树的ADT，包括其上的基本操作；节点的加入和删除。BSt和AVL的差别就在平衡性上，所以AVL的操作关键要考虑如何在保持二元查找树定义条件下对二元树进行平衡化。 （1）编写AVL树的判别程序，并判别一个人元查找数是否为AVL树。二元查找树用其先序遍历结果表示，如：5,2,1,3,7,8. （2）实现AVL树的ADT，包括其上的基本操作：节点的加入和删除，另外包括将一般二元查找树转变为AVL树的操作。 二、设计思想（宋体，三号加粗） 任意给定一组数据，设计一个算法，建立一棵平衡二叉树，对它进行查找、插入、删除等操作。平衡二叉树ADT结构如下： typedef struct{ Status key; }ElemType; typedef struct BSTNode{ ElemType data; Status bf; struct BSTNode *lchild,*rchild; }BSTNode,*BSTree; 给出一组数据，通过 InsertAVL(BSTree &T, ElemType e, Status &taller)插入算法，构建平衡二叉树，若在平衡的二叉排序树T中不存在和e有相同关键字的结点，则插入一个数据元素为e的新结点，并返回1，否则返回0。若因插入而使二叉排序树失去平衡，则作平衡旋转处理，布尔变量taller反映T长高与否。 在此算法中，利用到递归算法和 LeftBalance(BSTree &T)左平衡处理，RightBalance(BSTree &T)右平衡处理。进而实现构建平衡二叉树，使其左子树和右子树的高度之差不超过1. LeftBalance(BSTree &T）对以指针T所指结点为根的二叉树作左平衡旋转处理。本算法结束时，指针T指向新的根结点。 RightBalance(BSTree &T)// 对以指针T所指结点为根的二叉树作右平衡旋转处理。本算法结束时，指针T指向新的根结点。 R_Rotate(BSTree &p)对以*p为根的二叉排序树作右旋处理，处理之后p指向新的树根结点，即旋转处理之前的左子树的根结点 L_Rotate(BSTree &p)对以p↑为根的二叉排序树作左旋处理，处理之后p指向新的树 运筹学判断题 一、第1章 线性规划的基本理论及其应用 1、线性规划问题的可行解集不一定是凸集。（×） 2、若线性规划无最优解则其可行域无界。（×） 3、线性规划具有惟一的最优解是指最优表中非基变量检验数全部非零。（√） 4、线性规划问题的每一个基本可行解对应可行域的一个顶点。（√） 5、若线性规划模型的可行域非空有界，则其顶点中必存在最优解。（√） 6、线性规划问题的大M 法中，M 是负无穷大。（×） 7、单纯形法计算中，若不按最小比值原则选取换出变量，则在下一个解中至少有一个基变量为负。（√） 8、对于线性规划问题的基本可行解，若大于零的基变量数小于约束条件数，则解是退化的。（√）。 9、一旦一个人工变量在迭代过程中变为非基变量后，则该变量及相应列的数字可以从单纯性表中删除，且这样做不影响计算结果。（√） 10、线性规划的目标函数中系数最大的变量在最优解中总是取正值。（×） 11、对一个有n 个变量，m 个约束的标准型的线性规划问题，其可行域的顶点恰好为个m n C 。（×） 12、线性规划解的退化问题就是表明有多个最优解。（×） 13、如果一个线性规划问题有两个不同的最优解，则它有无穷多个最优解。（√） 14、单纯型法解线性规划问题时值为0的变量未必是非基变量。（√） 15、任何线性规划问题度存在并具有唯一的对偶问题。（√） 16、对偶问题的对偶问题一定是原问题。（√） 17、根据对偶问题的性质，当原问题为无界解时，其对偶问题无可行解；反之，当对偶问题无可行解时，其原问题为无界解。（×） 18、若原问题有可行解，则其对偶问题也一定有可行解。（×） 19、若原问题无可行解，其对偶问题也一定无可行解。（×） 20、若原问题有最优解，其对偶问题也一定有最优解。（√） 21、已知*i y 为线性规划的对偶问题的最优解，若*0i y >，说明在最优生产计划中，第i 种 资源一定有剩余。（×） 22、原问题具有无界解，则对偶问题不可行。（√） 23、互为对偶问题，或者同时都有最优解，或者同时都无最优解。（√） 24、某公司根据产品最优生产计划，若原材料的影子价格大于它的市场价格，则可购进原材料扩大生产。（√） 25、对于线性规划问题，已知原问题基本解不可行，对偶问题基本解可行，可采用对偶单纯形法求解。（√） 26、原问题（极小值）第i 个约束是“≥”约束，则对偶变量0i y ≥。（√） 27、线性规划问题的原单纯形解法，可以看作是保持原问题基本解可行，通过迭代计算，逐步将对偶问题的基本解从不可行转化为可行的过程。（√） *28、运输问题不能化为最小费用流问题来解决。（×） 29、运输问题一定有最优解。（√） 河北科技大学 课程设计报告 学生姓名：白云学号：Z110702301 专业班级：计算机113班 课程名称：数据结构课程设计 学年学期： 2 01 3—2 014学年第2学期指导教师：郑广 2014年6月 课程设计成绩评定表 目录 一、需求分析说明 (1) 1.1最小生成树总体功能要求 (1) 1.2基本功能 (1) 1.3 模块分析 (1) 二、概要设计说明 (1) 2.1设计思路 (1) 2.2模块调用图 (2) 2.3数据结构设计 (2) 2.3.1.抽象数据类型 (2) 2.3.2方法描述 (2) 三、详细设计说明 (3) 3.1主函数模块 (3) 3.2邻接表输出子模块 (3) 3.3邻接矩阵输出子模块 (3) 3.4创建邻接矩阵子模块 (3) 3.5创建邻接表子模块 (3) 3.6 Prim子模块 (3) 3.7 Kruscal子模块 (4) 四、调试分析 (4) 4.1实际完成情况说明 (4) 4.2 出现的问题及解决方案 (4) 4.3程序中可以改进的地方 (4) 六、课程设计总结 (7) 七、测试数据 (7) 八、参考书目 (7) 一、需求分析说明 1.1最小生成树总体功能要求 在n个城市之间建设网络，只需保证连通即可，求最经济的架设方法。存储结构采用多种。求解算法多种。 1.2基本功能 在n个城市之间建设网络，只需要架设n-1条线路，建立最小生成树即可实现最经济的架设方法。 程序可利用克鲁斯卡尔算法或prim算法生成最小生成树。 1.3 模块分析 主模块：用于生成界面和调用各个子模块。 Kruscal模块：以kruscal算法实现最小生成树。 Prim模块：以prim算法实现最小生成树。 邻接表模块：用邻接表方式存储图。 邻接表输出模块：输出邻接表。 邻接矩阵模块：用邻接矩阵方式存储图。 邻接矩阵模块：输出邻接矩阵。 二、概要设计说明 2.1设计思路 问题的解决分别采用普利姆算法以及克鲁斯卡尔算法。 1) 普利姆算法就是先选择根，把它放入一个集合U中，剩余的顶点放在集合V中。然后选择该顶点与V中顶点之间权值最小的一条边，以此类推，如果达到最后一个则返回上一个顶点。 2) 克鲁斯卡尔算法就是写出所有的顶点，选择权最小的边，然后写出第二小的，以此类推，最终要有一个判断是否生成环，不生成则得到克鲁斯卡尔的最小生成树。 第11章图与网络模型 习题1 配送的最短距离。用解：这是一个最短路问题，要求我们求出从v1到v 7 Dijkstra算法求解可得到这问题的解为27。我们也可以用此书附带的管理运筹学软件进行计算而得出最终结果为： 从节点1到节点7的最短路 ************************* 起点终点距离 ------------ 124 2312 356 575 此问题的解为:27 → 12357 习题2 解：这是一个最短路的问题，用Dijkstra算法求解可得到这问题的解为4.8，即在4年内购买、更换及运行维修最小的总费用为：4.8万元。 最优更新策略为：第一年末不更新 第二年末更新 第三年末不更新 第四年末处理机器 我们也可以用此书附带的管理运筹学软件进行求解，结果也可以得出此问题的解为4.8。 习题3 解：此题是一个求解最小生成树的问题，根据题意可知它要求出连接v1到v8的最小生成树。解此题可以得出结果为18。也可以使用管理运筹学软件，得出如下结果： 此问题的最小生成树如下： ************************* 起点终点距离 ------------ 132 342 124 252 573 习题4 782 763此问题的解为:18 解：此题是一个求解最大流的问题，根据题意可知它要求出连接v1到 v6 的最 大流量。解此题可以得出最大流量为 出结果为： 22。使用管理运筹学软件，我们也可以得v1从节点1到节点6的最大流 ************************* 起点终点距离 ------------ 126 146 1310 240 256 345 365 455 466 5611 此问题的解为:22 即从v1到v6的最大流量为：22 习题5 解：此题是一个求解最小费用最大流的问题，根据题意可知它要求出连接v1到v6的最小费用最大流量。解此问题可以得出最大流为5，最小费用为39。使用管理运筹学软件，我们也可以得出结果如下： 从节点1到节点6的最大流 ************************* 起点终点流量费用 ---------------- 1213 1341 2424 3211 3533 4624 《数据结构课程设计》报告 题目：课程设计题目2教学计划编制 班级：700 学号：09070026 姓名：尹煜 完成日期：2011年11月7日 一．需求分析 本课设的任务是根据课程之间的先后的顺序，利用拓扑排序算法，设计出教学计划，在七个学期中合理安排所需修的所有课程。 （一）输入形式：文件 文件中存储课程信息，包括课程名称、课程属性、课程学分以及课程之间先修关系。 格式：第一行给出课程数量。大于等于0的整形，无上限。 之后每行按如下格式“高等数学公共基础必修6.0”将每门课程的具体信息存入文件。 课程基本信息存储完毕后，接着给出各门课程之间的关系，把每门课程看成顶点，则关系即为边。 先给出边的数量。大于等于0的整形。 默认课程编号从0开始依次增加。之后每行按如下格式“1 3”存储。此例即为编号为1的课程与编号为3的课程之间有一条边，而1为3的前驱，即修完1课程才能修3课程。 例： （二）输出形式：1.以图形方式显示有向无环图 2.以文本文件形式存储课程安排 （三）课设的功能 1.根据文本文件中存储的课程信息（课程名称、课程属性、课程学分、课程之间关系） 以图形方式输出课程的有向无环图。 拓展：其显示的有向无环图可进行拖拽、拉伸、修改课程名称等操作。 2.对课程进行拓扑排序。 3.根据拓扑排序结果以及课程的学分安排七个学期的课程。 4.安排好的教学计划可以按图形方式显示也可存储在文本文件里供用户查看。 5.点击信息菜单项可显示本人的学好及姓名“09070026 尹煜” （四）测试数据（见六测设结果） 二．概要设计 数据类型的定义： 1.Class Graph即图类采用邻接矩阵的存储结构。类中定义两个二维数组int[][] matrix 和Object[][] adjMat。第一个用来标记两个顶点之间是否有边，为画图服务。第二个 是为了实现核心算法拓扑排序。 2.ArrayList 《机械设计基础》 一、选择题： 1.我国标准规定，渐开线标准直齿圆柱齿轮分度圆上的压力角应为 （）度。 a）20 b）30 c）60 d）90 2. 渐开线标准直齿圆柱齿轮（正常齿）的齿顶高系数为（），顶隙系 数为（）。 a）1，0.1 b）1，0.2 c） 1.2，0.2 d）1，0.25 3. 渐开线直齿圆柱齿轮的正确啮合条件是（） a）模数相等 b）压力角相等 c）模数和压力角分别相等且为标准值 d）a，b，c都 不对 4.用齿条形刀具加工标准直齿圆柱齿轮,当压力角为20°,齿顶系数为 1时,不根切的最少齿数是多少?（） a） 15 b）16 c） 17 d）18 5.平面机构自由度的计算公式为（）。 a）3n-2P L-P H b）3n- P L- P H c）2n- P L -P H d）n- P L- P H 6. 构件是机构的基本（）单元。 a）运动b）制造c）联结d）a）b）c）都不对 7.平面四杆机构的压力角和传动角的关系为（）。 a）互为余角 b）互为补角 c）a，b都可能 d）a，b都不可能 8. 带传动的最大应力发生在（）。 a)紧边与小轮的切点 b)紧边 c)松边 d)松边与小轮的切点 9.V带的截面形状为（）。 a）V形 b）梯形 c）圆形 d）矩形 10.用范成法切制齿轮时，只要两齿轮（），就可以用同一把滚刀。 a) 模数相等b）压力角相等c)模数和压力角分别相等d)齿数相等 二、填空题： 1．闭式硬齿面齿轮传动常按强度设计，然后校核 强度。 2．预紧后受轴向变载荷的螺纹联接，为提高联接的疲劳强度，应尽量减小的刚度，以及提高的高度。 3．增加蜗杆头数，可以传动效率，但蜗杆头数过多，将会给带来困难。 4．直齿圆锥齿轮传动的强度计算方法是以的当量圆柱齿轮为计算基础的。 5．阿基米德蜗杆与蜗轮正确啮合的条件是。 6._______是机器与机构的统称。 7.包角是指带与带轮接触弧所对的圆心角。对于平带传动，一般要求包角 α≥________；对于V带传动，一般要求包角α≥________。 8.凸轮基圆半径是从到的最短距离。 9.凸轮机构从动件的两种常用运动规律中，________________运动有刚性 冲击，这是因为其____________有突变,________________运动有柔性冲击，这是因为其____________有突变。 三、简答题：本大题共4题，每题6分，共24分。 1.影响带传动中摩擦力大小的主要因素是什么？ 2.试给出三种平面连杆机构演化的方法。 3.简述配合螺栓联接（绞制孔用）传递横向载荷的工作原理？ 4.零件和构件的区别是什么？ 、计算题：本大题共3个小题，共26分 2.图示铰链四杆机构，试问：当以杆AD为机架时，称为何种机构？（8分） 算法与数据结构 实验报告 系（院）：计算机科学学院 专业班级：软工11102 姓名：潘香杰 学号： 201104449 班级序号： 18 指导教师：詹泽梅老师 实验时间：2013.6.17 - 2013.6.29 实验地点：4号楼5楼机房 目录 1、课程设计目的．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 2、设计任务．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 3、设计方案．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 4、实现过程．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 5、测试．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 6、使用说明．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 7、难点与收获．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 8、实现代码．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 9、可改进的地方．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．． 算法与数据结构课程设计是在学完数据结构课程之后的实践教学环节。本实践教学是培养学生数据抽象能力，进行复杂程序设计的训练过程。要求学生能对所涉及问题选择合适的数据结构、存储结构及算法，并编写出结构清楚且正确易读的程序，提高程序设计基本技能和技巧。 一．设计目的 1．提高数据抽象能力。根据实际问题，能利用数据结构理论课中所学到的知识选择合适的逻辑结构以及存储结构，并设计出有效解决问题的算法。 2．提高程序设计和调试能力。学生通过上机实习，验证自己设计的算法的正确性。学会有效利用基本调试方法，迅速找出程序代码中的错误并且修改。 3．初步了解开发过程中问题分析、整体设计、程序编码、测试等基本方法和技能。二．设计任务 设计一个基于DOS菜单的应用程序。要利用多级菜单实现各种功能。内容如下： ①创建无向图的邻接表 ②无向图的深度优先遍历 ③无向创建无向图的邻接矩阵 ④无向图的基本操作及应用 ⑤图的广度优先遍历 1．有向图的基本操作及应用 ①创建有向图的邻接矩阵 ②创建有向图的邻接表 ③拓扑排序 2．无向网的基本操作及应用 ①创建无向网的邻接矩阵 ②创建无向网的邻接表 ③求最小生成树 3．有向网的基本操作及应用 ①创建有向网的邻接矩阵 ②创建有向网的邻接表 ③关键路径 ④单源最短路径 三．设计方案 第一步：根据设计任务，设计DOS菜单，菜单运行成果如图所示： 《数据结构》期末课程设计 题目第8题：最小生成树问题学院计算机学院 专业 班别 学号 姓名陈聪 2015年7月6日 一、需求分析 1、问题描述 若要在n个城市之间建设通讯网络，只需要架设n-1条线路即可。如何以最低的经济代价建设这个通讯网，是一个网的最小生成树问题。 2、基本要求 （1）利用克鲁斯卡尔算法求网的最小生成树。 （2）实现并查集。以此表示构造生成树过程中的连通分量。 （3）以文本形式输出生成树中各条边以及他们的权值。 3、实现提示 通讯线路一旦建立，必然是双向的。因此，构造最小生成树的网一定是无向网。设图的顶点数不超过30个，并为简单起见，网中边的权值设成小于100的整数，可利用C语言提供的随机数函数产生。 图的存储结构的选取应和所作操作向适应。为了便于选择权值最小的边，此题的存储结构既不选用邻接矩阵的数组表示法，也不选用邻接表，而是以存储边(带权)的数组即边集数组表示图。 二、详细设计 根据课设题目要求，拟将整体程序分为三大模块，分别是：图的存储结构，并查集的实现，克鲁斯卡尔算法的实现。 1、边集数组的类型定义： typedef struct { int x, y; int w; }edge; x表示起点，y表示终点，w为权值。 2、并查集功能的实现由以下函数实现： Make_Set(int x)初始化集合； Find_Set(int x) 查找x元素所在的集合,回溯时压缩路径； Union(int x, int y, int w)合并x,y所在的集合。 3、克鲁斯卡尔算法的实现 该算法的实现位于主函数中： qsort(e, n, sizeof(edge), cmp); //将边排序 printf("最小生成树的各条边及权值为：\n"); for (i = 0; i < n; i++) { x = Find_Set(e[i].x); y = Find_Set(e[i].y); if (x != y ) { printf("%c - %c : %d\n", e[i].x + 'A', e[i].y + 'A', e[i].w); Union(x, y, e[i].w); } } 4、设计中还包含以下函数： （1）/* 比较函数，按权值(相同则按x坐标)非降序排序*/ int cmp(const void *a, const void *b) { if ((*(edge *)a).w == (*(edge *)b).w) { return (*(edge *)a).x - (*(edge *)b).x; } return (*(edge *)a).w - (*(edge *)b).w; } （2）快排函数qsort,包含在stdlib.h头文件里 qsort(e, n, sizeof(edge), cmp); （3）C语言提供的随机数函数srand( unsigned int seed ); 使用随机数函数如下： srand( (unsigned)time( NULL ) ); for( i = 0; i < n;i++ ) 《数据结构》 课程设计报告 学号 姓名 班级 指导教师 安徽工业大学计算机学院 2010年6月 建立二叉树和线索二叉树 1.问题描述： 分别用以下方法建立二叉树并用图形显示出来： 1）用先序遍历的输入序列 2）用层次遍历的输入序列 3）用先序和中序遍历的结果 2.设计思路： 分三个方式去实现这个程序的功能，第一个实现先序遍历的输入数列建立二叉树；第二个是用层次遍历的方法输入序列；第三个是用先序和后序遍历的结果来建立二叉树；三种方法建立二叉树后都进行输出。关键是将这三个实现功能的函数写出来就行了；最后对所建立的二叉树进行中序线索化，并对此线索树进行中序遍历（不使用栈）。 3.数据结构设计： 该程序的主要目的就是建立二叉树和线索二叉树，所以采用树的存储方式更能完成这个程序； 结点的结构如下： typedef struct bnode { DataType data; int ltag,rtag; struct bnode *lchild, *rchild; } Bnode, *BTree; 4.功能函数设计： BTree CreateBinTree() 用先序遍历的方法讲二叉树建立； BTree CREATREE() 用队列实现层次二叉树的创建； void CreatBT()； 用先序和中序遍历的结果建立二叉树； void InThread(BTree t,BTree pre) 中序线索化； 5.编码实现： #include 实验五最小生成树 一、需求分析 1、本程序の目の是要建设一个最经济の网，，输出相应の最小生成树。在这里都用整型数来代替。 2、测试数据 见下程序。 二、概要设计 主程序： int main() { 初始化； while (条件) { 接受命令; 处理命令; } return 0; } 三、详细设计 #include { char adjvex; int lowcost; }Close,close[MAX_VERTEX_NUM]; typedef struct ArcNode { int adjvex; ArcNode *nextarc; int info; }ArcNode; typedef struct VNode { char data; ArcNode *firstarc; }VNode,AdjList[MAX_VERTEX_NUM]; typedef struct { AdjList verties; int vexnum,arcnum; }ALGraph; ALGraph G;//对象G int LocateVek(ALGraph ,char );//返回结点位置 int minimum(close);//返回最小数 void MinSpanTree_PRIM(ALGraph,char);//最小生成树 void Create(ALGraph &);//创建邻接表 int main() { char a;int i=1; Create(G); /*for(int i=1;i<=G.vexnum;i++) { for(s=G.verties[i].firstarc;s!=NULL;s=s->nextarc) cout< 课程设计任务书 2011 —2012 学年第一学期 电子与信息工程系计算机专业09计算机一班班级 课程设计名称：数据结构课程设计 设计题目：排序二叉树的遍历 完成期限：自2012 年 1 月 2 日至2012 年 1 月 6 日共 1 周 设计依据、要求及主要内容（可另加附页）： 一、设计目的 熟悉各种数据结构和运算，会使用数据结构的基本操作解决一些实际问题。 二、设计要求 （1）重视课程设计环节，用严谨、科学和踏实的工作态度对待课程设计的每一项任务； （2）按照课程设计的题目要求，独立地完成各项任务，严禁抄袭；凡发现抄袭，抄袭者与被抄袭者皆以零分计入本课程设计成绩。凡发现实验报告或源程序雷同，涉及的全部人员皆以零分计入本课程设计成绩； （3）学生在接受设计任务后，首先要按设计任务书的要求编写设计进程表； （4）认真编写课程设计报告。 三、设计内容 排序二叉树的遍历（用递归或非递归的方法都可以） 1)问题描述 输入树的各个结点，建立排序二叉树，对建立的排序二叉树进行层次、先序、中序和后序遍历并统计该二叉树中叶子结点的数目。 2)基本要求 (1)用菜单实现 (2)能够输入树的各个结点，并能够输出用不同方法遍历的遍历序列和叶子结点的数目。 四、参考文献 1．王红梅．数据结构．清华大学出版社 2．王红梅．数据结构学习辅导与实验指导．清华大学出版社3．严蔚敏，吴伟民．数据结构（C语言版）．清华大学出版社 #include 一、高校社团管理 在高校中，为了丰富学生的业余生活，在学校的帮助下，会成立许多社团，少则几个，多则几十个。为了有效管理这些社团，要求编写程序实现以下功能：1．社团招收新成员； 2．修改社团相应信息 3．老成员离开社团 4．查询社团情况； 5．统计社团成员数； 二、简单文本编辑器 设计一个文本编辑器，允许将文件读到内存中，也就是存储在一个缓冲区中。这个缓冲区将作为一个类的内嵌对象实现。缓冲区中的每行文本是一个字符串，将每行存储在一个双向链表的结点中，要求设计在缓冲区中的行上执行操作和在单个行中的字符上执行字符串操作的编辑命令。 基本要求： 包含如下命令列。可用大写或小写字母输入。 R：读取文本文件到缓冲区中，缓冲区中以前的任何内容将丢失，当前行是文件的第一行； W：将缓冲区的内容写入文本文件，当前行或缓冲区均不改变。 I：插入单个新行，用户必须在恰当的提示符的响应中键入新行并提供其行号。 D：删除当前行并移到下一行； F：可以从第1行开始或从当前行开始，查找包含有用户请求的目标串的第一行； C：将用户请求的字符串修改成用户请求的替换文本，可选择是仅在当前行中有效的还是对全文有效的。 Q：退出编辑器，立即结束； H：显示解释所有命令的帮助消息，程序也接受？作为H的替代者。 N：当前行移到下一行，也就是移到缓冲区的下一行； P：当前行移到上一行，也就是移到缓冲区的上一行； B：当前行移到开始处，也就是移到缓冲区的第一行； E：当前行移到结束处，也就是移到缓冲区的最后一行； G：当前行移到缓冲区中用户指定的行； V：查看缓冲区的全部内容，打印到终端上。 三、电话客户服务模拟 一个模拟时钟提供接听电话服务的时间(以分钟计),然后这个时钟将循环的 自增1(分钟)直到达到指定时间为止。在时钟的每个"时刻"，就会执行一次检查来看看对当前电话服务是否已经完成了,如果是,这个电话从电话队列中删除,模 拟服务将从队列中取出下一个电话(如果有的话)继续开始。同时还需要执行一个检查来判断是否有一个新的电话到达。如果是,其到达时间被记录下来,并为其产生一个随机服务时间,这个服务时间也被记录下来,然后这个电话被放入电话队列中,当客户人员空闲时,按照先来先服务的方式处理这个队列。当时钟到达指定时间时,不会再接听新电话,但是服务将继续,直到队列中所偶电话都得到处理为止。 基本要求： （1）程序需要的初始数据包括：客户服务人员的人数，时间限制，电话的到达速率，平均服务时间 （2）程序产生的结果包括：处理的电话数，每个电话的平均等待时间 四、停车场管理 设停车场是一个可停放n辆车的狭长通道，且只有一个大门可供汽车进出。在停车场内，汽车按到达的先后次序，由北向南依次排列（假设大门在最南端）。若停车场内已停满n辆车，则后来的汽车需在门外的便道上等候，当有车开走时，便道上的第一辆车即可开入。当停车场内某辆车要离开时，在它之后进入的车辆必须先退出停车场为它让路，待该辆车开出大门后，其他车辆再按原次序返回车场。每辆车离开停车场时，应按其停留时间的交费（从进入便道开始计时）。在这里假设汽车从便道上开走时不收取任何费用 基本要求： （1）汽车的输入信息格式为（到达/离去的标识，汽车牌照号码，到达/离去的时间）数据结构课程设计
最小生成树实验报告
运筹学试题
数据结构课程设计报告模板
五路呼叫器课程设计中北大学
最小生成树的Prim算法提高型实验报告
数据结构课程设计AVL树实现及其分析实验报告
实用运筹学习题选详解
最小生成树数据结构课程设计报告
运筹学答案_第_11_章__图与网络模型
数据结构课程设计报告
机械设计基础期末考试试题+答案解析
实验报告
大数据结构课程设计-最小生成树
数据结构课程设计
最小生成树-实验报告
数据结构课程设计二叉树遍历查找
数据结构课程设计
相关文档
- 中北大学本科培养方案.doc
- 机械设计基础单级斜齿圆柱齿轮减速器课程设计
- 五路呼叫器课程设计中北大学
- 本科培养方案
- (完整版)中北大学机械设计基础单级斜齿圆柱齿轮减速器 毕业课程设计
- 机械设计课程设计说明书(减速器)
- 中北大学11-12学年第二学期机械设计基础试题(A卷)
- 材料成型及控制工程就业调查报告
- 中北大学参考书
- 中北大学本科培养方案.doc
- 2019年中北大学考研参考书目初试参考书目
- 机械设计基础期末考试试题+答案解析
- 中北大学机械设计基础
- 单级斜齿圆柱齿轮减速器(10号)用于双滚式压碎机的传动系统中.
- 机械设计基础考研试卷
- 测控技术及仪器专业培养方案-中北大学仪器与电子学院
- 中北大学本科培养方案.doc
- 中北大学机械设计基础试卷分析
- 机械设计基础单级斜齿圆柱齿轮减速器课程设计
- 机械设计基础一级斜齿圆柱齿轮减速器_课程设计(中北大学)