exp_dlink.cpp

这是本人精心搜集的关于常用图论算法的一套源码

/* 求整数集合A = (A-B)∪(B-A)（求集合A、B的对称差存入集合A）。
算法思路：分别用带头结点的单链表La、Lb表示集合A和B，用for循环逐个从Lb表中取元素存入x中，
在La表中查找x，若找到，则x∈A∩B，将x从La表删除；否则x∈B－A，将x插入La表，
for循环结束算法完成；此时La表代表所求的(A-B)∪(B-A)集合，Lb保持不变。          */
#include <stdlib.h>
#include <time.h>
#include "DLList.h"

void Symm_diff(List<int>&, List<int>&);
// 求以双向链表存储的两个集合“对称差”之原型声明
void CrtLinkList(List<int>&,int); 
//为集合产生若干互不相等的整数插入双向链表的原型声明
void  SetUnion(List<int>&,List<int>&);
// 求以双向链表存储的两个集合“并”之原型声明
void visit(int &);
void main()
{ 
  List<int> La,Lb;
  int s1, s2;  // s1, s2是存放La,Lb大小的变量
  time_t t;   srand((unsigned)time(&t)); //初始化随时间变化的随机数种子
  cout<<"Please input Size of SetA && SetB =? =? ";
  cin>>s1>>s2;  // 输入集合A,B元素数
  cout<<"\nSet A = { ";  // 输出集合A的名称
  CrtLinkList(La,s1);     // 创建集合A,输出集合元素
  cout<<"}\n Length="<<s1<<"\n\nSet B = { "; // 输出集合B的名称
  CrtLinkList(Lb,s2);     // 创建集合B,输出集合元素
  List<int> Lc(La), Ld;
  cout<<" }\n Length="<<s2<<"\n\n(A-B) ∪ (B-A) = { ";
  Symm_diff(La,Lb);   // La =  (A-B) ∪ (B-A) 
  La.traverse(visit);  cout<<" }\n Length="<<La.size();
  cout<<"\n\nA ∪ B = { ";
  SetUnion(Lc,Lb); 
  Ld = Lc; // Ld = Lc =  A ∪ B  
  Lc.traverse(visit);  cout<<" }\n Length="<<Lc.size();
  cout<<"\n\nA ∩ B = { ";
  Symm_diff(Lc,La);  // Lc =  A ∩ B 
  Lc.traverse(visit);  cout<<" }\n Length="<<Lc.size();
  cout<<"\n\n( A∩B )∪((A-B)∪(B-A)= { ";
  SetUnion(Lc,La);   //  Lc = ( A ∩ B ) ∪ ( (A-B) ∪ (B-A)  )
  Lc.traverse(visit);  cout<<" }\n Length="<<Lc.size(); 
  if( Lc.size() == Ld.size() ) cout<<"\n\n Ok!\n\n";
   else cout<<"\n\n Error!\n\n";
 }
void visit(int &d)  // 输出单链表结点的数据域
{ cout<<d<<"  ";  }

void Symm_diff(List<int>& La, List<int>& Lb)
{ int x,i;     
  for(int j=0; j<Lb.size(); j++)
     { Lb.retrieve(j, x);
       if((i=La.find(x)) == -1)    // 集合B的元素不在A中
          La.insert(i+1,x);  // 插入A集合
       else  La.remove(i,x);       // 集合B的元素在A中,删除之
     } 	 
}  

void CrtLinkList(List<int>& L,int n) 
// 为链表L产生n个互不相等的整数插入表（集合中元素间无次序关系）
{ int x,i,j;
  x=rand() % 37; L.insert(0,x);
  for(i=1; i<n; i++)             // 用随机数发生器产生n个集合元素,不得重复
     { do{  x=rand() % 37;       // 产生0-36间的随机整数（要求各元素值不等）
         }while((j=L.find(x))!=-1);   // 在集合中找x, 找不到则脱离循环
       L.insert(j+1,x);             // 插入表
       cout<<x<<"  ";               // 输出x ( 集合元素边产生边输出)
     } 
}

void SetUnion(List<int>&La,List<int>&Lb)
// 将La表和Lb表所表示的集合做"并"，存入La表，Lb表被清空。
{int i,k,b;
 for(i=Lb.size(); i>0; i--)    //从Lb表中逐次删除素尾元素，这样不必移动元素
    { Lb.remove(i-1,b);        //调用删除算法，被删元素存入b
      k=La.find(b);           // 在La表中查找b
      if(k==-1)               //La表中找不到元素b
    	La.insert(0, b);     // 插入至la表头
    } //end_for
}