New Page 1

    采用模板仿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个。