查找技术实验——北京信息科技大学.doc

_实验四 查找技术实验北京信息科技大学计算机软件基础实验报告（二）By Dade实验一 顺序与折半查找#include stdio.h#define MAXLEN 10 /*n为查找表中元素个数的最大可能值*/struct elementint key; /*设关键字的类型为整型*/int otherterm; /*为说明起见，除关键字外只有一个整型数据项*/;typedef struct element DATATYPE; /定义结构体类型 DATATYPE tableMAXLEN;int n1=0,n2=0; int seqsearch1(DATATYPE A,int k) /*顺序查找函数*/ int i; i=0; while(Ai.key!=k)&(iMAXLEN) printf(%d ,Ai.key);i+;n1+; if(Ai.key=k) printf(%d ,Ai.key);n1+;return i; /*查找成功，返回被查元素在表中的相对位置*/ else return -1; /*查找失败，返回 -1*/int binsearch(DATATYPE A,int k) /*折半查找函数*/ int low,mid,high; low=0; high=MAXLEN-1; while(lowAmid.key) low=mid+1; else high=mid-1; return -1; /*查找失败，返回 -1*/main() /主函数 int j,m1,m2,b; for(j=0;jMAXLEN;j+) tablej.key=(j+1)*10+1; printf(在顺序表:n); for(j=0;jMAXLEN;j+) printf(%d ,tablej.key); printf(nn查找元素b:); scanf(%d,&b); printf(n(1)顺序查找：nn查找过程：); m1=seqsearch1(table,b); if(m1=-1)printf(nfail!n); else printf(nsuccess!n该元素的序号：%dn,m1+1); printf(比较次数：%dn,n1); printf(nn(2)折半查找：nn查找过程：); m2=binsearch(table,b); if(m2=-1)printf(nfail!n); else printf(nsuccess!n该元素的序号：%dn,m2+1); printf(比较次数：%dnnn,n2); 实验二 二叉排序树查找#include stdio.h #include stdlib.h#define N 6/*n为结点个数的最大值*/struct tnode /定义结构体类型 int data; struct tnode *lchild, *rchild;typedef struct tnode TNODE;int AN=45,24,53,13,30,85;int n=0; TNODE *create_binary_sort_tree() /*二叉排序树的生成函数*/ int i; TNODE *head,*s,*p,*q; head=NULL; for(i=0;idata=Ai; s-lchild=NULL; s-rchild=NULL; if(head=NULL) head=s; else p=head; while(p!=NULL) q=p;if(s-datadata) p=p-lchild;else p=p-rchild; if(s-datadata)q-lchild=s; elseq-rchild=s; return head;TNODE *bstsearch(TNODE *root,int k) /*二叉排序树的查找递归算法*/ if(root=NULL) return NULL;else if(root-data=k) printf(%d ,root-data);n+;return root; /*查找成功*/else if(root-datak) printf(%d ,root-data);n+;return bstsearch(root-lchild,k);/*查找左子树*/else printf(%d ,root-data);n+;return bstsearch(root-rchild,k);/*查找右子树*/void intrav(TNODE *bt) /中序遍历函数 if(bt!=NULL)intrav(bt-lchild); printf(%d ,bt-data); intrav(bt-rchild); return;main() /主函数 int b; TNODE *t=NULL,*m=NULL; printf(在顺序表：n45 24 53 13 30 85nn); t=create_binary_sort_tree(); /建立二叉树，用t指向 printf(查找元素b：); scanf(%d,&b); printf(n查找过程：); m=bstsearch(t,b); /将查找的结果放在m中 if(m!=NULL)printf(nnsuccess!nn); else