数据结构实习报告

数据结构实习报告班级 XXXXXX 学生姓名 XXXXXX 学号XXXX 指导教师 XXXXXX日期2012年11月10日报告简介：整篇实习报告主要分为三部分：实习一，实习二以及实习困惑。其中每个实习报告涉及6个部分：需求分析，设计，调试分析，用户手册，测试结果，源程序清单。具体报告内容如下：实习一：一元稀疏多项式运算器的设计1、 需求分析【问题描述】设计一个一元稀疏多项式简单计算器。【基本要求】输入并建立两个多项式；多项式a与b相加，建立和多项式c；多项式a与b相减，建立和多项式d；输出多项式a,b,c,d。输出格式：比如多项式a为：A(x)二clxel+c2xe2+…+cmxem，其中，ci和ei分别为第i项的系数和指数，且各项按指数的升幂排列，即0WelVe2V・・・Vem。2、 设计(1)设计思想存储结构：以带头结点的单链表存储多项式。算法主要思想：•首先定义单链表中每个结点的结构体类型，设计能够生成多项式链表的函数，这个函数的功能是可以根据给定的多项式来创建存储它的单链表。•然后需要设计两个多项式相加的函数与两个多项式相减的函数。•要检验多项式的运算结果以及初始的多项式链表正确与否，需要将其打印输出，故还需要设计打印输出函数。•主函数的设计：依次调用多项式链表生成的函数、多项式相加减的函数，最后将结果打印输出。(2)概要设计整个算法需要设计五个函数，分别是：多项式链表生成的函数、两个多项式相加的函数、两个多项式相减的函数、打印输出的函数以及主函数。在设计各个函数之前，要定义单链表结点的结构体类型。每个结点应该包括指数code、系数exp和指向下一个结点的指针next。

