试验一约瑟夫问题
一、实验目的。
1、 熟悉ｃ或vc++语言上机环境。
2、 熟悉单循环链表的一些基本操作和应用。
3、 加深单循环链表的理解，逐步培养解决实际问题的编程能力。
二、实验要求。
利用单向循环链表存储结构模拟此过程，按照出列的顺序输出个人的编号。
三，设计思路。
采用单循环链表，先构造一个有n个节点的单循环链表，再给出一个报数的上限值m(假设m>1)，在链表的首节点开始从1计数，计到m是时，对应的节点从链表中删除，然后再被删除节点的下一个节点又从1开始计数，直到最后一个节点从链表中删除算法结束。
单循环链表中节点的结构如下：
typedef struct
int num;
int sipher;
struct node *next;
linklist;
该问题有两部分组成，分别由一下算法完成：
算法一：建立一个由头指针head指示的有n个节点的约瑟夫单循环链表creat.
算法二：寻找、输出和删除head所指的单循环链表的第m个节点select。该算法有以下具体步骤组成：
1、 在head中的第一个节点起循环计数找第m个节点；
2、 输出该节点的num值，把该节点的cipher(密码)值赋给m；
3、 删除该节点；
4、 转去1，知道所有节点被删除为止。
四、程序**#include<>
#include<>
#define size 100输入人数的上限 */
void main()
int person[size];
int i, j循环修正变量 */
int arraylen数组长度 */
int start, overnum开始位置各跨过位置 */
int delenum出列人所在数组中的下标 */
int name, total输入时，人的信息以及人的总数 */
printf( "请输入圆桌的总人数 "
scanf( "d", arraylen );
printf( "n" )
if( (arraylen > size ) arraylen < 0 )
printf( "请输入各个人的信息(整数): n" )
for( i = 0; i < arraylen; i++
printf( "你输入的数据的顺序为： " )
for( i = 0; i < arraylen - 1; i++
printf( "d ==person[i] )
printf( "d ", person[arraylen - 1] )
printf( "你打算从第几个人开始？ 请输入开始号： "
scanf( "d", start );
printf( "n" )
start = start - 1;
printf( "请输入相邻两出列人之间的间隔： "
scanf( "d", overnum );
printf( "n" )
total = arraylen;
printf( "程序运行后，出列人的顺序为：" )
for( i = 0; i < total; i要打印total个人的情况，故做total次 */
printf( "n" )
五、运行结果
实验二分布计数排序算法的设计。
一、实验目的。
1熟悉ｃ或vc++语言上机环境。
2熟悉分布计数排序算法的一些基本操作和应用。
3加深分布计数排序算法的理解，逐步培养解决实际问题的编程能力。
二、实验要求。
1）用c语言实现，要求运行时间尽可能少。
2）分析该算法的比较次数和使用的辅助空间数。
三，设计思路。
1 计数排序：(采用非递减排序)设有n个关键字不同的记录，对每个记录r[i]，求出在其它n-1个记录中，小于该记录关键字的记录个数c，则c+1就是排序后该记录的位置。
2 分布计数排序：这是当关键字的取值范围比较小，并且重复的关键字较多时的一种排序方法。
3（1）计数排序分析：设在r[0...n-1]中有n个关键字不同的记录。
数组count[i]存放小于r[i]的记录个数。 对于0 ≤ j < i ≤ n-1 , 比较r[j].key 和r[i].
key, 若r[j].key < r[i].key, 则count[i] +1, 否则count[j] +1； 算法结束时， count[i] 就是r[i]应处的位置。
2）算法： ①清count] 把count[0]至count[n-1]都置0 。
②[对i进行循环] 对i = n-1，n-2，……1，执行第3步。
③[对j进行循环] 对j = i-1, i-2，……0，执行第4步。
④ [比较r[j].key和r[i].key] 若 r[j].key < r[i].key, 则count[i] +1, 否则count[j] +1。
⑤ [复制] 对i=0, …n-1, 把r[i]写到s[ count[i] ]中。
4（1）分布计数排序法分析：设关键字的取值范围u≤r[i]≤v，并且（v-u）很小。这些假定看起来十分苛刻，但事实上这一思想有不少应用。
例如，若把这个算法应用于关键字的头几位数字，而不是整个关键字，则这个文件被部分的排序，完成这项任务是相当简单的。
2）算法： ①清count] 把count[u]到count[v]清为0。
②.[求关键字的重复数] 对i=1,2,…,n, 执行： count[r[i]]+1。
③.[累加] (此时count[i]的值是关键字i的个数) 对i=u+1,u+2,……v,执行 count[i] =count[i] +count[i-1]。
输出](此时的count[i]是小于或等于i的关键字的个数，特别地count[v]=n)
对j=n,n-1,…,1, 执行： s[count[r[j]]]r[j]和count[r[j]]-1。
四算法的c语言描述如下：
1计数排序。
typedef struct rectype
keytype key;
datatype otherinfo;
rectype;
void countsort1(rectype r,int n)
{ int count[n];
for ( i =0; i<=n-1; i++)count[i] =0;
for ( i = n-1; i>=1; i--)
for ( j = i-1; j>=0; j--)
if r[j].key < r [i].key count[i] +
else count[j] +
for ( i =0; i<=n-1; i++)
s[count[i]]=r[i];
说明：由算法可以看出， 对于n个元素， 比较次数为： (n-1)+(n-2)+…1= n(n-1)/2, 另外，还需要2n个辅助单元， 当n很大时， 这不是一个有效的算法。
在上述讨论中， 我们假设关键字互不相同， 若允许存在相同关键字的记录时，该算法也能正确工作，并且是稳定的。若允许存在相同关键字的记录，且在第4步中，把“r[j].key < r [i].
key”改成“r[j].key <=r [i].key”，仍能正确工作，但是不稳定了。
2分布计数排序。
程序为了符合程序设计的习惯， 把count定义成从count[1]到count[v-u+1].
程序如下：void countsort2(int r,n,u,v)
int m=v-u+1;
for(i=1; i<=m; i置初值*/
count[i]=0;
for(i=1; i<=n; i求各键的重复次数*/
count[r[i]-u+1]++
for(i=2; i<=m; i累加*/
count[i]= count[i]+count[i-1];
for(j=n; j>=1; j输出*/
i=r[j]-u+1;
课程设计报告格式 课程设计
洛阳理工学院。课程设计说明书。课程名称。设计课题。专业。班级。学号。姓名。完成日期2014年12月26日。问题描述 小四宋体，行间距单倍行距，每段缩进两个字符。叙述一下设计的内容要求。基本要求 小四宋体，行间距单倍行距，每段缩进两个字符。叙述一下设计的基本要求。测试数据 小四宋体，行间距单倍行距，每...
课程设计总结,课程设计报告
课程设计总结，课程设计报告。3.尝试应用项目管理软件进行项目进程的规划管理 绘制甘特图，不作硬性要求 二 选题说明。人事管理是企业信息管理的重要部分，面对大量的人事工资信息，财务部门采用人力处理将浪费大量的时间 人力和物力，且数据的准确性低。因此，开发一个界面友好，易于操作的人事工资管理软件进行自动...
课程设计 课程设计报告格式
学校名。课程设计报告。课程名称 c语言程序设计 系别 专业班级 学号。姓名。课程题目 企业人事管理系统 完成日期 指导老师 年月日。附件。课程设计的内容。企业人事管理系统 本项目的目标是开发一个功能实用，操作简便，简单明了的人事管理系统。能够录入人事的基本资料，在操作上能够完成诸如添加 修改 删除 ...