第一篇：北郵數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告 單鏈表

北京郵電大學(xué) 數(shù)據(jù)結(jié)構(gòu)試驗(yàn)報(bào)告

實(shí)驗(yàn)名稱： 實(shí)驗(yàn)一

線性表 學(xué)生姓名：

班

級(jí)：

班內(nèi)序號(hào)：

學(xué)

號(hào)：

日

期： 2014年1月3日

實(shí)驗(yàn)?zāi)康?/p>

? 熟悉C++語言的基本編程方法，掌握集成編譯環(huán)境的調(diào)試方法 ? 學(xué)習(xí)指針、模板類、異常處理的使用 ? 掌握線性表的操作的實(shí)現(xiàn)方法 ? 學(xué)習(xí)使用線性表解決實(shí)際問題的能力 實(shí)驗(yàn)內(nèi)容

2.1題目1 根據(jù)線性表的抽象數(shù)據(jù)類型的定義，選擇下面任一種鏈?zhǔn)浇Y(jié)構(gòu)實(shí)現(xiàn)線性表，并完成線性表的基本功能。

線性表存儲(chǔ)結(jié)構(gòu)（五選一）：

1、帶頭結(jié)點(diǎn)的單鏈表

2、不帶頭結(jié)點(diǎn)的單鏈表

3、循環(huán)鏈表

4、雙鏈表

5、靜態(tài)鏈表

線性表的基本功能：

1、構(gòu)造：使用頭插法、尾插法兩種方法

2、插入：要求建立的鏈表按照關(guān)鍵字從小到大有序

3、刪除

4、查找

5、獲取鏈表長度

6、銷毀

7、其他：可自行定義

編寫測試main()函數(shù)測試線性表的正確性。程序分析

3.1 存儲(chǔ)結(jié)構(gòu) 單鏈表的存儲(chǔ)結(jié)構(gòu)：

3.2 關(guān)鍵算法分析

一、關(guān)鍵算法 1.頭插法

自然語言描述：a.在堆中建立新結(jié)點(diǎn)

b.將a[i]寫入到新結(jié)點(diǎn)的數(shù)據(jù)域

c.修改新結(jié)點(diǎn)的指針域

d.修改頭結(jié)點(diǎn)的指針域,將新結(jié)點(diǎn)加入鏈表中 代碼描述： template LinkList::LinkList(T a[], int n)//頭插法建立 {

front = new Node;front->next = NULL;for(int i=n-1;i>=0;i--){ Node* s = new Node;s->data = a[i];

}

} s->next = front->next;front->next = s;時(shí)間復(fù)雜度：O(n)

2.尾插法

自然語言描述：a.在堆中建立新結(jié)點(diǎn)

b.將a[i]寫入到新結(jié)點(diǎn)的數(shù)據(jù)域

c.將新結(jié)點(diǎn)加入到鏈表中

d.修改修改尾指針 代碼描述: template LinkList::LinkList(T a[], int n)//尾插法建立 {

front = new Node;front->next=NULL;Node * r = front;for(int i=0;i * s = new Node;

}

} s->data = a[i];s->next = r->next;r->next= s;r=s;時(shí)間復(fù)雜度：O(n)

3.析構(gòu)函數(shù)

自然語言描述：a.新建立一個(gè)指針，指向頭結(jié)點(diǎn)

b.移動(dòng)a中建立的指針

c.逐個(gè)釋放指針

代碼描述: template LinkList::~LinkList()//析構(gòu)函數(shù)，銷毀鏈表 {

Node * p = front;while(p){ front = p;p = p->next;

} } delete front;4.按位查找函數(shù)

自然語言描述: a.初始化工作指針p和計(jì)數(shù)器j，p指向第一個(gè)結(jié)點(diǎn)，j=1

b.循環(huán)以下操作，直到p為空或者j等于1

b1：p指向下一個(gè)結(jié)點(diǎn)

b2：j加1

c.若p為空，說明第i個(gè)元素不存在，拋出異常

d.否則，說明p指向的元素就是所查找的元素，返回元素地址

代碼描述: template Node* LinkList::Get(int i)//按位查找 {

Node * p = front;int j=0;while(p){

if(j

} else break;p = p->next;j++;

} if(!p)throw“查找位置非法”;else

return p;} 時(shí)間復(fù)雜度：O(n)

5.按值查找函數(shù)

自然語言描述：a.初始化工作指針p和計(jì)數(shù)器j，p指向第一個(gè)結(jié)點(diǎn)，j=1

b.循環(huán)以下操作，找到這個(gè)元素或者p指向最后一個(gè)結(jié)點(diǎn)

b1.判斷p指向的結(jié)點(diǎn)是不是要查找的值，如果是，返回j;

b2.否則p指向下一個(gè)結(jié)點(diǎn),并且j的值加一

c.如果找到最后一個(gè)結(jié)點(diǎn)還沒有找到要查找的元素，返回查找失敗信息

代碼描述: template int LinkList::Locate(T x)//按值查找 {

Node * p = front->next;int j = 1;while(p){

} return-1;if(p->data == x)return j;else { p = p->next;

j++;} } 時(shí)間復(fù)雜度：O(n)6.插入函數(shù)

自然語言描述： a.在堆中建立新結(jié)點(diǎn)

b.將要插入的結(jié)點(diǎn)的數(shù)據(jù)寫入到新結(jié)點(diǎn)的數(shù)據(jù)域

c.修改新結(jié)點(diǎn)的指針域

d.修改前一個(gè)指針的指針域，使其指向新插入的結(jié)點(diǎn)的位置

代碼描述: template void LinkList::Insert(int i,T x)//插入函數(shù) {

Node * p = Get(i-1);if(p){

} else throw“插入位置非法”;Node * s = new Node;s->data = x;s->next = p->next;p->next = s;} 時(shí)間復(fù)雜度：O(n)7.按位刪除函數(shù)

自然語言描述：a.從第一個(gè)結(jié)點(diǎn)開始，查找要?jiǎng)h除的位數(shù)i前一個(gè)位置i-1的結(jié)點(diǎn)

b.設(shè)q指向第i個(gè)元素

c.將q元素從鏈表中刪除

d.保存q元素的數(shù)據(jù)

e.釋放q元素 代碼描述: template T LinkList::Delete(int i)//刪除函數(shù) { Node *p = Get(i-1);Node *q = p->next;

T x=q->data;

} p->next = q->next;delete q;return x;

8.遍歷打印函數(shù)

自然語言描述: a.判斷該鏈表是否為空鏈表，如果是，報(bào)錯(cuò)

b.如果不是空鏈表，新建立一個(gè)temp指針

c.將temp指針指向頭結(jié)點(diǎn)

d.打印temp指針的data域

e.逐個(gè)往后移動(dòng)temp指針，直到temp指針的指向的指針的next域?yàn)榭?/p>

代碼描述: template void LinkList::PrintList()//打印鏈表 {

} Node * p = front->next;while(p){

} cout<data<<' ';p = p->next;9.獲取鏈表長度函數(shù)

自然語言描述： a.判斷該鏈表是否為空鏈表，如果是，輸出長度0

b.如果不是空鏈表，新建立一個(gè)temp指針，初始化整形數(shù)n為0

c.將temp指針指向頭結(jié)點(diǎn)

d.判斷temp指針指向的結(jié)點(diǎn)的next域是否為空，如果不是，n加一，否則return n

e.使temp指針逐個(gè)后移，重復(fù)d操作，直到temp指針指向的結(jié)點(diǎn)的next域?yàn)?，返回n 代碼描述: template int LinkList::GetLength()//分析鏈表長度 {

} Node * p = front;int i=0;while(p){

} return i-1;p = p->next;i++;4 程序運(yùn)行結(jié)果

4.1主函數(shù)流程圖

4.2程序運(yùn)行框圖

實(shí)驗(yàn)心得

1.調(diào)試時(shí)出現(xiàn)的問題及解決的方法

