查找 实验报告

查找 实验报告（共6篇）

篇1：查找 实验报告

实验六

查找

实验目的：

掌握几种查找的思想及算法 问题分析：

（一）顺序查找 1.查找思想

从表的一端开始逐个将记录的关键字和给定K值进行比较，若某个记录的关键字和给定K值相等，查找成功；否则，若扫描完整个表，仍然没有找到相应的记录，则查找失败。2.算法实现

int Seq_Search(SSTable ST,int key){

int p;

} ST.data[0].key=key;/* 设置监视哨兵,失败返回0 */ for(p=ST.length;ST.data[p].key!=key;p--);return(p);

3.算法分析

设查找每个记录成功的概率相等，即Pi=1/n；查找第i个元素成功的比较次数Ci=n-i+1 ； ◆ 查找成功时的平均查找长度ASL：

◆

包含查找不成功时：查找失败的比较次数为n+1，若成功与不成功的概率相等，对每个记录的查找概率为Pi=1/(2n)，则平均查找长度ASL：

（二）折半查找

前提条件：查找表中的所有记录是按关键字有序(升序或降序)。

查找过程中，先确定待查找记录在表中的范围，然后逐步缩小范围(每次将待查记录所在区间缩小一半)，直到找到或找不到记录为止。1.查找思想

用Low、High和Mid表示待查找区间的下界、上界和中间位置指针，初值为Low=1，High=n。

⑴

取中间位置Mid：Mid=(Low+High)/2 ；

⑵

比较中间位置记录的关键字与给定的K值： ①

相等： 查找成功；

②

大于：待查记录在区间的前半段，修改上界指针： High=Mid-1，转⑴ ； ③

小于：待查记录在区间的后半段，修改下界指针：Low=Mid+1，转⑴ ； 直到越界(Low>High)，查找失败。2.算法实现

int Bin_Search(SSTable ST , KeyType k){

int low=1，high=ST.length, mid;

while(low<=high){

mid=(low+high)/2;

if(EQ(ST.data[mid].key, k))

return(mid);

else if(LT(ST.dat[mid].key, k))

low=mid+1;

else high=mid-1;

}

return(0);

/*

查找失败

*/ } 3.算法分析

①

查找时每经过一次比较，查找范围就缩小一半，该过程可用一棵二叉树表示： ◆

根结点就是第一次进行比较的中间位置的记录； ◆ 排在中间位置前面的作为左子树的结点； ◆ 排在中间位置后面的作为右子树的结点；

对各子树来说都是相同的。这样所得到的二叉树称为判定树(Decision Tree)。②

将二叉判定树的第㏒2n+1层上的结点补齐就成为一棵满二叉树，深度不变，h= ㏒2(n+1)。4.算法分析

①

查找时每经过一次比较，查找范围就缩小一半，该过程可用一棵二叉树表示： ◆

根结点就是第一次进行比较的中间位置的记录； ◆ 排在中间位置前面的作为左子树的结点； ◆ 排在中间位置后面的作为右子树的结点；

对各子树来说都是相同的。这样所得到的二叉树称为判定树(Decision Tree)。②

将二叉判定树的第㏒2n+1层上的结点补齐就成为一棵满二叉树，深度不变，h= ㏒2(n+1)。

③

由满二叉树性质知，第i 层上的结点数为2i-1(i≤h)，设表中每个记录的查找概率相等，即Pi=1/n，查找成功时的平均查找长度ASL：

当n很大(n>50)时，ASL≈ ㏒2(n+1)-1。

（三）BST树 1.BST树的插入（1）插入思想

在BST树中插入一个新结点x时，若BST树为空，则令新结点x为插入后BST树的根结点；否则，将结点x的关键字与根结点T的关键字进行比较：

① 若相等： 不需要插入；

②

若x.keykey：结点x插入到T的左子树中； ③

若x.key>T->key：结点x插入到T的右子树中。（2）算法实现

递归算法

void Insert_BST(BSTree T , KeyType key){ BSTNode *s;s=(BSTNode *)malloc(sizeof(BSTNode));s->key=key;s->Lchild=s->Rchild=NULL;if(T==NULL)T=s;else { if(EQ(T->key, s->key))return;/* 已有结点

*/ else if(LT(s->key, T->key))Insert_BST(T->Lchild, key);else Insert_BST(T->Rchild, key);

} 非递归算法

void Insert_BST(BSTree T , KeyType key){ BSTNode *s, *p , *f;s=(BSTNode *)malloc(sizeof(BSTNode));s->key=key;s->Lchild=s->Rchild=NULL;if(T==NULL)T=s;else { p=T;

while(p!=NULL)

{

if(EQ(p->key, s->key))return;

f=p;

/*q作为p的父结点

*/

if(LT(s->key, p->key))p=p->Lchild;

else p=p->Rchild;

}

if(LT(s->key, f->key))f->Lchild=s;else f->Rchild=s;} }

利用BST树的插入操作，可以从空树开始逐个插入每个结点，从而建立一棵BST树，算法如下：

#define ENDKEY 65535 BSTree create_BST(){

KeyType key;BSTree T=NULL;scanf(“%d”, &key);while(key!=ENDKEY){

Insert_BST(T, key);scanf(“%d”, &key);} return(T);}

2.BST树的查找

（1）查找思想

首先将给定的K值与二叉排序树的根结点的关键字进行比较：若相等： 则查找成功； ① 给定的K值小于BST的根结点的关键字：继续在该结点的左子树上进行查找； ②

