《数据通信与通信网技术》课程设计指导书高玉潼编沈阳大学信息工程学院课程编码：通信工程适用层次：本科周数：1适用专业：通信工程适用学期:第4学期撰写人：高玉潼审核人：周昕教学院长：王晖一、课程设计的目的本课程设计是学习《数据通信与通信网技术》课程必要的教学环节。
由于该课程是专业必修课，需要通过实践巩固基础知识，为使学生取得最现代化的设计技能和研究方法，课程设计训练也就成为了一个重要的教学环节。
通过对路由算法的设计和实现，达到进一步完善对该课程学习的效果。
二、课程设计的基本要求课程设计是分阶段分步完成的，各阶段的要求和安排如下：1、指导教师发放题目，学生根据题目查找有关资料和书籍，在同课题组的同学对于某些难点、关键问题可以互相讨论，共同研究。
2、学生根据自己的题目和有关参考资料，独立进行构思和分析，制订整体设计方案，进行详细设计。
3、书写课程设计报告，按规定时间交指导教师评审，给出课程设计综合成绩。
三、课程设计的主要内容通过对最短路径算法的学习与分析，掌握常用算法的基本思想并通过开发工具进行实现。
课程设计主要内容是：任选一个最短路径算法，每个人完成一个算法的程序设计、调试，实现，应提供包括下述内容的课程设计总结报告：1、任务书：说明算法的基本思想；2、程序设计及调试过程总结（需指出解决所遇到问题的途径）。
参考题目：基于VC的最短路径Dijkstra算法的实现。
1、增加对仿真软件的认识，学会对各种软件的操作和使用方法；2、加深理解路径算法的概念；3、初步掌握系统的设计方法，培养独立工作能力。
参考程序如下：#include<iostream.h>// 定义状态代码及数据类型#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 Q2DeQueue(Q2,e);} // copy one by onep=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 linkchar *info;}AcrCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];// 图的结构typedef struct{char vexs[MAX_VERTEX_NUM][5]; // 顶点数组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;i<G.vexnum;++i){for(j=0;j<4;j++){G.vexs[i][j]=*names;names++;}G.vexs[i][4]='\0';}// 初始化邻接矩阵（全为INFINITY）for(i=0;i<MAX_VERTEX_NUM;++i){for(j=0;j<MAX_VERTEX_NUM;++j){G.arcs[i][j].adj=INFINITY;G.arcs[i][j].info=NULL;}}// 建立邻接矩阵每条边的数值for(k=0;k<G.arcnum;++k){i=int(*edges)-48;edges++;j=int(*edges)-48;edges++;value=(int(*edges)-48)*10;edges++;value+=int(*edges)-48;edges++;G.arcs[i][j].adj=value;if(!key){G.arcs[j][i].adj=value;}}return OK;}// 打印出邻接矩阵void PrintGraph(MGraph &G){int i,j;cout<<"\n//--------------- PrintMatrix -----------------//\n\n ";for(i=0;i<G.vexnum;++i){cout<<G.vexs[i]<<" ";}cout<<endl;for(i=0;i<G.vexnum;++i){cout<<"\n\n"<<G.vexs[i]<<" ";for(j=0;j<G.vexnum;++j){if(G.arcs[i][j].adj==INFINITY)cout<<" / ";elsecout<<" "<<G.arcs[i][j].adj<<" ";}}cout<<"\n\n//--------------- PrintMatrix -----------------//\n";}// ---------------------- 求源点v0到各点的最短路径--------------------------//void ShortestPath(MGraph &G,int v0){int D[MAX_VERTEX_NUM],final[MAX_VERTEX_NUM],i,w,v=0,min;// 建立队列数组，用以依次储存最短的路径LinkQueue Q[MAX_VERTEX_NUM];// 初始化数组for(i=0;i<G.vexnum;++i){InitQueue(Q[i]);D[i]=G.arcs[v0][i].adj;final[i]=false;}final[v0]=true;// 一个一个循环找出最短距离（共vexnum－1个）for(i=1;i<G.vexnum;++i){min=INFINITY;// 扫描找出非final集中最小的D[]for(w=0;w<G.vexnum;++w){if(!final[w] && D[w]<min){v=w;min=D[w];}}final[v]=true;// 更新各D[]数据for(w=0;w<G.vexnum;++w){if(!final[w] && G.arcs[v][w].adj+min<D[w]){D[w]=G.arcs[v][w].adj+min;CopyQueue(Q[v],Q[w]);EnQueue(Q[w],v);}}}// 打印出结果cout<<"//--------------- ShortestPath -----------------//\n\n";cout<<" 出发地->目的地\t最短距离\t详细路径\n\n";for(i=0;i<G.vexnum;i++){if(D[i]!=INFINITY){cout<<" "<<G.vexs[v0]<<" -> "<<G.vexs[i]<<"\t\t"<<D[i]<<" \t\t"; cout<<G.vexs[v0];while(!EmptyQueue(Q[i])){DeQueue(Q[i],v);cout<<" -> "<<G.vexs[v];}cout<<" -> "<<G.vexs[i]<<endl;}else{cout<<" "<<G.vexs[v0]<<" -> "<<G.vexs[i]<<"\t\tNo path!\n";}}cout<<"\n//--------------- ShortestPath -----------------//\n";}void PrintCity(char *names,int vexnum){int i,j;cout<<"列表：\n\n";for(i=0;i<vexnum;++i){cout<<" "<<i<<"-";for(j=0;j<4;j++){cout<<*names;names++;}cout<<" ";}cout<<"\n请选择出发地点 >";}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);cin>>city;cout<<"\n\n操作：\n0－无向图列表 1－有向图列表\n2－无向图矩阵 3－有向图矩阵\n4－选择地点 5－退出\n\n请选择操作 >";do{cin>>kind;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<<"\n\n操作：\n0－无向图列表 1－有向图列表\n2－无向图矩阵 3－有向图矩阵\n4－选择地点 5－退出\n\n请选择操作 >";}while(kind<4);}while(kind<5);}四、主要技术关键的分析、解决、方案比较1、按照实验原理和实验步骤完成设计过程。
