最近在研的项目有效率问题,自己动手写了个二分查询为基础的链表。记得上次写数据结构的东西大约在3年前,我还算个程序员么?
实现过程是痛苦的,实现结果是相当的丑陋的。。。容器类库用多了的必然结果,不上进的典型程序员。。。最终,还是找到角落里的《数据结构》。
。。。。。。。。。。。。
我还是总结下吧:
程序中为什么我想不到呢?没有书里面实现优美?那些东西是没想到,而且很重要的呢?
1、 from、to的初始化值的选定
2、二分查询主要是区间的查询,总是开始--结束,怎么保证始终有效
总结如下:
查询算法结构主要如下:
1、循环结束条件
2、循环变量(循环结束条件里的值)的变迁:可不要有死循环
3、开始状态的设定:初始值的设定
4、抽象的归纳:每次循环都应该是一个模式(如递归)
public class BinaryList
{
private List<IComp> _list = new List<IComp>();
/// <summary>
/// 找到最小匹配区间
/// </summary>
/// <param name="obj">要查询(插入)的对象</param>
/// <param name="from">区间开始索引</param>
/// <param name="to">区间结束索引</param>
/// <returns>是否空</returns>
private bool FindIntv(IComp obj, out int from, out int to)
{
//初值保证,能遍历所有元素
from = -1;
to = _list.Count;
if ( _list.Count < 1 )
{
return false;
}
//找到最小区间
while (from + 1 != to)
{
int middle = (from + to) / 2;
if (obj.IsBefore(_list[middle]))
{
to = middle;
}
else
from = middle;
}
//保证区间有效:当只有一个元素时
if ( from < 0)
{
from = 0;
}
if ( to >= _list.Count)
{
to = _list.Count - 1;
}
return true;
}
public void Add( IComp obj )
{
int from,to;
if( FindIntv(obj, out from, out to) )
{
if (obj.IsBefore(_list[from]))
{
_list.Insert(from, obj);
}
else if (obj.IsBefore(_list[to]))
{
_list.Insert(to, obj);
}
else
_list.Insert(to + 1, obj);
}
else
{
_list.Add(obj);
}
}
public bool IsExist( IComp obj )
{
int from, to;
if( FindIntv(obj, out from, out to))
{
return obj == _list[from] || obj == _list[to];
}
return false;
}
public void Display()
{
foreach (IComp s in _list)
Console.WriteLine(s.ToString());
}
}