集合的交并差运算
//集合的交并差运算
//济南大学信息学院 计算机 数据结构 课程设计
/*
【问题描述】
编制一个额能演示集合的并、交、差运算的程序
【基本要求】
集合的元素限定为['a'.....'z', '0'....'9']
*/
//setdemos.cpp
#include "iostream"
#include "public.h"
#include "OrderSet.h"
using namespace std;
#include "Functions.h"
OrderedSet Set1, Set2, Set3;
void Interpret(char cmd)
{
char v[100];
switch(cmd){
case '1': //显示以串的形式键入集合元素的提示信息
cout
Scanf(v);//读入集合元素到串变量v
CreatSet(Set1,v); cout
PrintSet(Set1); //system("pause");
break;
case '2': //显示以串的形式键入集合元素的提示信息
cout
Scanf(v);//读入集合元素到串变量v
CreatSet(Set2,v); cout
PrintSet(Set2); //system("pause");
break;
case 'U': ; case 'u':
Union(Set3, Set1, Set2); //求有序集Set1和Set2的并集Set3
cout
PrintSet(Set3);
DestroyList(Set3);
//cout
break;
case 'I': ; case'i':
Intersection(Set3, Set1, Set2); //求有序集Set1和Set2的交集Set3
cout
PrintSet(Set3);
DestroyList(Set3);
break;
case 'D': ; case 'd':
Difference(Set3, Set1, Set2); //求有序集Set1和Set2的差集Set3
cout
PrintSet(Set3);
DestroyList(Set3);
break;
}
}
void main()
{
char cmd;
Initialization();//初始化
do{
ReadCommand(cmd);//读取一个操作符指令
//cout
Interpret(cmd);//解释执行操作符指令
system("pause");
}while(cmd!='q' && cmd!='Q' );
}//main
void Scanf(char *p)
{
cout
cin>>p;
}
void clrscr()
{
//清屏函数
system("cls");
}
void ReadCommand(char &cmd)
{
char command;
bool first=true;
do{
if(!first) {
//clrscr();
//Initialization();
//cout
cout
} //if
cmd=getchar();
command=cmd;
first=false;
}while( command!='1' && command!='2' && command!='U' && command!='u' && command!='I' && command!='i' && command!='D' && command!='d' && command!='Q' && command!='q' );
}
void Initialization()
{
//初始化
clrscr();//清屏
cout
cout
cout
cout
//CreatSet(Set1,""); PrintSet(Set1);//构造并显示空集Set1
//CreatSet(Set2,""); PrintSet(Set2);//构造并显示空集Set2
}
//Node.h
typedef char ElemType;
typedef struct NodeType
{
ElemType data;
NodeType *next;
}NodeType, *LinkType; //结点类
型,指针类型
Status MakeNode(LinkType &p, ElemType e)
{
//分配由P指向的数据元素为e 后继为空的结点,并返回 OK
//若分配失败,则返回ERROR
p=(LinkType )malloc(sizeof(NodeType));
if(!p) return ERROR;
p->data=e;
p->next=NULL;
return OK;
}
void FreeNode(LinkType &p)
{
free(p);
}
LinkType Copy(LinkType p)
{
//复制生成和指针P所指向结点有同值元素的新结点并返回
//如分配空间失败,则返回空指针。新节点的指针域为NULL
LinkType s;
s=(LinkType )malloc(sizeof(NodeType));
if(!s) return 0;
s->data=p->data;
s->next=NULL;
return s;
}
ElemType Elem(LinkType p)
{
//若指针p!=NULL,则返回p所指结点的数据元素,否则返回'#'
if(p!=NULL) return p->data;
else return '#';
}
LinkType SuccNode(LinkType p)
{
//若指针p!=NULL,则返回p所指结点的后继元素的指针
//否则返回NULL
if(p) { p=p->next; return p; }
else return NULL;
}
//OrderSet.h
#include "OrdList.h"
using namespace std;
typedef OrderedList OrderedSet;
//////////////////////////////////////////////////
bool Islower(char &ch) //ok 判断ch是否是小写字母
{
if(ch>='a' && ch
//else if(ch>='A' && ch
else return false;
}
int length(char *s) //ok
{
char *p;
p=s;
int i=0;
while(*p>='a' && *p
i++;
p++;
}
return i;
}
void CreatSet(OrderedSet &T, char *s ) //OK
{
int i=0;
LinkType p, q;
if(InitList(T))
for( i=0; i
if( Islower(s[i]) && !LocateElem(T, s[i], p) )
if(MakeNode(q, s[i])) InsertAfter(T,p,q);
}
///////////////////////////////////////////////////
void DestroySet(OrderedSet &T )
{
DestroyList(T);
}
/////////////////////////////////////////////////////////
void Union(OrderedSet &T, OrderedSet S1, OrderedSet S2 )
{
//求并集
LinkType p1, p2;
char c1, c2;
if(InitList(T)) {
p1=GetElemPos(S1, 1); p2=GetElemPos(S2, 1);
while( p1 && p2 ) {
c1=Elem(p1); c2=Elem(p2);
if(c1
Append(T, Copy(p1)); p1=SuccNode(p1);
if(c1 == c2) p2=SuccNode(p2);
}else { Append(T, Copy(p2)); p2=SuccNode(p2); }
}//while
while(p1) { Append(T, Copy(p1)); p1=SuccNode(p1); }
while(p2) { Append(T, Copy(p2)); p2=SuccNode(p2); }
}//if
}//Union
//Intersection
void Intersection( OrderedSet &T, OrderedSet S1, OrderedSet S2 )
{
//交集
LinkType p1, p2;
char c1, c2;
if( !InitList(T)) T.head =NULL;
else {
p1=GetElemPos(S1, 1); p2=GetElemPos(S2, 1);
while( p1 && p2 ) {
c1=Elem(p1); c2=Elem(p2);
if(c1
else if(c1>c2 ) p2=SuccNode(p2);
else { //c1==c2
Append(T, Copy(p1));
p1=SuccNode(p1);
p2=SuccNode(p2);
}//else
}//while
}//else
}//Intersection
void Difference(OrderedSet &T, OrderedSet S1, OrderedSet S2 )
{
//差集
LinkType p1, p2;
char c1, c2;
if( !InitList(T))
T.head =NULL;
else {
p1=GetElemPos(S1, 1); p2=GetElemPos(S2, 1);
while( p1 && p2 ) {
c1=Elem(p1); c2=Elem(p2);
if(c1
else if(c1>c2 ) p2=SuccNode(p2);
else { //c1==c2
p1=SuccNode(p1);
p2=SuccNode(p2);
}//else
}//while
while(p1) { Append(T, Copy(p1)); p1=SuccNode(p1); }
}//else
}//Difference
////////////////////////////////////////////////////////////////
void WriteElem(char p)
{
cout
}
Status WriteSetElem(LinkType p)
{
cout
return OK;
}//
////////////////////////////
void PrintSet(OrderedSet T)
{
//显示集合的全部元素
LinkType p;
p=GetElemPos(T, 1);
cout
if(p) { WriteElem(Elem(p) ); p=SuccNode(p); }
ListTraverse(p, WriteSetElem);
cout
cout
}//
//////////////////////////////////////////////////////////////
//OrdList.h
#include "Node.h"
typedef struct{
LinkType head, tail;//分别指向有序链表的头结点和尾结点
int size; //指向链表当前的长度
}OrderedList; //有序链表类型
Status InitList(OrderedList &L)
{
if(MakeNode(L.head,' ') ) {
L.tail=L.head; L.size=0; return OK;
}
else { L.head=NULL; return ERROR ; }
}
void DestroyList(OrderedList &L)
{
LinkType p,q;
p=L.head;
while(p) { q=p; p=SuccNode(p); FreeNode(q); }
L.head=L.tail =NULL;
}
LinkType GetElemPos(OrderedList L, int pos)
{
LinkType p;
int k=0;
if( !L.head || posL.size ) return NULL;
else if(pos==L.size ) return L.tail;
else {
p=L.head->next; k=1;
while (p&&k
return p;
}
}
Status LocateElem( OrderedList L, ElemType e, LinkType &p )
{
LinkType pre;
if(L.head){
pre=L.head ; p=pre->next; //pre指向*p 的前驱,p指向第一个元素接点
while(p&&p->data
if(p&&p->data==e ) return OK;
else { p=pre; return ERROR; }
}
else return ERROR;
}
void Append(OrderedList &L, LinkType s)
{
if(L.head && s ){
if(L.tail !=L.head ) L.tail->next=s;
else L.head->next=s;
L.tail =s; L.size++;
}
}
//InsertAfter
void InsertAfter(OrderedList &L, LinkType q, LinkType s )
{
if(L.head && q && s){
s->next=q->next; q->next=s;
if(L.tail ==q ) L.tail =s;
L.size ++;
}
}
void ListTraverse(LinkType p, Status (*visit)(LinkType) )
{
while(p) { visit(p); p=SuccNode(p); }
}
//public.h
enum Status{
ERROR,
OK
};
//函数声明
void Initialization();
void ReadCommand(char &cmd);
void Interpret(char cmd);
void Scanf(char *p);