2023年数据结构实验报告魔方阵

实验报告

实验名称：（一）魔方阵（二）本科生导师制问题

实验类型：设计性实验

班级：20230631

学号：

姓名：万星含

（一）魔方阵

1.问题描述

魔方阵是一个古老的智力问题,它规定在一个mXm的矩阵中填入1〜m?的数

字（m为奇数），使得每一行、每一列、每条对角线的累加和都相等，如图1所

Zj\O

15812417

16147523

22201364

321191210

92251811

图1五阶魔方阵示例

②基本规定

・输入魔方阵的行数m,规定m为奇数，程序对所输入的m作简朴的判断,

如m有错,能给出适当的提醒信息。

・实现魔方阵。

・输出魔方阵。

③实现提醒

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

解魔方阵问题的方法很多，这里采用如下规则生成魔方阵。

•由1开始填数，将1放在第0行的中间位置。

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

令左上角超过上方边界，则在最下边相相应的位置填入下一个数字；

令左上角超过左边边界，则在最右边相应的位置填入下一个数字；

令假如按上述方法找到的位置已填入数据，则在同一列下一行填入下一

个数字。

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

(g)(h)(i)

图2三阶魔方阵的生成过程

由三阶魔方阵的生成过程可知，某一位置(x,y)的左上角的位置是(xT,

yT),假如xTNO,不用调整，否则将其调整为xT+m;同理，假如yT20,不用

调整，否则将其调整为y—1+m。所以，位置(x,y)的左上角的位置可以用求模的

方法获得，即：

x=(x-l+m)%m

y=(y-l+m)%m

假如所求的位置已有数据了，将该数据填入同一列下一行的位置。这里需要

注意的是。此时的x和y已经变成之前的上一行上一列了，假如想变回之前位置

的下一行同一列,x需要跨越两行,y需要跨越一列，即：

x=(x+2)%m

y=(y+l)%m

④思考

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

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

多。

2.实验规定

（1）认真阅读和掌握和本实验相关的教材内容、算法和设计程序。

（3）上机运营程序。

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

3.实验目的

(1)设计数据结构；

(2)设计算法完毕任意n阶魔方阵的填数；

(3)分析算法的时间复杂度。

4.程序源代码

#inc1ude<stdio.h>

#include<stdlib.h>

#defineMAX_NUM500/*这里可以修改最大阶*Aintmain(>{

introws=0,center=0,iArrayCMAX_NUM][MAX_NUM]/intRowSet=0,

LineSet=0,newRowSet=0,newLineSet=0；Ainti=0,j=0；

intokNum=05A//settheiternsofarray"iArray"tobeOfor(i=

0；i<MAX_NUM;i+4-)Afor(j=0；j<MAX_NUM;j++)

iArray[i][j]=0;

//gettherowsnumber

whiIe(1)

{Aprintf("输入行数：\n")泠seanf("%d"，&rows);

if(rows<=MAX_NUM>{

rows

break；町else

Printf("行数必须在0和%d之间，请重新”,MAX_NUM)；A)

)A

//setnumber1crows2；

iArray[0][center]=1：AA//nitiaIizetheokNum,RowSetandLine

SetAokNum

RowSet0;

LineSetcenter

teachemn"iArray

While(okNum(rows+1)*(r0ws+)A

ifRowSt0&&LineSetrows)

RowS+=

}

wRowSetRowSet0)?rowsRowSet1

newLineSet(LineSetrOWS)?0:LineSet+1

Af(iAray[newROwSet][wLineSet]!=0)

//thsaireadyanumbhere

RowSet(RowSerows)?0RowSe1

//RowSet1)

se(

RowSenewRowSet；ALineSetnewLineSet

))

iArray[RowSet][LineSet]++okNum；A}

printthe"iArray

for(i=0；rows;i++)A{Afor(j=0；<=rows；j++)

printf("%5d”Array[i][j])

printf)；

}

system("pause")；Areturn0

}

6.调试结果

1791352719

2416863426

2523157533

32302214124

39129211311

10236282018

（-）本科生导师制问题

1.问题描述

在高校的教学改革中，有很多学校实行了本科生导师制。一个班级的学生被

分给几个老师，每个老师带n个学生，假如该老师还带研究生，那么研究生也可

直接带本科生。本科生导师制问题中的数据元素具有如下形式：

•导师带研究生A（老师，（（研究生1,（本科生1,本科生m1））,（研

究生2,（本科生1,…，本科生m2））…））

