管道铺设施工的最佳方案问题

道铺设施工佳方案问题
． 问题描述：
1 实验题目：
需某城市n居民区间铺设煤气道n居民区间需铺设n1条道假设意两区间铺设道理环境需费相选择优方案总投资问题求网生成树
2 基求：
假设m条道中选取n1条道连通n区总投资条道费网中该边权值形式出网存储采邻接表结构
3 测试数：
图出线网数作程序输入求出佳铺设方案右侧出参考解

4 简述部分象目求：
I函数部分：
象：图G
目：图G分配空间作续调函数参数
求：
II Create_ALGraph( )函数部分：
象：顶点边权值
目：顶点边存放起构成图
求：构造顶点表顶点邻接表构造图
III Create_WLGraph( )函数部分：
象：图G
目：图中权值存放次存放w指结构体中
求：权值存放次分存放该边左右顶点
IV select_info( )函数部分：
象：w指结构体
目：该结构体中权值升序排列
求：采简单选择法进行排序
V Create_TLGraph( )函数部分：
象：排序w指结构体
目：找构成生成树边
求：权值升序排列判断边否构成回路取舍边
二． 需求分析
1 程序达基：
n区m条道中选取n1条道实现连通n区时权值
2 输入输出形式输入值范围：
程序运行户根提示信息：Please input the vertices and the edges输入顶点数边数根提示信息：Please input the information of the vertices输入顶点信息然进入循环创建顶点邻接表根提示信息Please input the information of edgesPlease input the information of weight次输入顶点顶点身两者间权值创建图完毕户输入完毕程序动输出运行结果输入值必须字母浮点数必区分写
3 测试数求：
户输入字母时输入写写该程序识正常运行必须根提示信息面出参考形式针性输入逗号
三． 概设计
实现述功该程序邻接表存储图需图抽象数类型
1 图抽象数类型定义：
ADT ALGraph{
数象：D{i123nn}
数关系：R
基操作：Create_ALGraph(G)创建图
Create_WLGraph(G) 图G中顶点权值存放新图中权值存放次
select_info(W G)新图W中权值升序排列
Create_TLGraph(w G)生成树顶点 （i j）形式输出
}ADT ALGraph
2程序保护模块：
函数模块
图模块
调关系：

3算法流程图：


Create_ALGraph( )算法流程图： Create_WLGraph()算法流程图：




Create_TLGraph( )算法流程图：

