北邮数据结构实验一约瑟夫问题实验报告(递归做法)

数据结构实验报告

实验名称：实验一——线性表

学生姓名：

班级：

班内序号：

学号：

日期：

1．实验要求

（1）实验目的

通过选择下面四个题目之一进行实现，掌握如下内容：

熟悉C++语言的基本编程方法，掌握集成编译环境的调试方法

学习指针、模板类、异常处理的使用

掌握线性表的操作的实现方法

学习使用线性表解决实际问题的能力

（2）实验内容

利用循环链表实现约瑟夫问题的求解。

约瑟夫问题如下：已知n个人（n>=1）围坐一圆桌周围，从1开始顺序编号。从序号为1的人开始报数，顺时针数到m的那个人出列；他的下一个人又从1开始报数，数到m 的那个人又出列；依此规则重复下去，直到所有人全部出列。请问最后一个出列的人的编号。

2. 程序分析

2.1 存储结构

存储结构为单循环链表，线性表简称表，是由零个或多个具有相同类型的数据元素构成的有限序列。链表为了正确表示结点间的逻辑关系，在存储每个元素值的同时，还要存储该元素的直接后继元素的位置信息，这两部分信息构成了实际的存储结构，称为结点。此循环链表只为解决约瑟夫问题，所以有参构造函数让尾指针存储着最后一个元素的数据，然后指向第一个元素，形成单循环链表。如图：

（rear）

2.2 关键算法分析

1．关键算法

约瑟夫问题的实质就是在含n个元素的循环链表中依次删除第m个元素，返回链表中最

后一个元素值。即用含那n个元素的数组初始化循环链表，从第一个元素开始查找第m-1个元素，删除第m个元素，然后从第m+1个元素开始继续查找第m-1个元素，删除第m个元素，循环此过程直到链表中只剩下最后一个元素。

关键算法伪代码如下：

[1] 让用户输入要删第几个元素和总人数n，并给含n个元素的数组赋值；

[2] 用含n个元素的数组初始化循环链表（头插法）；

[3] 调用单循环表类的删除函数，实参为数组和尾指针的下一结点（即第一个元素）；[3.1] 定义新结点p，用以存储要删除的结点；

[3.2] 进行循环找到要删除元素的上一结点；

[3.3] 初始化指针p指向b->next，p的指针域指向b的指针域，第m个元素摘链，删除p，指针b后移，人数n自减1；

[3.4.1] 判断如果n等于1，输出剩下一元素的序号，然后删除最后一结点，此为递归结束条件；

[3.4.2] 判断如果n大于1，则进行自身递归调用，直至遇到结束条件停止；

[3.4.3] 如果n等于0，即一开始链表只有一个结点，输出“无人剩下！”；

2. 代码详细分析:

（1）删除操作的算法步骤：

①从第一个结点开始，查找第m-1个元素，设为b指向该结点；

②设p指向第i个元素：p = b->next;

③摘链，即将b元素从链表中摘除：b->next = p->next;

④释放q元素：delete q;

(2) 递归调用算法步骤：

①判断如果n等于1，输出剩下一元素的序号，然后删除最后一结点，此为递归结

