实验二电路布线问题

《实验二电路布线问题》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、实验二电路布线问题班级:计算机1405组别：4姓名：刘诚阳学号:201437121.问题定义及需求分析1・1课题目的和任务问题描述：印刷电路板将布线区域划分为nXn个方格阵列。在布线时，电路只能沿直线或直角布线。为避免线路相交，已布线的方格要做封锁标记。设起始位置为终止位置为b,求解电路布线问题。实验要求：设计印刷电路板的布线模拟程序。1）采用栈或队列等数据结构。2）采用穷举法的回溯搜索，求3到b可能的布线线路。3）推荐采用层次优先搜索，求3到b最优的布线线路。1・2数据形式输入数据形式：通过生成随机数的函数随机生成一个

2、矩阵。输入值的范围：生成的矩阵中的数值为int型，为0或者1,其中0表示死路，1表示通路。输出数据形式：输出到显示器。1・3程序功能随机给定一个线路分布矩阵，利用穷举法，通过栈的应用，求出从a到b的可能布线线路；采用层次优先搜索，通过队列的应用，求岀a到b的最优布线线路。1・4测试数据测试数据为随机生成的矩阵。2.概要设计2.1抽象数据类型需要定义一个位置类型的数据，里面包含int型的x和y坐标，用来记录位置信息；再定义一个SWire的通道块数据类型，里面包含该通道块的位置数据，在路径上的序号和方向信息；另外述需要构建栈

3、和队列的基本结构类型。2.2主程序流程及各模块之间的调用关系3.详细设计2.1存储结构实现typedefstruct{//位置intx;inty;}Position;typedefstruct{//移动标记intord;Positionseat;intdi;}SWire;typedefstruct{//栈SWire*base;SWire*top;intstacksize;}Stack;typedefstructQNode{〃队歹!JPositiondata;structQNode*next;JQNode/QP;typed

4、efstruct{QPfron;QPrear;JLinkQ;1.2负责模块的伪码算法(1)intWirePath(int**Board,Positionstart,Positionfinish){//寻找路径算法//若有从电路板的入I」start到出口end的通道，则求得一条存放在栈中//(从栈底到栈顶)InitStack(S);curpos=start;//设定当前位置为入口位置curstep二1;//探索第一步do{辻(Pass(S,curpos)){//当前位置可通过，即是未曾走到的通道块Footprint(cur

5、pos);//留下足迹e=(curstep,curpos,1);Push(S,e);〃加入路径if(curpos二二finish){//到达出口(终点)PrintStack(S);〃输岀路径Printf(电路板的搜寻图)}return1;//返冋}NcxtPos(curpos,1);//下一位置是当而位置的东邻curstep++;//探索-卜-一步}else{//当前位置不能通过Pop(S,e);if(S.top!=S.base){//栈空while(e・di==5&&S.top!=S・base){MarkPrint(e

6、.seat);Pop(S,e);//留下不能通过的标记，并退冋一步}}辻(e.di<5){e.di++;Push(S,e);//换下一个方向探索NextPos(e.seat,e.di);〃设定当前位置是该新方向//上的相邻块curpos.x=e.seat,x;curpos.y二c.scat,y;}}}while(S.base!二S.top);printf(没有通路)；printf(电路板的搜寻图)；return0;}(2)intFindShortWay(int**Board,Positionstart,Positionf

7、inish){〃搜寻最短布线路径算法if(finish==start){//到达终点,结束MShortPath=0;return1;}curpos二start;//标记当前位置if(Board[start,x][start.y]==0){没有通路!return0;}Board[start,x][start.y]=2;//有通路,则令其值为2while仃){//将笫一个通道块赋值2,并将其相邻通道块从右开始，按顺时〃针依次入队列，当队列不空时，出队列一个通道块，对其相邻通道块做相〃同操作，直至所有的未标记通路通道块都被标记

8、后为止。for(i=l;i〈5;i++){//对其相邻通道块赋值neighbour二curpos;NextPos(neighbour,i);if(Board[neighbour.x][neighbour,y]二二1

9、

10、Board[neighbour.x][neighbour,y]~-l

11、

12、Board[neighbou