【数据结构】【A】十进制整数四则运算计算器

东北大学信息科学与工程学院

数据结构课程设计报告题目十进制整数四则运算计算器课题组长余灏然

课题组成员魏嘉张越

专业名称计算机科学与技术

班级计算机1307

指导教师杨雷

2015 年1月

课程设计任务书

题目：

十进制整数四则运算计算器

问题描述：

由输入的四则运算表达式字符串，动态生成算术表达式所对应的二叉树，通过表达式二叉树自动求值并输出。

设计要求：

设计十进制整数四则运算计算器。

（1）采用二叉树、栈等数据结构。

（2）给定表达式字符串，生成二叉链表的表达式二叉树。

（3）对表达式二叉树采用后序遍历求值并输出。

（4）可以考虑加入复数四则运算功能。

（5）其它完善性功能。

指导教师签字：

2014年12月28日

目录

1 课题概述 (1)

1.1 课题任务 (1)

1.2 课题原理 (1)

1.3 相关知识 (4)

2 需求分析 (4)

2.1 课题调研 (5)

2.2 用户需求分析 (5)

3 方案设计 (5)

3.1 总体功能设计 (5)

3.2 数据结构设计 (5)

3.3 函数原型设计 (5)

3.4 主算法设计 (5)

3.5 用户界面设计 (5)

4 方案实现 (6)

4.1 开发环境与工具 (6)

4.2 程序设计关键技术 (6)

4.3 个人设计实现（按组员分工）

4.3.1余灏然设计实现 (6)

4.3.2 魏嘉设计实现 (9)

4.3.3 张越设计实现 (11)

5 测试与调试 (13)

5.1 个人测试（按组员分工） (13)

5.1.1 余灏然测试 (13)

5.1.2 魏嘉测试 (16)

5.1.3 张越测试 (20)

5.2 组装与系统测试 (25)

5.3 系统运行 (25)

6 课题总结 (26)

6.1 课题评价 (26)

6.2 团队协作 (26)

6.3 个人设计小结（按组员分工） (26)

6.3.1 余灏然设计小结 (26)

6.3.2 魏嘉设计小结 (27)

6.3.3 张越设计小结 (27)

7 附录A 课题任务分工 (28)

A-1 课题程序设计分工 (28)

A-2 课题报告分工 (29)

附录C 用户操作手册（可选） (30)

C.1 运行环境说明 (30)

C.2 操作说明 (30)

1 课题背景

1.1 课题任务

【问题描述】

由输入的四则运算表达式字符串，动态生成算术表达式所对应的二叉树，通过表达式二叉树自动求值并输出。

【设计要求】

设计十进制整数四则运算计算器。

（1）采用二叉树、栈等数据结构。

（2）给定表达式字符串，生成二叉链表的表达式二叉树。

（3）对表达式二叉树采用后序遍历求值并输出。

（4）可以考虑加入复数四则运算功能。

（5）其它完善性功能。

1.2 课题原理

用二叉链表处理表达式字符串，用栈处理括号在表达式计算时的优先级问题，并且使用MFC编程语言实现可视化。

1.2.1二叉链表

1.2.2栈处理符号表达式

1.2.3MFC编程语言实现可视化

用MFC语言中对按钮Button功能的添加，将外界输入的由数字0~9，符号“+”、“-”、“*”、“/”、“（”、“）”构成的表达式传入编辑框中的变量CString 中。与此同时，可以使用退格键“←”执行退格功能和清屏键执行清屏功能。并且使用“=”按钮时，对输入的表达式进行计算。最终，由编辑框输出计算结果。

流程图如下

流程图1

开始

输入表达式

表达式入栈

（反转表达式）

转化为先序表

达式

后序遍历求值

输出计算结果

结束

流程图2

1.3相关知识

生成二叉链表，树的后序遍历，MFC编程语言实现可视化

2需求分析

2.1 课题调研

整数十进制四则运算计算器，用户输入算式程序程序运行并输出运算结果。

2.2 用户需求分析

（1）用户可以通过MFC按钮输入多项式；

（2）可输入带括号的运算；

（3）该程序应该有对用户错误输入的辨别纠错功能；

（4）程序应具有演示功能和调试功能。

（5）程序应具有良好的人机接口。

（6）程序应能友好的展现结果。

3方案设计

3.1 总体功能设计

十进制整数四则运算

3.2 数据结构设计

栈结构，用来储存多项式及生成树；

树结构，用来后序遍历以求多项式的值。

3.3 函数原型设计

函数原型参数说明功能描述

void turn(Stack &T,char d[max])

void change(Stack

T,Stack &S)栈T，字符数组d

[]

栈T，栈S

将输入的多项式压栈并转化为前缀

表达式

int CreatTree(Tree

&T,Stack &S)

Void PostOrder(Tree

T,Stack &S)

树T，栈S 建立二叉链表并且后序遍历求值

3.4主算法设计

⑴将输入的表达式压栈，并将其转换为前缀表达式；

⑵由前缀表达式生成二叉链表；

⑶后序遍历二叉树求值。

3.5 用户界面设计

使用MFC编程语言设计界面如下：

4 方案实现

4.1 开发环境与工具

主要编程环境：Blend for Visual Studio 2013

编程工具：C++。

4.2 程序设计关键技术

⑴将输入的表达式压栈，并将其转换为前缀表达式；

⑵由前缀表达式生成二叉链表；

⑶后序遍历二叉树求值。

4.3 个人设计实现（按组员分工）

4.3.1 余灏然设计实现

数据结构定义和描述：

反转表达式及转换前缀表达式：

#include"head.h"

#include"fuhao.cpp"

#include"iostream"

using namespace std;

void turn(Stack &T,char d[max]);

void change(Stack T,Stack &S);