束条件：if(n==1){cout<<”剩下一人的序号：”<next->data<

②判断如果n大于1，则进行自身递归调用，直至遇到结束条件停止:

else if(n>1) Delete(m,b->next,n);

③如果n等于0，即一开始链表只有一个结点，输出“无人剩下！”:

else if(n==0)

{

cout<<"无人剩下!"<

system("pause");

}

3．时间复杂度的计算

[1] O(n)

[2] O(n)

[3] O(1)

[3.1] O(1)

[3.2] O(m)

[3.3] O(1)

[3.4.1] O(1)

[3.4.2] O(n*m)

[3.4.3] O(1)

2.3 其他

（1）在此需要说明的是，在初始化链表时，特使用了头插法，并对头插法做了相应的修改。使尾指针rear存储着最后一个结点。

伪代码如下：

[1] 用含n个元素的数组a[]初始化循环链表；

[2] 尾指针的data域存储最后一个结点a[n-1]；

[3] 进行循环初始化新结点s存储a[i];

[4] s->next=rear->next;

[5] rear指向s: rear->next=s;

（2）在这里为了使代码简洁，在删除函数里使用了递归调用，结束条件时只剩一个人时，并输出该人序号。

3. 程序运行结果

1．流程

流程图如下：

2．测试条件：人数n和删除数m必须为整数。

3. 测试结论：

4. 总结

（1）调试时出现的问题及解决方法

①在调试时出现了执行错误，在析构函数中设置了断点。在执行时，发现析构函数停不下来，原来在删除函数里已经析构到只剩一个结点，而且尾指针可能已经被删除，所以我去掉了析构函数，而在输出最后一个结点后析构该结点。

②在执行时发现剩下一人的序号不对，在删除函数的摘链操作中设置了断点，在执行时，发现每次删除的结点不正确，原来删除函数的实参错误写为了尾指针，该为第一个结点后程序正确。

（2）心得体会

在本次实验中，熟悉了单循环链表的各种基本操作，特别对插入操作、查找操作和删除操作有了较深的理解。对于数组和指针的用法也更熟练，在程序的调试和异常处理方面有了一定的经验。相信在本次实验中积累的经验、提高的能力将在今后的实验中展现出来。尤其在递归函数的使用方面有了很大的提高，熟悉了递归函数使用条件，了解了要设置递归结束条件。

（3）下一步的改进

程序有的代码不够简洁，可以写得更简洁，可能还有更好的方法，此程序把尾指针存储了一个元素，违反了尾指针的原意，可以进一步改进。

附代码：

//ClinkList.h

#include

using namespace std;

template

struct Node//储存节点的结构

{

T data;

struct Node * next;

};

template

class ClinkList//单循环链表类

{

public:

ClinkList(){rear=new Node;rear->next=rear;}//无参构造函数ClinkList(T a[],int n);//有参构造函数

void Delete(int m,Node *b,int n);//删除结点函数

Node * rear;//尾指针

};

template

ClinkList::ClinkList(T a[],int n)//头插法

{

rear =new Node ;

rear->next=rear;

rear->data=a[n-1];

for(int i=n-2;i>=0;i--)

{

Node*s=new Node ;

s->data=a[i];

s->next=rear->next;

rear->next=s;

}

}

template

void ClinkList::Delete(int m,Node *b,int n)

{

Node * p;

for(int j=0;j<(m-2+n)%n;j++)//找到要删结点的前一结点

{

b=b->next;

}

p=b->next;

b->next=p->next;

delete p;

n--;

if(n==1)//递归结束条件

{

cout<<"剩下一人的序号是:"<next->data<

system("pause");

delete b;

}

else if(n>1) Delete(m,b->next,n);//递归函数，递归删除

else if(n==0)

{

cout<<"无人剩下!"<

system("pause");

}

}

//main.cpp

#include

#include"ClinkList.h"

using namespace std;

void main()

{

int m,n;

cout<<"输入共有几个人：";

cin>>n;

cout<<"输入要删除第几个人：";

cin>>m;

int *a=new int [n];

for(int i=0;i

a[i]=i+1;

ClinkList b(a,n);//声明对象

b.Delete(m,b.rear->next,n);

}

北邮信通院数据结构实验报告三哈夫曼编码器之欧阳光明创编

数据结构实验报告 欧阳光明（2021.03.07） 实验名称：实验三树——哈夫曼编/解码器 学生姓名： 班级： 班内序号： 学号： 日期： 2014年12月11日 1．实验要求 利用二叉树结构实现赫夫曼编/解码器。 基本要求： 1、初始化(Init)：能够对输入的任意长度的字符串s进行统 计，统计每个字符的频度，并建立赫夫曼树 2、建立编码表(CreateTable)：利用已经建好的赫夫曼树进行编 码，并将每个字符的编码输出。 3、编码(Encoding)：根据编码表对输入的字符串进行编码，并 将编码后的字符串输出。 4、译码(Decoding)：利用已经建好的赫夫曼树对编码后的字符 串进行译码，并输出译码结果。 5、打印(Print)：以直观的方式打印赫夫曼树（选作） 6、计算输入的字符串编码前和编码后的长度，并进行分析， 讨论赫夫曼编码的压缩效果。 测试数据： I love data Structure, I love Computer。I will try my best to study

data Structure. 提示： 1、用户界面可以设计为“菜单”方式：能够进行交互。 2、根据输入的字符串中每个字符出现的次数统计频度，对没有 出现的 字符一律不用编码。 2. 程序分析 2.1 存储结构 Huffman树 给定一组具有确定权值的叶子结点，可以构造出不同的二叉树，其中带权路径长度最小的二叉树称为Huffman树，也叫做最优二叉树。

weight lchild rchildparent 2-1-1-1 5-1-1-1 6-1-1-1 7-1-1-1 9-1-1-1 weight lchild rchild parent

(完整版)数据结构实验报告全集

数据结构实验报告全集 实验一线性表基本操作和简单程序 1 ．实验目的 （1 ）掌握使用Visual C++ 6.0 上机调试程序的基本方法； （2 ）掌握线性表的基本操作：初始化、插入、删除、取数据元素等运算在顺序存储结构和链表存储结构上的程序设计方法。 2 ．实验要求 （1 ）认真阅读和掌握和本实验相关的教材内容。 （2 ）认真阅读和掌握本章相关内容的程序。 （3 ）上机运行程序。 （4 ）保存和打印出程序的运行结果，并结合程序进行分析。 （5 ）按照你对线性表的操作需要，重新改写主程序并运行，打印出文件清单和运行结果 实验代码： 1）头文件模块 #include iostream.h>// 头文件 #include// 库头文件------ 动态分配内存空间 typedef int elemtype;// 定义数据域的类型 typedef struct linknode// 定义结点类型 { elemtype data;// 定义数据域 struct linknode *next;// 定义结点指针 }nodetype; 2）创建单链表

nodetype *create()// 建立单链表，由用户输入各结点data 域之值， // 以0 表示输入结束 { elemtype d;// 定义数据元素d nodetype *h=NULL,*s,*t;// 定义结点指针 int i=1; cout<<" 建立一个单链表"<> d; if(d==0) break;// 以0 表示输入结束 if(i==1)// 建立第一个结点 { h=(nodetype*)malloc(sizeof(nodetype));// 表示指针h h->data=d;h->next=NULL;t=h;//h 是头指针 } else// 建立其余结点 { s=(nodetype*) malloc(sizeof(nodetype)); s->data=d;s->next=NULL;t->next=s; t=s;//t 始终指向生成的单链表的最后一个节点

北邮2016电磁场与电磁波实验报告

电磁场与电磁波实验报告 题目：校园无线信号场强特性的研究 姓名班级学号序号

目录 一、实验目的 (2) 二、实验内容 (2) 三、实验原理 (5) 四、实验步骤 (5) 1、实验对象选取 (5) 2、数据采集 (5) 五、实验数据 (2) 1、原始数据录入 (7) 2、数据处理流程 (7) 六、实验结果与分析 (8) 1、主楼周边电磁场信号强度分析 8 2、主楼室内不同楼层楼道信号强度分析 11 七、问题分析与解决 (15) 1、Matlab 仿真问题研究与解决 (23) 2、场强分布的研究 (23)

3、模型拟合........................................................ . (24) 八、分工安排及心得体会 (25) 附录I：原始数据 (26) 附录II：源代码 (30) 一．实验目的 1.掌握在室内环境下场强的正确测试方法，理解建筑物穿透损耗 的概念； 2.通过实地测量，分析建筑物穿透损耗随频率的变化关系； 3.研究建筑物穿透损耗与建筑材料的关系。 4.掌握在移动环境下阴影衰落的概念以及正确测试方法。二．实验内容 利用DS1131场强仪和拉杆天线，实地测量信号场强。

1.研究具体现实环境下阴影衰落分布规律，以及具体的分布参数 如何； 2.研究在校园内电波传播规律与现有模型的吻合程度，测试值与 模型预测值的预测误差如何； 3.研究建筑物穿透损耗的变化规律 三．实验原理 无线通信系统是由发射机、发射天线、无线信道、接收机、接收天线所组成。对于接收者，只有处在发射信号覆盖的区域内，才能保证接收机正常接收信号，此时，电波场强大于等于接收机的灵敏度。因此，基站的覆盖区的大小，是无线工程师所关心的。决定覆盖区大小的因素主要有：发射功率、馈线及接头损耗、天线增益、天线架设高度、路径损耗、衰落、接收机高度、人体效应、接收机灵敏度、建筑物的穿透损耗、同播、同频干扰。 【阴影衰落】 阴影衰落是电磁波在空间传播时受到地形起伏、高达建筑物群的阻挡，在这些障碍物后面会产生电磁场的阴影，造成场强中值的变化，从而引起信号衰减。阴影衰落的信号电平起伏是相对缓慢的，又称为慢衰落，其特点是衰落与无线电传播地形和地物的分布、高度有关。在无线信道里，造成慢衰落的最主要原因是建筑物或其他物体对电波的遮挡。在测量过程中，不同测量位置遇到的建筑物遮挡情况不同，

北邮通电实验报告

实验3 集成乘法器幅度调制电路 信息与通信工程学院 2016211112班 苏晓玥杨宇宁 2016210349 2016210350

一．实验目的 1．通过实验了解振幅调制的工作原理。 2．掌握用MC1496来实现AM和DSB的方法，并研究已调波与调制信号，载波之间的关系。3．掌握用示波器测量调幅系数的方法。 二．实验准备 1．本实验时应具备的知识点 （1）幅度调制 （2）用模拟乘法器实现幅度调制 （3）MC1496四象限模拟相乘器 2．本实验时所用到的仪器 （1）③号实验板《调幅与功率放大器电路》 （2）示波器 （3）万用表 （4）直流稳压电源 （5）高频信号源 三．实验内容 1．模拟相乘调幅器的输入失调电压调节。 2．用示波器观察正常调幅波（AM）波形，并测量其调幅系数。 3．用示波器观察平衡调幅波（抑制载波的双边带波形DSB）波形。 四．实验波形记录、说明 1.DSB信号波形观察

2.DSB信号反相点观察 3.DSB信号波形与载波波形的相位比较 结论：在调制信号正半周期间，两者同相；负半周期间，两者反相。

4.AM正常波形观测 5.过调制时的AM波形观察（1）调制度为100%

（2）调制度大于100% （3）调制度为30% A=260.0mv B=140.0mv

五．实验结论 我们通过实验了解振幅调制的工作原理是：调幅调制就是用低频调制信号去控制高频振荡（载波）的幅度，使其成为带有低频信息的调幅波。目前由于集成电路的发展，集成模拟相乘器得到广泛的应用，为此本实验采用价格较低廉的MC1496集成模拟相乘器来实现调幅之功能。 DSB信号波形与载波波形的相位关系是：在调制信号正半周期间，两者同相；负半周期间，两者反相。 通过实验了解到了调制度的计算方法 六．课程心得体会 通过本次实验，我们了解了振幅调制的工作原理并掌握了实现AM和DSB的方法，学会计算调制度，具体见实验结论。我们对集成乘法器幅度调制电路有了更好的了解，对他有了更深入的认识，提高了对通信电子电路的兴趣。 和模电实验的单独进行，通电实验增强了团队配合的能力，两个人的有效分工提高了实验的效率，减少了一个人的独自苦恼。

北邮校园无线信号场强特性分析实验报告

校园内无线信号场强 特性研究 班级： 姓名： 学号： 序号： 日期： 北京邮电大学B e i j i n g U n i v e r s i t y o f P o s t s a n d T e l e c o m m u n i c a t i o n s

一、实验目的 1．掌握在移动环境下阴影衰落的概念以及正确的测试方法 2．研究校园内各种不同环境下阴影衰落的分布规律 3．掌握在室内环境下场强的正确测试方法，理解建筑物穿透损耗的概念 4．通过实地测量，分析建筑物穿透损耗随频率的变化关系 5．研究建筑物穿透损耗与建筑材料的关系。 二、实验原理 无线通信系统有发射机、发射天线、无线信道、接收机、接收天线所组成。对于接收者，只有处在发射信号的覆盖区域内，才能保证接收机正常接收信号，此时，电波场强大于等于接收机的灵敏度。因此，基站的覆盖区的大小，是无限工程师所关心的。决定覆盖区的大小的主要因素有：发射功率、馈线及接头损耗、天线增益、天线架设高度、路径损耗、衰落、接收机高度、人体效应、接收机灵敏度、建筑物的穿透损耗、同波、同频干扰。 无线 信道 发射接收 发射机接收机 2.1大尺度路径损耗 在移动通信系统中，路径损耗是影响通信质量的一个重要因素。 大尺度平均路径损耗：用于测量发射机与接收机之间信号的平均衰落，即定义为有效发射功率和平均接收功率之间的（dB）差值，根据理论和测试的传播模型，无论室内还是室外信道，平均接收信号功率随距离对数衰减，这种模型已被广泛使用。对于任意的传播距离，大尺度平均路径损耗表示为：

()[]()10l g (/) o o PL d dB PL d n d d =+ （n 依赖于具体的传输环境） 即平均接收功率为： 0000()[][]()10lg(/)()[]10lg(/)r t r P d dBm P dBm PL d n d d P d dBm n d d =--=- 其中，n 为路径损耗指数，表明路径损耗随距离增长的速度；d0为近地参考距离；d 为 发射机与接收机（T-R ）之间的距离。公式中的横岗表示给定值d 的所有可能路径损耗的综合平均。坐标为对数—对数时，平均路径损耗或平均接收功率可表示为斜率10ndB/10倍程的直线。n 值依赖于特定的传播环境。例如在自由空间，n 为2，当有阻挡物时，n 比2大。 决定路径损耗大小的首要因素是距离，此外，它还与接收点的电波传播条件密切相关。为此，我们引进路径损耗中值的概念。中值是使实测数据中一半大于它而另一半小于它的一个数值（对于正态分布中值就是均值）。人们根据不同的地形地貌条件，归纳总结出各种电波传输模型。下边介绍几种常用的描述大尺度衰落的模型。 2.2 常用的电波传播模型 2.2.1自由空间模型 自由空间模型假定发射天线和接收台都处在自由空间。我们所说的自由空间一是指真空，二是指发射天线与接收台之间不存在任何可能影响电波传播的物体，电波是以直射线的方式到达移动台的。 自由空间模型计算路径损耗的公式是： ()10lg /32.420lg 20lg p t r L P P d f ==++ 其中p L 是以B d 为单位的路径损耗，d 是以公里为单位的移动台和基站之间的距离，f 是以MHz 为单位的移动工作频点或工作频段的频率。 空气的特性近似为真空，因此当发射天线和接收天线距离地面都比较高时，可以近似使用自由空间模型来估计路径损耗。 2.2.2布灵顿模型 布灵顿模型假设发射天线和移动台之间是理想平面大地，并且两者之间的距离d 远大于发射天线的高度ht 或移动台的高度hr 。 布灵顿模型的出发角度是接收信号来自于电波的直射和一次反射，也被叫做“平面大地模型”。 该模型的路径损耗公式为： 12040lg 20lg 20lg p t r L d h h =+-- 单位： d （km ） ht （m ）hr （m ）Lp （dB ）

北邮微波实验报告整理版

北京邮电大学信息与通信工程学院 微波实验报告 班级：20112111xx 姓名：xxx 学号：20112103xx 指导老师：徐林娟 2014年6月

目录 实验二分支线匹配器 (1) 实验目的 (1) 实验原理 (1) 实验内容 (1) 实验步骤 (1) 单支节 (2) 双支节 (7) 实验三四分之一波长阻抗变换器 (12) 实验目的 (12) 实验原理 (12) 实验内容 (13) 实验步骤 (13) 纯电阻负载 (14) 复数负载 (19) 实验四功分器 (23) 实验目的 (23) 实验原理 (23) 实验内容 (24) 实验步骤 (24) 公分比为1.5 (25) 公分比为1（等功分器） (29) 心得体会 (32)

201121111x 班-xx 号-xx ——电磁场与微波技术实验报告 实验二 分支线匹配器 实验目的 1．熟悉支节匹配器的匹配原理 2．了解微带线的工作原理和实际应用 3．掌握Smith 图解法设计微带线匹配网络 实验原理 支节匹配器是在主传输线上并联适当的电纳（或者串联适当的电抗），用附加的反射来抵消主传输线上原来的反射波，以达到匹配的目的。 单支节匹配器，调谐时主要有两个可调参量：距离d 和由并联开路或短路短截线提供的电纳。匹配的基本思想是选择d ，使其在距离负载d 处向主线看去的导纳Y 是Y0+jB 形式。然后，此短截线的电纳选择为-jB ，根据该电纳值确定分支短截线的长度，这样就达到匹配条件。 双支节匹配器，通过增加一个支节，改进了单支节匹配器需要调节支节位置的不足，只需调节两个分支线长度，就能够达到匹配（但是双支节匹配不是对任意负载阻抗都能匹配的，即存在一个不能得到匹配的禁区）。 微带线是有介质εr (εr >1)和空气混合填充，基片上方是空气，导体带条和接地板之间是介质εr ，可以近似等效为均匀介质填充的传输线，等效介质电常数为 εe ，介于1和εr 之间，依赖于基片厚度H 和导体宽度W 。而微带线的特性阻抗与其等效介质电常数为εe 、基片厚度H 和导体宽度W 有关。 实验内容 已知：输入阻抗Z 75in ，负载阻抗Z (6435)l j ，特性阻抗0Z 75 ，介质基片 2.55r ，1H mm 。 假定负载在2GHz 时实现匹配，利用图解法设计微带线单支节和双支节匹配网络，假设双支节网络分支线与负载的距离114d ，两分支线之间的距离为21 8 d 。画出几种可能的电路图并且比较输入端反射系数幅度从1.8GHz 至2.2GHz 的变化。 实验步骤 1．根据已知计算出各参量，确定项目频率。 2．将归一化阻抗和负载阻抗所在位置分别标在Smith 圆上。 3．设计单枝节匹配网络，在图上确定分支线与负载的距离以及分支线的长度，根据给定的介质基片、特性阻抗和频率用TXLINE 计算微带线物理长度和宽度。此处应该注意电长度和实际长度的联系。 4．画出原理图，在用微带线画出基本的原理图时，注意还要把衬底添加到图中，将各部分的参数填入。注意微带 分支线处的不均匀性所引起的影响，选择适当的模型。 5．负载阻抗选择电阻和电感串联的形式，连接各端口，完成原理图，并且将项目的频率改为1.8—2.2GHz 。 6．添加矩形图，添加测量，点击分析，测量输入端的反射系数幅值。 7．同理设计双枝节匹配网络，重复上面的步骤。

北邮数据结构实验3哈夫曼编码

数据结构实验报告 实验名称：实验3——哈夫曼编码 学生姓名： 班级： 班内序号： 学号： 日期：2013年11月24日 1．实验要求 利用二叉树结构实现赫夫曼编/解码器。 基本要求： 1、初始化(Init)：能够对输入的任意长度的字符串s进行统计，统计每个 字符的频度，并建立赫夫曼树 2、建立编码表(CreateTable)：利用已经建好的赫夫曼树进行编码，并将每 个字符的编码输出。 3、编码(Encoding)：根据编码表对输入的字符串进行编码，并将编码后的 字符串输出。 4、译码(Decoding)：利用已经建好的赫夫曼树对编码后的字符串进行译 码，并输出译码结果。 5、打印(Print)：以直观的方式打印赫夫曼树（选作） 6、计算输入的字符串编码前和编码后的长度，并进行分析，讨论赫夫曼 编码的压缩效果。 2. 程序分析 2.1存储结构： struct HNode { char c;//存字符内容 int weight; int lchild, rchild, parent; }; struct HCode

{ char data; char code[100]; }; //字符及其编码结构 class Huffman { private: HNode* huffTree; //Huffman树 HCode* HCodeTable; //Huffman编码表 public: Huffman(void); void CreateHTree(int a[], int n); //创建huffman树 void CreateCodeTable(char b[], int n); //创建编码表 void Encode(char *s, string *d); //编码 void Decode(char *s, char *d); //解码 void differ(char *,int n); char str2[100];//数组中不同的字符组成的串 int dif;//str2[]的大小 ~Huffman(void); }; 结点结构为如下所示： 三叉树的节点结构： struct HNode//哈夫曼树结点的结构体 { int weight;//结点权值 int parent;//双亲指针 int lchild;//左孩子指针 int rchild;//右孩子指针 char data;//字符 }; 示意图为： int weight int parent int lchild int rchild Char c 编码表节点结构：

数据结构实验报告

数据结构实验报告 一．题目要求 1）编程实现二叉排序树，包括生成、插入，删除； 2）对二叉排序树进行先根、中根、和后根非递归遍历； 3）每次对树的修改操作和遍历操作的显示结果都需要在屏幕上用树的形状表示出来。 4）分别用二叉排序树和数组去存储一个班(50人以上)的成员信息(至少包括学号、姓名、成绩3项),对比查找效率，并说明在什么情况下二叉排序树效率高,为什么? 二．解决方案 对于前三个题目要求，我们用一个程序实现代码如下 #include #include #include #include "Stack.h"//栈的头文件，没有用上 typedefintElemType; //数据类型 typedefint Status; //返回值类型 //定义二叉树结构 typedefstructBiTNode{ ElemType data; //数据域 structBiTNode *lChild, *rChild;//左右子树域 }BiTNode, *BiTree; intInsertBST(BiTree&T,int key){//插入二叉树函数 if(T==NULL) { T = (BiTree)malloc(sizeof(BiTNode)); T->data=key; T->lChild=T->rChild=NULL; return 1; } else if(keydata){ InsertBST(T->lChild,key); } else if(key>T->data){ InsertBST(T->rChild,key); } else return 0; } BiTreeCreateBST(int a[],int n){//创建二叉树函数 BiTreebst=NULL; inti=0; while(i

北邮—电磁场实验之校园场强

电磁场实验 校园内无线信号场强特性的研究 学院：信息与通信工程学院 班级： _______________________________ 姓名： _______________________________ 学号： _______________________________ 班内序号：

、实验目的 1、掌握在移动环境下阴影衰落的概念以及正确测试方法； 2、研究校园内不同环境下阴影衰落的分布规律； 3、熟练使用DS1131场强仪实地测试信号场强的方法； 4、学会对大量数据进行统计分析和处理，进而得出实验结论 二、实验原理 1、三种基本电波传播机制 影响电波在空间传播的三种最基本的机制为反射、绕射、散射。当电磁波传 播遇到比其波长大得多的物体时，发生反射。当接收机和发射机之间无线路径被尖利的边缘阻挡时会发生绕射。散射波产生于粗糙表面、小物体或其它不规则物体，比如树叶、街道标志和灯柱等都会引发散射。 2、阴影衰落 在无线信道里，造成慢衰落的最主要原因是建筑物或其它物体对电波的遮挡。 在测量过程中，不同位置遇到的建筑物遮挡情况不同，因此接收功率也不同，这样就会观察到衰落现象，这就叫“阴影效应”或“阴影衰落”。在阴影衰落的情况下收到的信号是各种绕射，反射，散射波的合成。所以，在距基站距离相同的地方，由于阴影效应的不同，它们收到的信号功率有可能相差很大，理论和测试表明，对任意的d值，特定位置的接受功率为随机对数正态分布。 对数正态分布描述了在传播路径上，具有相同T-R距离时，不同的随机阴影 效应。这样利用高斯分布可以方便地分析阴影的随机效应。正态分布，也叫高斯 分布，它的概率密度函数是： (??- ??)2 ???? = 2?? 应用于阴影衰落时，上式中的？表示某一次测量得到的接收功率，？?表示以dB表示的接收功率的均值或中值，（表示接收功率的标准差，单位是dB。阴影 衰落的标准差同地形，建筑物类型，建筑物密度等有关，在市区的150MHz频段其典型值是5dB

北京邮电大学通信原理软件实验报告

北京邮电大学实验报告 题目：基于SYSTEMVIEW通信原理实验报告

实验一：验证抽样定理 一、实验目的 1、掌握抽样定理 2. 通过时域频域波形分析系统性能 二、实验原理 低通滤波器频率与m（t）相同 三、实验步骤 1. 要求三个基带信号相加后抽样，然后通过低通滤波器恢复出原信号。 2. 连接各模块完成系统，同时在必要输出端设置观察窗。 3. 设置各模块参数。 三个基带信号的频率从上到下分别设置为10hz、12hz、14hz。 抽样信号频率设置为28hz，即2*14hz。（由抽样定理知，） 将低通滤波器频率设置为14hz，则将恢复第三个信号（其频率为14hz）进行系统定时设置，起始时间设为0，终止时间设为1s.抽样率设为1khz。 3.观察基带信号、抽样后的信号、最终恢复的信号波形

四、实验结果 最上面的图为原基带信号波形，中间图为最终恢复的信号波形，最下面的图为抽样后的信号波形。 五、实验讨论 从实验结果可以看出，正如前面实验原理所述，满足抽样定理的理想抽样应该使抽样后的波形图如同冲激信号，且其包络图形为原基带信号波形图。抽样后的信号通过低通滤波器后，恢复出的信号波形与原基带信号相同。 由此可知，如果每秒对基带模拟信号均匀抽样不少于2次，则所得样值序列含有原基带信号的全部信息，从该样值序列可以无失真地恢复成原来的基带信号。 讨论：若抽样速率少于每秒2次，会出现什么情况？ 答：会产生失真，这种失真被称为混叠失真。 六、实验建议、意见 增加改变抽样率的步骤，观察是否产生失真。

实验二:奈奎斯特第一准则 一、实验目的 （1）理解无码间干扰数字基带信号的传输； （2）掌握升余弦滚降滤波器的特性； （3）通过时域、频域波形分析系统性能。 二、实验原理 在现代通信系统中，码元是按照一定的间隔发送的，接收端只要能够正确地恢复出幅度序列，就能够无误地恢复传送的信号。因此，只需要研究如何使波形在特定的时刻无失真，而不必追求整个波形不变。 奈奎斯特准则提出：只要信号经过整形后能够在抽样点保持不变，即使其波形已经发生了变化，也能够在抽样判决后恢复原始的信号，因为信息完全恢复携带在抽样点幅度上。 奈奎斯特准则要求在波形成形输入到接收端的滤波器输出的整个传送过程传递函数满足：,其充分必要条件是x(t)的傅氏变换X ( f )必须满足 奈奎斯特准则还指出了信道带宽与码速率的基本关系。即R B =1/T B =2? N =2B N。 式中R b 为传码率，单位为比特/每秒（bps）。f N 和B N 分别为理想信道的低通截止 频率和奈奎斯特带宽。上式说明了理想信道的频带利用率为R B /B N =2。 在实际应用中，理想低通滤波器是不可能实现的，升余弦滤波器是在实际中满足无码间干扰传输的充要条件，已获得广泛应用的滤波器。 升余弦滤波器的带宽为：。其中，α为滚降系数，0 ≤α≤1， 三、实验步骤 1.根据奈奎斯特准则，设计实现验证奈奎斯特第一准则的仿真系统，同时在必 要输出端设置观察窗。设计图如下

数据结构实验报告范例

《数据结构与算法》实验报告 专业班级姓名学号 实验项目 实验一二叉树的应用 实验目的 1、进一步掌握指针变量的含义及应用。 2、掌握二叉树的结构特征，以及各种存储结构的特点及使用范围。 3、掌握用指针类型描述、访问和处理二叉树的运算。 实验内容 题目1:编写一个程序，采用一棵二叉树表示一个家谱关系。要求程序具有如下功能：（1）用括号表示法输出家谱二叉树， （2）查找某人的所有儿子， （3）查找某人的所有祖先。 算法设计分析 （一）数据结构的定义 为了能够用二叉树表示配偶、子女、兄弟三种关系，特采用以下存储关系，则能在二叉树上实现家谱的各项运算。 二叉树型存储结构定义为： typedef struct SNODE {char name[MAX]; //人名 struct SNODE *left; //指向配偶结点 struct SNODE *right; //指向兄弟或子女结点 }FNODE; （二）总体设计 实验由主函数、家谱建立函数、家谱输出函数、儿子查找函数、祖先查找函数、结点定位函数、选择界面函数七个函数共同组成。其功能描述如下： （1）主函数：统筹调用各个函数以实现相应功能 void main() （2）家谱建立函数：与用户交互建立家族成员对应关系 void InitialFamily(FNODE *&head) //家谱建立函数 （3）家谱输出函数：用括号表示法输出家谱 输出形式为：父和母（子1和子妻1（孙1），子2和子妻2（孙2）） void PrintFamily(FNODE *head) //家谱输出函数

（4）儿子查找函数：在家谱中查找到某人所有的子女并输出，同时也能辨别出其是否为家族成员与是否有子女 void FindSon(FNODE *b,char p[]) //儿子查找函数 （5）祖先查找函数：在家谱中查找到某人所有的祖先并输出，同时也能辨别出其是否为家族中成员。 int FindAncestor(FNODE *head,char son[ ]) //祖先查找函数 （6）结点定位函数：在家谱中找到用户输入人名所对应的结点。 FNODE *findnode(FNODE *b,char p[]) //结点定位函数 （7）选择界面函数：为便于编写程序，将用户选择部分独立为此函数。 void PRINT(int &n) （三）各函数的详细设计： void InitialFamily(FNODE *&head) //家谱建立函数 1：首先建立当前人的信息，将其左右结点置为空， 2：然后让用户确定其是否有配偶，如果没有配偶，则当前程序结束， 3：如果有则建立其配偶信息，并将配偶结点赋给当前人的左结点； 4：再让用户确定其是否有子女，如果有则递归调用家谱建立函数建立子女结点，并将其赋给配偶结点的下一个右结点。 5：如无，则程序结束 void PrintFamily(FNODE *head) //家谱输出函数 1：首先判断当前结点是否为空，如果为空则结束程序； 2：如果不为空，则输出当前结点信息， 3：然后判断其左结点（配偶结点）是否为空，如不为空则输出“和配偶信息。 4：再判断配偶结点的右结点是否为空，如不为空则递归调用输出其子女信息，最后输出“）”； 5：当配偶结点为空时，则判断其右结点（兄弟结点）是否为空 6：如果不为空，则输出“，”，并递归调用输出兄弟信息 7程序结束 FNODE *findnode(FNODE *b,char p[]) //结点定位函数 1：当前结点是否为空，为空则返回空； 2：如果和查找信息相同，则返回当前结点； 3：如不然，则先后递归访问其左结点，再不是则递归访问右结点 void FindSon(FNODE *b,char p[]) //儿子查找函数 1：在家谱中定位到要查找的结点，如无则输出“查找不到此人” 2：判断其配偶结点与子女结点是否为空，为空则输出“无子女” 3：不为空则输出其配偶结点的所有右结点（子女结点）。 int FindAncestor(FNODE *head,char son[ ]) //祖先查找函数 1：先在家谱中定位到要查找的结点，如为空输出“不存在此人”，程序结束 2：先将父母结点入栈，当栈为空时程序结束， 3：栈不为空时，判断栈顶元素是否已访问过， 4：访问过，再判断是否为查找结点，如是则输出栈中保存的其祖先结点，并滤过其兄弟结点不输出；不是查找结点，则退栈一个元素 5：未访问过，则取当前栈顶元素，置访问标志——1，同时取其右结点 6：栈不为空或当前所取结点不为空时，转到2； 实验测试结果及结果分析

北邮场强仪实验报告

北邮场强仪实验报告 Company Document number：WUUT-WUUY-WBBGB-BWYTT-1982GT

电磁 场与电磁波实验报告 班级 姓名： 学号： 姓名： 学号： 时间：2015年5月3日 校园内无线信号场强特性的研究 一、实验目的 1.掌握在移动环境下阴影衰落的概念以及正确测试方法； 2.研究校园内各种不同环境下阴影衰落的分布规律； 3.掌握在室内环境下场强的正确测试方法，理解建筑物穿透损耗的概念； 4.通过实地测量，分析建筑物穿透损耗随频率的变化关系； 5.研究建筑物穿透损耗与建筑材料的关系。 二、实验内容 无线通信系统是由发射机，发射天线，无线信道，接收机，接收天线所组成。对于接收者，只有处在发射信号的覆盖区内，才能保证接收机正常接收信号，此时，电波场强大于等于接收机的灵敏度。因此，基站的覆盖区的大小，是无线工程师所关心的。决定覆盖区的大小的主要因素有：发射功率，馈线及接头损耗，天线增益，天线架设高度，路径损耗，衰落，接收机高度，人体效应，接收机灵敏度，建筑物的穿透损耗，同播，同频干扰。 (1) 大尺度路径损耗 在移动通信系统中，路径损耗是影响通信质量的一个重要因素。大尺度路径损耗：用于测量发射机与接收机之间信号的平均衰落，即定义为有效发射功率和平均接收功率之间的(dB)差值，根据理论和测试的传播模型，无论室内或室外信道，平均接收信号功率随距离对数衰减，这种模型已被广泛地采 用。对任意的传播距离，大尺度平均路径损耗表示式为： PL(d )[dB] PL(d )10n lg(d / d ) (5-1) 即平均接收功率为：

P (d )dBm PdBm PL(d )10n log(d / d ) P (d )dBm10n log(d / d ) （5-2） 其中，n 为路径损耗指数，表明路径损耗随距离增长的速度；d 0为近地参考距离；d 为发射机与接收机(T-R)之间的距离。公式(5-1)和(5-2)中的横杠表示给定值 d的所有可能路径损耗的综合平均。坐标为对数-对数时，平均路径损耗或平均接收功率可表示为斜率 10ndB/10 倍程的直线。n 值取决于特定的传播环境。例如在自由空间，n 为 2，当有阻挡物时，n 比 2 大。决定路径损耗大小的首要因素是距离，此外，它还与接收点的电波传播条件密切相关。为此，我们引进路径损耗中值的概念。中值是使实测数据中一半大于它而另一半小于它的一个数值(对于正态分布中值就是均值)。人们根据不同的地形地貌条件，归纳总结出各种电波传播模型。常见的电波传播模型有： 1) 自由空间模型 自由空间模型假定发射天线和接收台都处在自由空间。自由空间一是指真空，二是指发射天线与接收台之间不存在任何可能影响电波传播的物体，电波是以直射线的方式到达移动台的。自由空间模型计算路径损耗的公式是： Lp 20Lgd 20Lgf （5-3） 其中 Lp 是以 dB 为单位的路径损耗，d 是以公里为单位的移动台与基站之间的距离，f 是以 MHz 为单位的移动工作频点或工作频段的频率。 空气的特性可近似为真空，因此当发射天线与移动台距离地面都较高时，可以近似使用自由空间模型来估计路径损耗。 2) 布灵顿模型 布灵顿模型假设发射天线和移动台之间的地面时理想平面大地，并且两者之间的距离 d 远大于发射天线的高度 ht 或移动台的高度 hr，此时的路径损耗计算公式为：Lp 120 40Lgd 20Lgt 20Lghr （5-4） 其中距离 d 的单位是公里，天线高度 ht 及 hr 的单位是米，路径损耗 Lp 的单位是dB。系统设计时一般把接收机高度按典型值 hr= 处理，这时的路径损耗计算公式为：Lp 40Lgd 20Lght （5-5） 按自由空间模型计算时，距离增加一倍时对应的路劲损耗增加 6dB；按布灵顿模型计算时，距离增加一倍时对应的路径损耗要增加 12dB。 3) EgLi 模型 前述的自由空间模型及布灵顿模型都是基于理论分析得出的计算公式。EgLi模型则是从大量实测结果中归纳出来的中值预测公式，属于经验模型，其计算式为：Lp 88 40Lgd 20Lght 20Lghr 20Lgf G （5-6） 其中路径损耗 Lp 的单位是 dB，距离 d 的单位是公里，天线高度 ht 及 hr 的单位是米，工作频率 f 的单位是 MHz，地形修正因子 G 的单位是 dB。G 反应了地形因素对路径损耗的影响。 EgLi 模型认为路径损耗同接收点的地形起伏程度h 有关，地形起伏越大，则路径损耗也越大。当h 用来测量时，可按下式近似的估计地形的影响： 若将移动台的典型高度值 hr= 代入 EgLi 模型，则有： Lp 40Lgd 20Lght 20Lgf G （5-8） 4) Hata- Okumu ra 模 型 H ata- Okumu

