linearlist_c++.cpp

设计模式：工厂模式、单例模式的基本实现

/************************************
* Copyright (c) 2008,LDCI
*
* 文件名称： LinearList_C++.cpp
* 摘要：
*	使用 C++ 语言实现对顺序存储结构的线性表
* 时间：
*	2008-6-10
* 作者：
*	左建华
************************************/
#ifndef __LINEARLIST_H__
#define __LINEARLIST_H__

#include <iostream>
using namespace std;

// 1. 线性表类
template<class T>
class LinearList {
public:
	LinearList(int = 10);
	~LinearList();
	bool IsEmpty() const;
	int Length() const;
	bool Find(int, T&) const; 
	int Search(const T&) const; 
	LinearList<T>& Delete(int, T&);
	LinearList<T>& Insert(int, const T&); 
	void Output(ostream&) const;

private:
	int length;
	int MaxSize;
	T *element;
};


// 2. 异常类
class Exception
{
	char *msg;
public:
	Exception(char *message)
	{
		msg = new char[strlen(message)+1];
		strcpy(msg, message);
	}
	virtual ~Exception()
	{
		delete []msg;
	}
	const char* GetExceptionInfomation()
	{
		return msg;
	}
};

// 地址越界异常类
class OutOfBoundsException: public Exception
{
public:
	OutOfBoundsException(char *message):Exception(message)
	{
	}
};

// 超过线性表长度异常类
class NoMemoryException: public Exception
{
public:
	NoMemoryException(char *message):Exception(message)
	{
	}
};


///////////// 线性表类具体实现 ////////////////


template<class T>
LinearList<T>::LinearList(int MaxListSize)
{
	// 基于公式的线性表的构造函数
	MaxSize = MaxListSize;
	element = new T[MaxSize];
	
	// 所有元素清零
	memset(element, 0, sizeof(T)*MaxSize);

	length = 0;
}


template<class T>
LinearList<T>::~LinearList()
{
	delete [] element;
}


template<class T>
bool LinearList<T>::IsEmpty() const 
{
	return (length == 0);
}


template<class T>
int LinearList<T>::Length() const 
{
	return length;
}


template<class T>
bool LinearList<T>::Find(int k, T& x) const
{ 
	//把第k个元素取至x中
	//如果不存在第k个元素则返回f a l s e，否则返回t r u e
	//位置从1开始
	if (k < 1 || k > length) 
		return false; // 不存在第k个元素

	x = element[k - 1];

	return true;
}


template<class T>
int LinearList<T>::Search(const T& x) const
{
	// 查找x，如果找到，则返回x所在的位置(从1开始)
	// 如果x不在表中，则返回-1
	for (int i = 0; i < length; i++)
		if (element[i] == x) 
			return ++i;

	return -1;
}


template<class T>
LinearList<T>& LinearList<T>::Delete(int k, T& x)
{
	
	// 把第k个元素放入x中，然后删除第k个元素
	// 如果不存在第k个元素，则引发异常O u t O f B o u n d s
	if( Find(k, x) ) 
	{
		
		// 把元素k+l, ...向前移动一个位置
		for (int i=k; i<length; i++)
		{
			element[i-1] = element[i];
		}
		

		length--;
		return *this;
	}
	
	else 
	{
		throw new OutOfBoundsException("The out of bounds exception ...");
	}
	
}


template<class T>
LinearList<T>& LinearList<T>::Insert(int k, const T& x)
{
	// 在第k个元素之后插入x
	// 如果不存在第k个元素，则引发异常O u t O f B o u n d s
	// 如果表已经满，则引发异常N o M e m
	// 可以插入第0个位置
	if (k < 0 || k > length) 
		throw new OutOfBoundsException("The out of bounds exception ...");

	if (length == MaxSize) 
		throw new NoMemoryException("The no memory exception ...");

	//向后移动一个位置
	for (int i = length-1; i >= k; i--)
		element[i+1] = element[i];

	element[k] = x;
	length++;

	return *this;
}


// 重载<<
template <class T>
ostream& operator<<(ostream& out, const LinearList<T>& x)
{
	x.Output(out); 
	return out;
}

template<class T>
void LinearList<T>::Output(ostream& out) const
{ 
	//把表输送至输出流
	for (int i = 0; i < length; i++)
	out << element[i] << " ";
}


#endif

//////////////  main.cpp   //////////////

int main()
{
	try
	{	
		LinearList<int> list(2);
	
		cout << "Length = " << list.Length() << endl;
		cout << "Is empty = " << list.IsEmpty() << endl;

		list.Insert(0, 100);
		list.Insert(1,30);
		list.Insert(2,330);

		cout << "List is : " << list << endl;
		cout << "Is empty = " << list.IsEmpty() << endl;

		int data = 0;

		list.Find(1,data);
		cout << "data = " << data << endl;
		cout << "Length = " << list.Length() << endl;
		
		list.Delete(1,data);
		cout << "List is : " << list << endl;

		cout << list.Search(303) << endl;
	}
	catch(Exception *exception)
	{
		cout << exception->GetExceptionInfomation() << endl;
		delete exception;
	}

	return 0;
}