在編寫按值查找函數(shù)時(shí)，由于沒有處理好指針類型的原因，導(dǎo)致指針無法正常返回，屢屢報(bào)錯(cuò)。最后意識(shí)到c++沒有指針強(qiáng)制類型的轉(zhuǎn)換機(jī)制，經(jīng)過細(xì)致檢查后才改正錯(cuò)誤使得程序正常運(yùn)行。2.心得體會(huì)

了解了單鏈表的基本的操作函數(shù)實(shí)現(xiàn)，對(duì)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)有了較好的認(rèn)識(shí) 3.下一步的改進(jìn)

可以增加完善報(bào)錯(cuò)機(jī)制，增強(qiáng)程序的健壯性

完整源代碼

#include using namespace std;

template struct Node {

};

template class LinkList { public:

};

//template //LinkList::LinkList(T a[], int n)//頭插法建立 LinkList(){ front = new Node;front->next = NULL;}//無參構(gòu)造函數(shù) LinkList(T a[],int n);//構(gòu)造函數(shù) void Insert(int i,T x);//插入函數(shù) T Delete(int i);//刪除函數(shù)

Node* Get(int i);//查找第幾個(gè)的元素，返回的是該元素的地址 int Locate(T x);//定位某元素 int GetLength();//分析鏈表長度 ~LinkList();//析構(gòu)函數(shù) void PrintList();//打印鏈表 Node * front;T data;Node * next;private: //{ // // // // // // // // // //}

template LinkList::LinkList(T a[], int n)//尾插法建立 {

}

template LinkList::~LinkList()//析構(gòu)函數(shù)，銷毀鏈表 {

}

template void LinkList::PrintList()//打印鏈表 { Node * p = front;while(p){

} front = p;p = p->next;delete front;front = new Node;front->next=NULL;Node * r = front;for(int i=0;i

} Node * s = new Node;s->data = a[i];s->next = r->next;r->next= s;r=s;front = new Node;front->next = NULL;for(int i=n-1;i>=0;i--){

} Node* s = new Node;s->data = a[i];s->next = front->next;front->next = s;

} Node * p = front->next;while(p){

} cout<data<<' ';p = p->next;

template Node* LinkList::Get(int i)//按位查找 {

}

template int LinkList::Locate(T x)//按值查找 {

} Node * p = front->next;int j = 1;while(p){

} return-1;if(p->data == x)return j;else

{ } p = p->next;

j++;Node * p = front;int j=0;while(p){

} if(!p)throw“查找位置非法”;else

return p;if(j

} else break;p = p->next;j++;

template void LinkList::Insert(int i,T x)//插入函數(shù) {

}

template T LinkList::Delete(int i)//刪除函數(shù) {

}

template int LinkList::GetLength()//分析鏈表長度 {

}

void main(){ Node * p = front;int i=0;while(p){

} return i-1;p = p->next;i++;Node *p = Get(i-1);Node *q = p->next;p->next = q->next;delete q;return x;Node * p = Get(i-1);if(p){

} else throw“插入位置非法”;Node * s = new Node;s->data = x;s->next = p->next;p->next = s;

T x=q->data;

} int n;cout<<“將要輸入的鏈表長度為：”;cin>>n;int *b=new int[n];cout<<“輸入鏈表中的元素：”;for(int k=0;k>b[k];LinkList a(b,n);a.PrintList();cout<<“鏈表的長度:”<>i;cout<<“被刪除掉的元素是：”<>j;cout<<“要將其插入在哪個(gè)位置：”;cin>>i;a.Insert(i,j);cout<<“插入后得到的鏈表是：”;a.PrintList();cout<<“要查找第幾個(gè)元素：”;cin>>i;cout<<“要查找的元素為：”<data<>j;cout<<“輸入的元素位置在：”<

第二篇：北郵數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告-排序

北京郵電大學(xué) 數(shù)據(jù)結(jié)構(gòu)試驗(yàn)報(bào)告

實(shí)驗(yàn)名稱： 實(shí)驗(yàn)四

排序 學(xué)生姓名：

班

級(jí)：

班內(nèi)序號(hào)：

學(xué)

號(hào)：

日

期： 2014年1月4日

實(shí)驗(yàn)?zāi)康?/p>

學(xué)習(xí)、實(shí)現(xiàn)、對(duì)比各種排序算法，掌握各種排序算法的優(yōu)劣，以及各種算法使用的情況。實(shí)驗(yàn)內(nèi)容

2.1 題目1 使用簡單數(shù)組實(shí)現(xiàn)下面各種排序算法，并進(jìn)行比較。排序算法：

1、插入排序

2、希爾排序

3、冒泡排序

4、快速排序

5、簡單選擇排序

6、堆排序（選作）

7、歸并排序（選作）

8、基數(shù)排序（選作）

9、其他

要求：

1、測試數(shù)據(jù)分成三類：正序、逆序、隨機(jī)數(shù)據(jù)

2、對(duì)于這三類數(shù)據(jù)，比較上述排序算法中關(guān)鍵字的比較次數(shù)和移動(dòng)次數(shù)（其中關(guān)鍵字交換計(jì)為3次移動(dòng)）。

3、對(duì)于這三類數(shù)據(jù)，比較上述排序算法中不同算法的執(zhí)行時(shí)間，精確到微秒（選作）

4、對(duì)2和3的結(jié)果進(jìn)行分析，驗(yàn)證上述各種算法的時(shí)間復(fù)雜度

編寫測試main()函數(shù)測試線性表的正確性。程序分析

3.1 存儲(chǔ)結(jié)構(gòu)

順序存儲(chǔ)結(jié)構(gòu)——數(shù)組

3.2 關(guān)鍵算法分析

1.插入排序：依次將待排序的序列中的每一個(gè)記錄插入到先前排序好的序列中，直到全部記錄排序完畢

void Insertsort(int r[],int n,int* compare,int* move)//插入排序 {

*compare=0;*move=0;int i;int j;for(i=1;i=0;j--){

(*compare)++;

(*move)++;

r[j+1]=r[j];} if(j>=0)(*compare)++;r[j+1]=x;} } 2.希爾排序：先將整個(gè)序列分割成若干個(gè)子列，分別在各個(gè)子列中運(yùn)用直接插入排序，待整個(gè)序列基本有序時(shí)，再對(duì)全體記錄進(jìn)行一次直接插入排序 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]往后逐個(gè)元素確定是否需要前移 { 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.冒泡排序：兩兩比較相鄰記錄的關(guān)鍵碼，如果反序則交換，直到?jīng)]有反序記錄為止 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.快速排序：首先選擇一個(gè)基準(zhǔn)，將記錄分割為兩部分，左支小于或等于基準(zhǔn)，右支則大于基準(zhǔn)，然后對(duì)兩部分重復(fù)上述過程，直至整個(gè)序列排序完成

int Partion(int r[],int first,int end,int* compare,int* move)//快速排序中的軸定位 { int i=first;int j=end;int zhou=r[i];//默認(rèn)第一個(gè)元素為軸 while(i=zhou))//查看右側(cè)元素與軸的大小關(guān)系

{

(*compare)++;

j--;} if(i

r[i]=r[j];//發(fā)現(xiàn)軸右側(cè)的某數(shù)比軸值小，將其前置

} while((i

(*compare)++;

(*move)++;

r[j]=r[i];//發(fā)現(xiàn)軸左側(cè)的某數(shù)比軸值小，將其后置

} } 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;//記錄下當(dāng)前找到的最小值的位置

}

if(min!=i)

{(*move)+=3;

int Min;

Min=r[min];

r[min]=r[i];

r[i]=Min;

}

} } 程序運(yùn)行結(jié)果

4.1主函數(shù)流程圖

4.2程序運(yùn)行框圖 實(shí)驗(yàn)心得

1.調(diào)試時(shí)出現(xiàn)的問題及解決的方法

在初期構(gòu)思代碼的時(shí)候，首先構(gòu)造了各種算法的基本實(shí)現(xiàn)代碼，封裝成類，已經(jīng)能夠?qū)崿F(xiàn)七種排序的基本功能，并且測試無誤。

