课程设计报告-周广捷.doc

《课程设计报告-周广捷.doc》由会员分享，可在线阅读，更多相关《课程设计报告-周广捷.doc（22页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、上海应用技术学院课程设计任务书课程名称数据结构课程设计课程代码设计题目1、纸牌游戏 2、猴子选大王3、一元多项式计算 4、拓扑排序 设计时间2012年 6 月 17 日 2012年 6 月 21 日系（院）计算机科学与信息工程学院专业计算机科学与技术班级一、课程设计任务（条件）、具体技术参数（指标）本次课程设计完成如下模块（共13个模块，学生可以在其中至少挑选3个功能块完成，但有*号的模块是必须要选择2个,多做可以加分）1、 运动会分数统计*2、 一元多项式计算*3、 订票系统4、 迷宫求解5、 文章编辑*6、 joseph环7、 猴子选大王*8、建立二叉树，层序、先序、中序、后序遍历（ 用递

2、归或非递归的方法都可以）*9、 赫夫曼树的建立10、纸牌游戏*11、图的建立及输出12、拓扑排序13、各种排序二、对课程设计成果的要求（包括课程设计说明书、图纸、图表、实物等软硬件要求）1. 提交课程设计报告（格式及文件名参见模板）一份。2. 提交源程序文件及配套文件一套。三、课程设计工作进度计划：6月17日：指导老师下发课程设计指导书和任务书，并进行必要的指导，学生完成选题。6月18日：完成详细设计说明，进入编程阶段。6月19日：完成编程和测试工作。6月20日：提交课程设计报告和源程序，答辩，成绩评定。四、主要参考资料1李春葆.数据结构学习指导.清华大学出版社,20102张晓莉等.数据结构与

3、算法.机械工业出版社,20023李春葆.数据结构教程上机实验指导.清华大学出版社,2010.4 R Krishnamoorthy、G Indirani Kumaravel。Data Structures Using C数据结构（C语言版）。清华大学出版社。2009-9指导教师（签名）： 年 月 日教研室主任（签名）： 年 月 日上海应用技术学院课程设计报告课程名称 数据结构课程设计 设计题目 1 纸牌游戏 2.猴子选大王 3.多项式计算 4 拓扑排序 院系 计算机科学与信息工程学院 专业 网络工程 班级 姓名 周广捷 学号 指导教师 林捷 日期 12年6月17日_12 年 6月21日一. 目的

4、与要求1. 巩固和加深对常见数据结构的理解和掌握2. 掌握基于数据结构进行算法设计的基本方法3. 掌握用高级语言实现算法的基本技能4. 掌握书写程序设计说明文档的能力5. 提高运用数据结构知识及高级语言解决非数值实际问题的能力二. 课程设计内容说明1、纸牌游戏 ；任务：编号为1-52张牌，正面向上，从第2张开始，以2为基数，是2的倍数的牌翻一次，直到最后一张牌；然后，从第3张开始，以3为基数，是3的倍数的牌翻一次，直到最后一张牌；然后从第4张开始，以4为基数，是4的倍数的牌翻一次， 直到最后一张牌；.再依次5的倍数的牌翻一次，6的，7的直到以52为基数的翻过，输出：这时正面向上的牌有哪些？2、

5、猴子选大王任务：一堆猴子都有编号，编号是1，2，3 .m ,这群猴子（m个）按照1-m的顺序围坐一圈，从第1开始数，每数到第N个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。要求：输入数据：输入m,n m,n 为整数，nm输出形式：中文提示按照m个猴子，数n 个数的方法，输出为大王的猴子是几号 ，建立一个函数来实现此功能 3、一元多项式计算任务：能够按照指数降序排列建立并输出多项式；能够完成两个多项式的相加、相减，并将结果输入；在上交资料中请写明：存储结构、多项式相加的基本过程的算法（可以使用程序流程图） 、源程序、测试数据和结果、算法的时间复杂度、另外可以提

6、出算法的改进方法；4、拓扑排序任务：编写函数实现图的拓扑排序3.1.1需求分析及功能简介这道题的需求很简单，就是一副纸牌（52）张按序号递增的顺序依次正面向上放好，以2为基数从2号牌开始依次翻过2的倍数；以32为基数从32号牌开始依次翻过32的倍数；以52为基数从52号牌开始依次翻过52的倍数；然后输出此时依然正面向上的牌。由于52张牌已经定死，所以这个程序的功能相对也简单，就是按照它的要求输出经过51次后仍然正面向上的牌。3.1.2功能模块一览该模块就一个功能，输出正面向上的牌的序号。3.1.3核心算法该算法用到的数据结构是数组，也可以说是一个顺序表。定义的结构体有两个数据项：data用来存

7、放牌的序号，info用来存放牌被翻过的次数。开始的时候做一个52次的循环，分别为52个空间的编号赋值，并把info全部置零，因为他们都没有被翻过。for(i=2;i=52;i+)这句话的意思是依次以2，3，4，n为基数翻拍，所谓基数，就是如果这张牌的代码是基数的倍数，那么这张牌就翻一次。if(aj.data)%i=0)这句话就是来判断代号是否为基数的倍数的，因为余数为零就表示为倍数，info+1，翻一次。全部翻过之后，开始一次扫描info的值，因为一开始全是正面，换言之，当info的值为奇数表示这张牌是背面向上，为偶数表示这张牌是正面向上。用ai.info%2=0的方法判断info为偶数的牌，