四． 详细设计
1 相关头文件调说明：
#include
#include
#define MaxVerNum 100
2元素类型结点类型结点指针类型：
static void forcefloat(float *p)
{
float f *p
forcefloat(&f)
}
typedef struct node
{ int adjvex
float info
struct node *next
}EdgeNode
typedef struct vnode
{ char vertex
EdgeNode *firstedge
}VertexNode
typedef VertexNode AdjList[MaxVerNum]
struct bian
{int zy
float info
}
typedef struct
{char v[MaxVerNum]
struct bian e[MaxVerNum]
}WGraph
struct visit
{visited[MaxVerNum]
position[MaxVerNum]
vvpp[MaxVerNum][MaxVerNum]
}
3邻接表类型：
typedef struct
{AdjList adjlist
int ne
}ALGraph
部分基操作伪码实现
Create_ALGraph(ALGraph *G)
{int ij char pq
int k * int x0 *
EdgeNode *s
char ab
printf(Please input the vertices and the edges＼n)
scanf(dd&(G>n)&(G>e))
printf(Please input the information of the vertices＼n)
getchar()
for(i0i<(G>n)i++)
{scanf(c&(G>adjlist[i]vertex))
G>adjlist[i]firstedgeNULL
*if(G>adjlist[i]vertex＇ ＇&&G>adjlist[i]vertex＇＼n＇&&G>adjlist[i]vertex＇ ＇)
x++*
}
for(k0k<2*(G>e)k++)
{printf(Please input the information of edges＼n)
getchar()
scanf(cc&p&q)
s(EdgeNode *)malloc(sizeof(EdgeNode))
s>adjvexq64
ip64
getchar()
printf(Please input the information of weight＼n)
scanf(f&(s>info))
s>nextG>adjlist[i1]firstedge
G>adjlist[i1]firstedges
}*
printf(Please output the information＼n)
printf(dd＼nG>nG>e)
printf(xd＼nx)
for(i0ini++)
{printf(c＼nG>adjlist[i]vertex)
sG>adjlist[i]firstedge
while(sNULL)
{printf(the linbian is dthe info is 1f＼ns>adjvexs>info)
ss>next
}
}*
}
int Panduan_Vertex(int kint iWGraph *wEdgeNode *s)
{int t
for(t0t if((w>e[t])yi+1&&(w>e[t])zs>adjvex)
return 1
return 0
}
void select_info(WGraph *WALGraph *G)
{int ijpk
float t
for(i0i<(G>e)i++)
{pi
for(ji+1j<(G>e)j++)
if(W>e[j]infoe[p]info) pj
if(pi)
{tW>e[p]info
W>e[p]infoW>e[i]info
W>e[i]infot
kW>e[p]z
W>e[p]zW>e[i]z
W>e[i]zk
kW>e[p]y
W>e[p]yW>e[i]y
W>e[i]yk
}
}*
for (i0i<(G>e)i++)
printf(1f W>e[i]info)
printf(＼n)*
}
int judge_vertex(WGraph *wint istruct visit *vp)
{
if(vp>visited[w>e[i]z1]1&&vp>visited[w>e[i]y1]1)
return 1
else if(vp>visited[w>e[i]z1]1&&vp>visited[w>e[i]y1]1)
return 2
else if(vp>visited[w>e[i]y1]1&&vp>visited[w>e[i]z1]1)
return 3
else if(vp>visited[w>e[i]z1]1&&vp>visited[w>e[i]y1]1)
return 4
}
void Create_TLGraph(WGraph *wALGraph *G)
{WGraph T
int ijthk2
int m1 int abcbcd
struct visit *vp
vp(struct visit *)malloc(sizeof(struct visit))
for(i0i<(G>n)i++)
{vp>visited[i]1
vp>position[i]1
vp>vvpp[i][0]i+1
for(j1jnj++)
vp>vvpp[i][j]0
}
Tv[0]w>v[w>e[0]z1]
Tv[1]w>v[w>e[0]y1]
vp>visited[w>e[0]z1]1
vp>position[w>e[0]z1]w>e[0]z
for(j0j<(G>n)j++)
if(vp>vvpp[w>e[0]z1][j]0)
{vp>vvpp[w>e[0]z1][j]w>e[0]y
break}
vp>visited[w>e[0]y1]1
vp>position[w>e[0]y1]w>e[0]z
Te[0]infow>e[0]info
Te[0]zw>e[0]z
Te[0]yw>e[0]y
for(i1i<(G>e)i++)
{tjudge_vertex(wivp)
if(t4)
{if(vp>position[w>e[i]z1]vp>position[w>e[i]y1])
continue
else{ abc0 bcd0
for(j0jnj++)
if(vp>vvpp[vp>position[w>e[i]y1]1][j]0)
abc++
for(j0jnj++)
if(vp>vvpp[vp>position[w>e[i]z1]1][j]0)
bcd++
for(jbcdh0jn&&h {vp>vvpp[(vp>position[w>e[i]z1])1][j]vp>vvpp[(vp>position[w>e[i]y1])1][h]
vp>vvpp[vp>position[w>e[i]y1]1][h]0
}
for(hbcdh vp>position[(vp>vvpp[vp>position[w>e[i]z1]1][h])1]vp>position[w>e[i]z1]
Te[m]infow>e[i]info
Te[m]zw>e[i]z
Te[m]yw>e[i]y
m++
}
}
else if(t1)
{ vp>visited[w>e[i]z1]1
vp>visited[w>e[i]y1]1
Tv[k++]w>v[w>e[i]z1]
Tv[k++]w>v[w>e[i]y1]
Te[m]infow>e[i]info
Te[m]zw>e[i]z
Te[m]yw>e[i]y
m++
vp>position[w>e[i]z1]w>e[i]z
vp>position[w>e[i]y1]w>e[i]z
vp>vvpp[w>e[i]z1][1]w>e[i]y
vp>vvpp[w>e[i]y1][0]0
}
else if(t2)
{vp>visited[w>e[i]z1]1
vp>position[w>e[i]z1]vp>position[w>e[i]y1]
for(j0j<(G>n)j++)
if(vp>vvpp[vp>position[w>e[i]y1]1][j]0)
{vp>vvpp[vp>position[w>e[i]y1]1][j]w>e[i]z
break
}
vp>vvpp[w>e[i]z1][0]0
Tv[k++]w>v[w>e[i]z1]
Te[m]infow>e[i]info
Te[m]zw>e[i]z
Te[m]yw>e[i]y
m++
}
else if(t3)
{vp>visited[w>e[i]y1]1
vp>position[w>e[i]y1]vp>position[w>e[i]z1]
for(j0j<(G>n)j++)
if(vp>vvpp[vp>position[w>e[i]z1]1][j]0)
{vp>vvpp[vp>position[w>e[i]z1]1][j]w>e[i]y
break
}
vp>vvpp[w>e[i]y1][0]0
Tv[k++]w>v[w>e[i]y1]
Te[m]infow>e[i]info
Te[m]zw>e[i]z
Te[m]yw>e[i]y
m++
}
}
printf(Please output the information＼n)
for(i0i<(G>n)1i++)
printf((cc)＼nTe[i]z+64Te[i]y+64)
}
void Create_WLGraph(ALGraph *G)
{int ijtmk0
EdgeNode *s*p
WGraph *W
W(WGraph *)malloc(sizeof(WGraph))
W>v[0]G>adjlist[0]vertex
sG>adjlist[0]firstedge
while(sNULL)
{W>e[k]z1
W>e[k]ys>adjvex
W>e[k]infos>info
k++
ss>next
}
for(i1i<(G>n)i++)
{W>v[i]G>adjlist[i]vertex
sG>adjlist[i]firstedge
while(sNULL)
{mPanduan_Vertex(kiWs)
if(m1)
{ss>next
continue}
else
{ W>e[k]zi+1
W>e[k]ys>adjvex
W>e[k]infos>info
k++
ss>next
}
}
}*
printf(Please output the information＼n)
for(i0ini++)
printf(c＼nW>v[i])
for(i0iei++)
printf(dd1f＼nW>e[i]zW>e[i]yW>e[i]info)*
select_info(WG)
Create_TLGraph(WG)
}
4 函数伪码：
main()
{ALGraph *G
G(ALGraph *)malloc(sizeof(ALGraph))
Create_ALGraph(G)
Create_WLGraph(G)
}
5函数调关系：
五．调试分析
1出现问题解决方法：
刚开始写程序时考虑全面连通图闭合回路算法中遇困难采方法解决问题：
顶点分放结构体中结构体中数组visited[i]记录顶点Vi否访问情况position[i]记录顶点Vi具体位置二维数组vvpp[i][j]记录已该顶点左顶点右顶点权值存入T中该权值右顶点左顶点编号具体思想：权值存入T中相应左右顶点放二维数组中欲权值加入T中先检验该权值两顶点否二维数组中该权值存入T中该权值舍（该权值加入T中会出现回路）
2 方法优缺点分析：
优点：①思想较简单容易令理解
②写核心算法时先字母顶点相应数字代数字转化成字母回时利数字ASCII码值固定差值保证户输入时写字母该程序识
缺点：采数字代字母中间转换关系较复杂尤应关系理清需足够耐心细心
3．算法时间空间复杂度分析：
（1）Create_ALGraph( )算法中读入顶点操作执行n次读入边操作执行2m次时间复杂度O（n+2m）
（2）Create_WLGraph( )算法读入权值左右顶点操作执行n次时间复杂度O（n）
（3）Create_TLGraph( )算法中根判断否构成回路取舍边n条边执行n次时间复杂度O（n）
（4）select_info( )函数采简单选择法排序时间复杂度O（）
（5）算法空间复杂度O（1）
六．说明
程序运行户根提示输入顶点数边数顶点信息边信息权值输入完毕程序会动顶点（i j）形式输出生成树边
七．调试结果
输入数：915ABCDEFGHIAB328AC446AH121AI182BA328BC59CA446CB59CD213CE411CG564DC213DE673DF987EC411ED673EF856EG105FD987FE856FI792GC564GE105GH525HA121HG525HI87IA182IF792IH87(双引号需输入)
输出数：(BC)(HI)(EG)(AH)(CD)(AB)(CE)(FI)
运行结果截屏：



八．附录
源程序清单：
#include *调头文件库说明*
#include
#define MaxVerNum 100
static void forcefloat(float *p)
{
float f *p *TC中支持浮点数添加程序段*
forcefloat(&f)
}
typedef struct node *构造邻接表结构体*
{ int adjvex
float info *存放权值*
struct node *next *指邻接点指针域*
}EdgeNode
typedef struct vnode *构造顶点表结构体*
{ char vertex *顶点域*
EdgeNode *firstedge *边表头指针*
}VertexNode
typedef VertexNode AdjList[MaxVerNum]
typedef struct *构造图结构体*
{AdjList adjlist *邻接表*
int ne *顶点数边数*
}ALGraph
struct bian *存放权值左右顶点结构体*
{int zy
float info
}
typedef struct *该结构体存放次权值相应顶点*
{char v[MaxVerNum]
struct bian e[MaxVerNum]
}WGraph
struct visit *该结构体存放结点访问情况
{visited[MaxVerNum] 位置结点关系*
position[MaxVerNum]
vvpp[MaxVerNum][MaxVerNum]
}
Create_ALGraph(ALGraph *G) *创建图*
{int ij char pq
int k
EdgeNode *s
char ab
printf(Please input the vertices and the edges＼n) *输入顶点数边数*
scanf(dd&(G>n)&(G>e))
printf(Please input the information of the vertices＼n)
getchar()
for(i0i<(G>n)i++) *建立n顶点顶点表*
{scanf(c&(G>adjlist[i]vertex)) *读入顶点信息*
G>adjlist[i]firstedgeNULL
}
for(k0k<2*(G>e)k++) *建立边表*
{printf(Please input the information of edges＼n)
getchar()
scanf(cc&p&q) *读入边顶点*
s(EdgeNode *)malloc(sizeof(EdgeNode))
s>adjvexq64 *邻接点序号q64*
ip64
getchar()
printf(Please input the information of weight＼n) *读入权值*
scanf(f&(s>info))
s>nextG>adjlist[i1]firstedge *新边表结点s插入顶点Vi边表头部*
G>adjlist[i1]firstedges
}
}
int Panduan_Vertex(int kint iWGraph *wEdgeNode *s) *判断该边已读入w指
{int t 结构体中*
for(t0t if((w>e[t])yi+1&&(w>e[t])zs>adjvex)
return 1
return 0
}
void select_info(WGraph *WALGraph *G) *w指结构体中权值升序
{int ijpk 排列*
float t
for(i0i<(G>e)i++) *简单选择排序*
{pi
for(ji+1j<(G>e)j++)
if(W>e[j]infoe[p]info) pj
if(pi)
{tW>e[p]info *两条边权值左右顶点进行交换*
W>e[p]infoW>e[i]info
W>e[i]infot
kW>e[p]z
W>e[p]zW>e[i]z
W>e[i]zk
kW>e[p]y
W>e[p]yW>e[i]y
W>e[i]yk
}
}*
for (i0i<(G>e)i++)
printf(1f W>e[i]info)
printf(＼n)*
}
int judge_vertex(WGraph *wint istruct visit *vp) *判断顶点访问情况*
{
if(vp>visited[w>e[i]z1]1&&vp>visited[w>e[i]y1]1)
return 1
else if(vp>visited[w>e[i]z1]1&&vp>visited[w>e[i]y1]1)
return 2
else if(vp>visited[w>e[i]y1]1&&vp>visited[w>e[i]z1]1)
return 3
else if(vp>visited[w>e[i]z1]1&&vp>visited[w>e[i]y1]1)
return 4
}
void Create_TLGraph(WGraph *wALGraph *G) *生成生成树*
{WGraph T
int ijthk2
int m1 int abcbcd
struct visit *vp
vp(struct visit *)malloc(sizeof(struct visit))
for(i0i<(G>n)i++) *顶点访问情况位置顶点
{vp>visited[i]1 相互关系进行初始化*
vp>position[i]1
vp>vvpp[i][0]i+1
for(j1jnj++)
vp>vvpp[i][j]0
}
Tv[0]w>v[w>e[0]z1]
Tv[1]w>v[w>e[0]y1]
vp>visited[w>e[0]z1]1
vp>position[w>e[0]z1]w>e[0]z
for(j0j<(G>n)j++)
if(vp>vvpp[w>e[0]z1][j]0)
{vp>vvpp[w>e[0]z1][j]w>e[0]y
break}
vp>visited[w>e[0]y1]1
vp>position[w>e[0]y1]w>e[0]z
Te[0]infow>e[0]info
Te[0]zw>e[0]z
Te[0]yw>e[0]y
for(i1i<(G>e)i++)
{tjudge_vertex(wivp) *根顶点访问情况选取相应操作*
if(t4) *两顶点均已访问情况*
{if(vp>position[w>e[i]z1]vp>position[w>e[i]y1]) *两顶点位置相*
continue *舍条边否会构成回路*
else{ abc0 bcd0 *两顶点位置*
for(j0jnj++)
if(vp>vvpp[vp>position[w>e[i]y1]1][j]0)
abc++
for(j0jnj++)
if(vp>vvpp[vp>position[w>e[i]z1]1][j]0)
bcd++
for(jbcdh0jn&&h {vp>vvpp[(vp>position[w>e[i]z1])1][j]vp>vvpp[(vp>position[w>e[i]y1])1][h]
vp>vvpp[vp>position[w>e[i]y1]1][h]0 *原数组置零*
}
for(hbcdh vp>position[(vp>vvpp[vp>position[w>e[i]z1]1][h])1]vp>position[w>e[i]z1]
Te[m]infow>e[i]info *该边存入T中*
Te[m]zw>e[i]z
Te[m]yw>e[i]y
m++
}
}
else if(t1) *两顶点未访问情况*
{ vp>visited[w>e[i]z1]1
vp>visited[w>e[i]y1]1
Tv[k++]w>v[w>e[i]z1]
Tv[k++]w>v[w>e[i]y1]
Te[m]infow>e[i]info *该边存入T中*
Te[m]zw>e[i]z
Te[m]yw>e[i]y
m++
vp>position[w>e[i]z1]w>e[i]z *两顶点位置改相*
vp>position[w>e[i]y1]w>e[i]z
vp>vvpp[w>e[i]z1][1]w>e[i]y *两顶点存放数组中*
vp>vvpp[w>e[i]y1][0]0
}
else if(t2) *左顶点未访问右顶点已访问情况*
{vp>visited[w>e[i]z1]1
vp>position[w>e[i]z1]vp>position[w>e[i]y1] *左顶点位置改右顶点位置*
for(j0j<(G>n)j++) *两顶点存放数组中*
if(vp>vvpp[vp>position[w>e[i]y1]1][j]0)
{vp>vvpp[vp>position[w>e[i]y1]1][j]w>e[i]z
break
}
vp>vvpp[w>e[i]z1][0]0
Tv[k++]w>v[w>e[i]z1]
Te[m]infow>e[i]info *该边存放T中*
Te[m]zw>e[i]z
Te[m]yw>e[i]y
m++
}
else if(t3) *右顶点未访问左顶点已访问情况*
{vp>visited[w>e[i]y1]1
vp>position[w>e[i]y1]vp>position[w>e[i]z1] *右顶点位置改左顶点位置*
for(j0j<(G>n)j++) *两顶点存放数组中*
if(vp>vvpp[vp>position[w>e[i]z1]1][j]0)
{vp>vvpp[vp>position[w>e[i]z1]1][j]w>e[i]y
break
}
vp>vvpp[w>e[i]y1][0]0
Tv[k++]w>v[w>e[i]y1]
Te[m]infow>e[i]info *该边存放T中*
Te[m]zw>e[i]z
Te[m]yw>e[i]y
m++
}
}
printf(Please output the information＼n)
for(i0i<(G>n)1i++) *顶点形式输出生成树*
printf((cc)＼nTe[i]z+64Te[i]y+64)
}
void Create_WLGraph(ALGraph *G) *边权值存次w指结构体中*
{int ijtmk0
EdgeNode *s*p
WGraph *W
W(WGraph *)malloc(sizeof(WGraph))
W>v[0]G>adjlist[0]vertex
sG>adjlist[0]firstedge *顶点A顶点边存放w指结构体中*
while(sNULL)
{W>e[k]z1
W>e[k]ys>adjvex
W>e[k]infos>info
k++
ss>next
}
for(i1i<(G>n)i++)
{W>v[i]G>adjlist[i]vertex
sG>adjlist[i]firstedge
while(sNULL)
{mPanduan_Vertex(kiWs) *调该函数确定该边权值否重复出现*
if(m1) *直接跳*
{ss>next
continue}
else *该边存放w指结构体中*
{ W>e[k]zi+1
W>e[k]ys>adjvex
W>e[k]infos>info
k++
ss>next
}
}
}
select_info(WG) *调该函数权值排升序*
Create_TLGraph(WG) *调该函数确定生成树*
}
main()
{ALGraph *G
G(ALGraph *)malloc(sizeof(ALGraph))
Create_ALGraph(G) *创建图*
Create_WLGraph(G)
}
文档香网(httpswwwxiangdangnet)户传

《香当网》用户分享的内容，不代表《香当网》观点或立场，请自行判断内容的真实性和可靠性！
该内容是文档的文本内容，更好的格式请下载文档