数据结构课程设计报告---joseph环.doc

数据结构课程设计报告 班 级：信息安全101班 学 号： 02 姓 名： 时 间： 2011年12月25日 ～2012年1月6日 2012年01月06日 joseph环 问题描述 任务：编号是1，2，……,n的n个人按照顺时针方向围坐一圈，每个人只有一个密码（正整数）。一开始任选一个正整数作为报数上限值m,从第一个仍开始顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向的下一个人开始重新从1报数，如此下去，直到所有人全部出列为止。设计一个程序来求出出列顺序。 要求：利用单向循环链表存储结构模拟此过程，按照出列的顺序输出各个人的编号。 测试数据： m的初值为20，n=7 ,7个人的密码依次为3，1，7，2，4，7，4，首先m=6,则正确的输出是什么？ 要求： 输入数据：建立输入处理输入数据，输入m的初值，n ，输入每个人的密码，建立单循环链表。 输出形式：建立一个输出函数，将正确的输出序列 二、 需求分析 利用单向循环链表存储结构模拟此过程，按照出列的顺序输出各个人的编号。首先创建一个空链表，初始化链表，构造出一个只有头结点的空链表，建立好一个约瑟夫环。1. 输入的形式和输入值的范围? ?本程序中，输入报数上限值m和人数上限l，密码，均限定为正整数，输入的形式为一个以“回车符”为结束标志的正整数。2. 输出的形式? ?从屏幕显示出列顺序。3. 程序功能? ?提供用户从键盘输入，Joseph约瑟夫环的必要数据，并显示出列顺序。三、概要设计以单向循环链表实现该结构。1. 抽象数据类型的定义为：ADT LNode{? ?数据对象：D={ai | ai∈CharSet，i= 1，2，…，n，n≥0}? ?数据关系：R1={lt; ai-1 ，ai gt; | ai ∈D， I=2，…，n} 四、源程序 #includestdio.h #includestdlib.h typedef struct Node { int key;//每个人持有的密码 int num;//这个人的编号 struct Node *next;//指向下一个节点 }Node,*Link; void InitList(Link L) //创建一个空的链表 { L=(Node *)malloc(sizeof(Node)); if(!L) exit(1); L-key=0; L-num=0; L-next=L; } void Creater(int n,Link L) //初始化链表 { Link p,q; q=L; for(int i=1;i=n;i++) { p=(Node *)malloc(sizeof(Node)); if(!p) exit(1); printf(the key_%d is:,i); scanf(%d,p-key); p-num=i; L-next=p; L=p; } L-next=q-next; free(q); } void main() { Link L,p,q; int n,x; L=NULL; InitList(L);//构造出一个只有头结点的空链表 printf(please input the totle number of people:); scanf(%d,n);//总共的人数n printf(the start key is:); scanf(%d,x);//初始密码为x Creater(n,L);//建立好一个约瑟夫环 p=L; for(int i=1;i=n;i++) { for(int j=1;jx;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 输出：6 7 4 1 5 3 2 一元多项式计算 问题描述 能够按照指数降序排列建立多项式；能够完成两个多项式的相加、相减和相乘，并将结果输出。 设计思路 这个程序的关键是多项式的创建和排列，以及相乘时系数相乘和指数相加、相加时相同指数的系数相加、相减时相同指数的系数相减。由于多项式拥有