?? 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 + -