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

课程设计题目：数字旋转方阵 问题描述 设计一个能正确输出N×N（1=N=10）数字旋转方阵（如图1.1） 图1.1 5阶旋转方阵 图1.2逐层填数，从最外层填起 基本要求 设计数据结构存储； 设计算法完成任意N（1=N=10）阶数字旋转方阵； 分析时间复杂度和空间复杂度； 概要设计 数据结构的设计 程序采取二维数组的存储结构进行数字旋转方阵的存储，因为数字旋转方阵也是一个平面图，采用二维数组的存储结构能更直观反映方阵。 算法的设计 每一层的数字分作四个小组，每一组的数字个数为N-1，通过设立一个标志来判断转换方向（如图1.2）。算法结束的标志有两种情况：一是N为1，则填入数字，结束；二是N=0，直接结束。以上两种分别对应奇数阶数字方阵和偶数阶数字方阵。 时间复杂度和空间复杂度 数字旋转方阵是每进行一步填入一个数，所以时间复杂度为O(n*n)； 二维数组所占用的空间是在声明时所分配固定的，所以的空间复杂度为O(100) 详细设计 算法伪代码： 声明二维数组a[10][10]，size为需建立的方阵阶数，初始化i，j，num为1 若size=0，则循环结束； 若size=1，则使a[i][j]=num，循环结束； 填写区域A，重复操作size-1次 a[i][j]=num；i++；num++； 填写区域B，重复操作size-1次 a[i][j]=num；j++；num++； 填写区域C，重复操作size-1次 a[i][j]=num；i--；num++； 填写区域D，重复操作size-1次 a[i][j]=num；j--；num++； i++；j++；size=size-2；返回第1步； 循环结束后，输出数组a； 这是填写逆时针数字方阵的算法，填写顺时针方阵只需把顺序ABCD改为BADC即可 为了方便程序的使用，为其增加了一个菜 单，使用的是switch-case作为选择结构，while 作循环判断 程序详细的流程图如右图所示： 运行与调试 菜单界面 如右图所示： 测试数据和结果 5阶的数字旋转方阵： 总结和心得 在老师的教导和书本的指引下，了解程序的运行方法，掌握其核心要领，一步步进行思考、编写代码。在填写方阵部分，因为size不等于1或0的情况下填数的次数必然大于一，所以选用do-while这种先执行后判断的判断语句。通过自己的思考和努力编写出这个小程序，使我对数据结构的运用有更好的认识，掌握不同的结构，灵活运用。 程序代码 #include iostream using namespace std; //逆时针数字旋转方阵实现 void NFangZhen(int n) { int size=n; int flag=0; //设置转换方向标志 int a[10][10]; //设置二维数组 int i=0,j=0,num=1; while(1) { if(size==0) break; else if(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; } //顺时针数字旋转方阵实现 void SFan