数据结构期末课程设计.docx
- 文档编号:13080505
- 上传时间:2023-06-10
- 格式:DOCX
- 页数:52
- 大小:553.60KB
数据结构期末课程设计.docx
《数据结构期末课程设计.docx》由会员分享,可在线阅读,更多相关《数据结构期末课程设计.docx(52页珍藏版)》请在冰点文库上搜索。
数据结构期末课程设计
设计1----约瑟夫环问题
一、需求分析
1、问题描述:
设编号为1,2…,n(n>0)个人按顺时针方向围坐一圈,每人持有一个正整数密码。
开始时任意给出一个报数上限值m,从第一人开始顺时针方向自1起顺序报数,报到m时停止报数,报m的人出列,将他的密码作为新的m值,从他在顺指针方向上的下一个人起重新自1起顺序报数;下去,直到所有人全部出列为止。
2、首先指定报数上限值,建立循环链表中不需要头结点,注意空表与非空表的界限。
3、程序执行的命令包括:
创建链表;删除结点;输出出列顺序;结束。
二、概要设计
1、为实现上述程序功能,应以不带头结点的循环链表存储密码与编号。
为此,需要一个抽象数据类型:
循环链表。
如下:
数据关系:
R1={ 基本操作: creat(&L,n) 操作结果: 构造长度为n的循环链表。 Listdelete(&L,e) 初始条件: 线性表L存在。 操作结果: 删去报数为e的元素L长度减一。 2、本程序包括三个模块: 一是主程序模块; Voidmain(){ 初始化L调用linklistcreat(linklistL) 调用voiddeletenode(linklistL) } 二是链表的建立;三是删除指定链表元素。 三、详细设计 主要程序: typedefstructLNode { intnumber; intpassword; structLNode*next; }LNode,*LinkList; LinkListcreate(intn)//建立一个没有头结点的循环链表 { LinkListhead,p1,p2; inti; for(i=1;i<=n;i++) { p1=(LinkList)malloc(sizeof(LNode)); printf("第%d个人的密码为: ",i); scanf("%d",&p1->password); p1->number=i; if(i==1) head=p1; else p2->next=p1; p2=p1; } p2->next=head; return(head); } intmain()//主函数 { LinkListhead,p,s; intm,N,j,k,count=0; printf("输入总的人数: "); scanf("%d",&N); printf("输入初始密码: "); scanf("%d",&m); head=create(N); for(j=N;j>=1;j--) { count++; p=head; for(k=1;k { s=p; p=p->next; } m=p->password; printf("第%d个退出的是编号为%d的人,密码为%d\n",count,p->number,m); s->next=p->next; head=p->next; free(p); } return0; } 四、运行结果及分析 五、总结 通过这次课程设计,让我对单循环链表有了更深刻的体会,掌握了单循环链表的初始化,创建,删除,遍历等操作。 在调试程序的时候,可以逐块的检查,遇到程序报错时,可以手工操作模拟程序的运行,需要跟踪某个变量时,可以在函数适当的位置加入输出语句,查看变量的值的变化情况。 经常会将链表中的指针所指的位置混淆,以致在头结点的位置上徘徊多时,今后应多注意这方面的问题。 设计2----迷宫问题 一、需求分析 1、问题描述: 迷宫是一些互相连通的交叉路口的集合,给定一个迷宫入口,一个迷宫出口,当从入口到出口存在通路时输出其中的一条通路,当从入口到出口不存在通路时输出无通路存在。 2、要求: 利用随机方法产生一个mn的迷宫,0和1分别表示迷宫中的通路和障碍。 存在回路时能记住已经走过的路口,不重复已经走过的路口。 3、程序执行命令包括: 创建迷宫;创建空栈;销毁栈;寻找通路;输出迷宫。 二、概要设计 1、设定栈的抽象数据类型定义: ADT Stack{ 数据对象: D={ai|ai∈CharSet,i=1,2,…,n,n>=0} 数据关系: R1={ } 2、求解迷宫的算法: 设定当前位置的初值为入口位置; do{ 若当前位置可通 则{将当前位置插入栈顶; 若当前位置是出口位置,则结束; 否则切换当前位置的相邻位置为新的当前位置; } 否则{ 若栈不空且栈顶位置尚有其他方向未被探索; 则设定新的位置为沿顺时针方向旋转找到的栈顶位置的下一邻块; 若栈不空且栈顶位置的四周均不可通; 则{删去栈顶位置; 若栈不空,则重新测试新的栈顶位置,直至找到一个可通的相邻块或栈空; } } }while(栈不空); 3、以结构的形式来表示迷宫矩阵的每个点以及后续的整个通路的点 struct { inti;//行号 intj;//列号 intdi;//下一个可走相邻方位的方位号 }Stack[MaxSize];//定义栈 三、详细设计 主要程序: #include #defineMaxSize100 #defineM4 #defineN4 迷宫初始化: intmg[6][6]={{1,1,1,1,1,1}, {1,0,1,1,1,1}, {1,0,1,1,1,1}, {1,0,0,1,1,1}, {1,1,0,0,0,1}, {1,1,1,1,1,1}}; inttop=-1;//初始化栈顶 intcount=1;//路径数计数 迷宫函数: voidMgPath() { inti,j,k,di,find; top++;//初始方块进入栈 Stack[top].i=1; Stack[top].j=1; Stack[top].di=-1; mg[1][1]=-1; while(top>-1)//栈不空时循环 { i=Stack[top].i;j=Stack[top].j;di=Stack[top].di;//取栈顶 if(i==M&&j==N&&count>=1)//找到了出口,输出路径 { printf("%d: ",count++); for(k=0;k<=top;k++) { printf("(%d,%d)",Stack[k].i,Stack[k].j); } printf("\n"); mg[Stack[top].i][Stack[top].j]=0;//让该位置变为其他路径可走方块 top--; i=Stack[top].i;j=Stack[top].j;di=Stack[top].di; } find=0; while(di<4&&find==0)//找(i,j)方块下一个可走方块 { di++; switch(di) { case0: i=Stack[top].i-1;j=Stack[top].j;break; case1: i=Stack[top].i;j=Stack[top].j+1;break; case2: i=Stack[top].i+1;j=Stack[top].j;break; case3: i=Stack[top].i,j=Stack[top].j-1;break; } if(mg[i][j]==0) find=1; } if(find==1)//找到了一个可走的相邻方块 { Stack[top].di=di;//修改原栈顶元素的di值 top++;//将可走相邻方块进栈 Stack[top].i=i; Stack[top].j=j; Stack[top].di=-1; mg[i][j]=-1;//避免重复走到该方块,将其置为-1 } else//没有相邻方块可走,则退栈 { mg[Stack[top].i][Stack[top].j]=0;//让该位置变为其他路径可走方块 top--; } } if(count==1) printf("迷宫无通路\n"); } 主函数: intmain() { printf("从(1,1)到(4,4)的通路为: \n"); MgPath(); return0; } 四、运行结果及分析 五、总结 开始对栈的构造以及出栈入栈函数不清楚,而且定义的出栈函数繁琐,定义的函数有逻辑上的错误。 通过迷宫求解的编程练习思考数据结构的使用,比如对栈、指针、链表等的深入了解,让我们感受到了数据结构及其算法的重要。 此外还熟悉了各种函数的应用。 对于我们初学者来说,学习编写迷宫求解,对我们掌握了解数据结构的知识有很大的帮助。 我们通过编程实践,还能拓展思路,让我们主动去寻找所需要的算法,怎样提高程序的质量等。 设计3----表达式求值问题 一、需求分析 1、问题描述: 键盘输入表达式,求该表达式的后缀表达式、再求该表达式的值。 2、要求: 分别测试表达式中运算符为一位数、多位数、小数时的值。 3、为了实现算符优先算法。 可以使用两个工作栈。 一个称为OPTR,用以寄存运算符,另一个称做OPND,用以寄存操作数或运算结果。 二、概要设计 1、首先置操作数栈为空栈,表达式起始符“#”为运算符栈的栈底元素;依次读入表达式,若是操作符即进OPND栈,若是运算符则和OPTR栈的栈顶运算符比较优先权后作相应的操作,直至整个表达式求值完毕(即OPTR栈的栈顶元素和当前读入的字符均为“#”)。 2、ADT描述: ADT Stack{ 数据对象: D={ai|ai∈ElemSet,i=1,2,„,n, n≧0} 数据对象: R1={ 约定an端为栈顶,ai端为栈底; 基本操作: InitStack(&S) 操作结果: 构造一个空栈S。 GetTop(S)初始条件: 栈S已存在。 操作结果: 用P返回S的栈顶元素。 Push(&S,ch) 初始条件: 栈S已存在。 操作结果: 插入元素ch为新的栈顶元素。 Pop(&S) 初始条件: 栈S已存在。 操作结果: 删除S的栈顶元素。 In(ch) 操作结果: 判断字符是否是运算符,运算符即返回1。 Precede(c1, c2) 初始条件: c1,c2为运算符。 操作结果: 判断运算符优先权,返回优先权高的。 Operate(a,op,b) 初始条件: a,b为整数,op为运算符。 操作结果: a与b进行运算,op为运算符,返回其值。 num(n) 操作结果: 返回操作数的长度。 EvaluateExpression() 初始条件: 输入表达式合法。 操作结果: 返回表达式的最终结果。 }ADT Stack 三、详细设计 主要程序: #include #include #defineOK1 #defineERROR0 #defineSTACK_INIT_SIZE100 #defineSTACKINCREMENT20//定义字符类型栈 typedefstruct{ char*base; char*top; intstacksize; }Stack1;//定义整型栈 typedefstruct{ float*base; float*top; intstacksize; }Stack2; intInitStack1(Stack1*s)//构造运算符栈,操作数栈 { s->base=(char*)malloc(STACK_INIT_SIZE*sizeof(char)); if(! s->base) returnERROR; s->top=s->base; s->stacksize=STACK_INIT_SIZE; returnOK; } intIn(charc)//判断字符是否是运算符,运算符即返回1 { if(c=='+'||c=='-'||c=='*'||c=='/'||c=='('||c==')'||c=='#') return1; else return0; } intPush1(Stack1*s,charc)//运算符栈,操作数栈插入c为新的栈顶元素 { *s->top=c; s->top++; returnOK; } charPop1(Stack1*s)//删除运算符栈,操作数栈s的栈顶元素,用e返回其值 { chare; s->top--; e=*s->top; returne; } charGetTop1(Stack1s)//用e返回运算符栈,操作数栈s的栈顶元素 { chare; e=*(s.top-1); returne; } charPrecede(charc1,charc2) { inti,j; staticchara[49]={'>','>','<','<','<','>','>','>','>','<','<','<','>','>','>','>','>','>','<','>','>','>','>','>','>','<','>','>','<','<','<','<','<','=','! ','>','>','>','>','! ','>','>','<','<','<','<','<','! ','='}; switch(c1) { case'+': i=0;break; case'-': i=1;break; case'*': i=2;break; case'/': i=3;break; case'(': i=4;break; case')': i=5;break; case'#': i=6;break; } switch(c2) { case'+': j=0;break; case'-': j=1;break; case'*': j=2;break; case'/': j=3;break; case'(': j=4;break; case')': j=5;break; case'#': j=6;break; } return(a[7*i+j]); } intGetNumber(charc)//转化数码 { return(c-48); } floatOperate(floata,chartheta,floatb) { switch(theta) { case'+': return(a+b); case'-': return(a-b); case'*': return(a*b); case'/': return(a/b); } } floatEvaluateExpression() { charc,theta; floata,b,m,n; intk=0,i,j=0; Stack1OPTR; Stack2OPND; InitStack1(&OPTR); Push1(&OPTR,'#'); InitStack2(&OPND); c=getchar(); while(c! ='#'||GetTop1(OPTR)! ='#'){ if(! In(c)){ if(c=='.'){ k=2; j++; } else{ m=GetNumber(c); if(k==1){ n=Pop2(&OPND); m=n*10+m; Push2(&OPND,m); k=1; } elseif(k==2){ n=Pop2(&OPND); for(i=1;i<=j;i++) m=m*0.1; m=n+m; Push2(&OPND,m); k=2; j++; } else{ Push2(&OPND,m); k=1; } } c=getchar(); } else switch(Precede(GetTop1(OPTR),c)){ case'<': Push1(&OPTR,c);k=0;j=0;c=getchar();break; case'=': Pop1(&OPTR);c=getchar();break; case'>': theta=Pop1(&OPTR);b=Pop2(&OPND);a=Pop2(&OPND);Push2(&OPND,Operate(a,theta,b));break; } } returnGetTop2(OPND); } intmain() { printf("请输入正确的表达式以'#'结尾: "); printf("表达式结果为: %f\n",EvaluateExpression()); return0; } 四、运行结果及分析 五、总结 这次课程设计让我有一个深刻的体会,那就是细节决定成败,编程最需要的是严谨,如何的严谨都不过分,往往检查了半天发现错误发生在某个括号,分号,引号,或者数据类型上。 就像我在写EvaluateExpression()函数时,忘了指针的地址符值不用加*号,这一点小小的错误也耽误了我几十分钟,所以说细节很重要。 设计4----前缀算术表达式转换及表达式计算 一、需求分析 1、问题描述: 算术表达式与二叉树之间存在着对应关系,编写把以前缀形式输入的合法算术表达式转换为中缀表达式,再转换为后缀表达式,并求表达式的值 2、要求: ①把前缀表达式转换为中缀表达式; ②输出中缀表达式; ③把中缀表达式转换为后缀表达式; ④利用栈结构实现后缀表达式的求值; 3、利用二叉树的遍历的顺序实现把以前缀形式输入的算术表达式转换为中缀和后缀表达式 。 二、概要设计 1、主模块: Void main(){ 新建栈,树,并实现初始化; 接受命令; 处理命令; } 2、栈的抽象类型数据定义: ADT Stack{ 数据对象: D={ ai|ai ∈ElemSet,i=1,2,...,n,n≥0} 数据关系: R1={ 基本操作: InitStack(SqStack *S) Push(SqStack *S,SNodeEType e) Pop(SqStack *S,SNodeEType *e) StackEmpty(SqStack *S) } ADT Stack 三、详细设计 主要程序: typedefstructBiTNode { chardata[10]; structBiTNode*lchild,*rchild; }BiTNode,*BiTree; intVisit(chardata[10]) { printf("%s",data); returnOK; } intInitBiTree(BiTree&T) { if(! (T=(BiTree)malloc(sizeof(BiTNode)))) returnERROR; T->lchild=NULL; T->rchild=NULL; returnOK; } voidCreateBiTree(BiTree&T) { charch[20]; scanf("%s",ch); if(strcmp(ch,"+")==0||strcmp(ch,"-")==0||strcmp(ch,"*")==0||strcmp(ch,"/")==0) { strcpy(T->data,ch); if(! (T->lchild=(BiTNode*)malloc(sizeof(BiTNode)))) exit(0); CreateBiTree(T->lchild); if(! (T->rchild=(BiTNode*)malloc(sizeof(BiTNode)))) exit(0); CreateBiTree(T->rchild); } else { strcpy(T->data,ch); T->lchild=NULL; T->rchild=NULL; } } intPreOrderTraverse(BiTree&T) { if(T) { Visit(T->data); PreOrderTraverse(T->lchild); PreOrderTraverse(T->rchild); returnOK; } else returnERROR; } intInOrderTraverse(BiTree&T) { if(T) { InOrderTraverse(T->lchild); Visit(T->data); InOrderTraverse(T->rchild); returnOK; } else returnERROR; } intPostOrderTraverse(BiTree&T) { if(T) { PostOrderTraverse(T->lchild); PostOrderTraverse(T->rchild); Visit(T->data); Calculator(T->data,stack);//设计3表达式求值 returnOK; } else returnERROR; } intmain() { InitStack(stack); BiTreeT;
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 期末 课程设计