算法实验报告(三)

PAGEPAGE4西南大学实验报告《算法设计与分析》课程2014-2015学年度第1学期专业年级计算机科学与技术姓名罗江涛学号222012321210140任课教师何国斌实验教师何国斌上机地点25教西南大学计算机与信息科学学院2014年9月

《算法设计与分析》课程实验报告（一）实验题目动态规划实验时间2014/9一、实验目的及要求了解动态规划二、实验内容、过程和结果（实验主要内容的介绍、主要的操作步骤、程序代码和测试数据及实验结果）多段图问题#include<stdio.h>#include<conio.h>#include<malloc.h>#defineMAX_VERTEX_NUM50typedefstructArcNode{ intadjvex;//该弧所指向的顶点的位置 intvalue;//该结点与邻接结点间的代价 structArcNode*nextarc;//指向下一条弧的指针}ArcNode,*node;typedefstructVNode{ intdata;//顶点信息ArcNode*firstArc;//指向第一条依附该顶点的弧的指针}VNode,AdjList[MAX_VERTEX_NUM];typedefstructGraph{ AdjListvertices; intvexnum,arcnum;//图的当前顶点数和弧数}*ALGraph;intbuild_adList(ALGraphG,intn,inta){//建立邻接表 intv,m,i,t,h; nodep,q; if(n<0)returnprintf("ERROR"); G->vexnum=n;//图的顶点数 if(a<0)returnprintf("ERROR"); G->arcnum=a;//图的弧数 for(m=0;m<n;m++) { G->vertices[m].data=m; G->vertices[m].firstArc=NULL; } for(m=1;m<=a;m++) { i=1; printf("输入第%d条弧:",m); scanf("%d,%d,%d",&t,&h,&v); p=(ArcNode*)malloc(sizeof(ArcNode)); p->adjvex=h; p->value=v; p->nextarc=NULL; while(G->vertices[i].data!=t)i++;//转到下一个结点 if(!G->vertices[i].firstArc)//终点 G->vertices[i].firstArc=p; else {//若当前结点有后继节点则后移 for(q=G->vertices[i].firstArc;q->nextarc;q=q->nextarc); q->nextarc=p;//新开辟结点 } } returnv;}voidprint_Graph(ALGraphG){//打印邻接表 ArcNode*p=(ArcNode*)malloc(sizeof(ArcNode)); inti; for(i=1;i<G->vexnum;i++) { p=G->vertices[i].firstArc; printf("[%d]",i); while(p) { printf("->%d,%d",p->adjvex,p->value);//第i个结点的邻接结点信息 p=p->nextarc; } printf("\n"); }}voidfgraph(ALGraphG,intk,intn){//多段图ALGraphG，n为结点数，k为图的段数//输入是按段的顺序给结点编号 intcost[100]; intd[100]; intpath[100]; intj,r,i,min,w,value; nodep; cost[n]=0; for(j=n-1;j>=1;j--)//向前处理结点 { p=G->vertices[j].firstArc; min=p->value+cost[p->adjvex];//初始化路径最小代价 r=p->adjvex; value=p->value; while(p!=NULL) {//r是一个的这样的结点，权值c(j,r)+cost[r]取最小值 if((p->value+cost[p->adjvex])<min) { min=p->value+cost[p->adjvex];//p->value=c(j,r) r=p->adjvex; value=p->value; } p=p->nextarc; } cost[j]=value+cost[r];//当前节点的代价值 d[j]=r;//决策阶段，各结点到终点最小代价路径上前方顶点的编号 } path[1]=1;path[k]=n; for(i=2;i<=k-1;i++)//找出最小代价路径上的结点 path[i]=d[path[i-1]]; printf("最小成本为:%d\n",cost[1]); printf("最小成本路径为:"); for(w=1;w<=k;w++) printf("%d->",path[w]);}voidmain(){ ALGraphg;intn,a,k; g=(ALGraph)malloc(sizeof(ALGraph));printf("请输入多段图节点数目:");scanf("%d",&n); printf("请输入多段图边的数目:");scanf("%d",&a); printf("请输入多段图的段数:"); scanf("%d",&k);printf("输入多段图的弧的信息（弧头，弧尾，权值）\n"); build_adList(g,n,a);