数据结构课程设计 纸牌游戏.docx

《数据结构课程设计 纸牌游戏.docx》由会员分享，可在线阅读，更多相关《数据结构课程设计 纸牌游戏.docx（10页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构课程设计 纸牌游戏 纸牌游戏 1.课程设计目的 本课程设计是为了配合数据结构课程的开设，通过设计一完整的程序，使学生掌握数据结构的应用、算法的编写、类C语言的算法转换成C程序并用TC上机调试的基本方法。 2.设计方案论证 2.1课程设计任务 纸牌游戏，编号为152张牌，正面向上，从第二张开始，以2为基数，是2的倍数的牌翻一次，直到最后一张牌；然后从第三张牌开始，以3为基数，是3的倍数的牌翻一次，直到最后一张牌；直到以52为基数的翻过，输出：这时输出正面向上的牌有哪些？ 2.2设计思路 2.2.1程序思路 编号为1的牌没有进行翻牌，即翻牌的次数为0，仍然为正面朝上；编号为2的牌在整个过程

2、中只翻了一次，为反面朝上；编号为3的牌在整个过程中只翻了一次，为反面朝上；编号为4的牌在整个过程中翻了两次，为正面朝上；编号为5的牌在整个过程中翻了一次，为反面朝上；编号为6的牌在整个过程中翻了三次（由于6是2、3、6的倍数），为反面朝上；以此类推直至编号为52的牌，从上述过程可以总结出这样的规律：从编号为1的第一张牌到编号为52的最后一张牌，只要它翻过的次数为偶数则是正面朝上，反之则为反面朝上。因此我们可以依据每张牌翻过的次数来确定它最终是否为正面向上，从而输出实验所需要的结果：所有正面向上的牌的编号。 2.2.2数据结构的选择 因为编号为152的52张牌没有要求在物理位置上相邻接，且在翻牌

3、操作时要对编号依次进行判断，很容易想到用指针来进行操作。为方便起见，我选用单链表这种数据结构来对52张牌进行链接存储。单链表是有限个具有相同类型的数据元素组成的链表，且该链表中的每一个结点只有一个指针域。根据第一部分的问题分析可知该单链表中每个结点应包括三个部分：存储该结点所对应的牌的编号信息data域、记录该结点 所对应的牌的翻牌次数count域、存储其直接后继的存储位置的next域（指针域），其结点结构图如下（其中data、count为整型，next为指针类型）： 故可创建以单链表为存储结构的结构体，如下： type struct node int data ; /牌的编号 int cou

4、nt ; /记录翻牌的次数 struct node *next ; /指向下一个结点的指针 LinkList；/该单链表为LinkList类型 2.2.3概要设计 定义了单链表中结点的数据类型后，接下来就要创建单链表。我选用的是尾插法创建带有头结点的单链表，运用malloc函数申请内存空间。然后设计翻牌程序，利用j%i=o 的思想，并记录每张牌翻过的次数。再编写输出结果程序，思想是：若翻牌的次数为偶数时则为正面朝上，输出该牌的编号。最后编写主函数，主函数中调用子函数，并输出一些提示信息。为了实现程序所需的功能，程序中用到三个子函数和一个主函数： 子函数1：创建带有头结点的链表的函数 LinkL

5、ist *creat (int k) 子函数2：翻牌函数 LinkList *overcard (LinkList *head) 子函数3：输出结果函数 void result（LinkList *head） 主函数：void main （） 各函数模块间的调用关系如图1所示。 main creat overcard result 图1各函数调用关系 主函数流程图，如图2所示。 开始 初始化工作：char ch; Int k=52; LinkList *head,*p N Ch=Y Y 调用创建链表函数： Head=creat(k) 调用翻牌函数： p=overcard(head,k) 调用输

6、出结果函数：result(p) 重新选择操作，输入ch值 结束 图2主函数流程图 2.2.4详细设计和编码 （1）定义单链表结点类型： type struct node int data ; /牌的编号 int count ; /记录翻牌的次数 struct node *next ; /指向下一个结点的指针 LinkList； /该单链表为LinkList类型 （2）子函数1：尾插法创建带有头结点的单链表 LinkList *creat (int k) 说明：形参k表示单链表中结点的个数 建立的过程大致如下：一开始定义LinkList类型的三个指针变量 *head、*p、*q：LinkList

7、 *head，*p，*q； 定义并初始化记录结点个数的变量i：int i=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作为新的p q=q-next; /q指针后移 q=(LinkLi

8、st *)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=

9、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; /共有52张牌 LinkList

10、 *head,*p; printf(执行此程序（Y），不执行此程序（Q）n); scanf(%c,&ch); while(1) if(ch=Y) head=creat(k); p=overcard(head,k); result(p); else if(ch=Q) printf(退出程序！n);break; scanf(%c,&ch); 3.设计结果与分析 3.1时间、空间性能分析 本算法的空间复杂度很低，只需要一个含有52个结点的单链表来存储已编号的52张牌，因此空间复杂度为O(n)。但是该算法的时间复杂度有点高，每个子函数中都用到了循环语句，尤其是在翻牌子程序中用到了双重循环，其时间复杂度

11、为O(n2) 。 3.2错误分析 在初次编写完成后出了一些语法和拼写上的小错误，导致运行结果不正确。例如翻牌子程序中的用到了for循环：for(int i=2；idata=i+1; /给每个结点的data赋值 q-count=0; /给每个结点的count赋值 p-next=q; /q链接到p之后 p=q; /将q作为新的p q=q-next; /q指针后移 q=(LinkList *)malloc(sizeof(LinkList); i+; p-next=NULL; /将最后一个结点的next域赋为空return(head); LinkList *overcard(LinkList *hea

12、d,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; /共有52张牌 LinkList *head,*p; printf(执行此程序（Y），不执行此程序（Q）n); scanf(%c,&ch); while(1) if(ch=Y) head=creat(k); p=overcard(head,k); result(p); else if(ch=Q) printf(退出程序！n);break; scanf(%c,&ch);