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

纸牌游戏
1. 课程设计目的
本课程设计是为了配合《数据结构》课程的开设，通过设计一完整的程序，使学生掌握数据结构的应用、算法的编写、类C语言的算法转换成C程序并用TC上机调试的基本方法。
2.设计方案论证
2.1课程设计任务
纸牌游戏，编号为1~52张牌，正面向上，从第二张开始，以2为基数，是2的倍数的牌翻一次，直到最后一张牌；然后从第三张牌开始，以3为基数，是3的倍数的牌翻一次，直到最后一张牌；直到以52为基数的翻过，输出：这时输出正面向上的牌有哪些？
2.2设计思绪
2.2.1程序思绪
编号为1的牌没有进行翻牌，即翻牌的次数为0，仍然为正面朝上；编号为2的牌在整个过程中只翻了一次，为反面朝上；编号为3的牌在整个过程中只翻了一次，为反面朝上；编号为4的牌在整个过程中翻了两次，为正面朝上；编号为5的牌在整个过程中翻了一次，为反面朝上；编号为6的牌在整个过程中翻了三次（由于6是2、3、6的倍数），为反面朝上；以此类推直至编号为52的牌，从上述过程可以总结出这样的规律：从编号为1的第一张牌到编号为52的最后一张牌，只要它翻过的次数为偶数则是正面朝上，反之则为反面朝上。因此我们可以依据每张牌翻过的次数来拟定它最终是否为正面向上，从而输出实验所需要的结果：所有正面向上的牌的编号。
2.2.2数据结构的选择
由于编号为1～52的52张牌没有规定在物理位置上相邻接，且在翻牌操作时要对编号依次进行判断，很容易想到用指针来进行操作。为方便起见，我选用单链表这种数据结构来对52张牌进行链接存储。单链表是有限个具有相同类型的数据元素组成的链表，且该链表中的每一个结点只有一个指针域。根据第一部分的问题分析可知该单链表中每个结点应涉及三个部分：存储该结点所相应的牌的编号信息data域、记录该结点所相应的牌的翻牌次数count域、存储其直接后继的存储位置的next域（指针域），其
结点结构图如下（其中data、count为整型，next为指针类型）：
故可创建以单链表为存储结构的结构体，如下：
type struct node
{ int data ; //牌的编号
int count ; //记录翻牌的次数
struct node *next ; //指向下一个结点的指针
} LinkList； //该单链表为LinkList类型
2.2.3概要设计
定义了单链表中结点的数据类型后，接下来就要创建单链表。我选用的是尾插法创建带有头结点的单链表，运用malloc函数申请内存空间。然后设计翻牌程序，运用j%i=o的思想，并记录每张牌翻过的次数。再编写输出结果程序，思想是：若翻牌的次数为偶数时则为正面朝上，输出该牌的编号。最后编写主函数，主函数中调用子函数，并输出一些提醒信息。为了实现程序所需的功能，程序中用到三个子函数和一个主函数：
子函数1：创建带有头结点的链表的函数 LinkList *creat (int k)
子函数2：翻牌函数 LinkList *overcard (LinkList *head)
子函数3：输出结果函数 void result（LinkList *head）
主函数：void main （ ）
各函数模块间的调用关系如图1所示。
main
creat
overcard
result

图1各函数调用关系
主函数流程图，如图2所示。

