基础成绩：82分《数据结构》课程实验
实验报告
题目：Joseph问题求解算法的设计与实现
专业：网络工程
班级：网络102
姓名：张晨曦
学号： 102534
完成日期：2012/6/20
一、试验内容
约瑟夫（Joseph ）问题的一种描述是：编号为1，2，…，n 的n 个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。开始任选一个正整数作为报数上限值m ，从第一个人开始按顺时针方向自1开始顺序报数，报到m 时停止报数。报m 的人出列，将他的密码作为新的m 值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。试设计一个程序求出出列顺序。
二、试验目的
掌握链表的基本操作：插入、删除、查找等运算，能够灵活应用链表这种数据结构。
三、流程图
四、源程序代码 #include
#include
struct list
{ 创建并初始化
n 个结点
输入第一个报
的数key
n==0
输入总人数n
报数过程 输出出列者
的编号及密码
n-- 结束
int num,code;
struct list *next;
};
void main()
{
printf("Joseph问题求解算法的设计与实现\n \n");
int i,j,m=1;
int key; // 密码.
int n; //人数.
list *p,*s,*head;
head=(list *)malloc(sizeof(list)); //为头结点分配空间.
p=head; //使指针指向头节点
printf("输入人的总个数:");
scanf("%d",&n);
for(i=1;i<=n;i++)
{
printf("第%d个人的密码:\n",i);
scanf("%d",&key);
s=p;
p=(list *)malloc(sizeof(list)); //创建新的结点.
s->next=p;
p->num=i;
p->code=key;
}
p->next=head->next;
p=head;
head=head->next;
free(p); //释放头结点.
p=head;
printf("\n\n输入初始值:\n");
scanf("%d",&key);
printf("\n出列顺序为:\n");
do
{ j=1; p=head;
while(j { s=p; p=p->next;//使P指向下一结点 j++; } //报数过程. i=p->num; key=p->code; printf("%d\n",i); s->next=p->next; head=p->next; //重新定义head,下次循环的开始结点. free(p);// 释放已出列的结点. n--; //人数减一. }while(n>0); int x; printf(“输入0退出：”); scanf(“%d”,&x); for(;;) { if(x==o) break; } } 五、调试过程 调试过程中,曾出现过缺少分号、括号之类的错误,还出现过运算顺序颠倒，致使运算出现了错误，在经过仔细的检查并且向人请教,终于得出了正确结果. 六、结果分析 输入人数：7 输入密码：3 1 7 2 4 8 4 初值：6 排序结果：6 1 4 7 2 3 5 基础成绩：82分《数据结构》课程实验 实验报告 题目：Joseph问题求解算法的设计与实现 专业：网络工程 班级：网络102 姓名：张晨曦 学号： 102534 完成日期：2012/6/20 一、试验内容 - 约瑟夫（Joseph）问题的一种描述是：编号为1，2，…，n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。试设计一个程序求出出列顺序。 二、试验目的 掌握链表的基本操作：插入、删除、查找等运算，能够灵活应用链表这种数据结构。 三、流程图 struct list { - int num,code; struct list *next; }; void main() { printf("Joseph问题求解算法的设计与实现\n \n"); int i,j,m=1; int key; // 密码. int n; //人数. list *p,*s,*head; head=(list *)malloc(sizeof(list)); //为头结点分配空间. p=head; //使指针指向头节点 printf("输入人的总个数:"); scanf("%d",&n); for(i=1;i<=n;i++) { printf("第%d个人的密码:\n",i); scanf("%d",&key); s=p; p=(list *)malloc(sizeof(list)); //创建新的结点. s->next=p; p->num=i; p->code=key; } p->next=head->next; p=head; head=head->next; free(p); //释放头结点. p=head; printf("\n\n输入初始值:\n"); scanf("%d",&key); printf("\n出列顺序为:\n"); do { j=1; p=head; while(j 重庆文理学院软件工程学院实验报告册 专业：_____软件工程__ _ 班级：_____软件工程2班__ _ 学号：_____201258014054 ___ 姓名：_____周贵宇___________ 课程名称：___ 数据结构 _ 指导教师：_____胡章平__________ 2013年 06 月 25 日 实验序号 1 实验名称实验一线性表基本操作实验地点S-C1303 实验日期2013年04月22日 实验内容1.编程实现在顺序存储的有序表中插入一个元素（数据类型为整型）。 2.编程实现把顺序表中从i个元素开始的k个元素删除（数据类型为整型）。 3.编程序实现将单链表的数据逆置，即将原表的数据（a1,a2….an）变成 (an,…..a2,a1)。（单链表的数据域数据类型为一结构体，包括学生的部分信息：学号，姓名，年龄） 实验过程及步骤1. #include { ElemType elem[MAXSIZE]; /*线性表占用的数组空间*/ int last; /*记录线性表中最后一个元素在数组elem[ ]中的位置（下标值），空表置为-1*/ }SeqList; #include "common.h" #include "seqlist.h" void px(SeqList *A,int j); void main() { SeqList *l; int p,q,r; int i; l=(SeqList*)malloc(sizeof(SeqList)); printf("请输入线性表的长度:"); scanf("%d",&r); l->last = r-1; printf("请输入线性表的各元素值:\n"); for(i=0; i<=l->last; i++) { scanf("%d",&l->elem[i]); } px(l,i); printf("请输入要插入的值:\n"); 信息学院 数据结构实验报告 学号：姓名：班级 课程名称：数据结构实验名称：约瑟夫环 实验性质：①综合性实验√②设计性实验③验证性实验实验时间：2017.10 试验地点： 本实验所用设备：PC及VS2010 【数据结构】： typedef struct _RingNode { int pos; // 位置 struct _RingNode *next; }RingNode, *RingNodePtr; 【算法思想】： 以单链表实现约瑟夫环 用户输入M,N值，从1至N开始顺序循环数数，每数到M输出该数值，直至全部输出。（约瑟夫环问题Josephus）。以环状链表实现 【算法描述】： void CreateRing(RingNodePtr pHead, int count) { RingNodePtr pCurr = NULL, pPrev = NULL; int i = 1; pPrev = pHead; while(--count > 0) { pCurr = (RingNodePtr)malloc(sizeof(RingNode)); i++; pCurr->pos = i; pPrev->next = pCurr; pPrev = pCurr; } pCurr->next = pHead; // 构成环状链表 } void PrintRing(RingNodePtr pHead) { RingNodePtr pCurr; printf("%d", pHead->pos); pCurr = pHead->next; while(pCurr != NULL) { if(pCurr->pos == 1) break; printf("\n%d", pCurr->pos); pCurr = pCurr->next; } } void KickFromRing(RingNodePtr pHead, int m) { RingNodePtr pCurr, pPrev; int i = 1; // 计数 pCurr = pPrev = pHead; while(pCurr != NULL) { if (i == m) { // 踢出环 printf("\n%d", pCurr->pos); // 显示出圈循序 pPrev->next = pCurr->next; free(pCurr); pCurr = pPrev->next; i = 1; } pPrev = pCurr; pCurr = pCurr->next; if (pPrev == pCurr) { // 最后一个 printf("\n%d", pCurr->pos); // 显示出圈循序 free(pCurr); break; } i++; } } int main() 苏州科技学院 数据结构（C语言版） 实验报告 专业班级测绘1011 学号10201151 姓名XX 实习地点C1 机房 指导教师史守正 目录 封面 (1) 目录 (2) 实验一线性表 (3) 一、程序设计的基本思想，原理和算法描述 (3) 二、源程序及注释（打包上传） (3) 三、运行输出结果 (4) 四、调试和运行程序过程中产生的问题及采取的措施 (6) 五、对算法的程序的讨论、分析，改进设想，其它经验教训 (6) 实验二栈和队列 (7) 一、程序设计的基本思想，原理和算法描述 (8) 二、源程序及注释（打包上传） (8) 三、运行输出结果 (8) 四、调试和运行程序过程中产生的问题及采取的措施 (10) 五、对算法的程序的讨论、分析，改进设想，其它经验教训 (10) 实验三树和二叉树 (11) 一、程序设计的基本思想，原理和算法描述 (11) 二、源程序及注释（打包上传） (12) 三、运行输出结果 (12) 四、调试和运行程序过程中产生的问题及采取的措施 (12) 五、对算法的程序的讨论、分析，改进设想，其它经验教训 (12) 实验四图 (13) 一、程序设计的基本思想，原理和算法描述 (13) 二、源程序及注释（打包上传） (14) 三、运行输出结果 (14) 四、调试和运行程序过程中产生的问题及采取的措施 (15) 五、对算法的程序的讨论、分析，改进设想，其它经验教训 (16) 实验五查找 (17) 一、程序设计的基本思想，原理和算法描述 (17) 二、源程序及注释（打包上传） (18) 三、运行输出结果 (18) 四、调试和运行程序过程中产生的问题及采取的措施 (19) 五、对算法的程序的讨论、分析，改进设想，其它经验教训 (19) 实验六排序 (20) 一、程序设计的基本思想，原理和算法描述 (20) 二、源程序及注释（打包上传） (21) 三、运行输出结果 (21) 四、调试和运行程序过程中产生的问题及采取的措施 (24) 五、对算法的程序的讨论、分析，改进设想，其它经验教训 (24) 实验一线性表 一、程序设计的基本思想，原理和算法描述： 程序的主要分为自定义函数、主函数。自定义函数有 InitList_Sq、Out_List、ListInsert_Sq、ListDelete_Sq、LocateElem_Sq 、compare。主函数在运行中调用上述的自定义函数，每个自定义函数实现程序的每部分的小功能。 1.程序设计基本思想 用c语言编译程序，利用顺序存储方式实现下列功能：根据键盘输入数据建立一个线性表，并输出该线性表；然后根据屏幕菜单的选择，可以进行数据的插入、删除、查找，并在插入或删除数据后，再输出线性表；最后在屏幕菜单中选择结束按钮，即可结束程序的运行。 2．原理 线性表通过顺序表现，链式表示，一元多项式表示，其中链式表示又分为静态链表，双向链表，循环链表等，在不同的情况下各不相同，他可以是一个数字，也可以是一个符号，通过符号或数字来实现程序的运行。 3.算法描述 一．需求分析 1.约瑟夫环（Joseph）问题的一种描述是：编号为1，2……，n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。 2.演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信息”之后，有用户在键盘上输入演示程序中规定的运算命令，相应的输入数据和运算结果显示在其后。 3.程序执行的命令包括： 1）输入初始密码和人数2）输入所有人的密码3）显示输入的所有人的编号及相应的密码4）输出出列密码及编号5）结束 4.测试数据 (1)m=20, n=7, 7个人的密码依次为3，1，7，2，4，8，4 (2)m=20,n=1 (3)m=20,n=0 前面一组为常规数据，后面两组为边缘数据 二、概要设计 为实现上述功能，应以有序单向循环链表表示约瑟夫环。为此，需要有一个抽象数据类型。该抽象数据类型的定义为： ADT LinkList { 数据对象：D={ ai | ai ∈termset,i=1,2,……n,n>=0}， termset中每个元素包含编号，密码，和一个指向下一节点的指针数据关系：R1={ 课程实验报告 题目：2016.4.6 学生姓名：黄玲 学生学号：201408070105 专业班级：智能1401 指导老师：骆嘉伟 完成日期：2016.4.6 一．需求分析 1.本实验基本要求是用数组来实现线性表，再基于线性表的基本操作（插入、删除、修改等）来实现约瑟夫问题 2.由键盘输入总人数n和出列报数m 3.在DOS界面上显示依次出圈的人的编号和最后一个留下的人,在当前文件夹里生成一个文本文件，里面是相同的输出。 4.测试数据： 输入： 10，3 输出： 3 6 9 2 7 1 8 5 10 4//DOS 3 6 9 2 7 1 8 5 10 4//TXT 二．概要设计 §抽象数据类型 为实现上述程序的逻辑功能，应以整数存储用户的输入 用线性表实现，线性表定义如下： ADT LISt 数据对象：整数 基本操作： AList(100);//构建一个最大人数为100的顺序表（数组）来存储人 Next();//指向下一个人 moveStart();//回到第一个人继续数数 Length();//查看圈里还剩多少人 currPos();//查看当前数到人的编号 getValue();//查看当前编号的人是否还在圈内 §程序的流程 以书上的代码案例为参考，编写线性表的ADT在继承线性表的基础上编写顺序表（数组）的类文件编写主函数，创建类的对象，完成程序 三．详细设计 §物理数据类型 将大小为n的数组赋好值，其值为他本身的编号，即数组下标。 §程序思路的具体步骤实现 设一个标志点，在数组中移动，同时报数，当报到m时，当前人的值变为0，出圈，然后继续移动，重新数。当数到值为0的人时自动跳过（已出圈），当数 数据结构实验报告(2015级)及答案 《数据结构》实验报告 专业__信息管理学院______ 年级__2015级___________ 学号___ _______ 学生姓名___ _ _______ 指导老师____________ 华中师范大学信息管理系编 I 实验要求 1．每次实验中有若干习题，每个学生至少应该完成其中的两道习题。 2．上机之前应作好充分的准备工作，预先编好程序，经过人工检查无误后，才能上机，以提高上机效率。 3．独立上机输入和调试自己所编的程序，切忌抄袭、拷贝他人程序。 4．上机结束后，应整理出实验报告。书写实验报告时，重点放在调试过程和小节部分，总结出本次实验中的得与失，以达到巩固课堂学习、提高动手能力的目的。 II 实验内容 实验一线性表 【实验目的】 1．熟悉VC环境，学习如何使用C语言实现线性表的两种存储结构。 2．通过编程、上机调试，进一步理解线性表的基本概念,熟练运用C语言实现线性表基本操作。 3．熟练掌握线性表的综合应用问题。 【实验内容】 1．一个线性表有n个元素（n 的顺序不变。设计程序实现。要求：采用顺序存储表示实现；采用链式存储表示方法实现；比较两种方法的优劣。 2. 从单链表中删除指定的元素x，若x在单链表中不存在，给出提示信息。 要求： ①指定的值x由键盘输入； ②程序能处理空链表的情况。 3．设有头结点的单链表，编程对表中的任意值只保留一个结点，删除其余值相同的结点。 要求： ①该算法用函数（非主函数）实现； ②在主函数中调用创建链表的函数创建一个单链表， 并调用该函数，验证算法的正确性。 LinkedList Exchange（LinkedList HEAD，p）∥HEAD是单链表头结点的指针，p是链表中的一个结点。本算法将p所指结点与其后 继结点交换。 {q=head->next；∥q是工作指针，指向链表中当前待处理结点。 pre=head；∥pre是前驱结点指针，指向q的前驱。 while（q!=null && q!=p）{pre=q；q=q->next；} ∥ 《数据结构》 课程设计报告 课程名称：《数据结构》课程设计课程设计题目：joseph环 姓名： 院系：计算机学院 专业： 年级： 学号： 指导教师： 2011年12月18日 目录 1 课程设计的目的 (2) 2 需求分析 (2) 3 课程设计报告内容 (3) 1、概要设计 (3) 2、详细设计 (3) 3、调试分析 (x) 4、用户手册 (x) 5、测试结果 (6) 6、程序清单 (7) 4 小结 (10) 1、课程设计的目的 （1）熟练使用C++编写程序，解决实际问题； （2）了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力； （3）初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能； （4）提高综合运用所学的理论知识和方法独立分析和解决问题的能力； 2、需求分析 1、问题描述： 编号是1，2，……,n的n个人按照顺时针方向围坐一圈，每个人只有一个密码（正整数）。一开始任选一个正整数作为报数上限值m,从第一个仍开始顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向的下一个人开始重新从1报数，如此下去，直到所有人全部出列为止。设计一个程序来求出出列顺序。 2、要求： 利用不带表头结点的单向循环链表存储结构模拟此过程，按照出列的顺序输出各个人的编号。 3、测试数据： m的初值为20，n=7 ,7个人的密码依次为3，1，7，2，4，7，4，首先m=6,则正确的输出是什么？ 输出形式：建立一个输出函数，将正确的输出序列 3、课程设计报告内容 概要设计： 在理解了题目后，我先想到的是我们所学的单链表，利用单链表先建立循环链表进行存贮，建立完循环链表后，我将所要编写的函数分为了两块，一块是经过学过的单链表改编的循环链表的基本操作函数，还有一块是运行约瑟夫环的函数。 详细设计： 我先建立一个结构体，与单链表一样，只是多了一个存密码的code域 struct LinkNode { int data; /删除的是尾结点时（不知道为什么我写程序里总是编译出现错误）{ q->next=head; //重新链接 delete a; len--; return out; } else { q->next=a->next; delete a; len--; return out; } } } } 5、测试结果： 《数据结构》课程实验 实验报告 题目：Joseph问题求解算法的设计与实现专业：计算机科学与技术 班级： 姓名： 学号： 完成日期： 一、试验内容 约瑟夫（Joseph）问题的一种描述是：编号为1，2，…，n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。试设计一个程序求出出列顺序。 二、试验目的 掌握链表的基本操作：插入、删除、查找等运算，能够灵活应用链表这种数据结构。 三、流程图 输入总人数n 创建并初始化 n个结点 输入第一个报 的数key n==0 报数过程 输出出列者 的编号及密 码 结束 n-- 四、源程序代码 //Joseph问题求解算法的设计与实现 #include 数据结构(C语言版) 实验报告 专业班级学号姓名 实验1 实验题目：单链表的插入和删除 实验目的： 了解和掌握线性表的逻辑结构和链式存储结构，掌握单链表的基本算法及相关的时间性能分析。 实验要求： 建立一个数据域定义为字符串的单链表，在链表中不允许有重复的字符串；根据输入的字符串，先找到相应的结点，后删除之。 实验主要步骤： 1、分析、理解给出的示例程序。 2、调试程序，并设计输入数据（如：bat，cat，eat，fat，hat，jat，lat，mat，#），测 试程序的如下功能：不允许重复字符串的插入；根据输入的字符串，找到相应的结点并删除。 3、修改程序： （1）增加插入结点的功能。 （2）将建立链表的方法改为头插入法。 程序代码: #include"" #include"" #include"" #include"" typedef struct node . . 示意图： head head head 心得体会： 本次实验使我们对链表的实质了解更加明确了，对链表的一些基本操作也更加熟练了。另外实验指导书上给出的代码是有一些问题的，这使我们认识到实验过程中不能想当然的直接编译执行，应当在阅读并完全理解代码的基础上再执行，这才是实验的意义所在。 实验2 实验题目：二叉树操作设计和实现 实验目的： 掌握二叉树的定义、性质及存储方式，各种遍历算法。 实验要求： 采用二叉树链表作为存储结构，完成二叉树的建立，先序、中序和后序以及按层次遍历 的操作，求所有叶子及结点总数的操作。 实验主要步骤： 1、分析、理解程序。 2、调试程序，设计一棵二叉树，输入完全二叉树的先序序列，用#代表虚结点（空指针）， 如ABD###CE##F##，建立二叉树，求出先序、中序和后序以及按层次遍历序列，求 所有叶子及结点总数。 实验代码 #include"" #include"" #include"" #define Max 20 ertex=a; irstedge=NULL; irstedge; G->adjlist[i].firstedge=s; irstedge; R[i] 留在原位 #include L->next = p; L = p; } L->next = q->next; free(q); } void PrintList(int x,int n,LinkList L) //输出出列顺序 { LinkList p,q; p = L; for(int i = 1;i <= n;i++) { for(int j = 1;j < x;j++) p = p->next; q = p->next; x = q->cipher; printf("%d ",q->number); p->next = q->next; free(q); } } int main() { printf("=============约瑟夫环==============\n\n\n"); int n,x; LinkList L; L = NULL; InitList(L); //构造空链表 printf("输入初始密码："); scanf("%d",&x); //初始密码为x printf("\n"); printf("输入参与总人数："); scanf("%d",&n); //总共的人数n printf("\n"); CreateList(n,L); //建立好一个约瑟夫环printf("\n\n\n===================================\n\n"); printf("出列编号为："); PrintList(x,n,L); //输出出列顺序 printf("\n\n"); return 0; } 数据结构实验报告-答案 数据结构(C语言版)实验报告专业班级学号姓名实验1实验题目：单链表的插入和删除实验目的：了解和掌握线性表的逻辑结构和链式存储结构，掌握单链表的基本算法及相关的时间性能分析。 实验要求：建立一个数据域定义为字符串的单链表，在链表中不允许有重复的字符串；根据输入的字符串，先找到相应的结点，后删除之。 实验主要步骤：1、分析、理解给出的示例程序。 2、调试程序，并设计输入数据（如：bat，cat，eat，fat，hat，jat，lat，mat，#），测试程序的如下功能：不允许重复字符串的插入；根据输入的字符串，找到相应的结点并删除。 3、修改程序：（1）增加插入结点的功能。 （2）将建立链表的方法改为头插入法。 程序代码:#include“stdio.h“#include“string.h“#include“stdlib.h“#include“ctype. h“typedefstructnode//定义结点{chardata[10];//结点的数据域为字符串structnode*next;//结点的指针域}ListNode;typedefListNode*LinkList;//自定义LinkList单链表类型LinkListCreatListR1();//函数，用尾插入法建立带头结点的单链表LinkListCreatList(void);//函数，用头插入法建立带头结点的单链表ListNode*LocateNode();//函数，按值查找结点voidDeleteList();//函数，删除指定值的结点voidprintlist();//函数，打印链表中的所有值voidDeleteAll();//函数，删除所有结点，释放内存 邻接矩阵的实现 1. 实验目的 （1）掌握图的逻辑结构 （2）掌握图的邻接矩阵的存储结构 （3）验证图的邻接矩阵存储及其遍历操作的实现2. 实验内容 （1）建立无向图的邻接矩阵存储 （2）进行深度优先遍历 （3）进行广度优先遍历3．设计与编码MGraph.h #ifndef MGraph_H #define MGraph_H const int MaxSize = 10; template int vertexNum, arcNum; }; #endif MGraph.cpp #include 《计算机软件技术基础》实验报告 I —数据结构 实验一、约瑟夫斯问题求解 一、问题描述 1.实验题目：编号 1,2,....,n的n个人顺时针围坐一圈，每人持有一个密码（正整数）。 开始选择一个正整数作为报数上限m，从第一个人开始顺时针自 1 报数，报到m的人出列，将他的密码作为新的m值，从他在顺时针方向下一个人开始重新从 1 报数，直至所有人全部出列。 2. 基本要求：利用单向循环链表存储结构模拟此过程，按照出列的顺序印出个人的编号。 3. 测试数据： n=7,7 个人的密码依次为：3,1,7,2,4,8, 4.m初值为6（正确的出列顺序 应为 6,1,4,77,2,3）。 二、需求分析 1. 本程序所能达到的基本可能： 该程序基于循环链表来解决约瑟夫问题。用循环链表来模拟n 个人围坐一圈，用链表 中的每一个结点代表一个人和他所代表的密码。在输入初始密码后m，对该链表进行遍历，直到第 m个结点，令该结点的密码值作为新的密码值，后删除该结点。重复上述过程，直至所有的结点被释放空间出列。 2. 输入输出形式及输入值范围： 程序运行后提示用户输入总人数。输入人数 n 后，程序显示提示信息，提示用户输入第 i个人的密码，在输入达到预定次数后自动跳出该循环。程序显示提示信息，提示用户输入 初始密码，密码须为正整数且不大于总人数。 3．输出形式 提示用户输入初始密码，程序执行结束后会输出相应的出列结点的顺序，亦即其编号。 用户输入完毕后，程序自动运行输出运行结果。 4.测试数据要求： 测试数据 n=7，7 个人的密码依次为：3， 1， 7， 2， 4， 8， 4。 m初值为 6（正确的出列 顺序应为6， 1， 4，7， 2， 3， 5）。 三、概要设计 为了实现上述功能，应用循环链表来模拟该过程，用结构体来存放其相应的编号和密码 数据结构实验报告 题目：约瑟夫环 姓名： 学号： 专业班级： 指导教师： 课题工作时间： 一．需求分析 1.约瑟夫环（Joseph）问题的一种描述是：设有编号1,2,3。。。n(n>0)的N个人围成一个圈，每个人持有一个密码（正整数）。开始时从第k（1<=k<=n）个人按顺时针方向自1开始顺序报数，报到m（m为第K个人的密码）的人出圈，再以这个人顺时针方向上的下一个人的密码为m，并开始重新从1报数。如此下去，直至所有人全部出列为止。试设计一个程序求出出列顺序。 2.演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信息”之后，有用户在键盘上输入演示程序中规定的运算命令，相应的输入数据和运算结果显示在其后。 3.测试数据 (1)m=20, n=7, 结果依次为为3，1，7，2，4，8，4 (2)m=20,n=1 (3)m=20,n=0 前面一组为常规数据，后面两组为边缘数据 二、概要设计 本程序是多文件程序，构成的函数有 int main() 主函数，输出出队序列 int initsuiji() 随机数产生初始化 int suiji(int x,int y) 随机数产生函数 int InitList(SqList &L) 初始化顺序表 int ListInsert(SqList &L,int i,ElemType e) 在顺序表中插入元素 int ListDelete(SqList &L,int i,ElemType &e) 删除顺序表中的元素 int shunxu(int number) 顺序存储算法 JosephuNode *Creat_Node(int numbers) 创建单循环链表 void Josephu(JosephuNode *head,int Password) 添加元素信息 int lianbiao(int number) 链表算法 其中，void main()是最主要的函数，分别执行两种算法，并在执行的同时按照出列顺序输出元素信息（编号，密码），并在结尾输出两种算法执行所用的时间长短。 三、详细设计 头文件 #include 《用哈夫曼编码实现文件压缩》 实验报告 课程名称数据结构 实验学期2015至2016学年第一学期 学生所在系部计算机学院 年级2014专业班级物联B142班 学生姓名杨文铎学号201407054201 任课教师白磊 实验成绩 用哈夫曼编码实现文件压缩 1、了解文件的概念。 2、掌握线性表的插入、删除的算法。 3、掌握Huffman树的概念及构造方法。 4、掌握二叉树的存储结构及遍历算法。 5、利用Haffman树及Haffman编码，掌握实现文件压缩的一般原理。 微型计算机、Windows系列操作系统、Visual C++6.0软件 根据ascii码文件中各ascii字符出现的频率情况创建Haffman树，再将各字符对应的哈夫曼编码写入文件中，实现文件压缩。 本次实验采用将字符用长度尽可能短的二进制数位表示的方法，即对于文件中出现的字符，无须全部都用S为的ascii码进行存储，根据他们在文件中出现的频率不同，我们利用Haffman算法使每个字符能以最短的二进制数字符进行存储，已达到节省存储空间，压缩文件的目的，解决了压缩需要采用的算法，程序的思路已然清晰: 1、统计需压缩文件中的每个字符出现的频率 2、将每个字符的出现频率作为叶子节点构建Haffman树，然后将树中结点引向 其左孩子的分支标“0”，引向其右孩子的分支标“1”；每个字符的编码 即为从根到每个叶子的路径上得到的0、1序列，这样便完成了Haffman 编码，将每个字符用最短的二进制字符表示。 3、打开需压缩文件，再将需压缩文件中的每个ascii码对应的haffman编码按bit 单位输出。 4、文件压缩结束。 （1）构造haffman树的方法一haffman算法 构造haffman树步骤： I.根据给定的n个权值{w1，w2，w3…….wn}，构造n棵只有根结点的二叉 树，令起权值为wj。 II.在森林中选取两棵根结点权值最小的树作左右子树，构造一棵新的二叉树，置新二叉树根结点权值为其左右子树根结点权值之和。 III.在森林中删除这两棵树，同时将得到的二叉树加入森林中。 IV.重复上述两步，知道只含一棵树为止，这棵树即哈夫曼树。 对于haffman的创建算法，有以下几点说明： a）这里的Haffman树采用的是基于数组的带左右儿子结点及父结点下标作为 韶关学院 学生实验报告册 实验课程名称：数据结构与算法 实验项目名称：实验二线性表及其应用 约瑟夫环 实验类型（打√）：（基础、综合、设计√） 院系：信息工程学院计算机系专业：***** 姓名：*** 学号：***** 指导老师：陈正铭 韶关学院教务处编制 一、实验预习报告内容 二、实验原始（数据）记录 实验时间：2007 年 4 月 4 日（星期三第7，8 节）实验同组人： 三、实验报告内容 2007年4 月5 日 注：1、如有个别实验的实验报告内容多，实验报告册页面不够写，或有识图，画图要求的，学生应根据实验指导老师要求另附相同规格的纸张并粘贴在相应的“实验报告册”中。 2、实验报告册属教学运行材料，院系（中心）应按有关规定归档保管。 【源程序】 #include "stdio.h" #include "conio.h" #include "stdlib.h" /* 设立无头结点的单循环链表*/ typedef struct LNode{ int id; /* 编号*/ int pw; /* 密码*/ struct LNode *next; }LNode,*LinkList; void main() { int m,n,pw,i=1,j=0; /* m为初始报数值，n 为参与人数，pw为密码临时保存变量，i、j 为循环变量*/ LinkList L,p,q; /* L为链表头指针，p、q为临时指针*/ printf("输入人数n(n>0):"); scanf("%d",&n); printf("输入第1 人密码:"); scanf("%d",&pw); L=(LinkList)malloc(sizeof(struct LNode)); L->id=i; L->pw=pw; L->next=L; /* 创建首结点*/ q=L; /* q指向尾结点*/ p=L; /* p指向待删除结点前驱*/ for(i=2;i<=n;i++) /* 依次输入第2……第n个参与者密码*/ { printf("输入第%d 人密码:",i); scanf("%d",&pw); p=(LinkList)malloc(sizeof(struct LNode)); p->id=i; p->pw=pw; /* 创建第i个参与者结点p */ q->next=p; /* 在尾结点q后插入新结点p */ q=p; /* 更新q指向新的尾结点p */ p->next=L; /* 新结点p的后继指针指向首结点*/ } printf("输入约瑟夫环的初始报数值m:"); scanf("%d",&m); printf("出列顺序为:"); for(i=1;i<=n;i++) /* n个参与者依次按规则出列*/ { for(j=1;j 武汉工业学院数学与计算机学院 数据结构课程设计 设计题目：约瑟夫环 专业大类计算机 班级计算机6班 学号 100702129 姓名王元 指导教师李禹生 2011年9月3 日 一．选题背景： 题目：约瑟夫环 问题描述： 编号为1,2，…..，n的n个人按顺时针方向围坐圈，每个人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新重新从1报数，如此下去，直至所有人全部出列为止。 基本要求： ⑴建立模型，确定存储结构； ⑵对任意 n个人，密码为 m，实现约瑟夫环问题； ⑶出圈的顺序可以依次输出，也可以用一个数组存储。 设计指导思想： 首先，设计实现约瑟夫环问题的存储结构。由于约瑟夫环问题本身具有循环性质，考虑采用循环链表，为了统一对表中任意结点的操作，循环链表不带头结点。其次，建立一个不带头结点的循环链表并由头指针 first 指示。最后，设计约瑟夫环问题的算法。下面给出伪代码描述，操作示意图如图 2-1 所示。 二．方案论证： 本方案通过建立单循环链表模拟了约瑟夫问题；首先，建立一个结构体node，然后给他开辟一个储存空间；利用头指针head标记链表，利用尾指针向后移将建立的结点连接成我们需要的单循环链表， 过程如下： 约瑟夫问题中的人数个数即为链表的长度，链表中node->num 编号n，node->data为每个人的密码。建立单循环链表后，通过初始报数上限找到出列的结点，输出该结点的node->num值，将该结点中的data中数作为新密码开始下一个步的开始，将该结点从链表中删除，并释放该结点的空间。重复此过程，直到剩下最后一个结点，就直接将该结点中的num值输出，删除该结点，并释放该结点的空间。输出的num值即为约瑟夫中人的编号。 三．过程论述： typedef struct node { int data; int num; struct node *next; }listnode; 定义一个结构体用来储存学生的编号和所携带的密码 for(i=1;i<=n;i++) { printf("输入第%d号同学的密码:",i); scanf("%d",&j);//输入学生所带密码 p1->next=(listnode*)malloc(sizeof(listnode));//建立一个新的空间，并将它的地址赋给p1->next p1=p1->next; p1->data=j; p1->num=i;//对结点的num和data成员赋值 p1->next=head->next;//构成单循环链表 } 定义指针p1，然后建立一个新结点并将p1->next指向它的地址，然后将这个地址赋给p1，最后将head->next赋给p1->next,构成一个单循环链表，并不断在尾部插入新的结点，直至所有人都进入循环链表中，而且在循环的过程中给结点的num和data成员赋值数据结构实验报告(约瑟夫环)
数据结构实验答案1
数据结构实验报告 约瑟夫环问题
《数据结构》实验报告
约瑟夫环实验报告
约瑟夫环实验报告
数据结构实验报告(2015级)及答案
约瑟夫环课程设计实验报告
数据结构实验报告(约瑟夫环)
数据结构实验报告-答案
数据结构课程设计——约瑟夫环报告(含代码)
数据结构实验报告-答案.doc
数据结构实验报告图实验
数据结构实验报告—约瑟夫问题求解
数据结构：约瑟夫环实验报告
数据结构实验报告
数据结构实验报告(实验二 约瑟夫环)
数据结构约瑟夫环的课程设计报告
相关主题
文本预览