void turn(Stack &T,char d[max]) //字符串输入表达式且压栈

{

int h,r=0; //h用于重置数字，r用于计位置

data b;

while(1)

{

if(d[r]=='\0') break;

if( In(d[r]) )

{

b.k=2;

b.s=d[r++];

Push(T,b);

}

else

{

h=0;

while(d[r]!='\0')

{

if(d[r]=='+'||d[r]=='-'||d[r]=='*'||d[r]=='/'||d[r]=='('||d[r]==')') break;

h*=10;

switch(d[r])

{

case '1': h+=1;break;

case '2': h+=2;break;

case '3': h+=3;break;

case '4': h+=4;break;

case '5': h+=5;break;

case '6': h+=6;break;

case '7': h+=7;break;

case '8': h+=8;break;

case '9': h+=9;break;

case '0': h+=0;break;

default: cout<<"表达式有误!"; exit(0);

}

r++;

}

b.k=1;

b.i=h;

Push(T,b);

}

}

}

void change(Stack T,Stack &S) //转前置表达式

{

Stack P;

InitStack(P);

data a,b,c;

a.k=2 ; a.s='=';

Push(P,a);

while(1)

{

Pop(T,b);

if(b.k==2 && b.s=='=') break;

if(b.k==1) { Push(S,b);continue; }

if(b.k==2)

{

if( b.s==')' ) { Push(P,b);continue; }

if( b.s!='('&& b.s!=')')

{

while(1)

{

GetTop(P,c);

if( Compare(b.s,c.s)=='>'||Compare(b.s,c.s)=='=') {Push(P,b);break;}

else { Pop(P,c); Push(S,c);}

}

}

if( b.s=='(' )

{

while(1)

{

Pop(P,c);

if(c.k==2 && c.s==')') break;

Push(S,c);

}

}

}

}

while(1)

{

GetTop(P,c);

if(c.k==2 && c.s=='=') break;

Pop(P,c);

Push(S,c);

}

}

4.3.2 魏嘉设计实现

符号相关操作：

#include"iostream"

using namespace std;

char Compare(char a,char b);

int In(char c);

int Operate(int b,char x,int a);

/*判断运算的优先顺序*/

char Compare(char a,char b)

{

char c;

switch(a)

{

case'+':if(b=='*'||b=='/'||b=='(')

c='<';

else c='>';

break;

case'-':if(b=='*'||b=='/'||b=='(')

c='<';

else c='>';

break;

case'*':if(b=='(')

c='<';

else c='>';

break;

case'/':if(b=='(')

c='<';

else c='>';

break;

case'(':if(b==')')c='=';

else c='<';

break;

case')':c='>';

break;

case'=':if(b=='=')

c='=';

else c='<';

break;

}

return c;

}

int In(char c){

if(c=='+' || c=='-' || c=='*'|| c=='/'||c=='('||c==')'||c=='=')

return 1;

else return 0;

}

int Operate(int b,char x,int a)

{

int z;

switch(x){

case'+': z=a+b;break;

case'-': z=a-b;break;

case'*': z=a*b;break;

case'/': z=a/b;break;

}

return z;

}

#include"head.h"

#include"fuhao.cpp"

#include"iostream"

using namespace std;

void turn(Stack &T,char d[max]);

void change(Stack T,Stack &S);

typedef struct Node{

data p;

struct Node *lchild,*rchild;

}Node,*Tree;

后序遍历求值：

void PostOrder(Tree T,Stack &S) //利用递归，后序遍历并求值，T为二叉树，S为存储用的栈

{

data a,b,c,d;

if(T!=NULL)

{

PostOrder(T->lchild,S);

PostOrder(T->rchild,S);

c=T->p;

if(c.k==1) Push(S,c);

if(c.k==2)

{

Pop(S,b);Pop(S,a);

d.k=1;d.i=Operate(b.i,c.s,a.i);

Push(S,d);

}

}

}

4.3.3 张越设计实现

建立二叉链表：

#include"head.h"

#include"fuhao.cpp"

#include"iostream"

using namespace std;

void turn(Stack &T,char d[max]);

void change(Stack T,Stack &S);

typedef struct Node{

data p;

struct Node *lchild,*rchild;

}Node,*Tree;

int CreatTree(Tree &T,Stack &S) //建立二叉链表

