沈春元，张晓峰，李华君

(1.海军驻南京地区雷达系统军事代表室，南京 210003;2.中国船舶重工集团公司第七二四研究所，南京 210003)

0 引言

随着计算机的不断升级，关于信息的插入大多数采用的是遍历方式，在通常情况下很符合条件，其原理为:

(1）在信息库中查找是否有相同标识的信息，如果有转到(3），否则转到(2）;

(2）查找是否有空闲的位置，如果有转到(3），否则转到(4）;

(3）更新数据信息;

(4）满信息后，采用处理方式。

此算法的时间复杂度为O(2n）。在实际处理过程中，信息量越来越大，在一些强实时情况下，采用上述的算法很难达到要求。

本文提出的快速插入与搜索算法(Quick Insert and Search Algorithm，简写QISA）QISA算法主要包括快速插入算法(QIA）和快速搜索算法(QSA）。

1 快速插入算法

本文提出的快速插入算法(见图1），主要是基于双索引之上实时变化索引关系，快速达到空闲位置，其时间复杂度为O(1）。

图1中，索引表A 存放索引表B的位置信息，索引表B 存放索引表A 对应的位置信息，指针p为读指针指向当时可以写的位置，指针q为写指针指向索引表A中所要修改的位置。

图1 快速插入算法

图2 算法关系图

算法流程如下:

(1）初始化p和q 指向索引表A中的A1的位置，索引表A与索引表B 一一对应，如图1(b）所示;

(2）有信息输入时，直接索引到p所指定的位置，对应的索引表B中的信息为B［p］;

(3）第3个信息需要删除时(图2(a）），交换A［q］与A［Bi］中的位置信息，更新索引表A的值，其结果如图2(b）所示。

2 快速搜索算法

搜索算法实际上是根据初始条件和扩展规则构造一颗“解答树”并寻找符合目标状态的节点的过程。……