用有序链表实现集合抽象教据类型 first last last first 08+17233549+72 用带表头结点的有序链表表示集合 用有序链表来表示集合时,链表中的每个结 点表示集合的一个成员。 各结点所表示的成员,e1,…,en在链表中按 升序排列,即0<1<…< 集合成员可以无限增加。因此,用有序链表 可以表示无穷全集合的子集。 21
用有序链表实现集合抽象数据类型 • 用有序链表来表示集合时，链表中的每个结 点表示集合的一个成员。 • 各结点所表示的成员 e0 , e1 , …, en 在链表中按 升序排列，即 e0 < e1 < … < en。 • 集合成员可以无限增加。因此，用有序链表 可以表示无穷全集合的子集。 21 用带表头结点的有序链表表示集合 first first 08 17 23 35 49 72 last last
集合的有序链表类的定义 template <class t> struct SetNode i 集合的结点类定义 t datas 每个成员的数据 Setnode<T>ink:∥链接指针 Setnodeo: link ( null /构造函数 SetNode(const T& x, setnode<t> *next= NULL) data(x), link(next); /构造函数
集合的有序链表类的定义 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 i 集合的类定义 rivate SetNode<t> *first, *last /)序链表表头指针,表尾指针 public LinkedSet o i first=last=new SetNode<t>;j LinkedSset( LinkedSet<T>&R);/复制构造函数 LinkedSet o( make Empty; delete first;) void make Empty; ∥置空集合 bool addMember(const t& x); bool delmember(const T& x LinkedSet<T>& operator= LinkedSet<T>& ri LinkedSet<T>& operator + LinkedSet<t>& ri;
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>& ri bool contains( const TX);判x是否集合的成员 bool operator == LinkedSet<T>&r) /判集合this与R相等 bool min(T&x);∥回集合最小元素的值 bool max(T&x);/回集合最大元素的值 bool subSet LinkedSet<T > r); /判th是否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
表示集合的几个重载函数 a frst-17+35 Rrs-+08+17+2349 pb pc temp. first-+08+17233549 template <class t> Linkedset<t>& Linkedset<t> operator + linkedSet<T>&r)i /求集合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