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

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

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

簡要的說明一下我的過程：
基本的集合結構體：

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)建，該函數的實現(xiàn)是集合實現(xiàn)的最復雜的一個函數，之所以這么復雜是因為很多的操作都是基于該函數完成的，當然也可以采用更精細的函數來實現(xiàn)，我開始的想法是將元素插入和創(chuàng)建操作合并，都基于一個函數進行操作，但是寫完以后發(fā)現(xiàn)函數太長，而且比較爛，不夠必將還是完成了一些基本的操作。采用了升序存儲的方式，主要是為了后續(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/*已經存在部分集合*/
{
/******************************
采用順序存儲的方式插入新的元素
首先查找是否存在值，有不做任何操作
不存在，則按值大小找到合適的位置
******************************/

/*遍歷*/
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;
}

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

while(head->next != NULL)
{
/*已經存在*/
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;
}
}
/*說明以上不存在該值*/
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;
}

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