数据结构实验报告-魔方阵

实验报告实验名称：（一）魔方阵（二）本科生导师制问题实验类型：设计性实验班级：20100631学号：2010063114姓名：万星含（一）魔方阵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.程序源代码#includestdio.h#includestdlib.h#defineMAX_NUM500/*这里可以修改最大阶*/intmain(){introws=0,center=0,iArray[MAX_NUM][MAX_NUM];intRowSet=0,LineSet=0,newRowSet=0,newLineSet=0;inti=0,j=0;intokNum=0;//settheitemsofarrayiArraytobe0for(i=0;iMAX_NUM;i++)for(j=0;jMAX_NUM;j++)iArray[i][j]=0;//gettherowsnumberwhile(1){printf(输入行数:\n);scanf(%d,&rows);if(rows=MAX_NUM){rows-=1;break;}else{printf(行数必须在0和%d之间,请重新,MAX_NUM);}}//setnumber'1'center=rows/2;iArray[0][center]=1;//initializetheokNum,RowSetandLineSetokNum=1;RowSet=0;LineSet=center;//seteachiteminiArraywhile(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(iArray[newRowSet][newLineSet]!=0)//thereisalreadyanumberhere!{RowSet=(RowSet==rows)?0:RowSet+1;//RowSet+=1;}else{RowSet=newRowSet;LineSet=newLineSet;}}iArray[RowSet][LineSet]=++okNum;}//printtheiArrayfor(i=0;i=rows;i++){for(j=0;j=rows;j++)printf(%5d,iArray[i][j]);printf(\n);}system(pause);return0;}6.调试结果（二）本科生导师制问题1.问题描述在高校的教学改革中，有很多学校实行了本科生导师制。一个班级的学生被分给几个老师，每个老师带n个学生，如果该老师还带研究生，那么研究生也可直接带本科生。本科生导师制问题中的数据元素具有如下形式：导师带研究生（老师，（（研究生1，（本科生1，…，本科生m1）），（研究生2，（本科生1，…，本科生m2））…））导师不带研究生（老师，（本科生1，…，本科生m））导师的自然情况只包括姓名、职称；研究生的自然情况只包括姓名、班级；本科生的自然情况只包括姓名、班级。②基本要求要求完成以下功能：建立：建立导师广义表。插入：将某位本科生或研究生插入到广义表的相应位置。删除：将某本科生或研究生从广义表中删除。查询：查询导师、本科生（研究生）的情况。统计：某导师带了多少个研究生和本科生。输出：将某导师所带学生情况输出。退出：程序结束。2.设计思路本实验使用的数据结构是广义表，广义表采用头尾链表存储结构来实现。定义教师、学生结点结构体如下：typedefstructGLNode{charname[100];/*教师或学生的姓名*/charprof[100];/*教师结点表示职称，学生结点表示班级*/inttype;/*结点类型：0-教师，1-研究生，2-本科生*/struct{structGLNode*hp,*tp;}ptr;/*hp指向同级的下一结点，tp指向下级的首结点*/}GList;人员信息的表示形式为：高老师-教授-0、李刚-二班-1、李明-二班-2.人员信息中的姓名、职称、班级、人员类型用“-”隔开，如高老师-教授-0，“高老师”表示姓名，“教师”表示职称，“0”表示人员的类型是教师；李刚-二班-1，“李刚”表示姓名，“二班”表示班级，“1”表示人员的类型是研究生；李明-二班-2，“李明”表示姓名，“二班”表示班级，“2”表示人员的类型是本科生。广义表（（高老师-教授-0，（李明-一班-2，王平-二班-2）），（李老师-副教授-0，（白梅-二班-1，（李刚-一班-2）））可以用图3表示。3.功能要求要求完成以下功能：⑴插入：将某位本科生或研究生插入到广义表的相应位置；⑵删除：将某本科生或研究生从广义表中删除；⑶查询：查询导师、本科生（研究生）的情况；⑷统计：某导师带了多少个研究生和本科生；⑸输出：将某导师所带学生情况输出。4.源代码#includestdio.h#includestring.h#includemalloc.htypedefcharDataType;#includeGList.hvoidmain(){charstr1[]=(((a,b,c),(d)),e);charstr2[]=(((a,b,c),(d)),e);charhstr[100];GLNode*h,*p;intdepth,number,length;h=CreatGList(str1);printf(广义表str1=%s,str2);DecomposeStr(str2,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);elseprintf(\n广义表中不存在要查找的数据元素\n);DestroyGList(h);头文件：typedefstructGListNode{inttag;union{DataTypeatom;//原子元素域structsubGL{structGListNode*head;//头指针structGListNode*tail;//尾指针}subList;//子表域}val;}GLNode;voidDecomposeStr(charstr[],charhstr[]){inti,j,tag,n=strlen(str);charch;ch=str[0];tag=0;for(i=0;i=n-1;i++){if(str[i]==','&&tag==1)break;//搜索最外层的第一个逗号ch=str[i];if(ch=='(')tag++;if(ch==')')tag--;}if(i=n-1&&str[i]==',')//广义表表尾部分非空时{for(j=0;ji-1;j++)hstr[j]=str[j+1];//取表头字符串hstr[j]='\0';//添加结束符if(str[i]==',')i++;str[0]='(';//添'('for(j=1;i=n-2;i++,j++)str[j]=str[i];//取表尾字符串str[j]=')';//添')'str[++j]='\0';//添加结束符}else//广义表表尾部分空时{str++;//路过最左边的'('strncpy(hstr,str,n-2);//不复制右边的')'hstr[n-2]='\0';//添加结束符str--;//恢复字符串指针位置strcpy(str,());//表尾部分为空}}GLNode*CreatGList(charstr[]){GLNode*h;charhstr[200];intlen=strlen(str);if(strcmp(str,())==0)h=NULL;elseif(len==1)//建立原子结点{h=(GLNode*)malloc(sizeof(GLNode));h-tag=0;h-val.atom=str[0];}else//建立子表{h=(GLNode*)malloc(sizeof(GLNode));h-tag=1;DecomposeStr(str,hstr);h-val.subList.head=CreatGList(hstr);if(strcmp(str,())!=0)//表尾非空时h-val.subList.tail=CreatGList(str);elseh-val.subList.tail=NULL;//赋值空指针}returnh;}intGListDepth(GLNode*h){intmax,dep;GLNode*pre;if(h==NULL)return1;//递归出口，空表深度为1if(h-tag==0)return0;//递归出口，原子元素深度为0//递归求广义表深度pre=h;for(max=0;pre!=NULL;pre=pre-val.subList.tail){dep=GListDepth(pre-val.subList.head);//求表头深度if(depmax)max=dep;}returnmax+1;}intGListLength(GLNode*h){intnumber=0;GLNode*p;for(p=h;p!=NULL;p=p-val.subList.tail)number++;returnnumber;}intGListAtomNum(GLNode*h){if(h==NULL)return0;else