算法与数据结构实验报告

计算机与信息学院

课程名称：姓 名：系：专 业：年 级：学 号：指导教师：职 称：（程序设计类课程）

实验报告

算法与数据结构

计算机科学与技术

计算机科学与技术 2009级 091150022 宁正元 2011 年 6 月 5 日

实验项目列表

福建农林大学计算机与信息学院实验报告

数据结构的程序实现

一、 实验目的和要求

1.进一步了解数据结构的实验策略。 2.掌握动态结构的静态实现方法。 3.了解大批量数据的组织策略。 4.掌握数据结构在问题建模中的应用。

二、 实验内容

编程实现Josephus问题 问题描述：

有n个人围坐一圈并由1～n编号，从某个人（例如编号为k的人）开始报数，数到m的人出列；接着从出列的下一个人开始重新1~m报数，数到m的人又出列；如此反复地报数，直到最后一个人出列为止。试设计确定这n个人出列序列的程序。分析：首先对每一个人赋以一个序号值作为人出列时，将他的序号改为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<m;) {

i=(i+1)%n; //取下标加1的模，当i的值在0到n-1之间循环 if(People[i]!=-1) //人在环中则数数有效； j++; }

if(k==n) //如果k==n则表示，此时数组中只留下一个人， break; //序号为People[i]中的值，跳出循环; cout<<People[i]<<","; //输出离开人的序号;

People[i]=-1; //离开的人用-1作标记 k=k+1; }

cout<<endl;

return(People[i]); //返回最获胜人的序号

}

五、调试过程

在Microsoft Visual C++中调试通过，完整的程序：

#include<iostream.h>

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<j;l++) {

cout<<l+1<<","; allPeople[l]=l+1; }

cout<<endl;

cout<<Josephus(allPeople,j,k); } }

int Josephus(int *People,int n,int m) {

int i=-1,j=0,k=1; while(1)

{

for(j=0;j<m;) {

i=(i+1)%n; if(People[i]!=-1) j++; }

if(k==n) break;

cout<<People[i]<<","; People[i]=-1; k=k+1; }

cout<<endl; return(People[i]);

}

六、 实验结果

（1）（输入有误，分隔符逗号错了，没有“，”）

(2)（输入10个数，出列的间隔是2）

(3)（输入100个数，出列的间隔是22）

七、 总结

每次实验后，我都会写报告。因为每次亲自动手操作后我都会得到一些课本上学不到的东西。我认为做实验、写报告不仅仅是为了加深对课本上的内容的理解和掌握，更重要的一点是，我们需要掌握写报告这种“技能”。通过本次实验，我明白了循环链表和单链表的差别仅在于，判别链表中最后一个结点的条件不再是“后继是否为空”，而是“后继是否为头结点”。循环链表的运算与单链表的运算基本一致。所不同的有以下几点：

1、在建立一个循环链表时，必须使其最后一个结点的指针指向表头结点，而不是象单链表那样置为NULL。此种情况还使用于在最后一个结点后插入一个新的结点。

2、在判断是否到表尾时，是判断该结点链域的值是否是表头结点，当链域值等于表头指针时，说明已到表尾。而非象单链表那样判断链域值是否为NULL。

福建农林大学计算机与信息学院实验报告

姓名： 张文绮 学号： 091150022 实验室号__田实513_计算机号 22 实验时间： 2011.6.2 指导教师签字： 成绩：

系： 计算机科学与技术 专业： 计算机科学与技术 年级： 2009级

数据结构的程序实现

一、实验目的和要求

1.进一步了解数据结构的实验策略。 2.掌握动态结构的静态实现方法。 3.了解大批量数据的组织策略。 4.掌握数据结构在问题建模中的应用。

二、 实验内容

编程实现哈夫曼算法，并用该程序求解某一实际问题的哈夫曼编码。

问题描述：利用哈夫曼编码实现对一个文本文件的内容加密。假设该文本文件只能包含小写字母、空格、逗号和句号等字符。

三、 实验环境

Microsoft Visual C++

四、 算法描述及实验步骤

通过在《算法与数据结构》第四章知道怎么构造一棵哈夫曼树：

1、对给定的n个权值{W1,W2,W3,...,Wi,...,Wn}构成n棵二叉树的初始集合F={T1,T2,T3,...,Ti,...,Tn}，其中每棵二叉树Ti中只有一个权值为Wi的根结点，它的左右子树均为空。（为方便在计算机上实现算法，一般还要求以Ti的权值Wi的升序排列。）

2、在F中选取两棵根结点权值最小的树作为新构造的二叉树的左右子树，新二叉树的根结点的权值为其左右子树的根结点的权值之和。

3、从F中删除这两棵树，并把这棵新的二叉树同样以升序排列加入到集合F中。 4、重复二和三两步，直到集合F中只有一棵二叉树为止。

用C语言实现上述算法，可用静态的二叉树或动态的二叉树。若用动态的二叉树可用以下数据结构：

struct tree

{ float weight; /*权值*/ union{

char leaf; /*叶结点信息字符*/ struct tree *left; /*树的左结点*/ };

struct tree *right; /*树的右结点*/ };

struct forest{ /*F集合，以链表形式表示*/ struct tree *ti; /* F中的树*/ struct forest *next; /* 下一个结点*/ };

五、 调试过程

1、能正常开启程序，但是在编译的时候出现Error spawning cl.exe的提示

2、出现Compiling... Error s …… 此处隐藏：3297字，全部文档内容请下载后查看。喜欢就下载吧 ……