《约瑟夫环问题可惜设计.doc》由会员分享，可在线阅读，更多相关《约瑟夫环问题可惜设计.doc（46页珍藏版）》请在三一文库上搜索。
1、1. 设计1 约瑟夫环问题 一、需求分析1、利用单向循环链表存储结构模拟此过程，按照出列的顺序印出个人的编号，只适用于一个案例。具体目标包括： （1）实现单循环链表的初始化； （2）理解约瑟夫环的定义，用循环找到每次报数人的序号； （3）从单循环链表中删除节点，并判断链表空与非空的临界条件。2、构造一个含有n个元素的单向循环链表3、程序中，先输入总人数 PN与初始密码SN，再输入输入 n 个正整数，作为这n个人的密码，接下来初始密码 m。4、测试数据 PN=5 SN=2 ，N 个人的密码依次 = 1 4 6 4 8。 出列为：2 1 3 5 4。二、概要设计1、函数功能在main函数中实现vo
2、id main(void)int PN, SN,i;LinkList L; printf(请输入总人数PN,和出示密码SN：);scanf(%d%d,&PN,&SN);int aN;a0=SN;/将a0保存为初始密码printf(请输入%d个人各自所持的密码:n,PN);for(i=1;idata = 1;for (i=2;idata=i;p-next=q;p=q;p-next =(*L);流程图：结束p-next=headp=qP-next=p2head=qi=1q指向申请空间i=np指向申请空间 2、程序主模块实现算法从头结点开始，根据报数上限找到下一个出列人的序号，并读出该人的密码作为新
3、的报数上限，从此节点的下一个节点开始进行新的查找。取每次将要删除的人的密码，用于下次报数的上限.通过指针依次删除出列人相应的节点，直到该链表中无节点，退出循环。四、运行结果及分析1.调试分析（1）进入程序后按提示输入程序初始数据回车后即可得到结果，输出结果表示依次出列人的序号，程序结束。若输入过程中输入有误，程序直接结束。算法时间复杂度正比于2n加上所有人的密码和。（2）结果分析：对一般数据与边界数据能输出正确结果；对错误数据能做出合适的反应。2.测试结果输入值不符合条件是：五、总结1.本程序比较简单，只有一个main函数，功能在main函数中实现，程序有待优化。本次实验主要考察了对单循环链表
4、的应用。2.调试过程中，由于指针使用不当多次出现错误，对指针的设计还需要熟练掌握。通过本次实验设计，巩固了演循环链表的知识。附：主要源代码#include#include#define N 100typedef struct Nodeint data;/将这一圈人按从1PN贴上序号struct Node *next;Node,*LinkList;void CreatLinkList(LinkList *L,int PN)Node *p, *q;int i; (*L) = (LinkList)malloc(sizeof(Node);p = (*L);p-data = 1;for (i=2;ida
5、ta=i;p-next=q;p=q;p-next =(*L);void deldata(LinkList *L,int PN,int a)Node *p, *q;int k;int j=1;int i=0;/取每次将要删除的人的密码，用于下次报数的上限p=(*L);for (;PN=1;PN-)k=1;while(k!=ai)p=p-next;k+;printf(第%d个出列的人的序号是%d，其密码是%d.n, j, p-data,aj);j+;i=p-data;p-data=p-next-data;q=p-next;p-next = p-next-next;free(q); void mai
6、n(void)int PN, SN,i;LinkList L; printf(请输入总人数PN,和出示密码SN：);scanf(%d%d,&PN,&SN);int aN;a0=SN;/将a0保存为初始密码printf(请输入%d个人各自所持的密码:n,PN);for(i=1;iPN+1;i+)scanf(%d,&ai);/创建链表CreatLinkList(&L, PN);/报数删人，输出结果printf(Result:n);deldata(&L,PN,a);2. 设计2 前缀算术表达式转换及表达式计算一、需求分析1.问题描述：算术表达式与二叉树之间存在着对应关系，编写把以前缀形式输入的合法算
7、术表达式转换为中缀表达式，再转换为后缀表达式，并求表达式的值。2.具体目标包括：（1） 把前缀表达式转换为中缀表达式；（2） 输出中缀表达式；（3） 把中缀表达式转换为后缀表达式；（4） 利用栈结构实现后缀表达式的求值；3定义栈的抽象数据类型：ADT Stack 数据对象： D ai|ai ElemSet,i=1,2,.,n,n0 数据关系： R1 | ai-1, aiD, i=2,.,n 基本操作：InitStack(SqStack *S)Push(SqStack *S,SNodeEType e)Pop(SqStack *S,SNodeEType *e)StackEmpty(SqStack
8、*S) ADT Stack二、概要设计1、程序包括两部分（1）结点类型typedef struct BiTNode TElemType data; struct BiTNode *lchild,*rchild;BiTNode,*BiTree;typedef struct Node SNodeEType data; struct Node *next;SElemType;typedef struct Stack SElemType *base; SElemType *top;SqStack;typedef struct QNode/队列QElemType data; struct QNode *
9、next;QNode,*QueuePtr;typedef struct QueuePtr front; QueuePtr rear; LinkQueue;（2）基本操作的实现（见附：主要源代码）2、主要模块主模块 main()队列初始化输入算术表达式输出算术表达式三、详细设计（含主要算法的流程图）1、删除栈顶元素并返回其值的算法int Pop(SqStack *S,SNodeEType *e)int *e1;if(S-top =S-base)return ERROR;*e=S-top-data;e1=S-top;S-top=S-top-next;free(e1);return OK;2、BiT
10、ree CreatBiTree(BiTree T)/按前缀形式输入算术表达式，构造二叉链表表示的二叉树Tchar ch;scanf(%c,&ch); switch(ch) case +: ; case -: ; case *: ; case /: if(!(T=(BiTNode *)malloc(sizeof(BiTNode) exit(OVERFLOW); T-data=ch; T-lchild=(BiTNode *)malloc(sizeof(BiTNode); T-rchild=(BiTNode *)malloc(sizeof(BiTNode); T-lchild=CreatBiTree
11、(T-lchild); T-rchild=CreatBiTree(T-rchild);break; default: if(!(T=(BiTNode *)malloc(sizeof(BiTNode) exit(OVERFLOW); T-data=ch; T-lchild=NULL; T-rchild=NULL;return T;实现流程图：scanf(“%c”,&ch)case+case*case-case/!(T=(BiTNode*)malloc(sizeof(BiTNode)exitT-data=ch;T-lchild=(BiTNode*)malloc(sizeof(BiTNode);T-
12、rchild=(BiTNode*)malloc(sizeof(BiTNode);T-lchild=CreatBiTree(T-lchild)T-rchild=CreatBiTree(T-rchild);default!(T=(BiTNode*)malloc(sizeof(BiTNode)T-data=ch;T-lchild=NULL;T-rchild=NULL;return ok四、运行结果及分析五、总结1、调试过程中遇到的问题：在调试过程中，插入新结点时，结点指针指的位置不对，导致添加后的二叉树不符合；在输出二叉树时由于输出算法错误导致输出不正确，经过网上找了一些材料，最后输出正确。 2、编
13、写程序时必须注意一些细小的问题，对临界问题考虑全面，养成良好的编程习惯。熟练掌握算术表达式与二叉树的性质与算法，巩固算术表达式之间的转换算法以及后序遍历的递归算法实现树的输出算法。附：主要源代码#include#include#include#define MAXSIZE 100#define TElemType char#define QElemType char#define SNodeEType float#define OK 1#define OVERFLOW 0#define TRUE 1#define FALSE 0#define ERROR 0#define status int
14、typedef struct BiTNode TElemType data; struct BiTNode *lchild,*rchild;BiTNode,*BiTree;typedef struct Node SNodeEType data; struct Node *next;SElemType;typedef struct Stack SElemType *base; SElemType *top;SqStack;typedef struct QNodeQElemType data; struct QNode *next;QNode,*QueuePtr;typedef struct Qu
15、euePtr front; QueuePtr rear; LinkQueue;status InitQueue(LinkQueue *Q)/构造一个空队列Qif(!(Q-rear=(QueuePtr)malloc(sizeof(QNode)exit(OVERFLOW); Q-front=Q-rear;Q-front-next=NULL;return OK;status EnQueue(LinkQueue *Q,QElemType e)/插入以e为Q的新的队尾元素 QueuePtr p; if(!(p=(QueuePtr)malloc(sizeof(QNode) exit(OVERFLOW);
16、p-data=e; p-next=NULL; Q-rear-next=p; Q-rear=p; return OK;status DeQueue(LinkQueue *Q,QElemType *e)/删除Q的队头元素，用e返回其值 QueuePtr p; p=Q-front-next; *e=p-data; Q-front-next=p-next; if(Q-rear=p) Q-rear=Q-front; free(p); return OK;status InitStack(SqStack *S) /构造一个空栈SS-base=(SElemType *)malloc(sizeof(SElem
17、Type);if(!S-base)exit(OVERFLOW); /存储分配失败S-top=S-base;return OK; /InitStackvoid Push(SqStack *S,SNodeEType e) /插入元素e为新的栈顶元素SElemType *e1;e1=(SElemType *)malloc(sizeof(SElemType);e1-next=S-top;e1-data=e;S-top=e1;/Pushstatus Pop(SqStack *S,SNodeEType *e) /若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK,否则返回ERRORSElemType
18、*e1;if(S-top =S-base)return ERROR;*e=S-top-data;e1=S-top;S-top=S-top-next;free(e1);return OK; status StackEmpty(SqStack *S) /判断栈S是否为空，若不空返回TRUE,否者返回FALSEif(S-top=S-base)return TRUE;else return FALSE;BiTree CreatBiTree(BiTree T)/按前缀形式输入算术表达式/构造二叉链表表示的二叉树Tchar ch; scanf(%c,&ch); switch(ch) case +: ; c
19、ase -: ; case *: ; case /: if(!(T=(BiTNode *)malloc(sizeof(BiTNode) exit(OVERFLOW); T-data=ch; T-lchild=(BiTNode *)malloc(sizeof(BiTNode); T-rchild=(BiTNode *)malloc(sizeof(BiTNode); T-lchild=CreatBiTree(T-lchild); T-rchild=CreatBiTree(T-rchild); break; default: if(!(T=(BiTNode *)malloc(sizeof(BiTNo
20、de) exit(OVERFLOW); T-data=ch; T-lchild=NULL; T-rchild=NULL; return T;status InOrderT(BiTree T) /中序遍历二叉树if(T)InOrderT(T-lchild);printf(%c,T-data);InOrderT(T-rchild);return OK;status AfterOrderT(BiTree T,LinkQueue *Q) char e; /后序遍历二叉树if(T)AfterOrderT(T-lchild,Q);AfterOrderT(T-rchild,Q);printf(%c,T-da
21、ta);e=T-data;EnQueue(Q,e);return OK;status Jisuan(SNodeEType *e1,SNodeEType e2,char ch)switch(ch)case +: *e1=*e1+e2;break; case -: *e1=e2-*e1;break; case *: *e1=*e1*e2;break; case /:*e1=e2/(*e1);break;return OK;status Oper(LinkQueue *Q)SqStack *S;char ch;int sag=1;SNodeEType e1,e2,e;if(!(S=(SqStack
22、*)malloc(sizeof(SqStack) exit(OVERFLOW);while(Q-front!=Q-rear)DeQueue(Q,&ch);switch(ch)case +: ;case -: ;case *: ;case /:Pop(S,&e1);Pop(S,&e2); Jisuan(&e1,e2,ch);Push(S,e1);break;default:if(sag=1)printf(有几个变量？按行输入)为变量赋值：);sag=0;scanf(%f,&e); Push(S,e);Pop(S,&e1);printf(结果为：%3fn,e1);return OK;void ma
23、in()BiTNode *T; LinkQueue *Q; Q=(LinkQueue *)malloc(sizeof(LinkQueue);InitQueue(Q); T=(BiTNode *)malloc(sizeof(BiTNode);T-lchild=NULL; T-rchild=NULL; printf(按前缀形式输入算术表达式n);printf(请输入前缀表达式:);T-lchild=CreatBiTree(T-lchild);printf(中序表达式：); InOrderT(T-lchild);printf(n);printf(后序表达式：);AfterOrderT(T-lchil
24、d,Q);printf(n);Oper(Q);3. 设计3 矩阵乘法和加法算法的应用一、 需求分析1.问题描述：设A=，给定A上的关系R为R=, , , ，求R的传递闭包。2.具体目标： 设定一个关系R（矩阵），执行本程序，自动求出R的传递闭包。二、概要设计1.函数功能在main函数中实现。函数调用关系：在Main()中调用work（）,实现程序的主要功能。int main(int argc, char* argv)int R1010;int n,i,j;printf(请输入关系矩阵的维数n);scanf(%d,&n);printf(请输入关系矩阵R n);for(i=0;in;i+)for(
25、j=0;jn;j+)scanf(%d,&Rij);work(R,n);return 0;2.算法描述：在集合X上的二元关系R的传递闭包是包含R的X上的最小的传递关系。R的传递闭包在数字图像处理的图像和视觉基础、图的连通性描述等方面都是基本概念。一般用B表示定义在具有n个元素的集合X上关系R的nn二值矩阵，则传递闭包的矩阵B+ = B + B2 + B3 + + (B)n式中矩阵运算时所有乘法都用逻辑与代替，所有加法都用逻辑或代替。上式中的操作次序为B，B(B)，B(BB)，B(BBB)，以此类推。所以在运算的每一步我们只需简单地把现有结果乘以B，完成矩阵的n次乘法即可。三、详细设计1.主程序（
26、实现主要功能）int main(int argc, char* argv)int R1010;int n,i,j;printf(请输入关系矩阵的维数n);scanf(%d,&n);printf(请输入关系矩阵R n);for(i=0;in;i+)for(j=0;jn;j+)scanf(%d,&Rij);work(R,n);return 0;2.void work(int R1010,int n) 求矩阵R的传递闭包；将输入的矩阵R赋值给矩阵M；用M的行乘以R的列得到Rn ，并将Rn赋值给M；最后将R1R2R3R4 .Rn相加的结果赋给R；将矩阵R中非0元素置换为1；输出传递闭包；四、运行结果及
27、分析正确的运行结果：五、总结编写程序过程中，由于对矩阵相乘的性质和算法掌握不牢固，所以在程序运行遇到了一些问题。在集合X上的二元关系R的传递闭包是包含R的X上的最小的传递关系。R的传递闭包在数字图像处理的图像和视觉基础、图的连通性描述等方面都是基本概念。这些都是本实验设计所需的一些基本知识，但是由于学习是掌握不牢固，拿到题目时只能先巩固基础知识，这样就花费了不少时间。附：主要源代码/#include stdafx.h#include stdio.h#include stdlib.hvoid work(int R1010,int n) /求矩阵R的传递闭包int i,j,k,m;int M101
28、0;int a=0;for(i=0;in;i+)for(j=0;jn;j+)Mij=Rij;for(m=1;mn;m+)for(i=0;in;i+)for(j=0;jn;j+)for(k=0;kn;k+)a=a+Mik*Rkj;Mij=a;Rij=Rij+Mij;a=0;for(i=0;in;i/ 将矩阵R中非0元素置换为1for(j=0;jn;j+)if (Rij=0)continue ;elseRij=1;printf(传递闭包关系矩阵t:n);for(i=0;in;i+)for(j=0;jn;j+)printf(%d ,Rij);printf(n);int main(int argc,
29、char* argv)int R1010;int n,i,j;printf(请输入关系矩阵的维数n);scanf(%d,&n);printf(请输入关系矩阵R n);for(i=0;in;i+)for(j=0;jn;j+)scanf(%d,&Rij);work(R,n);return 0;4. 设计4 有向无环图每个顶点出发的最短路径及其长度 一、需求分析1.问题描述：生成一个有向无环图，并用邻接表存储它。2.要求：求从该有向无环图的每个顶点出发的最短路径及其长度，并估计算法的时间复杂度。3.具体目标包括：1、生成一个有向无环图2、用邻接表存储3、从有向无环图的每个顶点出发求其最长路径和它的长
30、度。二、概要设计1.函数功能在main函数中实现void main() ALGraph *G; G=(ALGraph *)malloc(sizeof(ALGraph); CreatDG(G); CriticalPath(G);2.定义抽象数据类型ADT Graph 数据对象: V是具有相同特性的数据元素的集合，称为顶点集； 数据关系：R=VR,VR| v,wV 且 P(v,w)表示从 v 到 w 的一条弧，并称 v 为弧尾，w 为弧头。谓词 P(v,w) 定义了弧 的意义或信息。基本操作：CreatGraph(&G, V, VR): 操作结果： 按定义(V, VR) 构造图InsertVex(
31、&G, v); 操作结果：在图G中增添新顶点v。DeleteVex(&G, v);操作结果： 删除G中顶点v及其相关的弧。DFSTraverse(G, v, Visit(); 操作结果：从顶点v起深度优先遍历图G，并对每个顶点调用函数Visit一次且仅一次三、详细设计1、程序包括两部分（1）结点类型定义typedef struct ArcNode int adjvex; /改弧所指向的定点 struct ArcNode *nextarc; /指向下一条弧的指针 InfoType info; /权重ArcNode;typedef struct VNode VertexType data; /顶点
32、信息 ArcNode *firstarc; /指向第一条依附于改顶点的弧的指针VNode,AdjListMAX_VERTEX_NUM;typedef struct AdjList vertices; int vexnum,arcnum;/图的当前顶点数和弧数ALGraph;typedef struct Node SNodeEType data; struct Node *next;SElemType;typedef struct StackSElemType *base; SElemType *top;SqStack;（2）基本操作的实现（见附：主要源代码）2.采用邻接表的存储表示，构造一个有
33、向图大体流程图：Return ok给p申请一个空间；p-adjvex=j;p-nextarc=G-verticesi.firstarc;G-verticesi.firstarc=p;p-info=wk+;i=locatevex(G,v1)j=locate(G,v2)输入各个顶点的值Karcnum输入各个弧尾，弧头权重int i ,j,k,w ;char v1,v2;ArcNode *p四、运行结果及分析五、总结本实验要求生成一个有向无环图，并用邻接表存储它。利用栈的结果，求有向无环图的关键路径。编写程序过程中，由于对图的性质和算法掌握的比较好， 所以在程序运行遇到了一些问题。通过查看课本，逐步
34、完善了程序，实现了主要功能。例如，每输入一个结点都要判别是在该边的哪个指针域，增加了时间复杂度，有待改进。程序的时间复杂度依赖于输入的结点和边的信息。附：主要源代码#include#include#include#define MAX_VERTEX_NUM 50#define InfoType int#define VertexType char#define status int#define SNodeEType int#define OK 1#define OVERFLOW 0#define TRUE 1#define FALSE 0#define ERROR 0typedef stru
35、ct ArcNode int adjvex; /改弧所指向的定点 struct ArcNode *nextarc; /指向下一条弧的指针 InfoType info; /权重ArcNode;typedef struct VNode VertexType data; /顶点信息 ArcNode *firstarc; /指向第一条依附于改顶点的弧的指针VNode,AdjListMAX_VERTEX_NUM;typedef struct AdjList vertices; int vexnum,arcnum;/图的当前顶点数和弧数ALGraph;typedef struct Node SNodeET
36、ype data; struct Node *next;SElemType;typedef struct StackSElemType *base; SElemType *top;SqStack;status InitStack(SqStack *S)S-base=(SElemType *)malloc(sizeof(SElemType);if(!S-base)exit(OVERFLOW); /存储分配失败S-top=S-base;return OK; /InitStackvoid Push(SqStack *S,SNodeEType e) /插入元素e为新的栈顶元素 SElemType *e
37、1;e1=(SElemType *)malloc(sizeof(SElemType);e1-next=S-top;e1-data=e;S-top=e1;/Pushstatus Pop(SqStack *S,SNodeEType *e) /若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK,否则返回ERRORSElemType *e1;if(S-top =S-base)return ERROR;*e=S-top-data;e1=S-top;S-top=S-top-next;free(e1);return OK;status StackEmpty(SqStack *S) /判断栈S是否为空，若不空返回TRUE,否者返回FALSEif(S-top=S-base)return TRUE;elsereturn FALSE;status LocateVex(ALGraph *G,char vl) int i; for(i=0;ivexnum;i+) if(vl=G-verticesi.data) return i; printf(输入错误); return 0;status FindInDegree(ALGraph *G,int *indegree) int i,k; ArcNode *p; for(i=0;i