數(shù)據(jù)結(jié)構(gòu)拉丁方陣課程設(shè)計(jì)

1、吉林工程技術(shù)師范學(xué)院信息工程學(xué)院 數(shù)據(jù)結(jié)構(gòu) 課程設(shè)計(jì)報(bào)告題 目： 拉丁方陣 專 業(yè)： 軟件工程 班 級(jí)： R1241 姓 名： 冮冶 學(xué) 號(hào)： 03號(hào) 指導(dǎo)教師： 劉明 時(shí) 間： 摘 要拉丁方陣是一種n×n的方陣，方陣中恰有n種不同的元素，每種元素恰有n個(gè)，并且每種元素在一行和一列中恰好出現(xiàn)一次。例如下圖是一個(gè)3×3的拉丁方陣：3 2 12 1 31 3 2如果一個(gè)拉丁方陣的第一行和第一列按照元素的先后順序來排列，那么這稱為拉丁方陣的標(biāo)準(zhǔn)型，例如下圖就是一個(gè)3x3的拉丁方陣標(biāo)準(zhǔn)型，第一行和第一列都是”1 2 3”。1 2 32 3 13 1 2編寫一個(gè)程序讀入一個(gè)方陣，判斷

2、其是否為拉丁方陣；進(jìn)一步地，判斷是否為標(biāo)準(zhǔn)型。（1）輸入包含多組數(shù)據(jù)。每組數(shù)據(jù)第一行為正整數(shù)n，表示方陣的大小。其后n行，每行有n個(gè)1到n之間的整數(shù)，整數(shù)之間恰有一個(gè)空格，表示方陣的內(nèi)容。輸入保證1n100輸入以n=0結(jié)束，不要處理這個(gè)數(shù)據(jù)。（2）每組數(shù)據(jù)對(duì)應(yīng)于一行輸出。如果輸入是拉丁方陣，但不是標(biāo)準(zhǔn)型則輸出1；如果輸入是標(biāo)準(zhǔn)型則輸出2；如果輸入不是拉丁方陣則輸出0。（3）應(yīng)用“數(shù)據(jù)結(jié)構(gòu)與算法”課程知識(shí)建立該問題的數(shù)據(jù)結(jié)構(gòu)模型；關(guān)鍵字：拉丁方陣 ，比較，數(shù)據(jù)結(jié)構(gòu)與算法22目 錄一、課程設(shè)計(jì)的目的 二、設(shè)計(jì)方案的論證（背景、意義、技術(shù)路線） 三、設(shè)計(jì)實(shí)現(xiàn)過程四、調(diào)試運(yùn)行及結(jié)果分析 五、測(cè)試及問題

3、探討 六、課設(shè)總結(jié)與體會(huì) .七、致謝八、參考文獻(xiàn) 九、附錄 一、 課程設(shè)計(jì)的目的數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)的目的是使同學(xué)們能夠根據(jù)數(shù)據(jù)對(duì)象的特性，合理的組織數(shù)據(jù)并能綜合運(yùn)用數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計(jì)基本知識(shí)解決實(shí)際問題，培養(yǎng)基本的、良好的程序設(shè)計(jì)技能。明確題目要求、確定數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)；完成核心算法的設(shè)計(jì)、編碼與調(diào)試；準(zhǔn)備測(cè)試數(shù)據(jù)，對(duì)軟件進(jìn)行測(cè)試與調(diào)試并撰寫課程設(shè)計(jì)報(bào)告；，驗(yàn)收及答辯。通過實(shí)踐操作，能熟練運(yùn)用C語言實(shí)現(xiàn)邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)及核心算法；掌握書寫程序設(shè)計(jì)說明文檔的能力和工程軟件設(shè)計(jì)的基本方法。二、 設(shè)計(jì)方案的論證（背景、意義、技術(shù)路線）據(jù)說普魯士的腓特列大帝曾組成一支儀仗隊(duì)，儀仗隊(duì)共有36名軍

4、官，來自6支部隊(duì)，每支部隊(duì)中，上校、中校、少校、上尉、中尉、少尉各一名。他希望這36名軍官排成6×6的方陣，方陣的每一行，每一列的6名軍官來自不同的部隊(duì)并且軍銜各不相同。令他惱火的是，無論怎么絞盡腦汁也排不成。后來，他去求教瑞士著名的大數(shù)學(xué)家歐拉。歐拉發(fā)現(xiàn)這是一個(gè)不可能完成的任務(wù)。來自n個(gè)部隊(duì)的n種軍銜的n×n名軍官，如果能排成一個(gè)正方形，每一行，每一列的n名軍官來自不同的部隊(duì)并且軍銜各不相同，那么就稱這個(gè)方陣叫正交拉丁方陣。歐拉猜測(cè)在n=2，6，10，14，18，時(shí)，正交拉丁方陣不存在。然而到了上世紀(jì)60年代，人們用計(jì)算機(jī)造出了n=10的正交拉丁方陣，推翻了歐拉的猜測(cè)?，F(xiàn)