之后考慮如何能簡化代碼以實(shí)現(xiàn)多達(dá)七種排序算法的簡單調(diào)用、亂序和順序以及逆序數(shù)據(jù)的分別排序和性能指標(biāo)統(tǒng)計(jì)（算法移動(dòng)次數(shù)和比較次數(shù)的精確統(tǒng)計(jì)）。2.心得體會(huì)

程序的優(yōu)化是一個(gè)艱辛的過程，如果只是實(shí)現(xiàn)一般的功能，將變得容易很多，當(dāng)加上優(yōu)化，不論是效率還是結(jié)構(gòu)優(yōu)化，都需要精心設(shè)計(jì)。3.改進(jìn)

本程序代碼設(shè)計(jì)時(shí)運(yùn)用了遞歸的調(diào)用方式，效率還可以通過將其轉(zhuǎn)換為棧模擬的方式得以提高。另外還可以進(jìn)一步考慮算法時(shí)間的精確統(tǒng)計(jì)，以便從時(shí)間角度比較這幾種排序算法的優(yōu)劣。

完整源代碼

#include using namespace std;

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=0;j--){

} 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]往后逐個(gè)元素確定是否需要前移 {

} } }

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];//默認(rèn)第一個(gè)元素為軸 while(i

{ }

if(i=zhou))//查看右側(cè)元素與軸的大小關(guān)系 {

} if(i

r[i]=r[j];//發(fā)現(xiàn)軸右側(cè)的某數(shù)比軸值小，將其前置

(*move)++;

r[j]=r[i];//發(fā)現(xiàn)軸左側(cè)的某數(shù)比軸值小，將其后置

} } 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;//記錄下當(dāng)前找到的最小值的位置

}

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<<“請(qǐng)您先輸入一個(gè)正序數(shù)組哦”<>n;int *r=new int[n];cout<<“請(qǐng)輸入數(shù)組中的元素：”;for(i=0;i>r[i];int *a=new int[n];for(i=0;i

cout<<“再輸入一個(gè)逆序數(shù)組~~~”<>n;cout<<“請(qǐng)輸入數(shù)組中的元素：”;for(i=0;i>r[i];for(i=0;i

cout<<“最后輸入一個(gè)亂序數(shù)組~~~”<>n;cout<<“請(qǐng)輸入數(shù)組中的元素：”;for(i=0;i>r[i];for(i=0;i

第三篇：2012《數(shù)據(jù)結(jié)構(gòu)》上機(jī)實(shí)驗(yàn)報(bào)告 鏈表

西華大學(xué)數(shù)計(jì)學(xué)院學(xué)生上機(jī)實(shí)踐報(bào)告

西華數(shù)學(xué)與計(jì)算機(jī)學(xué)院上機(jī)實(shí)踐報(bào)告

課程名稱：數(shù)據(jù)結(jié)構(gòu) 指導(dǎo)教師：唐劍梅 上機(jī)實(shí)踐名稱：

上機(jī)實(shí)踐編號(hào)：1 年級(jí)： 2011 姓名：蔣俊 學(xué)

號(hào)

：

***

上機(jī)實(shí)踐成績：

上機(jī)實(shí)踐日期：2012-11-6

上機(jī)實(shí)踐時(shí)間：8:00-9:30

一、實(shí)驗(yàn)?zāi)康?/p>

1.了解線性表的邏輯結(jié)構(gòu)特性，以及這種特性在計(jì)算機(jī)內(nèi)的兩種存儲(chǔ)結(jié)構(gòu)。

2.重點(diǎn)是線性表的基本操作在兩種存儲(chǔ)結(jié)構(gòu)上的實(shí)現(xiàn)；其中以鏈表的操作為側(cè)重點(diǎn)；并進(jìn)一步學(xué)習(xí)程序設(shè)計(jì)方法。

3.掌握棧這種數(shù)據(jù)結(jié)構(gòu)特性及其主要存儲(chǔ)結(jié)構(gòu)，并能在現(xiàn)實(shí)生活中靈活運(yùn)用。

4.掌握隊(duì)列這種數(shù)據(jù)結(jié)構(gòu)特性及其主要存儲(chǔ)結(jié)構(gòu)，并能在現(xiàn)實(shí)生活中靈活運(yùn)用。

5.了解和掌握遞歸程序設(shè)計(jì)的基本原理和方法。

6.掌握使用 C++面向?qū)ο蟮某绦蛟O(shè)計(jì)技術(shù)設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)源程序的方法。

二、實(shí)驗(yàn)內(nèi)容

1.熟悉前面的【程序示例2】，按照約瑟夫問題的方法2，試著不設(shè)頭結(jié)點(diǎn)改寫原來的程序，上機(jī)調(diào)試運(yùn)行。

2.用鏈表建立通訊錄。通訊錄內(nèi)容有：姓名、通訊地址、電話號(hào)碼。

要求：（1）通訊錄按姓名項(xiàng)的字母順序排列；

（2）能查找通訊錄中某人的信息；

[提示] 用鏈表來存放這個(gè)通訊錄，一個(gè)人的信息作為一個(gè)結(jié)點(diǎn)。成鏈的過程可以這樣考慮：先把頭結(jié)點(diǎn)后面的

西華大學(xué)數(shù)計(jì)學(xué)院學(xué)生上機(jī)實(shí)踐報(bào)告

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

輸入總?cè)藬?shù) n=”;cin>>n;

pre=new NodeType;

Head=new NodeType;

pre->num=1;

cout<<“n 編號(hào)”<<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 編號(hào)”<

姓名=”;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

根據(jù)m值，開始報(bào)數(shù)輸出：”<

while(q->next!=q)

西華大學(xué)數(shù)計(jì)學(xué)院學(xué)生上機(jī)實(shí)踐報(bào)告

{ for(i=1;inext;}

cout<<“編號(hào)為：”<num<<“ 的人的姓名：”<name<

cout<<“n 編號(hào)為:”<num<<“的人的密碼：”<psw<

m=q->psw;

p->next=q->next;delete q;

q=p->next;

}

cout<<“編號(hào)為：”<num<<“的人的姓名：”<name<

cout<<“n 編號(hào)為:”<num<<“的人的密碼：”<psw<

delete q;}

int main()

{

Jose h;

h.creat();

h.outs();

return 0;}

西華大學(xué)數(shù)計(jì)學(xué)院學(xué)生上機(jī)實(shí)踐報(bào)告

{ 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,“電話號(hào)碼”);} Sqlist::~Sqlist(){

NodeType *p=Head->next;

while(p!=NULL)

{Head->next=p->next;

delete p;

p=Head->next;} } void Sqlist::creat()

//初步建立一個(gè)通訊錄

{ NodeType*p,*s,*q;ElemType x;

西華大學(xué)數(shù)計(jì)學(xué)院學(xué)生上機(jī)實(shí)踐報(bào)告

int a;q=Head;cout<<“n 輸入姓名：”;cin>>x.name;cout<<“n 輸入通訊地址：”;cin>>x.Add;cout<<“n 輸入電話號(hào)碼：”;cin>>x.tel;p=new NodeType;p->data=x;Head->next=p;p->next=NULL;cout<<“輸入一個(gè)數(shù)。若為-1，結(jié)束輸入:”<>a;

while(a!=-1){ cout<<“n 輸入姓名：”;cin>>x.name;cout<<“n 輸入通訊地址：”;cin>>x.Add;cout<<“n 輸入電話號(hào)碼：=”;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<<“輸入一個(gè)數(shù)。若為-1，結(jié)束輸入:”<>a;} } void Sqlist::Insert(ElemType x)//插入 { NodeType *p,*q,*s;s=new NodeType;

西華大學(xué)數(shù)計(jì)學(xué)院學(xué)生上機(jī)實(shí)踐報(bào)告

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<<“刪除結(jié)點(diǎn)成功”<