给定的K值大于BST的根结点的关键字：继续在该结点的右子树上进行查找。（2）算法实现

递归算法

BSTNode *BST_Serach(BSTree T , KeyType key)

{

if(T==NULL)return(NULL);else

{ if(EQ(T->key, key))return(T);else if(LT(key, T->key))

return(BST_Serach(T->Lchild, key));

else

return(BST_Serach(T->Rchild, key));} } 非递归算法

BSTNode *BST_Serach(BSTree T , KeyType key){ BSTNode * p=T;while(p!=NULL&&!EQ(p->key, key)){ if(LT(key, p->key))p=p->Lchild;else p=p->Rchild;} if(EQ(p->key, key))return(p);else return(NULL);} 在随机情况下，二叉排序树的平均查找长度ASL和㏒(n)(树的深度)是等数量级的。3.BST树的删除

（1）

删除操作过程分析

从BST树上删除一个结点，仍然要保证删除后满足BST的性质。设被删除结点为p，其父结点为f，删除情况如下： ①

若p是叶子结点： 直接删除p

②

若p只有一棵子树(左子树或右子树)：直接用p的左子树(或右子树)取代p的位置而成为f的一棵子树。即原来p是f 的左子树，则p的子树成为f 的左子树；原来p是f 的右子树，则p的子树成为f的右子树

③ 若p既有左子树又有右子树 ：处理方法有以下两种，可以任选其中一种。◆

用p的直接前驱结点代替p。即从p的左子树中选择值最大的结点s放在p的位置(用结点s的内容替换结点p内容)，然后删除结点s。s是p的左子树中的最右边的结点且没有右子树，对s的删除同②

◆ 用p的直接后继结点代替p。即从p的右子树中选择值最小的结点s放在p的位置(用结点s的内容替换结点p内容)，然后删除结点s。s是p的右子树中的最左边的结点且没有左子树，对s的删除同②（2）算法实现

void Delete_BST(BSTree T , KeyType key)

// 在以T为根结点的BST树中删除关键字为key的结点

{ BSTNode *p=T , *f=NULL , *q , *s;while(p!=NULL&&!EQ(p->key, key)){ f=p;//f 指向p的父结点

if(LT(key, p->key))p=p->Lchild;//搜索左子树

else p=p->Rchild;// 搜索右子树

} if(p==NULL)return;

// 没有要删除的结点 s=p;

// 找到了要删除的结点为p

if(p->Lchild!=NULL&& p->Rchild!=NULL)

{ f=p;s=p->Lchild;

// 从左子树开始找

while(s->Rchild!=NULL)

{

f=s;s=s->Rchild;

} // 左、右子树都不空，找左子树中最右边的结点

p->key=s->key;p->otherinfo=s->otherinfo;

// 用结点s的内容替换结点p内容

}

// 将第3种情况转换为第2种情况

if(s->Lchild!=NULL)

// 若s有左子树，右子树为空

q=s->Lchild;else q=s->Rchild;if(f==NULL)T=q;else if(f->Lchild==s)f->Lchild=q;

else f->Rchild=q;free(s);}

（四）哈希查找

1.基本思想：在记录的存储地址和它的关键字之间建立一个确定的对应关系；这样，不经过比较，一次存取就能得到所查元素的查找方法。2.哈希函数 除留余数法

取关键字被某个不大于哈希表表长m的数p除后所得余数作哈希地址，即H(key)=key

MOD p

(pm)3.冲突处理

★链地址法（拉链法）

方法：将所有关键字为同义词(散列地址相同)的记录存储在一个单链表中，并用一维数组存放链表的头指针。

设散列表长为m，定义一个一维指针数组： RecNode *linkhash[m]，其中RecNode是结点类型，每个分量的初值为空。凡散列地址为k的记录都插入到以linkhash[k]为头指针的链表中，插入位置可以在表头或表尾或按关键字排序插入。（1）链地址法查找

int Hash_Insert2(HTNode *T[ ], HTNode *s, int m)

{ HTNode *p=Hash_Search(T,s->key,m);

if(p!=NULL)

return 0;

//表中已有该结点

else {

d=h(s->key);

s->next=T[d];

T[d]=s;

return 1;

//插入成功

}

}

（2）链地址法插入

typedef struct node { KeyType key;struct node *next;}HTNode;

HTNode *hash_search2(HTNode *T[ ], KeyType k){ HTNode *p;

int i;p=T[h(k)];while(p!=NULL&&p->key!=k)

p=p->next;return p;} /*用链地址法解决冲突

*/

源程序清单：

#include #include typedef struct RecType{

int key;char info;}RecType;#define MAX_SIZE 100 typedef struct SSTable{

// 顺序表结构

RecType data[MAX_SIZE];

int length;}SSTable;

typedef struct Node{

//二叉树结构

int key;char info;struct Node *Lchild,*Rchild;}BSTNode;

typedef BSTNode * BSTree;

int Seq_Search(SSTable ST,int key){

//顺序查找

int p;

ST.data[0].key=key;for(p=ST.length;ST.data[p].key!=key;p--);return(p);}

