分类： 算法&&ACM

1.为了保证范围不超过范围，我们需要在初始化的时候，让变量不超出范围。这样每次循环得到的新的范围是慢慢缩小的，不会越界。

2.迭代的二分查找。

int bs( int *a, int l, int r, int v ){
while( l <= r ){
if( a[l] == v ) return l;
int mid = (l+r)/2;
if( a[mid] < v ) l = mid+1;
if( a[mid] == v )r = mid;
if( a[mid] > v ) r = mid-1;
}
return -1;
}

这个二分可以返回所需要查询的元素第一次出现的位置，如果不存在，则返回-1.在每个循环内，我们假定元素第一次出现的范围是闭区间[l，r]内，当循环体内语句执行完之后，我们得到了一个新的区间。新的区间的范围是一直在收敛的（不会存在r，l执行完循环之后大小没有变化。），所以程序可以终止，得到正确结果。

3.将2的二分程序改写成递归的形式。

int bss( int *a, int l, int r, int v ){
if( l > r ) return -1;
if( a[l] == v ) return l;
int mid = (l+r)/2;
if( a[mid] < v ) return bss( a, mid+1, r, v );
if( a[mid] == v )return bss( a, l, mid, v );
if( a[mid] > v ) return bss( a, l, mid-1, v );
}

（更多…）

继续阅读 →

此List仿照的时STL中的list 写的，完成了一些基本功能。学习时候时按照书上（数据结构与算法分析，c++描述）学习的，了解到了迭代器的基本实现，感觉很有成就感。List用双向链表实现的，这样就可以方便地对迭代器应用++，–操作符。链表中又添加了两个节点tail和head，这样在插入删除元素的时候在操作上就统一了。

虽然说写出来了，而且经过简单的测试，没有啥问题（当然，我没有做任何的错误处理。。），但是感觉这种接口与实现分离的写法实在是太麻烦了。以后考虑把这些接口都放到注释中去，然后再在实际代码中实现，这样就不用去写一堆的template<typename Object>了。

前两天学习了git的用法，准备把自己的代码放到github上面，repo名称为fkcode。有兴趣的可以watch me。放代码~

#include<iostream>
template<typename Object>
class List{
private:
	struct Node;	//存放节点信息
	int theSize;	//List包含的元素的个数
	Node *head,*tail; //当容器为空的时候，有两个节点

	void init();
public:
	class const_iterator; //const迭带器
	class iterator;			//迭带器

	List();//constructor
	List( const List & rhs );
	~List();
	const List & operator= (const List & rhs );
	//the "Big Three"

	//basic routines, easy to understand by name
	iterator begin();
	iterator end();
	const_iterator begin() const;
	const_iterator end() const;

	int size() const;
	bool empty() const;
	void clear();

	Object & front();
	Object & back();
	const Object & front() const;
	const Object & back()  const;

	void push_front( const Object & x );
	void push_back(  const Object & x );
	void pop_front();
	void pop_back();

	iterator insert( iterator itr, const Object & x );
	iterator erase( iterator itr );
	iterator erase( iterator start, iterator end );

};


 （更多…）

	
继续阅读 →