{ 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.初步建立一個(gè)通訊錄（單鏈表）

”;

西華大學(xué)數(shù)計(jì)學(xué)院學(xué)生上機(jī)實(shí)踐報(bào)告

cout<<“nn

2.插入新的電話記錄 ”;

cout<<“nn

3.刪除一個(gè)電話記錄”;

cout<<“nn

4.結(jié)束程序”;

cout<<“n******************************** ”;

cout<<“n

請(qǐng)輸入你的選擇(1,2,3,4)”;cin>>k;switch(k){ case 1:{ as.creat();as.PrintOut();}break;

case 2:{

cout<<“n 插入的數(shù)據(jù) 姓名”;cin>>e.name;

cout<<“n 插入的數(shù)據(jù) 電話號(hào)”;cin>>e.tel;

cout<<“n 插入的數(shù)據(jù) 地址”;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;}

西華大學(xué)數(shù)計(jì)學(xué)院學(xué)生上機(jī)實(shí)踐報(bào)告

西華大學(xué)數(shù)計(jì)學(xué)院學(xué)生上機(jī)實(shí)踐報(bào)告

西華大學(xué)數(shù)計(jì)學(xué)院學(xué)生上機(jī)實(shí)踐報(bào)告

const int MAXSIZE=100;

// 數(shù)組的容量 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<

西華大學(xué)數(shù)計(jì)學(xué)院學(xué)生上機(jī)實(shí)踐報(bào)告

} 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<<“請(qǐng)輸入一個(gè)正整數(shù):”<>a;cout<<“請(qǐng)輸入要轉(zhuǎn)換的進(jìn)制:”<>m;SqStack as;as.f(a,m);}

西華大學(xué)數(shù)計(jì)學(xué)院學(xué)生上機(jī)實(shí)踐報(bào)告

五、總結(jié)

通過本次實(shí)驗(yàn)，我熟悉了鏈表的操作，了解了線性表在現(xiàn)實(shí)生活中的運(yùn)用，認(rèn)識(shí)了順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)這兩種結(jié)構(gòu)。本次上機(jī)實(shí)踐基本完成了實(shí)驗(yàn)內(nèi)容，但完成的不是很好，以后需要更加努力地掌握基本的知識(shí)。實(shí)驗(yàn)內(nèi)容對(duì)于隊(duì)列的運(yùn)用沒有涉及，希望以后有所涉及。

西華大學(xué)數(shù)計(jì)學(xué)院學(xué)生上機(jī)實(shí)踐報(bào)告

第四篇：北郵操作系統(tǒng)第二次實(shí)驗(yàn)[模版]

北京郵電大學(xué)操作系統(tǒng)實(shí)驗(yàn)實(shí)驗(yàn)報(bào)告

班號(hào)：2011211314姓名：oneseven學(xué)號(hào)：

實(shí)驗(yàn)日期： 2013.12.16 實(shí)驗(yàn)名稱： 操作系統(tǒng)實(shí)驗(yàn)

一、實(shí)驗(yàn)?zāi)康?/p>

通過模擬實(shí)現(xiàn)內(nèi)存分配的伙伴算法和請(qǐng)求頁式存儲(chǔ)管理的幾種基本頁面置換算法，了解存儲(chǔ)技術(shù)的特點(diǎn)。掌握虛擬存儲(chǔ)請(qǐng)求頁式存儲(chǔ)管理中幾種基本頁面置換算法的基本思想和實(shí)現(xiàn)過程，并比較它們的效率。

二、實(shí)驗(yàn)內(nèi)容

1.實(shí)現(xiàn)一個(gè)內(nèi)存管理的伙伴算法，實(shí)現(xiàn)內(nèi)存塊申請(qǐng)時(shí)的分配和釋放后的回收。

實(shí)驗(yàn)準(zhǔn)備

用隨機(jī)函數(shù)仿真進(jìn)程進(jìn)行內(nèi)存申請(qǐng)，并且以較為隨機(jī)的次序進(jìn)行釋放。對(duì)其碎片進(jìn)行統(tǒng)計(jì)，當(dāng)申請(qǐng)分配內(nèi)存失敗時(shí)區(qū)分實(shí)際空間不足和由于碎片而不能滿足。

2.設(shè)計(jì)一個(gè)虛擬存儲(chǔ)區(qū)和內(nèi)存工作區(qū)，并使用下述算法計(jì)算訪問命中率。

1)最佳置換算法（Optimal）

2)先進(jìn)先出法（Fisrt In First Out）

3)最近最久未使用（Least Recently Used）4)最不經(jīng)常使用法（Least Frequently Used）

其中，命中率＝１－頁面失效次數(shù)／頁地址流長度。試對(duì)上述算法的性能加以較各：頁面?zhèn)€數(shù)和命中率間的關(guān)系；同樣情況下的命中率比較。

實(shí)驗(yàn)準(zhǔn)備

本實(shí)驗(yàn)中主要的流程：首先用srand()和rand()函數(shù)定義和產(chǎn)生指令序列，然后將指令序列變換成相應(yīng)的頁地址流，并針對(duì)不同的算法計(jì)算出相應(yīng)的命中率。

實(shí)驗(yàn)可先從一個(gè)具體的例子出發(fā)。

(1)通過隨機(jī)數(shù)產(chǎn)生一個(gè)指令序列，共2048條指令。指令的地址按下述原則生成： A：50%的指令是順序執(zhí)行的

B：25%的指令是均勻分布在前地址部分 C：25%的指令是均勻分布在后地址部分 具體的實(shí)施方法是：

A：在[0，1023]的指令地址之間隨機(jī)選取一起點(diǎn)m B：順序執(zhí)行一條指令，即執(zhí)行地址為m+1的指令

C：在前地址[0,m+1]中隨機(jī)選取一條指令并執(zhí)行，該指令的地址為m’ D：順序執(zhí)行一條指令，其地址為m’+1 E：在后地址[m’+2，2047]中隨機(jī)選取一條指令并執(zhí)行 F：重復(fù)步驟A-E，直到2048次指令(2)將指令序列變換為頁地址流 設(shè)：頁面大小為4K；

用戶內(nèi)存容量4頁到32頁； 用戶虛存容量為32K。

在用戶虛存中，按每K存放64條指令排列虛存地址，即2048條指令在虛存中的存放方式為：

第 0 條-第 63 條指令為第0頁（對(duì)應(yīng)虛存地址為[0，63]）第64條-第127條指令為第1頁（對(duì)應(yīng)虛存地址為[64，127]）

………………………………

－1－ 第1984條-第2047條指令為第31頁（對(duì)應(yīng)虛存地址為[1984，2047]）按以上方式，用戶指令可組成32頁。

以此為基礎(chǔ)，給出較為一般的情形：仿真內(nèi)存容量和虛存容量參數(shù)變化時(shí)的情形。

3.實(shí)現(xiàn)內(nèi)存的slab分配器：

其基本思想是：一次向內(nèi)核獲取整數(shù)頁，slab根據(jù)數(shù)據(jù)結(jié)構(gòu)的大小進(jìn)行劃分為一個(gè)個(gè)小的數(shù)據(jù)結(jié)構(gòu)，當(dāng)需要時(shí)直接從該鏈表上摘取一個(gè)返回應(yīng)用程序，當(dāng)應(yīng)用程序釋放時(shí)，而非真正釋放，只需要該空間放回到鏈表中，當(dāng)分散的一頁多塊又聚集一頁時(shí)，又會(huì)拼成一頁，同時(shí)判斷slab空閑的頁數(shù)，如果空閑頁超過一定的頁數(shù)，就會(huì)向系統(tǒng)釋放一定的頁數(shù)。一個(gè)slab分配器只能管理一個(gè)指定大小的數(shù)據(jù)結(jié)構(gòu)分配。

三、項(xiàng)目要求及分析

