学步园

--------------------------------------------------------------------------------
标题: 查找相同项的双螺旋匹配算法
作者: 叶飞虎
日期: 2012.07.16
--------------------------------------------------------------------------------

已知:
    有两个列表 List1 和 List2, 列表中没有相同项且已经排序

问题:
    输出两个列表的所有相同项

双螺旋匹配算法示例如下:

// 二分查找函数
bool Find(long* AList, long AFrom, long ATo, long AValue, long& AIndex)
{
   // 初始化
   bool result = false;
   long intMid;

   // 循环比较
   while (AFrom <= ATo)
   {
      intMid   = (AFrom + ATo) >> 1;
      if (AList[intMid] == AValue)
      {
         result= true;
         AFrom = intMid;
         break;
      }
      else if (AList[intMid] < AValue)
         AFrom = intMid + 1;
      else
         ATo   = intMid - 1;
   }

   // 最近索引项
   AIndex = AFrom;

   // 返回结果
   return result;
}

// 输出相同项, 返回相同项数
long OutSame(long* AList1, long* AList2, long ACount1, long ACount2)
{
   // 初始化
   long result = 0;
   long intTo1 = ACount1 - 1;
   long intTo2 = ACount2 - 1;
   long intNo1 = 0;
   long intNo2 = 0;
   long intIndex;

   // 循环查找
   while ((intNo1 < ACount1) && (intNo2 < ACount2))
      if (AList1[intNo1] == AList2[intNo2])
      {
         // 输出项: Output(...);
         intNo1++;
         intNo2++;
         result++;
      }
      else if (AList1[intNo1] < AList2[intNo2])
      {
         if (Find(AList1, intNo1 + 1, intTo1, AList2[intNo2], intIndex))
         {
            // 输出项: Output(...);
            intNo1 = intIndex + 1;
            intNo2++;
            result++;
         }
         else
         {
            intNo1 = intIndex;
            intNo2++;
         }
      }
      else if (Find(AList2, intNo2 + 1, intTo2, AList1[intNo1], intIndex))
      {
         // 输出项: Output(...);
         intNo2 = intIndex + 1;
         intNo1++;
         result++;
      }
      else
      {
         intNo2 = intIndex;
         intNo1++;
      }

   // 返回结果
   return result;
}