{

data b,c;

Pop(S,b);

if(b.k==1) //当遇数字时，在后面补两个空位，用于建立二叉树{ c.k=3; Push(S,c); Push(S,c);}

if(b.k==3) T=NULL;

else

{

if(!(T=(Node*)malloc(sizeof(Node)))) exit(-1);

数据结构课程实验指导书

数据结构实验指导书 一、实验目的 《数据结构》是计算机学科一门重要的专业基础课程，也是计算机学科的一门核心课程。本课程较为系统地论述了软件设计中常用的数据结构以及相应的存储结构与实现算法，并做了相应的性能分析和比较，课程内容丰富，理论系统。本课程的学习将为后续课程的学习以及软件设计水平的提高打下良好的基础。 由于以下原因，使得掌握这门课程具有较大的难度： 1）理论艰深，方法灵活，给学习带来困难； 2）内容丰富，涉及的知识较多，学习有一定的难度； 3）侧重于知识的实际应用，要求学生有较好的思维以及较强的分析和解决问题的能力，因而加大了学习的难度； 根据《数据结构》课程本身的特性，通过实验实践内容的训练，突出构造性思维训练的特征，目的是提高学生分析问题，组织数据及设计大型软件的能力。 课程上机实验的目的，不仅仅是验证教材和讲课的内容，检查自己所编的程序是否正确，课程安排的上机实验的目的可以概括为如下几个方面： （1）加深对课堂讲授内容的理解 实验是对学生的一种全面综合训练。是与课堂听讲、自学和练习相辅相成的必不可少的一个教学环节。通常，实验题中的问题比平时的习题复杂得多，也更接近实际。实验着眼于原理与应用的结合点，使学生学会如何把书上学到的知识用于解决实际问题，培养软件工作所需要的动手能力；另一方面，能使书上的知识变" 活" ，起到深化理解和灵活掌握教学内容的目的。 不少学生在解答习题尤其是算法设计时，觉得无从下手。实验中的内容和教科书的内容是密切相关的，解决题目要求所需的各种技术大多可从教科书中找到，只不过其出

现的形式呈多样化，因此需要仔细体会，在反复实践的过程中才能掌握。 (2) 培养学生软件设计的综合能力 平时的练习较偏重于如何编写功能单一的" 小" 算法，而实验题是软件设计的综合训练，包括问题分析、总体结构设计、用户界面设计、程序设计基本技能和技巧，多人合作，以至一整套软件工作规范的训练和科学作风的培养。 通过实验使学生不仅能够深化理解教学内容，进一步提高灵活运用数据结构、算法和程序设计技术的能力，而且可以在需求分析、总体结构设计、算法设计、程序设计、上机操作及程序调试等基本技能方面受到综合训练。实验着眼于原理与应用的结合点，使学生学会如何把书本上和课堂上学到的知识用于解决实际问题，从而培养计算机软件工作所需要的动手能力。 (3) 熟悉程序开发环境，学习上机调试程序一个程序从编辑，编译，连接到运行，都要在一定的外部操作环境下才能进行。所谓" 环境" 就是所用的计算机系统硬件，软件条件，只有学会使用这些环境，才能进行 程序开发工作。通过上机实验，熟练地掌握程序的开发环境，为以后真正编写计算机程序解决实际问题打下基础。同时，在今后遇到其它开发环境时就会触类旁通，很快掌握新系统的使用。 完成程序的编写，决不意味着万事大吉。你认为万无一失的程序，实际上机运行时可能不断出现麻烦。如编译程序检测出一大堆语法错误。有时程序本身不存在语法错误，也能够顺利运行，但是运行结果显然是错误的。开发环境所提供的编译系统无法发现这种程序逻辑错误，只能靠自己的上机经验分析判断错误所在。程序的调试是一个技巧性很强的工作，尽快掌握程序调试方法是非常重要的。分析问题，选择算法，编好程序，只能说完成一半工作，另一半工作就是调试程序，运行程序并得到正确结果。 二、实验要求 常用的软件开发方法，是将软件开发过程划分为分析、设计、实现和维护四个阶段。虽然数据结构课程中的实验题目的远不如从实际问题中的复杂程度度高，但为了培养一个软件工作者所应具备的科学工作的方法和作风，也应遵循以下五个步骤来完成实验题目： 1) 问题分析和任务定义 在进行设计之前，首先应该充分地分析和理解问题，明确问题要求做什么?限制条件是什么。本步骤强调的是做什么?而不是怎么做。对问题的描述应避开算法和所涉及的数据类型，而是对所需完成的任务作出明确的回答。例如：输入数据的类型、值的范围以及输入的

数据结构习题(456章)

第四章串 一．选择题 1．若串S='software',其子串的数目是（） A．8 B．37 C．36 D．9 2．设有两个串p和q,求q在p中首次出现的位置的运算称作（） A．连接B．模式匹配C．求串长D．求子串 3．设字符串S1=“ABCDEFG”，S2=“PQRST”，则运算： S=CONCAT（SUBSTR（S1，2，LEN（S2））；SUBSTR（S1，LEN（S2），2））；后的串值为（） A．A BCDEF B．BCDEFG C．BCDPQRST D． BCDEFEF 4．下面的说法中，只有（）是正确的 A．串是一种特殊的线性表B．串的长度必须大于零 C．串中元素只能是字母D．空串就是空白串 5．两个字符串相等的条件是（） A．两串的长度相等 B．两串包含的字符相同 C．两串的长度相等，并且两串包含的字符相同 D．两串的长度相等，并且对应位置上的字符相同 二．填空题 1．串“ababcbaababd”的next函数值为，nextval函数值为。2．子串的长度为。 第五章数组和广义表 一．选择题 1．设有数组A[i,j]，数组的每个元素长度为3字节，i的值为1 到8 ，j的值为1 到10，数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素A[5，8]的存储首地址为( ) A. BA+141 B. BA+180 C. BA+222 D. BA+225 2．假设以行序为主序存储二维数组A=array[1..100，1..100]，设每个数据元素占2个存储单元，基地址为10，则LOC[5，5]=（） A. 808 B. 818 C. 1010 D. 1020 3．对稀疏矩阵进行压缩存储目的是（） A．便于进行矩阵运算B．便于输入和输出C．节省存储空间D．降低运算的时间复杂度 4．假设以三元组表表示稀疏矩阵，则与如图所示三元组表对应的4×5的稀疏矩阵是（注：矩阵的行列下标均从1开始）（）

简单的四则运算计算器程序

简单的四则运算计算器程序

注：1、报告内的项目或内容设置，可根据实际情况加以调整和补充。 2、教师批改学生实验报告时间应在学生提交实验报告时间后10日内。

附件：程序源代码 // sizheyunsuan.cpp : Defines the entry point for the console application. #include #include const int MAX=100; class Operand{ private: double operS; public: Operand(){} Operand(double opers){ operS=opers; } void set(double opers){ operS=opers; } double get() { return operS;} }; class Operator{ private: char operF; int priority; public: Operator(){} Operator(char operf) { operF=operf; switch(operf) { case'(':priority=-1;break; case'+':priority=0;break; case'-':priority=0;break; case'*':priority=1;break; case'/':priority=1;break; case')':priority=2;break; } } void set(char operf){ operF=operf; } char get(){ return operF;} int getpriority(){ return priority; } };

计算机数据结构习题1附答案

页眉内容 1 第1章 绪论 1.1 简述下列术语：数据，数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。 解：数据是对客观事物的符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。 数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 数据对象是性质相同的数据元素的集合，是数据的一个子集。 数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 存储结构是数据结构在计算机中的表示。 数据类型是一个值的集合和定义在这个值集上的一组操作的总称。 抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。是对一般数据类型的扩展。 1.2 填空题： 1.常见的数据结构有__结构，_____结构，____结构等三种。 2.常见的存储结构有_________结构，______结构等两种。 3.数据的基本单位是____，它在计算机中是作为一个整体来处理的。 4.数据结构中的结构是指数据间的逻辑关系，常见的结构可分为两大类，______和_____。 5.《数据结构》课程讨论的主要内容是数据的逻辑结构、存储结构和________。 1.2设有数据结构(D,R)，其中 {}4,3,2,1d d d d D =，{}r R =，()()(){}4,3,3,2,2,1d d d d d d r = 试按图论中图的画法惯例画出其逻辑结构图。 解： 1.3设有以下三个函数： ()1000 2124++=n n n f ，()3450015n n n g +=，()n n n n h log 5005.3+= 请判断以下断言正确与否： (1) f(n)是O(g(n)) (2) h(n)是O(f(n)) (3) g(n)是O(h(n)) (4) h(n)是O(n 3.5) (5) h(n)是O(nlogn) 解：(1)对 (2)错 (3)错 (4)对 (5)错

数据结构实验报告代码

线性表 代码一 #include "stdio.h" #include "malloc.h" #define OK 1 #define ERROR 0 #define OVERFLOW -2 #define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 typedef struct { int * elem; int length; int listsize; }SqList; int InitList_Sq(SqList *L) { L->elem = (int*)malloc(LIST_INIT_SIZE*sizeof(int)); if (!L->elem) return ERROR; L->length = 0; L->listsize = LIST_INIT_SIZE; return OK; } int ListInsert_Sq(SqList *L, int i,int e) { int *p,*newbase,*q; if (i < 1 || i > L->length+1) return ERROR; if (L->length >= L->listsize) { newbase = (int *)realloc(L->elem,(L->listsize+LISTINCREMENT)*sizeof (int)); if (!newbase) return ERROR; L->elem = newbase; L->listsize += LISTINCREMENT; } q = &(L->elem[i-1]); //插入后元素后移for(p=&(L->elem[L->length-1]);p>=q;p--) *(p+1)=*p; *q=e; L->length++; return OK; } int ListDelete_Sq(SqList *L, int i, int *e) {

数据结构实验8实验报告

暨南大学本科实验报告专用纸 课程名称数据结构实验成绩评定 实验项目名称习题6.37 6.38 6.39 指导教师孙世良 实验项目编号实验8 实验项目类型实验地点实验楼三楼机房学生姓名林炜哲学号2013053005 学院电气信息学院系专业软件工程 实验时间年月日午～月日午温度℃湿度(一)实验目的 熟悉和理解二叉树的结构特性； 熟悉二叉树的各种存储结构的特点及适用范围； 掌握遍历二叉树的各种操作及其实现方式。 理解二叉树线索化的实质是建立结点与其在相应序列中的前去或后继之间的直接联系，熟练掌握二叉树的线索化的过程以及在中序线索化树上找给定结点的前驱和后继的方法。 (二)实验内容和要求 6.37试利用栈的基本操作写出先序遍历的非递归形式的算法。 6.38同题6.37条件，写出后序遍历的非递归算法（提示：为分辨后序遍 历时两次进栈的不同返回点需在指针进栈时同时将一个标志进栈）。 6.39假设在二叉链表的结点中增设两个域：双亲域以指示其双亲结点； 标志域以区分在遍历过程中到达该结点时应继续向左或向右或访问该节点。试以此存储结构编写不用栈进行后序遍历的递推形式的算法。(三)主要仪器设备 实验环境：Microsoft Visual Studio 2012 (四)源程序

6.37： #include #include #define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 #define TRUE 1 #define FALSE 0 typedef struct bitnode{ char data; struct bitnode *lchild,*rchild; }bitnode,*bitree; void create(bitree &T){ char t; t=getchar(); if(t==' ') T=NULL; else{ if( !( T=(bitnode*)malloc(sizeof(bitnode)) ) ) exit(0); T->data=t; create(T->lchild); create(T->rchild); } } typedef struct{ bitree *base; bitree *top; int stacksize; }sqstack; void initstack(sqstack &S){ S.base=(bitree*)malloc(STACK_INIT_SIZE *sizeof(bitree)); if(!S.base) exit(0); S.top=S.base; S.stacksize=STACK_INIT_SIZE; } void Push(sqstack &s,bitree e){ if(s.top - s.base >= s.stacksize){ s.base =

四则运算计算器

基于单片机实现的四则运算计算器 姓名 学号： 班级： 专业名称：测控技术与仪器 指导教师： 东北大学 2016年1月

课程设计（论文）任务书课程设计（论文）题目：基于单片机实现的四则运算计算器 基本内容和设计要求： 1、主机的矩阵键盘输入数和运算符号，从机显示运算结果。 2、主从单片机串行通信系统，并在LCD上显示运算内容及结果。 3、计算结果超过十位数字则显示错误。 4、运算除法时，结果只取整数，不是四舍五入。 5、有清零功能。

目录 课程设计（论文）任务书................................................................................................ i i 摘要 (1) 第1章绪论 (2) 1.1计算器简介 (2) 1.2设计主要内容 (2) 第2章系统硬件设计 (4) 2.1硬件组成 (4) 2.2输入模块 (4) 2.3输出模块 (5) 2.4运算模块 (5) 第3章系统软件设计 (7) 3.1 主程序 (7) 3.1.1主程序框图及初始化 (7) 3.1.2LCD程序框图及初始化 (8) 3.1.3键盘程序框图及初始化 (9) 3.1.4运算程序框图 (10) 第4章调试测试与实验分析 (11) 4.1 计算器调试 (11) 参考文献 (12) 心得体会 (13) 附录硬件原理图及PCB图 (14) 附录程序清单 (15) 附录实物照片 (28)

摘要 单片机的出现是计算机制造技术高速发展的产物，它是嵌入式控制系统的核心，如今，它已广泛的应用到我们生活的各个领域，电子、科技、通信、汽车、工业等。本设计是基于89C52RC单片机来进行的四则运算计算器系统设计，可以完成计算器的键盘输入，进行加、减、乘、除的基本四则运算，并在LCD1602液晶显示屏上显示相应的结果。本电路采用89C52RC单片机为主要控制电路，利用4*4矩阵键盘作为计算器以及运算符的输入。显示采用字符LCD静态显示。软件用C语言编程，并用开发板进行演示。 关键词：计算器，89C52RC单片机，LCD，矩阵键盘

数据结构课程设计计算器

数据结构课程设计报告 实验一：计算器 设计要求 1、问题描述：设计一个计算器，可以实现计算器的简单运算，输出并检验结果的正确性，以及检验运算表达式的正确性。 2、输入：不含变量的数学表达式的中缀形式，可以接受的操作符包括+、-、*、/、%、(、)。 具体事例如下： 3、输出：如果表达式正确，则输出表达式的正确结果；如果表达式非法，则输出错误信息。 具体事例如下： 知识点：堆栈、队列 实际输入输出情况： 正确的表达式

对负数的处理 表达式括号不匹配 表达式出现非法字符 表达式中操作符位置错误 求余操作符左右出现非整数 其他输入错误 数据结构与算法描述 解决问题的整体思路： 将用户输入的中缀表达式转换成后缀表达式，再利用转换后的后缀表达式进行计算得出结果。 解决本问题所需要的数据结构与算法： 用到的数据结构是堆栈。主要算法描述如下： A．将中缀表达式转换为后缀表达式： 1. 将中缀表达式从头逐个字符扫描，在此过程中，遇到的字符有以下几种情况： 1）数字 2）小数点 3）合法操作符+ - * / %

4）左括号 5）右括号 6）非法字符 2. 首先为操作符初始化一个map priority，用于保存各个操作符的优先级，其中+ -为0，* / %为1 3. 对于输入的字符串from和输出的字符串to，采用以下过程： 初始化遍历器std::string::iterator it=infix.begin() 在当it!=from.end()，执行如下操作 4. 遇到数字或小数点时将其加入到后缀表达式： case'1':case'2':case'3':case'4':case'5':case'6':case'7':case '8':case'9':case'0':case'.': { to=to+*it; break; } 5. 遇到操作符（+，-，*，/，%）时，如果此时栈顶操作符的优先级比此时的操作符优先级低，则将其入栈，否则将栈中的操作符从栈顶逐个加入到后缀表达式，直到栈空或者遇到左括号，并将此时的操作符加入到栈中，在此过程中需判断表达式中是否出现输入错误： case'+':case'-':case'*':case'/':case'%': { if((it+1)==from.end()) { cout<<"输入错误：运算符号右边缺少运算数"<

数据结构实验一的源代码

#include #include typedef struct Node { int key;//密码 int num;//编号 struct Node *next;//指向下一个节点 } Node, *Link; void InitList(Link &L) //创建一个空的链表{ L = (Node *)malloc(sizeof(Node)); if (!L) exit(1); L->key = 0; L->num = 0; L->next = L; } void Creatlinklist(int n, Link &L) //初始化链表{ Link p, q; q = L; for (int i = 1; i <= n; i++) { p = (Node *)malloc(sizeof(Node)); if (!p) exit(1); scanf("%d", &p->key); p->num = i; L->next = p; L = p; } L->next = q->next; free(q); } Link Locate_m(Link &p, int m)//找到第m个 { Link q; for (int j = 1; jnext; q = p->next; m = q->key;

return q; } void Delete_m(Link &L, Link p, Link q)//删除第m个{ p->next = q->next; free(q); } void main() { Link L, p, q; int n, m; L = NULL; InitList(L);//构造出一个只有头结点的空链表 printf("请输入初始密码人数每个人的密码：\n"); scanf("%d", &m);//初始密码为m scanf("%d", &n);// Creatlinklist(n, L);//构建 p = L; for (int i = 1; i <= n; i++) { q = Locate_m(p, m);//找到第m个 printf("%d", q->num); Delete_m(L, p, q);//删除第m个 } system("pause"); }

数据结构实验报告(四)

《数据结构》实验报告 班级： 学号： 姓名：

实验四二叉树的基本操作实验环境：Visual C++ 实验目的： 1、掌握二叉树的二叉链式存储结构； 2、掌握二叉树的建立，遍历等操作。 实验内容： 通过完全前序序列创建一棵二叉树，完成如下功能： 1)输出二叉树的前序遍历序列； 2)输出二叉树的中序遍历序列； 3)输出二叉树的后序遍历序列； 4)统计二叉树的结点总数； 5)统计二叉树中叶子结点的个数； 实验提示： //二叉树的二叉链式存储表示 typedef char TElemType; typedef struct BiTNode{ TElemType data; struct BiTNode *lchild,*rchild; }BiTNode,*BiTree;

