信号放大器.docx
- 文档编号:15838418
- 上传时间:2023-07-08
- 格式:DOCX
- 页数:20
- 大小:90.34KB
信号放大器.docx
《信号放大器.docx》由会员分享,可在线阅读,更多相关《信号放大器.docx(20页珍藏版)》请在冰点文库上搜索。
信号放大器
课程设计任务书
2010—2011学年第1学期
电子与信息工程系专业班级
课程设计名称:
数据结构课程设计
设计题目:
信号放大器
完成期限:
自2012年1月2日至2012年1月6日共1周
设计依据、要求及主要内容(可另加附页):
一、设计目的
熟悉各种数据结构和运算,会使用数据结构的基本操作解决一些实际问题。
二、设计要求
(1)重视课程设计环节,用严谨、科学和踏实的工作态度对待课程设计的每一项任务;
(2)按照课程设计的题目要求,独立地完成各项任务,严禁抄袭;凡发现抄袭,抄袭者与被抄袭者皆以零分计入本课程设计成绩。
凡发现实验报告或源程序雷同,涉及的全部人员皆以零分计入本课程设计成绩;
(3)学生在接受设计任务后,首先要按设计任务书的要求编写设计进程表;
(4)认真编写课程设计报告。
三、设计内容
1)问题描述
天然气经过管道网络从其生产基地输送到消耗地,在传输过程中,其性能的某一个或几个方面可能会有所衰减(例如气压)。
为了保证信号衰减不超过容忍值,应在网络中的合适位置放置放大器以增加信号(例如电压)使其与源端相同。
设计算法确定把信号放大器放在何处,能使所用的放大器数目最少并且保证信号衰减不超过给定的容忍值。
2)基本要求
(1)建立模型,设计数据结构;
(2)设计算法完成放大器的放置;
(3)分析算法的时间复杂度。
3)设计思想
为了简化问题,假设分布网络是二叉树结构,源端是树的根结点,信号从一个结点流向其孩子结点,树中的每一结点(除了根)表示一个可以用来放置放大器的位置。
图5是一个网络示意图,边上标出的是从父结点到子结点的信号衰减量。
对于网络中任一结点i,设d(i)表示结点i与其父结点间的衰减量,D(i)为从结点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.程序的功能
假设分布网络是二叉树结构,源端是树的根结点,信号从一个结点流向其孩子结点,树中的每一结点(除了根)表示一个可以用来放置放大器的位置。
设计算法确定把信号放大器放在何处,能使所用的放大器数目最少并且保证信号衰减不超过给定的容忍值。
2.输入输出的要求
输入为一棵二叉树,带有衰减值d;
输出为放置放大器的位置,那里放置,那里不放置,予以说明。
3.测试数据
测试数据为一课二叉树,如图5
此二叉树的扩展数按前序遍历存放在bitree.txt文件中。
二、概要设计
本程序使用的是二叉树结构,其结点数据源为结构体Element。
structElement
{
stringname;//结点名字
intD;//该结点的衰减量
intd;//父结点的衰减量
boolboost;//当且仅当本处设置放大器,则boost为true
friendostream&operator<<(ostream&output,Element&element);
};
structBiNode//二叉树的结点结构
{
Elementdata;
BiNode*lchild,*rchild;
};
三、详细设计
1.程序的入口和出口函数
int_tmain(intargc,_TCHAR*argv[])
{
BiTreebiTree;
cout<<"计算结果如下:
"< biTree.LeverOrder(); return0; } 2.核心函数 BiTree: : BiTree() { cout<<"请输入容忍值\n"; cin>>this->limit; CheckNum(this->limit); this->root=Creat(); Init(root); this->SetBooster(root); } BiTreebiTree();为构造函数,其功能为构造二叉树 此程序调用三个函数完成二叉树的构造 (1)BiNode*BiTree: : Creat()//构造结点函数 { BiNode*root; Elementelement; cout<<"请输入创建一棵二叉树的结点数据"< cin>>element; if("#"==element.name)root=NULL; else{ root=newBiNode;//生成一个结点 root->data=element; root->lchild=Creat();//递归建立左子树 root->rchild=Creat();//递归建立右子树 } returnroot; } 此为重载函数 istream&operator>>(istream&input,Element&element) { cout<<"请输入结点名字\n"; input>>element.name; if("#"! =element.name) { cout<<"请输入父结点的衰减量\n"; input>>element.d; CheckNum(element.d); } returninput; } (2)此函数初始化D值,叶子结点为0,其余均为-1. voidBiTree: : 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); } } } (3)此函数运用递归计算D值,并设置放大器位置。 voidBiTree: : SetBooster(BiNode*root) { intD=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(D { D=root->rchild->data.d; } } elseif(D { D=root->rchild->data.D+root->rchild->data.d; } } root->data.D=D; } BiTree: : ~BiTree(void) { Release(root); } 3.输出函数 biTree.LeverOrder();次序遍历函数,完成遍历并输出放置放大器位置 voidBiTree: : LeverOrder() { constintMaxSize=100; intfront=0; intrear=0;//采用顺序队列,并假定不会发生上溢 BiNode*Q[MaxSize]; BiNode*q; if(root==NULL)return; else{ Q[rear++]=root; while(front! =rear) { q=Q[front++]; cout< if(q->lchild! =NULL)Q[rear++]=q->lchild; if(q->rchild! =NULL)Q[rear++]=q->rchild; } } } 4.重载函数 ostream&operator<<(ostream&output,Element&element) 此函数为重载函数,为了输出放大器位置信息 ostream&operator<<(ostream&output,Element&element) { if(element.boost) output< else output< returnoutput; } 包括模块功能说明(如函数功能、入口及出口参数说明,函数调用关系描述等),每个模块的算法设计说明(可以是描述算法的流程图)。 源程序要按照写程序的规则来编写。 要结构清晰,重点函数的重点变量,重点功能部分要加上清晰的程序注释。 四、调试分析 1、测试数据为此二叉树,此树以按前序遍历写入文件中 2、测试输出的结果 3、时间复杂度分析 此程序的核心算法为设置放大器算法voidBiTree: : SetBooster(BiNode*root),此算法运用递归,时间和空间复杂性都很高。 五、核心源程序清单和执行结果 1.头文件 //声明类BiTree及定义结构BiNode,文件名为BiTree.h #ifndefBITREE_H #defineBITREE_H #include #include usingnamespacestd; voidCheckNum(int&num); structElement { stringname;//结点名字 intD;//该结点的衰减量 intd;//父结点的衰减量 boolboost;//当且仅当本处设置放大器,则boost为true friendostream&operator<<(ostream&output,Element&element); friendistream&operator>>(istream&input,Element&element); }; structBiNode//二叉树的结点结构 { Elementdata; BiNode*lchild,*rchild; }; classBiTree { public: BiTree(); ~BiTree();//析构函数,释放二叉链表中各结点的存储空间 voidLeverOrder();//层序遍历二叉树 private: BiNode*Creat(); voidRelease(BiNode*root);//析构函数调用 voidSetBooster(BiNode*root);//完成以root指向的结点为根结点的二叉树的放大器放置 voidInit(BiNode*root);//完成对所有结点D值的初始化 BiNode*root;//指向根结点的头指针 intlimit; }; #endif 2.各种子函数文件 #include"StdAfx.h" //定义类中的成员函数,文件名为BiTree.cpp #include #include #include"BiTree.h" usingnamespacestd; ostream&operator<<(ostream&output,Element&element) { if(element.boost) output< else output< returnoutput; } istream&operator>>(istream&input,Element&element) { cout<<"请输入结点名字\n"; input>>element.name; if("#"! =element.name) { cout<<"请输入父结点的衰减量\n"; input>>element.d; CheckNum(element.d); } returninput; } BiTree: : BiTree() { cout<<"请输入容忍值\n"; cin>>this->limit; CheckNum(this->limit); this->root=Creat(); Init(root); this->SetBooster(root); } BiTree: : ~BiTree() { Release(root); } voidBiTree: : LeverOrder() { constintMaxSize=100; intfront=0; intrear=0;//采用顺序队列,并假定不会发生上溢 BiNode*Q[MaxSize]; BiNode*q; if(root==NULL)return; else{ Q[rear++]=root; while(front! =rear) { q=Q[front++]; cout< if(q->lchild! =NULL)Q[rear++]=q->lchild; if(q->rchild! =NULL)Q[rear++]=q->rchild; } } } BiNode*BiTree: : Creat() { BiNode*root; Elementelement; cout<<"请输入创建一棵二叉树的结点数据"< cin>>element; if("#"==element.name)root=NULL; else{ root=newBiNode;//生成一个结点 root->data=element; root->lchild=Creat();//递归建立左子树 root->rchild=Creat();//递归建立右子树 } returnroot; } voidBiTree: : Release(BiNode*root) { if(root! =NULL){ Release(root->lchild);//释放左子树 Release(root->rchild);//释放右子树 deleteroot; } } voidBiTree: : SetBooster(BiNode*root) { intD=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(D { D=root->rchild->data.d; } } elseif(D { D=root->rchild->data.D+root->rchild->data.d; } } root->data.D=D; } voidBiTree: : 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); } } } voidCheckNum(int&num) { while(! cin) { cin.clear(); cin.sync(); cout<<"请输入数字\n"; cin>>num; } } 3.主程序文件 //SignalBooster.cpp: 定义控制台应用程序的入口点。 #include"stdafx.h" #include"BiTree.h" #include usingnamespacestd; int_tmain(intargc,_TCHAR*argv[]) { BiTreebiTree; cout<<"计算结果如下: "< biTree.LeverOrder(); return0; } 4.执行结果 六、心得体会 这次数据结构课程设计,我又不得不把已经遗忘的数据结构再看了一边,经过复习和设计,我又对数据结构有了深刻的认识,它果然很重要,涉及的方面也很广。 这次我这设计的是信号放大器,它在实际生活中的例子很多,比如电话网、输电网和石油传输网络,他们在传输过程中都会有不同程度的衰减,都需要放置一些放大器来增大信号,而怎样放置放大器,放置在何处,怎样放置能最少就是我要解决的问题。 程序虽然简单,但是很要特色,我设计的算法是递归,和经典算法棋盘覆盖很相似,都可以很好的算出预计值,并且可读性很强。 经过这次课程设计,虽然有点累,但是收获不少,我很高兴,以后要继续努力。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 信号 放大器