這段時間一直在看C++相關(guān)的數(shù)據(jù)結(jié)構(gòu)，感覺STL庫的出現(xiàn)確實給C++實現(xiàn)一些基本的數(shù)據(jù)結(jié)構(gòu)更加的方便，特別是map、list、set、vector的靈活運用能實現(xiàn)很多強(qiáng)大的數(shù)據(jù)結(jié)構(gòu)，記得在一本書中曾經(jīng)讀到過“C++中算法的重要性沒有C語言中那么明顯，而是設(shè)計方法的問題”這句話的正確性有待于進(jìn)一步的考察，但是面向?qū)ο笾械母嗟氖且揽坷^承多態(tài)性實現(xiàn)多對象編程，而在C語言中更多的事依靠算法和數(shù)據(jù)結(jié)構(gòu)�；艘煌砩喜捎肅語言實現(xiàn)了一個簡單的集合操作，支持集合的創(chuàng)建，元素的查詢，刪除，支持集合的交集、差集、并集計算。
首先說明一下集合的ADT，肯定有包括基本的創(chuàng)建、刪除操作。以及某一個元素的插入和刪除操作。集合的一個重要特征就是元素的不重復(fù)性。這種方式我在實現(xiàn)的過程中通過鏈表管理一個集合，按照元素的大小進(jìn)行排列，之所以排列主要是為了方便刪除、查找元素的操作。實質(zhì)上集合對元素的順序是沒有要求的。
集合的交集：是指兩個集合元素相同的部分構(gòu)成的集合。
集合的差集：是指其中一個集合中除去另一個集合相同元素以后剩余的元素構(gòu)成的集合。
集合的并集：是指兩個集合的所有元素構(gòu)成的集合。
其中需要注意的就是集合的元素是不能重復(fù)的，本來我打算采用二叉查找樹的方式實現(xiàn)，因為這種樹型結(jié)構(gòu)便于快速的查詢，但是我采用元素的升序排序就能避免集合中漫無目的的查詢操作。畢竟實現(xiàn)二叉查找樹也增加了一個指針成員，而且還需要大量的操作。
簡要的說明一下我的過程：
基本的集合結(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ù)的實現(xiàn)是集合實現(xiàn)的最復(fù)雜的一個函數(shù)，之所以這么復(fù)雜是因為很多的操作都是基于該函數(shù)完成的，當(dāng)然也可以采用更精細(xì)的函數(shù)來實現(xiàn)，我開始的想法是將元素插入和創(chuàng)建操作合并，都基于一個函數(shù)進(jìn)行操作，但是寫完以后發(fā)現(xiàn)函數(shù)太長，而且比較爛，不夠必將還是完成了一些基本的操作。采用了升序存儲的方式，主要是為了后續(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)存在部分集合*/
{
/******************************
采用順序存儲的方式插入新的元素
首先查找是否存在值，有不做任何操作
不存在，則按值大小找到合適的位置
******************************/
/*遍歷*/
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)
{
/*已經(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;
}
}
/*說明以上不存在該值*/
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)系。
/***************************************
刪除集合中的某個元素
參數(shù): 指向集合指針的指針
需要刪除的元素
返回值： 是否刪除成功
***************************************/
bool delete_setElement(Set **s, int element)
{
Node_t *head = NULL;
Node_t *temp = NULL;
assert(*s);
head = (*s)->head;
// assert(head);
if(head == NULL)
{
return false;
}
/*表頭更新*/
if(head->value == element)
{
temp = head;
if(head->next != NULL)
head = head->next;
else
head = NULL;
(*s)->head = head;
(*s)->size --;
free(temp);
temp = NULL;
return true;
}
while(head->next != NULL)
{
/*刪除元素*/
if(head->next->value == element)
{
temp = head->next;
head->next = head->next->next;
free(temp);
(*s)->size --;
temp = NULL;
break;
}
/*不存在當(dāng)前元素*/
else if(head->next->value > element)
break;
else
head = head->next;
}
return true;
}
/****************************************
判斷元素是否在集合中
參數(shù)： 集合指針
元素值
返回值: 是否存在
*****************************************/
bool findElement(const Set *s, int Element)
{
// assert(s);
if(s == NULL)
{
return false;
}
Node_t *head = s->head;
while(head != NULL)
{
/*找得到當(dāng)前值*/
if(head->value == Element)
return true;
/*不存在當(dāng)前值*/
else if(head->value > Element)
break;
head = head->next;
}
return false;
}
最重要的一個函數(shù)，我認(rèn)為是集合的復(fù)制函數(shù)，這有點類似在C++中的復(fù)制構(gòu)造或者賦值操作符函數(shù)。
/****************************************
實現(xiàn)集合的復(fù)制操作
參數(shù)： 一個指向被創(chuàng)建集合的指針
一個集合指針
返回： 判斷是否成功
****************************************/
bool copySet(Set **dst,const Set *src)
{
Node_t *head = NULL;
assert(src);
head = src->head;
creat_nullset(dst);
while(head != NULL)
{
if(!create_set(dst,head->value))
return false;
head = head->next;
}
return true;
}
最后是集合的三個操作：主要是利用了前面定義的一些函數(shù)實現(xiàn)的，所以說前面的問題處理好了，基本的操作就是手到擒來的事。
/****************************************
實現(xiàn)兩個集合的并集
參數(shù):
分別是兩個Set集合的指針
返回值:
一個集合的指針
*****************************************/
Set * OrSets(const Set * s1, const Set *s2)
{
Set *news = NULL;
const Set *searchset = NULL;
Node_t *head = NULL;
assert(s1 != NULL || s2 != NULL);
if(get_setlength(s1) > get_setlength(s2))
{
copySet(&news,s1);
searchset = s2;
}
else
{
copySet(&news, s2);
searchset = s1;
}
head = searchset->head;
while(head != NULL)
{
if(!create_set(&news, head->value))
break;
head = head->next;
}
return news;
}
/*******************************************
實現(xiàn)兩個集合的交集
參數(shù)： 兩個集合指針
返回值： 新的集合
*******************************************/
Set * AndSets(const Set *s1, const Set *s2)
{
Set *newset = NULL;
const Set *searchset = NULL;
Node_t *head = NULL;
assert(s1 != NULL && s2 != NULL);
if(s1->head == NULL || s2->head == NULL)
{
/*空集合*/
creat_nullset(&newset);
return newset;
}
if(get_setlength(s1) > get_setlength(s2))
{
searchset = s1;
head = s2->head;
}
else
{
searchset = s2;
head = s1->head;
}
while(head != NULL)
{
if(findElement(searchset, head->value))
{
create_set(&newset, head->value);
}
head = head->next;
}
return newset;
}
/*********************************************
集合的差集操作
參數(shù)： 兩個集合的指針
返回值: 新的集合指針
*********************************************/
Set * XorSets(const Set *s1, const Set *s2)
{
Set *newset = NULL;
Node_t *head = NULL;
assert(s1 != NULL && s2 != NULL);
if(s1->head == NULL)
{
/*空集合*/
creat_nullset(&newset);
return newset;
}
if(s2->head == NULL)
{
copySet(&newset,s1);
return newset;
}
/*newset和s1是相同的*/
copySet(&newset,s1);
head = s1->head;
while(head != NULL)
{
/*如果s2中存在當(dāng)前元素，刪除*/
if(findElement(s2, head->value))
{
delete_setElement(&newset,head->value);
}
head = head->next;
}
return newset;
}
集合打印操作、集合的刪除操作
/*********************************************
打印集合
參數(shù): 集合指針
返回： void
**********************************************/
void print_set(const Set *s)
{
Node_t * head = NULL;
int i = 0;
assert(s);
head = s->head;
printf("{ ");
while(head != NULL)
{
++i;
printf("%d ",head->value);
if(i % 5 == 0 && i != 0)
{
i = 0;
// printf("\n");
}
head = head->next;
}
printf("}\n");
}
/*********************************************
刪除一個集合
參數(shù)： 指向集合指針的指針
返回值： void
**********************************************/
void delete_set(Set **s)
{
Node_t *head = NULL;
Node_t *temp = NULL;
// assert(*s);
if(*s == NULL)
return;
head = (*s)->head;
while(head != NULL)
{
temp = head;
head = head->next;
free(temp);
(*s)->size --;
temp = NULL;
}
free(*s);
*s = NULL;
}
最后是我的測試程序：
/************************************************
主函數(shù)
完成各個函數(shù)的測試工作
最后需要完成內(nèi)存的釋放
************************************************/
int main()
{
Set* sets1 = NULL;
Set* sets2 = NULL;
Set* sets3 = NULL;
Set* sets4 = NULL;
int i = 0;
int j = 0;
for(i = 0; i < 10; ++ i)
{
if(!create_set(&sets1, i+10))
break;
j = i + 10 - 5;
if(!create_set(&sets2, j))
break;
}
printf("Set1 : ");
print_set(sets1);
printf("Set2 : ");
print_set(sets2);
sets3 = OrSets(sets1,sets2);
printf("Set1 + Set2: ");
print_set(sets3);
sets3 = OrSets(sets2,sets1);
printf("Set2 + Set1: ");
print_set(sets3);
delete_set(&sets3);
sets3 = AndSets(sets1,sets2);
printf("Set1 * Set2: ");
print_set(sets3);
delete_set(&sets3);
sets3 = AndSets(sets2,sets1);
printf("Set2 * Set1: ");
print_set(sets3);
delete_set(&sets3);
sets3 = XorSets(sets1,sets2);
printf("Set1 - Set2: ");
print_set(sets3);
delete_set(&sets3);
// creat_nullset(&sets4);
sets3 = XorSets(sets2,sets1);
printf("Set2 - Set1: ");
print_set(sets3);
delete_set(&sets1);
delete_set(&sets2);
delete_set(&sets3);
delete_set(&sets4);
return 0;
}
實驗效果：
總結(jié)：
該實現(xiàn)并沒有考慮性能方面，基本上實現(xiàn)了集合的簡單操作。后面有時間再想想如何優(yōu)化查找和刪除操作。