数据结构拉丁方阵课程设计

吉林工程技术师范学院

信息工程学院《数据结构》课程设计报告题目：拉丁方阵专业：软件工程班级：R1241姓名：冮冶学号：03号指导教师：刘明时间：摘要拉丁方阵是一种nXn的方阵，方阵中恰有n种不同的元素，每种元素恰有n个，并且每种元素在一行和一列中恰好出现一次。例如下图是一个3X3的拉丁方阵：321213132如果一个拉丁方阵的第一行和第一列按照元素的先后顺序来排列，那么这称为拉丁方阵的标准型，例如下图就是一个3x3的拉丁方阵标准型，第一行和第一列都是”123”。TOC\o"1-5"\h\z233112编写一个程序读入一个方阵，判断其是否为拉丁方阵；进一步地，判断是否为标准型。输入包含多组数据。每组数据第一行为正整数n，表示方阵的大小。其后n行，每行有n个1到n之间的整数，整数之间恰有一个空格，表示方阵的内容。输入保证1^n^100输入以n=0结束，不要处理这个数据。每组数据对应于一行输出。如果输入是拉丁方阵，但不是标准型则输出1;如果输入是标准型则输出2；如果输入不是拉丁方阵则输出0。应用“数据结构与算法”课程知识建立该问题的数据结构模型；关键字：拉丁方阵，比较，数据结构与算法一、课程设计的目的二、设计方案的论证（背景、意义、技术路线）三、设计实现过程四、调试运行及结果分析五、测试及问题探讨六、课设总结与体会七、致谢八、参考文献九、附录一、课程设计的目的数据结构课程设计的目的是使同学们能够根据数据对象的特性，合理的组织数据并能综合运用数据结构与程序设计基本知识解决实际问题，培养基本的、良好的程序设计技能。明确题目要求、确定数据的逻辑结构和存储结构；完成核心算法的设计、编码与调试；准备测试数据，对软件进行测试与调试并撰写课程设计报告；，验收及答辩。通过实践操作，能熟练运用C语言实现逻辑结构、存储结构及核心算法；掌握书写程序设计说明文档的能力和工程软件设计的基本方法。二、设计方案的论证（背景、意义、技术路线）据说普鲁士的腓特列大帝曾组成一支仪仗队，仪仗队共有36名军官，来自6支部队，每支部队中，上校、中校、少校、上尉、中尉、少尉各一名。他希望这36名军官排成6x6的方阵，方阵的每一行，每一列的6名军官来自不同的部队并且军衔各不相同。令他恼火的是，无论怎么绞尽脑汁也排不成。后来，他去求教瑞士著名的大数学家欧拉。欧拉发现这是一个不可能完成的任务。来自n个部队的n种军衔的nxn名军官，如果能排成一个正方形，每一行，每一列的n名军官来自不同的部队并且军衔各不相同，那么就称这个方阵叫正交拉丁方阵。欧拉猜测在n=2，6，10，14，18，…时，正交拉丁方阵不存在。然而到了上世纪60年代，人们用计算机造出了n=10的正交拉丁方阵，推翻了欧拉的猜测。现在已经知道，除了n=2,6以外，其余的正交拉丁方阵都存在，而且有多种构造的方法。意义：熟悉运用C语言实现数据结构的运算技术路线：工具WinTC三、设计实现过程3.1概要设计3.2详细设计定义数组a[100][100]。输入方阵for(i=0;i<n;i++){for(j=0;j<n;j++)scanf("%d”,&a[i][j]);}输出方阵for(i=0;i<n;i++){printf("\n");for(j=0;j<n;j++)printf("%d",a[i][j]);}判断各行是否有相等数据for(i=0;i<n;i++){for(j=i;j<n;j++){for(k=j+1;k<n;k++){if(a[i][j]=a[i][k]){ch=0;returnch;//行数中有相等数据返回L=0}}}}returnch;//符合数组各行无相等数据返回L=1判断各列是否有相等数据for(i=0;i<n;i++){for(j=i;j<n;j++){for(k=j+1;k<n;k++){if(a[j][i]=a[k][i])//(不无法比较相邻的行列){ch=0;returnch;//列数中有相等数据返回M=0}}}}returnch;//符合数组各列无相等数据返回M=1判断有序for(i=0;i<n;i++)〃第一行有序{if(a[0][i]<a[0][i+1]){flag1=0;break;}}for(j=0;j<n;j++)〃第一列有序{if(a[j][0]<a[j+1][0]){flag2=0;break;}}判断条件若有序情况下继续判断行列是否相等if((flag1==0)&&(flag2==0)){for(i=1;i<n;i++){if(a[0][i]=a[i][0])ch=0;returnch;//各行各列均有序且行与列相等返回N=0returnch;//行与列不相等则不是标准型返回N=1}输出判断的方阵类型if(k==1&&s==1){if(m==1)printf("2");//是拉丁方阵但不是标准拉丁方阵elseprintf("1阵”);//是标准拉丁方}elseprintf("0");//不是拉丁方阵四、调试运行及结果分析IE:\C¥u¥an\bin\wv/temp.exe请输入方阵阶教：5输入矩阵的数据技个234512345124561234253115392345123451245612342531153101。：此方阵不是拉丁方阵！Pressanvkeytocontinue图4-1T"IE:\CYu¥an\binXwv/temp.exe请输入方阵阶数：3输入矩阵的数据9个1232313211232313211102：此方阵是标准拉丁方阵!Pressanykeytocontinue图4-3

图4-6

〔E:\CYu¥an\bin\wv/temp.exe□回S3请输入方阵阶数：101此数据不符合要求Press:anytocontinue图4-7[.E:\C¥u¥an\bin\wv/temp.exe□回S3清输入方阵阶数:0此数据不符合要求Pressan/keytocontinue图4-8五、测试及问题探讨我们是通过在主函数中输入方阵数据，并调用子函数运行，输出结果，来实现的。第一次运行时，出现了很多错误。在我的逐条分析下，发现很多是语法错误。例如在语句后面没有加“；”，或是在输出的部分弄错了字符的表示格式等错误。我便仔细查看，一一改正过来。开始时，我所编写的程序，不能判断当输入的数大于n的情况。编写不符合要，我在主函数中添加了一条比较语句，得以实现。在编程序之前，我不知该如何实现方阵的排列，找到了C语言的课本，然后决定用二维数组来实现，在对方阵进行判断时，由于if语句比较多，运行时发现与要求不符，便重新对if语句进行排序，嵌套等操作，最终得以实现六、课设总结与体会通过这次课设我学会了如何利用C语言数组，在C语言的环境下实现方阵的形成，比较和判断，拉丁方阵具有悠久的历史，用现代的计算机编程语言，通过数据结构进行实现。在数据结构的课堂上有关数组我们学过了很多，例如：数组的定义。有关方阵，矩阵，我们也学过了很多例如方阵，矩阵的存储等知识，在这节课程设计之前，我花费了一些时间看书上的这些内容，以便我能更好的进行课程设计。这节课程设计不仅让我们巩固数据结构了知识，还让我们对C语言编程的实现，及语法进行了很好的巩固。不仅如此，也增强了我们的编程调试的能力，让我们能熟练的来运用C语言环境的各种工具。七、致谢在这次课程设计中，我要感谢我的课程设计老师帮助我完成了这次的课程设计，在许多技术性的问题上给予我帮助，在设计过程中给了我很多的意见和建议，在调试的时候也帮助我，把一些不晚上的想法完善了。还有，我要感谢我的同学们，在最早的选题时，都是同学们帮助我，geile我很多建议。最后我要感谢我的学校，给我们提供了一个良好的课程设计环境，在这次课设中我学到了很多，得到了很多，所以我还要再次感谢这些我要感谢的人八、参考文献王昆仑，李红.数据结构与算法.北京：中国铁道出版社，2006年5月。胡学钢.数据结构与算法指导.北京：清华大学出版社，1999。胡学钢.数据结构.北京：高等教育出版社，2006。王红梅，胡明，王涛编著.数据结构（C++版）.北京：清华大学出版社，2005.7.谭浩强编著.C++面向对象程序设计.北京：清华大学出版社，2006.1.九，附录源程序：#include"stdio.h"#include"stdlib.h”intpanduan1(inta[100][100],intn)//判断各行是否有相等数(intch=1;inti,j,k;for(i=0;i<n;i++)(for(j=0;j<n;j++)(for(k=j+1;k<n;k++)(if(a[i][j]==a[i][k])(ch=0;returnch;}//彳亍数有相等k=0}}}returnch;//符合数组各行不相等返回K=1}intpanduan2(inta[100][100],intn)//判断各列是否有相等数(intch=1;inti,j,k;for(i=0;i<n;i++)for(j=0;j<n;j++){for(k=j+1;k<n;k++){if(a[j][i]=a[k][i]){ch=0;returnch;}//列数有相等s=0}}}returnch;//符合数组各列不相等返回S=1}intpanduan3(inta[100][100],intn)//判断首行首列是否相等{intch=1,flag1=1,flag2=1;inti,j;for(i=0;i<n;i++)//第一行有序if(a[0][i]<a[0][i+1]){flag1=0;break;}for(j=0;j<n;j++)//第一列有序if(a[j][0]<a[j+1][0]){flag2=0;break;}if(flag1==0&&flag2==0){for(i=1;i<n;i++){if(a[0][i]==a[i][0])//有序且行列相等m=0ch=0;returnch;}}returnch;//不相等不是标准m=1}voidmain(){intn,i,j;intk,s,m;inta[100][100];printf(-请输入方阵阶数：\n");scanf("%d”,&n);if(n<=1||n>=100){printf(”此数据不符合要求\/);}else{printf('输入矩阵的数据％d^\n",n*n);k=panduan1(a,n);for(i=0;i<n;i++){for(j=0;j<n;j++)scanf("%d”,&a[i][j]);if(a[i][j]>n){k=0;}}for(i=0