数据通信与通信网技术课程设计指导书.doc

数据通信与通信网技术课 程 设 计 指 导 书一、课程设计的目的本课程设计是学习数据通信与通信网技术课程必要的教学环节。由于该课程是专业必修课，需要通过实践巩固基础知识，为使学生取得最现代化的设计技能和研究方法，课程设计训练也就成为了一个重要的教学环节。通过对路由算法的设计和实现，达到进一步完善对通信网基础及应用课程学习的效果。二、课程设计的基本要求课程设计是分阶段分步完成的，各阶段的要求和安排如下：1、指导教师发放题目，学生根据题目查找有关资料和书籍，在同课题组的同学对于某些难点、关键问题可以互相讨论，共同研究。2、学生根据自己的题目和有关参考资料，独立进行构思和分析，制订整体设计方案，进行详细设计。3、书写课程设计报告，按规定时间交指导教师评审，给出课程设计综合成绩。三、课程设计的主要内容通过对最短路径算法的学习与分析，掌握常用算法的基本思想并通过开发工具进行实现。课程设计主要内容是：任选一个最短路径算法，每个人完成一个算法的程序设计、调试，实现，应提供包括下述内容的课程设计总结报告：1、任务书：说明算法的基本思想；2、程序设计及调试过程总结（需指出解决所遇到问题的途径）。参考题目：基于VC的最短路径Dijkstra算法的实现。1、增加对仿真软件的认识，学会对各种软件的操作和使用方法；2、加深理解路径算法的概念；3、初步掌握系统的设计方法，培养独立工作能力。参考程序如下：#include/ 定义 状态代码 及 数据类型#define NULL 0#define OK 1#define ERROR 0#define INFINITY 255#define MAX_VERTEX_NUM 20typedef int Status;typedef int ElemType;/ - 队列结构 -/ 节点存储结构typedef struct QNode ElemType data; struct QNode *next;QNode,*QueuePtr;/ 队列typedef struct QueuePtr front; QueuePtr rear;LinkQueue;/ 初始化队列Status InitQueue(LinkQueue &Q) Q.front=Q.rear=new QNode; if(!Q.front) return ERROR; Q.front-next=NULL; return OK;/ 入队Status EnQueue(LinkQueue &Q,ElemType e) QueuePtr p=NULL; p=new QNode; if(!p) return ERROR; p-data=e; p-next=NULL; Q.rear-next=p; Q.rear=p; return OK;/ 出队Status DeQueue(LinkQueue &Q,ElemType &e) QueuePtr p=NULL; if(Q.front=Q.rear) return ERROR; p=Q.front-next; e=p-data; Q.front-next=p-next; if(Q.rear=p) / 注意当出队后为空队的情况 Q.rear=Q.front; delete p; return OK;/ 判断是否为空队列Status EmptyQueue(LinkQueue &Q) return Q.front=Q.rear?true:false;/ 复制队列(copy Q1 to Q2)Status CopyQueue(LinkQueue &Q1,LinkQueue &Q2) int e; QueuePtr p; while(!EmptyQueue(Q2) / clean Q2 DeQueue(Q2,e); / copy one by one p=Q1.front-next; while(p) e=p-data; p=p-next; EnQueue(Q2,e); return OK;/ - 图的结构：邻接矩阵（有向网） -/ 邻接矩阵元素typedef struct ArcCell int adj; / arc value: 0, INFINITY: no link char *info; AcrCell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;/ 图的结构 typedef struct char vexsMAX_VERTEX_NUM5; / 顶点数组 AdjMatrix arcs; / 邻接矩阵 int vexnum; / 图当前的顶点数 int arcnum; / 图当前边的个数MGraph;/ 建立邻接图（key=1为有向网，key=0为无向网）Status CreateUDN(MGraph &G,int vexnum,int edgenum,char *names,char *edges,int key) int i,j,k,value; / 输入当前图的顶点数，边个数 G.vexnum=vexnum; G.arcnum=edgenum; / 各个顶点数据 for(i=0;iG.vexnum;+i) for(j=0;j4;j+) G.vexsij=*names; names+; G.vexsi4=0; / 初始化邻接矩阵（全为INFINITY） for(i=0;iMAX_VERTEX_NUM;+i) for(j=0;jMAX_VERTEX_NUM;+j) G.arcsij.adj=INFINITY; G.=NULL; / 建立邻接矩阵每条边的数值 for(k=0;kG.arcnum;+k) i=int(*edges)-48; edges+; j=int(*edges)-48; edges+; value=(int(*edges)-48)*10; edges+; value+=int(*edges)-48; edges+; G.arcsij.adj=value; if(!key) G.arcsji.adj=value; return OK;/ 打印出邻接矩阵void PrintGraph(MGraph &G) int i,j; coutn/- PrintMatrix -/nn ; for(i=0;iG.vexnum;+i) coutG.vexsi ; coutendl; for(i=0;iG.vexnum;+i) coutnnG.vexsi ; for(j=0;jG.vexnum;+j) if(G.arcsij.adj=INFINITY) cout / ; else cout G.arcsij.adj ; coutnn/- PrintMatrix -/n;/ - 求源点v0到各点的最短路径 -/void ShortestPath(MGraph &G,int v0) int DMAX_VERTEX_NUM,finalMAX_VERTEX_NUM,i,w,v=0,min; / 建立队列数组，用以依次储存最短的路径 LinkQueue QMAX_VERTEX_NUM; / 初始化数组 for(i=0;iG.vexnum;+i) InitQueue(Qi); Di=G.arcsv0i.adj; finali=false; finalv0=true; / 一个一个循环找出最短距离（共vexnum1个） for(i=1;iG.vexnum;+i) min=INFINITY; / 扫描找出非final集中最小的D for(w=0;wG.vexnum;+w) if(!finalw & Dwmin) v=w; min=Dw; finalv=true; / 更新各D数据 for(w=0;wG.vexnum;+w) if(!finalw & G.arcsvw.adj+minDw) Dw=G.arcsvw.adj+min; CopyQueue(Qv,Qw); EnQueue(Qw,v); / 打印出结果 cout/- ShortestPath -/nn; cout目的地t最短距离t详细路径nn; for(i=0;iG.vexnum;i+) if(Di!=INFINITY) cout G.vexsv0 G.vexsittDi tt; coutG.vexsv0; while(!EmptyQueue(Qi) DeQueue(Qi,v); cout G.vexsv; cout G.vexsiendl; else cout G.vexsv0 G.vexsittNo path!n; coutn/- ShortestPath -/n;void PrintCity(char *names,int vexnum) int i,j; cout列表：nn; for(i=0;ivexnum;+i) cout i-; for(j=0;j4;j+) cout*names; names+; cout ; cout; void main() MGraph G; / 图的结构数据 char *edges,*names; int vexnum,arcnum,city,kind; vexnum=6; arcnum=10; names=A1 A2 A3 A4 A5 A6; edges=0103030505071205150623082403430152085407; do PrintCity(names,vexnum); cincity; cout; do cinkind; if(kind=0 & kind =3) CreateUDN(G,vexnum,arcnum,names,edges,kind%2); switch(kind/2) case 0:ShortestPath(G,city); break; case 1:PrintGraph(G); break; cout; while(ki