•导师不带研究生A（老师，（本科生1,…，本科生m））

导师的自然情况只涉及姓名、职称;研究生的自然情况只涉及姓名、班级；

本科生的自然情况只涉及姓名、班级。

②基本规定

规定完毕以下功能：

1建立:建立导师广义表。

•插入：将某位本科生或研究生插入到广义表的相应位置。

・删除：将某本科生或研究生从广义表中删除。

•查询：查询导师、本科生（研究生）的情况。

・记录:某导师带了多少个研究生和本科生。

I输出：将某导师所带学生情况输出。

•退出：程序结束。

2.设计思绪

本实验使用的数据结构是广义表，广义表采用头尾链表存储结构来实现。

定义教师、学生结点结构体如下：

typedefstructGLNode

（

charname[100];/*教师或学生的姓名*/

charprof[100];/*教师结点表达职称，学生结点表达班级

*/

inttype；/*结点类型：0—教师，1-研究生，2-本

科生*/

struct{structGLNode*hp,*tp;}ptr;

/*hp指向同级的下一结点，tp指向下级的首结

占*/

八、、I

{GList；

人员信息的表达形式为：高老师-专家-0、李刚一二班-1、李明-二班-2.

人员信息中的姓名、职称、班级、人员类型用隔开，如高老师-专家一

0,“高老师”表达姓名，“教师”表达职称，“0”表达人员的类型是教师;李刚-

二班一1,“李刚”表达姓名，“二班”表达班级，“1”表达人员的类型是研究

生；李明-二班一2,“李明”表达姓名，“二班”表达班级，“2”表达人员的类型

是本科生。

广义表（（高老师-专家-0,（李明-一班-2,王平-二班一2））,（李老师一

副专家一0,（白梅-二班-1,（李刚-一班-2）））可以用图3表达。

高老师教授o『「T_李老师副教授o

李明一班2*

图3导师制用广义表实现示例

3.功能规定

规定完毕以下功能：

⑴插入：将某位本科生或研究生插入到广义表的相应位置;

⑵删除：将某本科生或研究生从广义表中删除；

⑶查询：查询导师、本科生（研究生）的情况；

⑷记录:某导师带了多少个研究生和本科生；

⑸输出:将某导师所带学生情况输出。

4.源代码

#inelude<stdio.h>

#inelude<string.h>A#inc1ude<malloc.h>AtypedefcharDataType；A#includ

eGList.h

voidmain()A{charstrl[]n(((a,b,c),(d)),e)

charstr2[]="(((a,b,c),(d)),e)"；Acharhstr[100]?GLNode*h,*p；

intdepth,numbeelength/h=CreatGList(strl);

printf("广义表strl=%s",str2);

DecomposeStr(str2,hstr);

printf("\n表头二％s",hstr)泠printf("表尾二%s",str2)；AAdepth=GLi

n

stDepth(h)；Aprintf(\n深度depth=%d",depth)；Alength=GListLength

(h);

printf("\n深度Iength=%dIength);

number=GListAtomNum(h);

printf("\n原子元素个数number=%d",number);

p=GListSearch(h；d>if(p!=NULL)Aprintf("\n数据元素％(:在广义表中

n

,p->val.atom)；Aelse

printf("\n广义表中不存在要查找的数据元素\n”)；ADestroyGList(h)泠

头文献：

typedefstructGListNode

{Ainttag；Aunions{DataTypeatom;//原子元素域A

structsubGLA{structGListNode*head;〃头指针AstructGListN

ode*tai1;//尾指针

}subList;〃子表域

}va1泠}GLNode;

voidDecomposeStr(charstr[]zcharhstr[])

{Ajnti,jftag,n=str1en(str)；

charch;chstr[O]；tag0泠for(i0;i<=n-1;i++)

if(str[i]tag==1)break;〃搜索最外层的第一个逗号

chs[i]；

f(ch'(')tag++；Aif(ch'),)tag—;A)

<=n-1&&str[i]==7)〃广义表表尾部分非空时A

for(j=0；i-1；j++)hstr[j]str[j+1];〃取表头字符串

hstr[j]0//添加结束符

fstr[i])i++；

str[O]'('；//添'('Afor(j1;i<=n-2;i++,j++)

str[j]sr[i1；取表尾字符串

tr[j]=')'；〃添'str[H-+j],\O';//添加结束符A)

else〃广义表表尾部分空时4str++;〃路过最左边的'('astrnc

py(hstr;stn-2);