3.1實(shí)現(xiàn)一個(gè)內(nèi)存管理的伙伴算法，實(shí)現(xiàn)內(nèi)存塊申請(qǐng)時(shí)的分配和釋放后的回收。假設(shè)系統(tǒng)的可利用內(nèi)存空間容量為2m個(gè)字(地址從0到2m-1)，則在開始運(yùn)行時(shí)，整個(gè)內(nèi)存區(qū)是一個(gè)大小為2m的空閑塊，在運(yùn)行了一段時(shí)間之后，被分隔成若干占用塊和空閑塊。為了在分配時(shí)查找方便起見，我們將所有大小相同的空閑塊建于一張子表中。每個(gè)子表是一個(gè)雙重鏈表，這樣的鏈表可能有m+1個(gè)，將這m+1個(gè)表頭指針用向量結(jié)構(gòu)組織成一個(gè)表，這就是伙伴系統(tǒng)中的可利用空間表，如圖所示：

分配算法：

當(dāng)用戶提出大小為n的內(nèi)存請(qǐng)求時(shí)，首先在可利用表上尋找結(jié)點(diǎn)大小與n相匹配的子表，若此子表非空，則將子表中任意一個(gè)結(jié)點(diǎn)分配之即可；若此子表為空，則需從結(jié)點(diǎn)更大的非空子表中去查找，直至找到一個(gè)空閑塊，則將其中一部分分配給用戶，而將剩余部分插入相應(yīng)的子表中。

若2k-1 < n ≤ 2k-1，又第k+1個(gè)子表不空，則只要?jiǎng)h除此鏈表中第一個(gè)結(jié)點(diǎn)并分配給用戶即可；若 2k-2 < n ≤ 2k-1-1，此時(shí)由于結(jié)點(diǎn)大小為2k-1 的子表為空，則需從結(jié)點(diǎn)大小為2k 的子表中取出一塊，將其中一半分配給用戶，剩余的一半作為一個(gè)新結(jié)點(diǎn)插入在結(jié)點(diǎn)大小為2k-1的子表中，若2k-i-1 < n ≤ 2k-i-1(i為小于是的整數(shù))，并且所有結(jié)點(diǎn)小于2k的子表均為空，則同樣需從結(jié)點(diǎn)大小為2k的子表中取出一塊，將其中2k-i的一小部分分配給用戶，剩余部分分割成若干個(gè)結(jié)點(diǎn)分別插入在結(jié)點(diǎn)大小為2k-1、2k-

2、…、2k-i的子表中?；厥账惴ǎ?/p>

在用戶釋放不再使用的占用塊時(shí)，系統(tǒng)需將這新的空閑塊插入到可利用空間表中去。這里，同樣有一個(gè)地址相鄰的空閑塊歸并成大塊的問題。但是在伙伴系統(tǒng)中僅考慮互為“伙伴”的兩個(gè)空閑塊的歸并。

何謂“伙伴”?如前所述，在分配時(shí)經(jīng)常需要將一個(gè)大的空閑塊分裂成兩個(gè)大小相等的存

－2－ 儲(chǔ)區(qū)，這兩個(gè)由同一大塊分裂出來的小塊就稱之“互為伙伴”。例如：假設(shè)p為大小為pow(2,k)的空閑塊的初始地址，且p MOD pow(2,k+1)=0，則初始地址為p和p+pow(2,k)的兩個(gè)空閑塊互為伙伴。在伙伴系統(tǒng)中回收空閑塊時(shí)，只當(dāng)其伙伴為空閑塊時(shí)才歸并成大塊。也就是說，若有兩個(gè)空閑塊，即使大小相同且地址相鄰，但不是由同一大塊分裂出來的，也不歸并在一起。

由此，在回收空閑塊時(shí)，應(yīng)首先判別其伙伴是否為空閑塊，若否，則只要將釋放的空閑塊簡單插入在相應(yīng)子表中即可；若是，則需在相應(yīng)子表中找到其伙伴并刪除之，然后再判別合并后的空閑塊的伙伴是否是空閑塊。依此重復(fù)，直到歸并所得空閑塊的伙伴不是空閑塊時(shí)，再插入到相應(yīng)的子表中去。

3.2.設(shè)計(jì)一個(gè)虛擬存儲(chǔ)區(qū)和內(nèi)存工作區(qū)，并使用下述算法計(jì)算訪問命中率。

頁式虛擬存儲(chǔ)器實(shí)現(xiàn)的一個(gè)難點(diǎn)是設(shè)計(jì)頁面調(diào)度（置換）算法，即將新頁面調(diào)入內(nèi)存時(shí)，如果內(nèi)存中所有的物理頁都已經(jīng)分配出去，就要按某種策略來廢棄某個(gè)頁面，將其所占據(jù)的物理頁釋放出來，供新頁面使用。頁面替換算法主要用于如下幾個(gè)地方：

(1)虛擬存儲(chǔ)器中，主存頁面（或程序段）的替換。

(2)Cache中的塊替換。

(3)虛擬存儲(chǔ)器的快慢表中，快表的替換。

(4)虛擬存儲(chǔ)器中，用戶基地址寄存器的替換。

在虛擬存儲(chǔ)器中常用的頁面替換算法有如下幾種：

(1)最優(yōu)替換算法，即OPT算法（OPTimal replacement algorithm）。上面介紹的幾種頁面替換算法主要是以主存儲(chǔ)器中頁面調(diào)度情況的歷史信息為依據(jù)的，它假設(shè)將來主存儲(chǔ)器中的頁面調(diào)度情況與過去一段時(shí)間內(nèi)主存儲(chǔ)器中的頁面調(diào)度情況是相同的。顯然，這種假設(shè)不總是正確的。最好的算法應(yīng)該是選擇將來最久不被訪問的頁面作為被替換的頁面，這種替換算法的命中率一定是最高的，它就是最優(yōu)替換算法。

要實(shí)現(xiàn)OPT算法，唯一的辦法是讓程序先執(zhí)行一遍，記錄下實(shí)際的頁地址流情況。根據(jù)這個(gè)頁地址流才能找出當(dāng)前要被替換的頁面。顯然，這樣做是不現(xiàn)實(shí)的。因此，OPT算法只是一種理想化的算法，然而，它也是一種很有用的算法。實(shí)際上，經(jīng)常把這種算法用來作為評(píng)價(jià)其它頁面替換算法好壞的標(biāo)準(zhǔn)。在其它條件相同的情況下，哪一種頁面替換算法的命中率與OPT算法最接近，那么，它就是一種比較好的頁面替換算法。(2)先進(jìn)先出算法，即FIFO算法（First-In First-Out algorithm）。這種算法選擇最先調(diào)入主存儲(chǔ)器的頁面作為被替換的頁面。它的優(yōu)點(diǎn)是比較容易實(shí)現(xiàn)，能夠利用主存儲(chǔ)器中頁面調(diào)度情況的歷史信息，但是，沒有反映程序的局部性。因?yàn)樽钕日{(diào)入主存的頁面，很可能也是經(jīng)常要使用的頁面。

(3)最久沒有使用算法，即LRU算法（Least Recently Used algorithm）。這種算法把近期最久沒有被訪問過的頁面作為被替換的頁面。它把LFU算法中要記錄數(shù)量上的“多”與“少”簡化成判斷“有”與“無”，因此，實(shí)現(xiàn)起來比較容易。

(4)近期最少使用算法，即LFU算法（Least Frequently Used algorithm）。這種算法選擇近期最少訪問的頁面作為被替換的頁面。顯然，這是一種非常合理的算法，因?yàn)榈侥壳盀橹棺钌偈褂玫捻撁妫芸赡芤彩菍碜钌僭L問的頁面。該算法既充分利用了主存中頁面調(diào)度情況的歷史信息，又正確反映了程序的局部性。但是，這種算法實(shí)現(xiàn)起來非常困難，它要為每個(gè)頁面設(shè)置一個(gè)很長的計(jì)數(shù)器，并且要選擇一個(gè)固定的時(shí)鐘為每個(gè)計(jì)數(shù)器定時(shí)計(jì)數(shù)。在選擇被替換頁面時(shí)，要從所有計(jì)數(shù)器中找出一個(gè)計(jì)數(shù)值最大的計(jì)數(shù)器。因此，通常采用如下一種相 －3－ 對(duì)比較簡單的方法。