北邮arduino实验报告

电子电路综合实验设计 实验名称： 基于 Arduino 的电压有效值测量电路设计与实现 学院： 班级： 学号： 姓名： 班内序号：

实验 基于Arduino 的电压有效值测量电路设计与实现 一. 摘要 Arduino是一个基于开放原始码的软硬件平台，可用来开发独立运作、并具互动性的电子产品，也可以开发与PC 相连的周边装置，同时能在运行时与PC 上的软件进行交互。为了测量正弦波电压有效值，首先我们设计了单电源供电的半波整流电路，并进行整流滤波输出，然后选择了通过Arduino设计了读取电压有效值的程序，并实现使用此最小系统来测量和显示电压有效值。在频率和直流电压幅度限定在小范围的情况下，最小系统的示数基本和毫伏表测量的值相同。根据交流电压有效值的定义，运用集成运放和设计的Arduino最小系统的结合，实现了运用少量元器件对交流电压有效值的测量。 关键字:半波整流整流滤波 Arduino最小系统读取电压有效值 二. 实验目的 1、熟悉Arduino 最小系统的构建和使用方法； 2、掌握峰值半波整流电路的工作原理； 3、根据技术指标通过分析计算确定电路形式和元器件参数； 4、画出电路原理图（元器件标准化，电路图规范化）； 5、熟悉计算机仿真方法； 6、熟悉Arduino 系统编程方法。 三. 实验任务及设计要求 设计实现 Arduino 最小系统，并基于该系统实现对正弦波电压有效值的测量和显示。 1、基本要求 （1）实现Arduino 最小系统，并能下载完成Blink 测试程序，驱动Arduino 数字13 口LED 闪烁； （2）电源部分稳定输出5V 工作电压，用于系统供电； （3）设计峰值半波整流电路，技术指标要求如下：

