实验5

实验5：二叉树的建立及遍历（第十三周星期三7、8节）一、实验目的1．学会实现二叉树结点结构和对二叉树的基本操作。

2．掌握对二叉树每种操作的具体实现，学会利用递归方法编写对二叉树这种递归数据结构进行处理的算法。

二、实验要求1．认真阅读和掌握和本实验相关的教材内容。

2．编写完整程序完成下面的实验内容并上机运行。

3．整理并上交实验报告。

三、实验内容1．编写程序任意输入二叉树的结点个数和结点值，构造一棵二叉树，采用三种递归遍历算法(前序、中序、后序)对这棵二叉树进行遍历并计算出二叉树的高度。

2 .编写程序生成下面所示的二叉树，并采用中序遍历的非递归算法对此二叉树进行遍历。

四、思考与提高1．如何计算二叉链表存储的二叉树中度数为1的结点数？2．已知有—棵以二叉链表存储的二叉树，root指向根结点，p指向二叉树中任一结点，如何求从根结点到p所指结点之间的路径?/*----------------------------------------* 05-1_递归遍历二叉树.cpp -- 递归遍历二叉树的相关操作* 对递归遍历二叉树的每个基本操作都用单独的函数来实现* 水上飘2009年写----------------------------------------*/// ds05.cpp : Defines the entry point for the console application.//#include "stdafx.h"#include <iostream>typedef char ElemType;using namespace std;typedef struct BiTNode {ElemType data;//左右孩子指针BiTNode *lchild, *rchild;}BiTNode, *BiTree;//动态输入字符按先序创建二叉树void CreateBiTree(BiTree &T) {char ch;ch = cin.get();if(ch == ' ') {T = NULL;}else {if(ch == '\n') {cout << "输入未结束前不要输入回车，""要结束分支请输入空格！" << endl;}else {//生成根结点T = (BiTNode * )malloc(sizeof(BiTNode));if(!T)cout << "内存分配失败！" << endl;T->data = ch;//构造左子树CreateBiTree(T->lchild);//构造右子树CreateBiTree(T->rchild);}}}//输出e的值ElemType PrintElement(ElemType e) { cout << e << " ";return e;}//先序遍历void PreOrderTraverse(BiTree T) { if (T != NULL) {//打印结点的值PrintElement(T->data);//遍历左孩子PreOrderTraverse(T->lchild);//遍历右孩子PreOrderTraverse(T->rchild);}}//中序遍历void InOrderTraverse(BiTree T) {if (T != NULL) {//遍历左孩子InOrderTraverse(T->lchild);//打印结点的值PrintElement(T->data);//遍历右孩子InOrderTraverse(T->rchild);}}//后序遍历void PostOrderTraverse(BiTree T) { if (T != NULL) {//遍历左孩子PostOrderTraverse(T->lchild);//遍历右孩子PostOrderTraverse(T->rchild);//打印结点的值PrintElement(T->data);}}//按任一种遍历次序输出二叉树中的所有结点void TraverseBiTree(BiTree T, int mark) {if(mark == 1) {//先序遍历PreOrderTraverse(T);cout << endl;}else if(mark == 2) {//中序遍历InOrderTraverse(T);cout << endl;}else if(mark == 3) {//后序遍历PostOrderTraverse(T);cout << endl;}else cout << "选择遍历结束！" << endl;}//输入值并执行选择遍历函数void ChoiceMark(BiTree T) {int mark = 1;cout << "请输入，先序遍历为1，中序为2，后序为3，跳过此操作为0：";cin >> mark;if(mark > 0 && mark < 4) {TraverseBiTree(T, mark);ChoiceMark(T);}else cout << "此操作已跳过！" << endl;}//求二叉树的深度int BiTreeDepth(BiTNode *T) {if (T == NULL) {//对于空树，返回0并结束递归return 0;}else {//计算左子树的深度int dep1 = BiTreeDepth(T->lchild);//计算右子树的深度int dep2 = BiTreeDepth(T->rchild);//返回树的深度if(dep1 > dep2)return dep1 + 1;elsereturn dep2 + 1;}}int _tmain(int argc, _TCHAR* argv[]){BiTNode *bt;bt = NULL; //将树根指针置空cout << "输入规则：" << endl<< "要生成新结点，输入一个字符，""不要生成新结点的左孩子，输入一个空格，""左右孩子都不要，输入两个空格，""要结束，输入多个空格（越多越好）,再回车！"<< endl << "按先序输入：";CreateBiTree(bt);cout << "树的深度为：" << BiTreeDepth(bt) << endl;ChoiceMark(bt);return 0;}/*----------------------------------------* 05-2_构造二叉树.cpp -- 构造二叉树的相关操作* 对构造二叉树的每个基本操作都用单独的函数来实现* 水上飘2009年写----------------------------------------*/// ds05-2.cpp : Defines the entry point for the console application.//#include "stdafx.h"#include <iostream>#define STACK_INIT_SIZE 100 //栈的存储空间初始分配量#define STACKINCREMENT 10 //存储空间分配增量typedef char ElemType; //元素类型using namespace std;typedef struct BiTNode {ElemType data; //结点值BiTNode *lchild, *rchild; //左右孩子指针}BiTNode, *BiTree;typedef struct {BiTree *base; //在栈构造之前和销毁之后，base的值为空BiTree *top; //栈顶指针int stacksize; //当前已分配的存储空间，以元素为单位}SqStack;//构造一个空栈void InitStack(SqStack &s) {s.base = (BiTree *)malloc(STACK_INIT_SIZE * sizeof(BiTree));if(!s.base)cout << "存储分配失败！" << endl;s.top = s.base;s.stacksize = STACK_INIT_SIZE;}//插入元素e为新的栈顶元素void Push(SqStack &s, BiTree e) {//栈满，追加存储空间if ((s.top - s.base) >= s.stacksize) {s.base = (BiTree *)malloc((STACK_INIT_SIZE+STACKINCREMENT) * sizeof(BiTree));if(!s.base)cout << "存储分配失败！" << endl;s.top = s.base + s.stacksize;s.stacksize += STACK_INIT_SIZE;}*s.top++ = e;}//若栈不空，则删除s的栈顶元素，并返回其值BiTree Pop(SqStack &s) {if(s.top == s.base)cout << "栈为空，无法删除栈顶元素！" << endl;s.top--;return *s.top;}//按先序输入字符创建二叉树void CreateBiTree(BiTree &T) {char ch;//接受输入的字符ch = cin.get();if(ch == ' ') {//分支结束T = NULL;} //if' 'endelse if(ch == '\n') {cout << "输入未结束前不要输入回车，""要结束分支请输入空格！（接着输入）" << endl;} //if'\n'endelse {//生成根结点T = (BiTNode * )malloc(sizeof(BiTree));if(!T)cout << "内存分配失败！" << endl;T->data = ch;//构造左子树CreateBiTree(T->lchild);//构造右子树CreateBiTree(T->rchild);} //Create end}//输出e的值，并返回ElemType PrintElement(ElemType e) {cout << e << " ";return e;}//中序遍历二叉树的非递归函数void InOrderTraverse(BiTree p, SqStack &S) {cout << "中序遍历结果：";while(S.top != S.base || p != NULL) {if(p != NULL) {Push(S,p);p = p->lchild;} //if NULL endelse {BiTree bi = Pop(S);if(!PrintElement(bi->data))cout << "输出其值未成功！" << endl;p = bi->rchild;} //else end} //while endcout << endl;}int _tmain(int argc, _TCHAR* argv[]){BiTNode *bt;SqStack S;InitStack(S);bt = NULL; //将树根指针置空cout << "老师要求的二叉树序列（‘空’表示空格）：""12空空346空空空5空空，再回车！"<< endl << "请按先序输入一个二叉树序列（可另输入，但要为先序），""无左右孩子则分别输入空格。

