采用模板仿Delphi的TList的动态数组

A.第一版

这个小程序是最初的版本。

1。 程序基本说明：学计算机的人应该都用过数组吧，如果是静态数组，长度是固定的，一旦元素个数超过就麻烦了，而且数组元素类型是声

	明的时候确定的实在不方便。Delphi里的TList还有排序的功能，每添加一个新元素自动按照顺序进行插入，非常的方便。本程序就是

	采用模板技术的类，使得类型灵活，数组长度动态增加，不受限制，增加查找功能，新增元素自动按照升序排列自动进行插入动作。

2。 程序思路：我以前在正航时候看过Delphi的TList的源代码，其实不复杂，只不过，每次增加长度时候，Delphi增加的是2的n次方。

3。 主要函数介绍：

	A. 先调用locate找到合适的位置，（也就进行了排序）在判断不存在相同元素后在找到的位置插入。

	void add(T ptr);

    B. 插入操作里，对空数组单独处理，（这一点我还想不出好办法，你是否有好主意？）。

    template<class T>
    void mylist<T>::insert(int index, T ptr)

4。 不足之处：

	A. 应该再加一个类的排序方法，因为，如果用户把一个数组的所有元素都赋给我的list，就有排序的需求了，我想把我的QuickSort

	写成一个类，来嵌入这里。

	B. 元素的大小比较，和升序，降序要可以选择，我想让用户以函数指针的形式传入大小比较的方法。

#include <iostream>
#include <iomanip>
#include <math.h>
#include <ctime>


using namespace std;


template<class T>
class mylist
{
private:
	T *flist;
	int LENGTH;
	int SIZE;
	int counter;
protected:
	void uninitialize();
	void initialize();
	bool checksize();
	void expand();
	int locate(T ptr);
public:
	mylist();
	~mylist();
	void add(T ptr);
	bool find(T ptr);
	void display();
	int count();
	T& items(int index);
	void insert(int index, T ptr);

};


int main()
{
	
	mylist<char> mlst;

	srand(time(0));
	for (int i=0; i< 10; i++)
	{
		mlst.add((char)('A'+rand()%26));
		mlst.add((char)('a'+rand()%26));
	}
	mlst.display();
	cout<<"\nTotal item number is: "<<mlst.count()<<endl;

	return 0;
}


template<class T>
void mylist<T>::insert(int index, T ptr)
{
	if (!checksize())
		expand();

	if (counter == 0)
	{
		items(0) = ptr;
		counter++;
	}
	else
	{
		if (index>=0&& index<=counter)
		{
			int i=index;
			T hold1 = items(index), hold2= items(index+1);
			while (i<counter)
			{	
				hold2 = items(i+1);
				items(i+1) = hold1;
				hold1 = hold2;				
				i++;
			}
			items(index) = ptr; //any exception trap???
			counter++;
		}
	}
}
			
template<class T>
int mylist<T>::locate(T ptr)
{
	int index = 0;
	while (items(index) <ptr &&index <counter)
	{
		index++;
	}
	return index;
}



template<class T>
bool mylist<T>::find(T ptr)
{
	int index = 0;

	index = locate(ptr);
	if (index == counter)
	{
		return false;
	}
	else
	{
		return (items(index) == ptr);
	}
}


template<class T>
int mylist<T>::count()
{
	return counter;
}

template<class T>
T& mylist<T>::items(int index)
{
	return flist[index];
}


template<class T>
void mylist<T>::display()
{
	cout<<setiosflags(ios::showpoint|ios::fixed);
	for (int i = 0; i < counter; i ++)
	{
		cout<<"Number "<<i<<" item is:"<<flist[i]<<endl;
	}
}

template<class T>
void mylist<T>::uninitialize()
{
	free(flist);
}

template<class T>
mylist<T>::~mylist()
{
	uninitialize();
}


template<class T>
void mylist<T>::add(T ptr)
{ 
	int index;
	index = locate(ptr);
	if (items(index)!=ptr)
	{
		insert(index, ptr);
	}
}

template<class T>
void mylist<T>::initialize()
{
	LENGTH = 10;
	SIZE = LENGTH;
	if ((flist =(T*)(malloc(sizeof(T) * SIZE)))==NULL)
		cout<<"Unable malloc memory for size of "<<SIZE<<endl;  //exception need to be handled here!!
	counter = 0;
}

template<class T>
bool mylist<T>::checksize()
{
	return (counter < SIZE);
}

template<class T>
void mylist<T>::expand()
{
	SIZE += LENGTH;
	if ((flist = (T*)(realloc(flist, sizeof(T) * SIZE)))== NULL)
		cout<<"Unable realloc memory for mylist of size "<<SIZE<<endl;
}

template<class T>
mylist<T>::mylist()
{
	initialize();
}

可以看到，随机产生的字符有重复的，所以只有17个。