信号放大器.doc-资料库

e1900f94-eec3-49b6-a0b7-faa7530514ed.doc.pdf-第1页.png

第1页 / 共18页

e1900f94-eec3-49b6-a0b7-faa7530514ed.doc.pdf-第2页.png

第2页 / 共18页

e1900f94-eec3-49b6-a0b7-faa7530514ed.doc.pdf-第3页.png

第3页 / 共18页

e1900f94-eec3-49b6-a0b7-faa7530514ed.doc.pdf-第4页.png

第4页 / 共18页

e1900f94-eec3-49b6-a0b7-faa7530514ed.doc.pdf-第5页.png

第5页 / 共18页

e1900f94-eec3-49b6-a0b7-faa7530514ed.doc.pdf-第6页.png

第6页 / 共18页

e1900f94-eec3-49b6-a0b7-faa7530514ed.doc.pdf-第7页.png

第7页 / 共18页

e1900f94-eec3-49b6-a0b7-faa7530514ed.doc.pdf-第8页.png

第8页 / 共18页

课程设计任务书 2010—2011 学年第 1 学期电子与信息工程系专业班级课程设计名称：数据结构课程设计设计题目：信号放大器完成期限：自 2012 年 1 月 2 日至 2012 年 1 月 6 日共 1 周设计依据、要求及主要内容（可另加附页）：一、设计目的熟悉各种数据结构和运算，会使用数据结构的基本操作解决一些实际问题。二、设计要求（1）重视课程设计环节，用严谨、科学和踏实的工作态度对待课程设计的每一项任务；（2）按照课程设计的题目要求，独立地完成各项任务，严禁抄袭；凡发现抄袭，抄袭者与被抄袭者皆以零分计入本课程设计成绩。凡发现实验报告或源程序雷同，涉及的全部人员皆以零分计入本课程设计成绩；（3）学生在接受设计任务后，首先要按设计任务书的要求编写设计进程表；（4）认真编写课程设计报告。三、设计内容 1) 问题描述天然气经过管道网络从其生产基地输送到消耗地，在传输过程中，其性能的某一个或几个方面可能会有所衰减（例如气压）。为了保证信号衰减不超过容忍值，应在网络中的合适位置放置放大器以增加信号（例如电压）使其与源端相同。设计算法确定把信号放大器放在何处，能使所用的放大器数目最少并且保证信号衰减不超过给定的容忍值。 2) 基本要求 (1) 建立模型，设计数据结构； (2) 设计算法完成放大器的放置； (3) 分析算法的时间复杂度。 3) 设计思想为了简化问题，假设分布网络是二叉树结构，源端是树的根结点，信号从一个结点流向其孩子结点，树中的每一结点（除了根）表示一个可以用来放置放大器的位置。图5是一个网络示意图，边上标出的是从父结点到子结点的信号衰减量。

3 1 C A 1 2 E 2 D B 1 I 2 H 2 F J 图 5 网络分布示意图 2 G 2 K 对于网络中任一结点 i，设 d(i)表示结点 i 与其父结点间的衰减量，D(i)为从结点 i 到结点 i 的子树中任一叶子结点的衰减量的最大值，并有如下递推公式： D(i)=0 D(i)= max{D(j) + d(j)} 若 i 不是叶结点且 j 是 i 的孩子若 i 为叶结点在此公式中，要计算某结点的 D 值，必须先计算其孩子结点的 D 值，因而必须后序遍历二叉树，当访问一个结点时，计算其 D 值。例如，D(B)=max{D(D)+d(D)，D(E)}=4，若容忍值为 3，则在 B 点或其祖先的任意一点放置放大器，并不能减少 B 与其后代的衰减量，必须在 D 点放置一个放大器或在其孩子结点放置一个或多个放大器。若在结点 D 处放置一个放大器，则 D(B)=2。四、参考文献 1．王红梅．数据结构．清华大学出版社 2．王红梅．数据结构学习辅导与实验指导．清华大学出版社 3．严蔚敏，吴伟民．数据结构（C 语言版）．清华大学出版社