void Bin_Search(SSTable ST,int key){ //折半查找

int low=1,high=ST.length,mid;int i,j,k;

} for(i=1;i

if(ST.data[j].key

k=j;} if(k!=i){

ST.data[0].key=ST.data[i].key;

ST.data[i].key=ST.data[k].key;

ST.data[k].key=ST.data[0].key;

ST.data[0].info=ST.data[i].info;

ST.data[i].info=ST.data[k].info;

ST.data[k].info=ST.data[0].info;} } while(low<=high){ mid=(low+high)/2;if(ST.data[mid].key==key)break;else if(ST.data[mid].keyhigh)printf(“Error!”);else printf(“%d,%cn”,ST.data[mid].key,ST.data[mid].info);BSTree Insert_BST(BSTree T,int key,char info){

//BST树的插入

BSTNode *s,*p,*f;s=(BSTNode *)malloc(sizeof(BSTNode));s->key=key;s->Lchild=s->Rchild=NULL;s->info=info;if(T==NULL)T=s;else{

p=T;

while(p!=NULL){

if(p->key==s->key)break;

f=p;

if(s->key

key)p=p->Lchild;

else p=p->Rchild;

}

if(s->keykey)f->Lchild=s;

else f->Rchild=s;} return T;}

void InorderTraverse(BSTree T){ if(T!=NULL){

InorderTraverse(T->Lchild);

printf(“%d,%ct”,T->key,T->info);

InorderTraverse(T->Rchild);} }

#define ENDKEY 65535 BSTree create_BST(SSTable ST){

//BST树的建立

BSTree T=NULL;int i,key,info;for(i=1;i<=ST.length;i++){

key=ST.data[i].key;

info=ST.data[i].info;

T=Insert_BST(T,key,info);} return T;} BSTNode *BST_Serach(BSTree T,int key){

if(T==NULL)return(NULL);else{

if(T->key==key)return(T);

else if(keykey)

return(BST_Serach(T->Lchild,key));

else

return(BST_Serach(T->Rchild,key));} }

BSTree Delete_BST(BSTree T, int key){

//BST树的删除

BSTNode *p=T,*f=NULL,*q,*s;while(p!=NULL&&(p->key!=key)){

f=p;

if(key

key)p=p->Lchild;

else p=p->Rchild;} if(p==NULL)return T;else s=p;if(p->Lchild!=NULL&&p->Rchild!=NULL){

f=p;s=p->Lchild;

while(s->Rchild!=NULL){

f=s;s=s->Rchild;

}

p->key=s->key;p->info=s->info;} if(s->Lchild!=NULL)q=s->Lchild;else q=s->Rchild;if(f==NULL)T=q;else if(f->Lchild==s)f->Lchild=q;else f->Rchild=q;free(s);return T;}

typedef struct node2{ int key;char info;struct node2 *next;}HTNode;HTNode *Hash_Search(HTNode *T[],int key,int m){

//链地址查找

HTNode *p;p=T[key%m];while(p!=NULL&&p->key!=key)p=p->next;return p;} HTNode *Hash_Insert(HTNode *T[],int key,char info,int m){

//链地址插入，建立哈希表

HTNode *s=(HTNode *)malloc(sizeof(HTNode));s->key=key;s->info=info;s->next=NULL;HTNode *p=Hash_Search(T,s->key,m);int d;if(p!=NULL)return *T;else{

d=s->key%m;

s->next=T[d];

T[d]=s;

} return *T;}

void main(){ int a,key,p,i,m;char info;SSTable ST;BSTree T=NULL;BSTNode *s;HTNode *HT[20];HTNode *ht;printf(“1.输入数据n2.顺序查找n3.折半查找n4.BST树的查找n5.BST树的插入n6.BST树的删除n7.链地址法查找n8.链地址法插入n0.退出n”);while(1){

printf(“n请选择：”);scanf(“%d”,&a);getchar();switch(a){ case 1: printf(“请输入记录数量n：”);scanf(“%d”,&ST.length);

printf(“请输入除数：”);scanf(“%d”,&m);

for(i=0;i<20;i++)HT[i]=NULL;for(i=1;i<=ST.length;i++){

printf(“请输入关键字码与数据：”);scanf(“%d,%c”,&ST.data[i].key,&ST.data[i].info);*HT=Hash_Insert(HT,ST.data[i].key,ST.data[i].info,m);}

T=create_BST(ST);printf(“已建立！”);break;case 2:printf(“请输入要查找的关键字码：”);scanf(“%d”,&key);p=Seq_Search(ST,key);printf(“%d,%cn”,ST.data[p].key,ST.data[p].info);break;case 3:printf(“请输入要查找的关键字码：”);scanf(“%d”,&key);Bin_Search(ST,key);break;case 4:printf(“请输入要查找的关键字码：”);scanf(“%d”,&key);s=BST_Serach(T,key);printf(“%d,%cn”,s->key,s->info);break;case 5:printf(“请输入要添加的关键字码及数据：”);scanf(“%d,%c”,&key,&info);T=Insert_BST(T,key,info);printf(“添加后的结果：”);InorderTraverse(T);printf(“n”);

}

} break;case 6:printf(“请输入要删除的关键字码：”);scanf(“%d”,&key);T=Delete_BST(T,key);

printf(“删除后的结果：”);InorderTraverse(T);printf(“n”);break;case 7:printf(“请输入要查找的关键字码：”);scanf(“%d”,&key);ht=Hash_Search(HT,key,m);printf(“%d,%cn”,ht->key,ht->info);break;case 8:printf(“请输入要添加的关键字码及数据：”);scanf(“%d,%c”,&key,&info);*HT=Hash_Insert(HT,key,info,m);for(i=0;i

ht=HT[i];

while(ht!=NULL){

printf(“%d,%ct”,ht->key,ht->info);

ht=ht->next;

} } break;case 0: exit(0);} 运行结果：

篇2：查找 实验报告

//文件名:exp9-1.cpp #include #define MAXL 100 typedef int KeyType;typedef char InfoType[10];typedef struct {

