算法实验报告三

西南大学实验报告《算法设计与分析》课程学年度第学期2014-20151专业年级计算机科学与技术姓名____________罗江涛________________学号任课教师_________何国斌______________实验教师_________何国斌______________上机地点____________25______________西南大学计算机与信息科学学院年月20149《算法设计与分析》课程实验报告

（一）实验题目动态规划实验时间2014/9

一、实验目的及要求了解动态规划

二、实验内容、过程和结果实验主要内容的介绍、主要的操作步骤、程序代码和测试数据及实验结果多段图问题#includestdio.h#includeconio.h#includemalloc.hftdefine MAX_VERTEX_NUM50typedef struct ArcNode{int adjvex;//该弧所指向的顶点的位置int value;〃该结点与邻接结点间的代价structArcNode*nextarc;〃指向下一条弧的指针}ArcNode,*node;typedef structVNode{int data;//顶点信息ArcNode*firstArc;〃指向第一条依附该顶点的弧的指针}VNode,AdjList[MAX_VERTEX_NUM];typedef structGraphAdjList vertices;int vexnum,arcnum;〃图的当前顶点数和弧数}*ALGraph;int build_adListALGraph G,int n,int a{〃建立邻接表int v,m,i,t,h;node p,q;ifn0return printfERROR;G-vexnum二n;〃图的顶点数ifa0return printfERROR;G-arcnum=a;〃图的弧数form=0;mn;m++G-vertices[m].data二m;G-vertices[m].firstArc=NULL;form=1;m=a;m++i=1;printf输入第%d条弧:〃，m;scanf〃％d,%d,%d〃，t,h,v;p二ArcNode*mallocsizeofArcNode;p-adjvex=h;p-value=v;p-nextarc二NULL;whileG-vertices[i].data!=t i++;//转到下一个结点if!G-vertices[i].firstArc〃终点G-vertices[i].firstArc=p;else{〃若当前结点有后继节点则后移forq=G-vertices[i].firstArc;q-nextarc;q=q-nextarc;q-nextarc=p;〃新开辟结点}return v;}void print GraphALGraph G〃打印邻接表ArcNode*p=ArcNode*mallocsizeofArcNode;int i;for i=1;iG-vexnum;i++{p=G-vertices[i].firstArc;printf[%d]〃，i;while pprintf，z-%d,%d〃，p-adjvex,p-value;〃第i个结点的邻接结点信息p=p-nextarc;}printf〃\n〃;void fgraphALGraph G,int k,int n{〃多段图ALGraphG,n为结点数，k为图的段数〃输入是按段的顺序给结点编号int cost

[100];int d

[100];int path

[100];int j,r,i,min,w,value;node p;cost[n]=0;forj=n-1;j=1;j—〃向前处理结点p=G-vertices[j].firstArc;min=p-value+cost[p-adjvex];〃初始化路径最小代价r=p-adjvex;value二p-value;whilep!=NULL〃「是一个的这样的结点，权值cj,r+cost[r]取最小值if p-value+cost[p-adjvex]minmin=p-value+cost[p-adjvex];//p-value=c j,rr=p-adjvex;value=p-value;p=p-nextarc;cost[j]=value+cost[r];〃当前节点的代价值d[j]二r;〃决策阶段，各结点到终点最小代价路径上前方顶点的编号path

[1]=1;path[k]=n;fori=2;i=k-1;i++〃找出最小代价路径上的结点path[i]=d[path[i-1]];printf最小成本为:％d\n,cost[l];printf〃最小成本路径为〃；forw=1;w=k;w++printf〃%d-〉〃，path[w];段上void main月主ALGraph g;主int n,a,k;刍g二ALGraphmallocsizeofALGraph;printf〃请输入多段图节点数目〃;scanf，，%d，7,n;printf〃请输入多段图边的数目〃；scanf〃%d〃，a;printf〃请输入多段图的段数:“；scanf k;printf〃输入多段图的弧的信息弧头，弧尾，权值\n〃;build adListg,n,a;printf〃多段图的邻接表为:\n;printGraphg;fgraph g,k,n;算法实验动态规划多段图实现.8*F:\Debug\exe人乙值目乙目入入弓节息川弧尾,权值）图边的入弓的段数弧多的数上多式多卷为本为反、路径为，getchO;

三、实验总结与收获通过这个实验，我了解了递归在代码中是如何具体实现的整体上，感受到了局部处理整合就是整体处理的策略，对递归思想有了更清晰的认识ocI/4B^^JAIAJAJAIAIA/1/1242J-2d-

2.2,3,4,5,

4.:1045865,-:

3.25--::-5S6-成绩评阅老师。