8、即正面向上的牌，输出。for(k=0;kMax;k+)/为数组赋初值，即从1到52张牌 ak.data=k+1;ak.info=0;/被翻次数一开始都是0，且均正面向上 for(i=2;i=Max;i+)/从2开始，基数递增 for(j=i-1;jMax;j+)/每次翻过基数的倍数的牌 if(aj.data)%i=0)aj.info+;/每翻过一次，加一 printf(正面向上的牌为：); for(i=0;irear=q-front表示队满。也可表示队空。void number(int n,int m) int i,j,e; SqQueue q; q.front=q.rear=0; for(i

9、=1;i=m;i+) q.rear=(q.rear+1)%m; q.dataq.rear=i; if(n=1)for(i=1;im;i+)printf(第%d只猴子被淘汰了T_Tn,i);printf(大王为第%d只猴子！,m);else while(q.rear-q.front)%m!=1) for(j=1;jnext,*pb=hb-next,*s,*tc;float c;hc=(PolyNode *)malloc(sizeof(PolyNode);tc=hc;while(pa!=NULL&pb!=NULL)if(pa-exppb-exp)s=(PolyNode *)malloc(sizeo

10、f(PolyNode);s-exp=pa-exp;s-coef=pa-coef;tc-next=s;tc=s;pa=pa-next;else if(pa-expexp)s=(PolyNode *)malloc(sizeof(PolyNode);s-exp=pb-exp;s-coef=-pb-coef;tc-next=s;tc=s;pb=pb-next;elsec=pa-coef-pb-coef;if(c!=0)s=(PolyNode *)malloc(sizeof(PolyNode);s-exp=pa-exp;s-coef=c;tc-next=s;tc=s;pa=pa-next;pb=pb-n

11、ext;if(pb!=NULL)pa=pb;while(pa!=NULL)s=(PolyNode *)malloc(sizeof(PolyNode);s-exp=pa-exp;s-coef=pa-coef;tc-next=s;tc=s;pa=pa-next;tc-next=NULL;printf(多项式减法的结果为：);DispPoly(hc);3.3.4流程图1、输入输出开始申请结点空间+num输入多项式的项数指针数组tempi中（i=1num）输入多项式各项的系数 x, 指数 y输出已输入的多项式 合并同类项结束否是是否输入正确2、 多项式的加法开始定义存储结果的空链 r是 否输出存储多项

12、式的和的链r结束是否同指数项系数相加后存入r中直接把p中各项存入r中直接把q中各项存入r存储多项式2的空链Q是否为空存储多项式1的空链P是否为空合并同类项3、 多项式的减法 开始定义存储结果的空链 r是 否输出存储多项式的和的链r结束是否同指数项系数相加后存入r中把p中各项系数改变符号后存入r中直接把q中各项存入r存储多项式2的空链Q是否为空存储多项式1的空链P是否为空合并同类项3.3.5调试3.4 拓扑排序3.4.1需求分析及功能简介编写函数实现图的拓扑排序这样的线性序列称为满足拓扑次序(Topological Order)的序列，简称拓扑序列。简单的说，由某个集合上的一个偏序得到该集合上的

13、一个全序，这个操作称之为拓扑排序。离散数学中关于偏序和全序的定义： 若集合X上的关系是R是自反的、反对称的和传递的，则称R是集合X上的偏序关系。 设R是集合X上的偏序（Partial Order）,如果对每个x,y属于X必有xRy 或 yRx，则称R是集合X上的全序关系。 注意： 若将图中顶点按拓扑次序排成一行，则图中所有的有向边均是从左指向右的。 若图中存在有向环，则不可能使顶点满足拓扑次序。一个DAG的拓扑序列通常表示某种方案切实可行。 3.4.2功能模块一览实现拓扑排序3.4.3核心算法void TopSort(ALGraph *G)int i,j;int StMAXV,top=-1;

14、/*栈St的指针为top*/ArcNode *p;for (i=0;in;i+)/*入度置初值0*/G-adjlisti.count=0;for (i=0;in;i+)/*求所有顶点的入度*/p=G-adjlisti.firstarc;while (p!=NULL)G-adjlistp-adjvex.count+;p=p-nextarc;for (i=0;in;i+)if (G-adjlisti.count=0) /*入度为0的顶点进栈*/top+; Sttop=i; while (top-1) /*栈不为空时循环*/i=Sttop;top-; /*出栈*/printf( %d ,i); /*输出顶点*/p=G-adjlisti.firstarc;/*找第一个相邻顶点*/while (p!=NULL) j=p-adjvex;G-adjlistj.count-; if (G-adjlistj.count=0)/*入度为0的相邻顶点进栈*/top+;Sttop=j;p=p-nextarc; /*找下一个相邻顶点*/3.4.4流程图3.4.5调试