c编程（丘志杰）实验报告格式

《c编程（丘志杰）实验报告格式》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、计算机专业类课程实验报告课程名称：数据结构学院专业:计算机学院计算机科学与技术学生姓名：齐巍巍学号：2010060040013指导教师：周益民日期：2011年10月日电子科技大学计算机学院实验中心电孑科披丈学实验报告一、实验室名称：A2-413-1二、实验项目名称：线性表的应用-瑟夫生死问题的求解三、实验原理：（以下正文文字：小四，楷体（楷体_GB2312）或宋体，行距：固定值20磅，段首空两个字符。此为硬要求，不得违反。）利用线性链表，特别是循环链表来实现约瑟夫生死问题。约瑟夫生死问题的描述有三：【其一

2、】据说著名犹太历史学家Josephus有过以下的故事：在罗马人占领乔塔帕特后，39个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。然而Josephus和他的朋友并不想遵从，Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。【其二】17世纪的法国数学家加斯帕在《数目的

3、游戏问题》中讲了这样一个故事：15个教徒和15个非教徒在深海上遇险，必须将一半的人投入海中，其余的人才能幸免于难，于是想了一个办法：30个人围成一圆圈，从第一个人开始依次报数，每数到第九个人就将他扔入大海，如此循环进行直到仅余15个人为止。问怎样排法，才能使每次投入大海的都是非教徒。【其三】N个人，编号0..N-1,从0开始报数，报到M-1的退出，通常取M

4、9人，便把他投入大海中，然后再从他的下一个人数起，数到第9人，再将他扔到大海中，如此循环地进行，直到剩下最后一个乘客为止。约瑟夫问题并不难，但求解的方法很多。题目中30个人围成一圈，因而启发我们用一个循环的链来表示。可以使用结构数组来构成一个循环链。结构中有两个成员，其一为指向下一个人的指针，以构成环形的链；其二为该人是否被扔下海的标记，为1表示还在船上。从第一个人开始对还未扔下海的人进行计数，每数到9时，将结构中的标记改为0,表示该人已被扔下海了。这样循环计数直到有最后一个人为止。顺序表算法原理：为了节

5、省空间复杂度，我们提出了这样一种问题：能否采用线性表来实现？答案是肯定的。以动态数组元素代替循环链表节点的算法实现。考虑：动态数组的申请、使用、回收三原则。用30个元素数组来存放结果,初始化全为1,如果这个人被丢到海里了，就把对应位置的元素置为0;用一个变量依次对数组里不为0的元素计数，数到9则把对应位置的数组元素置0;循环控制可以用乘客数量来控制；初始为30,每有一个元素被置0,则乘客数量减1,直到1。低复杂度算法原理：无论是用链表实现还是用数组实现都有一个共同点：要模拟整个游戏过程，不仅程序写起来比较

6、烦，而且时间复杂度高达O（MN）,当N,M非常大（例如上百万，上千万）的时候，几乎是没有办法在短时间内出结果的。我们注意到原问题仅仅是要求出最后的胜利者的序号，而不是要读者模拟整个过程。因此如果要追求效率，就要打破常规，实施一点数学策略。四、实验目的：通过本次约瑟夫环的算法实验，可以有效锻炼线性循环链表的初始化、遍历、插入删除操作，可以有效锻炼顺序表算法的取模置环方法，可以深刻讨论利用数学方法在低时间复杂度求解问题时带来的好处。本次实验重点考察数据结构课程“线性表”一章的内容。五、实验内容：本次实验内容包

7、含下面三个部分的内容：第一，线性循环链表求解约瑟夫环。第二，顺序表方案求解约瑟夫环。第三，第复杂度求解约瑟夫环。六、实验器材（设备、元器件）：（实验器材按照实际使用测试的，硬件平台：计算机配置，CPU内存等，软件平台：操作系统和开发环境，测试环境。越详细越好。）硬件配置：电脑型号：戴尔InspironN4010笔记本处理器：英特尔Corei3M38O@2.53GHz双核笔记本处理器安装内存：2.00GB（三星DDR31333MHz）主硬盘：西数WDCWD5000BEKT-75KA9T0（500GB/720

8、0转/分）主板：戴尔0Y73YY软件平台：系统类型：Windows旗舰版32位开发环境：MicrosoftVisualStudio2008测试环境：MicrosoftVisualStudio2008七、实验步骤：循环链表解决方案伪代码：1.首先定义链表节点。数据域用整数表示人员编号。2.然后将节点组成为30个节点的单循环链表。删除计数器置0。3.从指定位置开始计数，移动计数器置1,移动指针到下一个节点，移动计数器加1。计数器置