第一篇：北邮数据结构实验报告 单链表
北京邮电大学 数据结构试验报告
实验名称： 实验一
线性表 学生姓名：
班
级：
班内序号：
学
号：
日
期： 2014年1月3日
实验目的
熟悉C++语言的基本编程方法，掌握集成编译环境的调试方法 学习指针、模板类、异常处理的使用 掌握线性表的操作的实现方法 学习使用线性表解决实际问题的能力 实验内容
2.1题目1 根据线性表的抽象数据类型的定义，选择下面任一种链式结构实现线性表，并完成线性表的基本功能。
线性表存储结构（五选一）：
1、带头结点的单链表
2、不带头结点的单链表
3、循环链表
4、双链表
5、静态链表
线性表的基本功能：
1、构造：使用头插法、尾插法两种方法
2、插入：要求建立的链表按照关键字从小到大有序
3、删除
4、查找
5、获取链表长度
6、销毁
7、其他：可自行定义
编写测试main()函数测试线性表的正确性。程序分析
3.1 存储结构 单链表的存储结构：
3.2 关键算法分析
一、关键算法 1.头插法
自然语言描述：a.在堆中建立新结点
b.将a[i]写入到新结点的数据域
c.修改新结点的指针域
d.修改头结点的指针域,将新结点加入链表中 代码描述： template
front = new Node
}
} s->next = front->next;front->next = s;时间复杂度：O(n)
2.尾插法
自然语言描述：a.在堆中建立新结点
b.将a[i]写入到新结点的数据域
c.将新结点加入到链表中
d.修改修改尾指针 代码描述: template
front = new Node
}
} s->data = a[i];s->next = r->next;r->next= s;r=s;时间复杂度：O(n)
3.析构函数
自然语言描述：a.新建立一个指针，指向头结点
b.移动a中建立的指针
c.逐个释放指针
代码描述: template
Node
} } delete front;4.按位查找函数
自然语言描述: a.初始化工作指针p和计数器j，p指向第一个结点，j=1
b.循环以下操作，直到p为空或者j等于1
b1：p指向下一个结点
b2：j加1
c.若p为空，说明第i个元素不存在，抛出异常
d.否则，说明p指向的元素就是所查找的元素，返回元素地址
代码描述: template
Node
if(j } else break;p = p->next;j++; } if(!p)throw“查找位置非法”;else return p;} 时间复杂度：O(n) 5.按值查找函数 自然语言描述：a.初始化工作指针p和计数器j，p指向第一个结点，j=1 b.循环以下操作，找到这个元素或者p指向最后一个结点 b1.判断p指向的结点是不是要查找的值，如果是，返回j; b2.否则p指向下一个结点,并且j的值加一 c.如果找到最后一个结点还没有找到要查找的元素，返回查找失败信息 代码描述: template Node } return-1;if(p->data == x)return j;else { p = p->next; j++;} } 时间复杂度：O(n)6.插入函数 自然语言描述： a.在堆中建立新结点 b.将要插入的结点的数据写入到新结点的数据域 c.修改新结点的指针域 d.修改前一个指针的指针域，使其指向新插入的结点的位置 代码描述: template Node } else throw“插入位置非法”;Node 自然语言描述：a.从第一个结点开始，查找要删除的位数i前一个位置i-1的结点 b.设q指向第i个元素 c.将q元素从链表中删除 d.保存q元素的数据 e.释放q元素 代码描述: template T x=q->data; } p->next = q->next;delete q;return x; 8.遍历打印函数 自然语言描述: a.判断该链表是否为空链表，如果是，报错 b.如果不是空链表，新建立一个temp指针 c.将temp指针指向头结点 d.打印temp指针的data域 e.逐个往后移动temp指针，直到temp指针的指向的指针的next域为空 代码描述: template } Node } cout< 自然语言描述： a.判断该链表是否为空链表，如果是，输出长度0 b.如果不是空链表，新建立一个temp指针，初始化整形数n为0 c.将temp指针指向头结点 d.判断temp指针指向的结点的next域是否为空，如果不是，n加一，否则return n e.使temp指针逐个后移，重复d操作，直到temp指针指向的结点的next域为0，返回n 代码描述: template } Node } return i-1;p = p->next;i++;4 程序运行结果 4.1主函数流程图 4.2程序运行框图 实验心得 1.调试时出现的问题及解决的方法 在编写按值查找函数时，由于没有处理好指针类型的原因，导致指针无法正常返回，屡屡报错。最后意识到c++没有指针强制类型的转换机制，经过细致检查后才改正错误使得程序正常运行。2.心得体会 了解了单链表的基本的操作函数实现，对链式存储结构有了较好的认识 3.下一步的改进 可以增加完善报错机制，增强程序的健壮性 完整源代码 #include template }; template }; //template Node template } template } template } front = p;p = p->next;delete front;front = new Node } Node } Node } Node } cout< template } template } Node } return-1;if(p->data == x)return j;else { } p = p->next; j++;Node } if(!p)throw“查找位置非法”;else return p;if(j } else break;p = p->next;j++; template } template } template } void main(){ Node } return i-1;p = p->next;i++;Node } else throw“插入位置非法”;Node T x=q->data; } int n;cout<<“将要输入的链表长度为：”;cin>>n;int *b=new int[n];cout<<“输入链表中的元素：”;for(int k=0;k 北京邮电大学 数据结构试验报告 实验名称： 实验四 排序 学生姓名： 班 级： 班内序号： 学 号： 日 期： 2014年1月4日 实验目的 学习、实现、对比各种排序算法，掌握各种排序算法的优劣，以及各种算法使用的情况。实验内容 2.1 题目1 使用简单数组实现下面各种排序算法，并进行比较。排序算法： 1、插入排序 2、希尔排序 3、冒泡排序 4、快速排序 5、简单选择排序 6、堆排序（选作） 7、归并排序（选作） 8、基数排序（选作） 9、其他 要求： 1、测试数据分成三类：正序、逆序、随机数据 2、对于这三类数据，比较上述排序算法中关键字的比较次数和移动次数（其中关键字交换计为3次移动）。 3、对于这三类数据，比较上述排序算法中不同算法的执行时间，精确到微秒（选作） 4、对2和3的结果进行分析，验证上述各种算法的时间复杂度 编写测试main()函数测试线性表的正确性。程序分析 3.1 存储结构 顺序存储结构——数组 3.2 关键算法分析 1.插入排序：依次将待排序的序列中的每一个记录插入到先前排序好的序列中，直到全部记录排序完毕 void Insertsort(int r[],int n,int* compare,int* move)//插入排序 { *compare=0;*move=0;int i;int j;for(i=1;i (*compare)++; (*move)++; r[j+1]=r[j];} if(j>=0)(*compare)++;r[j+1]=x;} } 2.希尔排序：先将整个序列分割成若干个子列，分别在各个子列中运用直接插入排序，待整个序列基本有序时，再对全体记录进行一次直接插入排序 void ShellInsert(int r[],int n,int* compare,int* move)//希尔排序 { *compare=0;*move=0;int j;10 9 12 12 20 20 31 for(int d=n/2;d>=1;d=d/2)//间距越来越小 { for(int i=d;i<=n-1;i++)//从a[d]往后逐个元素确定是否需要前移 { if(r[i] { int x=r[i]; for(j=i-d;(j>=0)&&(x { (*compare)++; (*move)++; r[j+d]=r[j]; } if(j>=0)(*compare)++; r[j+d]=x;} else(*compare)++;} } } 3.冒泡排序：两两比较相邻记录的关键码，如果反序则交换，直到没有反序记录为止 void Bubblesort(int r[],int n,int* compare,int* move)//交换（冒泡）排序 { *compare=0;*move=0;int x;for(int j=0;j for(int i=n-1;i>j;i--) { if(r[i] { (*compare)++; (*move)+=3; x=r[i]; r[i]=r[i-1]; r[i-1]=x; } else(*compare)++; } } } 4.快速排序：首先选择一个基准，将记录分割为两部分，左支小于或等于基准，右支则大于基准，然后对两部分重复上述过程，直至整个序列排序完成 int Partion(int r[],int first,int end,int* compare,int* move)//快速排序中的轴定位 { int i=first;int j=end;int zhou=r[i];//默认第一个元素为轴 while(i { (*compare)++; j--;} if(i r[i]=r[j];//发现轴右侧的某数比轴值小，将其前置 } while((i (*compare)++; (*move)++; r[j]=r[i];//发现轴左侧的某数比轴值小，将其后置 } } r[i]=zhou;//最后确定轴的位置 return i;} void Qsort(int r[],int i,int j,int* compare,int* move)//快速排序 { if(i int min=i; for(int j=i+1;j { (*compare)++; if(r[j] min=j;//记录下当前找到的最小值的位置 } if(min!=i) {(*move)+=3; int Min; Min=r[min]; r[min]=r[i]; r[i]=Min; } } } 程序运行结果 4.1主函数流程图 4.2程序运行框图 实验心得 1.调试时出现的问题及解决的方法 在初期构思代码的时候，首先构造了各种算法的基本实现代码，封装成类，已经能够实现七种排序的基本功能，并且测试无误。 之后考虑如何能简化代码以实现多达七种排序算法的简单调用、乱序和顺序以及逆序数据的分别排序和性能指标统计（算法移动次数和比较次数的精确统计）。2.心得体会 程序的优化是一个艰辛的过程，如果只是实现一般的功能，将变得容易很多，当加上优化，不论是效率还是结构优化，都需要精心设计。3.改进 本程序代码设计时运用了递归的调用方式，效率还可以通过将其转换为栈模拟的方式得以提高。另外还可以进一步考虑算法时间的精确统计，以便从时间角度比较这几种排序算法的优劣。 完整源代码 #include void Insertsort(int r[],int n,int* compare,int* move);void ShellInsert(int r[],int n,int* compare,int* move);void Bubblesort(int r[],int n,int* compare,int* move);int Partion(int r[],int first,int end,int* compare,int* move);void Qsort(int r[],int i,int j,int* compare,int* move);void Selectsort(int r[],int n,int* compare,int* move); void Insertsort(int r[],int n,int* compare,int* move)//插入排序 { *compare=0; { } } void ShellInsert(int r[],int n,int* compare,int* move)//希尔排序 { int x=r[i];for(j=i-1;x } if(j>=0)(*compare)++;r[j+1]=x;(*move)++;r[j+1]=r[j];*move=0;int i;int j;for(i=1;i (*compare)++; *compare=0; { for(int i=d;i<=n-1;i++)//从a[d]往后逐个元素确定是否需要前移 { } } } void Bubblesort(int r[],int n,int* compare,int* move)//交换（冒泡）排序 { { for(int i=n-1;i>j;i--) { if(r[i] { (*compare)++; (*move)+=3;*compare=0;*move=0;int x;if(r[i] int x=r[i]; for(j=i-d;(j>=0)&&(x }(*compare)++;(*compare)++;(*move)++;r[j+d]=r[j];*move=0;int j;for(int d=n/2;d>=1;d=d/2)//间距越来越小 if(j>=0) r[j+d]=x;} else(*compare)++;for(int j=0;j x=r[i]; r[i]=r[i-1]; r[i-1]=x; } } else(*compare)++; } } int Partion(int r[],int first,int end,int* compare,int* move)//快速排序中的轴定位 { int i=first;int j=end;int zhou=r[i];//默认第一个元素为轴 while(i { } if(i } if(i r[i]=r[j];//发现轴右侧的某数比轴值小，将其前置 (*move)++; r[j]=r[i];//发现轴左侧的某数比轴值小，将其后置 } } r[i]=zhou;//最后确定轴的位置 return i;} void Qsort(int r[],int i,int j,int* compare,int* move)//快速排序 { if(i void Selectsort(int r[],int n,int* compare,int* move)//选择排序 { { int min=i; for(int j=i+1;j { (*compare)++; if(r[j] min=j;//记录下当前找到的最小值的位置 } if(min!=i) {(*move)+=3; int Min; Min=r[min]; r[min]=r[i]; r[i]=Min; } } } void main(){ int i;int compare=0;int move=0;cout<<“请您先输入一个正序数组哦”< cout<<“再输入一个逆序数组~~~”< cout<<“最后输入一个乱序数组~~~”< 西华大学数计学院学生上机实践报告 西华数学与计算机学院上机实践报告 课程名称：数据结构 指导教师：唐剑梅 上机实践名称： 上机实践编号：1 年级： 2011 姓名：蒋俊 学 号 ： *** 上机实践成绩： 上机实践日期：2012-11-6 上机实践时间：8:00-9:30 一、实验目的 1.了解线性表的逻辑结构特性，以及这种特性在计算机内的两种存储结构。 2.重点是线性表的基本操作在两种存储结构上的实现；其中以链表的操作为侧重点；并进一步学习程序设计方法。 3.掌握栈这种数据结构特性及其主要存储结构，并能在现实生活中灵活运用。 4.掌握队列这种数据结构特性及其主要存储结构，并能在现实生活中灵活运用。 5.了解和掌握递归程序设计的基本原理和方法。 6.掌握使用 C++面向对象的程序设计技术设计数据结构源程序的方法。 二、实验内容 1.熟悉前面的【程序示例2】，按照约瑟夫问题的方法2，试着不设头结点改写原来的程序，上机调试运行。 2.用链表建立通讯录。通讯录内容有：姓名、通讯地址、电话号码。 要求：（1）通讯录按姓名项的字母顺序排列； （2）能查找通讯录中某人的信息； [提示] 用链表来存放这个通讯录，一个人的信息作为一个结点。成链的过程可以这样考虑：先把头结点后面的 西华大学数计学院学生上机实践报告 char name[20]; // 姓名子域 NodeType *next; // 指针域 };class Jose //类声明 { private: NodeType *Head; public: Jose(){}; ~Jose(){ }; void creat(); void outs(); };void Jose::creat(){ int i=0, n; NodeType *newp, *pre; cout<<“n 输入总人数 n=”;cin>>n; pre=new NodeType; Head=new NodeType; pre->num=1; cout<<“n 编号”<<1<<“的人 姓名=”; cin>>pre->name; cout<<“n 密码”<<1<<“的人 密码=”; cin>>pre->psw; Head=pre; Head->next=Head; for(i=1;i { newp=new NodeType; newp->num=i+1; cout<<“n 编号”< 姓名=”;cin>>newp->name; cout<<“n 密码”< 密码=”; cin>>newp->psw; newp->next=Head; pre->next=newp; pre=newp; } } void Jose::outs() { int m,i; NodeType *q=Head, *p; cout<<“n 输入m值(m>=2)”;cin>>m; cout<<“n 根据m值，开始报数输出：”< while(q->next!=q) 西华大学数计学院学生上机实践报告 { for(i=1;i cout<<“编号为：”< cout<<“n 编号为:”< m=q->psw; p->next=q->next;delete q; q=p->next; } cout<<“编号为：”< cout<<“n 编号为:”< delete q;} int main() { Jose h; h.creat(); h.outs(); return 0;} 西华大学数计学院学生上机实践报告 { char Add[20]; char name[20]; char tel[20]; };struct NodeType { ElemType data; NodeType *next;};class Sqlist { private: NodeType *Head; public: Sqlist(); ~Sqlist(); void creat(); void Insert(ElemType x); void Delet(ElemType x); void PrintOut(); };Sqlist::Sqlist(){ Head=new NodeType;Head->next=NULL;strcpy(Head->data.name,“姓名”);strcpy(Head->data.Add,“地址”);strcpy(Head->data.tel,“电话号码”);} Sqlist::~Sqlist(){ NodeType *p=Head->next; while(p!=NULL) {Head->next=p->next; delete p; p=Head->next;} } void Sqlist::creat() //初步建立一个通讯录 { NodeType*p,*s,*q;ElemType x; 西华大学数计学院学生上机实践报告 int a;q=Head;cout<<“n 输入姓名：”;cin>>x.name;cout<<“n 输入通讯地址：”;cin>>x.Add;cout<<“n 输入电话号码：”;cin>>x.tel;p=new NodeType;p->data=x;Head->next=p;p->next=NULL;cout<<“输入一个数。若为-1，结束输入:”< while(a!=-1){ cout<<“n 输入姓名：”;cin>>x.name;cout<<“n 输入通讯地址：”;cin>>x.Add;cout<<“n 输入电话号码：=”;cin>>x.tel;s=new NodeType;s->data=x;if(strcmp(s->data.name,p->data.name)>0){ p->next=s;s->next=NULL; p=s;} else{ s->next=p;q->next=s;} q=q->next; cout<<“输入一个数。若为-1，结束输入:”< 西华大学数计学院学生上机实践报告 s->data=x;q=Head;p=q->next;while(p!=NULL&&strcmp(p->data.name,x.name)<0){q=p;p=p->next;} s->next=p;q->next=s;} void Sqlist::Delet(ElemType x)//删除 { NodeType *p,*q;q=Head;p=Head->next;while(p!=NULL&&strcmp(p->data.name,x.name)!=0){q=p;p=p->next;} if(p!=NULL){ q->next=p->next;delete p;cout<<“删除结点成功”< { NodeType *p;p=Head->next;while(p!=NULL){ cout< data.name<<“ ”;cout< data.tel<<“ ”;cout< data.Add<<“ ”;p=p->next;} cout< Sqlist as; cout<<“n 通讯录演示”; do{ cout<<“nn”; cout<<“nn 1.初步建立一个通讯录（单链表） ”; 西华大学数计学院学生上机实践报告 cout<<“nn 2.插入新的电话记录 ”; cout<<“nn 3.删除一个电话记录”; cout<<“nn 4.结束程序”; cout<<“n******************************** ”; cout<<“n 请输入你的选择(1,2,3,4)”;cin>>k;switch(k){ case 1:{ as.creat();as.PrintOut();}break; case 2:{ cout<<“n 插入的数据 姓名”;cin>>e.name; cout<<“n 插入的数据 电话号”;cin>>e.tel; cout<<“n 插入的数据 地址”;cin>>e.Add; as.Insert(e);as.PrintOut(); }break; case 3:{ cout<<“n 被删除的姓名= ”; cin>>e.name; as.Delet(e); as.PrintOut(); }break; default:break; } }while(k>=1&&k<4); cout<<“n 再见!”; return 0;} 西华大学数计学院学生上机实践报告 西华大学数计学院学生上机实践报告 西华大学数计学院学生上机实践报告 const int MAXSIZE=100; // 数组的容量 class SqStack { private: ElemType elem[MAXSIZE]; int top; public: SqStack(); ~SqStack(){}; void SqStack::push(ElemType e); ElemType SqStack::pop(); void SqStack::PrintOut(); int SqStack::IsEmpty(); void f(ElemType N,ElemType M);};void SqStack::f(ElemType N,ElemType M){ SqStack s; ElemType e;while(N){ s.push(N%M); N=N/M;} while(!s.IsEmpty()){ e=s.pop(); if(e>=10) { e=e%10; switch(e) { case 1:cout<<“b”< case 2:cout<<“c”< case 3:cout<<“d”< case 4:cout<<“e”< case 5:cout<<“f”< default:cout<<“a”< } } else cout< 西华大学数计学院学生上机实践报告 } cout< {cout<<“栈满溢出”< return; } else{top++; elem[top]=e;} } ElemType SqStack::pop(){ElemType x; if(top==0) { cout<< “ 栈为空，不能出栈操作”< else { x=elem[top]; top--; return x;} } void SqStack::PrintOut() {int k; cout<<“n PrintOut Data:n”; for(k=top;k>=1;k--)cout< cout< else return 0;} void main(){ ElemType a,m;cout<<“请输入一个正整数:”< 西华大学数计学院学生上机实践报告 五、总结 通过本次实验，我熟悉了链表的操作，了解了线性表在现实生活中的运用，认识了顺序存储和链式存储这两种结构。本次上机实践基本完成了实验内容，但完成的不是很好，以后需要更加努力地掌握基本的知识。实验内容对于队列的运用没有涉及，希望以后有所涉及。 西华大学数计学院学生上机实践报告 北京邮电大学操作系统实验实验报告 班号：2011211314姓名：oneseven学号： 实验日期： 2013.12.16 实验名称： 操作系统实验 一、实验目的 通过模拟实现内存分配的伙伴算法和请求页式存储管理的几种基本页面置换算法，了解存储技术的特点。掌握虚拟存储请求页式存储管理中几种基本页面置换算法的基本思想和实现过程，并比较它们的效率。 二、实验内容 1.实现一个内存管理的伙伴算法，实现内存块申请时的分配和释放后的回收。 实验准备 用随机函数仿真进程进行内存申请，并且以较为随机的次序进行释放。对其碎片进行统计，当申请分配内存失败时区分实际空间不足和由于碎片而不能满足。 2.设计一个虚拟存储区和内存工作区，并使用下述算法计算访问命中率。 1)最佳置换算法（Optimal） 2)先进先出法（Fisrt In First Out） 3)最近最久未使用（Least Recently Used）4)最不经常使用法（Least Frequently Used） 其中，命中率＝１－页面失效次数／页地址流长度。试对上述算法的性能加以较各：页面个数和命中率间的关系；同样情况下的命中率比较。 实验准备 本实验中主要的流程：首先用srand()和rand()函数定义和产生指令序列，然后将指令序列变换成相应的页地址流，并针对不同的算法计算出相应的命中率。 实验可先从一个具体的例子出发。 (1)通过随机数产生一个指令序列，共2048条指令。指令的地址按下述原则生成： A：50%的指令是顺序执行的 B：25%的指令是均匀分布在前地址部分 C：25%的指令是均匀分布在后地址部分 具体的实施方法是： A：在[0，1023]的指令地址之间随机选取一起点m B：顺序执行一条指令，即执行地址为m+1的指令 C：在前地址[0,m+1]中随机选取一条指令并执行，该指令的地址为m’ D：顺序执行一条指令，其地址为m’+1 E：在后地址[m’+2，2047]中随机选取一条指令并执行 F：重复步骤A-E，直到2048次指令(2)将指令序列变换为页地址流 设：页面大小为4K； 用户内存容量4页到32页； 用户虚存容量为32K。 在用户虚存中，按每K存放64条指令排列虚存地址，即2048条指令在虚存中的存放方式为： 第 0 条-第 63 条指令为第0页（对应虚存地址为[0，63]）第64条-第127条指令为第1页（对应虚存地址为[64，127]） ……………………………… －1－ 第1984条-第2047条指令为第31页（对应虚存地址为[1984，2047]）按以上方式，用户指令可组成32页。 以此为基础，给出较为一般的情形：仿真内存容量和虚存容量参数变化时的情形。 3.实现内存的slab分配器： 其基本思想是：一次向内核获取整数页，slab根据数据结构的大小进行划分为一个个小的数据结构，当需要时直接从该链表上摘取一个返回应用程序，当应用程序释放时，而非真正释放，只需要该空间放回到链表中，当分散的一页多块又聚集一页时，又会拼成一页，同时判断slab空闲的页数，如果空闲页超过一定的页数，就会向系统释放一定的页数。一个slab分配器只能管理一个指定大小的数据结构分配。 三、项目要求及分析 3.1实现一个内存管理的伙伴算法，实现内存块申请时的分配和释放后的回收。假设系统的可利用内存空间容量为2m个字(地址从0到2m-1)，则在开始运行时，整个内存区是一个大小为2m的空闲块，在运行了一段时间之后，被分隔成若干占用块和空闲块。为了在分配时查找方便起见，我们将所有大小相同的空闲块建于一张子表中。每个子表是一个双重链表，这样的链表可能有m+1个，将这m+1个表头指针用向量结构组织成一个表，这就是伙伴系统中的可利用空间表，如图所示： 分配算法： 当用户提出大小为n的内存请求时，首先在可利用表上寻找结点大小与n相匹配的子表，若此子表非空，则将子表中任意一个结点分配之即可；若此子表为空，则需从结点更大的非空子表中去查找，直至找到一个空闲块，则将其中一部分分配给用户，而将剩余部分插入相应的子表中。 若2k-1 < n ≤ 2k-1，又第k+1个子表不空，则只要删除此链表中第一个结点并分配给用户即可；若 2k-2 < n ≤ 2k-1-1，此时由于结点大小为2k-1 的子表为空，则需从结点大小为2k 的子表中取出一块，将其中一半分配给用户，剩余的一半作为一个新结点插入在结点大小为2k-1的子表中，若2k-i-1 < n ≤ 2k-i-1(i为小于是的整数)，并且所有结点小于2k的子表均为空，则同样需从结点大小为2k的子表中取出一块，将其中2k-i的一小部分分配给用户，剩余部分分割成若干个结点分别插入在结点大小为2k-1、2k- 2、…、2k-i的子表中。回收算法： 在用户释放不再使用的占用块时，系统需将这新的空闲块插入到可利用空间表中去。这里，同样有一个地址相邻的空闲块归并成大块的问题。但是在伙伴系统中仅考虑互为“伙伴”的两个空闲块的归并。 何谓“伙伴”?如前所述，在分配时经常需要将一个大的空闲块分裂成两个大小相等的存 －2－ 储区，这两个由同一大块分裂出来的小块就称之“互为伙伴”。例如：假设p为大小为pow(2,k)的空闲块的初始地址，且p MOD pow(2,k+1)=0，则初始地址为p和p+pow(2,k)的两个空闲块互为伙伴。在伙伴系统中回收空闲块时，只当其伙伴为空闲块时才归并成大块。也就是说，若有两个空闲块，即使大小相同且地址相邻，但不是由同一大块分裂出来的，也不归并在一起。 由此，在回收空闲块时，应首先判别其伙伴是否为空闲块，若否，则只要将释放的空闲块简单插入在相应子表中即可；若是，则需在相应子表中找到其伙伴并删除之，然后再判别合并后的空闲块的伙伴是否是空闲块。依此重复，直到归并所得空闲块的伙伴不是空闲块时，再插入到相应的子表中去。 3.2.设计一个虚拟存储区和内存工作区，并使用下述算法计算访问命中率。 页式虚拟存储器实现的一个难点是设计页面调度（置换）算法，即将新页面调入内存时，如果内存中所有的物理页都已经分配出去，就要按某种策略来废弃某个页面，将其所占据的物理页释放出来，供新页面使用。页面替换算法主要用于如下几个地方： (1)虚拟存储器中，主存页面（或程序段）的替换。 (2)Cache中的块替换。 (3)虚拟存储器的快慢表中，快表的替换。 (4)虚拟存储器中，用户基地址寄存器的替换。 在虚拟存储器中常用的页面替换算法有如下几种： (1)最优替换算法，即OPT算法（OPTimal replacement algorithm）。上面介绍的几种页面替换算法主要是以主存储器中页面调度情况的历史信息为依据的，它假设将来主存储器中的页面调度情况与过去一段时间内主存储器中的页面调度情况是相同的。显然，这种假设不总是正确的。最好的算法应该是选择将来最久不被访问的页面作为被替换的页面，这种替换算法的命中率一定是最高的，它就是最优替换算法。 要实现OPT算法，唯一的办法是让程序先执行一遍，记录下实际的页地址流情况。根据这个页地址流才能找出当前要被替换的页面。显然，这样做是不现实的。因此，OPT算法只是一种理想化的算法，然而，它也是一种很有用的算法。实际上，经常把这种算法用来作为评价其它页面替换算法好坏的标准。在其它条件相同的情况下，哪一种页面替换算法的命中率与OPT算法最接近，那么，它就是一种比较好的页面替换算法。(2)先进先出算法，即FIFO算法（First-In First-Out algorithm）。这种算法选择最先调入主存储器的页面作为被替换的页面。它的优点是比较容易实现，能够利用主存储器中页面调度情况的历史信息，但是，没有反映程序的局部性。因为最先调入主存的页面，很可能也是经常要使用的页面。 (3)最久没有使用算法，即LRU算法（Least Recently Used algorithm）。这种算法把近期最久没有被访问过的页面作为被替换的页面。它把LFU算法中要记录数量上的“多”与“少”简化成判断“有”与“无”，因此，实现起来比较容易。 (4)近期最少使用算法，即LFU算法（Least Frequently Used algorithm）。这种算法选择近期最少访问的页面作为被替换的页面。显然，这是一种非常合理的算法，因为到目前为止最少使用的页面，很可能也是将来最少访问的页面。该算法既充分利用了主存中页面调度情况的历史信息，又正确反映了程序的局部性。但是，这种算法实现起来非常困难，它要为每个页面设置一个很长的计数器，并且要选择一个固定的时钟为每个计数器定时计数。在选择被替换页面时，要从所有计数器中找出一个计数值最大的计数器。因此，通常采用如下一种相 －3－ 对比较简单的方法。 3.3实现内存的slab分配器 slab描述符和空闲对象管理部分成为 slab的管理部分，也可以称为slab头 slab的头可以放在slab自身，也可以放在 slab 之外。如果slab头放在了slab 之外，那么用户申请obj时，需要首先访问 slab头，slab头提供未使用free obj的指针 然后再访问这个free obj的地址。完成这项工作需要访问2个页块。会带来效率上的损失。slab头始终位于slab 也存在问题，比如一个页面只有4K，objsize = 2K，那么slab 头在slab 上，就意味着，这个4K的页面只能够分配一个obj。造成了内存的浪费。 如果 页数太少，存放的 obj个数少，那么 增加管理开销，同时 内存使用率低，如果页数太多对伙伴内存系统不好，所以需要一定的策略妥协。 这个妥协过程是有calculate_slab_order 这个函数来实现的。从 0阶（即一页）到kmalloc的最高阶 KMALLOC_MAX_ORDER，挨个尝试，由cache_estimate这个函数计算 如果选用order 阶，那么能分配 多少个 obj（num），剩余空间是多少（remainder）。所谓剩余空间，就是除去slab头（如果有的话），除去 obj*num，剩下的边角料空间是多少。需要分成两种情况去计算，分成两种情况的原因，很快就能看到 A)slab头不在slab上，即 flag & CFLGS_OFF_SLAB == 1的时候 这种情况比较简单，由于管理数据完全不在slab 上，size_tslab_size = PAGE_SIZE < 换句话，slab头的大小取决于obj的个数，obj的个数取决于 slab头的大小，四、具体实现 4.1实现一个内存管理的伙伴算法，实现内存块申请时的分配和释放后的回收。 程序： #include #define MIN_MOMORY_SIZE 536870912 //随机产生的最小内存空间 #define WORKTIME 1500 //系统工作时间 #define MAX_REQ_SIZE 268435456 //申请空闲内存分配的最大容量：256M #define MIN_DUE 30 //使用内存块的最短时间 #define MAX_DUE 90 //使用内存块的最长时间 #define OCCUPY_INTERVAL 60 //每次分配的最大间隔 #define USED 1 //内存块被使用 #define UNUSED 0 //内存块未被使用 //内存块链表结点结构 typedefstructbuddy_node { int flag; //标记空间是否被使用 －4－ int base; //本块儿内存的基地址 int occupy; //实际使用空间大小 int fragment; //碎片大小 intduetime; //使用时间 structbuddy_node *nextPtr; //指向下一个结点 } Buddy, *BuddyPtr; IndexTable table[INDEX_SIZE];//使用哈希表管理伙伴系统 int ready = 0; //需要分配内存的时刻 intavailSpace; //可分配空间大小 inttotalFragment = 0; //总碎片大小 //函数：添加结点（形参为内存块结点的信息） void insert_node(inti, intinbase, int f, intocc, int frag, int d){ BuddyPtrnewnodePtr = NULL, prePtr = NULL, curPtr = NULL; newnodePtr =(BuddyPtr)malloc(sizeof(Buddy));//分配结点 newnodePtr->base = inbase;newnodePtr->flag = f;newnodePtr->occupy = occ;newnodePtr->fragment = frag;newnodePtr->duetime = d;newnodePtr->nextPtr = NULL; if(table[i].headPtr == NULL) table[i].headPtr = newnodePtr; else { curPtr = table[i].headPtr;prePtr = NULL; //按地址顺序插入内存块 while(curPtr&&curPtr->base } if(prePtr == NULL){ //插在最前 newnodePtr->nextPtr = curPtr; table[i].headPtr = newnodePtr; } else if(curPtr == NULL){ //插在最后 prePtr->nextPtr = newnodePtr; } else { //插在中间 prePtr->nextPtr = newnodePtr;newnodePtr->nextPtr = curPtr; －5－ } } } //函数：删除结点 intdelete_node(inti, BuddyPtrdelPtr){ BuddyPtrprePtr = NULL, curPtr = NULL;intbasehold = delPtr->base; curPtr = table[i].headPtr; while(curPtr!= delPtr){ //寻找要删除的结点的位置 prePtr = curPtr;curPtr = curPtr->nextPtr; } if(prePtr == NULL) //要删除的结点在最前 table[i].headPtr = curPtr->nextPtr; else //要删除的结点不在链表的最前 prePtr->nextPtr = curPtr->nextPtr; free(curPtr); //释放结点 return basehold; //返回删除的内存块结点的基地址 } //函数：伙伴系统的分配算法 void buddy_allocate(inttime_slice){ inti, j, size, due;int state = 0; //分配状态：0为未分配，1为已分配 intinbase, basehold;BuddyPtrcurPtr = NULL; if(ready == time_slice){ //到达分配内存的时刻 printf(“Time %d:”, time_slice); size = 1 + rand()% MAX_REQ_SIZE; //申请使用内存的大小 due = MIN_DUE + rand()%(MAX_DUEsize;curPtr->duetime = due + ready; //修改可系统分配空间和碎片大小 availSpace-= table[i].nodesize;totalFragment += curPtr->fragment; state = 1;//标记已分配 break; } //空闲块的大小刚大于申请大小的2倍 else { basehold = delete_node(i, curPtr);//删除较大的空闲块并保留其基地址 inbase = basehold + table[i].nodesize; j = i; //分割空闲块 do { j--;inbase-= table[j].nodesize; //设置要添加内存块结点的基地址 insert_node(j, inbase, UNUSED, 0, 0, 0);//添加较小的空闲块 printf(“A block cut takes placen”); } while(table[j].nodesize / size > 1); //分配 insert_node(j, basehold, USED, size, table[j].nodesizesize; state = 1;//标记已分配 } } //块被占用，查看下一结点 else curPtr = curPtr->nextPtr; } } } printf(“Allocated %d,Fragment %d,Due %dn”, size, totalFragment, ready+due); －7－ } else if((availSpace< size)&&((availSpace + totalFragment)>= size))printf(“Allocation failed because of fragment!n”); else printf(“Allocation failed because of no enough unused space!n”); ready +=(1 + rand()% OCCUPY_INTERVAL);//下次需要分配内存的时刻 } } //函数：伙伴系统的回收算法 void buddy_retrieve(inttime_slice){ inti, basehold, dif;int f = 0;intModnext=0;BuddyPtrcurPtr = NULL, todelPtr = NULL; //依次查找，并回收需要回收的块 for(i = 0;i< INDEX_SIZE;i ++){ if(table[i].headPtr){ curPtr = table[i].headPtr; while(curPtr){ if((curPtr->flag == USED)&&(curPtr->duetime == time_slice)){//需要回收 //修改可系统分配空间和碎片大小 availSpace += table[i].nodesize;totalFragment-= curPtr->fragment; //回收为空闲块 curPtr->flag = UNUSED;curPtr->occupy = 0;curPtr->fragment = 0;curPtr->duetime = 0;printf(“Time %d:Retrieve %d,Fragment %dn”, time_slice, table[i].nodesize, totalFragment); } curPtr = curPtr->nextPtr; } } } //合并空闲块 for(i = 0;i< INDEX_SIZE;i ++){ if(table[i].headPtr){ －8－ curPtr = table[i].headPtr; while(curPtr&&curPtr->nextPtr){ //将地址连续且都为空闲的块合并后加入下一级的链表中 if(curPtr->flag == UNUSED &&(curPtr->nextPtr)->flag == UNUSED){ dif =(curPtr->nextPtr)->base-curPtr->base; Modnext =((int)(curPtr->nextPtr->base))%(2*table[i].nodesize); if((dif == table[i].nodesize)&&(Modnext==0)){ //删除两个结点 todelPtr = curPtr;curPtr = curPtr->nextPtr;basehold = delete_node(i, todelPtr);todelPtr = curPtr;curPtr = curPtr->nextPtr;delete_node(i, todelPtr);insert_node(i+1, basehold, UNUSED, 0, 0, 0);//添加合并后的结点 printf(“Two blocks mergen”); } else curPtr = curPtr->nextPtr; } else curPtr = curPtr->nextPtr; } } } } //函数：伙伴系统的处理过程 void buddy_system(void){ inttime_slice = 0; //在每个时间片内使用分配算法和回收算法 for(;time_slice< WORKTIME;time_slice ++){ buddy_allocate(time_slice); //分配算法 buddy_retrieve(time_slice); //回收算法 } } int main(intargc, char *argv[]){ intmemory_size; －9－ ini_index(); //初始化哈希索引表 srand(time(NULL)); //设置随机数种子 //随机产生需要管理的内存大小：512M ~ 1G memory_size = MIN_MOMORY_SIZE + rand()% MIN_MOMORY_SIZE;printf(“The size of memory is:%dn”, memory_size); int_system(memory_size); //初始化伙伴系统 buddy_system(); //伙伴系统的处理过程 printf(“Time %d:System execution stops and the spaces are all freed.n”, WORKTIME); free_system(); //释放所有结点 system(“pause”); return 0;} 4．2.设计一个虚拟存储区和内存工作区，并使用下述算法计算访问命中率。程序： #include //虚页长 #define clear_period 50 //清零周期 typedefstruct { intpn; //页号 intpfn; // 面号 int counter; // 一个周期内访问该页面的次数 int time; // time为访问时间 }pl_type;pl_typepl[total_vp];//页面结构数组 structpfc_struct{ //页面控制结构 intpn,pfn;structpfc_struct *next;};typedefstructpfc_structpfc_type; －10－ pfc_typepfc[total_vp],*freepf_head,*busypf_head,*busypf_tail;intdiseffect,a[total_instruction];int page[total_instruction], offset[total_instruction];/* Name: void Lprintf(void) Achieve: 格式控制 */ void Lprintf(void){ inti,j;printf(“|”); for(i = 1;i<=6;i++) { for(j = 1;j<=9;j++)printf(“-”); if(i!=6)printf(“+”); } printf(“|n”); } /* Name: void initialize(inttotal_pf) Achieve:初始化相关数据结构 */ void initialize(inttotal_pf){ inti;diseffect=0; for(i=0;i { pl[i].pn=i;pl[i].pfn=INVALID; //置页面控制结构中的页号，页面为空 pl[i].counter=0;pl[i].time=-1;//页面控制结构中的访问次数为0，时间为-1 } for(i=1;i { pfc[i-1 ].next=&pfc[i];pfc[i-1].pfn=i-1;//建立pfc[i-1]和pfc[i]之间的连接 } pfc[total_pf-1].next=NUL;pfc[total_pf-1].pfn=total_pf-1; freepf_head=&pfc[0]; //页面队列的头指针为pfc[0] } /* －11－ Name:void FIFO(inttotal_pf) Achieve:先进先出法（Fisrt In First Out）*/ void FIFO(inttotal_pf){ inti,j;pfc_type *p;//中间变量 initialize(total_pf);//初始化相关页面控制用数据结构 busypf_head=busypf_tail=NULL;//忙页面队列头，队列尾链接 for(i=0;i if(pl[page[i]].pfn==INVALID) //页面失效 { diseffect+=1;//失效次数 if(freepf_head==NULL)//无空闲页面 { p=busypf_head->next; pl[busypf_head->pn].pfn=INVALID; freepf_head=busypf_head;//释放忙页面队列的第一个页面 freepf_head->next=NULL;//表明还是缺页*/ busypf_head=p; } p=freepf_head->next; freepf_head->pn=page[i]; pl[page[i]].pfn=freepf_head->pfn; freepf_head->next=NULL;//使busy的尾为null if(busypf_tail==NULL) { busypf_tail=busypf_head=freepf_head; } else { busypf_tail->next=freepf_head; busypf_tail=freepf_head; } freepf_head=p; } } printf(“%6.3f”,1-(float)diseffect/320);} /* Name: void LRU(inttotal_pf) Achieve: 最近最久未使用（Least Recently Used）*/ －12－ void LRU(inttotal_pf){ intmin,minj,i,j,present_time;//minj为最小值下标 initialize(total_pf);present_time=0;for(i=0;i if(pl[page[i]].pfn==INVALID)//页面失效 { diseffect++; if(freepf_head==NULL)//无空闲页面 { min=32767;//设置最大值 for(j=0;j { if(min>pl[j].time&&pl[j].pfn!=INVALID) { min=pl[j].time; minj=j; } } freepf_head=&pfc[pl[minj].pfn]; //空出一个单元 pl[minj].pfn=INVALID; pl[minj].time=0; freepf_head->next=NULL; } pl[page[i]].pfn=freepf_head->pfn;//有空闲页面,改为有效 pl[page[i]].time=present_time; freepf_head=freepf_head->next;//减少一个free 页面 } else { pl[page[i]].time=present_time;//命中则增加该单元的访问次数 present_time++; } } printf(“%6.3f”,1-(float)diseffect/320);} /* Name:void OPT(inttotal_pf) Achieve:最佳置换算法（Optimal）*/ void OPT(inttotal_pf){ －13－ inti,j, max,maxpage,d,dist[total_vp];pfc_type *t;initialize(total_pf);for(i=0;i if(pl[page[i]].pfn==INVALID) /*页面失效*/ { diseffect++; if(freepf_head==NULL) /*无空闲页面*/ { for(j=0;j { if(pl[j].pfn!=INVALID) dist[j]=32767; else dist[j]=0; } for(j=0;j { if((pl[j].pfn!=INVALID)&&(dist[j]==32767)) { dist[j]=j; } } max=0; for(j=0;j if(max { max=dist[j]; maxpage=j; } freepf_head=&pfc[pl[maxpage].pfn]; freepf_head->next=NULL; pl[maxpage].pfn=INVALID; } pl[page[i]].pfn=freepf_head->pfn; freepf_head=freepf_head->next; } } printf(“%6.3f”,1-(float)diseffect/320);} /* Name: vodi LFU(inttotal_pf) Achieve:最不经常使用法（Least Frequently Used） －14－ */ void LFU(inttotal_pf) { inti,j,min,minpage;pfc_type *t;initialize(total_pf);for(i=0;i if(pl[page[i]].pfn==INVALID)//页面失效 { diseffect++; if(freepf_head==NULL)//无空闲页面 { min=32767; //获取counter的使用用频率最小的内存 for(j=0;j { if(min>pl[j].counter&&pl[j].pfn!=INVALID) { min=pl[j].counter; minpage=j; } } freepf_head=&pfc[pl[minpage].pfn]; pl[minpage].pfn=INVALID; pl[minpage].counter=0; freepf_head->next=NULL; } pl[page[i]].pfn=freepf_head->pfn;//有空闲页面,改为有效 pl[page[i]].counter++; freepf_head=freepf_head->next;//减少一个free 页面 } else { pl[page[i]].counter; pl[page[i]].counter=pl[page[i]].counter+1; } } printf(“%6.3f”,1-(float)diseffect/320);} int main(int){ intS,i; －15－ srand((int)getpid()); for(i=0;i { S=(int)rand()%320; a[i]=S; //任选一指令访问点 a[i+1]=a[i]+1;//顺序执行一条指令 a[i+2]=(int)rand()%a[i+1];//执行前地址指令m' a[i+3]=a[i+2]+1;//顺序执行一条指令 a[i+4]=(int)rand()%(319-a[i+2]-1)+a[i+2]+2;//执行后地址指令 } for(i=0;i { page[i]=a[i]/10; offset[i]=a[i]%10;} printf(“FrametOPTtFIFOtLRUtLFU n”);for(i=4;i<=32;i++)//用户内存工作区从4个页面到32个页面 { printf(“%dt”,i);OPT(i);printf(“t”); FIFO(i);printf(“t”); LRU(i); printf(“t”); LFU(i); printf(“n”);} system(“pause”);return 0;} 4.3 实现内存的slab分配器 程序: #include －17－ } 五、调试运行结果 －18－ 5.1 实现一个内存管理的伙伴算法 5.2设计一个虚拟存储区和内存工作区，并使用下述算法计算访问命中率。 －19－ 5.3 实现内存的slab分配器 六、所遇问题及解决方法 1.在写第一个程序的时候，对树的合并在之前的学习中，有比较多的学习，数据结构中此程序有详细的介绍，因此在编写这个程序的时候，比较顺利的完成了要求。但要求中需要产生一些随机的数据，重新对随机仿真函数进行回顾，最后较为顺利的完成了程序。2.第二个程序，要求随机产生一些数据，对srand()和rand()函数定义和产生指令序列，在进一步的学习中，完成了这些函数，仿真内存容量和虚存容量参数变化时的情形，对此不太熟悉，四个算法对要求较高，在完成算法的学习后，完成了程序。 3.第三个程序因不太理解其要求，上网搜寻了一些代码，但对其最后的结果依然没有得出，为此询问了同学，但不知是否正确。 －20－ 微波仿真实验报告 学 院：电子工程学院 班 级 学 号： 姓 名： 班内序号： 微波仿真课作业1 1.了解ADS Schematic的使用和设置 2．在Schematic里，分别仿真理想电容20pF和理想电感5nH，仿真频率为（1Hz-100GHz），观察仿真结果，并分析原因。20pF理想电容 仿真图 原因分析：史密斯原图下半部分是容性，随频率增加，电容由开路点变到短路点，通高频，阻低频。5nH理想电感 仿真图 原因分析：史密斯原图上半部分是感性，随频率增加，电容由短路点变到开路点，阻高频，通低频。 3． Linecalc的使用 a)计算中心频率1GHz时，FR4基片的50Ω微带线的宽度 宽度为：2.9112mm b)计算中心频率1GHz时，FR4基片的50Ω共面波导（CPW）的横截面尺寸（中心信号线宽度与接地板之间的距离） 横截面尺寸为：W=171.355mm，G=5mm，L=63.5mm 4．基于FR4基板，仿真一段特性阻抗为50Ω四分之一波长开路CPW线的性能参数，中心工作频率为1GHz。仿真频段（500MHz-3GHz）,观察Smith圆图变化，分析原因。 仿真图 仿真图分析： 1、1GHz时，为四分之一波长，开路阻抗变换后变为短路，2GHz时为二分之一波长，所以仍为开路； 2、由于损耗，因此反射系数变小，所以等反射系数圆的半径也在变小。 5.基于FR4基板，仿真一段特性阻抗为50Ω四分之一波长短路CPW线的性能参数，中心工作频率为1GHz。仿真频段（500MHz-3GHz）,观察Smith圆图变化，分别求出500MHz和2GHz的输入阻抗，分析变化原因。 仿真图 仿真图分析： 1、1GHz时，为四分之一波长，短路阻抗变换后变为开路，2GHz时为二分之一波长，所以仍为短路； 2、由于损耗，因此反射系数变小，所以等反射系数圆的半径也在变小。分别求出500MHz和2GHz的输入阻抗： 500MHz:Z0*（0.003+j0.001）2GHz：Z0*（0.012-j0.005） 6.分别用理想传输线和在FR4基片上的微带传输线，仿真一段特性阻抗为50Ω四分之一波长开路线的性能参数，工作频率为1GHz。仿真频段（500MHz-3GHz）,观察Smith圆图变化，分别求出500MHz和2GHz的输入阻抗，分析变化原因。 仿真图 分别求出500MHz和2GHz的输入阻抗： 微带线 500MHz:Z0*（0.003-j0.992）2GHz：Z0*（32.830-j1.603）理想传输线 500MHz:Z0*（1.000E-10-j1.000）2GHz：Z0*（2.000E10-j2.000E5） 分析：因为相对于理想传输线，微带线有损耗产生误差，反射系数一直变小。 扩展仿真频率（500MHz-50GHz），分析曲线变化原因。 分析：对于理想传输线，反射系数不变，而对于微带线，由于存在损耗，反射系数会一直变小，因此其反射系数圆的半径在一直变小。 7.分别用理想传输线和在FR4基片上的微带传输线，仿真一段特性阻抗为50Ω四分之一波长短路线的性能参数，工作频率为1GHz。仿真频段（500MHz-3GHz）,观察Smith圆图变化，分别求出500MHz和2GHz的输入阻抗，分析变化原因。 仿真图 分别求出500MHz和2GHz的输入阻抗： 微带线 500MHz:Z0*（0.009+j1.003）2GHz：Z0*（0.031+j0.002）理想传输线 500MHz:Z0*（5.551E-17+j1.000）2GHz：Z0*（8.284E-18-j1.000E-5） 分析：因为相对于理想传输线，微带线有损耗产生误差，反射系数一直变小。 扩展仿真频率（500MHz-50GHz），分析曲线变化原因。 分析：对于理想传输线，反射系数不变，而对于微带线，由于存在损耗，反射系数会一直变小，因此其反射系数圆的半径在一直变小。 8.分别用理想传输线和在FR4基片上的微带传输线，仿真一段特性阻抗为50Ω二分之一波长开路线的性能参数，工作频率为1GHz。仿真频段（500MHz-3GHz）,观察Smith圆图变化，分别求出500MHz和2GHz的输入阻抗，分析变化原因。 仿真图 分别求出500MHz和2GHz的输入阻抗： 微带线 500MHz:Z0*（0.016+j0.006）2GHz：Z0*（16.430-j0.798）理想传输线 500MHz:Z0*（5.000E-11-j6.123E-17）2GHz：Z0*（2.000E10-j2.000E5） 分析：因为相对于理想传输线，微带线有损耗产生误差，反射系数一直变小。扩展仿真频率（500MHz-50GHz），分析曲线变化原因。 分析：对于理想传输线，反射系数不变，而对于微带线，由于存在损耗，反射系数会一直变小，因此其反射系数圆的半径在一直变小。 9.分别用理想传输线和在FR4基片上的微带传输线，仿真一段特性阻抗为50Ω二分之一波长短路线的性能参数，工作频率为1GHz。仿真频段（500MHz-3GHz）,观察Smith圆图变化，分别求出500MHz和2GHz的输入阻抗，分析变化原因。 仿真图 分别求出500MHz和2GHz的输入阻抗： 微带线 500MHz:Z0*（55.044-j19.301）2GHz：Z0*（0.061+j0.004）理想传输线 500MHz:Z0*（-1.000+j1.633E16）2GHz：Z0*（8.284E-18-j1.000E-5） 分析：因为相对于理想传输线，微带线有损耗产生误差，反射系数一直变小。 扩展仿真频率（500MHz-50GHz），分析曲线变化原因。 分析：对于理想传输线，反射系数不变，而对于微带线，由于存在损耗，反射系数会一直变小，因此其反射系数圆的半径在一直变小。微波测量实验中测得的几个史密斯圆图 四分之一开路微带线 四分之一短路微带线 二分之一开路微带线 二分之一短路微带线 微波仿真课作业2 1． 用一段理想四分之一波长阻抗变换器匹配10欧姆到50欧姆，仿真S参数，给出-20dB带宽特性，工作频率为1GHz。计算得，22.36欧姆 仿真S参数 计算分析：由图计算-20dB带宽为 1071-929=142MHz;且如仿真图所示，在1GHz处回波损耗最低，实现阻抗匹配。2． 用一段FR4基片上四分之一波长阻抗变换器匹配10欧姆到50欧姆，仿真S参数，给出-20dB带宽特性，工作频率为1GHz，比较分析题1和题2的结果。 仿真S参数 由图计算-20dB带宽为1065-921=144MHz。 比较分析题1和题2的结果 分析，微带线与理想传输线之间有一定的误差： 1、如图所示可以看出微带线情况下，回波损耗最低点稍微偏离1GHz； 2、-20dB带宽为144MHz大于理想传输线时的142MHz； 3、1GHz阻抗匹配时，微带线时的回波损耗大于理想传输线。 3． 设计一个3节二项式匹配变换器，用于匹配10欧姆到50欧姆的传输线，中心频率是1GHz，该电路在FR4基片上用微带线实现，设计这个匹配变换器并计算 m0.1的带宽，给出回波损耗和插入损耗与频率的关系曲线，比较分析题2和题3的结果。 根据所学的理论知识，先依题意算出三节匹配微带线的阻抗值,然后通过LineCalc计算出相应微带线的长和宽，修改电路图中MLIN的相关参数。 Z1=40.89Ω W=4.198480mm L=40.404500mm Z2=22.36Ω W=9.620970mm L=38.833700mm Z3=12.23Ω W=19.83080mm L=37.648400mm 插入损耗 m0.1的带宽，即为-20dB带宽，由图计算得1325-680=645MHz； 比较分析题2和题3的结果，3节二项式匹配变换器匹配误差更大： 1、如图所示可以看出3节二项式匹配变换器匹配时回波损耗最低点明显偏离1GHz； 2、-20dB带宽为645MHz大于微带线情况； 3、但1GHz阻抗匹配时，3节二项式匹配变换器时的回波损耗小于微带线情况。 4． 题3中，若用3节切比雪夫匹配变换器实现，比较同样情况下的带宽，回波损耗和插入损耗与频率的关系曲线，比较分析题3和题4结果。 根据所学的知识可以计算出切比雪夫变换器匹配的三个微带线的阻抗，然后通过LineCalc计算出相应微带线的长和宽，修改电路图中MLIN的相关参数。Z1=35.94Ω W=4.948710mm L=40.0910mm Z2=22.11Ω W=9.6519mm L=38.8278mm Z3=13.55Ω W=17.57710mm L=37.8241mm 仿真图 插入损耗 m0.1的带宽，即为-20dB带宽，由图计算得1485-534=951MHz； 比较分析题3和题4的结果，即二项式匹配变换器与切比雪夫匹配变换器： 1、切比雪夫匹配变换器的带宽显著增加； 2、切比雪夫匹配变换器回波损耗具有等波纹特性； 3、两者的插入损耗差别不明显。 5． 对于一个负载阻抗ZL=60-j80欧姆，利用Smith Chart Utility功能，分别设计并联短路单枝节和并联开路单枝节匹配，并将Smith Chart Utility给出的匹配结果在Schematic中仿真，给出1-3GHz的回波损耗与频率的关系曲线，并给出m0.1的带宽。并联短路单枝节 计算并联短路单枝节-20dB带宽：1053-952=101MHz 并联开路单枝节 计算并联开路单枝节-20dB带宽：1023-975=48MHz 6． 并联双枝节匹配电路，并联双枝节为开路，枝节之间相距λ/8，中心工作频率为2GHz,利用理想传输线，给出1-3GHz的回波损耗与频率的关系曲线，并给出m0.1的带宽。并联双枝节, 枝节之间相距λ/8，中心工作频率为2GHz 仿真 如图在2GHz匹配 计算-20dB带宽：2012-1988=24MHz第二篇：北邮数据结构实验报告-排序
第三篇：2012《数据结构》上机实验报告 链表
第四篇：北邮操作系统第二次实验[模版]
第五篇：北邮微波仿真实验1
点击咨询 