5、在已經(jīng)知道，除了n=2，6以外，其余的正交拉丁方陣都存在，而且有多種構(gòu)造的方法。意義：熟悉運(yùn)用C語言實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)的運(yùn)算技術(shù)路線：工具WinTC三、 設(shè)計(jì)實(shí)現(xiàn)過程3.1 概要設(shè)計(jì)開始判斷階數(shù)是否超出范圍輸出方陣結(jié)束輸入方陣階數(shù)否是輸入方陣的數(shù)字圖3.1-1開始判斷第一行，列判斷每行數(shù)據(jù)方陣判斷每列數(shù)據(jù)輸出結(jié)束圖3.1-23.2 詳細(xì)設(shè)計(jì)1）定義數(shù)組a100100。2）輸入方陣for (i=0;i<n;i+) for(j=0;j<n;j+) scanf("%d",&aij); 輸出方陣for(i=0;i<n;i+) printf("n&quo

6、t;); for(j=0;j<n;j+) printf("%d",aij);3）判斷各行是否有相等數(shù)據(jù)for (i=0;i<n;i+) for (j=i;j<n;j+) for (k=j+1;k<n;k+) if(aij=aik) ch=0; return ch;/行數(shù)中有相等數(shù)據(jù)返回L=0 return ch;/符合數(shù)組各行無相等數(shù)據(jù)返回L=14）判斷各列是否有相等數(shù)據(jù)for(i=0;i<n;i+)for(j=i;j<n;j+)for(k=j+1;k<n;k+)if(aji=aki)/（不無法比較相鄰的行列）ch=0;return

7、 ch;/列數(shù)中有相等數(shù)據(jù)返回M=0 return ch;/符合數(shù)組各列無相等數(shù)據(jù)返回M=15）判斷有序for(i=0;i<n;i+) /第一行有序 if(a0i<a0i+1) flag1=0; break;for(j=0;j<n;j+) /第一列有序 if(aj0<aj+10) flag2=0;break; 6）判斷條件若有序情況下繼續(xù)判斷行列是否相等if(flag1=0)&&(flag2=0) for (i=1;i<n;i+) if(a0i=ai0) ch=0; return ch;/各行各列均有序且行與列相等返回N=0 return ch;/

8、行與列不相等則不是標(biāo)準(zhǔn)型返回N=17）輸出判斷的方陣類型if(k=1&&s=1) if(m=1) printf("2 ");/是拉丁方陣但不是標(biāo)準(zhǔn)拉丁方陣 else printf("1陣");/是標(biāo)準(zhǔn)拉丁方 else printf("0 ");/不是拉丁方陣四、 調(diào)試運(yùn)行及結(jié)果分析圖4-1圖4-2圖4-3圖4-4圖4-5圖4-6圖4-7圖4-8五、 測(cè)試及問題探討我們是通過在主函數(shù)中輸入方陣數(shù)據(jù)，并調(diào)用子函數(shù)運(yùn)行，輸出結(jié)果，來實(shí)現(xiàn)的。第一次運(yùn)行時(shí)，出現(xiàn)了很多錯(cuò)誤。在我的逐條分析下，發(fā)現(xiàn)很多是語法錯(cuò)誤。例如在語句后面沒有

9、加“；”，或是在輸出的部分弄錯(cuò)了字符的表示格式等錯(cuò)誤。我便仔細(xì)查看，一一改正過來。開始時(shí)，我所編寫的程序，不能判斷當(dāng)輸入的數(shù)大于n的情況。編寫不符合要，我在主函數(shù)中添加了一條比較語句，得以實(shí)現(xiàn)。在編程序之前，我不知該如何實(shí)現(xiàn)方陣的排列，找到了C語言的課本，然后決定用二維數(shù)組來實(shí)現(xiàn)，在對(duì)方陣進(jìn)行判斷時(shí)，由于if語句比較多，運(yùn)行時(shí)發(fā)現(xiàn)與要求不符，便重新對(duì)if語句進(jìn)行排序，嵌套等操作，最終得以實(shí)現(xiàn)六、 課設(shè)總結(jié)與體會(huì)通過這次課設(shè)我學(xué)會(huì)了如何利用C語言數(shù)組，在C語言的環(huán)境下實(shí)現(xiàn)方陣的形成，比較和判斷，拉丁方陣具有悠久的歷史，用現(xiàn)代的計(jì)算機(jī)編程語言，通過數(shù)據(jù)結(jié)構(gòu)進(jìn)行實(shí)現(xiàn)。在數(shù)據(jù)結(jié)構(gòu)的課堂上有關(guān)數(shù)組我們學(xué)

