数据结构课程设计.doc

山东建筑大学课 程 设 计 成 果 报 告题 目： 1. 用数组实现两个矩阵的相乘运算 2. 迷宫问题课 程： 数据结构a课程设计院 （部）： 管理工程学院专 业： 信息管理与信息系统班 级： 信管122学生姓名：学 号：指导教师： 完成日期： 2014 年 12 月 24 日课程设计报告一、 课程设计概述3二、 课程设计题目一3详细设计3调试分析4三、 课程设计题目二5问题描述5需求分析5概要设计5存储结构5流程图6详细设计6调试分析11四、参考文献：13课程设计报告1、 课程设计概述本次数据结构课程设计共完成两个题：用数组实现两个矩阵的相乘运算、哈夫曼编/译码器。使用语言：c语言编译环境：vc6.02、 课程设计题目一用数组实现两个矩阵的相乘运算详细设计#include int r66;/存放相乘后的矩阵void mult(int a66,int b66)/实现两个矩阵相乘int i,j;for(i=0;i6;i+)for(j=0;j6;j+)rij=aij*bij;/矩阵的行列等于两个相乘矩阵对应的行列相乘void main()/主函数int i,j;int num166,num266;printf(请输入第一个矩阵的值：n);for(i=0;i6;i+)for(j=0;j6;j+)scanf(%d,&num1ij);/读入第一个矩阵相应的值printf(请输入第二个矩阵的值：n);for(i=0;i6;i+)for(j=0;j6;j+)scanf(%d,&num2ij);/读入第一个矩阵相应的值mult(num1,num2);/调用mult函数printf(n两个矩阵相乘后的结果为：n); for(i=0;i6;i+)for(j=0;j6;j+)printf(%4d,rij);/输出相乘后的矩阵printf(n);调试分析本程序主要的操作对象是数组，使用的存储结构是二维数组。利用循环结构完成数据的输入和计算。问题：现象：无法输入矩阵中的数字。原因：原题目中给出的代码中控制循环的变量初始值赋值错误，应该从0开始赋值。运行结果及分析运行结果正确。修改后，矩阵可以正确输入，计算过程也正确，所以运行结果正确。3、 课程设计题目二迷宫问题问题描述以一个m*n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。需求分析（1） 实现一个以链表作存储结构的栈类型，然后编写一个求解迷宫的非递归程序。求得的通路以三元组（i,j,d）的形式输出，其中：（i,j）指示迷宫中的一个坐标，d表示走到下一坐标的方向。（2） 编写递归形式的算法，求得迷宫中所有可能的通路；概要设计/初始化栈void initstack(stack *p)/入栈void push(stack *p,int x,int y,int d)/出栈并读出上一步的坐标void pop(stack *p,int read2,int d)/迷宫的初始化void initmaze(int maze1110)/输出迷宫void print(int maze1110)/寻找路径int ways(stack *p,int maze1110,int rkx,int rky,int ckx,int cky,int d)/显示菜单void menu()/主函数int main() 存储结构typedef structint posxlength;int posylength;int top;int base;stack;流程图详细设计#include #include #include #define length 50#define d directionint n=1;int step=0;typedef struct/进栈坐标int posxlength;int posylength;int top;int base;stack;/初始化栈void initstack(stack *p)p-top=p-base=0;/入栈void push(stack *p,int x,int y,int d)step+;d=0;n=n+1;p-top=p-top+1;p-posxn=x;p-posyn=y;/出栈并读出上一步的坐标void pop(stack *p,int read2,int d)step+;d=0;n=n-1;p-top=p-top-1;read0=p-posxn;read1=p-posyn;/迷宫的初始化void initmaze(int maze1110)int i;for(i=0;i10;i+)maze0i=2;/用2表示墙maze10i=2;for(i=1;i10;i+)mazei0=2;mazei9=2;maze11=0;maze12=0;maze13=1;maze14=0;maze15=0;maze16=0;maze17=1;maze18=0;maze21=0;maze22=0;maze23=1;maze24=0;maze25=0;maze26=0;maze27=1;maze28=0;maze31=0;maze32=0;maze33=0;maze34=0;maze35=1;maze36=1;maze37=0;maze38=1;maze41=0;maze42=1;maze43=1;maze44=1;maze45=0;maze46=0;maze47=1;maze48=0;maze51=0;maze52=0;maze53=0;maze54=1;maze55=0;maze56=0;maze57=0;maze58=0;maze61=0;maze62=1;maze63=0;maze64=0;maze65=0;maze66=1;maze67=0;maze68=1;maze71=0;maze72=1;maze73=1;maze74=1;maze75=1;maze76=0;maze77=0;maze78=1;maze81=1;maze82=1;maze83=0;maze84=0;maze85=0;maze86=1;maze87=0;maze88=1;maze91=1;maze92=1;maze93=0;maze94=0;maze95=0;maze96=0;maze97=0;maze98=0;/输出迷宫void print(int maze1110)int m,n;printf(迷宫中：0表示通路，1表示障碍，2代表墙，即障碍n);printf( 1 2 3 4 5 6 7 8n);for(m=0;m11;m+)for(n=0;ntop=p-base)printf(没有通路！n);return 0;ways(p,maze,x,y,ckx,cky,d);return 1;/显示菜单void menu()printf(-n);printf(-菜单-n);printf(-1.进入迷宫-n);printf(-2.退出迷宫-n);printf(-n);printf(请输入您的选择：);/主函数int main()stack *p;stack s;p=&s;int maze1110;int m11,m21,a;int rkx,rky,d=0;int ckx,cky,sum=0;initmaze(maze);menu();scanf(%d,&a);if(a=1)print(maze);printf(n);step=0;printf(请输入入口坐标：);scanf(%d,&m10);scanf(%d,&m11);rkx=m10;rky=m11;printf(请输入出口坐标：);scanf(%d,&m20);scanf(%d,&m21);ckx=m20;cky=m21;if(m1010|m119|m219|m2010|m100|m110|m200|m210)printf(输入的入口或出口坐标有误！n);elseprintf(n);printf(说明：(x,y,z)中x,y代表坐标点，z代表上一个坐标点到达这个坐标所走的方向，0为初始值，1234分别代表右下左上。n);printf(n);printf(查找路径的具体步骤：n);initstack(p);push(p,rkx,rky,d);ways(p,maze,rkx,rky,ckx,cky,d);return main();elseprintf(退出!n);调试分析计算机解迷宫通常用的是“穷举求解”方法，即从入口出发，顺着某一个方向进行探索，若能走通，则继续往前进；否则沿着原路退回，换一个方向继续探索，直至出口位置，求得一条通路。假如所有可能的通路都探索到而未能到达出口，则所设定的迷宫没有通路。问题一：现象：当沿着一个方向前进的时候，遇到边界为0时无法继续原因：遇到0时，可以前进但是没有路径可