if（s.GetNext（）!
=NULL）out<<‘,’;
}
else{//子集合
traverse（s.GetSubSet（））;//输出子集合
if（s.GetNext（）!
=NULL）out<<‘,’;
}
traverse（s.GetNext（））;//向同一集合下一元素搜索
}
elseout<<‘}’;
}
如果集合中包含有子集合，各个子集合之间没有重复的元素，采用广义表结构比较合适。
也可以使用并查集结构。
7-3当全集合可以映射成1到N之间的整数时，可以用位数组来表示它的任一子集合。
当全集合是下列集合时，应当建立什么样的映射？
用映射对照表表示。
（1）整数0,1,…,99
（2）从n到m的所有整数，nm
（3）整数n,n+2,n+4,…,n+2k
（4）字母‘a’,‘b’,‘c’,…,‘z’
（5）两个字母组成的字符串,其中，每个字母取自‘a’,‘b’,‘c’,…,‘z’。
【解答】
（1）i→i的映射关系，i=0,1,2,…,99
（2）i→n-i的映射关系，i=n,n+1,n+2,…,m
0
1
2
m-n
n
n+1
n+2
…
m
（3）i→（i-n）/2的映射关系，i=n,n+2,n+4,…,n+2k
0
1
2
k
n
n+2
n+4
…
n+2k
（4）ord（c）→ord（c）-ord（'a'）的映射关系，c='a','b','c',…,'z'
0
1
2
25
'a'
'b'
'c'
…
'z'
（5）（ord（c1）-ord（'a'））*26+ord（c2）-ord（'a'）的映射关系，c1=c2='a','b','c',…,'z'
0
1
2
675
'aa'
'ab'
'ba'
…
'zz'
7-4试证明：
集合A是集合B的子集的充分必要条件是集合A和集合B的交集是A。
【证明】
必要条件：
因为集合A是集合B的子集，有AB，此时，对于任一xA，必有xB，因此可以推得xA∩B，就是说，如果A是B的子集，一定有A∩B=A。
充分条件：
如果集合A和集合B的交集A∩B是A，则对于任一xA，一定有xA∩B，因此可以推得xB，由此可得AB，即集合A是集合B的子集。
7-5试证明：
集合A是集合B的子集的充分必要条件是集合A和集合B的并集是B。
【证明】
必要条件：
因为集合A是集合B的子集，有AB，此时，对于任一xA，必有xB，它一定在A∪B中。
另一方面，对于那些x'A,但x'B的元素，它也必在A∪B中，因此可以得出结论：
凡是属于集合B的元素一定在A∪B中，A∪B=B。
充分条件：
如果存在元素xA且xB，有xA∪B，但这不符合集合A和集合B的并集A∪B是B的要求。
集合的并A∪B是集合B的要求表明，对于任一xA∪B，同时应有xB。
对于那些满足x'A的x'，既然x'A∪B，也应当x'B，因此，在此种情况下集合A应是集合B的子集。
7-6设+、*、-是集合的或、与、差运算，试举一个例子，验证
A+B=（A-B）+（B-A）+A*B
【解答】
若设集合A={1,3,4,7,9,15}，集合B={2,3,5,6,7,12,15,17}。
则
A+B={1,2,3,4,5,6,7,9,12,15,17}
又A*B={3,7,15},A–B={1,4,9},B–A={2,5,6,12,17}
则（A–B）+（B–A）+A*B={1,2,3,4,5,6,7,9,12,15,17}
有A+B=（A–B）+（B–A）+A*B。
7-7给定一个用无序链表表示的集合，需要在其上执行operator+（）,operator*（）,operator-（）,Contains（x）,AddMember（x）,DelMember（x）,Min（），试写出它的类声明，并给出所有这些成员函数的实现。
【解答】
下面给出用无序链表表示集合时的类的声明。
templateclassSet;//用以表示集合的无序链表的类的前视定义
templateclassSetNode{//集合的结点类定义
friendclassSetList;
private:
Typedata;//每个成员的数据
SetNode*link;//链接指针
public:
SetNode（constType&item）:
data（item）,link（NULL）;//构造函数
};
templateclassSet{//集合的类定义
private:
SetNode*first,*last;//无序链表的表头指针,表尾指针
public:
SetList（）{first=last=newSetNode（0）;}//构造函数
~SetList（）{MakeEmpty（）;deletefirst;}//析构函数
voidMakeEmpty（）;//置空集合
intAddMember（constType&x）;//把新元素x加入到集合之中
intDelMember（constType&x）;//把集合中成员x删去
Set&operator=（Set&right）;//复制集合right到this。
Set&operator+（Set&right）;//求集合this与集合right的并
Set&operator*（Set&right）;//求集合this与集合right的交
Set&operator-（Set&right）;//求集合this与集合right的差
intContains（constType&x）;//判x是否集合的成员
intoperator==（Set&right）;//判集合this与集合right相等
Type&Min（）;//返回集合中的最小元素的值
}
（1）operator+（）
templateSet&Set:
:
operator+（Set&right）{
//求集合this与集合right的并,计算结果通过临时集合temp返回，this集合与right集合不变。
SetNode*pb=right.first->link;//right集合的链扫描指针
SetNode*pa,*pc;//this集合的链扫描指针和结果链的存放指针
Settemp;
pa=first->link;pc=temp.first;
while（pa!
=NULL）{//首先把集合this的所有元素复制到结果链
pc->link=newSetNode（pa->data）;
pa=pa->link;pc=pc->link;
}
while（pb!
=NULL）{//将集合right中元素一个个拿出到this中查重
pa=first->link;
while（pa!
=NULL&&pa->data!
=pb->data）pa=pa->link;
if（pa==NULL）//在集合this中未出现,链入到结果链
{pc->link=newSetNode（pa->data）;pc=pc->link;}
pb=pb->link;
}
pc->link=NULL;last=pc;//链表收尾
returntemp;
}
（2）operator*（）
templateSet&Set:
:
operator*（Set&right）{
//求集合this与集合right的交,计算结果通过临时集合temp返回，this集合与right集合不变。
SetNode*pb=right.first->link;//right集合的链扫描指针
Settemp;
SetNode*pc=temp.first;//结果链的存放指针
while（pb!
=NULL）{//将集合right中元素一个个拿出到this中查重
SetNode*pa=first->link;//this集合的链扫描指针
while（pa!
=NULL）{
if（pa->data==pb->data）//两集合公有的元素,插入到结果链
{pc->link=newSetNode（pa->data）;pc=pc->link;}
pa=pa->link;
}
pb=pb->link;
}
pc->link=NULL;last=pc;//置链尾指针
returntemp;
}
（3）operator-（）,
templateSet&Set:
:
operator-（Set&right）{
//求集合this与集合right的差,计算结果通过临时集合temp返回，this集合与right集合不变。
SetNode*pa=first->link;//this集合的链扫描指针
Settemp;
SetNode*pc=temp->first;//结果链的存放指针
while（pa!
=NULL）{//将集合this中元素一个个拿出到right中查重
SetNode*pb=right.first->link;//right集合的链扫描指针
while（pb!
=NULL&&pa->data!
=pb->data）
pb=pb->link;
if（pb==NULL）//此this中的元素在right中未找到,插入
{pc->link=newSetNode（pa->data）;pc=pc->link;}
pa=pa->link;
}
pc->link=NULL;last=pc;//链表收尾
returntemp;
}
（4）Contains（x）
templateintSet:
:
Contains（constType&x）{
//测试函数:
如果x是集合的成员,则函数返回1,否则返回0。
SetNode*temp=first->link;//链的扫描指针
while（temp!
=NULL&&temp->data!
=x）temp=temp->link;//循链搜索
if（temp!
=NULL）return1;//找到,返回1
elsereturn0;//未找到,返回0
}
（5）AddMember（x）
templateintSet:
:
AddMember（constType&x）{
//把新元素x加入到集合之中。
若集合中已有此元素,则函数返回0,否则函数返回1。
SetNode*temp=first->link;//temp是扫描指针
while（temp!
=NULL&&temp->data!
=x）temp=temp->link;/循链扫描
if（temp!
=NULL）return0;//集合中已有此元素,不加
last=last->link=newSetNode（x）;//否则,创建数据值为x的新结点,链入
return1;
}
（6）DelMember（x）
templateintSet:
:
DelMember（constType&x）{
//把集合中成员x删去。
若集合不空且元素x在集合中,则函数返回1,否则返回0。
SetNode*p=first->link,*q=first;
while（p!
=NULL）{
if（p->data==x）{//找到
q->link=p->link;//重新链接
if（p==last）last=q;//删去链尾结点时改链尾指针
deletep;return1;//删除含x结点
}
else{q=p;p=p->link;}//循链扫描
return0;//集合中无此元素
}
（7）Min（）
templateSetNode*Set:
:
Min（）{
//在集合中寻找值最小的成员并返回它的位置。
SetNode*p=first->link,*q=first->link;//p是检测指针,q是记忆最小指针
while（p!
=NULL）{
if（p->datadata）q=p;//找到更小的,让q记忆它
p=p->link;//继续检测
}
returnq;
}
7-8设有序顺序表中的元素依次为017,094,154,170,275,503,509,512,553,612,677,765,897,908。
试画出对其进行折半搜索时的二叉搜索树,并计算搜索成功的平均搜索长度和搜索不成功的平均搜索长度。
【解答】
509
677
154
897
553
275
017
908
765
612
512
503
170
094
7-9若对有n个元素的有序顺序表和无序顺序表进行顺序搜索,试就下列三种情况分别讨论两者在等搜索概率时的平均搜索长度是否相同?
（1）搜索失败;
（2）搜索成功,且表中只有一个关键码等于给定值k的对象;
（3）搜索成功,且表中有若干个关键码等于给定值k的对象,要求一次搜索找出所有对象。
【解答】
（1）不同。
因为有序顺序表搜索到其关键码比要查找值大的对象时就停止搜索，报告失败信息，不必搜索到表尾；而无序顺序表必须搜索到表尾才能断定搜索失败。
（2）相同。
搜索到表中对象的关键码等于给定值时就停止搜索，报告成功信息。
（3）不同。
有序顺序表中关键码相等的对象相继排列在一起，只要搜索到第一个就可以连续搜索到其它关键码相同的对象。
而无序顺序表必须搜索全部表中对象才能确定相同关键码的对象都找了出来，所需时间就不相同了。
前两问可做定量分析。
第三问推导出的公式比较复杂，不再进一步讨论。
7-10假定用一个循环链表来实现一个有序表，并让指针head指向具有最小关键码的结点。
指针current初始时等于head，每次搜索后指向当前检索的结点，但如果搜索不成功则current重置为head。
试编写一个函数search（head,current,key）实现这种搜索。
当搜索成功时函数返回被检索的结点地址，若搜索不成功则函数返回空指针0。
请说明如何保持指针current以减少搜索时的平均搜索长度。
【解答】
current
60
50
40
30
20
10
head
相应的搜索函数可以定义为链表及链表结点类的友元函数，直接使用链表及链表结点类的私有数据成员。
template
ListNode*Search（ListNode*head,ListNode*¤t,Typekey）{
ListNode*p,*q;
if（keyelse{p=current;q=head;}
while（p!
=q&&p->datalink;//循链搜索其值等于key的结点
if（p->data==key）{current=p;returnp;}//找到,返回结点地址
else{current=head;returnNULL;}//未找到,返回空指针
}
7-11考虑用双向链表来实现一个有序表，使得能在这个表中进行正向和反向搜索。
若指针p总是指向最后成功搜索到的结点，搜索可以从p指示的结点出发沿任一方向进行。
试根据这种情况编写一个函数search（head,p,key），检索具有关键码key的结点，并相应地修改p。
最后请给出搜索成功和搜索不成功时的平均搜索长度。
p
【解答】
40
70
∧
∧
60
50
30
20
10
head
template
DblListNode*Search（
升级会员 