KeyType key;

//KeyType为关键字的数据类型 //其他数据

//定义表中最多记录个数

InfoType data;

} NodeType;typedef NodeType SeqList[MAXL];

//顺序表类型

int SeqSearch(SeqList R,int n,KeyType k)//顺序查找算法

{

int i=0;

while(i

{

} printf(“%d ”,R[i].key);i++;

//从表头往后找

if(i>=n)return-1;

else

} void main(){ SeqList R;{

} printf(“%d”,R[i].key);return i;

} int n=10,i;KeyType k=5;int a[]={3,6,2,10,1,8,5,7,4,9};for(i=0;i

//建立顺序表

printf(“关键字序列:”);for(i=0;i

截图如下：

实验题9.2 设计一个程序exp9-2.cpp，输出在顺序表{1，2，3，4，5，6，7，8，9，10}中采用折半查找法查找关键字9的过程。

程序如下：

//文件名:exp9-2.cpp #include #define MAXL 100 typedef int KeyType;typedef char InfoType[10];typedef struct {

//定义表中最多记录个数 KeyType key;

//KeyType为关键字的数据类型

InfoType data;

//其他数据 } NodeType;typedef NodeType SeqList[MAXL];

//顺序表类型

int BinSearch(SeqList R,int n,KeyType k)//二分查找算法 { int low=0,high=n-1,mid,count=0;while(low<=high)

{

mid=(low+high)/2;printf(“ 第%d

次

比

较

:在[%d,%d]R[%d]:%dn”,++count,low,high,mid,R[mid].key);

if(R[mid].key==k)

//查找成功返回

return mid;

if(R[mid].key>k)

//继续在R[low..mid-1]中查找

high=mid-1;

else

low=mid+1;

//继续在R[mid+1..high]中查找 } return-1;} void main(){ SeqList R;KeyType k=9;int a[]={1,2,3,4,5,6,7,8,9,10},i,n=10;for(i=0;i

//建立顺序表

R[i].key=a[i];printf(“关键字序列:”);for(i=0;i

比

较

元

素

中

} else printf(“元素%d的位置是%dn”,k,i);printf(“元素%d不在表中n”,k);

截图如下：

实验题9.3 设计一个程序exp9-3.cpp，输出在顺序表{8，14，6，9，10,22,34,18,19,31,40,38,54,66,46,71,78,68,80,85,100,94,88,96,87}中采用分块查找法查找（每块的块长为5，共5块）关键字46的过程。

程序如下：

//文件名:exp9-3.cpp #include #define MAXL 100 #define MAXI 20 typedef int KeyType;typedef char InfoType[10];typedef struct {

KeyType key;

//KeyType为关键字的数据类型

//定义表中最多记录个数

//定义索引表的最大长度

InfoType data;

//其他数据 } NodeType;typedef NodeType SeqList[MAXL];typedef struct {

KeyType key;int link;

//KeyType为关键字的类型 //指向分块的起始下标

//顺序表类型

} IdxType;typedef IdxType IDX[MAXI];

//索引表类型

int IdxSearch(IDX I,int m,SeqList R,int n,KeyType k)//分块查找算法 { int low=0,high=m-1,mid,i,count1=0,count2=0;int b=n/m;

//b为每块的记录个数

printf(“二分查找n”);while(low<=high)

//在索引表中进行二分查找,找到的位置存放在low中

{

mid=(low+high)/2;printf(“ 第%d

次

比

较

:在[%d,%d]

中

比

较

元R[%d]:%dn”,count1+1,low,high,mid,R[mid].key);

if(I[mid].key>=k)

high=mid-1;

else

low=mid+1;

count1++;

//累计在索引表中的比较次数

} if(low

//在索引表中查找成功后,再在线性表中进行顺序查找

{

printf(“比较%d次,在第%d块中查找元素%dn”,count1,low,k);

i=I[low].link;

printf(“顺序查找:n

”);

while(i<=I[low].link+b-1 && R[i].key!=k)

{

i++;count2++;

printf(“%d ”,R[i].key);} //count2累计在顺序表对应块中的比较次数

printf(“n”);

printf(“比较%d次,在顺序表中查找元素%dn”,count2,k);

if(i<=I[low].link+b-1)

return i;

else

return-1;}

素 } return-1;void main(){

} SeqList R;KeyType k=46;IDX I;int a[]={8,14,6,9,10,22,34,18,19,31,40,38,54,66,46,71,78,68,80,85,100,94,88,96,87},i;for(i=0;i<25;i++)R[i].key=a[i];

//建立顺序表

I[0].key=14;I[0].link=0;I[1].key=34;I[1].link=4;I[2].key=66;I[2].link=10;I[3].key=85;I[3].link=15;I[4].key=100;I[4].link=20;if((i=IdxSearch(I,5,R,25,k))!=-1)else printf(“元素%d不在表中n”,k);printf(“元素%d的位置是%dn”,k,i);printf(“n”);

篇3：查找 实验报告

在运营商大力建设宽带网络背景下, 国内FTTx建设正在加速, 这也推动了ODN (无源光配线网络) 市场快速发展。上海电信副总工张军告诉记者, 相对于EPON和GPON技术的选择, 建设一个适合于各种PON技术的ODN网络更为重要。而ODN网络的建设尚存多个难点, 即缺乏统一的ODN网络建设标准和产品标准、老区光缆入户难、ODN网络故障定位难等。

其中, 如何解决ODN网络故障定位难的问题, 业界提出较多方案。近日, 中国电信在安徽宣城与合作伙伴完成了全球首个iODN解决方案商用试验局, 据悉, iODN可以有效帮助运营商解决该问题, 该试验局的成功建设标志着以电子标签 (eID) 为关键技术的智能ODN解决方案已经达到可正式商用水准。

ODN面临故障查找难题

ODN是光纤网络建设中的难点和重点。据业内人士分析, ODN网络建设成本高昂, 最高可占FTTH总体投资的50%～70%, 是FTTx投资的重点。另外, 随着各类业务对于带宽的要求越来越高, 无论未来采用哪种PON技术, 主设备的生命周期有多长, ODN网络都需要支撑宽带网络的长期发展。

ODN如此重要, 却是FTTx管理的难点。据悉, ODN与现有铜线网络相比有一些相似之处, 但更多的是不同。首先表现在相比铜线简单的P2P结构, ODN多采用P2MP拓扑, 网络中的接续节点多, 网络管理复杂。“传统光纤网络的部署是靠手写标识, 人工的校验和录入, 这样带来的问题是数据错误率达到20%, 故障难以精确地位, 所以运营商维护成本十分高昂, 利用效率非常低。”华为网络产品线总裁查均如是表示。

另外, ODN网络光纤比铜线敏感, 很容易受损 (例如施工误操作、动物嘶咬等) 。“ODN属于全程无源网络, 故障通常为光纤断裂、接头污损或松动等原因造成的通信中断。”中国电信一位内部人士表示。

国内外方案尚不完善

那么在大力发展光网城市的大背景下, 中国电信是如何ODN考虑故障定位问题呢?上述电信人士表示, 在ODN网络中, 故障定位的判断比故障类型的判断更加重要。目前行业内对故障定位判断可分为两种, 即故障段的判断和故障点的判断。

故障段判断的实现方式通常基于PON系统的网管功能, 通过网管系统中OLT和ONU中断的告警分析可能出现故障的光缆段落, 再由一线维护人员采用手持OTDR对该段光纤进行测量, 判断光纤故障点的位置。“这种故障定位方法比较成熟, 部署成本较低, 是目前国内应用较广泛的故障定位方式, 但无法定位故障点的准确位置。”上述电信人士表示。

据悉, 对于同样的问题, 日韩运营商大量应用较为成熟的方法是“OTDR集中在线测试”, 即在OLT PON端口侧通过合波器和光开关矩阵在PON系统中插入特定波长的光信号, 根据反射回来的光波判断故障点的位置, 目前厂家宣称的定位精度可达6m。上述电信人士则指出, 该方案对ODN规划建设的要求更加复杂, 总体实现成本高, 对于大分光比情况下分支光纤的故障定位精度有限, 目前还不具备在国内广泛推广的条件。

因此, 对ODN进行高效的建设、运营和维护需要一套智能、准确的管理解决方案, 确保ODN网络得到充分利用, 有效保护长期投资。

i ODN方案受认可

业界厂商提供较多针对ODN故障查找等完善的方案, 而华为公司表示其iODN (intelligent ODN) 解决方案具有较大的优势。据了解, 中国电信在安徽的iODN实验局就是和华为共同开展的。查均介绍, 华为iODN解决方案实现了无源光网的自动管理, 通过引入eID, 在不改变ODN网络无源属性的基础上, 可实现光纤连接关系自动识别管理、光纤连接操作智能指示、分光器智能管理等众多功能。从而, iODN方案可帮助运营商实现光纤自动化查找及操作精确记录, 实现FTTH高效部署及光纤故障准确定位。

据了解, iODN的核心思想是在不改变ODN无源网络特性的前提下, 为网络增加一定的智能特性, 例如光纤连接的识别和管理、光纤智能指示、分光器智能管理等, 同时在解决方案中引入现场工具PDA。在PDA的配合下, 通过广域无线网络或有线宽带网络实现ODN网络与存量管理系统实时互通;通过USB接口, PDA与iODN实现互通, 并为iODN提供临时电源。

篇4：实验力学实验报告

关键词 应变片;静态应变仪;动态应变仪;电桥;拉伸机

中图分类号 G64 文献标识码 A 文章编号 1673-9671-(2010)082-0141-01

1 标定试验

1.1 利用YE29003B应变标定仪标定动态应变仪

1)将YE29003B应变标定仪接入动态应变仪中:接完后相应的接口通道指示灯变暗,选折合适的拱桥电压和增益。本文选取:10V和2K欧姆,通道为3通道。

2)先将YE29003B应变标定仪拨到0欧姆,然后将动态应变仪选定通道电压调零,按下AUTO按钮机器会自动调零,若没有完全为零,可以用螺丝刀调节左边的微调FINE。

3)将YE29003B应变标定仪拨到1000欧姆,调节动态应变仪选定通道电压,并使其成为整数。

4)将YE29003B应变标定仪分别拨到800、600、400、200、0欧姆,记录每组的电压。

5)处理数据、得到回归曲线,由图可知应变与电压的关系。

1.2 模拟标定动态应变仪

本实验是用固定电阻和可变电阻接好电桥,模拟应变。因为应变片的工作原理就是,在某变形点应变片会随之变形,从而自身电阻改变,导致电桥不平衡。如此标定动态应变仪时完全可以用可调电阻代替应变片。

将可变电阻调到59880欧姆,将动态应变仪调零后接入刚调好的可变电阻,再将接入可变电阻后的电压调到整数。

依次调节可变电阻使分别其为74880欧姆、99880欧姆、149880欧姆、299880欧姆,并照如上操作得到五组电压如下表:,然后和YE29003B应变标定仪得出结论比较。

2 弯曲、拉伸试验

2.1 拉伸试验测量弹性模量E,泊松比v

1)应变片的粘贴、连接仪器。因为要测两个量故使用两片应变片,一片测纵向,另一片测横向,贴片贴好后将两片应变片接入YE2538A程控静态应变仪的两个不同通道中,并接成1/4桥电路,其中纵向应变接入通道1,横向应变片接入通道2。

2)试样加载、数据收集。摇动YE6253多功能材料力学试验台的加力手柄,使试样受拉,同时YE2538A程控静态应变仪会显示拉力和应变,选取合适的数据并记录。本文中以拉力为准,大约隔50N到100N记录一组数据。每次记录时先点通道1,记录纵向应变,再点通道2,记录横向应变。

