《数据结构》课程设计报告题目:本科生导师制问题专业:计算机科学与技术班级:15计算机科学与技术(2)班姓名:余宙指导教师:孙妍姑成绩:计算机学院2016年11月10日学号15080102322016-2017学年第一学期淮南师范学院计算机科学与技术(2)班1/11目录1.1设计内容及要求············21.2概要设计···············21.3设计过程及程序代码1.4设计结果与分析1.5参考文献淮南师范学院计算机科学与技术(2)班2/111.1、需求一、问题描述在高校的教学改革中,有很多学校实现了本科生导师制。一个班级的学生被分给几个老师,每个老师带n个学生,如果该老师还带研究生,那么研究生也可以直接带本科生。本科生导师制问题中的数据元素具有如下形式:1、导师带研究生:(老师,((研究生1,(本科生1,...,本科生m1)),(研究生2,(本科生1,...,本科生m2)),...))2、导师不带研究生:(老师,(本科生1,...,本科生m))导师的自然情况只包括姓名、职称;研究生的自然情况只包括姓名、班级;本科生的自然情况只包括姓名、班级。二、设计要求1、建立:建立导师广义表;2、插入:将某位本科生或研究生插入到广义表的相应位置;3、删除:将某位本科生或研究生从广义表中删除;4、查询:查询导师、本科生(研究生)的情况;5、统计:某位导师带了多少研究生和本科生;6、输出:将某导师所带学生情况输出;7、退出:程序结束。1.2、概要设计淮南师范学院计算机科学与技术(2)班3/111.3、设计过程及程序代码#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);淮南师范学院计算机科学与技术(2)班4/11length=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;//子表域淮南师范学院计算机科学与技术(2)班5/11}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';//添加结束符}淮南师范学院计算机科学与技术(2)班6/11else//广义表表尾部分空时{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));淮南师范学院计算机科学与技术(2)班7/11h-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;}淮南师范学院计算机科学与技术(2)班8/11returnmax+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{if(h-tag==0)return1;elsereturnGListAtomNum(h-val.subList.head)+GListAtomNum(h-val.subList.tail);}}GLNode*GListSearch(GLNode*h,DataTypex)淮南师范学院计算机科学与技术(2)班9/11{GLNode*p;if(h==NULL)returnNULL;//查找失败递归出口if(h-tag==0&&h-val.atom==x)returnh;//查找成功递归出口if(h-tag==1&&h-val.subList.head!=NULL){p=GListSearch(h-val.subList.head,x);//在头链中查找if(p!=NULL)returnp;}if(h-tag==1&&h-val.subList.tail!=NULL){p=GListSearch(h-val.subList.tail,x);//在尾链中查找if(p!=NULL)returnp;}returnNULL;//回溯至上一层}voidDestroyGList(GLNode*h){if(h==NULL)return;if(h-tag==1&&h-val.subList.head!=NULL)DestroyGList(h-val.subList.head);//撤销head所指子表淮南师范学院计算机科学与技术(2)班10/11if(h-tag==1&&h-val.subList.tail!=NULL)DestroyGList(h-val.subList.tail);//撤销tail所指子表free(h);}