N阶魔阵问题数据结构课程设计

N阶魔阵问题2011年6月14日1数据结构课程设计一、实验题目给定一奇数n，构造一个n阶魔阵。n阶魔阵是一个n阶方阵，其元素由自然数1，2，3，…，n2组成。魔阵的每行元素之和，每列元素之和以及主、副对角线之和均相等。既对于给定的奇数n以及i=1，2，3，…，n。魔阵a满足以上条件。要求：要求输出结果的格式要具有n阶方阵的形式。提示：依次将自然数填入方阵中，共填n轮，每轮填n次。第一轮的第一次，将1填入方阵的中间一行的最后一列位置。设前一次填入的位置是aij。（1）每轮中第2至第n次将数填入ai+1,j+1,若遇到下列情况之一，则填写位置按以下规则调整：①.aij是最后一列（即j=n）位置，则将下一个数填入ai+1，1；②.aij是最后一行（即i=n）位置，则将下一个数填入a1，j+1；（2）新一轮的第一次填入a1,j-1.二、实验目的一、了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；二、初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；三、提高综合运用所学的理论知识和方法独立分析和解决问题的能力；四、训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风；五、输出一个奇数N阶的具有矩阵形式魔阵。三、实验内容（一）需求分析1.定义一个整形变量order存放魔术矩阵的阶数order为一整形变量，是通过键盘来进行输入的阶数，也是进行分析的条件，可通过形参的值传递到子函数中，再对魔术矩阵按照进行排列，要求如下：n阶魔方矩阵是将自然数2,3,2,1n放置在一个nn的方阵中，同时要保证该矩阵2每行﹑每列及两条主对角线（即主对角线和副对角线）上的数值之和相等的要求。这似乎是一件比较复杂的事情，其实，求解“魔方矩阵”（奇数阶）有一个很巧妙的算法，这个算法的描述如下：（1）初始化“魔方矩阵”，即将所有元素置为0；（2）首先将1放置在第1行的中间位置。（3）将22n之间的整数按照下列规则依次放置在方阵中：如果上一个数值所放置的位置的右上方为空（该位置还没有放置数值），则当前数值被放置在一个数值的右上方；否则被放置在上一个数的正下方。很显然，“魔方矩阵”中的数据具有明显的二维排列关系，因此应该选用二维数组表示待求解的“魔方矩阵”。（4）对于给定的奇数n以及1,2,3,in，魔方矩阵满足的条件用数学表示如下：nkknknkkknknkkiikaaaa11,111定义为整型，将其返回，在主程序中打印出来。（5）显示“魔方矩阵”；2.算法流程图在主函数中定义order为整型，由键盘输入；定义整型变量row，column来描述数组插入的位置；3开始输入order初始化输入的是偶数超出取值范围row=0;column=order/2将1置于第1行中间NY4右上方空计算右上方的下标count+1count计算正下方的下标放置countYYNcount≤2NN2count输出matrix结束5（二）概要设计（1）定义的存储结构描述：首先在函数首部定义：#defineMAXSIZE31定义一个数组matrix[MAXSIZE][MAXSIZE];对n阶魔术矩阵进行存储；其中matrix[MAXSIZE][MAXSIZE]的参数类型为整型，此数组的最大值定义为31，如果超出则会发生错误，定义一个整型变量order，将order的值传到形参，在算法中对order阶的矩阵排列，使其满足下列条件：nkknknkkknknkkiikaaaa11,111因此称这样的矩阵为魔术矩阵；在算法程序中定义matrix[MAXSIZE][MAXSIZE];其中定义为整型，将其返回，在主程序中打印出来。算法分析：①．下面一段程序是用来限制输入的魔方矩阵的阶数所用：if(orderMAXSIZE){printf(\n取值超出范围：\n);printf(\n*******************************);}elseif(order%2==0){printf(\n输入有错误，请重新输入：\n);printf(\n*******************************);}②．下面一段程序是求解N阶魔方矩阵最关键的部分：首先将1放置在第1行的中间位置。将22n之间的整数按照下列规则依次放置在方阵中：如果上一个数值所放置的位置的右上方为空（该位置还没有放置数值），则当前数值被放置在一个数值的右上方；否则被放置在上一个数的正下方。row=0;/*startoffromthemiddle*/column=order/2;/*ofthefirstrow.*/6for(count=1;count=order*order;count++){matrix[row][column]=count;/*putnext#*/if(count%order==0)/*movedown?*/row++;/*YES,movedownonerow*/else{/*computenextindices*/row=(row==0)?order-1:row-1;column=(column==order-1)?0:column+1;}}printf(\n\n%d阶魔方阵如下:\n\n,order);for(row=0;roworder;row++){for(column=0;columnorder;column++)printf(%4d,matrix[row][column]);printf(\n);}（三）详细设计利用数组构造N阶魔阵，其N为奇数，并且取一定的范围。然后对该魔阵的正确性进行检验。根据魔阵的特性，需要对列、行、主对角线、副对角线进行检验，看是否相等。1、设计函数输出所要求的魔阵即构造满足nkknknkkknknkkiikaaaa11,111的矩阵：row=0;/*startoffromthemiddle*/column=order/2;/*ofthefirstrow.*/for(count=1;count=order*order;count++){7matrix[row][column]=count;/*putnext#*/if(count%order==0)/*movedown?*/row++;/*YES,movedownonerow*/else{/*computenextindices*/row=(row==0)?order-1:row-1;column=(column==order-1)?0:column+1;}}printf(\n\n%d阶魔方阵如下:\n\n,order);for(row=0;roworder;row++){for(column=0;columnorder;column++)printf(%4d,matrix[row][column]);printf(\n);}2、检查输入的数是否是奇数，如果不是则输出“输入有错误，请重新输入”。elseif(order%2==0){printf(\n输入有错误，请重新输入：\n);printf(\n*******************************);}3、检查输入的数是否超出范围，超出则输出“取值超出范围”否则继续程序。if(orderMAXSIZE){printf(\n取值超出范围：\n);printf(\n*******************************);}4、进行魔方矩阵的每一行和检验，输出每行和的值。printf(该魔方矩阵的每一行和检验:);printf(\n);8for(row=0;roworder;row++){intsum=0;for(column=0;columnorder;column++)sum+=matrix[row][column];printf(sum=%d);printf(\n);}5、进行魔方矩阵的每一列和检验，输出每列和的值。printf(该魔方矩阵的每一列和检验:);printf(\n);for(column=0;columnorder;column++){intsum=0;for(row=0;roworder;row++)sum+=matrix[row][column];printf(sum=%d);printf(\n);}6、进行魔方矩阵的主对角线和检验，输出对角线和的值。printf(该魔方矩阵的主对角线和检验:);printf(\n);sum=0;for(row=0;roworder;row++){column=row;sum+=matrix[row][column];}printf(sum=%d);7、进行魔方矩阵的副对角线和检验，输出副对角线和的值。printf(该魔方矩阵的副对角线和检验:);9printf(\n);intsum=0;for(row=0;roworder;row++){column=order-row-1;sum+=matrix[row][column];}printf(sum=%d);当所有验证和的结果相等，说明构造的矩阵就是魔阵，符合题目要求。（四）运行结果①．当输入偶数时测试结果如下：②．当输入一个大于max_NUM的数时测试结果如下：③．构造3阶魔方矩阵及对其各项要求的检验：10④．构造5阶魔方矩阵及对其各项要求的检验：（五）使用说明111．本程序的运行环境为DOS操作系统。2．进入程序后即显示用户界面。（字符型界面）3．用户按程序提示语言操作即可。4．接受输入的数据后，程序自动回输出相应结果。5．程序有最大数范围限制和奇数限制，否则不能运行出结果。四、实验体会通过本次数据结构课程设计，让我再次拾起很多C语言的知识,再次感受到了编程的魅力。课程设计过程中最大的问题应该就是编程，遇到很多不能解决的问题，在请教别人之后终于完成。拿到题目首先是读题了，在看到这个魔阵的特点之后，第一反应便是利用数组来解决。对于数组的初始化，定义一个数组的长度的不能是变量，因为在本程序中我是用一个二维数组去表示一个矩阵，在定义之后需要对数组进行初始化，这些都是C的数组知识掌握。每次利用数组都会忘记初始化，导致卡在那里半天不知道怎么编了。这也启示我对知识力求高效掌握，不能只见深林不见树木。对处理编写魔阵时出现的问题，有些自己不熟悉东西，例如，在多次运行程序过后，总是说文件错误。至于是什么原因现在都没搞清，只能重新打开一个VC再来一遍。做程序的过程中括号也给我造成了很大的困恼，因为总是因为少一个或多一个括号使得进程减慢，影响整个思路的延续。编写程序运行时的遇到问题，先看在编译时对语法错误进行纠正，如果语法无错误，但运行结果还不符合要求，则对自己的算法进行分析，看是否有什么不足之处，和没考虑到的地方，在对程序的相对应的模块进行修改，再编译调试，直到运行结果正确。数据结构是一门注重算法的学科，同时还应该将算法和实践联系起来，还对算法进行分析，尽量找到简洁的算法设计，因此数据结构中新的数据结构如栈，队列，链表，树解决了这一问题，这些可以很好的应用到实际当中去，我们并要掌握他们的运用。得益于平时上机对很多算法的练习，编程的方向感不错，知道考点，而且有了一定的纠错能力，使得整个课程设计过程比较顺利。数据结构课程设计在一定程度上给了我们一个利用所学知识的平台，让我们练习程序的编写以及探究实际问题，挑战自己的能力。经过课程设计之后对C语言和数据结构的知识有了更深的认识，理解的更到位，也有了更浓厚的兴趣。