《课程设计说明书》模版.doc

山东科技大学学生课程设计1. 设计1 约瑟夫环问题 一、需求分析1、利用单向循环链表存储结构模拟此过程，按照出列的顺序印出个人的编号，只适用于一个案例。具体目标包括： （1）实现单循环链表的初始化； （2）理解约瑟夫环的定义，用循环找到每次报数人的序号； （3）从单循环链表中删除节点，并判断链表空与非空的临界条件。2、构造一个含有n个元素的单向循环链表ADT CircleList 数据对象：Dai | aiElemset,i=1,2,n,n0 数据关系：R=, | ai-1,aiD,i=2,n 基本操作：Link InitList（int n）操作结果：构造一个含有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函数中实现void 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);流程图1结束p-next=headp=qP-next=p2head=qi=1q指向申请空间i=np指向申请空间 2、程序主模块实现算法从头结点开始，根据报数上限找到下一个出列人的序号，并读出该人的密码作为新的报数上限，从此节点的下一个节点开始进行新的查找。取每次将要删除的人的密码，用于下次报数的上限.通过指针依次删除出列人相应的节点，直到该链表中无节点，退出循环。输入总人数与初始密码jnm=1?inexei=i+1=1q=head-next输出q的numbermnext-number删除q节点初始化一个单循环链表四、运行结果及分析1.调试分析（1）进入程序后按提示输入程序初始数据回车后即可得到结果，输出结果表示依次出列人的序号，程序结束。若输入过程中输入有误，程序直接结束。算法时间复杂度正比于2n加上所有人的密码和。（2）结果分析：对一般数据与边界数据能输出正确结果；对错误数据能做出合适的反应。2.测试结果输入值不符合条件是：五、总结1.本程序比较简单，只有一个main函数，功能在main函数中实现，程序有待优化。本次实验主要考察了对单循环链表的应用。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;idata=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 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;iPN+1;i+)scanf(%d,&ai);/创建链表CreatLinkList(&L, PN);/报数删人，输出结果printf(Result:n);deldata(&L,PN,a);2. 设计2 迷宫问题 一、需求分析1.问题描述：算术表达式与二叉树之间存在着对应关系，编写把以前缀形式输入的合法算术表达式转换为中缀表达式，再转换为后缀表达式，并求表达式的值。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 *S) ADT Stack二、概要设计1、主模块（函数功能在main函数中实现） Void main() 新建栈，队列，树，并实现初始化； 接受命令； 处理命令；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;流程图12、BiTree 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(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;流程图2scanf(“%c”,&ch)case+case*case-case/!(T=(BiTNode*)malloc(sizeof(BiTNode)exitT-data=ch;T-lchild=(BiTNode*)malloc(sizeof(BiTNode);T-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四、运行结果及分析五、总结本程序主要应用三元组处理矩阵，利用矩阵的加法和乘法求自反闭包、对称闭包和传递闭包附：主要源代码#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 inttypedef 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 *next;QNode,*QueuePtr;typedef struct QueuePtr 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); 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(SElemType);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 *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 +: ; 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(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;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-data);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 *)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 main()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-lchild,Q);printf(n);Oper(Q);3. 设计3 矩阵乘法和加法算法的应用一、 需求分析1.问题描述：设A=，给定A上的关系R为R=, , , ，求R的传递闭包。2.具体目标： 设定一个关系R（矩阵），执行本程序，自动求出R的传递闭包。二、概要设计1.函数功能在main函数中实现。函数调用关系：Nain()Work()2.算法描述：在集合X上的二元关系R的传递闭包是包含R的X上的最小的传递关系。R的传递闭包在数字图像处理的图像和视觉基础、图的连通性描述等方面都是基本概念。一般用B表示定义在具有n个元素的集合X上关系R的nn二值矩阵，则传递闭包的矩阵B+可如下计算： B+ = B + B2 + B3 + + (B)n式中矩阵运算时所有乘法都用逻辑与代替，所有加法都用逻辑或代替。上式中的操作次序为B，B(B)，B(BB)，B(BBB)，所以在运算的每一步我们只需简单地把现有结果乘以B，完成矩阵的n次乘法即可。三、详细设计1.主程序请输入关系矩阵的维数 请输入关系矩阵调用work函数 return 0;2.void work(int R1010,int n) 求矩阵R的传递闭包定义一个矩阵M将输入的矩阵R赋值给矩阵M用M的行乘以R的列得到Rn ，并将Rn赋值给M最后将R1R2R3R4 .Rn相加的结果赋给R / 将矩阵R中非0元素置换为1输出传递闭包四、五、总结附：主要源代码/#include stdafx.h#include stdio.h#include stdlib.hvoid work(int R1010,int n) /求矩阵R的传递闭包int i,j,k,m;int M1010;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, 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、从有向无环图的每个顶点出发求其最长路径和它的长度。二、概要设计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(&G, v); 操作结果：在图G中增添新顶点v。DeleteVex(&G, v);操作结果： 删除G中顶点v及其相关的弧。DFSTraverse(G, v, Visit(); 操作结果：从顶点v起深度优先遍历图G，并对每个顶点调用函数Visit一次且仅一次三、详细设计采用邻接表的存储表示，构造一个有向图：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 *pTopologicalOrder：int indegree ,i,j,k;sqstack *s;ArcNode *p;对各个顶点求入度；建入度顶点栈ivexnumi+Indegreei=0Push(s,i)栈不为空Pop(S,&j);Push(T,j);+count;P!=NULLp=p-nextarc；k=p-adjvex;-indegreek=0Push(S,k);vej+p-infovekvek=vej+p-info;int veMAX_VERTEX_NUM=0int vlMAX_VERTEX_NUM=0;int i,j,ee,dut,k,el;char tag;SqStack *T;ArcNode *p;P!=NULL vli=veG-vexnum-1ivexnu i+;k=p-adjvex;dut=p-info;vlk-dutvlj vlj=vlk-dut;jvexnumP!=NULLp=p-next;P=k=p-adjvex;dut=p-info;ee=vej;el=vlk-dut;tag=(ee=el)?*: e=el return ok输出数据和路径+jp=p-nextarc四、运行结果及分析五、总结利用栈的结果，求有向无环图的关键路径。附：主要源代码#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 struct 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 /栈SNodeEType data; struct Node *next;SElemType;typedef struct StackSElemType *base; SElemType *top;SqStack;status InitStack(SqStack *S) /构造一个空栈SS-base=(SElemType *)malloc(sizeof(SElemType);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 *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;ivexnum;i+) for(p=G-verticesi.firstarc;p;p=p-nextarc) k=p-adjvex; indegreek+; return OK;status CreatDG(ALGraph *G)/采用邻接表的存储表示，构造一个有向图G int i,j,k,w; char v1,v2; ArcNode *p; printf(输入图的顶点数和弧数：); scanf(%d %d,&G-vexnum,&G-arcnum); printf(输入所有顶点值：); for(i=0;ivexnum;i+) getchar(); scanf(%c,&G-verticesi.data); G-verticesi.firstarc=NULL; /构造表头向量printf(输入各弧弧尾，弧头，权重：); for(k=0;karcnum;k+) getchar(); scanf(%c,%c,%d,&v1,&v2,&w); i=LocateVex(G,v1); j=LocateVex(G,v2); if(!(p=(ArcNode *)malloc(sizeof(ArcNode) exit(OVERFLOW); p-adjvex=j; p-nextarc=G-verticesi.firstarc; G-verticesi.firstarc=p; p-info=w; return OK;status TopologicalOrder(ALGraph *G,SqStack *T,int *ve) int indegreeMAX_VERTEX_NUM=0,count=0; int i,j,k; SqStack *S; ArcNode *p; if(!(S=(SqStack *)malloc(sizeof(SqStack) exit(OVERFLOW); FindInDegree(G,indegree);/对各顶点求入度 InitStack(S);/建0入度顶点栈 for(i=0;ivexnum;i+) if(indegreei=0) Push(S,i); while(!StackEmpty(S) Pop(S,&j); Push(T,j); +count;/j号顶点入栈并计数 for(p=G-verticesj.firstarc;p;p=p-nextarc)k=p-adjvex;if(-indegreek=0)Push(S,k);if(vej+p-infovek)vek=vej+p-info; if(countvexnum)return ERROR;elsereturn OK;status CriticalPath(ALGraph *G)int veMAX_VERTEX_NUM=0,vlMAX_VERTEX_NUM=0;int i,j,ee,dut,k,el;char tag;SqStack *T;ArcNode *p;if(!(T=(SqStack *)malloc(sizeof(SqStack) exit(OVERFLOW);InitStack(T);/初始化if(!TopologicalOrder(G,T,ve)return ERROR;for(i=0;ivexnum;i+) vli=veG-vexnum-1; while(!StackEmpty(T)for(Pop(T,&j),p=G-verticesj.firstarc;p;p=p-nextarc)k=p-adjvex;dut=p-info;if(vlk-dutvlj)vlj=vlk-dut;for(j=0;jvexnum;+j)for(p=G-verticesj.firstarc;p;p=p-nextarc)k=p-adjvex;dut=p-info;/dutee=vej;el=vlk-dut;tag=(ee=el)?*: ;if(ee=el)printf(n %c %c %d %c n,G-verticesj.data,G-verticesk.data,dut,tag);return OK;void main() ALGraph *G; G=(ALGraph *)malloc(sizeof(ALGraph); CreatDG(G); CriticalPath(G);5. 设计5 2-路归并排序 一、需求分析1、问题描述：某学校一个年级有M个班的学生参加某门课程的考试，每个班最多有N个学生，利用2-路归并排序的思想求全体考生的排名表。2.要求：（1）每个班的学生都是按学号顺序输入数据的，每个学生记录至少包含排列名次、学号、姓名、成绩四个域。（2）输出每个学生在本年级的排名情况，具有相同成绩的名次相同。3、具体目标包括： （1）利用顺序存储结构存储有序表。