Container---二维的动态数组

A.第二版

这个小程序应该是动态数组的第二个版本吧，因为，我所作的并不多，只是加了一个极其简单的remove的方法。有对模板类作了两个子类，分别是

整数子类IntList和整数子类的指针所组成的子类PtrList。这样就可以组成一个动态二维数组，而且每个数组都是动态的不定长度，你知道这个东

西有什么用吗？我还没有想好，不过，我是经常很讨厌为不定长度的多个数据用多维数组预分配巨大的内存的，同时，这个冬冬实际上可以作为搜索

的存储，比如BFS,或DFS，你总要来存，可是子节点长度不一，不是很讨厌吗？不过，话说回来了，那个时候，用这种复杂的类浪费内存可能比预分

配数组浪费的还要多。反正我也不知道为什么要写他，就算为了好玩吧，我现在什么东西都写不出来，实在很郁闷！

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

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

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

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

	继承的时候，必须传递子类的类型参数给父类，否则，你说教编译器怎么编法？这个道理，我写继承的时候才体会到的，算是收获吧。

3。 主要函数介绍：

	A. 这个函数是做什么用的？你知道数组里的元素如果是复杂的类或结构，在删除的时候，应该释放内存，这个就是做这个工作的地方了。

	virtual void onRemove(T ptr); //

4。 不足之处：

	A. 要能够继续嵌套，以便超过二维，达到无限维。

	B. 原来的基类里元素采用自然的大小比较，结果加一个指针进去，他去比较指针地址的大小，闹得很搞笑，结果加的元素位置乱七八糟。

	不过，也没有犯什么错就是了。不行，下个版本一定要让用户定义自己的比较大小的方法，类似回调函数那种。

#include <iostream>
#include <iomanip>

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);
	virtual void onRemove(T ptr);  //
	virtual void onDisplay(T ptr);  //derived class must implement their own methods

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);
	void remove(int index);
};


class IntList: public mylist<int>
{
protected:
	void onDisplay(int ptr);
};
	
class PtrList: public mylist<IntList*>
{
protected:
	void onRemove(IntList* ptr);
};

class Container
{
private:
	void onVisitItem(int data);
	void onVisitNode(IntList* ptr);
	PtrList lst;
public:
	int nodeCount();
	int itemCount(int node);
	void addItem(int node, int data);
	void addNode();
	int getItem(int node, int index);
	void eachNode();
	void eachItem(int node);
	void traverse();
};



int main()
{
	int array[20] = {21,31,24,51,42,3,23,5,45,6567,76,88,99,11,234, 3435,566,78,56,20};
	Container R;
	int count=0;
	for (int i=0; i<4; i++)
	{
		int bound;
		array[i]=i;
		R.addNode();
		bound = rand()%15;
		for (int j=0; j<bound; j++)
		{	
			count++;
			if (count==20)
			{
				break;
			}
			R.addItem(0, array[count]);
		}
	}
	R.traverse();

	return 0;
}

void Container::traverse()
{
	for (int i=0; i<lst.count(); i++)
	{
		eachItem(i);
	}
}

void Container::eachItem(int node)
{
	cout<<"node is:"<<node<<endl;
	cout<<"and itemcount is:"<<lst.items(node)->count()<<endl;
	onVisitNode(lst.items(node));
}

void Container::onVisitItem(int data)
{
	cout<<data<<endl;
}

void Container::onVisitNode(IntList* ptr)
{
	for (int i=0; i< ptr->count(); i++)
	{		
		onVisitItem(ptr->items(i));
	}
}

int Container::itemCount(int node)
{
	return lst.items(node)->count();
}

int Container::nodeCount()
{
	return lst.count();
}

void PtrList::onRemove(IntList* ptr)
{
	delete ptr;
}

void Container::addNode()
{
	IntList* ptr= new IntList;
	lst.add(ptr);
}

void Container::addItem(int node, int data)
{
	if (node <lst.count())
	{
		lst.items(node)->add(data);
	}
	else
	{
		cout<<"The node number is exceeding max!"<<endl;
	}
}

int Container::getItem(int node, int index)
{
	return lst.items(node)->items(index);
}

void IntList::onDisplay(int data)
{
	cout<<data;
}

template<class T>
void mylist<T>::onRemove(T ptr)
{
}

template<class T>
void mylist<T>::remove(int index)
{
	int temp= index;
	if (index<counter)
	{
		onRemove(items(index));
		while (temp<counter-1)
		{	
			
			items(temp) = items(temp+1);
			temp++;	
		}
		counter--;
	}
}

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>::onDisplay(T ptr)
{
//	cout<<ptr;
}


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:";
		onDisplay(flist[i]);
		cout<<endl;
	}
}

template<class T>
void mylist<T>::uninitialize()
{
	for (int i=0; i<counter; i++)
	{
		onRemove(items(i));
	}
	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)
	{
		//exception need to be handled here!!
		cout<<"Unable malloc memory for size of "<<SIZE<<endl;  		
	}
	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();
}

int array[20] = {21,31,24,51,42,3,23,5,45,6567,76,88,99,11,234, 3435,566,78,56,20};

The following is the output which is quite unpleasing.

node is:0
and itemcount is:8
11
20
56
78
99
234
566
3435
node is:1
and itemcount is:11
3
5
23
24
31
42
45
51
76
88
6567
node is:2
and itemcount is:0
node is:3
and itemcount is:0