用有序链表实现集合抽象数据类型 first last- last first-一 08 1723 35 49 72 用带表头结点的有序链表表示集合 用有序链表来表示集合时，链表中的每个结 点表示集合的一个成员。 各结点所表示的成员eo,e1,,en在链表中按 升序排列，即e<e1<.…<e 集合成员可以无限增加。因此，用有序链表 可以表示无穷全集合的子集。 21
用有序链表实现集合抽象数据类型 • 用有序链表来表示集合时，链表中的每个结 点表示集合的一个成员。 • 各结点所表示的成员 e0 , e1 , …, en 在链表中按 升序排列，即 e0 < e1 < … < en。 • 集合成员可以无限增加。因此，用有序链表 可以表示无穷全集合的子集。 21 用带表头结点的有序链表表示集合 first first 08 17 23 35 49 72 last last
集合的有序链表类的定义 template <class T> struct SetNode{ /集合的结点类定义 T data; 川每个成员的数据 SetNode<T>*link; 川链接指针 SetNode():link (NULL); 川构造数 SetNode (const T&x,SetNode<T>*next NULL) data (x),link (next); 川构造数 }; 22
集合的有序链表类的定义 template <class T> struct SetNode { //集合的结点类定义 T data; //每个成员的数据 SetNode<T> *link; //链接指针 SetNode() : link (NULL); //构造函数 SetNode (const T& x, SetNode<T> *next = NULL) : data (x), link (next); //构造函数 }; 22
template <class T> class LinkedSet /集合的类定义 private: SetNode<T>*first,*last; /有序链表表头指针，表尾指针 public: LinkedSet (first last new SetNode<T>;} LinkedSet(LinkedSet<-T>&R);/复制构造函数 LinkedSet (makeEmpty(;delete first; void makeEmpty(; 川置空集合 bool addMember (const T&x); bool delMember (const T&x); LinkedSet<T>&operator (LinkedSet<T>&R); LinkedSet<T>&operator (LinkedSet<T>&R); 23
template <class T> class LinkedSet { //集合的类定义 private: SetNode<T> *first, *last; //有序链表表头指针, 表尾指针 public: LinkedSet () { first = last = new SetNode<T>; } LinkedSet (LinkedSet<T>& R); //复制构造函数 ～LinkedSet () { makeEmpty(); delete first; } void makeEmpty(); //置空集合 bool addMember (const T& x); bool delMember (const T& x); LinkedSet<T>& operator = (LinkedSet<T>& R); LinkedSet<T>& operator + (LinkedSet<T>& R); 23
LinkedSet<T>&operator (LinkedSet<T>&R); LinkedSet<T>&operator -(LinkedSet<T>&R); bool Contains(const T x);/判x是否集合的成员 bool operator ==(LinkedSet<T>&R); /判集合this与R相等 bool Min (T&x); 川返回集合最小元素的值 bool Max (T&x); 川返回集合最大元素的值 bool subSet (LinkedSet<T >R); /判this是否R的子集 }; 24
LinkedSet<T>& operator * (LinkedSet<T>& R); LinkedSet<T>& operator - (LinkedSet<T>& R); bool Contains (const T x); //判x是否集合的成员 bool operator == (LinkedSet<T>& R); //判集合this与R相等 bool Min (T& x); //返回集合最小元素的值 bool Max (T& x); //返回集合最大元素的值 bool subSet (LinkedSet<T >& R); //判this是否R的子集 }; 24
表示集合的几个重载函数 pa first-17 35 R.first--081723+49 I pb temp.first--08 十17十23十35 -49 template <class T> LinkedSet<T>&LinkedSet<T>:: operator +(LinkedSet<T>&R) /求集合this与集合R的并 25
表示集合的几个重载函数 template <class T> LinkedSet<T>& LinkedSet<T>:: operator + (LinkedSet<T>& R) { //求集合this与集合R的并 25 first R.first 08 17 23 49 temp.first 23 17 35 pa pb pc 08 17 23 35 49