数据结构课程设计报告-纸牌游戏.pdf
-纸牌游戏纸牌游戏1.1.课程设计目的课程设计目的本课程设计是为了配合数据结构课程的开设，通过设计一完整的程序，使学生掌握数据结构的应用、算法的编写、类C语言的算法转换成C程序并用TC上机调试的基本方法。2.2.设计方案论证设计方案论证2.12.1 课程设计任务课程设计任务纸牌游戏，编号为152X 牌，正面向上，从第二X 开始，以2 为基数，是2 的倍数的牌翻一次，直到最后一 X 牌；然后从第三 X 牌开始，以 3 为基数，是 3 的倍数的牌翻一次，直到最后一 X 牌；直到以 52 为基数的翻过，输出：这时输出正面向上的牌有哪些？2.22.2 设计思路设计思路2.2.12.2.1 程序思路程序思路编号为 1 的牌没有进行翻牌，即翻牌的次数为 0，仍然为正面朝上；编号为 2 的牌在整个过程中只翻了一次，为反面朝上；编号为3 的牌在整个过程中只翻了一次，为反面朝上；编号为4 的牌在整个过程中翻了两次，为正面朝上；编号为5 的牌在整个过程中翻了一次，为反面朝上；编号为6 的牌在整个过程中翻了三次（由于 6 是 2、3、6 的倍数），为反面朝上；以此类推直至编号为 52 的牌，从上述过程可以总结出这样的规律：从编号为 1 的第一 X 牌到编号为 52 的最后一 X 牌，只要它翻过的次数为偶数则是正面朝上，反之则为反面朝上。因此我们可以依据每 X 牌翻过的次数来确定它最终是否为正面向上，从而输出实验所需要的结果：所有正面向上的牌的编号。2.2.22.2.2 数据结构的选择数据结构的选择因为编号为 152 的 52X 牌没有要求在物理位置上相邻接，且在翻牌操作时要对编号依次进行判断，很容易想到用指针来进行操作。为方便起见，我选用单链表这种数据-可修编.-结构来对 52X 牌进行存储。单链表是有限个具有相同类型的数据元素组成的链表，且该链表中的每一个结点只有一个指针域。根据第一部分的问题分析可知该单链表中每个结点应包括三个部分：存储该结点所对应的牌的编号信息 data 域、记录该结点所对应的牌的翻牌次数 count 域、存储其直接后继的存储位置的 next 域（指针域），其结点结构图如下（其中 data、count 为整型，next 为指针类型）：故可创建以单链表为存储结构的结构体，如下：typestructnodeintdata;/牌的编号intcount;/记录翻牌的次数structnode*next;/指向下一个结点的指针 LinkList；/该单链表为 LinkList 类型2.2.32.2.3 概要设计概要设计定义了单链表中结点的数据类型后，接下来就要创建单链表。我选用的是尾插法创建带有头结点的单链表，运用 malloc 函数申请内存空间。然后设计翻牌程序，利用 j%i=o的思想，并记录每X 牌翻过的次数。再编写输出结果程序，思想是：若翻牌的次数为偶数时则为正面朝上，输出该牌的编号。最后编写主函数，主函数中调用子函数，并输出一些提示信息。为了实现程序所需的功能，程序中用到三个子函数和一个主函数：子函数 1：创建带有头结点的链表的函数 LinkList*creat(intk)子函数 2：翻牌函数 LinkList*overcard(LinkList*head)子函数 3：输出结果函数void result（LinkList*head）主函数：void main（）各函数模块间的调用关系如图 1 所示。-可修编.-main图图 1 1 各函数调用关系各函数调用关系creatovercard主函数流程图，如图 2 所示。resultCh=Y开始初始化工作：charch;Int k=52;LinkList*head,*pNY调用创建链表函数：Head=creat(k)调用翻牌函数：p=overcard(head,k)调用输出结果函数：result(p)重新选择操作，输入 ch 值2.2.42.2.4 详细设计和编码详细设计和编码-可修编.结束图图 2 2 主函数流程图主函数流程图-（1）定义单链表结点类型：typestructnodeintdata;/牌的编号intcount;/记录翻牌的次数structnode*next;/指向下一个结点的指针 LinkList；/该单链表为 LinkList 类型（2）子函数 1：尾插法创建带有头结点的单链表LinkList*creat(intk)说明：形参 k 表示单链表中结点的个数建立的过程大致如下：一开始定义 LinkList 类型的三个指针变量*head、*p、*q：LinkList*head，*p，*q；定义并初始化记录结点个数的变量 i：inti=0；首先申请头结点空间：head=(LinkList*)malloc(sizeof(LinkList);指针 p 指向头结点 head：p=head;然后利用指针 q 再申请结点空间：q=(LinkList*)malloc(sizeof(LinkList);将结点成链表的核心操作如下：while(idata=i+1;/给每个结点的 data 赋值q-count=0;/给每个结点的 count 赋值p-next=q;/q 到 p 之后p=q;/将 q 作为新的 pq=q-next;/q 指针后移q=(LinkList*)malloc(sizeof(LinkList);i+;-可修编.-p-next=NULL;/将最后一个结点的 next 域赋为空return(head);（3）子函数 2：翻牌函数 LinkList*overcard(LinkList*head,int k)说明;形参分别指头指针、结点个数定义一个 LinkList 类型指针 p：LinkList*p因为翻牌时从基数 2 开始，可以使用 for 循环：for(int i=2;inext;/p 指向首元素结点while(p!=NULL)if(p-data)%i=0)/若牌的编号能被基数 i 整除，则使 p-count+p-count+;p=p-next;/p 指针后移return(head);（4）子函数 3：输出正面朝上的牌的编号函数 void result(LinkList*head)定义一个 LinkList 类型指针 q：LinkList*q;q=head-next;/q 指向首元素结点printf(正面向上的牌编号为：);while(q!=NULL)if(q-count)%2=0)/若翻页的次数为偶数则正面朝上，输出printf(%4d,q-data);-可修编.-q=q-next;printf(n);（5）主函数：void main()char ch;int k=52;/共有 52X 牌LinkList*head,*p;printf(执行此程序（Y），不执行此程序（Q）n);scanf(%c,&ch);while(1)if(ch=Y)head=creat(k);p=overcard(head,k);result(p);elseif(ch=Q)printf(退出程序！n);break;scanf(%c,&ch);3.3.设计结果与分析设计结果与分析3.13.1 时间、空间性能分析时间、空间性能分析本算法的空间复杂度很低，只需要一个含有 52 个结点的单链表来存储已编号的 52X牌，因此空间复杂度为O(n)。但是该算法的时间复杂度有点高，每个子函数中都用到了循环语句，尤其是在翻牌子程序中用到了双重循环，其时间复杂度为 O(n2)。-可修编.-3.23.2 错误分析错误分析在初次编写完成后出了一些语法和拼写上的小错误，导致运行结果不正确。例如翻牌子程序中的用到了 for 循环：for(inti=2；ik；i+),编译时没有错误，经验证，编号第 52 的牌应为反面朝上，因此上述运行结果并不正确。于是我开始一句句研究代码，发现是循环条件出错了，应该为 for(inti=2；i=k；i+)。出现这个错误是自己很大意，仿造上面的创建链表时的循环条件没有添加等于号而出错了。这也警示我在编写代码时要边写边思考，防止出现大的错误。3.33.3 运行程序运行程序进入主界面后，用户可以根据窗口提示得到想要的结果。即输入 Y 则运行该程序，得到所有正面朝上的牌的编号，输入 Q 则不运行该程序，退出运行窗口。程序开始运行，进入界面，如图 3 所示。图图 3 3 程序开始界面程序开始界面用户想要执行程序，选择 Y，进入下一界面，如图 4 所示。图图 4 4 执行程序界面执行程序界面-可修编.-用户不想要执行程序，选择 Q，进入的界面，如图 5 所示。图图 5 5 不执行程序界面不执行程序界面4 4 设计体会设计体会设计一个程序需要按一个完整的步骤来进行。首先必须弄懂程序要解决的是什么问题。在弄懂之后大脑中就要开始构思要用是什么方法来解决问题，在此期间需要“不择手段”，就是可以问同学、老师或者查阅相关资料通过网络等等，动用一切渠道把握别人的精髓来解决问题。完成后就要把方法赋之于行动，主要是画出流程图和结构图，依照图设计出解决问题的各种算法随后编写出程序。最后完成调试和纠错。这方，都觉得挺高兴的，只有经过这个过程才会提高自己的发现问题、分析问题、解决问题的能力，使得思维更加严谨。虽然这次课程设计不是很难，不是做一个比较大的系统，代码不算多，但是我认为要成功地完成一个程序，包括完整的实验报告都要投入必要的时间和精力，认真对待，这样我们可以收获不少东西。在这次程序设计中，遇到了许多的问题，深知自己学习的知识还远远不够。这是一种全面综合训练，是与课堂听讲，自学和练习相辅相成的，必不可少的一个教学环节。学习和掌握此门功课，掌握了面向对象程序设计方法，并能边学简单的程序。在此基础上，通过课程设计的综合训练，培养了我们实际分析问题，编程和动手能力，更系统掌握该门课程的主要内容。这次的课程设计为以后的学习打下了坚实的基础。感谢老师给予我们这次机会，我会继续努力，在学习的这条路上不断攀登！5 5 参考文献参考文献-可修编.-1 潘新民,王燕芳.微型计算机控制技术M,第 2 版.:电子工业,2003.4：305-3502 谭浩强.C 程序设计（第三版）M.：清华大学,20053 王昆仑.数据结构与算法M.：中国铁道,20074 谭浩强.C 程序设计指导M.：清华大学,2005-可修编.-6 附录：附录：带有注释的源程序带有注释的源程序#include#includetypedef struct nodeint data;/牌的编号int count;/记录翻牌的次数struct node*next;/指向下一个结点的指针LinkList;LinkList*creat(int k)/创建链表函数LinkList*head,*p,*q;int i=0;head=(LinkList*)malloc(sizeof(LinkList);/申请头结点空间p=head;/指针 p 指向头结点q=(LinkList*)malloc(sizeof(LinkList);/申请结点空间while(idata=i+1;/给每个结点的 data 赋值q-count=0;/给每个结点的 count 赋值-可修编.-p-next=q;/q 到 p 之后p=q;/将 q 作为新的 pq=q-next;/q 指针后移q=(LinkList*)malloc(sizeof(LinkList);i+;p-next=NULL;/将最后一个结点的 next 域赋为空return(head);LinkList*overcard(LinkList*head,int k)/翻牌函数LinkList*p;for(int i=2;inext;/p 指向首元素结点while(p!=NULL)if(p-data)%i=0)/若牌的编号能被基数 i 整除，则使 p-count+p-count+;p=p-next;/p 指针后移return(head);void result(LinkList*head)/输出结果函数LinkList*q;-可修编.-q=head-next;/q 指向首元素结点printf(正面向上的牌编号为：);while(q!=NULL)if(q-count)%2=0)/若翻过的次数为偶数则正面朝上，输出printf(%4d,q-data);q=q-next;printf(n);void main()char ch;int k=52;/共有 52X 牌LinkList*head,*p;printf(执行此程序（Y），不执行此程序（Q）n);scanf(%c,&ch);while(1)if(ch=Y)head=creat(k);p=overcard(head,k);result(p);elseif(ch=Q)printf(退出程序！n);break;scanf(%c,&ch);-可修编.-可修编.-可修编.-可修编.-可修编.-可修编.-阳大-可修编.-阳大-可修编.-可修编.-可修编.-可修编.-可修编.-阳大学-可修编.-可修编.-可修编.-可修编.-可修编.-可修编.-可修编.-可修编.-可修编.-可修编.-可修编.-可修编.-可修编.-可修编.-可修编.-可修编.-可修编.-可修编.-可修编.-可修编.-可修编.