一、程序源代码 #include #include #define MAXSIZE 30 typedef char ElemType; typedef struct TNode *BiTree; struct TNode { char data; BiTree lchild; BiTree rchild; }; int IsEmpty_BiTree(BiTree *T) { if(*T == NULL) return 1; else return 0;

} void Create_BiTree(BiTree *T){ char ch; ch = getchar(); //当输入的是"#"时，认为该子树为空 if(ch == '#') *T = NULL; //创建树结点 else{ *T = (BiTree)malloc(sizeof(struct TNode)); (*T)->data = ch; //生成树结点 //生成左子树 Create_BiTree(&(*T)->lchild); //生成右子树 Create_BiTree(&(*T)->rchild); } } void TraverseBiTree(BiTree T) { //先序遍历 if(T == NULL) return;

第6章 四则运算计算器

第6章四则运算计算器 本章介绍的项目是大家十分熟悉的计算器，通过该项目的实践，我们将学习状态图的一些基本知识、C# 中方法的概念和应用以及键盘事件的运用，同时，训练编写一个略微复杂的Windows应用程序的设计思路。 为了使读者能够循序渐进地学习此类项目的设计，我们根据难度的不同，分为三个项目分别实现，首先完成项目一：整数的四则运算计算器，然后在此基础上完善，实现项目二：实数四则运算计算器，最后添加记忆功能，完成项目三：带记功能的实数四则运算计算器。 6.1 项目一：整数四则运算计算器设计 6.1.1 工作目标 终极目标：完成一个整数四则运算的计算器，界面如图6.1所示： 图6.1 整数四则运算计算器

促成目标： 1.完成整数四则运算计算器整体设计——状态机分析； 2.完成整数四则运算模块设计——流程分析； 3.完成整数四则运算计算器的程序界面设计及属性设置； 4.完成整数四则运算器的程序编码； 5.对整数四则运算计算器进行必要的运行测试，如有错误进行调试修改。 6.1.2 工作任务 工作任务一：构建计算器的状态图； 工作任务二：设计程序模块的流程图； 工作任务三：设计界面完成窗体及控件的属性设置； 工作任务四：编写程序代码； 工作任务五：测试软件，对错误进行调试修改。 6.1.3 工作任务一：构建计算器的状态图 1、知识准备——状态图 状态图(Statechart Diagram)是描述一个实体基于事件反应的动态行为，显示了该实体如何根据当前所处的状态对不同的事件做出反应的。状态图用于显示状态机（它指定对象所在的状态序列）、使对象达到这些状态的事件和条件、以及达到这些状态时所发生的操作。状态机由状态组成，各状态由转移链接在一起。状态是对象执行某项活动或等待某个事件时的条件。转移是两个状态之间的关系，它由某个事件触发，然后执行特定的操作或评估并导致特定的结束状态。图6.2描绘了状态机的各种元素。

计算机数据结构考研真题及其答案

第1章绪论 一、选择题 1. 算法的计算量的大小称为计算的（）。【北京邮电大学2000 二、3 （20/8分）】 A．效率 B. 复杂性 C. 现实性 D. 难度2. 算法的时间复杂度取决于（）【中科院计算所 1998 二、1 （2分）】 A．问题的规模 B. 待处理数据的初态 C. A和B 3.计算机算法指的是（1），它必须具备（2）这三个特性。 (1) A．计算方法 B. 排序方法 C. 解决问题的步骤序列 D. 调度方法 (2) A．可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性 C. 确定性、有穷性、稳定性 D. 易读性、稳定性、安全性 【南京理工大学 1999 一、1（2分）【武汉交通科技大学 1996 一、1（ 4分）】 4．一个算法应该是（）。【中山大学 1998 二、1（2分）】 A．程序 B．问题求解步骤的描述 C．要满足五个基本特性D．A和C. 5. 下面关于算法说法错误的是（）【南京理工大学 2000 一、1（1.5分）】 A．算法最终必须由计算机程序实现 B.为解决某问题的算法同为该问题编写的程序含义是相同的 C. 算法的可行性是指指令不能有二义性 D. 以上几个都是错误的 6. 下面说法错误的是（）【南京理工大学 2000 一、2 （1.5分）】 (1）算法原地工作的含义是指不需要任何额外的辅助空间（2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法 （3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界（4）同一个算法，实现语言的级别越高，执行效率就越低 A．(1) B.(1),(2) C.(1),(4) D.(3) 7．从逻辑上可以把数据结构分为（）两大类。【武汉交通科技大学 1996 一、4（2分）】 A．动态结构、静态结构 B．顺序结构、链式结构

数据结构实验程序

顺序表的基本操作 #include using namespace std; typedef int datatype; #define maxsize 1024 #define NULL -1 typedef struct { datatype *data; int last; }sequenlist; void SETNULL(sequenlist &L) { L.data=new datatype[maxsize]; for(int i=0;i>https://www.doczj.com/doc/e5438914.html,st; cout<<"请输入"<>L.data[i]; } int LENGTH(sequenlist &L) { int i=0; while(L.data[i]!=NULL) i++; return i; } datatype GET(sequenlist &L,int i) { if(i<1||i>https://www.doczj.com/doc/e5438914.html,st) { cout<<"error1"<

int j=0; while(L.data[j]!=x) j++; if(j==https://www.doczj.com/doc/e5438914.html,st) { cout<<"所查找值不存在！"<=maxsize-1) { cout<<"overflow"; return NULL; } else if(i<1||(i>https://www.doczj.com/doc/e5438914.html,st)) { cout<<"error2"<=i-1;j--) L.data[j+1]=L.data[j]; L.data[i-1]=x; https://www.doczj.com/doc/e5438914.html,st++; } return 1; } int DELETE(sequenlist &L,int i) { int j; if((i<1)||(i>https://www.doczj.com/doc/e5438914.html,st+1)) { cout<<"error3"<

数据结构实验二叉树

实验六：二叉树及其应用 一、实验目的 树是数据结构中应用极为广泛的非线性结构，本单元的实验达到熟悉二叉树的存储结构的特性，以及如何应用树结构解决具体问题。 二、问题描述 首先，掌握二叉树的各种存储结构和熟悉对二叉树的基本操作。其次，以二叉树表示算术表达式的基础上，设计一个十进制的四则运算的计算器。 如算术表达式：a+b*(c-d)-e/f 三、实验要求 如果利用完全二叉树的性质和二叉链表结构建立一棵二叉树，分别计算统计叶子结点的个数。求二叉树的深度。十进制的四则运算的计算器可以接收用户来自键盘的输入。由输入的表达式字符串动态生成算术表达式所对应的二叉树。自动完成求值运算和输出结果。四、实验环境 PC微机 DOS操作系统或 Windows 操作系统 Turbo C 程序集成环境或 Visual C++ 程序集成环境 五、实验步骤 1、根据二叉树的各种存储结构建立二叉树； 2、设计求叶子结点个数算法和树的深度算法； 3、根据表达式建立相应的二叉树，生成表达式树的模块； 4、根据表达式树，求出表达式值，生成求值模块； 5、程序运行效果，测试数据分析算法。 六、测试数据 1、输入数据：*（+）3 正确结果： 2、输入数据：(1+2)*3+(5+6*7);

正确输出：56 七、表达式求值 由于表达式求值算法较为复杂，所以单独列出来加以分析： 1、主要思路：由于操作数是任意的实数，所以必须将原始的中缀表达式中的操作数、操作符以及括号分解出来，并以字符串的形式保存；然后再将其转换为后缀表达式的顺序，后缀表达式可以很容易地利用堆栈计算出表达式的值。 例如有如下的中缀表达式： a+b-c 转换成后缀表达式为： ab+c- 然后分别按从左到右放入栈中，如果碰到操作符就从栈中弹出两个操作数进行运算，最后再将运算结果放入栈中，依次进行直到表达式结束。如上述的后缀表达式先将a 和b 放入栈中，然后碰到操作符“+”，则从栈中弹出a 和b 进行a+b 的运算，并将其结果d（假设为d）放入栈中，然后再将c 放入栈中，最后是操作符“-”，所以再弹出d和c 进行d-c 运算，并将其结果再次放入栈中，此时表达式结束，则栈中的元素值就是该表达式最后的运算结果。当然将原始的中缀表达式转换为后缀表达式比较关键，要同时考虑操作符的优先级以及对有括号的情况下的处理，相关内容会在算法具体实现中详细讨论。 2、求值过程 一、将原始的中缀表达式中的操作数、操作符以及括号按顺序分解出来，并以字符串的 形式保存。 二、将分解的中缀表达式转换为后缀表达式的形式，即调整各项字符串的顺序，并将括 号处理掉。 三、计算后缀表达式的值。 3、中缀表达式分解 DivideExpressionToItem()函数。分解出原始中缀表达式中的操作数、操作符以及括号，保存在队列中，以本实验中的数据为例，分解完成后队列中的保存顺序如下图所示：

汇编语言课程设计报告实现加减乘除四则运算的计算器

实现加减乘除四则运算的计算器 目录 1 概述 (1) 1.1 课程设计目的 (1) 1.2 课程设计内容 (1) 2 系统需求分析 (1) 2.1 系统目标 (1) 2.2 主体功能 (2) 3 系统概要设计 (2) 3.1 系统的功能模块划分 (2) 3.2 系统流程图 (3) 4系统详细设计 (4) 5 测试 (5) 5.1 正确输出 (5) 5.2 实际输出 (6) 6 小结 (7) 参考文献 (8) 附录 (9) 附录1 源程序清单 (9)

汇编语言课程设计报告（2011） 实现加减乘除四则运算计算器的设计 1 概述 1.1 课程设计目的 运用汇编语言，实现简单计算器的一般功能.通过该程序设计，让我们熟悉并掌握DOS系统功能调方法用及BIOS系统功能调用方法，同时在程序设计过程中熟悉并掌握各种指令的应用，知道编程的具体流程，以及掌握DEBUG的一系列的功能执行命令，及用它进行调试，运行功能。 汇编语言是计算机能够提供给用户使用的最快而又最有效的语言，也是能够利用计算机所有硬件特性并能直接控制硬件的唯一语言。由于汇编语言如此的接近计算机硬件，因此，它可以最大限度地发挥计算机硬件的性能。由此可见汇编语言的重要性，学好这门课程，同样可为相关的专业打下基础。 汇编语言程序设计课程设计是在教学实践基础上进行的一次试验，也是对该课程所学理论知识的深化和提高。因此，要求学生能综合应用所学知识，设计和制造出具有具有一定功能的应用系统，并且在实验的基本技能方面进行了一次全面的训练。 此外，它还可以培养学生综合运用所学知识独立完成汇编程序课题的能力，使学生能够较全面的巩固和应用课堂上所学的基本理论和程序设计方法，能够较熟练地完成汇编语言程序的设计和调试。它同样可以提高学生运用理论去处理实际问题的能力和独立思考的能力，使学生的编程思想和编程能力有所提高，最终达到熟练地掌握编写汇编源程序的基本方法的目的。 1.2 课程设计内容 设计一个能实现加减乘除取余计算的程序。将键盘输入的表达式预放入一缓冲区中，然后从该缓冲区的第一个字符开始读取判断，当读到一个有效的表达式时对表达式进行相应的运算后，输出用十六进制数表示的运算结果。 2 系统需求分析 2.1 系统目标 1．熟悉汇编指令、宏汇编语言的编程方法 2． BIOS中断调用、系统功能中断调用方法 3．磁盘文件、及文件内容操作 目标：要求该程序接受从键盘输入的十六进制数，执行相应的计算后，计算结 1

数据结构实验报告全集

数据结构实验报告全集 实验一线性表基本操作和简单程序 1．实验目的 （1）掌握使用Visual C++ 上机调试程序的基本方法； （2）掌握线性表的基本操作：初始化、插入、删除、取数据元素等运算在顺序存储结构和链表存储结构上的程序设计方法。 2．实验要求 （1）认真阅读和掌握和本实验相关的教材内容。 （2）认真阅读和掌握本章相关内容的程序。 （3）上机运行程序。 （4）保存和打印出程序的运行结果，并结合程序进行分析。 （5）按照你对线性表的操作需要，重新改写主程序并运行，打印出文件清单和运行结果 实验代码： 1）头文件模块 #include >验目的 掌握顺序栈的基本操作：初始化栈、判栈空否、入栈、出栈、取栈顶数据元素等运算以及程序实现方法。 2.实验要求 （1）认真阅读和掌握和本实验相关的教材内容。 （2）分析问题的要求，编写和调试完成程序。 （3）保存和打印出程序的运行结果，并分析程序的运行结果。 3.实验内容 利用栈的基本操作实现一个判断算术表达式中包含圆括号、方括号是否正确配对的程序。具体完成如下：

（1）定义栈的顺序存取结构。 （2）分别定义顺序栈的基本操作（初始化栈、判栈空否、入栈、出栈等）。 （3）定义一个函数用来判断算术表达式中包含圆括号、方括号是否正确配对。其中，括号配对共有四种情况：左右括号配对次序不正确；右括号多于左括号；左括号多于右括号；左右括号匹配正确。 （4）设计一个测试主函数进行测试。 （5）对程序的运行结果进行分析。 实验代码： #include < > #define MaxSize 100 typedef struct { ??? int data[MaxSize]; ??? int top; }SqStack; void InitStack(SqStack *st) 验目的 （1）进一步掌握指针变量的用途和程序设计方法。 （2）掌握二叉树的结构特征，以及链式存储结构的特点及程序设计方法。 （3）掌握构造二叉树的基本方法。 （4）掌握二叉树遍历算法的设计方法。 3．实验要求 （1）认真阅读和掌握和本实验相关的教材内容。 （2）掌握一个实际二叉树的创建方法。 （3）掌握二叉链存储结构下二叉树操作的设计方法和遍历操作设计方法。 4．实验内容 （1）定义二叉链存储结构。

汇编语言课程设计报告——实现加减乘除四则运算的计算器

汇编语言课程设计报告( 2011 -- 2012 年度第 2 学期) 实现加减乘除四则运算的计算器 专业计算机科学与技术 学生姓名 班级 学号 指导教师 完成日期

目录 目录 (1) 1概述 0 设计目的 0 设计内容 0 2系统需求分析 0 系统目标 0 主体功能 (1) 开发环境 (1) 3 系统概要设计 (1) 系统的功能模块划分 (1) 系统流程图 (2) 4系统详细设计 (3) 5测试 (4) 测试方案 (4) 测试结果 (4) 6小结 (4) 参考文献 (6) 附录 (7) 附录源程序清单 (7)

实现加减乘除四则运算的计算器 1 概述 设计目的 本课程设计是在学完教学大纲规定的全部内容、完成所有实践环节的基础上，旨在深化学生学习的汇编语言课程基本知识，进一步掌握汇编语言程序设计方法，提高分析问题、解决问题的综合应用能力。 设计内容 能实现加、减、乘、除的计算；该程序接受的是16进制数；执行时，需要在文件名后直接跟上计算表达式，如在命令提示符下执行结果如下： c:\tasm>js 3+2 5 2 系统需求分析 系统目标 本次汇编语言课程设计的最终目的是要实现一个简单加减乘除四则运算的计算器，要求编写一个程序，每运行一次可执行程序，可以实现数的加减乘除四则运算。比如，十进制数的加减乘除四则运算。我们曾经学习过两个具体数字进行加减法运算，但是对于简单计算器用汇编语言实现难点在于这两个要做运算的数是未知的，是由自己调用中断输入到屏幕上并要用程序存储起来的数，然后才能对这两个数进行运算，而且做的是加法运算、减法运算乘法运算还是除法运算也未可知，为此我们还要判断用户所输入的运算是四则运算中的哪一个运算。此外，运算过程中的进位或是借位，选择用什么样的方式进行输出，如何实现清屏等也是要解决的问题。

数据结构课程设计算术表达式求值计算器.doc

高级语言程序设计 《算术表达式求值》 课程设计报告

算术表达式求值 系统可以实现实现对算术四则混合运算表达式求值，并打印求值过程中运算符栈、操作数栈的变化过程。 第二章系统分析 开始运行时界面如下： 你可以输入一个表达式，按E对其进行求值。

第四章系统实现 #include #include #include #include #define N 100 double numStack[N]={0};//操作数栈 int numTop; char opStack[N];//运算符栈 int opTop; void print_num(double str1[],int n) { int i; printf("\n操作数栈：\n"); for(i=0;i

if(ch=='+'||ch=='-') return 2; if(ch=='*'||ch=='/') return 3; if(ch=='(') return -1; return 0; } double result(double num1,char op,double num2)//计算 { if(op=='+') return num1+num2; if(op=='-') return num1-num2; if(op=='*') return num1*num2; if(op=='/') return num1/num2; return 0; } int compute(char str[]) { double num=0; int i=0,j=1,k=1; numTop=opTop=0; while(str[i]!='\0'||opTop>0) { if(str[i]>='0'&&str[i]<='9') num=num*10+str[i]-'0'; else if( k==1&&str[i]=='-'&&(i==0||op(str[i-1])) ) k=-1; else { if(i>0&&!op(str[i-1])&&str[i]!='('&&str[i-1]!=')')