数据结构试验报告 魔方阵

本文格式为Word版，下载可任意编辑——数据结构试验报告魔方阵

试验报告

试验名称：（一）魔方阵（二）本科生导师制问题试验类型：设计性试验班级：20230631学号：2023063114姓名：万星含（一）魔方阵1.问题描述

魔方阵是一个古老的智力问题，它要求在一个m×m的矩阵中填入1～m2的数字（m为奇数），使得每一行、每一列、每条对角线的累加和都相等，如图1所示。②基本要求

?输入魔方阵的行数m，要求m为奇数，程序对所输入的m作简单的判断，

如m有错，能给出适当的提醒信息。?实现魔方阵。?输出魔方阵。③实现提醒

本试验使用的数据结构是数组。

解魔方阵问题的方法好多，这里采用如下规则生成魔方阵。?由1开始填数，将1放在第0行的中间位置。

?将魔方阵想象成上下、左右相接，每次往左上角走一步，会有以下状况：

?左上角超出上方边界，则在最下边相对应的位置填入下一个数字；?左上角超出左边边界，则在最右边相应的位置填入下一个数字；?假使按上述方法找到的位置已填入数据，则在同一列下一行填入下一

个数字。

以3×3魔方阵为例，说明其填数过程，如图2所示。

由三阶魔方阵的生成过程可知，某一位置(x,y)的左上角的位置是(x-1,y-1),假使x-1≥0，不用调整，否则将其调整为x-1+m；同理，假使y-1≥0，不用调整，否则将其调整为y-1+m。所以，位置(x,y)的左上角的位置可以用求模的方法获得，即：

x=(x-1+m)%my=(y-1+m)%m

假使所求的位置已经有数据了，将该数据填入同一列下一行的位置。这里需要注意的是。此时的x和y已经变成之前的上一行上一列了，假使想变回之前位置的下一行同一列，x需要跨越两行，y需要跨越一列，即：

x=(x+2)%my=(y+1)%m④思考

?可以考虑使用其他方法生成魔方阵。任何算法都有不同的实现方法，通过

采用不同实现方法来重新实现算法，这要比单纯学习算法的效果好得多。

2.试验要求

（1）认真阅读和把握和本试验相关的教材内容、算法和设计程序。（3）上机运行程序。

（4）保存和打印出程序的运行结果，并结合程序进行分析。

3.试验目的

（1）设计数据结构；

（2）设计算法完成任意n阶魔方阵的填数；（3）分析算法的时间繁杂度。

4.程序源代码

#include#include#define

MAX_NUM

500

/*

这

里

可

以

修

改

最

大

阶

*/

int{intintintint//forfor//while{printf(\scanf(\if{rowsbreak;}elseprintf(\}}//center

iArray[0][center]//okNumRowSetLineSet//while{if{RowSet}else

+=

(

RowSet

==

0

0;

of

ij

=array

3.功能要求

要求完成以下功能：

⑴插入：将某位本科生或研究生插入到广义表的相应位置；⑵删除：将某本科生或研究生从广义表中删除；⑶查询：查询导师、本科生（研究生）的状况；⑷统计：某导师带了多少个研究生和本科生；⑸输出：将某导师所带学生状况输出。

4.源代码

#include#include#includetypedef#includevoid{charcharGLNodeint

h=CreatGList(str1);printf(\

DecomposeStr(str2,printf(\printf(\

depth=GListDepth(h);printf(\

length=GListLength(h);printf(\printf(\

原

深子

元

度素

个

数

length=%d\

number=%d\

length);number);

number=GListAtomNum(h);

深

度

depth=%d\

表

头

表

尾

广

义

表

str1=%s\

hstr);=%s\=%s\

depth,

*h,

number,

char

main()

str1[]=\str2[]=\

hstr[100];

*p;length;

char

DataType;\

p=GListSearch(h,'d');if

printf(\elseprintf(\头typedef{intunion{

DataType

atom;

//

//原//

子头尾

元

素指指

域针针

struct{

struct

GListNode

*tail;

*head;

struct}val;}GLNode;void{intcharfor(ichif(chif(ch}if(ihstr[j]if(str[i]str[0]

=

'(';

=

val.atom);

}subList;//子表域

{if(str[i]==','//探寻最外层的第一个逗号

for(j=1;itagh->val.atom}else

{hh->tag

DecomposeStr(str,h->val.subList.headif(strcmp(str,h->val.subList.tailelse

h->val.subList.tail}return}int{

==

NULL)归=

dep>

0;=

return求pre

!=max)max

GListLength(GLNode

GLNodeif(h//

递

1;//

递广

=NULL;

premax

+=

//

GListDepth(pre->val.subList.head);

求=

表

归

出义

口

，

空表

表

深深

GListDepth(GLNode

int

max,

空非

*)malloc(sizeof(GLNode));

*)malloc(sizeof(GLNode));

1;hstr);

CreatGList(hstr);

空

时

CreatGList(str);

指

针h;*h)dep;*pre;

度

为

10度h;

pre->val.subList.tail)

头

深

度dep;1;*h)

if(h->tagprefor(max{if(dep}return}int{

==0)return0;//递归出口，原子元素深度为

intGLNodefor(preturn}int{

if(helse{

==

=

h;

number=0;*p;

p!=NULL;p=p->val.subList.tail)

number;number++;

GListAtomNum(GLNode

NULL)

return

*h)0;if(h->tag==0)return1;elsereturnGListAtomNum(h->val.subList.head)

GListAtomNum(h->val.subList.tail);}}GLNode{GLNode

if(h==NULL)

return

NULL;//

查return

if(h->tag==0//回溯至上一层}void{

if(h==NULL)

if(h->tag==1DestroyGList(h->val.subList.tail);free(h);}

////

撤撤

销销

headtail

所所

指指

子子

表表

if(h->tag==1

DestroyGList(GLNode

*h)

p=GListSearch(h->val.subList.tail,x);

//

在

尾

链

中

查

找