第七章 7-1~7-8
7-1 设A={1,2,3},B={3,4,5}，求下列结果:
(1) A+B (2)A*B (3)A-B
(4) A.Contains(1) (5)A.AddMember(1)
(6) A.DelMember(1) (7)A.Min()

(1)A={1,2,3,4,5}
(2)A={3}
(3)A={1,2}
(4)1
(5)A={1,2,3}
(6)A={2,3}
(7)1


7-2 试编写一个算法，打印一个有穷集合中的所有成员。要求使用集合抽像数据类型中的基本操作。如果集合中包含有子集合，各个子集合之间没有重复的元素，采用什么结构比较合适。

采用广义表的结构会比较好，就像广义表的遍历操作一样，采用递归。
template< class Type >class Set{
  int Contains(const Type x);
  int SubSet(Set< Type >& right);
  int operator ==(Set< Type >&right);
  int Elemtype();
  Type GetData();
  char GetName();
  Set< Type >* GetSubSet();
  Set< Type >* GetNext();
  int IsEmpty();
};

ostream& operator<< (ostream& out,Set< Type >){
  t.traverse(out,t);return out;
}

void traverse(ostream&out, Set< Type >s){
  if(s.IsEmpty()==0){
    if(s.Elemtype()==0)out<< s.GetName()<< '{';
    else if(s.Elemtype()==1){
       out<< s.GetData;
       if(s.GetNext()!=NULL)out<< ',';
    }
    else{
         traverse(s.GetSubSet());
        if(s.GetNext()!=NULL)out<< ',';
    }
    traverse(s.GetNext());
  }
  else out<< '}';
}

除了最后一行外，全部照抄的参考答案。题目没意思，懒得做

7-3 当全集合可以映射成1到N之间的整数时，可以用位数组来表示它的任一子集合。当全集和是下列集合时，应当建立什么样的映射?
(1)整数0,1,...,99
(2)从n到m的所有整数，n<=m
(3) 整数n,n+2,n+4,...,n+2k
(4)字母'a','b','c',...,'z'
(5)两字母组成的字符串，其中每个字母取自'a','b','c',...,'z'.

假设不设置监哨点
(1) i={0,1,...,99}一一对应即可
(2) n->0,n+1->1,n+2->2,...,n+(m-n)->m-n 即可
(3) n->0,n+2->1,n+4->2,...,n+2k->k 即可
(4) 'a'->0,'b'->1,...,'z'->25
(5) 'aa'->0,'ab'->1,...,'zz'->675

7-7 给定一个用无序链表表示的集合，需要在其上执行operator+(),operator*(),operator-(),Contains(x),AddMember(x),DelMember(x),Min(),试写出它的类声明，并给出所有这些成员函数的实现。

思路：模仿教材中有序链表表示集合的类结构，写无序链表表示方法，无序链表在删除和加入时无序做过多操作，但是在求最大最小合并等操作里，要扫描全部链表。交并等集合运算时要注意是否有相同元素.
template < class Type >class SetList;
template< class Type >class SetNode{
//这部分参考教材
friend class SetList< Type >;
public:
  SetNode(const Type& item)
   :data(item),link(NULL);
private:
  Type data;
  SetNode< Type >* link;
};

template< class Type >class SetList{
//这部分参考教材
public:
  SetList();
  ~SetList();
  SetList< Type > &operator+(SetList< Type >& right);
  SetList< Type > &operator*(SetList< Type >& right); 
  SetList< Type > &operator-(SetList< Type >& right); 
  int Contains(const Type &x);
  int AddMember(const Type &x);
  int DelMember(const Type &x);
  Type & Min();
private:
  SetNode< Type > *first,*last;
}

template< class Type >SetList< Type >& SetList< Type >
  ::operator+(SetList< Type >& right){
  SetNode< Type > *pb=right.first->link; //目标链
  SetNode< Type > *tmp=pa=first->link;   //tmp暂存first
  SetNode< Type > *pc=first;             //新加入
  int diff;                 //判断元素是否在A集合中出现
  while(pb!=NULL){
    diff=1;              //初始置为 不在A集合中出现
    for(pa=tmp;pa=pa->link;pa!=NULL)
      if(pb->data==pa->data){ 
  //如果相等,pa直接到链尾
        pa=last->link;
        diff=0;
      }
    if(diff==1)
      pc=pc->link=pb;    //加入pb
    pb=pb->link;
  }
  pc->link=tmp;          
//原来的A链加入新链的链尾
  return * this;
}

template< class Type >SetList< Type >& SetList< Type >
  ::operator*(SetList< Type >& right){
  SetNode< Type > *pb=right.first->link; //目标链
  SetNode< Type > *tmp=pa=first->link;   //tmp暂存first
  SetNode< Type > *pc=first;             //新加入
  int diff;                 //判断元素是否在A集合中出现
  while(pb!=NULL){
    diff=1;              //初始置为 不在A集合中出现
    for(pa=tmp;pa=pa->link;pa!=NULL)
      if(pb->data==pa->data){ 
  //如果相等,pa直接到链尾
        pa=last->link;
        diff=0;
      }
    if(diff==0)
      pc=pc->link=pb;    //加入pb
    pb=pb->link;
  }
  return * this;
}

template< class Type >SetList< Type >& SetList< Type >
  ::operator-(SetList< Type >& right){
  SetNode< Type > *pb=right.first->link; //目标链
  SetNode< Type > *pa=first;   //this链
  SetNode< Type > *tmp;             
  while(pb!=NULL){
    for(pa=first;pa=pa->link;pa->link!=NULL)
      if(pa->link->data==pb->data){
    如果B中有元素与A相等，则删去A中的该元素
         tmp=pa->link;
         pa->link=pa->link-link;
         delete tmp;
         pa=last;
      }
    pb=pb->link;
  }
  return * this;
}

template< class Type >int SetList< Type >
  ::Contains(const Type &x){
  SetNode< Type > *p=first->link;
  while(p!=NULL)
    if(p->data==x)
      return 1;
    else p=p->link;
  return 0;
}

template< class Type >int SetList< Type >
  ::AddMember(const Type &x){
  int i=Contains(x);
  if(i==1)
    return 0;
  else{
    last->link=new SetNode(x);
    last=last->link;
    return 1;
  }
}

template< class Type >int SetList< Type >
  ::DelMember(const Type &x){
  SetNode< Type > *p=first->link,*q=first;
  while(p!=NULL){
    if(p->data==x){
      q->link=p->link;
      if(p==last)last=q;
      delete p;
      return 1;
    }
    else{
      p=p->link;
      q=q->link;
    }
  }
  return 0;
}

template< class Type >Type& SetList< Type >::Min(){
//求集合中的最小元素.
  SetNode< Type > *p=first->link;
  if(p==NULL){
//如果是空表返回错误；
    cout<< "空表"<< endl;
    return;
  }
  Type minnum=p->data;
  p=p->link;
  while(p!=NULL){
    if(minnum > p->data)
      minnum=p->data
    p=p->link;
  }
  return minnum;
}
22:13 | Category: | 0 评论

Comments (0)

发表评论