数据结构课程设计.doc

此文档收集于网络，如有侵权，请联系网站删除课程设计说明书设计题目： 数据结构课程设计 专业： 电子信息科学与技术 班级： 2008级1班 设计人： 山 东 科 技 大 学年 月 日课程设计任务书学院： 专业： 班级： 姓名： 一、 课程设计题目： 数据结构课程设计 二、 课程设计主要参考资料：（1） （2） （3） 三、课程设计应解决的主要问题：（1）约瑟夫环问题 （2 迷宫问题 （2）三元组表示的稀疏矩阵的转置、加法和乘法实现 （3）前缀算术表达式转换及表达式计算 （4）有向无环图每个顶点出发的最短路径及其长度； （5）2-路归并排序 四、课程设计相关附件（如图纸、软件等）：五、任务发出日期： 课程设计完成日期： 指导教师签字： 系主任签字： 指导教师对课程设计的评语指导教师签字： 年 月 日设计1 约瑟夫环问题一、需求分析一、具体目标包括： 1实现单循环链表的初始化 2理解约瑟夫环的定义，用循环找到每次报数人的序号 3. 从单循环链表中删除节点，并判断链表空与非空的临界条件。二、单向循环链表的抽象数据类型定义为： ADT CircleList 数据对象：Dai | aiElemset,i=1,2,n,n0 数据关系：R=, | ai-1,aiD,i=2,n 基本操作：Link InitList（int n）操作结果：构造一个含有n个元素的单向循环链表。三、问题描述设编号为1，2，n(n0)个人按顺时针方向围坐一圈，每人持有一个 正整数密码。开始时任意给出一个报数上限值m，从第一人开始顺时针方向自1 起顺序报数，报到m时停止报数，报m的人出列，将他的密码作为新的m值，从他在顺指针方向上的下一个人起重新自1起顺序报数；下去，直到所有人全部出列为止。要求设计一个程序模拟此过程。四、基本要求利用单向循环链表存储结构模拟此过程，按照出列的顺序印出个人的编号。二、概要设计一、本程序分三个模块 1）主模块 Void main() 初始化； 接受命令； 处理命令； 2）单向循环表单元模块，实现单向循环链表的抽象数据类型功能； 3）节点结构单元模块，定义单向循环链表的节点结构。三、详细设计1、构建一个单循环链表算法流程图1结束p-next=Lp=qP-next=qhead=qi=1P指向申请空间i=nP指向申请空间2主模块实现算法从头结点开始，根据报数上限找到下一个出列人的序号，并读出该人的密码作为新的报数上限，从此节点的下一个节点开始进行新的查找。通过指针依次删除出列人相应的节点，直到该链表中无节点，退出循环。输入报数上限jnm=1?inexti=i+1=1q=L-next输出q的numbermnext-number删除q节点初始化一个单循环链表四、运行结果及分析测试用例1：（一般数据）五、总结本次实验主要考察了对单循环链表的应用。附：主要源代码typedef struct LNode int data2;struct LNode *next;LNode, *Linklist;void Creatlist(Linklist L,int n)int i;Linklist p, q=L;printf(请输入报数密码以及学生序号，并用逗号隔开:n);for(i=n;i0;i-) p=(Linklist)malloc(sizeof(LNode);scanf(%d,%d,&p-data0,&p-data1);p-next=L; q-next=p; q=p;p-next=L-next;printf(学生依次出圈序号为：);printf(n*n);void main(void)int i=1,j,n; Linklist L,p,q; printf(请输入学生数目n=); scanf(%d,&j);L=(Linklist)malloc(sizeof(LNode); L-next=L; Creatlist(L,n); p=L-next;q=L-next; while(j=3) if(p-data0)=1)while(p-next)!=q) p=p-next;p-next=q-next;printf(%d ,q-data1);j-;free(q);q=p-next; p=q;elsewhile(idata0) q=q-next; i+;while(p-next)!=q) p=p-next;p-next=q-next;printf(%d ,q-data1);j-;free(q);q=p-next;p=q;i=1; if(p-data0%2) printf(%d ,p-data1); printf(%d ,p-next-data1); else printf(%d ,p-next-data1);printf(%d ,p-data1);printf(n*n); printf(n排序完毕n);设计2 迷宫问题一、需求分析一、具体目标：1、生成一个m x n的迷宫，0和1分别表示迷宫中的通路和障碍。2、存在回路时，找出回路；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、主模块void main () 构造一个空栈，实现其初始化、插入、删除操作； 输入迷宫入口位置； 判断是否有回路； 输出出口位置或“没有找到！”2、主要模块主模块main()构造空栈实现基本操作输出出口位置或“没有找到”输入入口的位置并判断是否有出口三、详细设计流程图：int *e1S-top=S-basee-di=S-top-di;e-ord=S-top-ord;e-seat.x=S-top-seat.x;e-seat.y=S-top-seat.y;e1=S-top;S-top=S-top-next;return ERROR;free(e1)return OK2、主函数：流程图：i=1; j=1i=njbase=(SElemType /构造一个空栈S*)malloc(sizeof(SElemType);S-base-ord=0;if(!S-base)exit(OVERFLOW); /存储分配失败S-top=S-base;return OK; /InitStackvoid Push(SqStack *S,SElemType *e) /插入元素e为新的栈顶元素e-next=S-top; S-top=e;/PushStatus Pop(SqStack *S,SElemType *e) /若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK,否则返回ERRORSElemType *e1;if(S-top =S-base) return ERROR;e-di=S-top-di;e-ord=S-top-ord;e-seat.x=S-top-seat.x;e-seat.y=S-top-seat.y;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;void Nextpos(PostType seat,int di,PostType curpose)switch(di)case 1:curpose-x=seat-x;curpose-y=(seat-y)+1;break;case 2:curpose-x=seat-x+1;curpose-y=seat-y;break;case 3:curpose-x=seat-x;curpose-y=seat-y-1;break;case 4:curpose-x=seat-x-1;curpose-y=seat-y;break;Status MazePath(SqStack *S,int maseNN,PostType start,PostType end) /若迷宫mase中存在从入口start到出口end的通道，则求得一条放在栈中（从栈底到栈顶），并返回TRUE，否则返回FALSE;SElemType *e;PostType curpos=start;int curstep=1; InitStack(S);doif(masecurpos-xcurpos-y=0) /当前位置可以通过，即未曾走过的道路masecurpos-xcurpos-y=2; /留下痕迹e=(SElemType *)malloc(sizeof(SElemType);if(!e)exit(OVERFLOW);/存储分配失败e-ord=curstep;/e-seat=(PostType )malloc(sizeof(struct Post);e-seat.x=curpos-x; e-seat.y=curpos-y; e-di=1;Push(S,e);/加入路径if(curpos-x=end-x & curpos-y=end-y )return TRUE; Nextpos(&S-top-seat,1,curpos);curstep+;else /当前位置不通if(!StackEmpty(S)while(S-top-di=4 & !StackEmpty(S) e=(SElemType )malloc(sizeof(SElemType);if(!e) exit(OVERFLOW);/存储分配失败Pop(S,e);curstep-;free(e);if(S-top-ditop-di+;Nextpos(&S-top-seat,S-top-di,curpos);/设定当前位置是该新方向上的相邻块while(!StackEmpty(S);return FALSE;void Imase(int maseNN,PostType start,PostType end,int *n1,int *m1)int n,m,x,y,i,j;printf(迷宫行列数为：（用逗号隔开）（没有外墙小于90）:);do scanf(%d,%d,&n,&m); while(n=0 & m=0);*n1=n;*m1=m;for(i=0;i=m+1;i+)mase0i=1;masen+1i=1;for(j=0;jn | ym | x-1 | yx,&start-y);printf(输入结束坐标：);scanf(%d,%d,&end-x,&end-y);while(!(start-xyx0 & start-y0 & end-xyx0 & end-y0);void main()SqStack S; ElemType e;int maseNN=0，i,j,n,m;struct Post start, end;Imase(mase,&start,&end,&n,&m);if(MazePath(&S,mase,&start,&end)while(!StackEmpty(&S)Pop(&S,&e);masee.seat.xe.seat.y=4;for(i=1;i=n;i+)for(j=1;j=m;j+)if(maseij=2) maseij=0;if(maseij=0) printf( );else if(maseij=1)printf( + );else printf( - );printf(n);else printf(没找到！);设计3 三元组表示的矩阵的操作实现一、需求分析一、抽象数据类型ADT SparseMatrix 数据对象： Daj1,j2, .,ji, .,jn| ji =0,.,bi -1, i=1,2,.,n 数据关系： Row|1=i=m,1=j=n-1 Col|1=i=m-1,1=j=n ADT Array 2、基本操作：（1）status LogicMatrix(SMatrix M,SMatrix N,SMatrix *Q)操作结果：求矩阵逻辑乘积Q=M*N （2）status SumMatrix(SMatrix M,SMatrix N,SMatrix *Q)操作结果：M+N=Q二、概要设计1、用三元组顺序表存储表示，求稀疏矩阵的转置矩阵2、求两个矩阵的和及乘积3、求稀疏矩阵的自反闭包、对称闭包和传递闭包三、详细设计文字性描述：本设计本人能力有限，用序偶输入的，根据自反、对称和可传递闭包定义，在矩阵操作上，稍微改动一下，但是也能基本实现，自反和对称闭包运算，另外，可传递闭包用递归实现，只是循环次数是矩阵的行数四、运行结果及分析五、总结 主要应用三元组处理矩阵，利用矩阵的加法和乘法求自反闭包、对称闭包和传递闭包附：主要源代码typedef struct int i,j, e;Triple;typedef struct Triple dataMAX+1;int mu,nu,tu;TSMatrix;void zifanbibao(int aMAXMAX,int mu,int nu)int i,j,cMAXMAX; for(i=1;i=mu;i+)for(j=1;j=nu;j+) if(i=j) printf(1 );cij=1;else cij=aij;printf(%d ,aij); printf(n); printf(自反闭包关系输出为：n);for(i=1;i=mu;i+)for(j=1;j=nu;j+) if(cij)printf( ,i,j);void duichenbibao(int aMAXMAX,int mu,int nu) int i,j, cMAXMAX; for(i=1;i=mu;i+)for(j=1;j=nu;j+) cij=aij|aji;printf(%d ,cij);printf(n); printf(对称闭包关系输出为：n); for(i=1;i=mu;i+)for(j=1;j=nu;j+) if(cij)printf( ,i,j); void kechuandibibao(int aMAXMAX,int mu,int nu)inti,j,k,t,t cMAXMAX=0,0,0,0,0,0,0,0,0;for(t=1;t=mu;t+) for(i=1;i=mu;i+)for(j=1;j=nu;j+)for(k=1;k=nu;k+) cij=cij|(aik*akj);for(i=1;i=mu;i+)for(j=1;j=nu;j+) printf(%d ,cij); printf(n); printf(可传递闭包关系输出为：n); for(i=1;i=mu;i+)for(j=1;j=nu;j+) if(cij)printf( ,i,j);void main() int i,j, mu,nu,tu=0, aMAXMAX;printf(请输入矩阵n); printf(行数为：);scanf(%d,&mu);printf(列数为：);scanf(%d,&nu);printf(数据为:n);for(i=1;i=mu;i+)for(j=1;j=nu;j+)scanf(%dn,&aij); if(aij!=0) tu+; printf(你输入的数据为：n);for(i=1;i=mu;i+)for(j=1;j=nu;j+)printf(%d ,aij); printf(n);printf(求得自反闭包为：n); zifanbibao(a,mu,nu); printf(n求得对称闭包为：n); duichenbibao(a,mu,nu);printf(n求得可传递闭包为：n);kechuandibibao(a,mu,nu);设计4前缀表达式一、需求分析1、具体目标包括：（1）构造一个队列，实现对队列元素的插入，删除操作（2）构造一个栈，实现对栈的元素的插入和删除操作，判断栈为空的条件（3）利用二叉树的遍历的顺序实现把以前缀形式输入的算术表达式转换为中缀和后缀表达式2、栈的抽象数据类型的定义：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 Stack3、问题描述算术表达式与二叉树之间存在着对应关系，编写把以前缀形式输入的合法算术表达式转换为中缀表达式，再转换为后缀表达式，并求表达式的值要求。(1) 把前缀表达式转换为中缀表达式；(2) 输出中缀表达式；(3) 把中缀表达式转换为后缀表达式；(4) 利用栈结构实现后缀表达式的求值；二、概要设计1、主模块 Void main() 新建栈，队列，树，并实现初始化； 接受命令； 处理命令；2、主要模块主模块 main()队列初始化输入算术表达式输出算术表达式三、详细设计1、Tree 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;流程图1scanf(“%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四、运行结果及分析附主要源代码：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 *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);设计5 有向无环图每个顶点出发的最长路径及其长度一、需求分析1、生成一个有向无环图2、用邻接表存储3、从有向无环图的每个顶点出发求其最长路径和它的长度。二、概要设计一、抽象数据类型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;P!=NULL vli=veG-vexnum-1ivexnuint veMAX_VERTEX_NUM=0int vlMAX_VERTEX_NUM=0;int i,j,ee,dut,k,el;char tag;SqStack *T;ArcNode *p; 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四、运行结果：五、总结利用栈的结果，求有向无环图的关键路径。附：主要源代码typedef 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) SElemType *e1;e1=(SElemType *)malloc(sizeof(SElemType)