3.3實(shí)現(xiàn)內(nèi)存的slab分配器

slab描述符和空閑對(duì)象管理部分成為 slab的管理部分，也可以稱為slab頭

slab的頭可以放在slab自身，也可以放在 slab 之外。如果slab頭放在了slab 之外，那么用戶申請(qǐng)obj時(shí)，需要首先訪問 slab頭，slab頭提供未使用free obj的指針

然后再訪問這個(gè)free obj的地址。完成這項(xiàng)工作需要訪問2個(gè)頁塊。會(huì)帶來效率上的損失。slab頭始終位于slab 也存在問題，比如一個(gè)頁面只有4K，objsize = 2K，那么slab 頭在slab 上，就意味著，這個(gè)4K的頁面只能夠分配一個(gè)obj。造成了內(nèi)存的浪費(fèi)。

如果 頁數(shù)太少，存放的 obj個(gè)數(shù)少，那么 增加管理開銷，同時(shí) 內(nèi)存使用率低，如果頁數(shù)太多對(duì)伙伴內(nèi)存系統(tǒng)不好，所以需要一定的策略妥協(xié)。

這個(gè)妥協(xié)過程是有calculate_slab_order 這個(gè)函數(shù)來實(shí)現(xiàn)的。從 0階（即一頁）到kmalloc的最高階 KMALLOC_MAX_ORDER，挨個(gè)嘗試，由cache_estimate這個(gè)函數(shù)計(jì)算 如果選用order 階，那么能分配 多少個(gè) obj（num），剩余空間是多少（remainder）。所謂剩余空間，就是除去slab頭（如果有的話），除去 obj*num，剩下的邊角料空間是多少。需要分成兩種情況去計(jì)算，分成兩種情況的原因，很快就能看到 A)slab頭不在slab上，即 flag & CFLGS_OFF_SLAB == 1的時(shí)候 這種情況比較簡單，由于管理數(shù)據(jù)完全不在slab 上，size_tslab_size = PAGE_SIZE <

換句話，slab頭的大小取決于obj的個(gè)數(shù)，obj的個(gè)數(shù)取決于 slab頭的大小，四、具體實(shí)現(xiàn)

4.1實(shí)現(xiàn)一個(gè)內(nèi)存管理的伙伴算法，實(shí)現(xiàn)內(nèi)存塊申請(qǐng)時(shí)的分配和釋放后的回收。

程序：

#include #include #include

#define MIN_MOMORY_SIZE 536870912

//隨機(jī)產(chǎn)生的最小內(nèi)存空間 #define WORKTIME 1500

//系統(tǒng)工作時(shí)間

#define MAX_REQ_SIZE 268435456

//申請(qǐng)空閑內(nèi)存分配的最大容量：256M #define MIN_DUE 30

//使用內(nèi)存塊的最短時(shí)間 #define MAX_DUE 90

//使用內(nèi)存塊的最長時(shí)間 #define OCCUPY_INTERVAL 60

//每次分配的最大間隔 #define USED 1

//內(nèi)存塊被使用 #define UNUSED 0

//內(nèi)存塊未被使用

//內(nèi)存塊鏈表結(jié)點(diǎn)結(jié)構(gòu) typedefstructbuddy_node { int flag;

//標(biāo)記空間是否被使用

－4－ int base;

//本塊兒內(nèi)存的基地址

int occupy;

//實(shí)際使用空間大小

int fragment;

//碎片大小

intduetime;

//使用時(shí)間

structbuddy_node *nextPtr;

//指向下一個(gè)結(jié)點(diǎn) } Buddy, *BuddyPtr;

IndexTable table[INDEX_SIZE];//使用哈希表管理伙伴系統(tǒng) int ready = 0;

//需要分配內(nèi)存的時(shí)刻 intavailSpace;

//可分配空間大小 inttotalFragment = 0;

//總碎片大小

//函數(shù)：添加結(jié)點(diǎn)（形參為內(nèi)存塊結(jié)點(diǎn)的信息）

void insert_node(inti, intinbase, int f, intocc, int frag, int d){ BuddyPtrnewnodePtr = NULL, prePtr = NULL, curPtr = NULL;

newnodePtr =(BuddyPtr)malloc(sizeof(Buddy));//分配結(jié)點(diǎn) 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;

//按地址順序插入內(nèi)存塊

while(curPtr&&curPtr->base nextPtr;

}

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－

}

} }

//函數(shù)：刪除結(jié)點(diǎn)

intdelete_node(inti, BuddyPtrdelPtr){ BuddyPtrprePtr = NULL, curPtr = NULL;intbasehold = delPtr->base;

curPtr = table[i].headPtr;

while(curPtr!= delPtr){ //尋找要?jiǎng)h除的結(jié)點(diǎn)的位置 prePtr = curPtr;curPtr = curPtr->nextPtr;

}

if(prePtr == NULL)

//要?jiǎng)h除的結(jié)點(diǎn)在最前

table[i].headPtr = curPtr->nextPtr;

else

//要?jiǎng)h除的結(jié)點(diǎn)不在鏈表的最前 prePtr->nextPtr = curPtr->nextPtr;

free(curPtr);

//釋放結(jié)點(diǎn)

return basehold;

//返回刪除的內(nèi)存塊結(jié)點(diǎn)的基地址 }

//函數(shù)：伙伴系統(tǒng)的分配算法 void buddy_allocate(inttime_slice){ inti, j, size, due;int state = 0;

//分配狀態(tài)：0為未分配，1為已分配 intinbase, basehold;BuddyPtrcurPtr = NULL;

if(ready == time_slice){ //到達(dá)分配內(nèi)存的時(shí)刻 printf(“Time %d:”, time_slice);

size = 1 + rand()% MAX_REQ_SIZE;

//申請(qǐng)使用內(nèi)存的大小

due = MIN_DUE + rand()%(MAX_DUEsize;curPtr->duetime = due + ready;

//修改可系統(tǒng)分配空間和碎片大小 availSpace-= table[i].nodesize;totalFragment += curPtr->fragment;

state = 1;//標(biāo)記已分配

break;

}

//空閑塊的大小剛大于申請(qǐng)大小的2倍

else { basehold = delete_node(i, curPtr);//刪除較大的空閑塊并保留其基地址 inbase = basehold + table[i].nodesize;

j = i;

//分割空閑塊

do {

j--;inbase-= table[j].nodesize;

//設(shè)置要添加內(nèi)存塊結(jié)點(diǎn)的基地址 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;//標(biāo)記已分配

}

}

//塊被占用，查看下一結(jié)點(diǎn)

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);//下次需要分配內(nèi)存的時(shí)刻

} }

//函數(shù)：伙伴系統(tǒng)的回收算法 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)){//需要回收

//修改可系統(tǒng)分配空間和碎片大小 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){

//將地址連續(xù)且都為空閑的塊合并后加入下一級(jí)的鏈表中

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)){

//刪除兩個(gè)結(jié)點(diǎn) 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);//添加合并后的結(jié)點(diǎn) printf(“Two blocks mergen”);

}

else curPtr = curPtr->nextPtr;

}

else curPtr = curPtr->nextPtr;

}

}

} }

//函數(shù)：伙伴系統(tǒng)的處理過程 void buddy_system(void){ inttime_slice = 0;

//在每個(gè)時(shí)間片內(nèi)使用分配算法和回收算法

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));

//設(shè)置隨機(jī)數(shù)種子

//隨機(jī)產(chǎn)生需要管理的內(nèi)存大?。?12M ~ 1G

memory_size = MIN_MOMORY_SIZE + rand()% MIN_MOMORY_SIZE;printf(“The size of memory is:%dn”, memory_size);

int_system(memory_size);

//初始化伙伴系統(tǒng)

