集合交差并三種操作的C實(shí)現(xiàn)

首先說(shuō)明一下集合的ADT，肯定有包括基本的創(chuàng)建、刪除操作。以及某一個(gè)元素的插入和刪除操作。集合的一個(gè)重要特征就是元素的不重復(fù)性。這種方式我在實(shí)現(xiàn)的過程中通過鏈表管理一個(gè)集合，按照元素的大小進(jìn)行排列，之所以排列主要是為了方便刪除、查找元素的操作。實(shí)質(zhì)上集合對(duì)元素的順序是沒有要求的。
集合的交集：是指兩個(gè)集合元素相同的部分構(gòu)成的集合。
集合的差集：是指其中一個(gè)集合中除去另一個(gè)集合相同元素以后剩余的元素構(gòu)成的集合。
集合的并集：是指兩個(gè)集合的所有元素構(gòu)成的集合。

其中需要注意的就是集合的元素是不能重復(fù)的，本來(lái)我打算采用二叉查找樹的方式實(shí)現(xiàn)，因?yàn)檫@種樹型結(jié)構(gòu)便于快速的查詢，但是我采用元素的升序排序就能避免集合中漫無(wú)目的的查詢操作。畢竟實(shí)現(xiàn)二叉查找樹也增加了一個(gè)指針成員，而且還需要大量的操作。

簡(jiǎn)要的說(shuō)明一下我的過程：
基本的集合結(jié)構(gòu)體：

typedef struct linknode
{
struct linknode *next;
int value;
}Node_t, *Node_handle_t;

typedef struct set
{
unsigned int size;
Node_handle_t head;
}Set;

集合的創(chuàng)建，該函數(shù)的實(shí)現(xiàn)是集合實(shí)現(xiàn)的最復(fù)雜的一個(gè)函數(shù)，之所以這么復(fù)雜是因?yàn)楹芏嗟牟僮鞫际腔谠摵瘮?shù)完成的，當(dāng)然也可以采用更精細(xì)的函數(shù)來(lái)實(shí)現(xiàn)，我開始的想法是將元素插入和創(chuàng)建操作合并，都基于一個(gè)函數(shù)進(jìn)行操作，但是寫完以后發(fā)現(xiàn)函數(shù)太長(zhǎng)，而且比較爛，不夠必將還是完成了一些基本的操作。采用了升序存儲(chǔ)的方式，主要是為了后續(xù)的查找操作，注意鏈表的更新操作。

bool create_set(Set **sets, int data)
{
Set * temp = (Set *)malloc(sizeof(Set)/sizeof(char));
Node_t *node = NULL;
Node_t *head = NULL;

if(*sets == NULL)
{
temp->size = 0;
temp->head = NULL;
*sets = temp;
node = (Node_t *)malloc(sizeof(Node_t)/sizeof(char));
if(node != NULL)
{
node->next = NULL;
node->value = data;
/*更新集合指針*/
temp->head = node;
temp->size ++;
*sets = temp;

temp = NULL;
return true;
}
}
else/*已經(jīng)存在部分集合*/
{
/******************************
采用順序存儲(chǔ)的方式插入新的元素
首先查找是否存在值，有不做任何操作
不存在，則按值大小找到合適的位置
******************************/

/*遍歷*/
if((*sets)->head != NULL)
{
/*更新表頭*/
if((*sets)->head->value > data)
{
node = (Node_t *)malloc(sizeof(Node_t)/sizeof(char));
if(node == NULL)
return false;
node->next = (*sets)->head;
node->value = data;
(*sets)->head = node;
(*sets)->size ++;

return true;
}
else if((*sets)->head->value == data)
{
return true;
}

/*從下一個(gè)節(jié)點(diǎn)開始*/
head = (*sets)->head;
node = head;

while(head->next != NULL)
{
/*已經(jīng)存在*/
if(head->next->value == data)
{
return true;
}
/*找到合適的位置,并插入*/
else if(head->next->value > data)
{
node = (Node_t *)malloc(sizeof(Node_t)/sizeof(char));
if(node == NULL)
return false;
node->value = data;
node->next = head->next;
head->next = node;
(*sets)->size ++;

return true;
}
else
{
head = head->next;
}
}
/*說(shuō)明以上不存在該值*/
node = (Node_t *)malloc(sizeof(Node_t)/sizeof(char));
if(node == NULL)
return false;
node->value = data;
node->next = NULL;
head->next = node;
(*sets)->size ++;
return true;
}
else
{
node = (Node_t *)malloc(sizeof(Node_t)/sizeof(char));
if(node == NULL)
return false;
node->value = data;
node->next = NULL;
(*sets)->head = node;
(*sets)->size ++;
return true;
}
}
return false;
}

查找、刪除元素操作，充分利用了前面的升序存儲(chǔ)關(guān)系。