数据结构实验学期总结
摘要：
本学期我完成的主要实验任务有：裴波那锲序列、约瑟夫环、表达式求值、赫夫曼编码
文档内容：本学期以来，我所完成的所有实验及其总结，分别包括实验名称、实验目的及要求、实验主要内容、实验结果结论、实验分析，还有我对该课程学习总结和建议。
关键字：
数据结构实验总结数组链表栈二叉树
实验一
实验名称：裴波那锲序列
实验目的及要求：
1. 熟悉开发工具的编程环境。
2. 体会算法和程序的不同。
3. 学习用不同算法实现同一程序功能，并能熟练编程实现。
4. 学习分析算法。对比不同算法实现的效率有何不同，所占空间有何
不同。对比不同算法的优点和缺点
实验主要内容：
概要设计和存储结构
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) 程序中未曾使用线性表或链表结构
主要算法
int f(int m,int k){ if(m<=k-1) return 0;
else if(m==k+1||m==k) return 1;
@ else return (2*f(m-1,k)-f(m-k-1,k)); } //f( )函数实现裴波那契序列
实验结果和结论
实验分析：
通过建立一个f( )函数，用递归的方式来实现第m 项输出的值，本次程序的设计因为采用了递归调用，所以速度相对比非递归要慢了些。
实验二
实验通过三组数据的测试，基本实现了实验要求的功能，经过几次的修改后，自己没有再发现什么bug 了，感觉还是很满意的
实验名称：约瑟夫环
实验目的及要求：
通过实习题的上机实践，帮助学生掌握线性表的基本操作在两种存储结构上算法的实现，特别是链表，实验以各类链表的操作和应用作为重点。
采用循环单链表作为存储结构，按照出列的顺序打印出各人的编号
实验主要内容：
概要设计和存储结构
分三个模块：自主定义的二个函数以及一个主函数
Creat函数目的在于建立一个循环链表
Count是实现本程序所要求的主要功能
而主函数main通过依次调用以上函数完成程序
Struct huan* creat (int n) 是用于构建一个单循环动态链表，通过malloc 开辟一个结构体结点，在main（）中通过由循环语句for将其连接成一个循环链表
struct huan{
int num;
int data;
struct huan *next;
}；定义的结构体形式
Struct huan* creat (int n) 创建一个单循环链表，目的用来存放人的位置及密码
void count(struct huan* head,int n) 实现约瑟夫环的功能 主要算法
struct huan* creat(int n)
{//创建一个单循环链表，目的用来存放人的位置及密码
struct huan* head;
if((head=(struct huan*)malloc(sizeof(struct huan)))==NULL) return NULL;
head->num=n;
//可以替换下一句head->data=rand()%100+1;密码随机产生
scanf("%d",&head->data);
return head;
}//creat
/*实现出列功能*/
void count(struct huan* head,int n)
{
struct huan *p2=head,*p1;
for(;p2->next!=head;p2=p2->next);
p1=p2->next;
int code;
printf("\n请输入起始密码:\n");
scanf("%d",&code);
int pas=code%n;
printf("出列次序:\n位置密码\n");
while(n>1)
{if(pas==0) pas=n;
for(int i=1;inext,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
实验结果和结论
实验要求完成的功能已经全部完成了，但是对于手动输入密码和随机产生密码这两种功能没能够通过程序选择来完成
实验分析：
可以看出这一题是考查单链表的应用，而且这一题中的循环单链表是不需要“头结点”的，要注意空表和非空表的界限。程序运行后要求用户指定初始报数上界值，人数及各人的密码。可先设n≤30。
实验三
