计算机与信息学院
（程序
设计
领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计
类课程）
实验
报告
软件系统测试报告下载sgs报告如何下载关于路面塌陷情况报告535n,sgs报告怎么下载竣工报告下载
课程名称：
算法与数据结构
姓 名：
系：
计算机科学与技术
专 业：
计算机科学与技术
年 级：
2009级
学 号：
091150022
指导教师：
宁正元
职 称：
2011 年 6 月 5 日
实验项目列
表
关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf
序号
实验项目名称
成绩
指导教师
1
编程实现Josephus问
题
快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题
宁正元
2
编程实现哈夫曼算法
宁正元
3
4
5
6
7
8
9
10
11
12
福建农林大学计算机与信息学院实验报告
数据结构的程序实现
一、 实验目的和要求
1.进一步了解数据结构的实验策略。
2.掌握动态结构的静态实现方法。
3.了解大批量数据的组织策略。
4.掌握数据结构在问题建模中的应用。
二、 实验内容
编程实现Josephus问题
问题描述：
有n个人围坐一圈并由1～n编号，从某个人（例如编号为k的人）开始报数，数到m的人出列；接着从出列的下一个人开始重新1~m报数，数到m的人又出列；如此反复地报数，直到最后一个人出列为止。试设计确定这n个人出列序列的程序。
分析
定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析
：首先对每一个人赋以一个序号值作为人出列时，将他的序号改为0作为出列的标志。
游戏情况如下：（假设n=6,k=1,m=2）
6个人围坐一圈的序号：1，2，3，4，5，6
人出列的序号：2，4，6，3，1
最后一个人出列的序号：5
三、 实验环境
Microsoft Visual C++
四、算法描述及实验步骤
解题思路：
这里假设k=1，定义一个循环链表，用其每个节点来记录1到n的数。从1数到m（每数一个就把指针移下一位），当数到m时就把对应的结点删除。直到循环链表里只剩下一个结点时就可以得到结果了。
要求用户输入的内容有：
（1）人的个数，也就是n的值；
（2）是出列的人的间隔，也就是m的值；
（3）所有人的序号要求存在链表中，需要定义一个指针，这里我们用数组来存放人的序号。
要求输出的内容是：
（1）离开人的序号；
（2）最后留下人的序号；
所以，根据上面分析输入输出参数，我们考虑出列的序号可以直接输出，这样可以使函数的复杂性。下面用Ｃ＋＋编写程序：
//输入参数：
//People为指向一个整形指针，指向保存人数组的首地址；
//n为人的个数；
//m为数人的个数；
int Josephus(int *People,int n,int m)
{
int i=-1,j=0,k=1;
//开始数人，只到留下一个人
while(1)
{
//数m个人
for(j=0;j
int Josephus(int *People,int n,int m);
void main()
{
int *allPeople,j,k,l;
cin>>j>>k;
if((allPeople= new int[j])!=NULL)
{
for(l=0;l=97&&xx[i][j]<=122)
a[xx[i][j]-97]++;
else
if(xx[i][j]==32)
a[26]++;
else
if(xx[i][j]==44)
a[27]++;
else
if(xx[i][j]==46)
a[28]++;
}
}
smax(int a[],int low,int high,int max[])
{ int mid,M[2],N[2];
mid=(high+low)/2;
if(high-low==1)
{if(a[low]a[N[0]])
{max[0]=M[0];
max[1]=N[0];
}
else
if(a[M[0]]>a[N[0]]&&a[M[0]]<=a[N[1]])
{max[0]=N[0];
max[1]=M[0];
}
else
if(a[M[0]]>a[N[0]]&&a[M[0]]>a[N[1]])
{max[0]=N[0];
max[1]=N[1];
}
}
}
bhtree(int a[])
{ int i,j;
int max[2];
int c[58]={0};
c[57]=4000;
l=0;
for(i=0;i<29;i++)
{ if(a[i]!=0)
{b[i].weight=a[i];
b[i].lchild=0;
b[i].rchild=0;
c[i]=a[i];
l++;
}
else
if(a[i]==0)
{b[i].weight=a[i];
b[i].lchild=0;
b[i].rchild=0;
c[i]=4000;
}
}
for(i=29;i<29+l-1;i++)
{smax(c,0,i-1,max);
c[max[0]]=4000;
c[max[1]]=4000;
b[i].weight=b[max[0]].weight+b[max[1]].weight;
b[i].lchild=max[0];
b[i].rchild=max[1];
b[max[0]].parent=i;
b[max[1]].parent=i;
c[i]=b[i].weight;
}
}
bma(int i,int j,int n,int M[])
{ int t;
t=b[n].parent;
if(n==29+l-2)
M[j]=2;
else
if(n==b[t].lchild)
{M[j]=0;
n=t;
bma(i,j+1,n,M);
}
else
if(n==b[t].rchild)
{M[j]=1;
n=t;
bma(i,j+1,n,M);
}
}
main()
{ int a[29]={0};
int i,j,n,k=0,p;
int m[29][10];
int M[10];
FILE *fp;
clrscr();
for(i=0;i<29;i++)
for(j=0;j<10;j++)
m[i][j]=3;
ReadDat();
pinlv(a);
bhtree(a);
fp=fopen("out.txt","w");
for(i=0;i=0;p--)
m[i][k-1-p]=M[p];
}
}
for(i=0;i<26;i++)
if(a[i]!=0)
{fprintf(fp,"%c:",97+i);
for(j=0;j<10;j++)
if(m[i][j]<2)
fprintf(fp,"%d",m[i][j]);
fprintf(fp,"\n");}
if(a[26]!=0)
{ fprintf(fp,":");
for(j=0;j<10;j++)
if(m[26][j]<2)
fprintf(fp,"%d",m[26][j]);
fprintf(fp,"\n");
}
if(a[27]!=0)
{ fprintf(fp,",:");
for(j=0;j<10;j++)
if(m[27][j]<2)
fprintf(fp,"%d",m[27][j]);
fprintf(fp,"\n");
}
if(a[28]!=0)
{fprintf(fp,".:");
for(j=0;j<10;j++)
if(m[28][j]<2)
fprintf(fp,"%d",m[28][j]);
fprintf(fp,"\n");
}
for(i=0;i=97&&xx[i][j]<=122)
{ k=xx[i][j]-97;
for(p=0;p<10;p++)
if(m[k][p]<2)
fprintf(fp,"%d",m[k][p]);
}
else
if(xx[i][j]==32)
{ for(p=0;p<10;p++)
if(m[26][p]<2)
fprintf(fp,"%d",m[26][p]);
}
else
if(xx[i][j]==44)
{ for(p=0;p<10;p++)
if(m[27][p]<2)
fprintf(fp,"%d",m[27][p]);
}
else
if(xx[i][j]==46)
{ for(p=0;p<10;p++)
if(m[28][p]<2)
fprintf(fp,"%d",m[28][p]);
}
}
fprintf(fp,"\n");
}
}
六、 实验结果
七、 总结
本次实验好像并不让我受益匪浅，因为大多数的代码依然不是我自己编写的，但是在实验过程中，不断地填空、修改以及调试的确使我的这方面的知识得到了提升。在实验中，我更深刻地掌握哈夫曼树的概念、存储结构，掌握建立哈夫曼树和哈夫曼编码的方法及带权路径长度的计算，熟练掌握二叉树的应用。
浙公网安备 33021202002483