3)数据处理,计算E和v。用Excel处理得到的数据并绘图,由竖向应变-应力图可得弹性模量E。由竖向应变和横向应变可得泊松比v。

2.2 弯曲试验正应力试验

1)试验用三点弯梁、应变片粘贴及电桥接法。本实验所用材料为已粘贴好五片应变片的三点弯曲梁:五片应变片(至上而下)本别测量上表面、中性层与上表面间、中性层、中性层与下表面间、下表面五个位置的应变,故有五片应变片接入YE2538A程控静态应变仪中,每片接入不同的通道中,规定应变片按至上而下的顺序接入通道1至通道5。

2)测量五点应变并与理论作比较。实验前先调零,测试时将拉力规定为某一特定值,本文使用600N,加载后先按通道1,記录上表面应变片的应变,以此类推测得其他点的应变。为消除误差,此过程复测量三次,每次拉力一定,取三组数据平均值。最后与理论值比较,得应变平均值,实际应力值,应力理论值和相对误差=|σ实-σ|/σ。

3 K片的测定

3.1 试验材料及方法描述

本实验用的是截面为18.1*18.1的正方形梁,简支梁表面放一幅梁,中点受集中力并用千分尺测梁中点位移。应变片贴在上下表面,测出梁上下表面的应变量。由《力学CAT基础》推导K片的值。

3.2 K片的推导

根据《力学CAT基础》,纯弯梁应变与应变片电阻率测量装置如下图所示。供货应变片粘贴在梁的纯弯区段内下表面,应变片纵向与梁的轴线方向重合,给定载荷后通过绕度计测量纯弯梁在加力线上的位移f,并由材料力学梁弯曲公式计算出应变片粘贴处梁的应变:

ε纵=fh/(l2+f2+fh)

1)用电阻仪表在贴片前测出应变片的阻值R;

2)将应变片和温度补偿片接入应变仪桥路调零后,按给定载荷P加载到位后测出应变仪的电压输出V;

3)将载荷卸去并使应变仪调零,随后对测量应变片电阻并联一个可调电阻仪,而后调并联电阻值到Rn,使对应应变仪的输出电压仍为V。此时应变片和外并电阻Rn的总电阻为:RRn/(R+Rn);

4)根据1)、3)步得到的电阻数值可以求出电阻变化率为:

ΔR/R=[RRn/(R+Rn)-R]/R=-R/(R+Rn)

5)灵敏系数Κ片的测量结果为:

Κ片=|ΔR/R|/ε纵=|ΔR/R|l2/fh

3.3 测量ε仪、千分表读数f

测出数据千分表读数f,ε仪(µε),ε纵(µε),△R/R,拉力(N)。由ε纵(µε)—△R/R曲线可得K片的大小。

4 COD引伸计标定、测量裂纹长度

4.1 COD引伸计侧线

因COD引伸计的五条输出线是混乱的我们必须对此整理,方法如下:

首先,COD引伸计内部桥路如下:

引线是4条桥线加一条地线,每个电阻120欧姆

如对于1线,将其和其他颜色的先接到欧姆表上若读数为90可知是1、4两端或1、3两端,二若欧姆表上若读数为120可知是1、2两端,这样便知道电桥的内部链接只要将对面的两端接入YE29003A盒中的V+、V—,或IN+、IN—中即可。

4.2 COD引伸计位移与动态应变仪电压的关系

在使用COD引伸计前必须标定引伸计位移与动态应变仪电压的关系,只有这样才可进行下一步试验。

4.3 测量裂纹长度

