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

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

//编译预处理语句：如果未定义__SCLASS5_6_0_T_H__则定义它，
//直到遇到#endif结束。
#ifndef __SCLASS5_6_0_T_H__ 
#define __SCLASS5_6_0_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;					//设置为只有头指针的单向链表。
};

//定义集合类模板--集合与链表采用同样的组织方式，如图6.1所示。
//但是链表和集合概念上有区别：集合中不允许有重复的节点。 
template<class Type>
class TSet : public TList<double>
{
public:
	bool Insert( double 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;						//没有找到需要的节点，返回假。
}

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 )			//找到有该节点，则返回。
		{
			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( double value )
{
	//集合中没有包含value值的节点，才可以作插入操作，否则直接返回假。插入失败也返回假。
	if ( !( TList<double>::Contain( value ) )&&( TList<double>::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<double> sIntSet;
	sIntSet.Insert( 12.0 );
	sIntSet.Insert( 24.0 );		//在集合sIntList中，两次插入24。
	sIntSet.Insert( 48.0 );
	sIntSet.Insert( 96.0 );
	sIntSet.Insert( 24.0 );		//在集合sIntList中，两次插入24。
	sIntSet.Print( );

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

	cin.get( );
}