10、過了很多，例如：數(shù)組的定義。有關(guān)方陣，矩陣，我們也學(xué)過了很多例如方陣，矩陣的存儲(chǔ)等知識(shí)，在這節(jié)課程設(shè)計(jì)之前，我花費(fèi)了一些時(shí)間看書上的這些內(nèi)容，以便我能更好的進(jìn)行課程設(shè)計(jì)。這節(jié)課程設(shè)計(jì)不僅讓我們鞏固數(shù)據(jù)結(jié)構(gòu)了知識(shí)，還讓我們對(duì)C語言編程的實(shí)現(xiàn)，及語法進(jìn)行了很好的鞏固。不僅如此，也增強(qiáng)了我們的編程調(diào)試的能力，讓我們能熟練的來運(yùn)用C語言環(huán)境的各種工具。七、致謝在這次課程設(shè)計(jì)中，我要感謝我的課程設(shè)計(jì)老師幫助我完成了這次的課程設(shè)計(jì)，在許多技術(shù)性的問題上給予我?guī)椭?，在設(shè)計(jì)過程中給了我很多的意見和建議，在調(diào)試的時(shí)候也幫助我，把一些不晚上的想法完善了。還有，我要感謝我的同學(xué)們，在最早的選題時(shí)，都是同學(xué)們幫助我，

11、geile我很多建議。最后我要感謝我的學(xué)校，給我們提供了一個(gè)良好的課程設(shè)計(jì)環(huán)境，在這次課設(shè)中我學(xué)到了很多，得到了很多，所以我還要再次感謝這些我要感謝的人八、參考文獻(xiàn)1 王昆侖，李紅. 數(shù)據(jù)結(jié)構(gòu)與算法. 北京：中國鐵道出版社，2006年5月。2 胡學(xué)鋼. 數(shù)據(jù)結(jié)構(gòu)與算法指導(dǎo).北京：清華大學(xué)出版社，1999。3 胡學(xué)鋼. 數(shù)據(jù)結(jié)構(gòu).北京：高等教育出版社，2006。4王紅梅，胡明，王濤編著.數(shù)據(jù)結(jié)構(gòu)（C+版）. 北京：清華大學(xué)出版社，2005.7.5譚浩強(qiáng)編著.C+面向?qū)ο蟪绦蛟O(shè)計(jì).北京：清華大學(xué)出版社，2006.1.九，附錄源程序：#include "stdio.h"#incl

12、ude"stdlib.h"int panduan1(int a100100,int n)/判斷各行是否有相等數(shù)int ch=1;int i,j,k; for (i=0;i<n;i+)for (j=0;j<n;j+) for (k=j+1;k<n;k+) if(aij=aik) ch=0;return ch;/行數(shù)有相等 k=0 return ch;/符合數(shù)組各行不相等返回 K=1 int panduan2(int a100100,int n)/判斷各列是否有相等數(shù)int ch=1; int i,j,k; for(i=0;i<n;i+)for(j=0;

13、j<n;j+)for(k=j+1;k<n;k+)if(aji=aki)ch=0;return ch;/列數(shù)有相等 s=0return ch;/符合數(shù)組各列不相等返回 S=1int panduan3(int a100100,int n)/判斷首行首列是否相等int ch=1,flag1=1,flag2=1;int i,j;for(i=0;i<n;i+) /第一行有序if(a0i<a0i+1)flag1=0;break;for(j=0;j<n;j+) /第一列有序if(aj0<aj+10)flag2=0;break;if(flag1=0&&fla

14、g2=0)for (i=1;i<n;i+)if(a0i=ai0)/有序且行列相等 m=0 ch=0;return ch; return ch;/不相等不是標(biāo)準(zhǔn) m=1void main() int n,i,j;int k,s,m;int a100100;printf("請(qǐng)輸入方陣階數(shù)：n");scanf("%d",&n);if(n<=1|n>=100)printf("此數(shù)據(jù)不符合要求n");elseprintf("輸入矩陣的數(shù)據(jù)%d個(gè)n",n*n);k=panduan1(a,n);for (i=0;i<n;i+)for(j=0;j<n;j+) scanf("%d",&aij);if(aij>n)k=0;for(i=0;i<n;i+) printf("n"); for(j=0;j<n;j+) printf(&quo