数据结构课程设计(joseph环拓扑排序和纸牌游戏)

1、目 录课题一joseph环 111 问题的提出 1 1. 2概要设计 113流程图 214 源代码 315 结果与分析 6课题二 拓扑排序 721 问题的提出 72. 2 概要设计 723 流程图 824 源代码 925 结果与分析 13课题三 纸牌游戏 1531 问题的提出 153. 2 概要设计 1533流程图 1634 源代码 1735 结果与分析 18课程设计总结 20参考文献 21课题一 joseph环11 问题的提出1.1问题的提出 1任务：编号是1，2，,n的n个人按照顺时针方向围坐一圈，每个人只有一个密码（正整数）。一开始任选一个正整数作为报数上限值m,从第一个仍开始顺时针方向

2、自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向的下一个人开始重新从1报数，如此下去，直到所有人全部出列为止。设计一个程序来求出出列顺序。2测试数据：输入（范围：整型数据）总成员数：7各成员密码：3 1 7 2 4 7 4初始值m:6输出（范围：大于等于1，小于等于n的整型数据）出列成员序号：6 7 4 1 5 3 21.2 概要设计 2.1算法思想 利用单向循环链表存储结构模拟此过程，因为循环链表最后一个结点的指针域指向头结点，整个链表形成一人环，刚好和题中的“n个人按照顺时针方向围坐一圈，每个人只有一个密码（正整数）”内容要求一致，而且，循环链表中

3、任一结点出发均可找到表中其他结点，利用这一优点可较容易地找出报数的人及下一个报数的人，最后按照出列的顺序用一个for语句实现。joseph环的组成成员由密码（password）和序号(No)组成，循环链表的存储结构如下：typedef struct LNode int password; /密码 int No; /序号 struct LNode *next; /下一成员指针member; /组成成员结构体13流程图 根据算法思想，画程序流程图如下：14 源代码1.3详细设计typedef struct LNode int password; /密码 int No; /序号 struct LNo

4、de *next; /下一成员指针member; /组成成员结构体typedef int status;#define OVERFLOW -2 #define OK 1 #define ERROR 0#include #include status CreateList_Circle(member *,int);status DeleteNode(member *);status main() int n,m; member *head=NULL,*p=NULL; /头指针即首成员地址，遍历指针p printf (Please enter number of people:n); scanf

