数据结构--旋转数字方阵--课程设计报告

课程设计题目：数字旋转方阵一、问题描述设计一个能正确输出N×N（1=N=10）数字旋转方阵（如图1.1）图1.15阶旋转方阵图1.2逐层填数，从最外层填起二、基本要求(1)设计数据结构存储；(2)设计算法完成任意N（1=N=10）阶数字旋转方阵；(3)分析时间复杂度和空间复杂度；三、概要设计1.数据结构的设计程序采取二维数组的存储结构进行数字旋转方阵的存储，因为数字旋转方阵也是一个平面图，采用二维数组的存储结构能更直观反映方阵。2.算法的设计每一层的数字分作四个小组，每一组的数字个数为N-1，通过设立一个标志来判断转换方向（如图1.2）。算法结束的标志有两种情况：一是N为1，则填入数字，结束；二是N=0，直接结束。以上两种分别对应奇数阶数字方阵和偶数阶数字方阵。3.时间复杂度和空间复杂度数字旋转方阵是每进行一步填入一个数，所以时间复杂度为O(n*n)；二维数组所占用的空间是在声明时所分配固定的，所以的空间复杂度为O(100)四、详细设计算法伪代码：声明二维数组a[10][10]，size为需建立的方阵阶数，初始化i，j，num为11.若size=0，则循环结束；2.若size=1，则使a[i][j]=num，循环结束；3.填写区域A，重复操作size-1次a[i][j]=num；i++；num++；4.填写区域B，重复操作size-1次a[i][j]=num；j++；num++；5.填写区域C，重复操作size-1次a[i][j]=num；i--；num++；6.填写区域D，重复操作size-1次a[i][j]=num；j--；num++；7.i++；j++；size=size-2；返回第1步；8.循环结束后，输出数组a；这是填写逆时针数字方阵的算法，填写顺时针方阵只需把顺序ABCD改为BADC即可为了方便程序的使用，为其增加了一个菜单，使用的是switch-case作为选择结构，while作循环判断程序详细的流程图如右图所示：开始显示菜单输入方阵阶数n(1=n=10)功能1建立数字旋转方阵建立二维数组进入循环size=0？size=1？否循环结束是填充区域Aa[i][j]=num;i++;num++;flag++;flag=size-1？否填充区域Ba[i][j]=num;j++;num++;flag++;填充区域CA[i][j]=num;i--;num++;flag++;flag=size-1？填充区域Da[i][j]=num;j--;num++;flag++;flag=size-1？flag=size-1？否否否i++;j++;size=size-2；否a[i][j]=num;循环结束是输出数组返回菜单功能0退出系统结束是是是是五、运行与调试1.菜单界面如右图所示：2.测试数据和结果5阶的数字旋转方阵：六、总结和心得在老师的教导和书本的指引下，了解程序的运行方法，掌握其核心要领，一步步进行思考、编写代码。在填写方阵部分，因为size不等于1或0的情况下填数的次数必然大于一，所以选用do-while这种先执行后判断的判断语句。通过自己的思考和努力编写出这个小程序，使我对数据结构的运用有更好的认识，掌握不同的结构，灵活运用。七、程序代码#includeiostreamusingnamespacestd;//逆时针数字旋转方阵实现voidNFangZhen(intn){intsize=n;intflag=0;//设置转换方向标志inta[10][10];//设置二维数组inti=0,j=0,num=1;while(1){if(size==0)break;elseif(size==1){a[i][j]=num;break;}else{do//区域A{a[i][j]=num;i++;num++;flag++;}while(flagsize-1);flag=0;do//区域B{a[i][j]=num;j++;num++;flag++;}while(flagsize-1);flag=0;do//区域C{a[i][j]=num;i--;num++;flag++;}while(flagsize-1);flag=0;do//区域D{a[i][j]=num;j--;num++;flag++;}while(flagsize-1);flag=0;//内圈循环i++;j++;size=size-2;}}for(i=0;in;i++){for(j=0;jn;j++){cout.width(4);couta[i][j]'';}coutendl;}coutendl;}//顺时针数字旋转方阵实现voidSFangZhen(intn){intsize=n;intflag=0;//设置转换方向标志inta[10][10];//设置二维数组inti=0,j=0,num=1;while(1){if(size==0)break;elseif(size==1){a[i][j]=num;break;}else{do//区域B{a[i][j]=num;j++;num++;flag++;}while(flagsize-1);flag=0;do//区域A{a[i][j]=num;i++;num++;flag++;}while(flagsize-1);flag=0;do//区域D{a[i][j]=num;j--;num++;flag++;}while(flagsize-1);flag=0;do//区域C{a[i][j]=num;i--;num++;flag++;}while(flagsize-1);flag=0;//内圈循环i++;j++;size=size-2;}}for(i=0;in;i++){for(j=0;jn;j++){cout.width(4);couta[i][j]'';}coutendl;}coutendl;}intmain(){intn;intchoice;intconitue=1;cout**欢迎使用数字旋转方阵系统**endl;coutendl;while(conitue==1){cout1--建立N阶数字旋转方阵endl;cout0--退出系统endl;cout请选择：;cinchoice;switch(choice){case0:conitue=0;break;case1:cout请输入数字旋转方阵的阶数：;cinn;coutendl;cout逆时针数字旋转方阵:endl;NFangZhen(n);coutendl;cout顺时针数字旋转方阵:endl;SFangZhen(n);}}return0;}