会计学术语：查找(检索)——根据给定的某个值，在表中确定一个关键字等于给定值的记录或数据元素关键字——是记录某个数据项的值，它可以唯一标识一个记录。次关键字——不能唯一的确定一个记录，但能确定表的一个子表。子表的元素个数应远少于表中元素数。为简化问题，将表中元素看成简单的整型数据，理解为关键字部分。8.1静态查找表顺序查找的平均时间为表长的一半。bin_search(st[],key,n){low=0;high=n-1;while(low<=high){mid=(low+high)/2;if(st[mid]==key)returnmid;elseif(st[mid]>key)high=mid-1;elselow=mid+1;}return-1;}3、分块查找123456789101112131415161718分块查找方法评价小结：时间：顺序查找最差，二分最好，分块介于两者之间空间：分块最大，需要增加索引数据的空间特点：1）顺序查找对表没有特殊要求2）分块时数据块之间在物理上可不连续。所以可以达到插入、删除数据只涉及对应的块；另外，增加了索引的维护。3）二分查找要求表有序，所以若表的元素的插入与删除很频繁，维持表有序的工作量极大。4）在表不大时，一般直接使用顺序查找。二分查找的C/C++接口#include<iostream.h>#include<stdlib.h>cmp(constvoid*a,constvoid*b){if(*(int*)a<*(int*)b)return-1;elseif(*(int*)a==*(int*)b)return0;elsereturn1;}voidmain(){intar[]={-2,3,6,9,10,21,22,34,56};int*p;intt;t=9;p=(int*)bsearch(&t,ar,sizeof(ar)/sizeof(int),sizeof(int),cmp);if(p!=NULL)cout<<*p<<endl;}8.2动态查找452、查找：步骤：若根结点的关键字值等于查找的关键字，成功。否则，若小于根结点的关键字值，递归查左子树。若大于根结点的关键字值，递归查右子树。若子树为空，查找不成功。3、插入算法：首先执行查找算法，找出被插结点的父亲结点。判断被插结点是其父亲结点的左、右儿子。将被插结点作为叶子结点插入。若二叉树为空。则首先单独生成根结点。注意：新插入的结点总是叶子结点。voidInsertBST(*&t，key)//在二叉排序树中插入查找关键字key{if(t==NULL){t=newBiTree;t->lchild=t->rchild=NULL;t->data=key;return;}if(key<t->data)InsertBST(t->lchild,key);elseInsertBST(t->rchild,key);}voidCreateBiTree(tree,d[],n）//n个数据在数组d中，tree为二叉排序树根{tree=NULL;for(i=0;i<n;i++)InsertBST(tree,d[i]);}在二叉排序树中删除结点的原则是：删除结点后仍是二叉排序树。（3）x即有左子树xL也有右子树xR二叉排序树的删除操作例子122被删结点的左、右子树皆不空voiddelete(*&p){if(p->rchild==NULL){q=p;p=p->lchild;deleteq;}elseif(p->lchild==NULL){q=p;p=p->rchild;deleteq;}else{q=p;s=p->lchild;while(s->rchild!=NULL){q=s;s=s->rchild;}p->data=s->data;if(q!=p)q->rchild=s->lchild;elseq->lchild=s->lchild;}deletes;}voiddelete(*&p){if(p->rchild==NULL){q=p;p=p->lchild;deleteq;}elseif(p->lchild==NULL){q=p;p=p->rchild;deleteq;}else{q=p;s=p->lchild;while(s->rchild!=NULL){q=s;s=s->rchild;}p->data=s->data;if(q!=p)q->rchild=s->lchild;elseq->lchild=s->lchild;}deletes;}vo