-N阶魔方课程设计报告.doc
《-N阶魔方课程设计报告.doc》由会员分享,可在线阅读,更多相关《-N阶魔方课程设计报告.doc(18页珍藏版)》请在冰点文库上搜索。
经济管理学院本科课程设计论文
数据结构课程设计
学号:
姓名:
班级:
专业:
信息管理与信息系统
系别:
管理系
指导教师:
2011年1月14日吉林
1
数据结构课程设计论文
目录
1
第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魔阵:
4
3
8
9
5
1
2
7
6
具体程序实行过程如下:
1
图1-1在中间行最后一列的位置上插入第一个数据1;
1
2
图1-2在数据1的右下角位置上插入元素2(即i+1);
3
1
2
图1-3检查2的右下方为空,即将3插入;
4
3
1
2
图1-43的右下方有数据1,故将4插入3的左方;
4
3
5
1
2
图1-54的右下方有空位置,插入5;
4
3
5
1
2
6
图1-6将6插入;
4
3
5
1
2
7
6
图1-7将7插入;
4
3
8
5
1
2
7
6
图1-8将8插入;
4
3
8
9
5
1
2
7
6v
图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在一维数组中的存储为如下图:
012345678
4
3
8
9
5
1
2
7
6
图3-1n=3时在一维数组中的存储图
*具体的表示运行方法为以下程序:
int*p=newint[n*n];
inti;
for(i=0;i {
p[i]=0;
}
i=n/2;
intj=n-1;
intk=1;
p[i*n+j]=k;
while(k {
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阶魔阵************"< cout<<"请输入一个奇数n"< intn;//魔阵阶数
stringnn;//浮点数,用以判断输入数是否为整数
while(cin>>nn,n=ConvertStringToInt(nn),n%2==0||n<=0||IsContainInString(nn,'.'))
{
if(IsContainInString(nn,'.'))
{
cout<<"请输入一个整数!
"< }
elseif(n%2==0)
{
cout<<"请不要输入偶数!
"< }
elseif(n<=0)
{
cout<<"请输入一个大于0的数"< }
}
*设计模块可进行连续计算,程序如下:
stringre;
cout<<"继续?
(y/n)"<while(cin>>re,!
IsContainInString(re,'y')&&!
IsContainInString(re,'n'))
{
cout<<"选择无效,请重新选择!
"<}
if(IsContainInString(re,'n'))
{
cout<<"谢谢使用,再见!
"<break;
}
*如遇到特殊情况,可以用dos命令对程序进行操作,具体程序如下:
system("pause");
return0;
*当遇到输入错误时,如,输入的为浮点型数据,则用一下模块进行处理:
intConvertStringToInt(stringre)
{
intn=re.length();
inti,t=0;
for(i=0;i {
if(re[i]<'0'||re[i]>'9')
return0;
t=t*10+re[i]-48;
}
returnt;
}
*IntConertStringToInt(stringre)的流程图如下:
开始
n=re.length()
t=0
i=0
N
结束
returnt
iY
Y
re{i}<’0’||re{i}>’9’
return0
N
t=t*10+re{i}-48
i=i+1
图3-1ConertStringToInt()函数流程图
*boolIsContainInString(string&a,charb)的流程图如下:
开始
n=a.length()
i=0
N
i结束
returnfalse
Y
N
a{i}=b
Y
returntrue
i=i+1
图3-2IsContainInString()函数流程图
第4章详细设计
#include
#include
#include
usingnamespacestd;
intConvertStringToInt(string);
boolIsContainInString(string&,char);
intmain()
{
while
(1)
{
cout<<"************n阶魔阵************"< cout<<"请输入一个奇数n"< intn;//魔阵阶数
stringnn;//浮点数,用以判断输入数是否为整数
while(cin>>nn,n=ConvertStringToInt(nn),n%2==0||n<=0||IsContainInString(nn,'.'))
{
if(IsContainInString(nn,'.'))
{
cout<<"请输入一个整数!
"< }
elseif(n%2==0)
{
cout<<"请不要输入偶数!
"< }
elseif(n<=0)
{
cout<<"请输入一个大于0的数"< }
}
int*p=newint[n*n];
inti;
for(i=0;i {
p[i]=0;//将数组全部清零
}
i=n/2;//将初始坐标定为中间一行最后一页
intj=n-1;
intk=1;//第一个被填的数设为1
p[i*n+j]=k;//填第一个数
while(k {
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;i {
for(j=0;j {
cout< }
cout< }
stringre;
cout<<"继续?
(y/n)"< while(cin>>re,!
IsContainInString(re,'y')&&!
IsContainInString(re,'n'))//如果既没有输入Y,也没有输入N,则认定
//非法输入,重新输入直到输入合法为止
{
cout<<"选择无效,请重新选择!
"< }
if(IsContainInString(re,'n'))//如果输入N,则退出
{
cout<<"谢谢使用,再见!
"< break;
}
}
system("pause");//外部DOS命令pause,用于暂停以监测
//结果
return0;
}
intConvertStringToInt(stringre)//将字符串转换成整型数的函数,若
//字符串中部全为字符,则返回0
{
intn=re.length();
inti,t=0;
for(i=0;i {
if(re[i]<'0'||re[i]>'9')
return0;
t=t*10+re[i]-48;
}
returnt;
}
boolIsContainInString(string&a,charb)//判断字符串中是否包
//含指定字符
{
intn=a.length();
inti;
for(i=0;i {
if(a[i]==b)
returntrue;
}
returnfalse;
}
第5章调试分析
5.1输入界面
(1):
图5-1输入1,再输入n
5.2输入界面
(2):
图5-2输入2
5.3输入界面(3):
图5-3输入3,再输入y
5.4输入界面(4):
图5-4输入3,再输入a
5.5输入界面(5):
图5-5输入1.3
为了使程序健壮行良好,我进行了多次调试,力求尽列出所有的可能数据,并最程序进行修改,使之成为一个优秀的程序。
本程序是关于二维数组的,时间复杂度为O(n2)。
第6章课设总结
通过此次课程设计,我深化了对数据结构的基本概念、理论和方法的理解,把所学的理论知识用于处理实际问题。
这种学以致用的感觉非常好,让自己真正的掌握了所学的知识,并将其利用在实际问题中。
还有就是C++的面向对象的程序设计理念,对程序设计是一个好的启发。
其中,在程序的调试中遇到了一些问题,这让我重新审视到了做好一个程序需要具备哪些能力。
实践能给人以成就之感,我是以着“态度决定一切”的心态对待此次《数据结构》课程设计的,于是偶然又必然地收获了诸多,概而言之,大约以下几点:
1.温故而知新。
课程设计发端之始,对知识系统全面地进行了梳理,遇到难处先是自己思考查资料,再向同学请教,掌握了基本理论知识,而且对理论知识进行实践应用,使得理解更加深刻,学会了如何思考的思维方式。
2实践出真知。
时至今日,课程设计基本告成,切身领悟有了思路还需要用实践进行考验,才明晓实践出真知。
如在进行算法分析时要深刻地从正确性、稳健性、可读性、时间复杂度等方面进行考虑,在一个算法中,进行简单操作的次数越少,其运行时间也就相对的越短;次数越多,其运行时间也就相对的越长。
同样很多时候时间的长短与程序的难易程度(实现的所要付出的代价)呈反比。
通过这次课设使我深刻理解了“不为则不知,无为则无知,实践出真知”这句名言。
3.创新求发展。
“创新”目前已经提升到国家发展战略地位,足见“创新”的举足轻重。
因此,我们要从小处着手,顺应时代发展潮流,在课程设计中不忘在小处创新,未必是创新技术,但凡创新思维亦可,未必成功,只要实现创新思维培育和锻炼即可。
4.过而能改,善莫大焉。
至善至美,是人类永恒的追求。
但是,不从忘却“金无足赤,人无完人”,我们换种思维方式,去恶亦是至善,改错亦为至美。
在课程设计过程中,我们不断发现错误,不断改正,不断领悟,不断获取。
最终的检测调试环节,本身就是在践行“过而能改,善莫大焉”的知行观。
一边制作一边探索,发现理论和实践要充分地结合,是需要扎实的基本功的,解决实际的应用问题,在理解了数据结构内在的逻辑关系的基础上,深入讨论它们在计算机中的存储表示,结合上机进行算法及存储表示的实现。
进一步提高自身的综合运用所学知识处理实际问题的能力,强化面向对象的程序设计理念,从而使自己有所提高。
这就表明学好基础知识是理论付诸实践的前提。
在这次《数据结构》课程设计中我学到了很多,收获了很多,这些收获将成为以后学习中一笔不可或缺的财富。
在以后学习中我会更加努力学习理论知识,并将所学与实践结合起来。
16
16