数据结构最小生成树课程设计
① C语言 课程设计 最小生成树的详细设计，还有能让人理解的话解释一下这个编程到底在做什么事情
我已经发到你的邮箱
② 求数据结构最小生成树的实验报告，包含流程图，
数据结构（实验报告）
姓名： 高 申 雷
学号： 0613042024
日期： 2008年3月25日
一、实验题目： 停 车 场 管 理
二、问题描述：
设停车场是一个可以停放n辆汽车的狭长通道，且只有一个大门可以供车辆进出。车辆按到达停车场时间的早晚依次从停车场最里向大门口处停放（最先到达的第一辆车放在停车场的最里面）。如果停车场已放满n辆车，则后来的车只能在停车场大门外的便道上等待，一旦停车场内有车开走，则排在便道上的第一辆车就进入停车场。停车场内如有某辆车要开走，在它之后进入停车场的车都必须先退出停车场为它让路，待其开出停车场后，这些车辆再依原来的次序进场。每辆车在离开停车场时，都应根据它在停车场内停留的时间长短交费。如果停留在便道上的车未进停车场就要离去，允许其离去，不收停车费，并且仍然保持在便道上等待的车辆次序。编制一程序模拟该停车场的管理。
三、需求分析：
停车场采用栈式结构，停车场外的便道采用队列结构（即便道就是等候队列）。停车场的管理流程如下：
①当车辆要进入停车场时，检查停车场是否已满，如果未满则车辆进栈（车辆进入停车场）；如果停车场已满，则车辆进入等候队列（车辆进入便道等候）。
②当车辆要求出栈时，该车到栈顶的那些车辆先弹出栈（在它之后进入的车辆必须先退出车场为它让路），再让该车出栈，其他车辆再按原次序进栈（进入车场）。当车辆出栈完毕后，检查等候队列（便道）中是否有车，有车则从队列头取出一辆车压入栈中。
四、概要设计：
1、用栈模拟停车场，用队列模拟车场外的便道，按照从终端读入的输入数据序列进行模拟管理。
2、每一组输入数据包括三个数据项：汽车到达或离去的信息，汽车牌照号码以及到达或离去的时刻。
3、每次输入完进行输出操作：若是车辆到达，输出汽车在停车场内或便道上的停车位置；若是车辆离去，输出停留时间和应缴纳的费用（在便道上停留的时间不收费）。
4、其中栈以顺序结构实现，队列以链表结构实现。
五、详细设计：
1、定义栈（停车场） struct stack
初始化栈void initstack(stack* s)
元素进栈int instack(stack* s,cinfo x)
元素出栈cinfo outstack(stack* s)
2、定义队列（车场外的便道）struct queue
初始化队列void initqueue(queue* q)
元素进队列void inqueue(queue* q,int num1)
元素出队列int outqueue(queue* q)
3、处理车辆到达的情况void carrival(stack* s,queue* q,cinfo x)
处理车辆离开void carleave(stack* s1,stack* s2,queue* q,cinfo x)
4、主程序void main()
注：详细设计中的具体代码见模块代码中。
六、模块代码：
#include"iostream.h"
int N;
const int M=5;//M为单元时间的收费值
struct cinfo//定义栈中元素的类型
{ int cnum; int atime;
};
struct stack//定义栈
{ cinfo cstack[3000];//这里随便定义一个数字表示数组的长度,因为后
int top; //面会根据用户输入的N值作为停车场能够停车的
int size; //数量.
};
struct node//定义队列节点的类型
{ node* next; int nnum;
};
struct queue//定义队列
{ node *front,*rear;
};
void initstack(stack* s)//初始化栈
{ s->top=-1;
}
int instack(stack* s,cinfo x)//元素进栈
{ //int 元素进栈n;
if(s->top==N-1)
{ cout<<"Stack is full!"<<endl; return 0;
} else
{ s->cstack[++s->top]=x;
return 1;
}
}
cinfo outstack(stack* s)//元素出栈
{ cinfo y;
if(s->top<0)
{ y.cnum=NULL;
y.atime=NULL;
return y;
} else
{ s->top--;
return s->cstack[s->top+1];
}
}
void initqueue(queue* q)//初始化队列
{ q->front=new node;
q->rear=q->front;
q->front->next=NULL;
q->front->nnum=0;
}
void inqueue(queue* q,int num1)//元素进队列
{ node* p;
p=new node;
p->nnum=num1;
p->next=NULL;
q->rear->next=p;
q->rear=p;
q->front->nnum++;
}
int outqueue(queue* q)//元素出队列
{ node* p;
int n;
if(q->front==q->rear) return 0;
else {
p=q->front->next;
q->front->next=p->next;
if(p->next==NULL)
q->rear=q->front;
n=p->nnum;
delete p;
q->front->nnum--;
return n;
}
}
void carrival(stack* s,queue* q,cinfo x)//处理车辆到达的情况
{ int f;
f=instack(s,x);
if(f==0) {
inqueue(q,x.cnum);
cout<<"The Number"<<x.cnum<<" "<<"car park into the pos"<<q->front->nnum<<" "<<"of the road."<<endl;
} else
{ cout<<"The Number"<<x.cnum<<" "<<"car park into the pos"<<s->top+1<<" "<<"of the room."<<endl;
}
}
void carleave(stack* s1,stack* s2,queue* q,cinfo x)//处理车辆离开
{ node* p;
cinfo y;
int a,n=0;
while((s1->top>-1)&&(n==0))
{ y=outstack(s1);
if(y.cnum!=x.cnum) {
a=instack(s2,y);
} else
n=1;
}
if(y.cnum==x.cnum)
{ cout<<"The number"<<x.cnum<<" "<<"car want to leave,the charge is"<<" "<<(x.atime-y.atime)*M<<" "<<"yuan!"<<endl;
while(s2->top>-1)
{ y=outstack(s2);
n=instack(s1,y);
}
a=outqueue(q);
if(a!=0)
{ y.cnum=a; y.atime=x.atime;
n=instack(s1,y);
cout<<"The Number"<<y.cnum<<" "<<"car park into the pos"<<s1->top+1<<" "<<"of the room."<<endl;
}
} else
{ while(s2->top>-1)
{ y=outstack(s2);
n=instack(s1,y);
}
p=q->front;
n=0;
while(p->next!=NULL&&n==0)
{ if(p->next->nnum!=x.cnum)
p=p->next;
else {
p->next=p->next->next;
q->front->nnum--;
if(p->next=NULL)
q->rear=q->front;
cout<<"The number"<<x.cnum<<" "<<"want to leave from the road."<<endl;
n=1;
}
}
if(n==0)
{ cout<<"You have entered a wrong number!"<<endl;
}
}
}
void main()//主程序
{ //int maxsize;
cout<<"Start，Written by ZIGZ"<<endl<<endl<<endl;
cout<<"Please enter a number as the maxsize of the roomStack:"<<endl;
cin>>N;//这里N将作为栈能存放元素的数量
while(N<=0)
{ cout<<"Oh!You have enter a wrong number,'N' should above 0.Please enter another number again:"<<endl;
cin>>N;
} //stack *max;
//max->size=maxsize;
char ch1;
stack* s1,*s2;
queue* q;
cinfo x;
int flag;
s1=new stack;
s2=new stack;
q=new queue;
initstack(s1);
initstack(s2);
initqueue(q);
flag=1;
for(;;) {cout<<"Please enter the infomation: 'A'/'D'; car number; car arrival time."<<endl;
cin>>ch1>>x.cnum>>x.atime;
switch(ch1)
{ case'A':
case'a':carrival(s1,q,x);
break;
case'D':
case'd':carleave(s1,s2,q,x);
break;
case'E':
case'e':flag=0;cout<<"Ok,the system will be shut down!Written by ZIGZ!"<<endl;
break;
default:cout<<"You have enter a wrong!!"<<endl;
}
if(flag==0)
break;
}
}
七、运行结果：
八、经验小结：
通过《停车场管理》的实验学习使我基本上理解并学会了用栈的先进后出和队列的先进先出的原理去解决实际问题的思想和方法。但是在编程方面还是很欠缺，还要加强学习。
③ 急求数据结构 C语言版 课程设计 最小生成树
#include <stdio.h>
#define inf 9999
#define max 40
void prim(int g[][max],int n) // prim的函数
{
int lowcost[max],closest[max];
int i,j,k,min;
for(i=2;i<=n;i++) // n个顶点，n-1条边
{ lowcost[i]=g[1][i]; // 初始化
closest[i]=1; // 顶点未加入到最小生成树中
}
lowcost[1]=0; // 标志顶点1加入U集合
for(i=2;i<=n;i++) // 形成n-1条边的生成树
{
min=inf;
k=0;
for(j=2;j<=n;j++) // 寻找满足边的一个顶点在U,另一个顶点在V的最小边
if((lowcost[j]<min)&&(lowcost[j]!=0))
{
min=lowcost[j];
k=j;
}
printf("(%d,%d)%d\t",closest[k],k,min);
lowcost[k]=0; // 顶点k加入U
for(j=2;j<=n;j++) // 修改由顶点k到其他顶点边的权值
if(g[k][j]<lowcost[j])
{ lowcost[j]=g[k][j];
closest[j]=k;
}
printf("\n");
}
}
int adjg(int g[][max]) // 建立无向图
{
int n,e,i,j,k,v1,v2,weight;
printf("输入顶点个数，边的条数：");
scanf("%d,%d",&n,&e);
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
g[i][j]=inf; // 初始化矩阵，全部元素设为无穷大
for(k=1;k<=e;k++)
{
printf("输入第%d条边的起点，终点，权值:",k);
scanf("%d,%d,%d",&v1,&v2,&weight);
g[v1][v2]=weight;
g[v2][v1]=weight;
}
return(n);
}
void prg(int g[][max],int n) // 输出无向图的邻接矩阵
{
int i,j;
for(i=0;i<=n;i++)
printf("%d\t",i);
for(i=1;i<=n;i++)
{
printf("\n%d\t",i);
for(j=1;j<=n;j++)
printf((g[i][j]==inf)?"\t":"%d\t",g[i][j]);
}
printf("\n");
}
void main()
{
int g[max][max],n;
n=adjg(g);
printf("输入无向图的邻接矩阵:\n");
prg(g,n);
printf("最小生成树的构造:\n");
prim(g,n);
}
④ 数据结构课程设计--用普里姆算法求最小生成树
for i:=1 to n do begin d[i]:=a[1,i]; f[i]:=false; end;
f[1]:=true; //放在生成树中回
ans:=0;
for i:=2 to n do
begin
min:=maxint;
for j:=1 to n do
if (not f[j]) and (d[j]<min) then
begin min:=d[j]; k:=j; end;
inc(ans,d[k]);
f[k]:=true;
for j:=1 to n do
if (not f[j]) and(a[k,j]<d[j]) then d[j]:=a[k,j];//修改答d
end;
⑤ 最小生成树的实现（避圈法）课程设计怎么弄
#include<stdio.h>
#include<stdlib.h>
#define M 20
#define MAX 20typedef struct
{
int begin; //头顶点
int end; //末顶点
int weight; //权值
}edge;typedef struct
{
int adj;
int weight;//权值
}AdjMatrix[MAX][MAX];typedef struct
{
AdjMatrix arc;
int vexnum, arcnum;//总边 点 的值
}MGraph;
//函数申明
void CreatGraph(MGraph *); //图构建
void sort(edge* ,MGraph *); //权值排序
void MiniSpanTree(MGraph *); //生成最小树
int Find(int *, int );// 尾顶点查找
void Swapn(edge *, int, int);//权值、头顶点、尾顶点交换
void CreatGraph(MGraph *G)//构件图
{
int i, j,n, m;
printf("请输入边数和顶点数:\n");
scanf("%d %d",&G->arcnum,&G->vexnum);
for (i = 1; i <= G->vexnum; i++)//初始化图
{
for ( j = 1; j <= G->vexnum; j++)
{
G->arc[i][j].adj = G->arc[j][i].adj = 0;
}
}
for ( i = 1; i <= G->arcnum; i++)//输入边和权值
{
printf("请输入有边的2个顶点\n");
scanf("%d %d",&n,&m);
while(n < 0 || n > G->vexnum || m < 0 || n > G->vexnum)
{
printf("输入的数字不符合要求 请重新输入:\n");
scanf("%d%d",&n,&m);
}
G->arc[n][m].adj = G->arc[m][n].adj = 1;
getchar();
printf("请输入%d与%d之间的权值:\n", n, m);
scanf("%d",&G->arc[n][m].weight);
}
printf("邻接矩阵为:\n");
for ( i = 1; i <= G->vexnum; i++)
{
for ( j = 1; j <= G->vexnum; j++)
{
printf("%d ",G->arc[i][j].adj);
}
printf("\n");
}
}void sort(edge edges[],MGraph *G)//对权值进行排序
{
int i, j;
for ( i = 1; i < G->arcnum; i++)
{
for ( j = i + 1; j <= G->arcnum; j++)
{
if (edges[i].weight > edges[j].weight)
{
Swapn(edges, i, j);//交换i和j 这两条边
}
}
}
printf("权排序之后的为:\n");
for (i = 1; i < G->arcnum; i++)
{
printf("<< %d, %d >> %d\n", edges[i].begin, edges[i].end, edges[i].weight);
}
}void Swapn(edge *edges,int i, int j)//交换权值 以及头和尾
{
int temp;
temp = edges[i].begin;
edges[i].begin = edges[j].begin;
edges[j].begin = temp;//交换头顶点 temp = edges[i].end;
edges[i].end = edges[j].end;
edges[j].end = temp;//交换尾顶点 temp = edges[i].weight;
edges[i].weight = edges[j].weight;
edges[j].weight = temp;//交换权值
}void MiniSpanTree(MGraph *G)//生成最小生成树
{
int i, j, n, m;
int k = 1;
int parent[M];
edge edges[M];
for ( i = 1; i < G->vexnum; i++)
{
for (j = i + 1; j <= G->vexnum; j++)
{
if (G->arc[i][j].adj == 1)
{
edges[k].begin = i;
edges[k].end = j;
edges[k].weight = G->arc[i][j].weight;
k++;
}
}
}
sort(edges, G);
for (i = 1; i <= G->arcnum; i++)
{
parent[i] = 0;
}
printf("最小生成树为:\n");
for (i = 1; i <= G->arcnum; i++)//核心部分
{
n = Find(parent, edges[i].begin);
m = Find(parent, edges[i].end);
if (n != m)//判断是否有回路，如果有，舍弃
{
parent[m] = n;
printf("<< %d, %d >> %d\n", edges[i].begin, edges[i].end, edges[i].weight);
}
}
}int Find(int *parent, int f)//找尾
{
while ( parent[f] > 0)
{
f = parent[f];
}
return f;
}int main(void)//主函数
{
MGraph *G;
G = (MGraph*)malloc(sizeof(MGraph));//为图动态分配存储空间
if (G == NULL)//如果图没有创建，则程序非正常结束
{
printf("memory allcation failed,goodbye");
exit(1);
}
CreatGraph(G);//创建一个图
MiniSpanTree(G);//求最小生成树
system("pause");//系统暂停运行
return 0;
⑥ 数据结构课程设计——构造可以使n个城市连接的最小生成树
用Prim吧，我资料里有联系方式
⑦ 最小生成树——最优通信网 课程设计
你这个开发语言是什么
平台
或数据库都怎样
谈
我这样才好帮你
⑧ 最小生成树课程设计
给你说说思路吧
在所有的边中选择权值最小的一个边 对其进行如下操作：专
将该边加入生成树属中 如果存在环 则删除该边
重复上面的操作 n-1 次
即可找到包含n个结点的最小生成树
至于怎么判断是否存在环 可以使用并查集 当然 最简单的方法是为每个边建立一个bool型变量 其包含在生成树里面时 设置为true 否则为false 每次加边之前判断边的头结点和尾结点的bool变量是否都为true就可以
具体怎么实现 还是希望楼主自行CODE
毕竟这个是基本功