多项式链表生成的函数：函数的返回值应该为定义的结构体类型，不需要设置参数。函数内部，需要有多项式指数和系数的输入，直至输入的系数为零时结束，将每一对输入的指数和系数保存到新结点中，并将结点插入到链表中。输入结束后，就生成了所要求的多项式链表。两个多项式相加的函数：函数的返回值应该为定义的结构体类型，参数包括：两个多项式链表的头指针。函数的功能是当两个链表中的两个结点的指数相等时，将二者的系数相加，存入新的结点中，并将此结点插入到新的多项式链表中，当指数不相等时，将指数较小的一项复制成新结点插入到新的多项式链表中。多项式相减的函数与相加函数类似，这里不再赘述。打印输出函数：设计成无返回值类型，参数为所需打印输出的单链表的头指针，这里需要注意输出格式，要分情况讨论。主函数：调用两次创建多项式链表的函数，创建头结点分别为heada,headb的两个多项式链表，然后依次调用多项式相加、多项式相减的函数，将结果存入头结点为headc，headd的多项式链表中。最后将初始的两条单链表以及新生成的链表打印输出。3）详细设计主函数3、3、调试分析生成两个多］将两个多项（将两个多项（将初始的两将计算结果项式链表式相加式相减条链表打印输出打印输出★问题的解决：在程序设计过程中遇到了很多的错误，一元稀疏多项式运算器的设计，第一次上机打印输出函数的设计并未完成，好在第二次上机时有老师的帮助，得以顺利完成。在调试过程中，主要的问题体现在打印输出函数中输出格式的设计。★回顾讨论与分析：刚开始我在打印输出函数中，没有分情况讨论输出格式，输出语句为：printf("%dx%d+",pl->code,pl->exp)，输出的多项式最后一项后仍跟着一个“+”，显然这样的格式并不是我们想要的，后来经过思考后调整了输出格式，分了两种情况，如下：出语句为：voidlistprintf(structpnode*head){structpnode*p,*p1;p=head;while(p!=NULL){p1=p;p=p->next;if(pl->next!二NULL&&p->code>0)//情况一：非末尾元素printf("%dx%d+",pl->code,pl->exp);elseprintf("%dx%d",pl->code,pl->exp);//情况二：当输出最后一个元素时}printf("\n");}经过调整，就得到了我们所需要的输出格式如图：1x1+1x1®^1x1+2x1^9+1x2001x1-1x28^Pr-ess：an9keytocontinue其中的测试数据为：(x+xl00)+(xl00+x200)=(x+2xl00+x200)次要问题是：两个多项式相减函数的设计中，当两个结点的指数不相等时，将指数较小的结点复制成一个新的结点插入到链表C中，这时如果和多项式相加时编写的语句一样就会出现问题，应该注意符号的正负，具体的程序设计将在源程序清单中给出。★时间复杂度的分析：创建多项式链表相加、减函数打印输出函数整体时间复杂度O(n)O(n)O(n)O(n)★改进设想：(1)在上机实习期间，时间比较紧，只是单纯的将一元稀疏多项式的运算器用算法实现，并没有设计，将其设计出可视化的界面。(2)在C程序的设计中，我将全部的程序写在同一个界面上，其实可以讲涉及到需要调用的函数写在头文件中，主函数在调用时，只许将此头文件包括进来即可，这样阅读起来方便简洁。★经验与体会：一个良好的算法需要满足5个目标：正确性、可读性、健壮性、高时间效率、高空间效率。程序设计过程中，在健壮性的处理上尚不能得心应手，常常会考虑不充分，造成不良后果，这说明仅仅掌握书本上的知识是远远不够的。此外，我发现了自己一个很严重的问题，即便是取得了计算机二、三级证书，在程序的设计实现上能力还很匮乏。我所擅长的更大程度上是阅读程序，编写单个的函数，在遇到一个涉及到多个函数的调用，多个功能的算法时，往往思维不够全面，分析不够到位，这就让我不得不边写程序边调整思路，后果就是效率低下，这让我十分苦恼。4、 用户手册因为整个算法均采用c语言设计，所以操作简单易懂，现在就具体说明：在创建多项式链表的函数中采用的输入语句为：scanf("%d,%d",&n,&m)，所以输入的系数与指数需要以“，”隔开。在输入过程中，输入结束时，将系数输入“0”,就完成了一个多项式链表的创建。接着就依次输入下一个多项式的系数和指数，同样以系数为“0”结束。按要求输入后整个程序就会运行，依次打印出初始的两条链表以及运算后的两条链表中的元素。示例：(x+x100)+(x100+x200)=(x+2x100+x200)输入：1,11,1000,01,1001,2000,05、 测试结果测试数据如下：(1)(x+x100)+(x100+x200)=(x+2x100+x200)(x+x100)-(x100+x200)=(x-x200)LA杀数n祁涓魏nilJ认索数麻咄认索数谪酣认索藪谪酣认索藪屏呵认索数需时ixl+1x10Sixl0B+lx2Gfi1x1+3xlE)B+lx26fjlxl-lx26fj^rcssan^pIce5,t;ocontinue旨数ml,100旨数嗣胡a®in：l,16£t□®ml,200疥数!n過詡2)(1+x+x2+x3+x4+x5)+(-x3-x4)=(1+x+x2+x5)(1+x+x2+x3+x4+x5)-(-x3-x4)=(1+x+x2+2x3+2x4+x5)凶n~nJo■>4凶n~nJo■>401-0*-1* 0:-0数数数数数数数数数数匕吕已日已日已日匕日匕日匕日匕日匕日匕曰_-<-•_-<-•■扌■扌■扌.nnnnnnnnnn示弄弄弄牙牙云云云二Jn数数数数数数数数数数奈系系系系系系系系系TAAAAAAAAkMIXMIXMIXMIXMIX^\.亠^\.亠^\.亠0*121*>-11Hu3)(2x+5x8-3x11)+(7-5x8+11x9)=(7+2x+11x9-3x11)(2x+5x8-3x11)-(7-5x8+11x9)=(-7+2x+10x8-11x9-3x11)1^-894QD4y444回43一7呂1一呼悶厂因m:m-.il吶蝕数数数数数数数

可日匕日匕臼匕臼匕臼匕臼匕日匕日T.T;T:「■■r.T.T.T.■扌1-nnnnnnnnl1匚*匚tr-1r-1匚t匚l匚Ic-X数数数数数数数数4亲系系系系系系系5X6、 源程序清单#include<stdio.h>#include<malloc.h>structpnode/*定义结点的结构体*/{intcode;/*系数*/intexp;//指数structpnode*next;};structpnode*poly()/*生成多项式链表的函数*/{structpnode*head,*r,*s;intm,n;head=(struetpnode*)malloc(sizeof(struetpnode));/*建立一个头结点*/r=head;printf("输入系数n和指数m:");scanf("%d,%d",&n,&m);while(n!=0){s=(struetpnode*)malloc(sizeof(struetpnode));/*建立结点*/s->code=n;s->exp=m;r->next二s;/*把结点s连接到r所指向的头结点之后，然后把指针r后移，r指向s结点*/r=s;printf("输入系数n和指数m");seanf("%d,%d",&n,&m);}r->next=NULL;/*删除掉头结点*/head=head->next;return(head);}structpnode*padd(heada,headb)/*两个多项式相加的函数*/structpnode*heada,*headb;{structpnode*headc,*p,*q,*r,*s;intx;p=heada;q=headb;headc=(structpnode*)malloc(sizeof(structpnode));r=headc;while(p!=NULL&&q!=NULL){if(p->exp==q->exp)/*两结点的指数相等时，将两节点的系数相加，然后存入结点S中*/{x=p->code+q->code;if(x!=0){S=(Structpnode*)malloc(Sizeof(Structpnode));S->code=x;S->exp=p->exp;r->next=S;r=S;}p=p->next;q=q->next;}else/*当两个结点的指数不相等时，将指数较小的结点复制成一个新的结点插入到C中*/if(p->exp>q->exp){s=(structpnode*)malloc(sizeof(structpnode));s->code=q->code;s->exp=q->exp;r->next=s;r=s;q=q->next;}else{s=(structpnode*)malloc(sizeof(structpnode));s->code=p->code;s->exp=p->exp;r->next=s;r=s;p=p->next;}}while(p!=NULL){s=(structpnode*)malloc(sizeof(structpnode));s->code=p->code;s->exp=p->exp;r->next=s;r=s;p=p->next;}while(q!=NULL){s=(structpnode*)malloc(sizeof(structpnode));s->code=q->code;s->exp=q->exp;r->next=s;r=s;q=q->next;}r->next=NULL;s=headc;headc=headc->next;free(s);return(headc);}structpnode*psubtract(heada,headb)/*两个多项式相减的函数*/structpnode*heada,*headb;{structpnode*headd,*p,*q,*r,*s;intx;p=heada;q=headb;headd=(structpnode*)malloc(sizeof(structpnode));r=headd;while(p!=NULL&&q!=NULL){if(p->exp==q->exp)/*两结点的指数相等时，将两节点的系数相减，然后存入结点S中*/{x=p->code-q->code;if(x!=0){s=(structpnode*)malloc(sizeof(structpnode));s->code=x;s->exp=p->exp;r->next=s;r=s;}p=p->next;q=q->next;}else/*当两个结点的指数不相等时，将指数较小的结点复制成一个新的结点插入到C中*/if(p->exp>q->exp){s=(structpnode*)malloc(sizeof(structpnode));s->code=-(q->code);s->exp=q->exp;r->next=s;r=s;q=q->next;}else{s=(structpnode*)malloc(sizeof(structpnode));s->code=p->code;s->exp=p->exp;r->next=s;r=s;p=p->next;}}while(p!=NULL){s=(structpnode*)malloc(sizeof(structpnode));s->code=p->code;s->exp=p->exp;r->next=s;r=s;p=p->next;}while(q!=NULL){s=(structpnode*)malloc(sizeof(structpnode));s->code=-(q->code);s->exp=q->exp;r->next=s;r=s;q=q->next;}r->next=NULL;s=headd;headd=headd->next;free(s);return(headd);}voidlistprintf(structpnode*head){structpnode*p,*p1;p=head;while(p!=NULL){p1=p;p=p->next;if(p1->next!=NULL&&p->code>0)printf("%dx%d+",p1->code,p1->exp);elseprintf("%dx%d",p1->code,p1->exp);}printf("\n");}main(){structpnode*heada,*headb,*headc,*headd;heada=poly();headb=poly();headc=padd(heada,headb);headd=psubtract(heada,headb);listprintf(heada);listprintf(headb);listprintf(headc);listprintf(headd);}实习二：唯一的确定一棵二叉树1、需求分析【问题描述】如果给出了遍历二叉树的前序序列和中序序列，则可以构造出唯一的一棵二叉树。试编写实现上述功能的程序。【基本要求】已知一棵二叉树的前序和中序序列，试设计完成下列任务的一个算法：（1） 构造一棵二叉树；（2） 证明构造正确（即分别以前序和中序遍历该树，将得到的结果与给出的序列进行比较）。（3） 对该二叉树进行后序遍历，输出后序遍历序列。（4）用凹入法输出该二叉树。2、设计（1）设计思想存储结构：以两个数组分别存储给定的前序遍历序列和中序遍历序列。而所构造的二叉树则以二叉链存储。算法主要思想：定义二叉链中结点的结构体类型。设计根据前序遍历序列、中序遍历序列构造二叉树的函数。设计后序遍历二叉树的函数设计凹入法打印输出二叉树的函数在主函数中定义两个数组，用来存放中序遍历、前序遍历序列的字符串主函数依次调用两次字符串输入函数，构造二叉树的函数，后序遍历函数，凹入法打印输出函数。（2）概要设计整个算法需要设计四个函数，分别是：根据前序遍历序列、中序遍历序列构造二叉树的函数、后序遍历二叉树的函数、凹入法打印输出的函数以及主函数。在设计各个函数之前，要定义二叉链中结点的结构体类型，存储遍历序列字符串的数组。根据前序遍历序列和中序遍历序列构造二叉树的函数：考虑算法的健壮性，要分情况讨论，当给出存放遍历序列的数组中有一个为空或者都为空时，就不能成功构造出二叉树，只有当二者都非空时才能进一步运行。后序遍历二叉树的函数：采用递归遍历的方式。凹入法打印输出的函数：这个函数课本上就有，在此我没有单独设计。主函数：将两个遍历序列字符串分别存入两个数组中，调用根据前序遍历序列、中序遍历序列构造二叉树的函数，构造完成二叉树后，调用后序遍历函数，将后序遍历序列输出，随后调用凹入法打印输出函数，将构造的二叉树打印输出。拓展内容：因为树和二叉树那一章节中，作业中涉及到求二叉树的深度及叶子结点数目的算法，所以在这次实习唯一确定一棵二叉树中，我在整体中加入了这两部分，希望能更好的掌握与二叉树相关的算法。（3）详细设计略（因为算法框架图太麻烦了，时间紧啊）3、调试分析★问题的解决：在实习二中我遇到的主要问题是凹入法打印输出函数的设计，别看书上已经有了这个函数，事实上我在应用上没有那么得心应手。将此函数的参数做相应改变后，我就在主函数中进行了调用，但是由于输出格式的问题，在开始阶段测试数据构造的二叉树的头结点A总是不能显示，最后经过多次修改输出格式，终于解决了这个问题。★回顾讨论与分析：在最初的凹入法打印输出函数中，输出格式不对，调试过程中发现输出结果如下图：显然这样的输出结果中，头结点A并没有正确输出，不满足算法的正确性。将输出格式进行调整，就得到了我们所需要的输出格式如图：★改进设想：两次上机实习，第二次实习任务并没有按时完成，只是在课后完成的，由于后期备考时间比较紧，所以这个算法的设计比较粗糙，此外拓展内容也没有完成。只是额外加上了求叶子结点和二叉树深度的算法。★经验与体会：除了有关算法的相关体会外，我还发现了一个问题，同学们在面对实习任务给出的算法要求时，大多感觉无从下手，或相互观望，或干脆放弃，只有少数同学能够坚持摸索。可能我比较幸运，只是按部就班的设计算法，后来能够得到老师的指点，最终完成整个算法。我知道不可能一蹴而就，在设计和调试过程中也算是吃了不少苦头，尤其在调整打印输出格式时尤为明显。这在一定程度上说明，我在格式控制这个知识点上掌握的不太理想。以后应该对这个知识点巩固加强。4、用户手册具体说明使用方法如下：1）在输入前序遍历序列、中序遍历序列的字符串时，只需要将给定的字符连续输入即可，输入完成一个后，回车，接着输入另一个。2）按要求输入后整个程序就会运行，显示的结果依次为：后序遍历序列，凹入法表示的二叉树，叶结点个数以及二叉树的深度。5、测试结果

测试数据实例一】前序序列为ABDEGCFHIJ，中序序列为DBGEAHFIJC。正确的后序遍历序列应该是：DGEBHJIFCA，构造的正确二叉树结构应该如下图：设计算法的运行结果如下图：6、 源程序清单#include<stdio.h>#include<malloc.h>#include<string.h>voidexit(int);#defineMAX100typedefintDataType;typedefstructnode//定义结点的结构体类型{chard;structnode*lchild,*rchild;}Tnode;voidMK(charin[],charis,charie,charpre[],charpres,charpree,Tnode**r)//根据前序、中序遍历序列构造二叉树的函数{inti;if(is>ie||pres>pree)//当存放遍历序列的数组有一个或两个为空时，构造失败*r=NULL;else{*r=malloc(sizeof(Tnode));(*r)->d=pre[pres];for(i=is;i<=ie;i++){if(in[i]==pre[pres]){MK(in,is,i-1,pre,pres+1,pres+i-is,&(*r)->lchild);MK(in,i+1,ie,pre,pres+i-is+1,pree,&(*r)->rchild);break;}if(i>ie){printf("输入错误!\n");exit(1);}}}}voidpostorder(Tnode*r)//后续遍历二叉树{if(r){postorder(r->lchild);postorder(r->rchild);printf("%c",r->d);}}intleaf(Tnode*r)//函数功能：求所构造的二叉树叶结点数目{if(r==NULL)return0;elseif(r->lchild==NULL&&r->rchild==NULL)return1;elsereturnleaf(r->lchild)+leaf(r->rchild);}intheight(Tnode*r)//函数功能：求所构造的二叉树的高度{inth1,h2;if(r==NULL)return0;else{h1=height(r->lchild);h2=height(r->rchild);return1+(h1>h2?h1:h2);}}voidPrintBiTree(Tnode*r,intn)//逆时针旋转90度打印二叉树r,n为缩进层数，初始值为0