文档介绍：摘要:本学期我完成的主要实验任务有:裴波那锲序列、约瑟夫环、表达式求值、赫夫曼编码文档内容:本学期以来,我所完成的所有实验及其总结,分别包括实验名称、实验目的及要求、实验主要内容、实验结果结论、实验分析,还有我对该课程学****总结和建议。关键字:数据结构实验总结数组链表栈二叉树实验一实验名称:裴波那锲序列实验目的及要求:1. 熟悉开发工具的编程环境。2. 体会算法和程序的不同。3. 学****用不同算法实现同一程序功能,并能熟练编程实现。。对比不同算法实现的效率有何不同,所占空间有何不同。对比不同算法的优点和缺点实验主要内容:概要设计和存储结构K阶(k>=2)裴波那契序列的第m项值假设为sum,则:sum(m)=sum(m-1)+sum(m-2)+……+sum(m-k)=sum(m-1)+sum(m-2)+……+sum(m-k)+sum(m-k-1)-sum(m-k-1)=sum(m-1)+[sum(m-2)+……+sum(m-k)+sum(m-k-1)]-sum(m-k-1)=2*sum(m-1)-sum(m-k-1)所以最后return返回的是2*f(m-1,k)-f(m-k-1,k),如此便实现了裴波那契序列第m项的计算。下面程序段中@语句的时间复杂度为:O(sum)=2(m-k)(m>k)程序中未曾使用线性表或链表结构主要算法intf(intm,intk){if(m<=k-1)return0; elseif(m==k+1||m==k)return1;@ elsereturn(2*f(m-1,k)-f(m-k-1,k));}//f()函数实现裴波那契序列实验结果和结论实验通过三组数据的测试,基本实现了实验要求的功能,经过几次的修改后,自己没有再发现什么bug了,感觉还是很满意的实验分析:通过建立一个f()函数,用递归的方式来实现第m项输出的值,本次程序的设计因为采用了递归调用,所以速度相对比非递归要慢了些。实验二实验名称:约瑟夫环实验目的及要求:通过实****题的上机实践,帮助学生掌握线性表的基本操作在两种存储结构上算法的实现,特别是链表,实验以各类链表的操作和应用作为重点。采用循环单链表作为存储结构,按照出列的顺序打印出各人的编号实验主要内容:概要设计和存储结构分三个模块:自主定义的二个函数以及一个主函数Creat函数目的在于建立一个循环链表Count是实现本程序所要求的主要功能而主函数main通过依次调用以上函数完成程序Structhuan*creat(intn)是用于构建一个单循环动态链表,通过malloc开辟一个结构体结点,在main()中通过由循环语句for将其连接成一个循环链表structhuan{ intnum; intdata; structhuan*next;};定义的结构体形式Structhuan*creat(intn)创建一个单循环链表,目的用来存放人的位置及密码voidcount(structhuan*head,intn)实现约瑟夫环的功能主要算法structhuan*creat(intn){//创建一个单循环链表,目的用来存放人的位置及密码structhuan*head;if((head=(structhuan*)malloc(sizeof(structhuan)))==NULL)returnNULL;head->num=n;//可以替换下一句head->data=rand()%100+1;密码随机产生scanf("%d",&head->data);returnhead;}//creat/*实现出列功能*/voidcount(structhuan*head,intn){structhuan*p2=head,*p1;for(;p2->next!=head;p2=p2->next);p1=p2->next;intcode;printf("\n请输入起始密码:\n");scanf("%d",&code);intpas=code%n;printf("出列次序:\n位置密码\n");while(n>1){if(pas==0)pas=n;for(inti=1;i<pas;p2=p1,p1=p1->next,i++);p2->next=p1->next;printf("%d\t%d\n",p1->num,p1->data);code=p1->data;free(p1);p1=p2->next;n--;pas=code%n;}printf("%d\t%d\n",p1->num,p1->data);free(p1);}//count实验结果和结论实验要求完成的功能已经全部完成了,但是对于手动输入密码和随机产生密码这两种功能没能够通过程序选择来完成实验分析:可以看出这一题是考查单链表的应用,而且这一题中的循环单链表