N
初始化工作：char ch;
Int k=52; LinkList *head,*p
Ch==‘Y’
调用创建链表函数：
Head=creat(k)
调用翻牌函数：p=overcard(head,k)
调用输出结果函数：result(p)
重新选择操作，输入ch值
结束
图2主函数流程图
Y
开始

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 *head，*p，*q；
定义并初始化记录结点个数的变量i：int i=0；
一方面申请头结点空间：head=(LinkList *)malloc(sizeof(LinkList));
指针p指向头结点head：p=head;
然后运用指针q再申请结点空间：q=(LinkList *)malloc(sizeof(LinkList));
将结点链接成链表的核心操作如下：
while(i<k)
{q->data=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);
}
（3）子函数2：翻牌函数 LinkList *overcard(LinkList *head,int k)
说明;形参分别指头指针、结点个数
{定义一个LinkList类型指针p：LinkList *p
由于翻牌时从基数2开始，可以使用for循环：
for(int i=2;i<=k;i++)
{p=head->next; //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; //共有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);}
}
3.设计结果与分析
3.1时间、空间性能分析
本算法的空间复杂度很低，只需要一个具有52个结点的单链表来存储已编号的52张牌，因此空间复杂度为O(n)。但是该算法的时间复杂度有点高，每个子函数中都用到了循环语句，特别是在翻牌子程序中用到了双重循环，其时间复杂度为O(n2) 。
3.2错误分析
在初次编写完毕后出了一些语法和拼写上的小错误，导致运营结果不对的。例如翻牌子程序中的用到了for循环：for(int i=2；i<k；i++) ,编译时没有错误，经验证，编号第52的牌应为反面朝上，因此上述运营结果并不对的。于是我开始一句句研究代码，发现是循环条件犯错了，应当为for(int i=2；i<=k；i++)。出现这个错误是自己很大意，仿造上面的创建链表时的循环条件没有添加等于号而犯错了。这也警示我在编写代码时要边写边思考，防止出现大的错误。
3.3运营程序
进入主界面后，用户可以根据窗口提醒得到想要的结果。即输入Y则运营该程序，得到所有正面朝上的牌的编号，输入Q则不运营该程序，退出运营窗口。
程序开始运营，进入界面，如图3所示。

图3程序开始界面
用户想要执行程序，选择Y，进入下一界面，如图4所示。

图4执行程序界面

用户不想要执行程序，选择Q，进入的界面，如图5所示。

图5不执行程序界面
4设计体会
设计一个程序需要按一个完整的环节来进行。一方面必须弄懂程序要解决的是什么问题。在弄懂之后大脑中就要开始构思要用是什么方法来解决问题，在此期间需要“不择手段”，就是可以问同学、老师或者查阅相关资料通过网络等等，动用一切渠道把握别人的精髓来解决问题。完毕后就要把方法赋之于行动，重要是画出流程图和结构图，依照图设计出解决问题的各种算法随后编写出程序。最后完毕调试和纠错。这 方，都觉得挺快乐的，只有通过这个过程才会提高自己的发现问题、分析问题、解决问题的能力，使得思维更加严谨。虽然这次课程设计不是很难，不是做一个比较大的系统，代码不算多，但是我认为要成功地完毕一个程序，涉及完整的实验报告都要投入必要的时间和精力，认真对待，这样我们可以收获不少东西。
在这次程序设计中，碰到了许多的问题，深知自己学习的知识还远远不够。这是一种全面综合训练，是与课堂听讲，自学和练习相辅相成的，必不可少的一个教学环节。学习和掌握此门功课，掌握了面向对象程序设计方法，并能边学简朴的程序。在此基础上，通过课程设计的综合训练，培养了我们实际分析问题，编程和动手能力，更系统掌握该门课程的重要内容。这次的课程设计为以后的学习打下了坚实的基础。感谢老师给予我们这次机会，我会继续努力，在学习的这条路上不断攀登！
5参考文献
[1] 潘新民, 王燕芳. 微型计算机控制技术[M], 第2版. 北京: 电子工业出版社, 2023.4：305-350
[2] 谭浩强. C程序设计（第三版）[M] .北京：清华大学出版社,2023
[3] 王昆仑. 数据结构与算法[M] .北京：中国铁道出版社,2023
[4] 谭浩强. C程序设计指导[M].北京：清华大学出版社,2023

6附录： 带有注释的源程序
#include<stdio.h>
#include<malloc.h>
typedef struct node
{int 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(i<k)
{q->data=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 *head,int k) //翻牌函数
{LinkList *p;
for(int i=2;i<=k;i++)
{p=head->next; //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);}
}

沈 阳 大

沈 阳 大

沈 阳 大 学