实验(5):探究作用力与反作用力的关系
一、实验原理图
二、基本实验要求 1.实验目的 (1)通过实验探究作用力与反作用力之间的关系。 (2)体验用力传感器研究作用力与反作用力关系的方法。
2.实验原理 (1)用弹簧测力计探究作用力与反作用力的关系。
甲 如图甲所示,任取A、B两把弹簧测力计,使两挂钩钩住,B固定,A用手拉着, 弹簧测力计A受到B的拉力为FBA,弹簧测力计B受到A的拉力为FAB,读出此时 两弹簧测力计的示数FA和FB,比较FA和FB的大小和方向。 乙 如图乙所示,将两个弹簧测力计挂钩钩住,B连接一块木块,A用手拉着,探 究在水平方向运动时,FA和FB的大小和方向。
(2)用力传感器探究作用力与反作用力的关系。
如图,用两只力传感器钩住对拉,从计算机屏幕上所显示的力和时间关系 图线中读出不同时刻两只力传感器间的相互作用力FA和FB,比较FA和FB的大 小和方向。 3.实验器材 弹簧测力计3个、包装用泡沫塑料若干、小刀1把、木块1块、力传感器2 只、数据采集器1台及计算机1台等。
考点1
考点2
(2)在弹簧测力计的指针下面放上一点泡沫塑料的作用是 。 A.为了增大指针受到的阻力 B.可以帮助我们记录下指针示数的最大值 关闭 C.防止指针与弹簧测力计外壳间的摩擦 (1)D. 弹簧测力计 A对B的拉力与B对A的拉力大小关系与运动状态无关,作用力与反 防止测的力超过弹簧测力计的测量范围
4.实验步骤 (1)用弹簧测力计探究作用力与反作用力的关系。 ①探究静止状态时物体间的作用力与反作用力。 ②增加弹簧测力计的“记忆功能”,即在弹簧测力计的指针下面放上一点泡 沫塑料,探究沿水平方向运动时物体 间作用力与反作用力。 (2)用力传感器探究作用力与反作用力的关系 ①探究静止状态时物体间的作用力与反作用力。 ②探究沿水平方向运动时物体间的作用力与反作用力。 ③探究沿竖直方向运动时物体间的作用力与反作用力。

