/*****************************************************************************
* *
* -------------------------------- set.c --------------------------------- *
* *
*****************************************************************************/
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include "list.h"
#include "set.h"
int match(const void *key1,const void *key2);
void select(void);
void print(Set *set);
Set *set_1,
*set_2,
*set_result;
int main()
{
if((set_1=(Set *)malloc(sizeof(Set)))==NULL)
return -1;
if((set_2=(Set *)malloc(sizeof(Set)))==NULL)
return -1;
if((set_result=(Set *)malloc(sizeof(Set)))==NULL)
return -1;
set_init(set_1,match,free);
set_init(set_2,match,free);
set_init(set_result,match,free);
select();
return 0;
}
void select(void)
{
void *data,
*rmdata,
*rmdata2;
int input,push;
while(1)
{
printf("n");
printf(" ┏━━━ set menu v1.0━━━━┓n");
printf(" ┃ 1 -> set init ┃n");
printf(" ┃ 2 -> set_1 insert ┃n");
printf(" ┃ 3 -> set_2 insert ┃n");
printf(" ┃ 4 -> set union ┃n");
printf(" ┃ 5 -> set intersection ┃n");
printf(" ┃ 6 -> set difference ┃n");
printf(" ┃ 9 -> set remove ┃n");
printf(" ┃ 0 -> Exit ┃n");
printf(" ┣━━━━━━━━━━━━━━┫n");
printf(" ┃select number ┃n");
printf(" ┗━━━━━━━━━━━━━━┛n");
printf(" ==> ");
scanf("%d",&input);
switch(input)
{
case 1:
system("cls");
set_init(set_1,match,free);
set_init(set_2,match,free);
set_init(set_result,match,free);
break;
case 2:
system("cls");
printf(" Input Data -> ");
scanf("%d",&data);
set_insert(set_1,data);
print(set_1);
print(set_2);
break;
case 3:
system("cls");
printf(" Input Data -> ");
scanf("%d",&data);
set_insert(set_2,data);
print(set_1);
print(set_2);
break;
case 4:
system("cls");
set_union(set_result,set_1,set_2);
print(set_1);
print(set_2);
printf(" set_union = ");
print(set_result);
break;
case 5:
system("cls");
set_intersection(set_result,set_1,set_2);
print(set_1);
print(set_2);
printf(" set_intersection = ");
print(set_result);
break;
case 6:
system("cls");
set_difference(set_result,set_1,set_2);
print(set_1);
print(set_2);
printf(" set_difference = ");
print(set_result);
break;
case 9:
system("cls");
printf(" Do you want set1 ? push 1 n");
printf(" Do you want set2 ? push 2 n");
printf(" Select -> ");
scanf("%d",&push);
if(push==1)
{
printf(" remove -> ");
scanf("%d",&rmdata);
set_remove(set_1,&rmdata);
print(set_1);
print(set_2);
}
else if(push==2)
{
printf(" remove -> ");
scanf("%d",&rmdata2);
set_remove(set_2,&rmdata2);
print(set_1);
print(set_2);
}
else
{
printf(" You select wrong number Try again");
continue;
}
break;
case 0:
free(set_1);
free(set_2);
free(set_result);
exit(1);
default:
printf(" Wrong number again choosen");
break;
}
}
}
void print(Set *set)
{
ListElmt *next;
if(set_1==set)
printf(" set_1 = ");
else if(set_2==set)
printf(" set_2 = ");
for(next=list_head(set);next!=NULL;next=list_next(next))
{
printf("[%d]",list_data(next));
}
printf("n");
}
int match(const void *key1,const void *key2)
{
if(key1==key2)
return 1;
else
return 0;
}
/*****************************************************************************
* *
* ------------------------------- set_init ------------------------------- *
* *
*****************************************************************************/
void set_init(Set *set, int (*match)(const void *key1, const void *key2),
void (*destroy)(void *data)) {
/*****************************************************************************
* *
* Initialize the set. *
* *
*****************************************************************************/
list_init(set, destroy);
set->match = match;
return;
}
/*****************************************************************************
* *
* ------------------------------ set_insert ------------------------------ *
* *
*****************************************************************************/
int set_insert(Set *set, const void *data) {
/*****************************************************************************
* *
* Do not allow the insertion of duplicates. *
* *
*****************************************************************************/
if (set_is_member(set, data))
return 1;
/*****************************************************************************
* *
* Insert the data. *
* *
*****************************************************************************/
return list_ins_next(set, list_tail(set), data);
}
/*****************************************************************************
* *
* ------------------------------ set_remove ------------------------------ *
* *
*****************************************************************************/
int set_remove(Set *set, void **data) {
ListElmt *member,
*prev;
/*****************************************************************************
* *
* Find the member to remove. *
* *
*****************************************************************************/
prev = NULL;
for (member = list_head(set); member != NULL; member = list_next(member)) {
if (set->match(*data, list_data(member)))
break;
prev = member;
}
/*****************************************************************************
* *
* Return if the member was not found. *
* *
*****************************************************************************/
if (member == NULL)
return -1;
/*****************************************************************************
* *
* Remove the member. *
* *
*****************************************************************************/
return list_rem_next(set, prev, data);
}
/*****************************************************************************
* *
* ------------------------------- set_union ------------------------------ *
* *
*****************************************************************************/
int set_union(Set *setu, const Set *set1, const Set *set2) {
ListElmt *member;
void *data;
/*****************************************************************************
* *
* Initialize the set for the union. *
* *
*****************************************************************************/
set_init(setu, set1->match, NULL);
/*****************************************************************************
* *
* Insert the members of the first set. *
* *
*****************************************************************************/
for (member = list_head(set1); member != NULL; member = list_next(member)) {
data = list_data(member);
if (list_ins_next(setu, list_tail(setu), data) != 0) {
set_destroy(setu);
return -1;
}
}
/*****************************************************************************
* *
* Insert the members of the second set. *
* *
*****************************************************************************/
for (member = list_head(set2); member != NULL; member = list_next(member)) {
if (set_is_member(set1, list_data(member))) {
/***********************************************************************
* *
* Do not allow the insertion of duplicates. *
* *
***********************************************************************/
continue;
}
else {
data = list_data(member);
if (list_ins_next(setu, list_tail(setu), data) != 0) {
set_destroy(setu);
return -1;
}
}
}
return 0;
}
/*****************************************************************************
* *
* --------------------------- set_intersection --------------------------- *
* *
*****************************************************************************/
int set_intersection(Set *seti, const Set *set1, const Set *set2) {
ListElmt *member;
void *data;
/*****************************************************************************
* *
* Initialize the set for the intersection. *
* *
*****************************************************************************/
set_init(seti, set1->match, NULL);
/*****************************************************************************
* *
* Insert the members present in both sets. *
* *
*****************************************************************************/
for (member = list_head(set1); member != NULL; member = list_next(member)) {
if (set_is_member(set2, list_data(member))) {
data = list_data(member);
if (list_ins_next(seti, list_tail(seti), data) != 0) {
set_destroy(seti);
return -1;
}
}
}
return 0;
}
/*****************************************************************************
* *
* ---------------------------- set_difference ---------------------------- *
* *
*****************************************************************************/
int set_difference(Set *setd, const Set *set1, const Set *set2) {
ListElmt *member;
void *data;
/*****************************************************************************
* *
* Initialize the set for the difference. *
* *
*****************************************************************************/
set_init(setd, set1->match, NULL);
/*****************************************************************************
* *
* Insert the members from set1 not in set2. *
* *
*****************************************************************************/
for (member = list_head(set1); member != NULL; member = list_next(member)) {
if (!set_is_member(set2, list_data(member))) {
data = list_data(member);
if (list_ins_next(setd, list_tail(setd), data) != 0) {
set_destroy(setd);
return -1;
}
}
}
return 0;
}
/*****************************************************************************
* *
* ----------------------------- set_is_member ---------------------------- *
* *
*****************************************************************************/
int set_is_member(const Set *set, const void *data) {
ListElmt *member;
/*****************************************************************************
* *
* Determine if the data is a member of the set. *
* *
*****************************************************************************/
for (member = list_head(set); member != NULL; member = list_next(member)) {
if (set->match(data, list_data(member)))
return 1;
}
return 0;
}
/*****************************************************************************
* *
* ----------------------------- set_is_subset ---------------------------- *
* *
*****************************************************************************/
int set_is_subset(const Set *set1, const Set *set2) {
ListElmt *member;
/*****************************************************************************
* *
* Do a quick test to rule out some cases. *
* *
*****************************************************************************/
if (set_size(set1) > set_size(set2))
return 0;
/*****************************************************************************
* *
* Determine if set1 is a subset of set2. *
* *
*****************************************************************************/
for (member = list_head(set1); member != NULL; member = list_next(member)) {
if (!set_is_member(set2, list_data(member)))
return 0;
}
return 1;
}
/*****************************************************************************
* *
* ------------------------------ set_is_equal ---------------------------- *
* *
*****************************************************************************/
int set_is_equal(const Set *set1, const Set *set2) {
/*****************************************************************************
* *
* Do a quick test to rule out some cases. *
* *
*****************************************************************************/
if (set_size(set1) != set_size(set2))
return 0;
/*****************************************************************************
* *
* Sets of the same size are equal if they are subsets. *
* *
*****************************************************************************/
return set_is_subset(set1, set2);
}
/*****************************************************************************
* *
* -------------------------------- set.h --------------------------------- *
* *
*****************************************************************************/
#ifndef SET_H
#define SET_H
#include <stdlib.h>
#include "list.h"
/*****************************************************************************
* *
* Implement sets as linked lists. *
* *
*****************************************************************************/
typedef List Set;
/*****************************************************************************
* *
* --------------------------- Public Interface --------------------------- *
* *
*****************************************************************************/
void set_init(Set *set, int (*match)(const void *key1, const void *key2),
void (*destroy)(void *data));
#define set_destroy list_destroy
int set_insert(Set *set, const void *data);
int set_remove(Set *set, void **data);
int set_union(Set *setu, const Set *set1, const Set *set2);
int set_intersection(Set *seti, const Set *set1, const Set *set2);
int set_difference(Set *setd, const Set *set1, const Set *set2);
int set_is_member(const Set *set, const void *data);
int set_is_subset(const Set *set1, const Set *set2);
int set_is_equal(const Set *set1, const Set *set2);
#define set_size(set) ((set)->size)
#endif
* *
* -------------------------------- set.c --------------------------------- *
* *
*****************************************************************************/
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include "list.h"
#include "set.h"
int match(const void *key1,const void *key2);
void select(void);
void print(Set *set);
Set *set_1,
*set_2,
*set_result;
int main()
{
if((set_1=(Set *)malloc(sizeof(Set)))==NULL)
return -1;
if((set_2=(Set *)malloc(sizeof(Set)))==NULL)
return -1;
if((set_result=(Set *)malloc(sizeof(Set)))==NULL)
return -1;
set_init(set_1,match,free);
set_init(set_2,match,free);
set_init(set_result,match,free);
select();
return 0;
}
void select(void)
{
void *data,
*rmdata,
*rmdata2;
int input,push;
while(1)
{
printf("n");
printf(" ┏━━━ set menu v1.0━━━━┓n");
printf(" ┃ 1 -> set init ┃n");
printf(" ┃ 2 -> set_1 insert ┃n");
printf(" ┃ 3 -> set_2 insert ┃n");
printf(" ┃ 4 -> set union ┃n");
printf(" ┃ 5 -> set intersection ┃n");
printf(" ┃ 6 -> set difference ┃n");
printf(" ┃ 9 -> set remove ┃n");
printf(" ┃ 0 -> Exit ┃n");
printf(" ┣━━━━━━━━━━━━━━┫n");
printf(" ┃select number ┃n");
printf(" ┗━━━━━━━━━━━━━━┛n");
printf(" ==> ");
scanf("%d",&input);
switch(input)
{
case 1:
system("cls");
set_init(set_1,match,free);
set_init(set_2,match,free);
set_init(set_result,match,free);
break;
case 2:
system("cls");
printf(" Input Data -> ");
scanf("%d",&data);
set_insert(set_1,data);
print(set_1);
print(set_2);
break;
case 3:
system("cls");
printf(" Input Data -> ");
scanf("%d",&data);
set_insert(set_2,data);
print(set_1);
print(set_2);
break;
case 4:
system("cls");
set_union(set_result,set_1,set_2);
print(set_1);
print(set_2);
printf(" set_union = ");
print(set_result);
break;
case 5:
system("cls");
set_intersection(set_result,set_1,set_2);
print(set_1);
print(set_2);
printf(" set_intersection = ");
print(set_result);
break;
case 6:
system("cls");
set_difference(set_result,set_1,set_2);
print(set_1);
print(set_2);
printf(" set_difference = ");
print(set_result);
break;
case 9:
system("cls");
printf(" Do you want set1 ? push 1 n");
printf(" Do you want set2 ? push 2 n");
printf(" Select -> ");
scanf("%d",&push);
if(push==1)
{
printf(" remove -> ");
scanf("%d",&rmdata);
set_remove(set_1,&rmdata);
print(set_1);
print(set_2);
}
else if(push==2)
{
printf(" remove -> ");
scanf("%d",&rmdata2);
set_remove(set_2,&rmdata2);
print(set_1);
print(set_2);
}
else
{
printf(" You select wrong number Try again");
continue;
}
break;
case 0:
free(set_1);
free(set_2);
free(set_result);
exit(1);
default:
printf(" Wrong number again choosen");
break;
}
}
}
void print(Set *set)
{
ListElmt *next;
if(set_1==set)
printf(" set_1 = ");
else if(set_2==set)
printf(" set_2 = ");
for(next=list_head(set);next!=NULL;next=list_next(next))
{
printf("[%d]",list_data(next));
}
printf("n");
}
int match(const void *key1,const void *key2)
{
if(key1==key2)
return 1;
else
return 0;
}
/*****************************************************************************
* *
* ------------------------------- set_init ------------------------------- *
* *
*****************************************************************************/
void set_init(Set *set, int (*match)(const void *key1, const void *key2),
void (*destroy)(void *data)) {
/*****************************************************************************
* *
* Initialize the set. *
* *
*****************************************************************************/
list_init(set, destroy);
set->match = match;
return;
}
/*****************************************************************************
* *
* ------------------------------ set_insert ------------------------------ *
* *
*****************************************************************************/
int set_insert(Set *set, const void *data) {
/*****************************************************************************
* *
* Do not allow the insertion of duplicates. *
* *
*****************************************************************************/
if (set_is_member(set, data))
return 1;
/*****************************************************************************
* *
* Insert the data. *
* *
*****************************************************************************/
return list_ins_next(set, list_tail(set), data);
}
/*****************************************************************************
* *
* ------------------------------ set_remove ------------------------------ *
* *
*****************************************************************************/
int set_remove(Set *set, void **data) {
ListElmt *member,
*prev;
/*****************************************************************************
* *
* Find the member to remove. *
* *
*****************************************************************************/
prev = NULL;
for (member = list_head(set); member != NULL; member = list_next(member)) {
if (set->match(*data, list_data(member)))
break;
prev = member;
}
/*****************************************************************************
* *
* Return if the member was not found. *
* *
*****************************************************************************/
if (member == NULL)
return -1;
/*****************************************************************************
* *
* Remove the member. *
* *
*****************************************************************************/
return list_rem_next(set, prev, data);
}
/*****************************************************************************
* *
* ------------------------------- set_union ------------------------------ *
* *
*****************************************************************************/
int set_union(Set *setu, const Set *set1, const Set *set2) {
ListElmt *member;
void *data;
/*****************************************************************************
* *
* Initialize the set for the union. *
* *
*****************************************************************************/
set_init(setu, set1->match, NULL);
/*****************************************************************************
* *
* Insert the members of the first set. *
* *
*****************************************************************************/
for (member = list_head(set1); member != NULL; member = list_next(member)) {
data = list_data(member);
if (list_ins_next(setu, list_tail(setu), data) != 0) {
set_destroy(setu);
return -1;
}
}
/*****************************************************************************
* *
* Insert the members of the second set. *
* *
*****************************************************************************/
for (member = list_head(set2); member != NULL; member = list_next(member)) {
if (set_is_member(set1, list_data(member))) {
/***********************************************************************
* *
* Do not allow the insertion of duplicates. *
* *
***********************************************************************/
continue;
}
else {
data = list_data(member);
if (list_ins_next(setu, list_tail(setu), data) != 0) {
set_destroy(setu);
return -1;
}
}
}
return 0;
}
/*****************************************************************************
* *
* --------------------------- set_intersection --------------------------- *
* *
*****************************************************************************/
int set_intersection(Set *seti, const Set *set1, const Set *set2) {
ListElmt *member;
void *data;
/*****************************************************************************
* *
* Initialize the set for the intersection. *
* *
*****************************************************************************/
set_init(seti, set1->match, NULL);
/*****************************************************************************
* *
* Insert the members present in both sets. *
* *
*****************************************************************************/
for (member = list_head(set1); member != NULL; member = list_next(member)) {
if (set_is_member(set2, list_data(member))) {
data = list_data(member);
if (list_ins_next(seti, list_tail(seti), data) != 0) {
set_destroy(seti);
return -1;
}
}
}
return 0;
}
/*****************************************************************************
* *
* ---------------------------- set_difference ---------------------------- *
* *
*****************************************************************************/
int set_difference(Set *setd, const Set *set1, const Set *set2) {
ListElmt *member;
void *data;
/*****************************************************************************
* *
* Initialize the set for the difference. *
* *
*****************************************************************************/
set_init(setd, set1->match, NULL);
/*****************************************************************************
* *
* Insert the members from set1 not in set2. *
* *
*****************************************************************************/
for (member = list_head(set1); member != NULL; member = list_next(member)) {
if (!set_is_member(set2, list_data(member))) {
data = list_data(member);
if (list_ins_next(setd, list_tail(setd), data) != 0) {
set_destroy(setd);
return -1;
}
}
}
return 0;
}
/*****************************************************************************
* *
* ----------------------------- set_is_member ---------------------------- *
* *
*****************************************************************************/
int set_is_member(const Set *set, const void *data) {
ListElmt *member;
/*****************************************************************************
* *
* Determine if the data is a member of the set. *
* *
*****************************************************************************/
for (member = list_head(set); member != NULL; member = list_next(member)) {
if (set->match(data, list_data(member)))
return 1;
}
return 0;
}
/*****************************************************************************
* *
* ----------------------------- set_is_subset ---------------------------- *
* *
*****************************************************************************/
int set_is_subset(const Set *set1, const Set *set2) {
ListElmt *member;
/*****************************************************************************
* *
* Do a quick test to rule out some cases. *
* *
*****************************************************************************/
if (set_size(set1) > set_size(set2))
return 0;
/*****************************************************************************
* *
* Determine if set1 is a subset of set2. *
* *
*****************************************************************************/
for (member = list_head(set1); member != NULL; member = list_next(member)) {
if (!set_is_member(set2, list_data(member)))
return 0;
}
return 1;
}
/*****************************************************************************
* *
* ------------------------------ set_is_equal ---------------------------- *
* *
*****************************************************************************/
int set_is_equal(const Set *set1, const Set *set2) {
/*****************************************************************************
* *
* Do a quick test to rule out some cases. *
* *
*****************************************************************************/
if (set_size(set1) != set_size(set2))
return 0;
/*****************************************************************************
* *
* Sets of the same size are equal if they are subsets. *
* *
*****************************************************************************/
return set_is_subset(set1, set2);
}
/*****************************************************************************
* *
* -------------------------------- set.h --------------------------------- *
* *
*****************************************************************************/
#ifndef SET_H
#define SET_H
#include <stdlib.h>
#include "list.h"
/*****************************************************************************
* *
* Implement sets as linked lists. *
* *
*****************************************************************************/
typedef List Set;
/*****************************************************************************
* *
* --------------------------- Public Interface --------------------------- *
* *
*****************************************************************************/
void set_init(Set *set, int (*match)(const void *key1, const void *key2),
void (*destroy)(void *data));
#define set_destroy list_destroy
int set_insert(Set *set, const void *data);
int set_remove(Set *set, void **data);
int set_union(Set *setu, const Set *set1, const Set *set2);
int set_intersection(Set *seti, const Set *set1, const Set *set2);
int set_difference(Set *setd, const Set *set1, const Set *set2);
int set_is_member(const Set *set, const void *data);
int set_is_subset(const Set *set1, const Set *set2);
int set_is_equal(const Set *set1, const Set *set2);
#define set_size(set) ((set)->size)
#endif
출처 - C로 구현하 알고리즘, 한빛미디어
