潍坊学院数据结构试验指导书

数据结构试验指导书王兆红徐翠霞潍坊学院2前言数据结构研究的是数据的各种逻辑结构，存储结构和相应运算的方法。实验是该课程教学必不可少的组成部分。通过上机实验，调试和运行已经学习到的算法，或开发新的算法，不仅能够加深理解和巩固所学的知识，而且更重要的是有助于提高学生根据实际问题分析，设计，开发和调试算法的实际能力和水平。本书共包括10个实验，依次为：线性表，约瑟夫环，栈与递归算法设计，串及其应用，数组与广义表，树及其应用，二叉树的建立及输出，图及其遍历，树表的查找，排序。涵盖了数据结构教学大纲的大部分内容，有些实验由两个参考程序组成，不同层次的学生可根据情况选作，其中每个参考程序都是由多个函数组成，实验学时较少的专业可以只完成几个主要函数的功能即可。当然，有条件的学生可全部完成，进行比较全面的实验训练。由于我们水平有限，加之时间仓促，错误和不当之处在所难免，敬请广大师生批评指正。王兆红徐翠霞2002．11．283目录实验一线性表实验二约瑟夫环实验三栈与递归算法设计实验四串及其应用实验五数组与广义表实验六树及其应用实验七二叉树的建立及输出实验八图及其遍历实验九树表的查找实验十排序4实验一线性表程序11、实验目的使学生熟练掌握单链线性表的基本操作2、实验内容设计程序完成一元稀疏多项式计算器的功能。用带表头结点的单链表存储多项式，设计一个一元稀疏多项式简单计算器，多项式的项数存放在头结点中。3、实验要求一元稀疏多项式简单计算器的基本功能是：（1）输入并建立多项式；（2）多项式的输出形式为整数序列：n，c1,e1，c2，e2，…，cn，en，其中n是多项式的项数，ci和ei分别是第i项的系数和指数，序列按指数降序排列；（3）多项式的输出形式为类数学表达式。例如：多项式-3x^8+6x^3-18的输出形式为-3x^8+6x^3-18，x^15+(-8)x^7-14的输出形式为x^15-8x^7-14。注意：系数值为1的非零次项的输出形式中略去系数1，如项1x8的输出形式为x^8，项-1x3的输出形式为-x^3（4）多项式a和b相加，建立多项式a+b；4、测试数据（1）（2x+5x^8-3.1x^11）+(7-5x^8+11x^9)=(-3.1x^11+11x^9+2x+7)（2）（1+x+x^2+x^3+x^4+x^5）+(-x^3-x^4)=(1+x+x^2+x^5)（3）（x+x^3）+(x-x^3)=0（4）（x+x^100）+(x^100+x^200)=(x+2x^100+x^200)(5)(x+x^2+x^3)+0=x+x^2+x^35、参考程序1：#defineNULL0#includestdio.htypedefstructLnode{/*结点类型*/5floatcoef;/*系数*/intexpn;/*指数*/structLnode*next;}Lnode,*link;typedeflinkpolynomail;/*用带表头结点的有序键表表示多项式*/polynomailpa,pb,pc;voidcreatpolyn(polynomailp,intm){/*输入m项的系数和指数,建立表示一元多项式的有序链表p*/inti;floatcoef;intexpn;polynomailtail,new;p-coef=m;p-expn=-1;tail=p;for(i=1;i=m;i++){new=(link)malloc(sizeof(Lnode));printf(pleaseinputcoefandexpn);scanf(%f,&coef);scanf(%d,&expn);new-coef=coef;new-expn=expn;new-next=NULL;tail-next=new;tail=new;}}voidaddpolyn(polynomailpa,polynomailpb){/*完成多项式相加运算,即:pc=pa+pb,并销毁一元多项式pb*/6intx,len;floaty;polynomailpre,p,q,u;pc=pa;len=0;pre=pa;p=pa-next;q=pb-next;while(p&&q){x=p-expn-q-expn;if(x0){pre=p;len++;p=p-next;}elseif(x==0){y=p-coef+q-coef;if(y!=0.0){p-coef=y;pre=p;len++;}else{pre-next=p-next;free(p);}p=pre-next;u=q;q=q-next;free(u);}else7{u=q-next;q-next=p;pre-next=q;pre=q;len++;q=u;}}if(q)pre-next=q;while(pre){pre=pre-next;if(pre)len++;}pc-coef=len;free(pb);}voidprintpoly(polynomailq){/*按类数学表达式的格式输出一元多项式的任意一项q*/if(q-expn==0)printf(%.0f,q-coef);elseif(q-expn==1){if(q-coef==1)printf(x);elseif(q-coef==-1)printf(-x);else{printf(%.0f,q-coef);printf(x);}}elseif(q-coef==1)printf(x^%d,q-expn);elseif(q-coef==-1)8printf(-x^%d,q-expn);elseprintf(%.0fx^%d,q-coef,q-expn);}voidprintpolyn(polynomailp){/*按类数学表达式的格式输出一元多项式p*/intn;polynomailq;q=p-next;n=0;while(q){n++;if(n==1)printpoly(q);elseif(q-coef0){printf(+);printpoly(q);}elseprintpoly(q);q=q-next;}/*while*/}/*printpolyn*/voidprint(polynomailp){/*按输出形式为整数序列：n，c1,e1，c2，e2，…，cn，en，打印输出一元多项式p*/polynomailq;printf(\n%.0f\n,p-coef);q=p-next;while(q){printf(%.0f,,q-coef);printf(%d\n,q-expn);q=q-next;}printf(\b\n);/*去掉最后一个逗号并换行*/}9main(){intm,n;printf(\npleaseinputn:);scanf(%d,&n);pa=(link)malloc(sizeof(Lnode));creatpolyn(pa,n);printf(\npa=);printpolyn(pa);printf(\npleaseinputm:);scanf(%d,&m);pb=(link)malloc(sizeof(Lnode));creatpolyn(pb,m);printf(\npb=);printpolyn(pb);addpolyn(pa,pb);printf(\npc=pa+pb=);printpolyn(pc);print(pc);getchar();getchar();}程序21、实验目的使学生熟练掌握单链线性表的基本操作2、实验内容该程序的功能是创建一个以正序排列的链表，链表节点为一个整形数据，插入一个元素，删除一个元素，均保持链表的正序。在执行完每个操作后将其输出。3、实验要求10所使用的单链表最好带有附加的头节点，这样所涉及的程序比较简洁。参考程序2#includestdio.h#includealloc.h#includestdlib.h#includestddef.h/*节点定义*/typedefintdatatype;typedefstructnode{datatypedata;structnode*next;}linklist;/*创建链表函数*/linklist*creatlist(){datatyped;linklist*p,*s,*head;head=malloc(sizeof(linklist));head-next=NULL;printf(pleaseinputtheinteger!(0---return));scanf(%d,&d);while(d!=0){s=malloc(sizeof(linklist));s-data=d;p=head;while(p-next!=NULL)if(p-next-datad)11p=p-next;elsebreak;s-next=p-next;p-next=s;printf(pleaseinputtheinteger!0----return);scanf(%d,&d);}returnhead;}/*输出链表中的所有元素*/voidoutput(head)linklist*head;{linklist*p;p=head-next;while(p!=NULL){printf(%6d,p-data);p=p-next;}printf(\n);}/*插入一个元素，标志链表的正序性。*/voidinsert(head,x)linklist*head;datatypex;{linklist*p,*s;12s=malloc(sizeof(linklist));s-data=x;p=head;while(p-next!=NULL)if(p-next-datax)p=p-next;elsebreak;s-next=p-next;p-next=s;printf(%dhasbeeninsertedintothelinklist!\n,x);}/*删除链表中的一个元素*/delete(head,x)linklist*head;datatypex;{linklist*p,*s;p=head;while(p-next!=NULL)if(p-next-data!=x)p=p-next;elsebreak;if(p-next!=NULL){s=p-next;p-next=s-next;printf(%dhasbeendeleted!\n,x);}elseprintf(%disn,tinthelinklist!\n,x);13}/*查找元素x,找到则返回其位置，否则返回空。*/linklist*search(head,x)linklist*head;datatypex;{linklist*p;p=head-next;while(p!=NULL)if(p-data!=x)p=p-next;elsebreak;returnp;}main(){linklist*head,*p;datatypex;inti=0;charchoice='';while(choice!='0'){printf(1-----createthelist!\n);i++;printf(2-----outputthelist!\n);i++;printf(3-----findaelementinthelist!\n);i++;14printf(4-----insertaelementtothelist!\n);i++;printf(5-----deleteaelementinthelist!\n);i++;printf(0------quit\n);printf(inputyourchoice(0-----5));scanf(%c,&choice);printf(\n);switch(choice){case'1':head=creatlist();break;case'2':outp