5、(%d,&n); /总成员数 while (n=0) printf (n must be positive, please enter again:n); scanf (%d,&n); if(!CreateList_Circle(&head,n) /创建循环链表，返回头指针head return OVERFLOW; printf (Please enter initial m:n); scanf (%d,&m); /初始值m while (m=2) /寻找出列成员 int i; m=(m%n=0)?n:m%n; /化简m值 for (i=1;inext; /p指向出列成员 printf (%d

6、n,p-No); /输出出列成员序号 m=p-password; /修改m DeleteNode(&p); /删除链表中的出列成员 n-; /成员数自减 printf (%dn,p-No); /输出最后一个成员序号 return OK;status CreateList_Circle(member *p_head,int n) /此算法创建一个无头结点的循环链表，结点数n,*p_head返回链表头指针即首结点地址 int i; member *tail,*p; *p_head=(member *)malloc(sizeof(member); if (!(*p_head) return OVER

7、FLOW; (*p_head)-No=1; /储存成员一序号 printf (Please enter password of No. 1:n); scanf (%d,&(*p_head)-password); /储存成员一密码 tail=*p_head; tail-next=NULL; for (i=2;iNo=i; /储存成员序号 printf (Please enter password of No. %d:n,i); scanf(%d,&(p-password); /储存成员密码 tail-next=p; tail=p; tail-next=*p_head; return OK;sta

8、tus DeleteNode(member *pp) /此算法删除链表中的结点*pp,操作实质是将*pp下一结点复制到*pp后将其free member *temp; (*pp)-password=(*pp)-next)-password; (*pp)-No=(*pp)-next)-No; temp=(*pp)-next; (*pp)-next=(*pp)-next-next; free(temp); return OK;15 结果与分析.4 测试及性能分析 1此程序的时间复杂度是O(m*n)。2本次设计主要用到了循环链表的相关知识，求joseph环的问题。调试过程中，一开始没有想到“指向指针

9、数据的指针变量”，使得问题一直没有明朗。3是否需要化简m值的语句：m=(m%n=0)?n:m%n;可根据m与总成员数的值的大小来判断。当m=n时，则此步是可以删除的；当mn时，则此步最好不删除，特别是当输入的m值很大，则化简m值的操作是很必要。 4. 遇到的问题主要是：指针的指向的边界问题，但根据运行程序时的出错提示，很快也就解决了。5.测试的结果如下：课题二 拓扑排序21 问题的提出2.1 问题的提出 任务：编写函数实现图的拓扑排序。程序所实现的功能：建立对应的邻接表，对该图进行拓扑排序，并显示排序结果。输入：顶点数, 边数及各顶点信息(数据格式为整形) 输出： 拓扑排序结果。 2. 2 概

10、要设计 1.拓扑排序是指由某个集合上的一个偏序得到该集合上的一个全序。更直观地讲，一个偏序是自反的、反对称的，用图表示时每个点都有环且只有单向边。拓扑排序的任务是在这个偏序上得到一个全序，即得到一个完成整个项目的各步骤的序列。2解决拓扑排序的方法如下：（1）在有向图中选一个没有前驱的顶点且输出之。（2）从图中删除该顶点和所有以它为尾的弧。重复上述两步，直至全部顶点均已输出，或者当前图中不存在无前驱的顶点为止。后一种情况则说明有向图中存在环。具体的算法实现参照源程序。3构造邻接表图：typedef struct AdjList vertices; int vexnum,arcnum;Graph;

11、/邻接表图 4. 为了避免重复检测入度为零的顶点，源程序中设了一个栈，暂存所有入度为零的顶点：typedef struct stackint *base;int *top;int stacksize;sqstack;/栈的结构，存储图的顶点序号23 流程图2.根据算法思想，画流程图如下：24 源代码/采用尾插法创的邻接图#includeusing namespace std;const int MAX=20;const int STACK_INIT_SIZE=100;const int ERROR=0;typedef struct stackint *base;int *top;int sta

12、cksize;sqstack;/栈的结构，存储图的顶点序号typedef struct lnodeint adjvex;struct lnode *next;ArcNode;/弧结点typedef struct node2char data;ArcNode *fristarc;VNode,AdjListMAX;/顶点数组,fristarc指向与顶点邻接的第一条弧typedef struct AdjList vertices; int vexnum,arcnum;Graph;/邻接表图void Initstack(sqstack &s)s.base=new int;if(!s.base)exit

13、(0);s.top=s.base;s.stacksize= STACK_INIT_SIZE;void Push(sqstack &s,int &e)*s.top+=e;int Emptystack(sqstack &s)if(s.base=s.top)return 1;elsereturn 0;int Pop(sqstack &s,int &e)if(s.base=s.top)return ERROR;e=*-s.top;void CreatGraph(Graph &G,int *indegree) cout请输入图的顶点数和弧数(且顶点数不能超过MAX)G.vexnumG.arcnum;co

14、ut请输入顶点值:endl;for(int i=0;iG.verticesi.data;G.verticesi.fristarc=NULL;indegreei=0;for(i=0;iG.arcnum;i+)/输入图的弧int m,n;ArcNode *p;cout请输入第i+1条弧的弧尾和弧头:mn;p=new ArcNode;if(!p)exit(0);indegreen-1+;/求每个顶点的入度值p-adjvex=n-1;p-next=G.verticesm-1.fristarc;G.verticesm-1.fristarc=p;int Toposort(Graph &G,int *ind

15、egree)sqstack S;Initstack(S);for(int i=0;iG.vexnum;i+)/0入度顶点入栈if(!indegreei)Push(S,i); int count=0; while(!Emptystack(S) Pop(S,i); coutG.verticesi.datanext)/把与顶点 /相邻接的顶点的入度 int k=p-adjvex; if(!(-indegreek) Push(S,k); if(countG.vexnum) return 0; else return 1;int main() Graph G; int *indegree; indegr

16、ee=new int; CreatGraph(G,indegree); if(!Toposort(G,indegree) coutendl; cout拓扑排序不成功!endl; else coutendl; cout拓扑排序成功!endl; return 0;25 结果与分析2.4 测试及性能分析1它的时间复杂度是O(G.vexnum+G.arcnum)。2. 整个程序的关键就是采用尾插法创的邻接表图，运用栈来实现各个数值的输入输出及存储。3注意*的使用，并不是什么情况下都用*，它有时候会造成数据破坏，利用破坏的值进行运算，结果可想而知，所以，如果没返回值时，一般不要用。4 为了避免重复检测入

17、度为零的顶点，源程序中设了一个栈，暂存所有入度为零的顶点，此程序段书写如下：InitStack(S); for (i=0;inext)k=p-adj; /对i号顶点的每个邻接点的入度减1if(!(-indegreek) Push(S,k); /一旦入度为0，则入栈/for/while5 测试的数据如下：第一组结果（有向无环图）：第二组结果（有向有环图）： 第一组对应的图如下：15432第二组对应的图如下：15432课题三 纸牌游戏31 问题的提出.1 问题的提出 任务：编号为1-52张牌，正面向上，从第2张开始，以2为基数，是2的倍数的牌翻一次，直到最后一张牌；然后，从第3张开始，以3为基数，

18、是3的倍数的牌翻一次，直到最后一张牌；然后从第4张开始，以4为基数，是4的倍数的牌翻一次， 直到最后一张牌；.再依次5的倍数的牌翻一次，6的，7的 直到 以52为基数的 翻过，输出：这时正面向上的牌有哪些？ 输出的纸牌号为：1 4 9 16 25 36 493. 2 概要设计 1.当每个号码每次遇到是某个数的倍数时，都会相应的翻一次，这样，每张牌会翻的次数就各不一样，可能很多次，也可能只有一两次，结果就只是要输出在经过各个不同次数的翻牌后，正面向上的牌都有哪几个。举例说明一下，比如24，第一次它是2的倍数时要从正面翻到背面，当进行到3时，就又要从背面翻回来，而到4时还要在翻，同理呢，到它都要来

19、回的翻。如果它在多次的翻牌后，正面还向上了，那么它就是要输出的结果之一。2用#define OPPOSITE(i) i = i?0:1这个宏将牌的状态标志求反,也即为翻牌操作。将所有的牌建立一个数组，运用for的循环嵌套执行以下操作：把52张牌初始化成正面朝上、控制基数和翻牌次数，判断最终的纸牌朝向并打印出结果，具体实现算法参看详细设计。33流程图 根据算法思想，画流程图如下：开始设一个一维数组card52，并将所有变量赋初值为0，表示牌正面朝上2=jj52j=kk52k%j=0翻牌，如果cardk-1为0，则变为1；如果为1，则变为0k+输出card数组中正面朝上的牌的序号结束j+34 源代

20、码 #include #define OBVERSE 0 /正面朝上 #define ADVERSE 1 /背面朝上 #define OPPOSITE(i) i = i?0:1 /这个宏是将牌的状态标志求反,也即为翻牌操作 void main() int card52;/52张牌for (int i = 0; i 52; i+) cardi = OBVERSE; /将52张牌初始化成正面朝上 for (int j=2; j=52; j+) /此层循环是控制基数的 for (int k = j; k = 52 ; k+)/此层循环是控制从第几张牌开始 if (k%j = 0)/判断第k张牌除以基

21、数j后的余数是否为0,如为0就是能整除 OPPOSITE(cardk-1);/翻牌 for (int h = 0; h 52; h+)/开始打印 if (cardh = OBVERSE)/判断牌的状态是否为正面朝上 printf(第%d张牌正面朝上n, h+1); 35 结果与分析 1这题的时间复杂度是O(52)。 2虽然本次程序的题目难度与其他问题相比不是很高，但仍有很多问题我们是很容易忽视的，其一：在理解题目的要求时，注意翻牌的次数可能有多次；其二：for循环的嵌套使用在书写时很容易漏掉大括弧。 3运用更多的基础算法，使得程序和算法思想得到更好的表现，为增强算法的可读性，则算法改进如下：#

22、include void main() int i,j,card52; for(i=0;i52;i+)/52张牌所有状态均为1，即均为正面 cardi=1; for(j=2;j=52;j+) /对52张牌（序号放在i里）对2，3.52（放在j里）按i+1是否是j的倍数进行状态翻转。 for(i=0;i52;i+) if(i+1)%j=0) cardi=cardi?0:1; printf(positive card are:); for(i=0;i52;i+)/对翻转处理后状态仍然是正面的（card保持为1）的将其编号输出。 if(cardi) printf(%d ,i+1); 4测试的结果如下： 课程设计总结 这个学期是我第一次接触数据结构，也是我第一次接触“课程设计”，在完成设计的过程中，我遇到了一系列的问题，能明显感觉到自己在很多方面的不足，但另一方面，问题是要分析解决的，找出问题以便为完善学习计划，改变学习内容与方法提供实践依据。所以在整个过程中，我不断加深了对数据结构的理解与一些程序写书时要注意的事项，体会了数据结构这门课程在解决现实生活问题上的可行性，也更进一步地激发了我的学习热情。 做一个课程设计要注意很多方面，无论是格式，还是