北邮数据结构实验四-链表排序

数据结构实验报告 实验名称：实验四——链表的排序 学生姓名： 班级： 班内序号： 学号： 日期： 1．实验要求 [内容要求] 使用链表实现下面各种排序算法，并进行比较。 排序算法： 1、插入排序 2、冒泡排序 3、快速排序 4、简单选择排序 5、其他 要求： 1、测试数据分成三类：正序、逆序、随机数据 2、对于这三类数据，比较上述排序算法中关键字的比较次数和移动次数（其 中关键字交换计为3次移动）。 3、对于这三类数据，比较上述排序算法中不同算法的执行时间，精确到微秒 （选作） 4、对2和3的结果进行分析，验证上述各种算法的时间复杂度 编写测试main()函数测试线性表的正确性 代码要求 1、必须要有异常处理，比如删除空链表时需要抛出异常； 2、保持良好的编程的风格： 代码段与段之间要有空行和缩近 标识符名称应该与其代表的意义一致 函数名之前应该添加注释说明该函数的功能 关键代码应说明其功能 3、递归程序注意调用的过程，防止栈溢出

2. 程序分析 2.1 存储结构 [内容要求] 存储结构：双链表 2.2 关键算法分析 [内容要求] 定义类： template class LinkList { public: LinkList(){front = new Node ;front->next=rear;front->prior=NULL;rear=new Node;rear->next=NULL;rear->prior=front;} LinkList(T a[],int n); void BackLinkList(T a[]);//恢复原链表 ~LinkList();//析构函数 void PrintList();//打印数列 void InsertSort();//插入排序 void BubbleSort();//冒泡排序 Node * Partion(Node *i,Node *j);//快速排序中寻找轴值的函数 void Qsort(Node *i,Node *j);//快速排序 void SelectSort();//选择排序 Node*front; Node*rear; }; 成员函数包括：构造函数：单链表，打印单链表，插入排序，快速排序，冒泡排序，选择排序，析构函数 公有成员：头指针和尾指针 1、构造函数： LinkList::LinkList(T a[],int n) { front=new Node; rear=new Node; front->prior=NULL;front->next=rear; rear->next=NULL;rear->prior=front; Node *s; for (int i=n-1;i>=0;i--) {

北邮电磁场与电磁波实验报告

信息与通信工程学院 电磁场与电磁波实验报告 题目：校园信号场强特性的研究 姓名班级学号序号薛钦予2011210496 201121049621

一、实验目的 1.掌握在移动环境下阴影衰落的概念以及正确的测试方法； 2.研究校园内各种不同环境下阴影衰落的分布规律； 3.掌握在室内环境下场强的正确测量方法，理解建筑物穿透损耗的概念； 4.通过实地测量，分析建筑物穿透损耗随频率的变化关系； 5.研究建筑物穿透损耗与建筑材料的关系。 二、实验原理 1、电磁波的传播方式 无线通信系统是由发射机、发射天线、无线信道、接收机、接收天线所组成。对于接受者，只有处在发射信号的覆盖区内，才能保证接收机正常接受信号，此时，电波场强大于等于接收机的灵敏度。因此基站的覆盖区的大小，是无线工程师所关心的。决定覆盖区的大小的主要因素有：发射功率，馈线及接头损耗，天线增益，天线架设高度，路径损耗，衰落，接收机高度，人体效应，接收机灵敏度，建筑物的穿透损耗，同播，同频干扰等。 电磁场在空间中的传输方式主要有反射﹑绕射﹑散射三种模式。当电磁波传播遇到比波长大很多的物体时，发生反射。当接收机和发射机之间无线路径被尖锐物体阻挡时发生绕射。当电波传播空间中存在物理尺寸小于电波波长的物体﹑且这些物体的分布较密集时，产生散射。散射波产生于粗糙表面，如小物体或其它不规则物体﹑树叶﹑街道﹑标志﹑灯柱。 2、尺度路径损耗 在移动通信系统中，路径损耗是影响通信质量的一个重要因素。大尺度平均路径损耗：用于测量发射机与接收机之间信号的平均衰落，即定义为有效发射功率和平均接受功率之间的（dB）差值，根据理论和测试的传播模型，无论室内或室外信道，平均接受信号功率随距离对数衰减，这种模型已被广泛的使用。对任意的传播距离，大尺度平均路径损耗表示为： ()[]()() =+（式1） 010log/0 PL d dB PL d n d d 即平均接收功率为： ()[][]()()()[]() =--=- Pr010log/0Pr010log/0 d dBm Pt dBm PL d n d d d dBm n d d （式2）其中，定义n为路径损耗指数，表明路径损耗随距离增长的速度，d0为近地参考距离，d为发射机与接收机之间的距离。公式中的横杠表示给定值d的所有可能路径损耗的综合平均。坐标为对数－对数时，平均路径损耗或平均接收功率可以表示为斜率10ndB /10 倍程的直线。n依赖于特定的传播环境，例如在自由空间，n为2；当有阻挡物时，n比2大。

北邮通信原理实验报告

北京邮电大学通信原理实验报告 学院：信息与通信工程学院班级： 姓名： 姓名：

实验一：双边带抑制载波调幅（DSB-SC AM ） 一、实验目的 1、了解DSB-SC AM 信号的产生以及相干解调的原理和实现方法。 2、了解DSB-SC AM 信号波形以及振幅频谱特点,并掌握其测量方法。 3、了解在发送DSB-SC AM 信号加导频分量的条件下,收端用锁相环提取载波的原理及其实现方法。 4、掌握锁相环的同步带和捕捉带的测量方法,掌握锁相环提取载波的调试方法。 二、实验原理 DSB 信号的时域表达式为 ()()cos DSB c s t m t t ω= 频域表达式为 1 ()[()()]2 DSB c c S M M ωωωωω=-++ 其波形和频谱如下图所示 DSB-SC AM 信号的产生及相干解调原理框图如下图所示

将均值为零的模拟基带信号m(t)与正弦载波c(t)相乘得到DSB—SC AM信号，其频谱不包含离散的载波分量。 DSB—SC AM信号的解调只能采用相干解调。为了能在接收端获取载波，一种方法是在发送端加导频，如上图所示。收端可用锁相环来提取导频信号作为恢复载波。此锁相环必须是窄带锁相，仅用来跟踪导频信号。 在锁相环锁定时，VCO输出信号sin2πf c t+φ与输入的导频信号cos2πf c t 的频率相同，但二者的相位差为φ+90°，其中很小。锁相环中乘法器的两个 输入信号分别为发来的信号s(t)（已调信号加导频）与锁相环中VCO的输出信号，二者相乘得到 A C m t cos2πf c t+A p cos2πf c t?sin2πf c t+φ =A c 2 m t sinφ+sin4πf c t+φ+ A p 2 sinφ+sin4πf c t+φ 在锁相环中的LPF带宽窄，能通过A p 2 sinφ分量，滤除m(t)的频率分量及四倍频载频分量，因为很小，所以约等于。LPF的输出以负反馈的方式控制VCO,使其保持在锁相状态。锁定后的VCO输出信号sin2πf c t+φ经90度移相后，以cos2πf c t+φ作为相干解调的恢复载波，它与输入的导频信号cos2πf c t 同频，几乎同相。 相干解调是将发来的信号s(t)与恢复载波相乘，再经过低通滤波后输出模拟基带信号 A C m t cos2πf c t+A p cos2πf c t?cos2πf c t+φ =A c 2 m t cosφ+cos4πf c t+φ+ A p 2 cosφ+cos4πf c t+φ 经过低通滤波可以滤除四倍载频分量，而A p 2 cosφ是直流分量，可以通过隔直