资源描述：
《数据结构课程设计报告---joseph环》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、数据结构课程设计报告班级：信息安全101班学号：02姓名：时间：2011年12月25日～2012年1月6日2012年01月06日joseph环一、问题描述任务：编号是1，2，……,n的n个人按照顺时针方向围坐一圈，每个人只有一个密码（正整数）。一开始任选一个正整数作为报数上限值m,从第一个仍开始顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向的下一个人开始重新从1报数，如此下去，直到所有人全部出列为止。设计一个程序来求出出列顺序。要求：利用单向循环链表存储结构模拟此过程，按照出列的顺序输出各个人的编号。测试
2、数据：m的初值为20，n=7,7个人的密码依次为3，1，7，2，4，7，4，首先m=6,则正确的输出是什么？要求：输入数据：建立输入处理输入数据，输入m的初值，n，输入每个人的密码，建立单循环链表。输出形式：建立一个输出函数，将正确的输出序列二、需求分析利用单向循环链表存储结构模拟此过程，按照出列的顺序输出各个人的编号。首先创建一个空链表，初始化链表，构造出一个只有头结点的空链表，建立好一个约瑟夫环。1.输入的形式和输入值的范围 本程序中，输入报数上限值m和人数上限l，密码，均限定为正整数，输入的形式为一个以“回车符”为结束标志的正整数。2.输出的形式
3、从屏幕显示出列顺序。3.程序功能 提供用户从键盘输入，Joseph约瑟夫环的必要数据，并显示出列顺序。三、概要设计以单向循环链表实现该结构。1.抽象数据类型的定义为：ADTLNode{ 数据对象：D={ai
4、ai∈CharSet，i=1，2，…，n，n≥0} 数据关系：R1={<ai-1，ai>
5、ai∈D，I=2，…，n}四、源程序#include#includetypedefstructNode{intkey;//每个人持有的密码intnum;//这个人的编号structNode*next;//指向下
6、一个节点}Node,*Link;voidInitList(Link&L)//创建一个空的链表{L=(Node*)malloc(sizeof(Node));if(!L)exit(1);L->key=0;L->num=0;L->next=L;}voidCreater(intn,Link&L)//初始化链表{Linkp,q;q=L;for(inti=1;i<=n;i++){p=(Node*)malloc(sizeof(Node));if(!p)exit(1);printf("thekey_%dis:",i);scanf("%d",&p->key);p->num=i
7、;L->next=p;L=p;}L->next=q->next;free(q);}voidmain(){LinkL,p,q;intn,x;L=NULL;InitList(L);//构造出一个只有头结点的空链表printf("pleaseinputthetotlenumberofpeople:");scanf("%d",&n);//总共的人数nprintf("thestartkeyis:");scanf("%d",&x);//初始密码为xCreater(n,L);//建立好一个约瑟夫环p=L;for(inti=1;i<=n;i++){for(intj=1;j<
8、x;j++)p=p->next;q=p->next;x=q->key;printf("%d",q->num);p->next=q->next;free(q);}}五、测试数据m的初值为20，n=7,7个人的密码依次为3，1，7，2，4，7，4输出：6741532一元多项式计算1、问题描述能够按照指数降序排列建立多项式；能够完成两个多项式的相加、相减和相乘，并将结果输出。2、设计思路这个程序的关键是多项式的创建和排列，以及相乘时系数相乘和指数相加、相加时相同指数的系数相加、相减时相同指数的系数相减。由于多项式拥有指数和系数（假设基数已定），所以可以定义一个包含
9、指数系数的结构体，用单链表存储多项式的数据，所以结构体包含next指针。数据插入时比较两数的指数，按照降序排序，从表头的next开始，直至找到合适的位置，然后开始链表中数值的插入，如果相等则直接将指数相加，如果大于就将新数据插入到当前指向的前面，否则将新数据插入到最后。输入完数据后选择计算方式（相乘、相加、相减），多项式运算时要循环遍历整个多项式，多项式的每一组数据都要和另一个多项式整组数据相运算（每一个运算值都存储到新建的“多项式”链表中），直到两个多项式都遍历完结束。3、数据结构设计在模拟多项式对象时，为了简化处理，只取最核心的两个数据：多项式的系数和指
10、数。前面提到，要用单链表操作，所以要加上个next指
