HUNAN UNIVERSITY 课程实验报告
题目:四则运算表达式求值
学生姓名:
学生学号:
专业班级:
指导老师:
完成日期:
一.需求分析
1.输入形式
用户需输入一个中缀表达式,用户需输入四则运算符.括号和数字回车表示结束才,如:(3+4)*5/3。当用户输入错误的符号时,提示用户输入有误,并重新输入。具体格式:
请输入四则运算表达式:
2.输出形式
如果该中缀表达式正确,那么在字符界面上输出其后缀表达式和计算结果,其中后缀表达式中两相邻操作数之间利用空格隔开;如果不正确,在字
符界面上输出表达式错误提示。具体格式:
后序表达式为:
最终结果为:
3.程序功能
该程序可以将用户输入的中缀表达式转换为后缀表达式并计算其结果
4.测试数据
1.请输入四则运算表达式:
21+23*(12-6)
后缀表达式为:
21 23 12 6 -*+
计算结果是 159
2.请输入四则运算表达式:
4/5+4-5
后缀表达式为:
4 5 / 4 + 5 -
计算结果是 -0.2
3.请输入四则运算表达式:
1.5+4/5
输入有误,请重新输入
4.请输入四则元素表达式:
21^7%y*4
输入有误,请重新输入
5.请输入四则运算表达式:
EXIT
程序结束运行
二.概要设计
1.抽象数据类型
定义一个二叉树,用来存储用户输入的表达式。表达式通过定义一个栈
来计算。
①为了访问二叉树中各节点的值,定义一个二叉树节点类,其ADT设计
如下:
数据对象:用户输入的中缀表达式
数据关系:二叉树所对应的数据关系
基本操作:
int val() ; //返回结点的数值
void setLeft(Node* ) ; //设置左结点
void setRight(Node* ); //设置右结点
Node* left()const; //返回左结点
Node* right()const ;//返回右结点
③为了更快对二叉树中的元素进行插入和查找操作,使用二叉链表实现二叉树
④为了计算中缀表达式的值,通过定义一个栈来计算。栈的ADT设计
如下:
数据对象:D={ a
i | a
i
∈ElemSet, i=1,2,...,n,n≥0 }
数据关系:R1={ | a i-1, a i∈D, i=2,...,n }
(约定a
n 端为栈顶,a
1
端为栈底。)
基本操作:
void clear();//初始化操作
bool push(const Elem&it);//插入元素操作
bool pop(const Elem&it);//删除操作
bool topValue(Elem&it);//获取栈顶元素的值
⑤为了存储中缀表达式,构建一个树的ADT
数据对象D:D是具有相同特性的数据元素的集合
数据关系R:
若D为空集,则称为空树。否则:
(1)在D中存在唯一的称为根的数据元素root;
(2) 当n>1时,其余结点可分为m (m>0)个互不相交的有限集T
1
,
T 2, …, T
m
,其中每一棵子集本身又是一棵符合本定义的树,称为
根root的子树。
基本操作:
void insert(const char&);
void clear();
算法基本思想
①先将用户输入的中缀表达式存入一个二叉树中,然后对该二叉树进行一
次后序遍历,即可得到该表达式的后序表达式,然后输出该后序表达式
即可;
②建树过程中构造两个栈S1和S2,S1用来存放节点指针,S2用来存储操
作符;遍历表达式时,如果遇到操作数,则建立节点并将其压入栈S1中。
遇到操作符则将其压入操作符栈S2中,若栈顶还有操作符则弹出该操作
符进行优先度比较,将优先度高的先放入栈中。弹出S2栈顶的操作符,
建立节点,并弹出两个S1栈顶的节点,将操作符结点的左右指针域指向
它们。直到操作符域为空。
③求后缀表达式值时再构造一个栈S用来存放操作数。因为在定义数据类
型的时候,要存储操作符,所以操作数也是用char类型存储的。后序遍
历到操作数是需要将其转换为float型并压入栈中。
遍历到操作符时,栈顶两个操作数弹出,进行运算并将结果压入栈中。
二叉树遍历完毕且栈中仅有一个元素,则计算完成,最后输出该结果
即可。
2.程序基本流程
本程序主要分四个模块:
输入模块:用户输入一个正确的中缀表达式,若输入错误,提示输入有
误并重新输入;
转换模块:将中缀表达式转换为后缀表达式;
计算模块:计算该中缀表达式的值;
输出模块:输出后缀表达式及其结果。
三.详细设计
1.物理数据类型
①二叉树节点类定义:
class Node
{
private:
Node *p1;//指向左子节点的指针
Node *p2;//指向右子节点的指针
public:
int val() {return data;} ;//返回结点的数值
void setLeft(Node* it){p1=it;} ; //设置左结点 void setRight(Node* it ){p2=it}; //设置右结点
Node* left()const{return p1;}; //返回左结点
Node* right()const{return p2;} ;//返回右结点
}
②栈的ADT设计:
class AStck:public Stack
{
private:
int size;//栈的长度
int top;//栈顶元素
Elem *listArray;//顺序表保存栈元素
public:
AStack(int sz)
{size=sz;top=0;listArray=new Car[sz];} //构造函数
~AStack(){delete []listArray;} //析构函数
void clear(){top=0;}//栈的清空
bool push(const char&item)
{
if(top==size) return false;
else
{listArray[top++]=item; return true; }
} //栈的插入
bool pop(char& item)
{
if(top==0) return false;
else
{
item=listArray[-top];return true;
}
} //栈的删除
bool topValue(char & it) const
{
if(top==0) return false;
else
{ it=listArray[top-1]; return true;}
} //获取栈顶元素
int length()const {return top;} //栈的长度
};
③树的ADT设计。用树来存储中缀表达式
class Tree
{
private:
Node *root;
public:
Tree()
{
root = NULL;
}
~Tree(){ delete[]root; }
void insert(BiTree &T,char exp[])
{
//插入
stack
char op;
Node N;
int i = 0;
OPTR.push('#');
op = OPTR.top();
while (!((exp[i] == '#') && (OPTR.top() == '#')))
{
if (IsDigital(exp[i]))
{//建立叶子节点并入栈 PTR
i += N.CrtNode(PTR, &exp[i]);
}
else if (exp[i] == ' ')
i++;
else
{
switch (exp[i])
{
case '(': {
OPTR.push(exp[i]);
i++;
break; }
case ')':
{
op = OPTR.top(); OPTR.pop();
while (op != '(')
{
N. CrtSubTree(PTR, op);
op = OPTR.top(); OPTR.pop();
}
i++;break;
}
default: //exp[i]是 + - * /
while (!OPTR.empty())
{
op = OPTR.top();
if (Precede(op, exp[i]) == '>')
{
N.CrtSubTree(PTR, op);
OPTR.pop();
}
if (exp[i] != '#')
{
OPTR.push(exp[i]);
i++;
}
break;
}
}
}//end else
}//end while
T = PTR.top();
PTR.pop();
}
};
2.算法具体步骤
④先将用户输入的中缀表达式存入一个二叉树中,然后对该二叉树进行一
次后序遍历,即可得到该表达式的后序表达式,然后输出该后序表达式即可;
⑤建树过程中构造两个栈S1和S2,S1用来存放节点指针,S2用来存储操
作符;遍历表达式时,如果遇到操作数,则建立节点并将其压入栈S1中。
遇到操作符则将其压入操作符栈S2中,若栈顶还有操作符则弹出该操作符进行优先度比较,将优先度高的先放入栈中。弹出S2栈顶的操作符,建立节点,并弹出两个S1栈顶的节点,将操作符结点的左右指针域指向它们。直到操作符域为空。
⑥求后缀表达式值时再构造一个栈S用来存放操作数。因为在定义数据类
型的时候,要存储操作符,所以操作数也是用char类型存储的。后序遍历到操作数是需要将其转换为float型并压入栈中。
遍历到操作符时,栈顶两个操作数弹出,进行运算并将结果压入栈中。二
叉树遍历完毕且栈中仅有一个元素,则计算完成,最后输出该结果即可。
树的构建部分伪代码:
class Tree
{
private:
Node *root;
public:
Tree()
{
root = NULL;
}
~Tree(){ delete[]root; }
void insert(BiTree &T,char exp[])
{
//插入
stack
stack
char op;
Node N;
int i = 0;
OPTR.push('#');
op = OPTR.top();
while (!((exp[i] == '#') && (OPTR.top() == '#')))
{
if (IsDigital(exp[i]))
{//建立叶子节点并入栈 PTR
i += N.CrtNode(PTR, &exp[i]);
}
else if (exp[i] == ' ')
i++;
else
{
switch (exp[i])
{
case '(': {
OPTR.push(exp[i]);
i++;
break; }
case ')':
{
op = OPTR.top(); OPTR.pop();
while (op != '(')
{
N. CrtSubTree(PTR, op);
op = OPTR.top(); OPTR.pop();
}
i++;break;
}
default: //exp[i]是 + - * /
while (!OPTR.empty())
{
op = OPTR.top();
if (Precede(op, exp[i]) == '>')
{
N.CrtSubTree(PTR, op);
OPTR.pop();
}
if (exp[i] != '#')
{
OPTR.push(exp[i]);
i++;
}
break;
}
}
}//end else
}//end while
T = PTR.top();
PTR.pop();
}
};
3.算法时空分析
用户输入的表达式存入二叉树的时间复杂度为?(n),对二叉树的后序遍历的时间复杂度也是?(n),运算的时间复杂度也是?(n)。所以总的时间复杂度是?(n)。
4.输入输出格式
输入:
char ch[100];//字符串数组存储表达式
while (i < 100)
{
scanf_s("%c", &c, 100);
ch[i++] = c;
}
输出:
T->PostOrderTraverse(T, exp, count);//输出后序遍历表达式
cout << "后序遍历表达式为:\n";
for (i = 0; i < count; i++)
cout << exp[i];
请输入一个四则运算表达式:
21+23*(12-6)
该表达式的后缀表达式为:
21 23 12 6 -*+
运算结果为:
159
5.函数调用关系
创建节点
创建二叉树
连接节点
主程序后序遍历输出二叉树
符数转换
表达式的计算优先级判断
四.调试分析
由于该程序算法较复杂,在实际编程中,曾因指针调用问题出现很多错误,后来通过设置断点的方法一一解决了这些问题。
五.测试结果
六.用户使用说明
1.本程序可以实现将一个四则运算中缀表达式转换成后缀表达式并输出结果的功
能;
2.请在DOS界面输入正确的四则运算表达式,若输入有误,请重新输入;
3.该程序只能实现加减乘除四项功能。
七.实验心得
通过该实验,我比较熟练地掌握了树的后序遍历的递归算法,以及通过栈来建树的基本方法
代码:
#include
using namespace std;
typedef float SElemtype;
typedef char * TElemType;
#include
#include
bool IsDigital(char ch)
{
if (ch >= '0'&&ch <= '9')
{
return 1; //是数字字母
}
return 0; //不是数字字母
}
char symbol[5][5] = { { '>', '>', '<', '<', '>' }, //符号优先级
{ '>', '>', '<', '<', '>' },
{ '>', '>', '>', '>', '>' },
{ '>', '>', '>', '>', '>' },
{ '<', '<', '<', '<', '=' } };
int sym2num(char s) //返回符号对应优先级矩阵位置
{
switch (s)
{
case '+': return 0; break;
case '-': return 1; break;
case '*': return 2; break;
case '/': return 3; break;
case '#': return 4; break;
default: break;
}
};
char Precede(char a, char b) //返回符号优先级{
return(symbol[sym2num(a)][sym2num(b)]);
}
class Node
{
private:
TElemType data;
int len;//
Node *p1;//指向左子节点的指针
Node *p2;//指向右子节点的指针
public:
char val() { return *data; };//返回结点的数值
void setLeft(Node* it){ p1 = it; }; //设置左结点
void setRight(Node* it){ p2 = it; }; //设置右结点
Node* left()const{ return p1; }; //返回左结点
Node* right()const{ return p2; };//返回右结点
//typedef Node *BiTree;
typedef Node*BiTree;
Node * T;
int CrtNode(stack
{
//Node * T;
int i = 0;
T = (Node *)malloc(sizeof(Node));
T->data = (char *)malloc(10*sizeof(char));
while (IsDigital(c[i]))
{
T->data[i] = c[i];
i++;
}
T->len = i;
T->setLeft(NULL);
T->setRight(NULL);
PTR.push(T);
return i;
}
void PostOrderTraverse(BiTree T, char * exp, int &count)
{
//后序遍历表达式树T,获取树中每个结点的数据值生成逆波兰表达式 exp
//T是表达式树的根节点;字符串exp保存逆波兰表达式;count保存exp 中字符的个数
//后序遍历中,处理根结点时,依据T->len的值,把T->data中的字符依次添加到当前exp字符串的尾端
//添加完T->data后,再添加一个空格字符,同时更新count计数器的值。
//填空
//int i;
if (T)
{
PostOrderTraverse(T->left(), exp, count);
PostOrderTraverse(T->right(), exp, count);
strncpy_s(exp + count, 100, T->data, T->len);
exp[count += (T->len)] = ' ';
count++;
}
}
void CrtSubTree(stack
{
Node * T;
T = (Node *)malloc(sizeof(Node));
T->data = (char *)malloc(10*sizeof(char));
T->data[0] = c;
T->len = 1;
T->setRight(PTR.top()); //先右子树,否则运算次序反了
PTR.pop();
T->setLeft(PTR.top());
PTR.pop();
PTR.push(T);
}
void insert(BiTree &T,char exp[])
{
//根据字符串exp的内容构建表达式树T
stack
stack
char op;
Node N;
int i = 0;
OPTR.push('#');
op = OPTR.top();
while (!((exp[i] == '#') && (OPTR.top() == '#'))) //与
{
if (IsDigital(exp[i]))
{//建立叶子节点并入栈 PTR
i += N.CrtNode(PTR, &exp[i]);
}
else if (exp[i] == ' ')
i++;
else{
switch (exp[i])
{
case '(': {
OPTR.push(exp[i]);
i++;
break; }
case ')': {
op = OPTR.top(); OPTR.pop();
while (op != '('){
N.CrtSubTree(PTR, op);
op = OPTR.top(); OPTR.pop();
}//end while
i++;
break; }
default: //exp[i]是 + - * /
while (!OPTR.empty())
{
op = OPTR.top();
if (Precede(op, exp[i]) == '>')
{
N.CrtSubTree(PTR, op);
OPTR.pop();
}
if (exp[i] != '#')
{
OPTR.push(exp[i]);
i++;
}
break;
}
}//end switch
}//end else
}//end while
T = PTR.top();
PTR.pop();
}
};
typedef struct
{
SElemtype *base;
SElemtype *top;
int stacksize;
} SqStack;
class Stack
{
private:
int size;//栈的长度
int top;//栈顶元素
char *listArray;// 顺序表保存栈元素
public:
Stack(int sz)
{
size = sz; top = 0; listArray = new char[sz];
} //构造函数
~Stack(){ delete[]listArray; } //析构函数
void clear(){ top = 0; }//栈的清空
bool push(const char&item)
{
if (top == size) return false;
else
{
listArray[top++] = item; return true;
}
} //栈的插入
bool pop(char& item)
{
if (top == 0) return false;
else
{
item = listArray[-top]; return true;
}
} //栈的删除
bool topValue(char & it) const
{
if (top == 0) return false;
else
{
it = listArray[top - 1]; return true;
}
} //获取栈顶元素
int length()const { return top; } //栈的长度};
typedef Node*BiTree;
Node * T;
class Tree
{
private:
Node *root;
public:
Tree()
{
root = NULL;
}
~Tree(){ delete[]root; }
/*void inorder(Tree T)
{
if (root != NULL)
{
inorder(root->left());
cout >> (char)root.data;
inorder(root->right());
}
}*/
void insert(BiTree &T,char exp[])
竭诚为您提供优质文档/双击可除数据结构表达式求值实验报告 篇一:数据结构实验二——算术表达式求值实验报告 《数据结构与数据库》 实验报告 实验题目算术表达式求值 学院:化学与材料科学学院 专业班级:09级材料科学与工程系pb0920603 姓学 邮名:李维谷号:pb09206285箱: liwg@https://www.docsj.com/doc/7316634788.html,指导教师:贾伯琪 实验时间:20XX年10月10日 一、需要分析 问题描述: 表达式计算是实现程序设计语言的基本问题之一,它的实现是栈的应用的一个典型例子。设计一个程序,演示通过将数学表达式字符串转化为后缀表达式,并通过后缀表达式结合栈的应用实现对算术表达式进行四则混合运算。
问题分析: 在计算机中,算术表达式由常量、变量、运算符和括号组成。由于不同的运算符具有不同的优先级,又要考虑括号,因此,算术表达式的求值不可能严格地从左到右进行。因而在程序设计时,借助栈实现。 设置运算符栈(字符型)和运算数栈(浮点型)辅助分析算符优先关系。在读入表达式的字符序列的同时完成运算符和运算数的识别处理,然后进行运算数的数值转换在进行四则运算。 在运算之后输出正确运算结果,输入表达式后演示在求值中运算数栈内的栈顶数据变化过程,最后得到运算结果。 算法规定: 输入形式:一个(:数据结构表达式求值实验报告)算术表达式,由常量、变量、运算符和括号组成(以字符串形式输入)。为使实验更完善,允许操作数为实数,操作符为(、)、.(表示小数点)、+、-、*、/、^(表示乘方),用#表示结束。 输出形式:演示表达式运算的中间结果和整个表达式的最终结果,以浮点型输出。 程序功能:对实数内的加减乘除乘方运算能正确的运算出结果,并能正确对错误输入和无定义的运算报错,能连续测试多组数据。 测试数据:正确输入:12*(3.6/3+4^2-1)#
《数据结构课程实验》大纲 一、《数据结构课程实验》的地位与作用 “数据结构”是计算机专业一门重要的专业技术基础课程,是计算机专业的一门核心的关键性课程。本课程较系统地介绍了软件设计中常用的数据结构以及相应的存储结构和实现算法,介绍了常用的多种查找和排序技术,并做了性能分析和比较,内容非常丰富。本课程的学习将为后续课程的学习以及软件设计水平的提高打下良好的基础。 由于以下原因,使得掌握这门课程具有较大的难度: (1)内容丰富,学习量大,给学习带来困难; (2)贯穿全书的动态链表存储结构和递归技术是学习中的重点也是难点; (3)所用到的技术多,而在此之前的各门课程中所介绍的专业性知识又不多,因而加大了学习难度; (4)隐含在各部分的技术和方法丰富,也是学习的重点和难点。 根据《数据结构课程》课程本身的技术特性,设置《数据结构课程实验》实践环节十分重要。通过实验实践内容的训练,突出构造性思维训练的特征, 目的是提高学生组织数据及编写大型程序的能力。实验学时为18。 二、《数据结构课程实验》的目的和要求 不少学生在解答习题尤其是算法设计题时,觉得无从下手,做起来特别费劲。实验中的内容和教科书的内容是密切相关的,解决题目要求所需的各种技术大多可从教科书中找到,只不过其出现的形式呈多样化,因此需要仔细体会,在反复实践的过程中才能掌握。 为了帮助学生更好地学习本课程,理解和掌握算法设计所需的技术,为整个专业学习打好基础,要求运用所学知识,上机解决一些典型问题,通过分析、设计、编码、调试等各环节的训练,使学生深刻理解、牢固掌握所用到的一些技术。数据结构中稍微复杂一些的算法设计中可能同时要用到多种技术和方法,如算法设计的构思方法,动态链表,算法的编码,递归技术,与特定问题相关的技术等,要求重点掌握线性链表、二叉树和树、图结构、数组结构相关算法的设计。在掌握基本算法的基础上,掌握分析、解决实际问题的能力。 三、《数据结构课程实验》内容 课程实验共18学时,要求完成以下六个题目: 实习一约瑟夫环问题(2学时)
《数据结构与算法设计》 实验报告 ——实验四 学院: 班级: 学号: 姓名:
一、实验目的 1. 通过实验实践、巩固线性表的相关操作; 2. 熟悉VC 环境,加强编程、调试的练习; 3. 用C 语言实现线性表的抽象数据类型,实现线性表构造、插入、取数据等基本操作; 4. 理论知识与实际问题相结合,利用上述基本操作实现三种排序并输出。 二、实验内容 从键盘输入10个数,编程实现分别用插入排序、交换排序、选择排序算法进行排序,输出排序后的序列。 三、程序设计 1、概要设计 为了实现排序的功能,需要将输入的数字放入线性表中,进行进一步的排序操作。 (1)抽象数据类型: ADT SqList{ 数据对象:D={|,1,2,,,0}i i a a ElemSet i n n ∈=≥ 数据关系:R1=11{,|,,1,2,,}i i i i a a a a D i n --<>∈= 基本操作: InPut(SqList &L) 操作结果:构造一个线性表L 。 OutPut(SqList L) 初始条件:线性表L 已存在。 操作结果:按顺序在屏幕上输出L 的数据元素。 InsertSort(SqList &L) 初始条件:线性表L 已存在。 操作结果:对L 的数据元素进行插入排序。 QuickSort(SqList &L) 初始条件:线性表L 已存在。 操作结果:对L 的数据元素进行快速排序。 SelectSort(SqList &L) 初始条件:线性表L 已存在。 操作结果:对L 的数据元素进行选择排序。 }ADT SqList ⑵主程序流程 由主程序首先调用InPut(L)函数创建顺序表,调用InsertSort(L)函数进行插入排序, 调用OutPut(L)函数显示排序结果。调用QuickSort(L)函数进行交换排序,调用OutPut(L) 函数显示排序结果。调用SelectSort(L)函数进行选择排序,调用OutPut(L)函数显示排序 结果。 ⑶模块调用关系 由主函数模块调用创建顺序表模块,排序模块与显示输出模块。
《数据结构》实验报告 班级: 学号: 姓名:
实验四二叉树的基本操作实验环境:Visual C++ 实验目的: 1、掌握二叉树的二叉链式存储结构; 2、掌握二叉树的建立,遍历等操作。 实验内容: 通过完全前序序列创建一棵二叉树,完成如下功能: 1)输出二叉树的前序遍历序列; 2)输出二叉树的中序遍历序列; 3)输出二叉树的后序遍历序列; 4)统计二叉树的结点总数; 5)统计二叉树中叶子结点的个数; 实验提示: //二叉树的二叉链式存储表示 typedef char TElemType; typedef struct BiTNode{ TElemType data; struct BiTNode *lchild,*rchild; }BiTNode,*BiTree;
一、程序源代码 #include
} 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;
《数据结构与数据库》 实验报告 实验题目 算术表达式求值 学院:化学与材料科学学院 专业班级:09级材料科学与工程系PB0920603 姓名:李维谷 学号:PB09206285 邮箱:liwg@https://www.docsj.com/doc/7316634788.html, 指导教师:贾伯琪 实验时间:2010年10月10日 一、需要分析 问题描述:
表达式计算是实现程序设计语言的基本问题之一,它的实现是栈的应用的一个典型例子。设计一个程序,演示通过将数学表达式字符串转化为后缀表达式,并通过后缀表达式结合栈的应用实现对算术表达式进行四则混合运算。 问题分析: 在计算机中,算术表达式由常量、变量、运算符和括号组成。由于不同的运算符具有不同的优先级,又要考虑括号,因此,算术表达式的求值不可能严格地从左到右进行。因而在程序设计时,借助栈实现。 设置运算符栈(字符型)和运算数栈(浮点型)辅助分析算符优先关系。在读入表达式的字符序列的同时完成运算符和运算数的识别处理,然后进行运算数的数值转换在进行四则运算。 在运算之后输出正确运算结果,输入表达式后演示在求值中运算数栈内的栈顶数据变化过程,最后得到运算结果。 算法规定: 输入形式:一个算术表达式,由常量、变量、运算符和括号组成(以字符串形式输入)。为使实验更完善,允许操作数为实数,操作符为(、)、.(表示小数点)、+、-、*、/、^(表示乘方),用#表示结束。 输出形式:演示表达式运算的中间结果和整个表达式的最终结果,以浮点型输出。 程序功能:对实数内的加减乘除乘方运算能正确的运算出结果,并能正确对错误输入和无定义的运算报错,能连续测试多组数据。 测试数据:正确输入:12*(3.6/3+4^2-1)# 输出结果:194.4
数据结构实验报告 一.题目要求 1)编程实现二叉排序树,包括生成、插入,删除; 2)对二叉排序树进行先根、中根、和后根非递归遍历; 3)每次对树的修改操作和遍历操作的显示结果都需要在屏幕上用树的形状表示出来。 4)分别用二叉排序树和数组去存储一个班(50人以上)的成员信息(至少包括学号、姓名、成绩3项),对比查找效率,并说明在什么情况下二叉排序树效率高,为什么? 二.解决方案 对于前三个题目要求,我们用一个程序实现代码如下 #include 软件技术基础实验报告 实验名称:表达式计算器 系别:通信工程 年级: 班级: 学生学号: 学生姓名: 《数据结构》课程设计报告 题目简易计算表达式的演示 【题目要求】 要求:实现基本表达式计算的功能 输入:数学表达式,表达式由整数和“+”、“-”、“×”、“/”、“(”、“)”组成输出:表达式的值 基本操作:键入表达式,开始计算,计算过程和结果记录在文档中 难点:括号的处理、乘除的优先级高于加减 1.前言 在计算机中,算术表达式由常量、变量、运算符和括号组成。由于不同的运算符具有不同的优先级,又要考虑括号,因此,算术表达式的求值不可能严格地从左到右进行。因而在程序设计时,借助栈实现。 算法输入:一个算术表达式,由常量、变量、运算符和括号组成(以字符串形式输入)。为简化,规定操作数只能为正整数,操作符为+、-*、/、=,用#表示结束。 算法输出:表达式运算结果。 算法要点:设置运算符栈和运算数栈辅助分析算符优先关系。在读入表达式的字符序列的同时,完成运算符和运算数的识别处理,以及相应运算。 2.概要设计 2.1 数据结构设计 任何一个表达式都是由操作符,运算符和界限符组成的。我们分别用顺序栈来寄存表达式的操作数和运算符。栈是限定于紧仅在表尾进行插入或删除操作的线性表。顺序栈的存储结构是利用一组连续的存储单元依次存放自栈底到栈顶的数据元素,同时附设指针top 指示栈顶元素在顺序栈中的位置,base 为栈底指针,在顺序栈中,它始终指向栈底,即top=base 可作为栈空的标记,每当插入新的栈顶元素时,指针top 增1,删除栈顶元素时,指针top 减1。 2.2 算法设计 为了实现算符优先算法。可以使用两个工作栈。一个称为OPTR ,用以寄存运算符,另一个称做OPND ,用以寄存操作数或运算结果。 1.首先置操作数栈为空栈,表达式起始符”#”为运算符栈的栈底元素; 2.依次读入表达式,若是操作符即进OPND 栈,若是运算符则和OPTR 栈的栈顶运算符比较优先权后作相应的操作,直至整个表达式求值完毕(即OPTR 栈的栈顶元素和当前读入的字符均为”#”)。 2.3 ADT 描述 ADT Stack{ 数据对象:D={ i a |i a ∈ElemSet,i=1,2,…,n, n ≧0} 数据对象:R1={< 1 ,-i i a a >| 1-i a ,D a i ∈,i=2,…,n} 数据结构实验报告全集 实验一线性表基本操作和简单程序 1.实验目的 (1)掌握使用Visual C++ 6.0上机调试程序的基本方法; (2)掌握线性表的基本操作:初始化、插入、删除、取数据元素等运算在顺序存储结构和链表存储结构上的程序设计方法。 2.实验要求 (1)认真阅读和掌握和本实验相关的教材内容。 (2)认真阅读和掌握本章相关内容的程序。 (3)上机运行程序。 (4)保存和打印出程序的运行结果,并结合程序进行分析。 (5)按照你对线性表的操作需要,重新改写主程序并运行,打印出文件清单和运行结果 实验代码: 1)头文件模块 #include iostream.h>//头文件 #include nodetype *create()//建立单链表,由用户输入各结点data域之值,//以0表示输入结束 { elemtype d;//定义数据元素d nodetype *h=NULL,*s,*t;//定义结点指针 int i=1; cout<<"建立一个单链表"< HUNAN UNIVERSITY 课程实习报告 题目:四则运算表达式求值 学生姓名: 学生学号: 专业班级: 指导老师: 完成日期: 一、需求分析 四则运算表达式求值,将四则运算表达式用中缀表达式表示,然后转换为后缀表达式,并计算结果。 本程序要求利用二叉树后序遍历来实现表达式的转换,同时可以使用实验2的结果来求解后缀表达式的值。 在字符界面上输入一个中缀表达式,回车表示结束。如果该中缀表达式正确,那么在字符界面上输出其后缀表达式,其中后缀表达式中两相邻操作数之间利用空格隔开;如果不正确,在字符界面上输出表达式错误提示。 测试数据 输入: 21+23*(12-6) 输出: 21 23 12 6 -*+ 二、详细设计 输入和输出的格式 输入 本程序可以将输入的四则运算表达式(中缀表达式)转换为后缀表达式 输出 后缀表达式为://输出结果的位置 表达式的值为://输出结果的位置 三、调试分析 本次实验的难点主要是在建立二叉树的问题上。关于如何把中缀表达式存入二叉树中,我参考了网上的一些方法,成功实现了目标,但是却遇到了一个问题,那就是不能处理小数,甚至两位或两位以上的整数。因为如果采用字符数组来存储操作数,运算符合一位整数还可以处理,但对于两位数就就会出问题,最后我改进采用字符串数组来存储操作数,成功解决了问题。 另外在处理输入的非法表达式问题中,我也费了很大功夫,但总体问题不大。 四、测试结果 五、用户使用说明(可选) 1、运行程序时 提示输入四则运算表达式 本程序可以将中缀表达式转化为后缀表达式,并计算结果 请输入四则运算表达式: 输出 后缀表达式为: 表达式的值为: 程序源代码(c++) #include 2009级数据结构实验报告 实验名称:约瑟夫问题 学生姓名:李凯 班级:21班 班内序号:06 学号:09210609 日期:2010年11月5日 1.实验要求 1)功能描述:有n个人围城一个圆圈,给任意一个正整数m,从第一个人开始依次报数,数到m时则第m个人出列,重复进行,直到所有人均出列为止。请输出n个人的出列顺序。 2)输入描述:从源文件中读取。 输出描述:依次从显示屏上输出出列顺序。 2. 程序分析 1)存储结构的选择 单循环链表 2)链表的ADT定义 ADT List{ 数据对象:D={a i|a i∈ElemSet,i=1,2,3,…n,n≧0} 数据关系:R={< a i-1, a i>| a i-1 ,a i∈D,i=1,2,3,4….,n} 基本操作: ListInit(&L);//构造一个空的单链表表L ListEmpty(L); //判断单链表L是否是空表,若是,则返回1,否则返回0. ListLength(L); //求单链表L的长度 GetElem(L,i);//返回链表L中第i个数据元素的值; ListSort(LinkList [内容要求] 1、存储结构:顺序表、单链表或其他存储结构,需要画示意图,可参考书上P59 页图2-9 2.2 关键算法分析 结点类: template 实验一约瑟夫问题 实验学时:3学时 实验类型:设计 实验要求:必修 一、实验目的 熟练掌握线性链表的基础知识; 能够使用C++或其他程序设计语言编程实现线性链表; 能够使用线性链表构造正确而且时间复杂度低的算法解决实际问题; 锻炼程序设计能力。 二、实验内容 M个教徒和N个非教徒在深海上遇险,必须将N个人投入海中,其余的人才能幸免于难,于是想了一个办法:所有人围成一圆圈,从第一个人开始依次报数,每数到第K个人就将他扔入大海,如此循环进行直到仅余M个人为止。设计一个算法,找出这样一个排序:使每次被扔进大海的都是非教徒。并用程序设计语言实现。 三、实验原理、方法和手段 使用循环单链表,将每个人作为一个结点,每个结点的指针域指向下一个人,采用循环链表的遍历对每隔N-1个结点的结点进行标记,直至标记出N个结点为止。该实验亦可用顺序表实现。 四、实验组织运行要求 本实验采用集中授课形式,每个同学独立完成上述实验要求。 五、实验条件 每人一台计算机独立完成实验,有如下条件: (1)硬件:联想高性能PC机; (2)软件:VC++ 6.0、VC++.Net。 六、实验步骤 (1)编写循环链表构造函数Node *Create( ),使链表中每个结点的数据域值为0,并让最后一个结点的指针域指向第一个结点; (2)编写约瑟夫问题函数 Node *Move(Node *H,int n); void Insert(Node *H,int pos,int data); (5)主函数中调用Create,Move和Insert,采用具体数据计算,输出结果。 七、实验程序 // stdafx.h : 标准系统包含文件的包含文件, // 或是经常使用但不常更改的 // 特定于项目的包含文件 // #pragma once #include"targetver.h" #include 实验课程名称 专业班级 学生姓名 学号 指导教师 20 至 20 学年第学期第至周 算术表达式求值演示 一、概述 数据结构课程设计,要求学生在数据结构的逻辑特性和物理表示、数据结构的选择和应用、算法的设计及其实现等方面,加深对课程基本容的理解。同时,在程序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。 在这次的课程设计中我选择的题目是算术表达式求值演示。表达式计算是实现程序设计语言的基本问题之一,也是栈的应用的一个典型例子。设计一个程序,演示用算符优先法对算术表达式求值的过程。深入了解栈和队列的特性,以便在解决实际问题中灵活运用它们,同时加深对这种结构的理解和认识。 二、系统分析 1.以字符列的形式从终端输入语确的、不含变量的整数表达式。利用已知的算符优先关系,实现对算术四则混合运算表达式的求值,并仿照教科书的例子在求值中运算符栈、运算数栈、输入字符和主要操作的变化过程。 2.一般来说,计算机解决一个具体问题时,需要经过几个步骤:首先要从具体问题抽象出一个适当的数学模型,然后设计一个解决此数学模型的算法,最后编出程序,进行测试,调试直至得到想要的答案。对于算术表达式这个程序,主要利用栈,把运算的先后步骤进行分析并实现简单的运算!为实现算符优先算法,可以使用两个栈,一个用以寄存运算符,另一个用以寄存操作数和运算结果。 3.演示程序是以用户于计算机的对话方式执行,这需要一个模块来完成使用者与计算机语言的转化。 4.程序执行时的命令: 本程序为了使用具体,采用菜单式的方式来完成程序的演示,几乎不用输入什么特殊 的命令,只需按提示输入表达式即可。(要注意输入时格式,否者可能会引起一些错误)5. 测试数据。 三、概要设计 一个算术表达式中除了括号、界限符外,还包括运算数据和运算符。由于运算符有优先级别之差,所以一个表达式的运算不可能总是从左至右的循序执行。每次操作的数据或运算符都是最近输入的,这与栈的特性相吻合,故本课程设计借助栈来实现按运算符的优先级完成表达式的求值计算。 算法设计 程序包含三个模块 (1) 主程序模块,其中主函数为 void main{ 输入表达式; 根据要求进行转换并求值; 输出结果; } (2) 表达式求值模块——实现具体求值。 (3) 表达式转换模块——实现转换。 各个函数之间的调用关系 《数据结构与算法统计》 实验报告 ——实验四 学院: 班级: 学号: 姓名: 一、实验目的 1、熟悉VC 环境,学会使用C 语言利用顺序表解决实际问题。 2、通过上机、编程调试,加强对线性表的理解和运用的能力。 3、锻炼动手编程,独立思考的能力。 二、实验内容 从键盘输入10个数,编程实现分别用插入排序、交换排序、选择排序算法进行排序,输出排序后的序列。 三、程序设计 1、概要设计 为了实现排序的功能,需要将输入的数字放入线性表中,进行进一步的排序操作。 (1)抽象数据类型: ADT SqList{ 数据对象:D={|,1,2,,,0}i i a a Elem Set i n n ∈=≥ 数据关系:R1=11{,|,,1,2,,}i i i i a a a a D i n --<>∈= 基本操作: InPut(SqList &L) 操作结果:构造一个线性表L 。 OutPut(SqList L) 初始条件:线性表L 已存在。 操作结果:按顺序在屏幕上输出L 的数据元素。 InsertSort(SqList &L) 初始条件:线性表L 已存在。 操作结果:对L 的数据元素进行插入排序。 QuickSort(SqList &L) 初始条件:线性表L 已存在。 操作结果:对L 的数据元素进行快速排序。 SelectSort(SqList &L) 初始条件:线性表L 已存在。 操作结果:对L 的数据元素进行选择排序。 }ADT SqList ⑵主程序流程 由主程序首先调用InPut(L)函数创建顺序表,调用InsertSort(L)函数进行插入排序,调用OutPut(L)函数显示排序结果。 再由主程序首先调用InPut(L)函数创建顺序表,调用QuickSort(L)函数进行交换排序,调用OutPut(L)函数显示排序结果。 再由主程序首先调用InPut(L)函数创建顺序表,调用SelectSort(L)函数进行选择排序,调用OutPut(L)函数显示排序结果。 ⑶模块调用关系 本科实验报告 课程名称:数据结构(C语言版) 实验项目:线性表、树、图、查找、内排序实验地点:明向校区实验楼208 专业班级:学号: 学生姓名: 指导教师:杨永强 2019 年 1 月10日 #include 淮海工学院计算机工程学院 课程设计报告 设计名称:数据结构课程设计 选题名称:表达式求值 姓名:学号: 专业班级: 系(院):计算机工程学院 设计时间: 设计地点:软件工程实验室、教室 指导教师评语: 成绩: 签名: 年月日 1.课程设计目的 1、训练学生灵活使用所学数据结构知识,独立完成问题分析,结合数据结构理论知识,编写程序求解指定问题。 2.初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能; 3.提高综合运用所学的理论知识和方法独立分析和解决问题的能力; 4.训练用系统的观点和软件开发一般规范进行软件开发,巩固、深化学生的理论知识,提高编程水平,并在此过程中培养他们严谨的科学态度和良好的工作作风。 2.课程设计任务和要求: 任务 根据教材《数据结构-C语言描述》(耿国华主编)和参考书《数据结构题集(C语言版)》(严蔚敏、吴伟民主编)选择课程设计题目,要求通过设计,在数据结构的逻辑特性和物理表示、数据结构的选择使用、算法的设计及其实现等方面加深对课程基本内容的理解和综合运用。 设计题目从任务书所列选题表中选取,每班每题不得超过2人。 学生自选课题 学生原则上可以结合个人爱好自选课题,要求课题有一定的深度和难度,有一定的算法复杂性,能够巩固数据结构课程所学的知识。学生自选课题需在18周前报课程设计指导教师批准方可生效。 要求: 1、在处理每个题目时,要求从分析题目的需求入手,按设计抽象数据类型、构思算法、通过设计实现抽象数据类型、编制上机程序和上机调试等若干步骤完成题目,最终写出完整的分析报告。前期准备工作完备和否直接影响到后序上机调试工作的效率。在程序设计阶段应尽量利用已有的标准函数,加大代码的重用率。 2、.设计的题目要求达到一定工作量(300行以上代码),并具有一定的深度和难度。 3、程序设计语言推荐使用C/C++,程序书写规范,源程序需加必要的注释; 4、每位同学需提交可独立运行的程序; 5 、每位同学需独立提交设计报告书(每人一份),要求编排格式统一、规范、内容充实,不少于10页(代码不算); 6、课程设计实践作为培养学生动手能力的一种手段,单独考核。 3.课程设计说明书 福建广播电视大学实验报告(学科:数据结构)姓名单位班级学号实验日期成绩评定教师签名批改日期 实验名称:实验四图的存储方式和应用 4.1建立图的邻接矩阵 【问题描述】 根据图中顶点和边的信息编制程序建立图的邻接矩阵。 【基本要求】 (1)程序要有一定的通用性。 (2)直接根据图中每个结点与其他结点的关联情况输入相关信息,程序能自动形成邻接矩阵 【测试用例】 【实现提示】 (1)对图的顶点编号。 (2)在上图中,以顶点1为例,因为顶点2,3,4与顶点1关联,可以输入信息1 2 3 4,然后设法求出与顶点1关联的结点,从而求得邻接矩阵中相应与顶点1的矩阵元素。 实验图4-1 设计程序代码如下: #include #define MaxEdgeNum 20 #define MaxValue 1000 typedef int VertexType; typedef VertexType vexlist [MaxVertexNum]; typedef int adjmatrix [MaxVertexNum] [MaxVertexNum]; void Createl(vexlist Gv,adjmatrix GA,int n,int e) { int i,j,k,w; printf("输入%d个顶点数据\n",n); for(i=0;i 一、算法基本思想: (1) 顺序查找:建立顺序表,从表内第一个数值开始与给定值比较,若相等,则查找成功;否则,用下一个数值继续进行比较,直到数值等于给定值或者线性表已比较完(查找不成功)为止。 (2) 首先提示用户建立有序数组的长度,然后输入有序的数据,接着提示用户输入要查找的元素,通过调用binarySearch()来判断用户要查找的元素是否在此数组中,如果返回值是-1则说明用户查找的数据不在此数组中,否则输出在此数组中。但是,折半查找的先决条件是查找表中的数据元素必须有序。查找过程中采用跃式方查找,即先以有序数列的中点位置为比较对象,如果要找的元素值小于该中点元素,则待查序列缩小为左半部分,否则为右半部分。通过一次比较,将查找区间缩小一半。折半查找是一种高效的查找方法。它可以明显减少比较次数,提高查找效率。 二、结构定义: 线性表的结构定义:有序表的结构定义: typedef struct typedef struct { { Elemtype *elem; KeyType Key; int length; } int listsize; }Elemtype; }SqList; 三、算法描述: int Search_Bin2(SqList &L,KeyType key) {//在有序表ST中折半查找其关键字等于//key的数据元素。若找到,则函数值为该元//素在表中的位置,否则为0 int low,high,mid; low=1; high=L.length;//置区间初值 while(low<=high){ mid=(low+high)/2; if(EQ(key,L.elem[mid].key)) //找到待查元素 {printf("待查元素的位置:%d\n",mid+1); return OK; } 清华大学数据结构课程实验报告(20 -20 学年第学期) 报告题目:算术表达式求值 任课老师: 专业: 学号: 姓名: 二0一年月日 摘要:现代科学技术高速发展,各种高科技产品频频问世,而各种技术的基础都离不开基本的表达式求值,它虽然简单,但却是任何复杂系统的基本执行操作。栈是一种重要的线性结构,从数据结构的角度看,它是一种特殊的线性表,具有先入先出的特点。而算符优先法的设计恰巧符合先入先出的思想。故我们基于栈这种数据结构,利用算符优先法,来实现简单算术表达式的求值。 关键字:算符优先法;算术表达式;数据结构;栈 一、课题概述 1、问题描述 一个算术表达式是由运算数、运算符、界限符组成。假设操作数是正整数,运算符只含有加“+”、减“-”、乘“*”、除“/”四种二元运算符,界限符有左括号“(”、右括号“)”和表达式起始、结束符“#”。利用算符优先法对算术表达式求值。 2、设计目的 (1)通过该算法的设计思想,熟悉栈的特点和应用方法; (2)通过对算符优先法对算术表达式求值的算法执行过程的演示,理解在执行相应栈的操作时的变化过程。 (3)通过程序设计,进一步熟悉栈的基本运算函数; (4)通过自己动手实现算法,加强从伪码算法到C语言程序的实现能力。3、基本要求: (1)使用栈的顺序存储表示方式; (2)使用算符优先法; (3)用C语言实现; (4)从键盘输入一个符合要求的算术表达式,输出正确的结果。 4、编程实现平台 Microsoft Visual C++ 6.0 二、设计思路及采取方案 1、设计思路: 为了实现算符优先法,可以使用两个工作栈。一个称做OPTR,用以寄存运 2011~2012第一学期数据结构实验报告 班级:信管一班 学号:201051018 姓名:史孟晨 实验报告题目及要求 一、实验题目 设某班级有M(6)名学生,本学期共开设N(3)门课程,要求实现并修改如下程序(算法)。 1. 输入学生的学号、姓名和 N 门课程的成绩(输入提示和输出显示使用汉字系统), 输出实验结果。(15分) 2. 计算每个学生本学期 N 门课程的总分,输出总分和N门课程成绩排在前 3 名学 生的学号、姓名和成绩。 3. 按学生总分和 N 门课程成绩关键字升序排列名次,总分相同者同名次。 二、实验要求 1.修改算法。将奇偶排序算法升序改为降序。(15分) 2.用选择排序、冒泡排序、插入排序分别替换奇偶排序算法,并将升序算法修改为降序算法;。(45分)) 3.编译、链接以上算法,按要求写出实验报告(25)。 4. 修改后算法的所有语句必须加下划线,没做修改语句保持按原样不动。 5.用A4纸打印输出实验报告。 三、实验报告说明 实验数据可自定义,每种排序算法数据要求均不重复。 (1) 实验题目:《N门课程学生成绩名次排序算法实现》; (2) 实验目的:掌握各种排序算法的基本思想、实验方法和验证算法的准确性; (3) 实验要求:对算法进行上机编译、链接、运行; (4) 实验环境(Windows XP-sp3,Visual c++); (5) 实验算法(给出四种排序算法修改后的全部清单); (6) 实验结果(四种排序算法模拟运行后的实验结果); (7) 实验体会(文字说明本实验成功或不足之处)。 三、实验源程序(算法) Score.c #include "stdio.h" #include "string.h" #define M 6 #define N 3 struct student { char name[10]; int number; int score[N+1]; /*score[N]为总分,score[0]-score[2]为学科成绩*/ }stu[M]; void changesort(struct student a[],int n,int j) {int flag=1,i; struct student temp; while(flag) { flag=0; for(i=1;i 浙江科技学院《数据结构》实验报告 年级班级 学号 姓名 任课老师 实验指导教师 实验地点 信息学院 实验一线性表操作(一元多项式的运算) 实验目的: 1、定义线性表的链式存储 2、实现对线性表的一些基本操作和具体函数定义 实验要求: 1、定义线性表的链式存储; 2、实现对线性表的一些基本操作和具体函数定义。 3、定义输出一元多项式的函数; 4、编写主程序调用上面的函数实现一元多项式的加减。 数据输入输出要求: 输入示例: 3 2 3 3 4 5 7 5 2 1 3 3 -3 4 4 6 5 7 (说明:第一个数据3表示该第一个一元多项式的项数为3,后面的2 3 表示第一项的系数为2 指数为3;按指数递增的次序输入) 输出示例: 一元多项式1: 2x(3)+3x(4)+5x(7) 一元多项式2: 2x(1)+3x(3)-3x(4)+4x(6)+5x(7) 加的结果:2x(1)+5x(3) +4x(6)+10x(7) 减的结果:-2x(1)-1x(3)+6x(4)-4x(6) 程序代码: #include #include数据结构算术表达式求值实验报告
数据结构实验报告全集
四则运算表达式求值实验报告
数据结构实验报告模板
数据结构实验报告
《数据结构课程设计》表达式求值实验报告
北京理工大学数据结构实验报告4
数据结构实验报告
表达式求值实验报告
数据结构实验报告4(中央电大)
数据结构实验报告四林昌雄
算术表达式求值-数据结构实验报告
数据结构实验报告及心得体会
数据结构实验报告