2023年數(shù)據(jù)結(jié)構(gòu)實驗報告魔方陣

實驗報告

實驗名稱：（一）魔方陣（二）本科生導(dǎo)師制問題

實驗類型：設(shè)計性實驗

班級：20230631

學(xué)號：

姓名：萬星含

（一）魔方陣

1.問題描述

魔方陣是一個古老的智力問題,它規(guī)定在一個mXm的矩陣中填入1?m?的數(shù)

字（m為奇數(shù)），使得每一行、每一列、每條對角線的累加和都相等，如圖1所

Zj\O

15812417

16147523

22201364

321191210

92251811

圖1五階魔方陣示例

②基本規(guī)定

?輸入魔方陣的行數(shù)m,規(guī)定m為奇數(shù)，程序?qū)λ斎氲膍作簡樸的判斷,

如m有錯,能給出適當(dāng)?shù)奶嵝研畔ⅰ?/p>

?實現(xiàn)魔方陣。

?輸出魔方陣。

③實現(xiàn)提醒

本實驗使用的數(shù)據(jù)結(jié)構(gòu)是數(shù)組。

解魔方陣問題的方法很多，這里采用如下規(guī)則生成魔方陣。

?由1開始填數(shù)，將1放在第0行的中間位置。

1將魔方陣想象成上下、左右相接，每次往左上角走一步，會有下列情況：

令左上角超過上方邊界，則在最下邊相相應(yīng)的位置填入下一個數(shù)字；

令左上角超過左邊邊界，則在最右邊相應(yīng)的位置填入下一個數(shù)字；

令假如按上述方法找到的位置已填入數(shù)據(jù)，則在同一列下一行填入下一

個數(shù)字。

以3X3魔方陣為例，說明其填數(shù)過程，如圖2所示。

(g)(h)(i)

圖2三階魔方陣的生成過程

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

yT),假如xTNO,不用調(diào)整，否則將其調(diào)整為xT+m;同理，假如yT20,不用

調(diào)整，否則將其調(diào)整為y—1+m。所以，位置(x,y)的左上角的位置可以用求模的

方法獲得，即：

x=(x-l+m)%m

y=(y-l+m)%m

假如所求的位置已有數(shù)據(jù)了，將該數(shù)據(jù)填入同一列下一行的位置。這里需要

注意的是。此時的x和y已經(jīng)變成之前的上一行上一列了，假如想變回之前位置

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

x=(x+2)%m

y=(y+l)%m

④思考

?可以考慮使用其他方法生成魔方陣。任何算法都有不同的實現(xiàn)方法，通過

采用不同實現(xiàn)方法來重新實現(xiàn)算法，這要比單純學(xué)習(xí)算法的效果好得

多。

2.實驗規(guī)定

（1）認真閱讀和掌握和本實驗相關(guān)的教材內(nèi)容、算法和設(shè)計程序。

（3）上機運營程序。

（4）保存和打印出程序的運營結(jié)果，并結(jié)合程序進行分析。

3.實驗?zāi)康?/p>

(1)設(shè)計數(shù)據(jù)結(jié)構(gòu)；

(2)設(shè)計算法完畢任意n階魔方陣的填數(shù)；

(3)分析算法的時間復(fù)雜度。

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("輸入行數(shù)：\n")泠seanf("%d"，&rows);

if(rows<=MAX_NUM>{

rows

break；町else

Printf("行數(shù)必須在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.調(diào)試結(jié)果

1791352719

2416863426

2523157533

32302214124

39129211311

10236282018

（-）本科生導(dǎo)師制問題

1.問題描述

在高校的教學(xué)改革中，有很多學(xué)校實行了本科生導(dǎo)師制。一個班級的學(xué)生被

分給幾個老師，每個老師帶n個學(xué)生，假如該老師還帶研究生，那么研究生也可

直接帶本科生。本科生導(dǎo)師制問題中的數(shù)據(jù)元素具有如下形式：

?導(dǎo)師帶研究生A（老師，（（研究生1,（本科生1,本科生m1））,（研

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

?導(dǎo)師不帶研究生A（老師，（本科生1,…，本科生m））

導(dǎo)師的自然情況只涉及姓名、職稱;研究生的自然情況只涉及姓名、班級；

本科生的自然情況只涉及姓名、班級。

②基本規(guī)定

規(guī)定完畢以下功能：

1建立:建立導(dǎo)師廣義表。

?插入：將某位本科生或研究生插入到廣義表的相應(yīng)位置。

?刪除：將某本科生或研究生從廣義表中刪除。

?查詢：查詢導(dǎo)師、本科生（研究生）的情況。

?記錄:某導(dǎo)師帶了多少個研究生和本科生。

I輸出：將某導(dǎo)師所帶學(xué)生情況輸出。

?退出：程序結(jié)束。

2.設(shè)計思緒

本實驗使用的數(shù)據(jù)結(jié)構(gòu)是廣義表，廣義表采用頭尾鏈表存儲結(jié)構(gòu)來實現(xiàn)。

定義教師、學(xué)生結(jié)點結(jié)構(gòu)體如下：

typedefstructGLNode

（

charname[100];/*教師或?qū)W生的姓名*/

charprof[100];/*教師結(jié)點表達職稱，學(xué)生結(jié)點表達班級

*/

inttype；/*結(jié)點類型：0—教師，1-研究生，2-本

科生*/

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

/*hp指向同級的下一結(jié)點，tp指向下級的首結(jié)

占*/

八、、I

{GList；

人員信息的表達形式為：高老師-專家-0、李剛一二班-1、李明-二班-2.

人員信息中的姓名、職稱、班級、人員類型用隔開，如高老師-專家一

0,“高老師”表達姓名，“教師”表達職稱，“0”表達人員的類型是教師;李剛-

二班一1,“李剛”表達姓名，“二班”表達班級，“1”表達人員的類型是研究

生；李明-二班一2,“李明”表達姓名，“二班”表達班級，“2”表達人員的類型

是本科生。

廣義表（（高老師-專家-0,（李明-一班-2,王平-二班一2））,（李老師一

副專家一0,（白梅-二班-1,（李剛-一班-2）））可以用圖3表達。

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

李明一班2*

圖3導(dǎo)師制用廣義表實現(xiàn)示例

3.功能規(guī)定

規(guī)定完畢以下功能：

⑴插入：將某位本科生或研究生插入到廣義表的相應(yīng)位置;

⑵刪除：將某本科生或研究生從廣義表中刪除；

⑶查詢：查詢導(dǎo)師、本科生（研究生）的情況；

⑷記錄:某導(dǎo)師帶了多少個研究生和本科生；

⑸輸出:將某導(dǎo)師所帶學(xué)生情況輸出。

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原子元素個數(shù)number=%d",number);

p=GListSearch(h；d>if(p!=NULL)Aprintf("\n數(shù)據(jù)元素％(:在廣義表中

n

,p->val.atom)；Aelse

printf("\n廣義表中不存在要查找的數(shù)據(jù)元素\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//添加結(jié)束符

fstr[i])i++；

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

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

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

else〃廣義表表尾部分空時4str++;〃路過最左邊的'('astrnc

py(hstr;stn-2);