buddy_system();

//伙伴系統(tǒng)的處理過程

printf(“Time %d:System execution stops and the spaces are all freed.n”, WORKTIME);

free_system();

//釋放所有結(jié)點(diǎn)

system(“pause”);

return 0;}

4．2.設(shè)計(jì)一個(gè)虛擬存儲(chǔ)區(qū)和內(nèi)存工作區(qū)，并使用下述算法計(jì)算訪問命中率。程序：

#include #include #include #define TRUE 1 #define FALSE 0 #define INVALID-1 #define NUL 0 #define total_instruction 320 //指令流長 #define total_vp 32

//虛頁長 #define clear_period 50

//清零周期

typedefstruct {

intpn;

//頁號(hào) intpfn;

// 面號(hào)

int counter;

// 一個(gè)周期內(nèi)訪問該頁面的次數(shù) int time;

// time為訪問時(shí)間 }pl_type;pl_typepl[total_vp];//頁面結(jié)構(gòu)數(shù)組

structpfc_struct{

//頁面控制結(jié)構(gòu) 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:初始化相關(guān)數(shù)據(jù)結(jié)構(gòu) */ void initialize(inttotal_pf){ inti;diseffect=0;

for(i=0;i

{ pl[i].pn=i;pl[i].pfn=INVALID;

//置頁面控制結(jié)構(gòu)中的頁號(hào)，頁面為空

pl[i].counter=0;pl[i].time=-1;//頁面控制結(jié)構(gòu)中的訪問次數(shù)為0，時(shí)間為-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];

//頁面隊(duì)列的頭指針為pfc[0] } /*

－11－ Name:void FIFO(inttotal_pf)

Achieve:先進(jìn)先出法（Fisrt In First Out）*/

void FIFO(inttotal_pf){ inti,j;pfc_type *p;//中間變量

initialize(total_pf);//初始化相關(guān)頁面控制用數(shù)據(jù)結(jié)構(gòu)

busypf_head=busypf_tail=NULL;//忙頁面隊(duì)列頭，隊(duì)列尾鏈接

for(i=0;i

if(pl[page[i]].pfn==INVALID)

//頁面失效

{

diseffect+=1;//失效次數(shù)

if(freepf_head==NULL)//無空閑頁面

{

p=busypf_head->next;

pl[busypf_head->pn].pfn=INVALID;

freepf_head=busypf_head;//釋放忙頁面隊(duì)列的第一個(gè)頁面

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為最小值下標(biāo)

initialize(total_pf);present_time=0;for(i=0;i

if(pl[page[i]].pfn==INVALID)//頁面失效

{

diseffect++;

if(freepf_head==NULL)//無空閑頁面

{

min=32767;//設(shè)置最大值

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];

//空出一個(gè)單元

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;//減少一個(gè)free 頁面

}

else

{

pl[page[i]].time=present_time;//命中則增加該單元的訪問次數(shù)

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:最不經(jīng)常使用法（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的使用用頻率最小的內(nèi)存

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;//減少一個(gè)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;

//任選一指令訪問點(diǎn)

a[i+1]=a[i]+1;//順序執(zhí)行一條指令

a[i+2]=(int)rand()%a[i+1];//執(zhí)行前地址指令m'

a[i+3]=a[i+2]+1;//順序執(zhí)行一條指令

a[i+4]=(int)rand()%(319-a[i+2]-1)+a[i+2]+2;//執(zhí)行后地址指令

} for(i=0;i

{

page[i]=a[i]/10;

offset[i]=a[i]%10;}

printf(“FrametOPTtFIFOtLRUtLFU n”);for(i=4;i<=32;i++)//用戶內(nèi)存工作區(qū)從4個(gè)頁面到32個(gè)頁面

{

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 實(shí)現(xiàn)內(nèi)存的slab分配器 程序: #include #include #include using namespace std;－16－

－17－

}

五、調(diào)試運(yùn)行結(jié)果

－18－ 5.1 實(shí)現(xiàn)一個(gè)內(nèi)存管理的伙伴算法

5.2設(shè)計(jì)一個(gè)虛擬存儲(chǔ)區(qū)和內(nèi)存工作區(qū)，并使用下述算法計(jì)算訪問命中率。

－19－

5.3 實(shí)現(xiàn)內(nèi)存的slab分配器

六、所遇問題及解決方法

1.在寫第一個(gè)程序的時(shí)候，對(duì)樹的合并在之前的學(xué)習(xí)中，有比較多的學(xué)習(xí)，數(shù)據(jù)結(jié)構(gòu)中此程序有詳細(xì)的介紹，因此在編寫這個(gè)程序的時(shí)候，比較順利的完成了要求。但要求中需要產(chǎn)生一些隨機(jī)的數(shù)據(jù)，重新對(duì)隨機(jī)仿真函數(shù)進(jìn)行回顧，最后較為順利的完成了程序。2.第二個(gè)程序，要求隨機(jī)產(chǎn)生一些數(shù)據(jù)，對(duì)srand()和rand()函數(shù)定義和產(chǎn)生指令序列，在進(jìn)一步的學(xué)習(xí)中，完成了這些函數(shù)，仿真內(nèi)存容量和虛存容量參數(shù)變化時(shí)的情形，對(duì)此不太熟悉，四個(gè)算法對(duì)要求較高，在完成算法的學(xué)習(xí)后，完成了程序。

3.第三個(gè)程序因不太理解其要求，上網(wǎng)搜尋了一些代碼，但對(duì)其最后的結(jié)果依然沒有得出，為此詢問了同學(xué)，但不知是否正確。

－20－

第五篇：北郵微波仿真實(shí)驗(yàn)1

微波仿真實(shí)驗(yàn)報(bào)告

學(xué) 院：電子工程學(xué)院 班 級(jí) 學(xué) 號(hào)： 姓 名： 班內(nèi)序號(hào)：

微波仿真課作業(yè)1

1.了解ADS Schematic的使用和設(shè)置

2．在Schematic里，分別仿真理想電容20pF和理想電感5nH，仿真頻率為（1Hz-100GHz），觀察仿真結(jié)果，并分析原因。20pF理想電容

仿真圖

原因分析：史密斯原圖下半部分是容性，隨頻率增加，電容由開路點(diǎn)變到短路點(diǎn)，通高頻，阻低頻。5nH理想電感

仿真圖

原因分析：史密斯原圖上半部分是感性，隨頻率增加，電容由短路點(diǎn)變到開路點(diǎn)，阻高頻，通低頻。

3． Linecalc的使用

a)計(jì)算中心頻率1GHz時(shí)，F(xiàn)R4基片的50Ω微帶線的寬度

寬度為：2.9112mm b)計(jì)算中心頻率1GHz時(shí)，F(xiàn)R4基片的50Ω共面波導(dǎo)（CPW）的橫截面尺寸（中心信號(hào)線寬度與接地板之間的距離）

橫截面尺寸為：W=171.355mm，G=5mm，L=63.5mm

4．基于FR4基板，仿真一段特性阻抗為50Ω四分之一波長開路CPW線的性能參數(shù)，中心工作頻率為1GHz。仿真頻段（500MHz-3GHz）,觀察Smith圓圖變化，分析原因。

仿真圖

仿真圖分析： 1、1GHz時(shí)，為四分之一波長，開路阻抗變換后變?yōu)槎搪罚?GHz時(shí)為二分之一波長，所以仍為開路；

2、由于損耗，因此反射系數(shù)變小，所以等反射系數(shù)圓的半徑也在變小。

5.基于FR4基板，仿真一段特性阻抗為50Ω四分之一波長短路CPW線的性能參數(shù)，中心工作頻率為1GHz。仿真頻段（500MHz-3GHz）,觀察Smith圓圖變化，分別求出500MHz和2GHz的輸入阻抗，分析變化原因。

仿真圖

仿真圖分析： 1、1GHz時(shí)，為四分之一波長，短路阻抗變換后變?yōu)殚_路，2GHz時(shí)為二分之一波長，所以仍為短路；

2、由于損耗，因此反射系數(shù)變小，所以等反射系數(shù)圓的半徑也在變小。分別求出500MHz和2GHz的輸入阻抗： 500MHz:Z0*（0.003+j0.001）2GHz：Z0*（0.012-j0.005）

6.分別用理想傳輸線和在FR4基片上的微帶傳輸線，仿真一段特性阻抗為50Ω四分之一波長開路線的性能參數(shù)，工作頻率為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）

分析：因?yàn)橄鄬?duì)于理想傳輸線，微帶線有損耗產(chǎn)生誤差，反射系數(shù)一直變小。

擴(kuò)展仿真頻率（500MHz-50GHz），分析曲線變化原因。

分析：對(duì)于理想傳輸線，反射系數(shù)不變，而對(duì)于微帶線，由于存在損耗，反射系數(shù)會(huì)一直變小，因此其反射系數(shù)圓的半徑在一直變小。

7.分別用理想傳輸線和在FR4基片上的微帶傳輸線，仿真一段特性阻抗為50Ω四分之一波長短路線的性能參數(shù)，工作頻率為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）

分析：因?yàn)橄鄬?duì)于理想傳輸線，微帶線有損耗產(chǎn)生誤差，反射系數(shù)一直變小。

擴(kuò)展仿真頻率（500MHz-50GHz），分析曲線變化原因。

分析：對(duì)于理想傳輸線，反射系數(shù)不變，而對(duì)于微帶線，由于存在損耗，反射系數(shù)會(huì)一直變小，因此其反射系數(shù)圓的半徑在一直變小。

8.分別用理想傳輸線和在FR4基片上的微帶傳輸線，仿真一段特性阻抗為50Ω二分之一波長開路線的性能參數(shù)，工作頻率為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）

分析：因?yàn)橄鄬?duì)于理想傳輸線，微帶線有損耗產(chǎn)生誤差，反射系數(shù)一直變小。擴(kuò)展仿真頻率（500MHz-50GHz），分析曲線變化原因。

