数据结构与算法实验指导书

数据结构与算法实验指导书山东师范大学数学科学学院实验大纲序号实验名称内容提要每组人数实验时数实验要求实验类别备注1抽象数据类型的实现复数的加、减、乘、除等运算13必做设计2线性表的基本操作在线性表中插入、删除、查找结点13必做设计3栈和队列及其应用利用栈或队列解决实际问题16必做设计4树和二叉树的建立及应用二叉树的建立、插入、删除、周游19必做设计5查找算法的实现利用检索算法进行查找16必做设计6内排序算法的实现用某个排序算法进行排序13必做设计7图的建立及应用图的建立等13必做设计8综合实验学生管理、订票系统等13必做综合实验一：抽象数据类型的实现一、实验目的：1、了解抽象数据类型的表示和实现方法2、会用C语言中已存在的数据类型来说明新的结构。3、能用已实现的操作来组合新的操作。4、熟悉C语言的程序设计二、实验内容复数的加、减、乘、除等运算三、实验指导1、由于C语言中没有复数数据类型，所以要定义一个结构体类型主要成员是复数的实部和虚部。structcomplex{doublereal;doubleimage;};typedefinestructcomplexfcomplex;2、对于复数的每一个运算用一个函数实现。fcomplexadd(fcomplexz1,fcomplexz2){fcomplexz;z.real=z1.real+z2.real;z.image=z1.image+z2.image;return(z);}fcomplexsub(fcomplexz1,fcomplexz2){fcomplexz;z.real=z1.real-z2.real;z.image=z1.image-z2.image;return(z);}fcomplexmul(fcomplexz1,fcomplexz2){fcomplexz;z.real=z1.real*z2.real-z1.image*z2.image;z.image=z1.real*z2.image+z1.image*z2.real;return(z);}fcomplexdiv(fcomplexz1,fcomplexz2){fcomplexz;z.real=(z1.real*z2.real+z1.image*z2.image)/(z2.real*z2.real+z2.image*z2.image);z.image=(z1.image*z2.real+z1.real*z2.image)/(z2.real*z2.real+z2.image*z2.image);return(z);}思考：如何实现求复数的模运算？3、将复数的定义和运算保存在一个名为COMPLEX.H的文件中。4、主函数主要实现运算的选择和数据的输入和输出。voidmain(){intn;fcomplexz,z1,z2;printf(请输入第一个复数的实部和虚部:);scanf(%lf,%lf,&z1.real,&z1.image);printf(请输入第二个复数的实部和虚部:);scanf(%lf,%lf,&z2.real,&z2.image);printf(请选择要进行的运算(1-4)\n);printf(1.加法\n);printf(2.减法\n);printf(3.乘法\n);printf(4.除法\n);do{scanf(%d,&n);}while(n1||n4);switch(n){case1:z=add(z1,z2);break;case2:z=sub(z1,z2);break;case3:z=mul(z1,z2);break;case4:z=div(z1,z2);break;}printf(z=%lf+i%lf\n,z.real,z.image);}实验二线性表的基本操作一、实验目的：1、掌握线性表的两种存储结构2、掌握线性表在两种存储结构上建立、插入、删除、查找结点的基本操作3、会利用线性表解决实际问题二、实验内容设有n个人围坐在一个圆桌周围，从第s个人开始报数，数到第m个人出列，然后从出列的下一个人重新开始报数，数到第m的人又出列。。。。。如此反复直到所有的人全部出列为止。三、实验指导1．定义数据结构如下：#defineFALSE0#defineTRUE1typedefintDataType;/*定义元素类型为整型，也可定义为其他类型*/structNode;/*单链表结点类型*/typedefstructNode*PNode;/结点指针类型*/structNode/*单链表结点结构*/{DataTypeinfo;PNodelink;};typedefstructNode*LinkList;typedefLinkList*PLinkList;2．初始化过程intinit_clist(PLinkListpclist,intn)/*用1，2，……，n为*pclist所示的循环表初始化*/{PNodep,q;inti;q=(PNode)malloc(sizeof(structNode));if(q==NULL)return(FALSE);*pclist=q;q-info=1;q-link=q;if(n==1)return(TRUE);for(i=2;in+1;i++){p=(PNode)malloc(sizeof(structNode));if(p==NULL)return(FALSE);p-info=i;p-link=q-link;q-link=p;q=p;}return(TRUE);}3．主要程序voidjosephus_clist(PLinkListpclist,ints,intm){PNodep,pre;inti;p=*pclist;/*找第s个元素*/if(s==1){pre=p;p=p-link;while(p!=*pclist){pre=p;p=p-link;}}elsefor(i=1;is;i++){pre=p;p=p-link;}while(p!=p-link)/*当链表中结点个数大于1时*/{for(i=1;im;i++)/*找第m个结点*/{pre=p;p=p-link;}printf(“outelement:%d\n”,p-info);/*输出该结点*/if(*pclist==p)/*该结点是第一个结点时，删除时需特殊处理一下*/*pclist=p-link;pre-link=p-link;/*删除该结点*/free(p);p=pre-link;}printf(“outelement:%d\n”,p-info);/*输出最后一个结点*/*pclist=NULL;free(p);}4．主函数voidmain(){LinkListjos_clist;intn,s,m;/*输入所需各参数的值*/do{printf(“\npleaseinputthevaluesofn=“);scanf(“%d”,&n);}while(n1);do{printf(“pleaseinputthevaluesofs=“);scanf(“%d”,&s);}while(s1);do{printf(“pleaseinputthevaluesofm=“);scanf(“%d”,&m);}while(m1);if(init_clist(&jos_clist,n))josephus_clist(&jos_clist,s,m);elseprintf(“Outofspace!\n”);}实验三栈和队列及其应用一、实验目的1、掌握栈和队列的存储结构及在两种存储结构上的基本操作2、会利用栈和队列解决实际问题二、实验内容1、八皇后问题2、农夫过河问题三、实验指导实验四树和二叉树的建立及应用一、实验目的：1、掌握树特别是二叉树的建立、插入、删除、周游等算法2、掌握二叉树的存储方法3、会利用树结构解决实际问题二、实验内容1、用先序序列生成二叉树；2、给出先序遍历,中序遍历和后序遍历各项操作结果。3、给出二叉树的高度。4、给出二叉树的叶子数。5、二叉树的每层结点数。6、查找二叉树的是否存在结点x。三、实验指导实验五查找算法的实现一、实验目的：1、掌握字典的存储结构2、掌握字典的检索算法3、会利用字典结构解决实际问题二、实验内容根据学生的学号，查找某个学生的信息三、实验指导1、输入下面程序#includestdio.htypedefstruct{intnum;charname[10];charsex;floatscore;}DicElement;typedefstruct{intm;DicElement*element;}HashDictionary;inth(intkey){returnkey%13;}HashDictionary*createEmptyDictionary(intm){inti;HashDictionary*phd=(HashDictionary*)malloc(sizeof(HashDictionary));if(phd!=NULL){phd-element=(DicElement*)malloc(sizeof(DicElement)*m);if(phd-element){phd-m=m;for(i=0;im;i++)phd-element[i].num=0;/*初始化*/return(phd);}elsefree(phd);}printf(Outofspace!!\n);/*存储分配失败*/returnNULL;}intlinearInsert(HashDictionary*phash,DicElementele){intposition;if(linearSearch(phash,ele.num,&position)==1)/*散列表中已有关键码为key的结点*/printf(Find\n);elseif(position!=-1)phash-element[position]=ele;/*插入结点*/elsereturn(0);/*散列表溢出*/return(1);}intlinearSearch(HashDictionary*phash,intnum,int*position){intd,inc;d=h(num);/*d为散列地址，散列函数为h(key)*/for(inc=0;incphash-m;inc++){if(phash-element[d].num==num){*position=d;/*检索成功*/return(1);}elseif(phash-element[d].num==0){*position=d;/*检索失败，找到插入位置*/return(0);}d=(d+1)%phash-m;}*position=-1;/*散列表溢出*/return(0);}main(){HashDictionary*phd;intm,i,num,p;DicElementelem;phd=createEmptyDictionary(100);printf(inputthenumberofstudent);scanf(%d,&m);for(i=1;i=m;i++){printf(num,name,sexandscore);scanf(%d,&elem.num);scanf(%s,elem.name);fflush(stdin);scanf(%c,&elem.sex);scanf(%f,&elem.score);linearInsert(phd,elem);}printf(inputthenumtosearch);scanf(%d,&num);linearSearch(phd,num,&p);printf(%d,%s,%c,%f\n,phd-element[p].num,phd-element[p].name,phd-element[p].sex,phd-element[p].score);}实验六内排序算法的实现一、实验目