数据结构实验报告 魔方阵

《数据结构实验报告 魔方阵》由会员分享，可在线阅读，更多相关《数据结构实验报告 魔方阵（10页珍藏版）》请在装配图网上搜索。

1、 实验报告实验名称：（一）魔方阵（二）本科生导师制问题实验类型：设计性实验班级：20100631学号：2010063114姓名：万星含（一）魔方阵1.问题描述魔方阵是一个古老的智力问题，它要求在一个mm的矩阵中填入1m2的数字（m为奇数），使得每一行、每一列、每条对角线的累加和都相等，如图1所示。 基本要求l输入魔方阵的行数m，要求m为奇数，程序对所输入的m作简单的判断，如m有错，能给出适当的提示信息。l实现魔方阵。l输出魔方阵。实现提示本实验使用的数据结构是数组。解魔方阵问题的方法很多，这里采用如下规则生成魔方阵。l由1开始填数，将1放在第0行的中间位置。l将魔方阵想象成上下、左右相接，每次

2、往左上角走一步，会有下列情况：左上角超出上方边界，则在最下边相对应的位置填入下一个数字；左上角超出左边边界，则在最右边相应的位置填入下一个数字；如果按上述方法找到的位置已填入数据，则在同一列下一行填入下一个数字。以33魔方阵为例，说明其填数过程，如图2所示。 由三阶魔方阵的生成过程可知，某一位置(x,y)的左上角的位置是(x-1,y-1),如果x-10，不用调整，否则将其调整为x-1+m；同理，如果y-10，不用调整，否则将其调整为y-1+m。所以，位置(x,y)的左上角的位置可以用求模的方法获得，即：x=(x-1+m)%my=(y-1+m)%m如果所求的位置已经有数据了，将该数据填入同一列下

3、一行的位置。这里需要注意的是。此时的x和y已经变成之前的上一行上一列了，如果想变回之前位置的下一行同一列，x需要跨越两行，y需要跨越一列，即：x=(x+2)%my=(y+1)%m思考l可以考虑使用其他方法生成魔方阵。任何算法都有不同的实现方法，通过采用不同实现方法来重新实现算法，这要比单纯学习算法的效果好得多。2.实验要求（1） 认真阅读和掌握和本实验相关的教材内容、算法和设计程序。（3） 上机运行程序。（4） 保存和打印出程序的运行结果，并结合程序进行分析。3.实验目的（1）设计数据结构；（2）设计算法完成任意n阶魔方阵的填数；（3）分析算法的时间复杂度。4. 程序源代码#include #

4、include #define MAX_NUM 500 /*这里可以修改最大阶*/int main() int rows = 0, center = 0, iArrayMAX_NUMMAX_NUM; int RowSet = 0, LineSet = 0, newRowSet = 0, newLineSet = 0; int i = 0, j = 0; int okNum = 0; / set the items of array iArray to be 0 for ( i = 0; i MAX_NUM; i+ ) for ( j = 0; j MAX_NUM; j+ ) iArrayij

5、= 0; / get the rows number while ( 1 ) printf(输入行数:n); scanf(%d, &rows); if ( rows = MAX_NUM ) rows -= 1; break; else printf(行数必须在 0 和 %d 之间, 请重新, MAX_NUM); / set number 1 center = rows / 2; iArray0center = 1; / initialize the okNum, RowSet and LineSet okNum = 1; RowSet = 0; LineSet = center; / set

6、each item in iArray while ( okNum (rows + 1) * (rows + 1) ) if ( RowSet = 0 & LineSet = rows ) RowSet += 1; else newRowSet = (RowSet = 0) ? rows : RowSet - 1; newLineSet = (LineSet = rows) ? 0 : LineSet + 1; if ( iArraynewRowSetnewLineSet != 0 ) / there is already a number here! RowSet = (RowSet = r

7、ows) ? 0 : RowSet + 1; /RowSet += 1; else RowSet = newRowSet; LineSet = newLineSet; iArrayRowSetLineSet = +okNum; / print the iArray for ( i = 0; i = rows; i+ ) for ( j = 0; j = rows; j+ ) printf(%5d, iArrayij); printf(n); system(pause); return 0; 6.调试结果（2） 本科生导师制问题1.问题描述在高校的教学改革中，有很多学校实行了本科生导师制。一个班

8、级的学生被分给几个老师，每个老师带n个学生，如果该老师还带研究生，那么研究生也可直接带本科生。本科生导师制问题中的数据元素具有如下形式：l导师带研究生（老师，（研究生1，（本科生1，本科生m1），（研究生2，（本科生1，本科生m2）l导师不带研究生（老师，（本科生1，本科生m）导师的自然情况只包括姓名、职称；研究生的自然情况只包括姓名、班级；本科生的自然情况只包括姓名、班级。基本要求要求完成以下功能：l建立：建立导师广义表。l插入：将某位本科生或研究生插入到广义表的相应位置。l删除：将某本科生或研究生从广义表中删除。l查询：查询导师、本科生（研究生）的情况。l统计：某导师带了多少个研究生和本科

