数据结构课程设计扑克牌的排序.doc

课 程 设 计 报 告课程设计名称：数据结构课程设计课程设计题目：扑克牌的排序目 录1 课程设计介绍11.1 课程设计内容11.2 课程设计要求12 课程设计原理22.1 课设题目粗略分析22.2 原理图介绍22.2.1 功能模块图22.2.2 流程图分析33 数据结构分析63.1 存储结构63.2 算法描述64 调试与分析124.1 调试过程124.2 程序执行过程12参考文献15附 录（关键部分程序清单）16 1 课程设计介绍1.1 课程设计内容编写算法能够用基数排序算法对扑克牌进行排序。应能够选择按花色优先或按面值优先，初始扑克牌牌序要求能自动生成（随机生成）。 1.2 课程设计要求1花色的符号可自定，输出要求给出初始牌序和结果牌序。 2参考相应资料，独立完成课程设计任务。3交规范课程设计报告和软件代码。2 课程设计原理2.1 课设题目粗略分析根据课设题目要求，拟将整体程序分为三大模块。此三个模块相互独立，没有嵌套调用的情况，以下是三个模块的大体分析：1建立一个结构体数组存放整副扑克。2根据要求的扑克数及生成的随机数建立一个结构体数组存放需要排序的扑克。3用基数排序的方法对随机生成的扑克进行相应要求的排序 2.2 原理图介绍2.2.1 功能模块图初始化生成整副扑克随机生成需排序的扑克对扑克按花色优先排序并输出对扑克按面值优先排序并输出图2. 1 功能模块图 2.2.2 流程图分析1随机生成需排序的扑克函数流程图，如图2.2所示：开始i=1i<=tn=rand() Yri.huase=pokern.huaseri.num=pokern.numri.order=pokern.orderri.key0=pokern.huaseri.key1=pokern.orderk=(n+2)%13ri.huase=pokern.huaseri.num=pokern.numri.order=pokern.orderri.key0=pokern.huaseri.key1=pokern.orderk=(n+2)%13NK=0,1,11,122111111Y以%d输出value以%c输出valuei+结束图2.2生成随机扑克的流程图利用一个for循环及随机函数rand()，利用每次循环生成的随机数对应的数值num建立初始的无序扑克，同时将huase、value分别赋给关键字key0、key1以对其进行排序2. 对扑克进行花色优先排序的函数流程图，如图2.3所示：开始Yi<n-1i=0Yrn.next=0i=0ri.next=i+1i+Ni<=1 Y调用distribute()、collect() 函数i+i=r0.nextINi!=0Y结束输出人ri.huaseri.value图2.3对扑克进行花色优先排序的流程图对长为n的数组R，利用next域建立为静态链表，进行关键字先key1(面值)后key0（花色）的基数排序，排序后的数组按关键字key0（花色）优先的顺序存放,利用静态链表依次将其输出。3. 对扑克进行面值优先排序的函数流程图如图2.4所示：开始i=0Yi<n-1Yrn.next=0i=1ri.next=i+1i+Ni>=0Y调用distribute()、collect() 函数i-i=r0.nextINi!=0Y结束输出人ri.huaseri.value图2.4对扑克进行面值优先排序的流程图对长为n的数组R，利用next域建成静态链表，进行关键字先key0(花色)后key1（面值）的基数排序，排序后的数组按关键字key1（面值）优先的顺序存放,利用静态链表依次将其输出。3 数据结构分析3.1 存储结构typedef struct int value ; / 扑克面值 char huase; / 扑克花色 int num; / 控制面值输出形式 int order; / 在同一花色扑克的位置 int key2; / 排序用的关键字 int next; / 下一个扑克的位置apoker; / 定义一个结构体表示一张扑克apoker poker52; / 定义一个大小为52的结构体数，组存放整副扑克apoker unsortpokermax ; / 定义一个足够大的结构体数组，存放需排序的扑克typedef int tempradix; / 大小为关键字的基数的整形数组，用于基数排序的分配、收集3.2 算法描述1初始化建立扑克的算法描述说明如下：结构体名定义为apoker，poker52，unsortpokermax是apoker类型，对其赋上每个结点的名字，每个名字对应自己的一个num，以控制面值的输出形式，value对应扑克的面值，huase对应扑克的花色。for(i=0;i<52;i+)/*建立整副扑克*/ j=i/13;/*将扑克分为四种花色*/k=(i+2)%13; /*控制面值的输出形式*/m=i%13;/*同一花色中所处的位置*/ pokeri.order=m;if(j=0) pokeri.huase=3;/*花色赋值*/ else if(j=1) pokeri.huase=4; else if(j=2) pokeri.huase=5; else pokeri.huase=6;if(k=0) pokeri.value=75;/*面值赋值*/ else if(k=1) pokeri.value=65; else if(k=11) pokeri.value=74; else if(k=12) pokeri.value=81; else pokeri.value=k;pokeri.num=i;2随机生成初始扑克的算法描述如下：利用一个for循环及随机函数rand()，利用每次循环生成的随机数对应的数值num建立初始的无序扑克，同时将huase、value分别赋给关键字key0、key1以对其进行排序。根据num控制扑克value的输出格式。for(i=1;i<=t;i+)/*生成t张扑克*/ n=rand()%51; /*随机生成52以内的数*/ unsortpokeri.huase=pokern.huase;/*结构体赋值*/ unsortpokeri.value=pokern.value; unsortpokeri.num=pokern.num; unsortpokeri.order=pokern.order; unsortpokeri.key0=unsortpokeri.huase; /*关键字赋值*/ unsortpokeri.key1=unsortpokeri.order; k=(n+2)%13; /*用num控制value输出形式*/ if(k=0|k=1|k=11|k=12) printf ("%c%c ",pokern.huase,pokern.value); else printf ("%c%d ",pokern.huase,pokern.value); 3按第i个关键字对记录分配算法如下：按第i位关键字keyi建立radix个队列，同一队列中的keyi相同。headi和taili分别指向各队列中第一个和最后一个记录。headj=0表示相应队列为空队列。 void distribute(apoker r,int i,temp head,temp tail) int j,p;for(j=0;j<radix;j+)headj=0;tailj=0; /*将个队列初始化为空队列*/p=r0.next; /*p指向链表中的第一个记录*/while(p!=0)j=rp.keyi;/*用记录中第i位关键字求相应队列号*/if(headj=0)headj=p;/*将p所指向的结点加入第i个结点中*/else rtailj.next=p; tailj=p;p=rp.next;4将分配后记录收集、连接算法如下：从0到radix-1依次扫描各队列，将所有非空队列首尾相接，重新链接成一个链表。void collect(apoker r,temp head,temp tail)int j;int t;j=0;while(headj=0)/*找第一个非空队列*/j+;r0.next=headj;t=tailj;while(j<radix-1)/*寻找并串接所有非空队列*/j+;while(j<radix-1)&&(headj=0)/*找下一个非空队列*/j+; if(headj!=0)/*链接非空队列*/ rt.next=headj; t=tailj; rt.next=0;/*t指向最后一个非空队列中的最后一个结点*/ 5按面值优先对扑克排序接算法如下：对长为len的数组R进行关键字先key0(花色)后key1（面值）的基数排序，排序后的数组按关键字key1（面值）优先的顺序存放,利用num控制输出格式将其输出。void valuepresort(apoker r,int len)int i,n,k;n=len;temp head,tail;n=len;for(i=0;i<=n-1;i+)ri.next=i+1;/*构造静态链表*/rn.next=0;for(i=0;i<=1;i+)/*从最低位关键字开始，进行分配收集*/distribute(r,i,head,tail);collect(r,head,tail);printf("按面值优先排序后的扑克：n");for(i=r0.next;i!=0;i=ri.next) k=(ri.num+2)%13; /*用num控制value输出形式*/ if(k=0|k=1|k=11|k=12) printf ("%c%c ",ri.huase,ri.value); else printf ("%c%d ",ri.huase,ri.value);6按花色优先对扑克排序算法如下：对长为len的数组R进行关键字先key1(面值)后key0（花色）的基数排序，排序后的数组按关键字key0（花色）优先的顺序存放,利用num控制输出格式将其输出。void huasepresort(apoker r,int len)int i,n,k;n=len;temp head,tail;n=len;for(i=0;i<=n-1;i+)ri.next=i+1; /*构造静态链表*/rn.next=0;for(i=1;i>=0;i-) /*从最低位关键字开始，进行分配收集*/distribute(r,i,head,tail);collect(r,head,tail);printf("按花色排序后的扑克：n");for(i=r0.next;i!=0;i=ri.next) k=(ri.num+2)%13; /*用num控制value输出形式*/ if(k=0|k=1|k=11|k=12) printf ("%c%c ",ri.huase,ri.value); else printf ("%c%d ",ri.huase,ri.value);4 调试与分析4.1 调试过程在调试过程中，使用函数rand()时，出现'rand' : undeclared identifier，意识到是由于没有添加#includes<time.h>这个头文件造成的，修改后就可以运行了；还有一个出现的问题是，在一个for循环中将i错写为j，导致程序无法正常运行，通过单步跟踪，找出问题。在字符ch的输入时少写了取地址符，使程序无法运行，加上后程序运行正常。4.2 程序执行过程首先要输入需生成的扑克数，如图4.1所示：图4.1 进入系统的界面生成需要张数的扑克如图4.2所示：图4.2 随机生成的扑克选择按花色优先排序后的扑克，如图4.3所示：图4.3按花色优先排序后的扑克选择按面值优先排序后的扑克，如图4.4所示：图4.4按面值优先排序后的扑克直到输入操作选C退出系统，算法结束。如图4.5所示：图4.5退出系统后的界面参考文献1 严蔚敏，吴伟民.数据结构M.北京：清华大学出版社，2007.2 张长海，陈娟.C程序设计M.北京：高等教育出版社，2004. 3 谭浩强.C程序设计M.北京：清华大学出版社，2005.4 苏士华，黄学俊.数据结构 解析.习题.课程设计M.合肥：中国科学技术大学出版社，2009.5 张瑞军.数据结构M. 北京：清华大学出版社，2009.6 刘怀亮. 数据结构 习题解析与实验指导M. 北京：冶金出版社，2009.附 录（关键部分程序清单）程序代码#include <stdio.h>#include <time.h>#include <stdlib.h>#define radix 13typedef struct int value ; char huase; int num; int order; int key2; int next;apoker;apoker poker52;typedef int tempradix;apoker *createpoker(apoker unsortpoker,int t) int i,j,k,m; int n ;for(i=0;i<52;i+) j=i/13;k=(i+2)%13; m=i%13; pokeri.order=m;if(j=0) pokeri.huase=3; else if(j=1) pokeri.huase=4; else if(j=2) pokeri.huase=5; else pokeri.huase=6;if(k=0) pokeri.value=75; else if(k=1) pokeri.value=65; else if(k=11) pokeri.value=74; else if(k=12) pokeri.value=81; else pokeri.value=k;pokeri.num=i; printf("随机生成的扑克:n");for(i=1;i<=t;i+) n=rand()%51; unsortpokeri.huase=pokern.huase; unsortpokeri.value=pokern.value; unsortpokeri.num=pokern.num; unsortpokeri.order=pokern.order; unsortpokeri.key0=unsortpokeri.huase; unsortpokeri.key1=unsortpokeri.order; k=(n+2)%13; if(k=0|k=1|k=11|k=12) printf ("%c%c ",pokern.huase,pokern.value); else printf ("%c%d ",pokern.huase,pokern.value); return unsortpoker; void distribute(apoker r,int i,temp head,temp tail) int j,p;for(j=0;j<radix;j+)headj=0;tailj=0;p=r0.next;while(p!=0)j=rp.keyi;if(headj=0)headj=p;else rtailj.next=p; tailj=p;p=rp.next;void collect(apoker r,temp head,temp tail)int j;int t;j=0;while(headj=0)j+;r0.next=headj;t=tailj;while(j<radix-1)j+;while(j<radix-1)&&(headj=0)j+; if(headj!=0) rt.next=headj; t=tailj; rt.next=0;void valuepresort(apoker r,int len)int i,n,k;n=len;temp head,tail;n=len;for(i=0;i<=n-1;i+)ri.next=i+1;rn.next=0;for(i=0;i<=1;i+)distribute(r,i,head,tail);collect(r,head,tail);printf("面值优先排序排序后的扑克：n");for(i=r0.next;i!=0;i=ri.next) k=(ri.num+2)%13; if(k=0|k=1|k=11|k=12) printf ("%c%c ",ri.huase,ri.value); else printf ("%c%d ",ri.huase,ri.value);void huasepresort(apoker r,int len)int i,n,k;n=len;temp head,tail;n=len;for(i=0;i<=n-1;i+)ri.next=i+1;rn.next=0;for(i=1;i>=0;i-)distribute(r,i,head,tail);collect(r,head,tail);printf("花色优先排序后的扑克：n");for(i=r0.next;i!=0;i=ri.next) k=(ri.num+2)%13; if(k=0|k=1|k=11|k=12) printf ("%c%c ",ri.huase,ri.value); else printf ("%c%d ",ri.huase,ri.value);void main() int i,N; char ch; apoker unsortpoker100; printf("说明：花色顺序：%c<%c<%c<%c, 面值顺序%d<%d<.<%c<%c<%c<%c",3,4,5,6,2,3,74,81,75,65); printf("n A.花色优先排序 B.面值优先排序 C.退出系统n"); for(i=0;i<100;i+) printf("n输入扑克张数: n"); scanf("%d",&N); createpoker(unsortpoker,N); getchar();printf("n输入要进行的操作：n");scanf("%c",&ch);if(ch='A') huasepresort(unsortpoker,N); else if(ch='B') valuepresort(unsortpoker,N); else if(ch='C') break; else printf("输入有误请重新输入"); printf("n");课程设计总结：本次课程设计涉及到的范围很广，使我能够比较系统的对C语言和数据结构进行一次整理和复习。同时有了很多的体会和经验。1. 这次课设使我巩固了以前学过的C语言的知识，学习了随机函数rand()，熟练使用VC+的编译环境，也对这两门课程有了新的了解、认识。2. 对数据结构的理解有所加强，算法方面的知识也得到提高。选择不同的存储结构，对应不同的算法，所以即使同样的程序，不同的人必然会设计出不同的方案，在以后的学习生活中，一定要广泛涉猎，掌握更多更好的解决问题的方法。3. 此次设计让我意识到程序设计是脑力劳动和体力劳动相结合的，没有平时基础的训练是不会写出高效的算法。4. 此次课程设计时间虽短，但却课设的过程是短暂的，但我所收获的是永恒的。它让我尝到了学习的快乐，成功的喜悦要完成一项任务或把东西学好就必须有足够的信心，持久的耐心，有面对困难无所畏惧的精神，这对我日后的学习和生活产生了深远的影响。指导教师评语：指导教师(签字)： 年 月 日课程设计成绩