会计学8.1查找(cházhǎo)的基本概念查找：根据给定的关键字值，在查找表中确定一个其关键字与给定值相同的数据元素，并返回该数据元素在查找表中的位置。若找到相应的数据元素，则称查找是成功的，否则称查找是失败的，此时(cǐshí)应返回空地址及失败信息，并可根据要求插入这个不存在的数据元素。8.2静态(jìngtài)查找表//静态查找表的顺序存储结构typedefstruct{ElemType*elem;//数据元素存储空间基址，建//表时按实际长度分配(fēnpèi)，0号单元留空intlength;//表长度}SSTable;基于顺序结构的算法如下：intSearch_Seq(SSTableST,KeyTypekey){//在顺序表ST中顺序查找其关键字等于key的数据元素。若找到，则函数值为该元素在表中的位置(wèizhi)，否则为0。算法9.1inti;ST.elem[0].key=key;//哨兵for(i=ST.length;!EQ(ST.elem[i].key,key);--i);//从后往前找returni;//找不到时，i为0}8.2.2有序表的查找(cházhǎo)图8.1折半(zhébàn)查找示意图折半查找(cházhǎo)的算法如下：8.2.3索引顺序(shùnxù)表的查找（分块查找法）图8.2分块查找(cházhǎo)法示意图分块查找的基本过程如下：(1)首先将待查关键字K与索引表中的关键字进行比较，以确定待查记录所在的块。具体的可用顺序(shùnxù)查找法或折半查找法进行。(2)用顺序(shùnxù)查找法在相应块内查找关键字为K的元素。例如，在上述索引顺序(shùnxù)表中查找36。首先，将36与索引表中的关键字进行比较，因为25＜36≤58，所以36在第二个块中，进一步在第二个块中顺序(shùnxù)查找，最后在8号单元中找到36。8.3动态(dòngtài)查找表8.3.1二叉排序(páixù)树图8.3二叉排序(páixù)树在下面讨论的二叉排序树的操作(cāozuò)中，使用二叉链表作为存储结构，其结点结构说明如下：1.二叉排序树的插入(chārù)和生成图8.4二叉排序树的建立(jiànlì)过程图8.5输入顺序不同(bùtónɡ)所建立的不同(bùtónɡ)二叉排序树2.二叉排序树的删除从二叉排序树中删除一个结点，不能把以该结点为根的子树都删去，只能删掉该结点，并且还应保证删除后所得的二叉树仍然(réngrán)满足二叉排序树的性质不变。也就是说，在二叉排序树中删去一个结点相当于删去有序序列中的一个结点。删除操作首先要查找，已确定被删结点是否在二叉排序树中。若不在，则不做任何操作；否则，假设要删除的结点为p，结点p的双亲结点为f，并假设结点p是结点f的左孩子（右孩子的情况类似）。下面分三种情况讨论(tǎolùn)：(1)若p为叶子结点，则可直接将其删除：f->lchild=NULL；free(p)；(2)若p结点只有左子树，或只有右子树，则可将p的左子树或右子树直接改为其双亲结点f的左子树，即：f->lchild=p->lchild（或f->lchild=p->rchild）；free(p)；(3)若p既有左子树，又有右子树，如图8.6(a)所示。此时有两种处理方法：方法1:首先找到p结点在中序序列中的直接前驱s结点，如图8.6(b)所示，然后(ránhòu)将p的左子树改为f的左子树，而将p的右子树改为s的右子树：f->lchild=p->lchild；s->rchild=p->rchild；free(p)；结果如图8.6(c)所示。方法2:首先找到p结点在中序序列中的直接前驱s结点，如图8.6(b)所示，然后(ránhòu)用s结点的值替代p结点的值，再将s结点删除，原s结点的左子树改为s的双亲结点q的右子树：p->data=s->data；q->rchild=s->lchild；free(s)；结果如图8.6(d)所示。图8.6二叉排序树删除(shānchú)示意3.二叉排序树的查找因为二叉排序树可看作是一个有序表，所以在二叉排序树上进行查找与折半查找类似，也是一个逐步缩小查找范围的过程。根据二叉排序树的特点，首先将待查关键字k与根结点关键字t进行比较，如果：(1）k=t，则返回(fǎnhuí)根结点地址；(2）k<t，则进一步查左子树；(3）k>t，则进一步查右子树。8.3.2平衡(pínghéng)二叉树图8.7平衡(pínghéng)与不平衡(pínghéng)的二叉排序树已知一棵平衡二叉排序树如图8.9（a）所示。在A的左子树的左子树上插入15后，导致失衡，如图8.9（b）所示。为