9、生。l输出：将某导师所带学生情况输出。l退出：程序结束。2.设计思路 本实验使用的数据结构是广义表，广义表采用头尾链表存储结构来实现。定义教师、学生结点结构体如下：typedef struct GLNode char name100; /*教师或学生的姓名*/ char prof100; /*教师结点表示职称，学生结点表示班级*/ int type; /*结点类型：0-教师，1-研究生，2-本科生*/struct struct GLNode *hp, *tp; ptr; /*hp指向同级的下一结点，tp指向下级的首结点*/GList;人员信息的表示形式为：高老师-教授-0、李刚-二班-1、李明

10、-二班-2.人员信息中的姓名、职称、班级、人员类型用“-”隔开，如高老师-教授-0，“高老师”表示姓名，“教师”表示职称，“0”表示人员的类型是教师；李刚-二班-1，“李刚”表示姓名，“二班”表示班级，“1”表示人员的类型是研究生；李明-二班-2，“李明”表示姓名，“二班”表示班级，“2”表示人员的类型是本科生。广义表（高老师-教授-0，（李明-一班-2，王平-二班-2），（李老师-副教授-0，（白梅-二班-1，（李刚-一班-2）可以用图3表示。 3. 功能要求 要求完成以下功能： 插入：将某位本科生或研究生插入到广义表的相应位置； 删除：将某本科生或研究生从广义表中删除； 查询：查询导师、本

11、科生（研究生）的情况； 统计：某导师带了多少个研究生和本科生； 输出：将某导师所带学生情况输出。4. 源代码#include #include #include typedef char DataType;#include GList.hvoid main() char str1=(a,b,c),(d),e); char str2=(a,b,c),(d),e); char hstr100; GLNode *h, *p; int depth, number, length; h=CreatGList(str1); printf(广义表str1=%s,str2); DecomposeStr(str

12、2, hstr); printf(n表头=%s,hstr); printf( 表尾=%s,str2); depth=GListDepth(h); printf(n深度depth=%d,depth); length=GListLength(h); printf(n深度length=%d, length); number=GListAtomNum(h); printf(n原子元素个数number=%d, number); p=GListSearch(h,d); if (p!=NULL) printf(n数据元素%c在广义表中, p-val.atom); else printf(n广义表中不存在要查

13、找的数据元素n); DestroyGList(h);头文件：typedef struct GListNodeint tag; union DataType atom; /原子元素域 struct subGL struct GListNode *head; /头指针 struct GListNode *tail; /尾指针 subList; /子表域 val;GLNode;void DecomposeStr(char str, char hstr) int i, j, tag, n = strlen(str); char ch; ch = str0; tag = 0; for(i = 0; i

14、= n-1; i+) if(stri = , & tag = 1 ) break;/搜索最外层的第一个逗号 ch = stri; if(ch = () tag+; if(ch = ) tag-; if(i = n-1 & stri = ,) /广义表表尾部分非空时 for(j = 0; j i-1; j+) hstrj = strj+1;/取表头字符串 hstrj = 0; /添加结束符 if(stri = ,) i+; str0 = (; /添( for(j = 1; i tag = 0; h-val.atom = str0; else /建立子表 h = (GLNode *)malloc(

15、sizeof(GLNode); h-tag = 1; DecomposeStr(str, hstr); h-val.subList.head = CreatGList(hstr); if(strcmp(str, () != 0) /表尾非空时 h-val.subList.tail = CreatGList(str); else h-val.subList.tail = NULL; /赋值空指针 return h;int GListDepth(GLNode *h) int max, dep; GLNode *pre; if(h = NULL) return 1;/递归出口，空表深度为1 if(h

16、-tag = 0) return 0; /递归出口，原子元素深度为0/递归求广义表深度 pre = h; for(max = 0; pre != NULL; pre = pre-val.subList.tail) dep = GListDepth(pre-val.subList.head); /求表头深度 if(dep max) max = dep; return max + 1; int GListLength(GLNode *h) int number = 0; GLNode *p; for(p = h; p != NULL; p = p-val.subList.tail) number+

17、; return number; int GListAtomNum(GLNode *h) if(h = NULL) return 0; else if(h-tag = 0) return 1; else return GListAtomNum(h-val.subList.head) + GListAtomNum(h-val.subList.tail); GLNode *GListSearch(GLNode *h, DataType x) GLNode *p; if(h=NULL) return NULL;/查找失败递归出口 if(h-tag=0&h-val.atom=x) return h;/

18、查找成功递归出口 if(h-tag=1&h-val.subList.head!=NULL) p=GListSearch(h-val.subList.head,x); /在头链中查找 if (p!=NULL) return p; if(h-tag=1&h-val.subList.tail!=NULL) p=GListSearch(h-val.subList.tail,x); /在尾链中查找 if (p!=NULL) return p; return NULL; /回溯至上一层 void DestroyGList(GLNode *h) if(h=NULL) return ; if(h-tag=1&h-val.subList.head!=NULL) DestroyGList(h-val.subList.head); /撤销head所指子表 if(h-tag=1&h-val.subList.tail!=NULL) DestroyGList(h-val.subList.tail); /撤销tail所指子表 free(h); （注：文档可能无法思考全面，请浏览后下载，供参考。可复制、编制，期待你的好评与关注！）