(本实验使用柔度法来测量裂纹长度,试验在弹性范围内进行,每次试验加载一次并马上卸载同时记录载荷与位移关系。

根据SET柔度公式:a/w=β0+β1µ 其中:β0=1.0056;β1=-2.8744

µ=1/(1+sqrt(E`*BefC));Bef=B-(B-Bn)/B

a是裂纹长度;B为式样的厚度,W为其宽度;测得B=2mm,W=18mm,E是弹性模量,C是测得的柔度即本实验的δ。

将数据代入得:a。

参考文献

[1]蔡立勋.力学CAT.西南交通大学.

篇5：数据结构实验报告-排序与查找

实

验

报

告

学生姓名：XXX 学 号：20***

指导教师：刘峤 实验地点：信软机房306

实验时间：2014/6/20

一、实验室名称：软件实验室

二、实验项目名称：数据结构与算法—排序与查找

三、实验学时：4

四、实验原理：

快速排序的基本思想是：通过一躺排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一不部分的所有数据都要小，然后再按次方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

假设要排序的数组是A[1]……A[N]，首先任意选取一个数据（通常选用第一个数据）作为关键数据，然后将所有比它的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一躺快速排序。一躺快速排序的算法是：

1）设置两个变量I、J，排序开始的时候I：=1，J：=N

2）以第一个数组元素作为关键数据，赋值给X，即X：=A[1]；

3）从J开始向前搜索，即（J：=J-1），找到第一个小于X的值，两者交换；

4）从I开始向后搜索，即（I：=I+1），找到第一个大于X的值，两者交换；

5）重复第3、4步，直到I=J。

二分法查找（折半查找）的基本思想：

（1）确定该区间的中点位置：mid=（low+high）/2 min代表区间中间的结点的位置，low代表区间最左结点位置，high代表区间最右结点位置

（2）将待查a值与结点mid的关键字（下面用R[mid].key）比较，若相等，则查找成功，否则确定新的查找区间：

A)如果R[mid].key>a，则由表的有序性可知，R[mid].key右侧的值都大于a，所以等于a的关键字如果存在，必然在R[mid].key左边的表中,这时high=mid-1;

B)如果R[mid].key

C)如果R[mid].key=a，则查找成功。

（3）下一次查找针对新的查找区间，重复步骤（1）和（2）

（4）在查找过程中，low逐步增加，high逐步减少，如果high

五、实验目的：

本实验通过实现快速排序和折半查找算法，使学生理解如何实现快速查找和排序的基本算法思想。通过练习，加强对算法的理解，提高编程能力。

六、实验内容：

（1）实现数据序列的输入;

（2）实现快速排序算法,并对输入的序列排序后输出；

（3）实现折半查找算法,并在步骤(2)排序后的序列上,进行任意地 查找,并输出查询结果。

七、实验器材（设备、元器件）：

八、数据结构及程序

#include

#define MAX_LEN 100

void Sort(int *data,int left,int right){

int i,j,temp;

i=left;

j=right;

temp=data[left];

if(left>right)

return;

while(i!=j){

while(data[j]>=temp&&j>i)

j--;

if(j>i)

data[i++]=data[j];

while(data[i]<=temp&&j>i)

i++;

if(j>i)

data[j--]=data[i];

}

data[i]=temp;

Sort(data,left,i-1);PC机一台，装有C/C++语言集成开发环境。

Sort(data,i+1,right);}

int Search(int *data,int start,int end,int key,int num){

int result;

int p =(start + end)/ 2;

if(data[p] == key&&start<=end){

result = p;

num++;

if(data[p] > key)

result = Search(data, start, p, key,num);

else

result = Search(data, p + 1, end, key,num);

return result;

}

else if(num==0&&start>end){

result =-1;

printf(“n 404 NO FOUNDn”);

return result;

}

else if(num!=0&&start>end){

result=-1;

if(num==1)

printf(“nFounded number only one”);

else

printf(“nFounded number more than one”);

return result;

}

else if(result!=-1){

if(data[p] > key)

result = Search(data, start, p-1, key, num);

else

result = Search(data, p + 1, end, key, num);

return result;

}

else {

result=-1;

return result;

} }

void loadFile(int *data,char *filename,int n){

int i;

FILE *pfile=NULL;

pfile=fopen(filename,“r”);

if(!pfile){

printf(“Open file failn”);

exit(0);

}

else

printf(“Open file success!n”);

for(i = 0;i < n;i++)

fscanf(pfile , “%d ”,&data[i]);}

int main(int argc, const char * argv[]){

int input=1,data[MAX_LEN],num=0,key=1,i,cmd;

char filename[100];

printf(“Choose Mode :n 1.Input Mode

2.File Moden”);

scanf(“%d”,&cmd);

if(cmd==1){

printf(“Input data :(Enter 0 to detemine)n”);

while(input!=0){

printf(“Enter the %d data :”,num+1);

scanf(“%d”,&input);

if(input!=0){

data[num]=input;

num++;

}

}

}

else{

printf(“nInput the address of the file: ”);

scanf(“%s”,filename);

printf(“nInput the number of elem: ”);

scanf(“%d”,&num);

loadFile(data,filename,--num);

}

Sort(data, 0, num);

printf(“nSort result: ”);

for(i=1;i<=num;i++)

printf(“%d ”,data[i]);

printf(“nn”);

while(key!=0){

printf(“nInput a key to search :(Enter 0 to detemine)”);

scanf(“%d”,&key);

if(key!=0)

Search(data, 0, num, key, 0);

}

return 0;}

九、程序运行结果： 1.打开程序：

2.尝试手动输入模式：

3.搜索已存在数： 4.搜索不存在数：

5.尝试文件读入模式并搜索

实验成功。

十、实验结论：

使用好的排序与查找算法对于程序的运行效率至关重要，一个好的算法，适合的算法能使计算机对数据的处理事半功倍，而选用错误的算法，不但可能事倍功半，还有可能造成不稳定因素。

快速排序的时间复杂度为n（log2n）,是排序算法中最为快速的一种，但是不稳定，对基本有序的序列效率较差。

二分查找算法在查找算法中，速度快，效率高，但是要求数据要有序。

十一、总结及心得体会：

当空间充足，对稳定性要求不高的情况，排序算法宜使用快速排序。

篇6：四风查找报告

党的群众路线教育活动开展以来，我认真学习上级文件精神，以及“三李”精神，观看《焦裕禄》、《吴仁宝》、《周恩来的四个昼夜》等教育影片，在此基础上，对照党章和廉政准则、对照八项规定、对照焦裕禄精神和三李精神，对照督导组和党委要求这四面镜子，自己找差距、理问题、“梳辫子”，发现：

一、个人在“四风”方面存在以下主要问题：

（一）、形式主义方面的问题

1、理论学习不深入、不系统，有的不求甚解，有的学而不用，在理论与实践结合上能力不强，在用科学的理论指导实践上效果不理想。

2、工作作风不实，求真务实的精神不够。对于部分次要的工作，有时首先想到的是怎样尽快完成，而不是怎样做到最好，特别是任务多、压力大的时候更是如此，有时存在着应付以求过关的想法，影响了工作效果，没有时刻以高标准严格要求自己。二是对有关的政策法规研究不够，工作方法较简单，同志间的思想交流不多，深入基层调查研究不够，对工作指导和督促还不够深入，致使工作效果不够理想。

（二）、官僚主义问题的具体表现

1、官僚主义方面：和村干部接触多，和群众接触少，深入群众不够。下村深入群众少，对群众的思想动态了解得 1

不及时不全面，解决群众迫切愿望的措施少。

2、对一些议题，有想法，有见解，或因顾虑，或碍于情面，不想坦言，不愿直说，随大流，“跟着走”，大家同意我同意。对个别重大问题，吃不透，拿不准，顾虑多，担心大，怕说错了话，表错了态，担责任，失面子，弄不好会影响发展和稳定，没有做到“知无不言、言无不尽”。

（三）、享乐主义问题的具体表现

1、虽然想干工作、想干好工作，但工作主动性不够，自我加压少、主动请缨少，奉命行事多，上级安排什么工作就干什么工作，对工作的全局性、前瞻性、创新性不够。

2、习惯按分工开展工作，“不分家”的责任感差，不想多管分外事，不愿多干分外活，一定程度存在着“管好自己分内之事”的想法。

（四）、奢靡之风问题自认为没有。

二、存在问题的主要原因

（一）、政治理论学习不够深入，政治理论修养不到家。

1、没有把理论学习放在应有的位置，凭兴趣、凭爱好、凭自觉，被动接受要我学的要求，而不是我要学的主动进取。

2、理论与实践隔离，忽视了理论与实践的辨证唯物关系，对政治理论的学习只满足于记住几条重要论断和几句讲话，缺乏系统性、经常性的深入学习，不能用马列主义的立

2场和观点分析问题，不具备用邓小平理论认识问题、解决问题的能力。

（二）、改造主观世界不够自觉主动，缺乏艰苦奋斗的精神。社会转型时期，传统的价值观受到很大冲击，权力和金钱崇拜逐步成为更多人的价值取向，也或多或少地影响到了自己。从理论上说，也知道共产党员要在改造客观世界的同时改造主观世界。但实际上是存在着轻重不同的问题的，以事务工作代替政治和党性锻炼，党性修养有放松，有进也考虑个人的荣辱进退了，考虑群众利益和全局利益少了。致使工作有时不够深入，满足于完成领导交办的任务，满足于面上不出问题，创新意识淡化，作的积极性、主动性、创造性减弱。左顾右盼，上下比较，还是自我感觉良好，比不上好的典型，但也还不算太差，安于现状，精神懈怠，不思进取。

（三）、群众工作经验缺乏，宗旨观念有所淡化。

对党的群众路线认识不深，对坚持改造自己的世界观、人生观和价值观的重要性认识不足，还没有真正在思想上、行动上树立起全心全意为人民服务的公仆意识。党的宗旨意识淡化，逐步远离了马克思主义的群众观点和党的群众路线，对自己人民公仆身份产生的模糊认识，颠倒了党和群众的关系。在工作上群众观念淡薄，看不到群众的首创精神，指导工作主观意志成份多，为群众想的少、做的少，服务群

3众，缺乏真功夫。

三、整改措施

（一）、进一步加强理论学习，夯实理论功底。

提高自己的政治敏锐性和政治鉴别力，树立科学的世界观、人生观和价值观，要以解决思想和工作中存在的实际问题为出发点，以改进自己的工作作风和工作方式、提高工作成效为落脚点，特别要在理论联系实际、指导实践上下真功夫，不断提高理论学习的效果，实现理论与实践相统一。

（二）、改作风，强宗旨，树立无私奉献和艰苦奋斗的精神。要牢固树立全心全意为人民服务的思想，树立为党为人民无私奉献的精神，把个人的追求融入党的事业之中，坚持党的事业第一、人民的利益第一；保持思想道德的纯洁性，正确对待权力、金钱、名利，在生活上艰苦朴素，勤俭节约，不奢侈浪费；在工作作风上，要深入实际，联系群众，倾听群众意见，想群众之所想，急群众之所急，同群众建立鱼水关系；努力克服消极思维、模糊认识，破除急躁情绪，迎难而上，积极工作；要把加强宗旨意识和作风修养作为自己的终身课题，坚持下去。

（三）、保持清正廉洁，增强拒腐防变能力。

在当前社会还存在腐败现象情况下，要有真佛不破戒的修为，抗得起诱惑，耐得住寂寞，经得起考验，做到自重、白警、白省、自励，做到在拜金主义、享乐主义和极端个人

4主义的侵蚀面前一尘不染，一身正气；要加强道德修养，树立正确的利益观、荣辱观、道德观、人生观，追求积极向上的生活情趣，坚决抵制歪风邪气，始终做到清正廉洁，自觉与各种腐败现象作斗争，带头树立高度的责任感和敬业精神，尽心尽力把工作做好。

（四）、坚持务实创新，增强工作实效。