/*********************************************************************************

- Phan tich va thiet ke thuat toan

- Bieu dien tap hop bang danh sach lien ket

- Thuc hien cac phep toan voi

- tap hop cac so le va so nguyen to nho hon 10

- Writed by Nguyen The Linh

*********************************************************************************/

#include<stdio.h>

#include<conio.h>

#include<math.h>

#include<stdlib.h>

const int n=10;

// Initialize application

typedef int ElementType;

typedef struct tagnode

{

ElementType data;

struct tagnode *next;

}node;

typedef struct tagSet

{

node *head;

node *tail;

}Set;

// Tao mot node moi return dia chi cua node

node *createnode(ElementType x)

{

node *p;

p=new node;

if (p==NULL)

exit(1);

else

{

p->data=x;

p->next=NULL;

}

return p;

}

/*********************************************************************************

- Class tap hop

*********************************************************************************/

// Tao tap hop rong

void makenull_Set(Set &A)

{

A.head=NULL;

A.tail=NULL;

}

// Kiem tra xem mot phan tu co thuoc tap hop hay khong

// Return vi tri if thuoc, return NULL neu khong thuoc

node *member_Set(ElementType x,Set A)

{

node *a;

a=A.head;

while((a!=NULL) && (a->data!=x))

{

a=a->next;

}

return a;

}

// Ham chen mot phan tu vo tap hop

void insert_Set(ElementType x,Set &A)

{

node *p;

if(member_Set(x,A)==NULL)

{

p=new node;

if(p==NULL)

exit(1);

else

{

p->data=x;

p->next=NULL;

}

if (A.head==NULL)

{

A.head=p;

A.tail=p;

}

else

{

A.tail->next=p;

A.tail=p;

}

}

}

// Lay hop cua hai tap hop A va B tao thanh tap hop C

void union_Set(Set A,Set B,Set &C)

{

node *a,*b;

a=A.head;

b=B.head;

while((a!=NULL) && (b!=NULL))

{

if(a->data< b->data)

{

insert_Set(a->data,C);

a=a->next;

}

else if(a->data>b->data)

{

insert_Set(b->data,C);

b=b->next;

}

else

{

insert_Set(a->data,C);

a=a->next;

b=b->next;

}

}

while(a!=NULL)

{

insert_Set(a->data,C);

a=a->next;

}

while(b!=NULL)

{

insert_Set(b->data,C);

b=b->next;

}

}

// Lay giao cua hai tap hop A va B tao thanh tap hop C

void intersection_Set(Set A,Set B,Set &C)

{

node *a,*b;

a=A.head;

b=B.head;

while(a!=NULL && b!=NULL)

{

if(a->data < b->data) a=a->next;

else if(a->data> b->data) b=b->next;

else

{

insert_Set(a->data,C);

a=a->next;

b=b->next;

}

}

}

// Lay hieu cua hai tap hop A va B tao thanh tap hop C

void difference_Set(Set A,Set B,Set &C)

{

node *a;

a=A.head;

while(a!=NULL)

{

if(member_Set(a->data,B)==NULL)

insert_Set(a->data,C);

a=a->next;

}

}

// Hien thi cac phan tu cua tap hop ra man hinh

void show_Set(Set A)

{

node *a;

a=A.head;

while(a!=NULL)

{

printf("%4d",a->data);

a=a->next;

}

}

/*********************************************************************************

- Chuong trinh chinh

*********************************************************************************/

// Mot so ham phu

// Ham kiem tra mot so n co phai so nguyen to

int is_nguyento(int n)

{

if(n<=1) return 0;

int ok=1,i=2;

while(ok && (i<=(int)sqrt(n)))

{

ok=n%i;

i++;

}

return (ok!=0);

}

// Kiem tra mot so x co phai la so le khong

int is_le(int x)

{

return (x&0x0001);

}

int main()

{

Set A; // Tap cac so nguyen to

Set B; // Tap cac so le

Set C; // Tap giao cua A va B

Set D; // Tap hop cua A va B

Set E; // Tap hieu cua A va B

// Khoi tao cac tap hop A , B la cac tap rong

makenull_Set(A);

makenull_Set(B);

makenull_Set(C);

makenull_Set(D);

makenull_Set(E);

// Insert du lieu vo cac tap hop

for(int i=0;i<n;i++)

{

if(is_nguyento(i))

insert_Set(i,A);

if(is_le(i))

insert_Set(i,B);

}

// Hien thi cac tap hop A va B

printf("

----------------------------------------------

");

printf("

Tap hop cac so nguyen to A");

printf("

----------------------------------------------

");

show_Set(A);

printf("

----------------------------------------------

");

printf("

Tap hop cac so le B");

printf("

----------------------------------------------

");

show_Set(B);

// Giao cua hai tap hop

printf("

----------------------------------------------

");

printf("

Giao cua hai tap hop");

printf("

----------------------------------------------

");

intersection_Set(A,B,C);

show_Set(C);

// Hop cua hai tap hop

printf("

----------------------------------------------

");

printf("

Hop cua hai tap hop");

printf("

----------------------------------------------

");

union_Set(A,B,D);

show_Set(D);

// Hieu cua hai tap hop

printf("

----------------------------------------------

");

printf("

Hieu cua hai tap hop");

printf("

----------------------------------------------

");

difference_Set(A,B,E);

show_Set(E);

getch();

return 0;

}