THIPTTKTT
/*********************************************************************************
- 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;
}
Bạn đang đọc truyện trên: Truyen2U.Com