2014广工数据结构实验报告抽象数据类型课案

数据结构设计性实验报告课程名称_____数据结构实验_题目名称树学生学院__计算机学院______专业班级13计科3班_学号__________学生姓名______指导教师_________2015年7月3日（1）设计任务、要求及所用软件环境或工具；（2）抽象数据类型定义以及各基本操作的简要描述；（3）所选择的存储结构描述及在此存储结构上各基本操作的实现；（4）程序清单（计算机打印），输入的数据及各基本操作的测试结果；（5）实验总结和体会。实验报告以规定格式的电子文档书写、打印并装订，排版及图表要清楚、工整。3.9思考题对设计性实验进行总结和讨论，包括本实验的优、缺点，数据存储结构的特点，与其它存储结构之间的比较等。通过总结，可以对抽象数据类型有更全面、深入的认识，这是设计性实验不可缺少的重要内容。这部分内容应作为实验报告中的一个组成部分。1.题目:树所用软件为VS_2013基本操作：CreateTree(CSTree&T)功能：创建一棵树操作结果：输入根节点及孩子，构造一个用户自定义的树。DestroyTree(CSTree&T)初始条件：树T已存在。操作结果：销毁树T。TreeDepth(CSTreeT)初始条件：树T已存在。操作结果：返回T的深度。Empty(CSTreeT)初始条件：判断树T是否为空操作结果：空为返回TURE，不空则返回FALSESearch(CSTreeT,TElemTypee)初始条件：树T已存在操作结果：查找T的结点e并返回其指针若这样的元素不存在，则返回值为0。LevelOrderTraverse(constCSTree&T)初始条件：树T已存在操作结果：层次遍历树TInsertChild(CSTreeT,inti,CSTreec)初始条件：树T已存在且非空，1≤i≤d+1操作结果：插入树作为T的第i棵子树2．存储结构定义公用头文件Header.h:#includestdio.h#includestdlib.h#includestdarg.h#defineMAX_TREE_SIZE100#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineOVERFLOW-2typedefintStatus;typedefintTElemType;树操作头文件：Treefunction.h:#includeHeader.h#includestdarg.h#includestring.h#includestddef.h//孩子兄弟表示的树typedefstructCSNode{chardata;structCSNode*firstchild,*nextsibling;}*CSTree;3.算法设计TreeFunction.h:#includeHeader.h#includestdarg.h#includestring.h#includestddef.h//孩子兄弟表示的树typedefstructCSNode{chardata;structCSNode*firstchild,*nextsibling;}*CSTree;/*------------程序中用到的队列------------------------------*/typedefCSTreeQElemType;//队中的元素typedefstructQNode{QElemTypedata;structQNode*next;}QNode,*QueuePtr;/*typedefstructTreeName{charname;structCSNode*nametree;structTreeName*next;}TreeName,*TreeNameP;*/typedefstruct{QueuePtrfront;//队头指针QueuePtrrear;//队尾指针}LinkQueue;StatusInitQueue(LinkQueue&Q)//构造一个空队列{Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));//队头结点if(!Q.front)exit(OVERFLOW);Q.front-next=NULL;returnOK;}StatusQueueEmpty(constLinkQueue&Q)//若队列为空，则返回TRUE，否则返回FALSE{if(Q.rear==Q.front)returnTRUE;returnFALSE;}StatusEnQueue(LinkQueue&Q,QElemTypee)//插入元素e为Q的新队尾元素{QueuePtrp=(QueuePtr)malloc(sizeof(QNode));if(!p)exit(OVERFLOW);p-data=e;p-next=NULL;Q.rear-next=p;Q.rear=p;returnOK;}StatusDeQueue(LinkQueue&Q,QElemType&e)//若队列不空，则删除Q的队头元素，用e返回其值，并返回OK;{if(Q.front==Q.rear){returnERROR;//队空}QueuePtrp=Q.front-next;e=p-data;Q.front-next=p-next;if(Q.rear==p)Q.rear=Q.front;free(p);returnOK;}/*--------------------------------------------------------------*///构造空树voidinit_cstree(CSNode*T){T-firstchild=NULL;T-nextsibling=NULL;}//创建一棵树StatusCreateTree(CSTree&T)//创建一棵树{LinkQueueQ;InitQueue(Q);//构造一个空队列charbuffChild[10];//用于存放孩子们的缓存memset(buffChild,0,10);//初始化缓存数组，置为NULLprintf(请输入树的根结点（字符,以#代表空）:\n);scanf_s(%c,&buffChild[0],10);if(buffChild[0]!='#'){T=(CSTree)malloc(sizeof(CSNode));//为根结点开辟一个空间if(!T)exit(OVERFLOW);//开辟失败，终止程序T-data=buffChild[0];T-nextsibling=NULL;//根结点无兄弟EnQueue(Q,T);//根结点入队while(!QueueEmpty(Q)){QElemTypee;DeQueue(Q,e);//结点出队//CSTreep=e;//用以指向队头结点printf(请按长幼顺序输入结点%c的孩子(字符,以#结束):\n,e-data);fflush(stdin);//清空输入流缓冲区的数据gets_s(buffChild);//scanf(%s,buffChild);if(buffChild[0]!='#')//有孩子{CSTreeq;q=(CSTree)malloc(sizeof(CSNode));//开辟孩子结点空间if(!q)exit(OVERFLOW);q-data=buffChild[0];//e-firstchild=q;//指向第一个孩子EnQueue(Q,q);//第一个孩子入队CSTreep=q;//指向刚入队的孩子for(size_ti=1;istrlen(buffChild)-1;++i)//孩子存在兄弟{q=(CSTree)malloc(sizeof(CSNode));//开辟孩子结点空间if(!q)exit(OVERFLOW);q-data=buffChild[i];//p-nextsibling=q;EnQueue(Q,q);p=q;//指向刚入队的孩子}p-nextsibling=NULL;}else//无孩子{e-firstchild=NULL;}}}else{T=NULL;//空树}returnOK;}//销毁树voidDestroyTree(CSTreeT){//树T存在，销毁树Tif(T)//树不空{if(T-firstchild)//左子树存在，即销毁以长子为结点的子树DestroyTree(T-firstchild);if(T-nextsibling)//右子树存在，即销毁以兄弟为结点的子树DestroyTree(T-nextsibling);free(T);//释放根结点T=NULL;}}//返回树的深度intTreeDepth(CSTreeT){intdep1=0,dep2=0,dep=0;if(NULL==T)dep=0;else{dep1=TreeDepth(T-firstchild);dep2=TreeDepth(T-nextsibling);dep=dep1+1dep2?dep1+1:dep2;}returndep;}//创建树CSTreeMaketree(TElemTypee,intn){inti;CSTreet,p;CSTreep1;va_listargptr;//argptr是存放变长信息的数组t=(CSTree)malloc(sizeof(CSNode));if(NULL==t)returnNULL;t-data=e;//根节点的值为et-firstchild=t-nextsibling=NULL;if(n=0)returnt;//若无子树，则返回根节点va_start(argptr,n);p=va_arg(argptr,CSTree);t-firstchild=p;p1=p;for(i=1;in;i++){//将n课树作为根节点的子树插入p=va_arg(argptr,CSTree);p1-nextsibling=p;p1=p;}va_end(argptr);returnt;}//判空StatusEmpty(CSTreeT){//树T存在，空树返回TRUE，否则返回FALSEif(T)returnTRUE;elsereturnFALSE;}//插入第i棵子树StatusInsertChild(CSTreeT,inti,CSTreec){intj;if(NULL==T||i1)returnERROR;if(1==i){//c插入为T的第1棵子树c-nextsibling=T-firstchild;T-firstchild=c;//c成为T的第i棵子树}else{T=T-firstchild;for(j=2;T!=NULL&&ji;j++)T=T-nextsibling;//寻找插入位置if(j==i){c-nextsibling=T-nextsibling;T-nextsibling=c;}elsereturnERROR;//参数i过大}returnOK;}//查找T的结点e并返回其指针CSNode*Search(CSTreeT,TElemTypee){CSNode*result=NULL;if(NULL==T)returnNULL;if(T-data==e)returnT;if((result=Search(T-firstchild,e))!=NULL)returnresult;returnSearch(T-nextsibling,e);}StatusLevelOrderTraverse(constCSTree&T){//层次遍历树LinkQueueQ;InitQueue(Q);if(T){printf(%c,T-data);//访问结点EnQueue(Q,T);//根结点排队while(!QueueEmpty(Q)){QElemTypee,p;DeQueue(Q,e);p=e-firstchild;whil