www.gusucode.com > 《C++高级语言程序设计》PPT及全书例子源代码-源码程序 > 《C++高级语言程序设计》PPT及全书例子源代码-源码程序/code/C++例题程序/第5章/s5_6/smain5_6.cpp

    //Download by http://www.NewXing.com
//主文件
//文件名：s5_6\smain5_6.cpp
//类声明及实现文件，对类模板，类的声明和实现放在同一个文件中

//编译预处理语句：如果未定义__SCLASS5_6_T_H__则定义它，
//直到遇到#endif结束

#ifndef __SCLASS5_6_T_H__ 
#define __SCLASS5_6_T_H__ 

#include <iostream>  		//包含头文件。使用iostream库

using namespace std; 		//使用std命名空间

//定义链表的结点结构类
class SNode
{

public:
	SNode( int value );
	~SNode( ){ };
	
	//公有数据，方便后面取值
	int m_value;		//结点值
	SNode *m_next;		//结点后继，指向下一个结点的指针
};

//定义链表的类模板
template <class Type>
class TList
{
public:
	TList( );						//构造函数
	~TList( );						//析构函数

	virtual bool Insert( Type value );	//在链表头部插入一个结点
	bool Delete( Type value );			//从链表中删除值为value的一个结点
	bool Contain( Type value );			//判断链表中是否包含某结点
	void Print( );					//输出链表结点的值
protected:
	SNode *m_head;					//设置为只有头指针的单向链表
};

//定义集合类模板--集合与链表采用同样的组织方式，如图5.1所示
//但是链表和集合德概念不同：集合中不允许有重复的结点
template<class Type>
class TSet : public TList<Type>
{
public:
	bool Insert( Type value );	//在集合中重载插入方法，插入前先判断结点是否已经存在
};

#endif   					//结束编译预处理 

//结点类构造函数
SNode::SNode( int value )
{
	m_value = value;			//结点值
	m_next = NULL;				//结点后继
}

//构造函数
template <class Type>
TList<Type>::TList( )
{
	m_head = NULL;			//链表头
}

//链表析构函数。在析构函数中需要delete所有还在链表中的结点
template <class Type>
TList<Type>::~TList( )
{
	SNode *p = m_head;			//
	for (  ; p != NULL;  )		//直到结点不为空
	{
		m_head = p->m_next;		//头结点指向下一个结点，作为新的头结点
		delete p;				//释放p所指向的结点
		p = m_head;			//p指向新的头结点
	}
}

//在链表头部插入
template <class Type>
bool TList<Type>::Insert( Type value )
{
	SNode  *pTemp = new SNode( value );		//构造一个新结点
	if ( pTemp == NULL )					//结点空间申请不成功,退出
	{
		return false;
	}
	
	pTemp->m_next = m_head;		//新结点的m_next指针指向头结点原来所指的结点
	m_head = pTemp;				//头结点改为新生成的结点
	return true;
}

template <class Type>
bool TList<Type>::Delete( Type value )
{
	SNode *p1, *p2;		//申请两个结点指针，用于结点操作时
	//要遍历整个链表以查找其中是否包含有结点值为value的结点
	//但是一次遍历只能够删除一个值为value的结点。
	//如果在链表中有多个值相同的结点，需要分别删除。
	if ( m_head->m_value == value )		//如果头结点就是要找的结点，直接删除
	{
		p1 = m_head->m_next;			//p1指向头结点的后继结点
		delete m_head;				//释放头结点
		m_head = p1;				//p1成为新的头结点，即原头结点的后继成为新的头结点
		return true;				//返回真
	}
	else							//要删除的结点非头结点
	{
		for ( p1 = m_head, p2 = m_head->m_next; p2 != NULL;   )//遍历链表
		{
			if ( p2->m_value == value )		//如果找到，则释放该结点，并结束遍历
			{
				p1->m_next = p2->m_next;	//p1指向p2的下一个结点
				delete p2;				//释放p2
				p2 = NULL;				//让p2指向NULL，该步骤通常很有必要
				return true;				//结束遍历。
			}
			else						//如果该结点不是要找的结点，则p1,p2向后遍历
			{
				p1 = p1->m_next;		//p1指向其后继
				p2 = p2->m_next;		//p2指向其后继
			}
		}
	}
	return false;						//没有找到需要的结点，返回false
}

template <class Type>
bool TList<Type>::Contain( Type value )
{
	//遍历链表以查找其中是否包含有结点值为value的结点，有返回true，没有返回false
	for ( SNode  *p = m_head; p != NULL; p = p->m_next )
	{
		if ( p->m_value == value )			//找到该结点，返回true
		{
			return true;
		}
	}
	return false;
}

//显示表中的结点数据
template <class Type>
void TList<Type>::Print( )
{
	cout << "结点的值依次为：";
	//遍历链表以读出每一个结点的值并在终端上显示。
	for ( SNode  *p = m_head; p != NULL; p = p->m_next )
	{
		cout << " " << p->m_value << "; ";      //显示结点值
	}
	cout << endl;								//结束输出流
}


//集合类的结点插入方法
template <class Type>
bool TSet<Type>::Insert( Type value )
{
	//集合中无值为value的结点，才可以作插入操作，否则直接返回false。插入失败也返回false
	if ( !( TList<Type>::Contain( value ) )&&( TList<Type>::Insert( value ) ) )
	{
		return true;
	}
	return false;
}


//主测试程序
void main( )  
{
	TList<int> sIntList;
	sIntList.Insert( 12 );
	sIntList.Insert( 24 );		//在链表sIntList中，两次插入24
	sIntList.Insert( 48 );
	sIntList.Insert( 96 );
	sIntList.Insert( 24 );		//在链表sIntList中，两次插入24
	sIntList.Print( );

	sIntList.Delete( 24 );		//删除一次24
	sIntList.Print( );

	TSet<int> sIntSet;
	sIntSet.Insert( 12 );
	sIntSet.Insert( 24 );		//在集合sIntList中，两次插入24
	sIntSet.Insert( 48 );
	sIntSet.Insert( 96 );
	sIntSet.Insert( 24 );		//在集合sIntList中，两次插入24
	sIntSet.Print( );

	sIntSet.Delete( 24 );		//删除一次24
	sIntSet.Print( );

	cin.get( );
}