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

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

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

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

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í)現的最復雜的一個(gè)函數，之所以這么復雜是因為很多的操作都是基于該函數完成的，當然也可以采用更精細的函數來(lái)實(shí)現，我開(kāi)始的想法是將元素插入和創(chuàng )建操作合并，都基于一個(gè)函數進(jìn)行操作，但是寫(xiě)完以后發(fā)現函數太長(cháng)，而且比較爛，不夠必將還是完成了一些基本的操作。采用了升序存儲的方式，主要是為了后續的查找操作，注意鏈表的更新操作。

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)存在部分集合*/
{
/******************************
采用順序存儲的方式插入新的元素
首先查找是否存在值，有不做任何操作
不存在，則按值大小找到合適的位置
******************************/

/*遍歷*/
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è)節點(diǎn)開(kāi)始*/
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;
}

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