?? p216.cpp
字號:
#include "iostream.h"
template <class Type> class SetList; //用以表示集合的有序鏈表的類的前視定義
template <class Type> class SetNode { //集合的結點類定義
public:
SetNode ():link(NULL){};
SetNode (const Type & item ) : data (item), link (NULL){}; //構造函數
friend class SetList<Type>;
friend ostream& operator <<(ostream& strm, SetList<Type>& a);
private:
Type data; //每個成員的數據
SetNode<Type> *link; //鏈接指針
};
template <class Type> class SetList { //集合的類定義
public:
SetList ( ); //構造函數
void MakeEmpty ( ); //置空集合
int AddMember ( const Type & x ); //把新元素x加入到集合之中
int DelMember ( const Type & x ); //把集合中成員x刪去
void operator = ( SetList<Type> & right ); //復制集合right到this。
void operator + ( SetList<Type> & right ); //求集合this與集合right的并
void operator * ( SetList<Type> & right ); //求集合this與集合right的交
void operator - ( SetList<Type> & right ); //求集合this與集合right的差
int Contains ( const Type & x ); //判x是否集合的成員
int operator == ( SetList<Type> & right ); //判集合this與集合right相等
Type & Min ( ); //返回集合中的最小元素的值
Type & Max ( ); //返回集合中的最大元素的值
friend ostream& operator <<(ostream& strm, SetList<Type>& a);
private:
SetNode<Type> *first, *last; //有序鏈表的表頭指針, 表尾指針
}
template <class Type> void SetList<Type>::SetList ( ) {
//本操作建立集合鏈表的頭結點, 并將鏈表置空。
first = last = new SetNode<Type>(); first->link = NULL;
}
template <class Type> void SetList<Type>::MakeEmpty(void){
SetNode<Type> *tmp1=first->link,*tmp2;
first->link=NULL;
last=first;
while (tmp1)
{
tmp2=tmp1;
tmp1=tmp1->link;
delete tmp2;
}
}
template <class Type> int SetList<Type>::Contains ( const Type & x ) {
//測試函數: 如果x是集合的成員, 則函數返回1, 否則返回0。
SetNode<Type> *temp = first->link; //鏈的掃描指針
while ( temp != NULL && temp->data < x ) temp = temp->link; //循鏈搜索
if ( temp != NULL && temp->data == x ) return 1; //找到, 返回1
else return 0; //未找到, 返回0
}
template <class Type> int SetList<Type>::AddMember ( const Type & x ) {
//把新元素x加入到集合之中。若集合中已有此元素, 則函數返回0, 否則函數返回1。
SetNode<Type> *p = first->link, *q = first; //p是掃描指針, q是p的前驅
while ( p != NULL && p->data < x ) { q = p; p = p->link; } //循鏈掃描
if ( p != NULL && p->data == x ) return 0; //集合中已有此元素
SetNode<Type> *s = new SetNode<Type> (x); //創建數據值為x的新結點
s->link = p; q->link = s; //鏈入有序鏈表, 插入位置在q、p之間
if ( p == NULL ) last = s; //鏈到鏈尾時要改鏈尾指針
return 1;
}
template <class Type> int SetList<Type>::DelMember ( const Type & x ) {
//把集合中成員x刪去。若集合不空且元素x在集合中, 則函數返回1, 否則返回0。
SetNode<Type> *p = first->link, *q = first;
while ( p != NULL && p->data < x ) { q = p; p = p->link; } //循鏈掃描
if ( p != NULL && p->data == x ) { //找到
q->link = p->link; //重新鏈接, , x位置在p所指結點
if ( p == last ) last = q; //刪去鏈尾結點時要改鏈尾指針
delete p; return 1; //刪除含x結點
}
else return 0; //集合中無此元素
}
template <class Type> void SetList<Type>::operator = ( SetList<Type> & right ) {
//復制集合right到this。
SetNode<Type> *pb = right.first->link; //復制源集合
SetNode<Type> *pa = first = new SetNode<Type>; //復制目標集合, 創建表頭結點
while ( pb != NULL ) { //在鏈中逐個結點復制
pa->link = new SetNode<Type> (pb->data); //創建this鏈下一個新結點
pa = pa->link; pb = pb->link; // pa進到新結點位置, pb進到下一結點
}
pa->link = NULL; last = pa; //目標鏈表收尾
}
template <class Type> void SetList<Type>::operator + ( SetList<Type> & right ) {
//求集合this與集合right的并, 計算結果在this集合中, right集合不變。
SetNode<Type> *pb = right.first->link; //right集合的鏈掃描指針
SetNode<Type> *pa = first->link; //this集合的鏈掃描指針
SetNode<Type> *pc = first; //結果鏈的頭結點和存放指針
while ( pa != NULL && pb != NULL ) { //兩鏈數據兩兩比較
if ( pa->data == pb->data ) //兩集合共有元素
{ pc->link = pa; pa = pa->link; pb = pb->link; }
else if ( pa->data < pb->data )
{ pc->link = pa; pa = pa->link; } //this中元素值小
else //right集合中元素值小, 創建新結點, 鏈入結果鏈
{ pc->link = new SetNode<Type> (pb->data); pb = pb->link; }
pc = pc->link;
}
if ( pa != NULL ) pc->link = pa; //this集合未掃完, 鏈接
else { //right集合未掃完,
while ( pb != NULL ) //向this集合逐個復制
{ pc->link = new SetNode<Type> (pb->data); pc = pc->link; pb = pb->link; }
pc->link = NULL; last = pc; //鏈表收尾
}
}
template <class Type> void SetList<Type>::operator * ( SetList<Type> & right ) {
//求兩個集合的交, 結果保存在this集合中, right集合不變
SetNode<Type> *pb = right.first->link; //right集合的鏈掃描指針
SetNode<Type> *pa = first->link; //this集合的鏈掃描指針
SetNode<Type> *pc = first; //結果鏈的頭結點和存放指針
while ( pa != NULL && pb != NULL ) { //兩鏈數據兩兩比較
if ( pa->data == pb->data ) //兩集合公有的元素
{ pc = pc->link; pa = pa->link; pb = pb->link; }
else if ( pa->data < pb->data ) //this集合中元素值小, 刪去這個元素
{ pc->link = pa->link; delete pa; pa = pc->link; }
else pb = pb->link; //right集合中元素值小, pb指針進1
}
while ( pa != NULL ) //逐個刪去this集合中非公共元素
{ pc->link = pa->link; delete pa; pa = pc->link; }
last = pc; //置鏈尾指針
}
template <class Type> void SetList<Type>::operator - ( SetList<Type> & right ) {
//求集合this與集合right的差。結果保留在集合this中, 集合right不變。
SetNode<Type> *pb = right.first->link; //right集合的鏈掃描指針
SetNode<Type> *pa = first->link; //this集合的鏈掃描指針
SetNode<Type> *pc = first; //結果鏈的頭結點和存放指針
while ( pa != NULL && pb != NULL ) { //兩兩比較
if ( pa->data == pb->data ) //兩集合共有的元素, 從this鏈中刪去
{ pc->link = pa->link; delete pa; pa = pc->link; pb = pb->link; }
else if ( pa->data < pb->data ) //this集合中的元素值小, 保留
{ pc = pc->link; pa = pa->link; }
else pb = pb->link; //不要, 向前繼續檢測
}
if ( pa == NULL ) last = pc; //pa!=NULL時, 原來的last不變
}
template <class Type> int SetList<Type>::operator == ( SetList<Type> & right ) {
//當且僅當集合this與集合right相等時, 函數返回1, 否則返回0。
SetNode<Type> *pb = right.first->link; //right集合的鏈掃描指針
SetNode<Type> *pa = first->link; //this集合的鏈掃描指針
while ( pa != NULL && pb != NULL )
if ( pa->data == pb->data ) //相等, 繼續檢測
{ pa = pa->link; pb = pb->link; }
else return 0; //掃描途中不等時退出, 返回0
if ( pa != NULL || pb != NULL ) return 0; //鏈不等長時, 返回0
return 1;
}
template <class Type>
ostream& operator <<(ostream& strm, SetList<Type>& a)
{
SetNode<Type> *p=a.first;
if (a.first!=a.last)
{
do
{
p=p->link;
strm<<p->data<<' ';
}while (p!=a.last);
}
strm<<endl;
return strm;
}?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -