N阶魔方课程设计报告.doc

经济管理学院本科课程设计论文数据结构课程设计学 号： 姓 名： 班 级： 专 业： 信息管理与信息系统 系 别: 管理系 指导教师： 2011 年 1 月 14日 吉 林目 录第1章 引言概述数据结构是一门理论性强、思维抽象、难度较大的课程，是基础课和专业课之间的桥梁。该课程的先行课程是计算机基础、程序设计语言、离散数学等，后续课程有操作系统、编译原理、数据库原理、软件工程等。 通过本门课程的学习，我们应该能透彻地理解各种数据对象的特点，学会数据的组织方法和实现方法，并进一步培养良好的程序设计能力和解决实际问题的能力，而且该课程的研究方法对我们学生在校和离校后的学习和工作，也有着重要的意义。数据结构是计算机科学与技术专业的一门核心专业基础课程，在该专业的课程体系中起着承上启下的作用，学好数据结构对于提高理论认知水平和实践能力有着极为重要的作用。学习数据结构的最终目的是为了获得求解问题的能力。对于现实世界中的问题，应该能从中抽象出一个适当的数学模型，该数学模型在计算机内部用相应的数据结构来表示，然后设计一个解此数学模型的算法，再进行编程调试，最后获得问题的解答。进行课程设计是为了加强编程能力的培养，鼓励我们在学习完理论知识之后多动手同时发挥我们自主学习的能力。相信通过数据结构课程实践，无论是理论知识，还是实践动手能力，我们都会有不同程度上的提高。第2章 需求分析2.1问题描述2.1.1语言描述：给定一奇数n，构造一个n阶魔阵。n阶魔阵是一个n阶方阵，其元素由自然数1，2，3，n2组成。魔阵的每一行元素之和，每列元素之和以及主、副对角线元素之和均相等。即对于给定的奇数n以及i=1,2,3,n，魔阵a满足条件：要求输出结果的格式要具有n阶方阵的形式。2.1.2算法概述:依次将自然数填入方阵中，共填n轮，每轮填n次。第一轮的第一次，将1填如入方阵的中间一行的最后一列位置。设前一次填入的位置是，每轮中第2至第n次将数填入，若遇到下列两种情况之一，则填写位置按以下规则调整。l 是最后一列（即j=n）位置，则将下一个数填入；l 是最后一行（即i=n）位置，则将下一个数填入；新一轮的第一次填入。2.1.3举例说明：当n=3时，得到3*3魔阵：438951276具体程序实行过程如下：1图1-1 在中间行最后一列的位置上插入第一个数据1；12图1-2 在数据1的右下角位置上插入元素2（即i+1）；31 2图1-3 检查2的右下方为空，即将3插入；4312 图1-4 3的右下方有数据1，故将4插入3的左方；435 12图1-5 4的右下方有空位置，插入5；435126图1-6 将6插入；4351276图1-7 将7插入；43851276图1-8 将8插入；438951276v图1-9将9插入；2.2 基本要求要求输出结果的格式要具有n阶魔阵的形式。给定一奇数n，构造一个n阶魔阵。n阶魔阵是一个n阶方阵，其元素由自然数1，2，3，n2组成。魔阵的每一行元素之和，每列元素之和以及主、副对角线元素之和均相等。遇到不合法数据时能有相应的提示并加以处理，同时保证不会出现死循环。提供连续实现的功能。2.3测试数据第一组：1,n; 第二组：2; 第三组：3,y; 第四组：3,a; 第五组：1，3; 第3章 概要设计3.1 数据结构 此课程设计采用一维数组来存储二维矩阵。利用指针和数组之间相互应用，表达矩阵。所用一维数组来存储二维矩阵的方法能够使矩阵更容易操作，并可在开辟的连续存储空间中能够有效的存储矩阵。则上例n=3在一维数组中的存储为如下图： 0 1 2 3 4 5 6 7 8 438951276图3-1 n=3时在一维数组中的存储图具体的表示运行方法为以下程序： int *p=new intn*n;int i; for(i=0;in*n;i+) pi=0; i=n/2; int j=n-1;int k=1; pi*n+j=k; while(kn*n) if(!p(i+1)%n)*n+(j+1)%n) p(i+1)%n)*n+(j+1)%n)=k+1; i+; j+; else p(i%n)*n+(j-1)%n)=k+1; j-; k+; 为了保证算法的健壮性，在程序的设计当中，加入了一些模块。while(1)cout*n阶魔阵*endl;cout请输入一个奇数nnn,n=ConvertStringToInt(nn),n%2=0|n=0|IsContainInString(nn,.)if(IsContainInString(nn,.)cout请输入一个整数！endl;else if(n%2=0) cout请不要输入偶数！endl; else if(n=0) cout请输入一个大于0的数endl; 设计模块可进行连续计算，程序如下：string re;cout继续？(y/n)re,!IsContainInString(re,y)& !IsContainInString(re,n)cout选择无效，请重新选择！endl;if(IsContainInString(re,n)cout谢谢使用，再见！endl;break;如遇到特殊情况，可以用dos命令对程序进行操作,具体程序如下：system(pause); return 0; 当遇到输入错误时，如，输入的为浮点型数据，则用一下模块进行处理：int ConvertStringToInt(string re) int n=re.length(); int i,t=0; for(i=0;in;i+) if(rei9) return 0; t=t*10+rei-48; return t; Int ConertStringToInt(string re)的流程图如下：开始n =re.length()t=0i =0N结束return ti nYYrei9return 0Nt =t*10+rei-48i=i+1图3-1 ConertStringToInt()函数流程图bool IsContainInString(string &a,char b)的流程图如下：开始n=a.length()i=0Nin结束return falseYNai=bYreturn truei =i+1图3-2 IsContainInString()函数流程图第4章 详细设计#include #include #include using namespace std;int ConvertStringToInt(string);bool IsContainInString(string &,char);int main()while(1)cout*n阶魔阵*endl;cout请输入一个奇数nnn,n=ConvertStringToInt(nn),n%2=0|n=0| IsContainInString(nn,.)if(IsContainInString(nn,.) cout请输入一个整数！endl; else if(n%2=0) cout请不要输入偶数！end else if(n=0) cout请输入一个大于0的数endl; int *p=new intn*n;int i;for(i=0;in*n;i+) pi=0; /将数组全部清零 i=n/2; /将初始坐标定为中间一行最后一页 int j=n-1;int k=1; /第一个被填的数设为1 pi*n+j=k; /填第一个数 while(kn*n) /需要循环n*n-1次 if(!p(i+1)%n)*n+(j+1)%n) /判断当前坐标的右下方是否有数 p(i+1)%n)*n+(j+1)%n)=k+1; /将右下方数填为k+1 i+; /当前坐标移向右下方 j+;else /右下方有数 p(i%n)*n+(j-1)%n)=k+1; /将左方数填为k+1 j-; /当前坐标移向左方 k+; /被填数自增 for(i=0;in;i+) /填数完毕，将矩阵输出 for(j=0;jn;j+)coutsetw(4)pi*n+j; /格式控制 coutendl;string re;cout继续？(y/n)re,!IsContainInString(re,y) & !IsContainInString(re,n) /如果既没有输入Y，也没有输入N，则认定/非法输入，重新输入直到输入合法为止 cout选择无效，请重新选择！endl;if(IsContainInString(re,n) /如果输入N，则退出 cout谢谢使用，再见！endl;break;system(pause); /外部DOS命令pause，用于暂停以监测 /结果return 0;int ConvertStringToInt(string re) /将字符串转换成整型数的函数，若 /字符串中部全为字符，则返回0int n=re.length();int i,t=0;for(i=0;in;i+)if(rei9)return 0;t=t*10+rei-48;return t;bool IsContainInString(string &a,char b) /判断字符串中是否包 /含指定字符 int n=a.length();int i;for(i=0;in;i+)if(ai=b)return true;return false;第5章 调试分析5.1输入界面（1）:图5-1 输入1，再输入n5.2输入界面（2）:图5-2 输入25.3输入界面（3）:图5-3 输入3，再输入y5.4输入界面（4）:图5-4 输入3，再输入a5.5输入界面（5）:图5-5 输入1.3为了使程序健壮行良好，我进行了多次调试，力求尽列出所有的可能数据，并最程序进行修改，使之成为一个优秀的程序。本程序是关于二维数组的，时间复杂度为O(n2 )。 第6章 课设总结通过此次课程设计，我深化了对数据结构的基本概念、理论和方法的理解，把所学的理论知识用于处理实际问题。这种学以致用的感觉非常好，让自己真正的掌握了所学的知识，并将其利用在实际问题中。还有就是C+的面向对象的程序设计理念，对程序设计是一个好的启发。其中，在程序的调试中遇到了一些问题，这让我重新审视到了做好一个程序需要具备哪些能力。实践能给人以成就之感，我是以着“态度决定一切”的心态对待此次数据结构课程设计的，于是偶然又必然地收获了诸多，概而言之，大约以下几点：1.温故而知新。课程设计发端之始，对知识系统全面地进行了梳理，遇到难处先是自己思考查资料，再向同学请教，掌握了基本理论知识，而且对理论知识进行实践应用，使得理解更加深刻，学会了如何思考的思维方式。2实践出真知。时至今日，课程设计基本告成，切身领悟有了思路还需要用实践进行考验，才明晓实践出真知。如在进行算法分析时要深刻地从正确性、稳健性、可读性、时间复杂度等方面进行考虑，在一个算法中，进行简单操作的次数越少，其运行时间也就相对的越短；次数越多，其运行时间也就相对的越长。同样很多时候时间的长短与程序的难易程度（实现的所要付出的代价）呈反比。通过这次课设使我深刻理解了“不为则不知，无为则无知，实践出真知”这句名言。 3.创新求发展。“创新”目前已经提升到国家发展战略地位，足见“创新”的举足轻重。因此，我们要从小处着手，顺应时代发展潮流，在课程设计中不忘在小处创新，未必是创新技术，但凡创新思维亦可，未必成功，只要实现创新思维培育和锻炼即可。4.过而能改，善莫大焉。至善至美，是人类永恒的追求。但是，不从忘却“金无足赤，人无完人”，我们换种思维方式，去恶亦是至善，改错亦为至美。在课程设计过程中，我们不断发现错误，不断改正，不断领悟，不断获取。最终的检测调试环节，本身就是在践行“过而能改，善莫