目录一、需求分析 ................................................................................................................................................1 1. 程序的功能 ..................................................................................................................................................1 2. 输入输出的要求 ..........................................................................................................................................1 3. 测试数据 ......................................................................................................................................................1 二、概要设计 ................................................................................................................................................2 三、详细设计 ................................................................................................................................................3 1. 程序的入口和出口函数 ..............................................................................................................................3 2. 核心函数 ......................................................................................................................................................3 3. 输出函数 ......................................................................................................................................................6 4. 重载函数 ......................................................................................................................................................7 四、调试分析 ................................................................................................................................................8 五、核心源程序清单和执行结果 .................................................................................................................9 1. 头文件 ..........................................................................................................................................................9 2. 各种子函数文件 ........................................................................................................................................10 3. 主程序文件 ................................................................................................................................................13 4. 执行结果 ....................................................................................................................................................14 六、心得体会 ..............................................................................................................................................15

一、需求分析 1. 程序的功能假设分布网络是二叉树结构，源端是树的根结点，信号从一个结点流向其孩子结点，树中的每一结点（除了根）表示一个可以用来放置放大器的位置。设计算法确定把信号放大器放在何处，能使所用的放大器数目最少并且保证信号衰减不超过给定的容忍值。 2. 输入输出的要求输入为一棵二叉树，带有衰减值 d；输出为放置放大器的位置，那里放置，那里不放置，予以说明。 3. 测试数据测试数据为一课二叉树，如图 5 3 1 C A 1 2 E 2 D B 1 I 2 H 2 F J 图 5 网络分布示意图 2 G 2 K 此二叉树的扩展数按前序遍历存放在 bitree.txt 文件中。 ~ 1~

二、概要设计本程序使用的是二叉树结构，其结点数据源为结构体 Element 。 struct Element { string name; int D; int d; bool boost; friend ostream& operator<<(ostream&output,Element &element); //结点名字 // 该结点的衰减量 // 父结点的衰减量 //当且仅当本处设置放大器，则 boost 为 true }; struct BiNode { //二叉树的结点结构 Element data; BiNode *lchild, *rchild; }; ~ 2~

三、详细设计 1. 程序的入口和出口函数 int _tmain(int argc, _TCHAR* argv[]) { BiTree biTree; cout<<"计算结果如下："<>this->limit; CheckNum(this->limit); this->root = Creat( ); Init(root); this->SetBooster(root); } BiTree biTree( );为构造函数，其功能为构造二叉树此程序调用三个函数完成二叉树的构造（1） BiNode* BiTree::Creat( ) { //构造结点函数 BiNode* root; Element element; cout<<"请输入创建一棵二叉树的结点数据"<>element; if ("#"==element.name) root = NULL; else{ root = new BiNode; root->data=element; //生成一个结点 ~ 3~

root->lchild = Creat( ); root->rchild = Creat( ); //递归建立左子树 //递归建立右子树 } return root; } 此为重载函数 istream& operator>>(istream&input,Element &element) { cout<<"请输入结点名字\n"; input>>element.name; if("#"!=element.name) { cout<<"请输入父结点的衰减量\n"; input>>element.d; CheckNum(element.d); } return input; } （2）此函数初始化 D 值，叶子结点为 0，其余均为-1. void BiTree::Init(BiNode *root) { if(NULL!=root) { root->data.boost=false; if(NULL==root->lchild&&NULL==root->rchild) root->data.D=0; else { } } root->data.D=-1;//表示 D 值尚未计算 Init(root->lchild); Init(root->rchild); ~ 4~

} （3) 此函数运用递归计算 D 值，并设置放大器位置。 void BiTree::SetBooster(BiNode *root) { int D=0; if(NULL!=root->lchild) { if(-1==root->lchild->data.D) SetBooster(root->lchild); if(root->lchild->data.D+root->lchild->data.d>this->limit) { root->lchild->data.boost=true; D=root->lchild->data.d; } else D=root->lchild->data.D+root->lchild->data.d; } if(NULL!=root->rchild) { if(-1==root->rchild->data.D) SetBooster(root->rchild); if(root->rchild->data.D+root->rchild->data.d>this->limit) { root->rchild->data.boost=true; if(Drchild->data.d) { D=root->rchild->data.d; } } else if(Drchild->data.D+root->rchild->data.d) { D=root->rchild->data.D+root->rchild->data.d; } } ~ 5~

资料库

信号放大器.doc

相关推荐

课程资源

热门标签

最新资料