分析：對(duì)于理想傳輸線，反射系數(shù)不變，而對(duì)于微帶線，由于存在損耗，反射系數(shù)會(huì)一直變小，因此其反射系數(shù)圓的半徑在一直變小。

9.分別用理想傳輸線和在FR4基片上的微帶傳輸線，仿真一段特性阻抗為50Ω二分之一波長短路線的性能參數(shù)，工作頻率為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）

分析：因?yàn)橄鄬?duì)于理想傳輸線，微帶線有損耗產(chǎn)生誤差，反射系數(shù)一直變小。

擴(kuò)展仿真頻率（500MHz-50GHz），分析曲線變化原因。

分析：對(duì)于理想傳輸線，反射系數(shù)不變，而對(duì)于微帶線，由于存在損耗，反射系數(shù)會(huì)一直變小，因此其反射系數(shù)圓的半徑在一直變小。微波測量實(shí)驗(yàn)中測得的幾個(gè)史密斯圓圖 四分之一開路微帶線

四分之一短路微帶線

二分之一開路微帶線

二分之一短路微帶線

微波仿真課作業(yè)2

1． 用一段理想四分之一波長阻抗變換器匹配10歐姆到50歐姆，仿真S參數(shù)，給出-20dB帶寬特性，工作頻率為1GHz。計(jì)算得，22.36歐姆

仿真S參數(shù)

計(jì)算分析：由圖計(jì)算-20dB帶寬為 1071-929=142MHz;且如仿真圖所示，在1GHz處回波損耗最低，實(shí)現(xiàn)阻抗匹配。2． 用一段FR4基片上四分之一波長阻抗變換器匹配10歐姆到50歐姆，仿真S參數(shù)，給出-20dB帶寬特性，工作頻率為1GHz，比較分析題1和題2的結(jié)果。

仿真S參數(shù)

由圖計(jì)算-20dB帶寬為1065-921=144MHz。

比較分析題1和題2的結(jié)果

分析，微帶線與理想傳輸線之間有一定的誤差：

1、如圖所示可以看出微帶線情況下，回波損耗最低點(diǎn)稍微偏離1GHz；

2、-20dB帶寬為144MHz大于理想傳輸線時(shí)的142MHz； 3、1GHz阻抗匹配時(shí)，微帶線時(shí)的回波損耗大于理想傳輸線。

3． 設(shè)計(jì)一個(gè)3節(jié)二項(xiàng)式匹配變換器，用于匹配10歐姆到50歐姆的傳輸線，中心頻率是1GHz，該電路在FR4基片上用微帶線實(shí)現(xiàn)，設(shè)計(jì)這個(gè)匹配變換器并計(jì)算

?m?0.1的帶寬，給出回波損耗和插入損耗與頻率的關(guān)系曲線，比較分析題2和題3的結(jié)果。

根據(jù)所學(xué)的理論知識(shí)，先依題意算出三節(jié)匹配微帶線的阻抗值,然后通過LineCalc計(jì)算出相應(yīng)微帶線的長和寬，修改電路圖中MLIN的相關(guān)參數(shù)。

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

插入損耗

?m?0.1的帶寬，即為-20dB帶寬，由圖計(jì)算得1325-680=645MHz；

比較分析題2和題3的結(jié)果，3節(jié)二項(xiàng)式匹配變換器匹配誤差更大：

1、如圖所示可以看出3節(jié)二項(xiàng)式匹配變換器匹配時(shí)回波損耗最低點(diǎn)明顯偏離1GHz；

2、-20dB帶寬為645MHz大于微帶線情況；

3、但1GHz阻抗匹配時(shí)，3節(jié)二項(xiàng)式匹配變換器時(shí)的回波損耗小于微帶線情況。

4． 題3中，若用3節(jié)切比雪夫匹配變換器實(shí)現(xiàn)，比較同樣情況下的帶寬，回波損耗和插入損耗與頻率的關(guān)系曲線，比較分析題3和題4結(jié)果。

根據(jù)所學(xué)的知識(shí)可以計(jì)算出切比雪夫變換器匹配的三個(gè)微帶線的阻抗，然后通過LineCalc計(jì)算出相應(yīng)微帶線的長和寬，修改電路圖中MLIN的相關(guān)參數(shù)。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

仿真圖

插入損耗

?m?0.1的帶寬，即為-20dB帶寬，由圖計(jì)算得1485-534=951MHz；

比較分析題3和題4的結(jié)果，即二項(xiàng)式匹配變換器與切比雪夫匹配變換器：

1、切比雪夫匹配變換器的帶寬顯著增加；

2、切比雪夫匹配變換器回波損耗具有等波紋特性；

3、兩者的插入損耗差別不明顯。

5． 對(duì)于一個(gè)負(fù)載阻抗ZL=60-j80歐姆，利用Smith Chart Utility功能，分別設(shè)計(jì)并聯(lián)短路單枝節(jié)和并聯(lián)開路單枝節(jié)匹配，并將Smith Chart Utility給出的匹配結(jié)果在Schematic中仿真，給出1-3GHz的回波損耗與頻率的關(guān)系曲線，并給出?m?0.1的帶寬。并聯(lián)短路單枝節(jié)

計(jì)算并聯(lián)短路單枝節(jié)-20dB帶寬：1053-952=101MHz

并聯(lián)開路單枝節(jié)

計(jì)算并聯(lián)開路單枝節(jié)-20dB帶寬：1023-975=48MHz

6． 并聯(lián)雙枝節(jié)匹配電路，并聯(lián)雙枝節(jié)為開路，枝節(jié)之間相距λ/8，中心工作頻率為2GHz,利用理想傳輸線，給出1-3GHz的回波損耗與頻率的關(guān)系曲線，并給出?m?0.1的帶寬。并聯(lián)雙枝節(jié), 枝節(jié)之間相距λ/8，中心工作頻率為2GHz

仿真

如圖在2GHz匹配

計(jì)算-20dB帶寬：2012-1988=24MHz