数据结构课程设计报告正文

课程设计(**)

题目名称表达式求值问题课程名称数据结构课程设计学生姓名陈春林学号***系、专业信息工程系、信息工程类指导教师陈智。

2023年1月3日。

目录。1问题描述22需求分析23概要设计23．1抽象数据类型定义23．2模块划分34详细设计44．1数据类型的定义44．2主要模块的算法描述45测试分析75．1程序运行结果75．2程序调试与体会86课程设计总结8参考文献8附录（源程序清单9

1问题描述。

编写一个表达式求值程序，使输入一个四则运算表达式后，能够返回正确的结果。该表达式由数字0～9、+、括号组成，且表达式必须正确无误。程序的编写可用到栈或队列的基本算法，求出该表达式的值，并分析算法的时间复杂度和运算的结果。

2需求分析。

1）为实现算符优先算法，可以使用两个工作栈。一个称做optr，用以。

寄存运算符；另一个称做opnd;用以寄存操作数或运算结果。算法的基本思想是：

首先置操作数栈为空栈，表达式起始符“#”为运算符栈的栈底元素；②依次读入表达式中每个字符，若是操作数则opnd栈，若是运算符，则和optr栈的栈顶运算符比较优先权后做相应操作，直至整个表达式求值完毕(即optr栈的栈顶元素和当前读入的字符均为"#

2）该程序实现表达式的求值问题：

从键盘读入一个合法的算术表达式，利用算符优先关系，实现对算术四则混合运算的求值，输出正确的结果。

3概要设计。

3．1抽象数据类型定义。

设定栈抽象数据类型的定义采用两个栈的入栈与出栈的操作来进行“运算符和操作数的配对”。程序中主要用到以下抽象数据类型：

1）adt stack

数据关系：r1＝约定an端为栈顶，a1端为栈底。基本操作：

1）initstack(&s)

操作结果：构造一个空栈s。

2）gettop(s, &e)

初始条件：栈s已存在且非空。

操作结果：用e返回s的栈顶元素。（3）push(&s, e)

初始条件：栈s已存在。

操作结果：插入元素e为新的栈顶元素。（4）stackempty(&s)

初始条件：栈s已存在。

操作结果：若s为空栈，则返回true,否则返回false（5）pop(&s, &e)

初始条件：栈s已存在且非空。

操作结果：删除s的栈顶元素，并用e返回其值。} adt stack

3．2模块划分。

本程序包括三个模块：（1）主函数模块。

void main()

输入表达式；

根据要求进行转换并求值；输出结果；}

2）表达式求值模块---实现具体求值（3）表达式转换模块---实现转换。

三模块之间简单调用关系：

表达式求值。

图3.2模块调用图。

表达式转换。

主函数模块。

4详细设计。

4．1数据类型的定义。

1）栈类型。

#define maxsize 100typedef int elmtype;struct sqstack;

2）运算符号类型。

char ch[7

3）运算符号优先级类型。

int f1[7]=;栈内元素优先级*/

int f2[7]=;栈外元素优先级*/4．2主要模块的算法描述。

该程序主要由主函数模块、表达式求值模块、表达式转换模块三个个部分组成。

1）主函数及表达式求值模块。

void main()

int result;

result=evaluateexpression();对evaluateexpression()进行调用*/}

2）表达式求值模块。

主函数只调用了evaluateexpression()函数；而其他的函数则由。

evaluateexpression()调用了，因此使得主函数十分简洁明了。其中求值函数流。程图如下：

return(gettop(opnd)

结束。图4.2表达式求值模块流程图。

push(&opnd,sum)c=getchar()isdigit(c)yn

yn定义char c

c!='#y

nisdigit(c)

nsum=0yk

error!判断！jy

nsum=sum*10-(c-'0')sum=sum*10+(c-'0')

3）表达式转换模块。

void trans(char *exp,char *postexp) st;

5测试分析。

5．1程序运行结果：

5．2程序调试与体会。

运用栈的基本操作顺利的解决表达式求值及转换问题，主要利用栈的先进后出结构，执行出栈进栈操作并在出栈时进行配对并输出配对情况，而整个过程不需要不需要移动元素使程序在空间复杂度上降到最小，采用指针的移动大大加快了程序的执行效率。并且对输入进行了改进，以防止用户随意输入时出现的各种意想不到的错误。系统整体上比较完美，无论是输入、输出，还是整个系统的界面，都非常美观、简洁、大方。

6课程设计总结。

通过这段时间的课程设计，本人对计算机的应用、数据结构的作用以及c语言的使用都有了更深的了解。在理论学习和上机实践的各个环节中，通过自主学习和请教陈智、成娅辉老师，我收获了不少。当然也遇到不少问题，也正是因为这些问题引发的思考给我带来了收获。

从当初不喜欢上机写程序到现在能主动写程序，从当初拿着程序不知从何下手道现在知道如何分析问题，如何用专业知识解决实际问题的转变。我发现无论是专业知识还是动手能力，自己都有很大程度的提高。

在实际上机操作过程中，不仅是让我们了解数据结构的理论知识，更重要的是培养解决实际问题的能力。所以相信通过此次课程设计实习可以提高我们分析设计能力和编程能力，为后续课程的学习及实践打下良好的基础。

在这次短短的课程实践里，我得到了陈智老师的关心和帮助。他给了我们很多的信息，与我们一起**问题，询问我们遇到了哪些问题并耐心给予指导。当我们遇到技术上难以解决的问题时，他就会指导我们解决问题，他把自己多年来积累的经验传授给我们，是我们顺利的完成了课程设计的任务。

再一次感谢给予我指导及帮助的老师和同学们！

参考文献。1]黄同成，黄俊民，董建寅．数据结构[m]．北京：中国电力出版社，2008

2]董建寅，黄俊民，黄同成．数据结构实验指导与题解[m]．北京：中国电力出版社，2008[3]严蔚敏，吴伟民。数据结构（c语言版）[m].北京：清华大学出版社，2002

4]刘振鹏，张晓莉，郝杰．数据结构[m]．北京：中国铁道出版社，2003

附录（源程序清单）

#include <>#include <>#include <>#define maxsize 100

typedef int elmtype;

typedef struct sqstack sqstack;char ch[7

int f1[7]=;栈内元素优先级*/int f2[7]=;栈外元素优先级*/int n=0;struct sqstack

elmtype stack[maxsize];int top;};

void initstack(sqstack *s)

s->top=0;}

int stackempty(sqstack s )

void push(sqstack *s,elmtype x)}

void pop(sqstack *s,elmtype *x)}

elmtype gettop(sqstack s)else

return

elmtype f(char c)}

char compare(char c1,char c2)return sum;}

float compvalue(char *postexp) st;

evaluateexpression()else

sum=sum*10+(c-'0');c=getchar();push(&opnd,sum);j=1;}elseif(k)return(gettop(opnd));main()

数据结构课程设计报告正文

数据结构课程设计正文

数据结构课程设计正文

数据结构课程设计报告

其他用户还读了