实验五课程名称：大学计算机实验项目名称：Excel的应用2. 对一列数据进行通过excel求和函数进行求和，对另一列数据求最大值。

1）输入两列数据，单击需要算出和的单元格，进入功能区的“公式”，点击“插入函数”，在弹出的对话框中选择“Sum”函数，点击确定后在随后的对话框中选择求和的数的范围，再次点击确认即可。

2）单击需要算出和的单元格，进入功能区的“公式”，点击“插入函数”，在弹出的对话框中选择“Max”函数，点击确定后在随后的对话框中选择求最大值的数的范围，再次点击确认即可。

3. 验证数据有效性，验证是否有来自“北京”“上海”之外的地区（P127）1）选中“地区”那列所有数据，在功能区找到“数据”，在“数据工具”找到“数据验证”，点进去，在弹出的对话框中，在“设置”选项卡里找到“允许”的下拉列表，选择“序列”，在“来源”输入“北京,上海”，其中逗号用半角模式下的英语模式的逗号。

点击确定即可。

如果再次输入“北京,上海”之外的数据就会提示错误，且可以制作下拉菜单。

4. 自动筛选出销售数量大于100000的行（P128~P129）1）点击清单中任意一个单元格，在功能区找到“数据”，在其中找到“筛选”，单击后，找到“销售与数量”旁边的下拉按钮，点进去出来一个菜单，点击“全选”，再在“数字筛选”的下一级菜单中选择“大于”，在点击后弹出的对话框中输入“100000”，点击确定即可，设置完成后可以发现，全部的销售数量都低于100000，故全部都消失。

5.实现案例5-161）输入基础数值如下2）单击E2单元格开始编辑，输入公式“=PMT(B2/12,C2*12,D2)”，按下回车键即可自动计算月供金额。

再选中该单元格，单击右键，在弹出的菜单中找到“设置单元格式”，单击进入，选择第二个格式即可。

3)在B5单元格输入公式“=E2”4）选择数据区域B5：I10，单击“数据”选项卡上的“数据工具”组中的模拟分析的下拉按钮，选择“模拟运算表”，在弹出的对话框中在“输入引用行的单元格”旁输入“D2”,在“输入引用列的单元格”旁输入“C2”点击确定即可。

注意：每位同学各自选择乘数和被乘数
3X3位十进制移位相加原理分析
当被乘数被加载于8位右移寄存器SREG8B后，随着
每一时钟节拍，最低位在前，由低位至高位逐位移出。 当为1时，1位乘法器ANDARITH打开，8位乘数 B[7..0]在同一节拍进入8位加法器，与上一次锁存在 16位锁存器REG16B中的高8位进行相加，其和在下
一时钟节拍的上升沿被锁进此锁存器。而当被乘数的 移出位为0时，与门全零输出。如此往复，直至8个时 钟脉冲后，最后乘积完整出现在REG16B端口。在这 里，1位乘法器ANDARITH的功能类似于1个特殊的与 门，即当ABIN为‘1’时，DOUT直接输出DIN，而当 ABIN为‘0’时，DOUT输出全“00000000”。
（3）实验内容1：根据给出的乘法器逻辑原理图及其 各模块的VHDL描述，在MAX+plusII上完成全部设计 ，包括编辑、编译、综合和仿真操作等。以87H乘以 F5H为例，进行仿真，对仿真波形作出详细解释，包 括对8个工作时钟节拍中，每一节拍乘法操作的方式和 结果，对照波形图给以详细说明根据顶层设计，结合 图8－3，画出乘法器的详细电路原理框图。
（4）实验内容2：编程下载，进行实验验证。实验电 路可选择电路模式1，8位乘数可分别用键2、键1输入 、8位被乘数用键4和键3输入；16位乘积可由4个数码 管（数码管8，7，6，5显示）显示；用键8输入CLK ，键7输入START。详细观察每一时钟节拍的运算结 果，并与仿真结果进行比较。
图8-4 8位移位相加乘法器运算逻辑波形图
END ANDARITH;
ARCHITECTURE behav OF ANDARITH IS
BEGIN
PROCESS(ABIN, DIN)
BEGIN