集合-用链表实现集合

集合分可分为有序集合和无序集合，可以分别用有序链表和无序链表进行表示。

以下用有序链表表示有序集合。

• 集合的结构定义

 1 /*链表中的结点定义*/
 2 typedef struct node
 3 {
 4     listitem element;
 5     link next;
 6 }node, *link;
 7 
 8 /*集合定义*/
 9 typedef struct list
10 {
11     link frist;        //指向第一个元素的指针
12 }list,*set;

 

• 相关操作

  1 /*创建一个空集合*/
  2 set setinit()
  3 {
  4     set s = new list;
  5     s->frist = null;
  6     return s;
  7 }
  8 
  9 /*判断一个集合是否为空*/
 10 int setempty(set s)
 11 {
 12     return s->frist == null;
 13 }
 14 
 15 /*setsize(s)返回集合s的大小*/
 16 int setsize(set s)
 17 {
 18     int len;
 19     link curren = s->frist;
 20     len = 0;
 21     while (curren)
 22     {
 23         len++;
 24         curren = curren->next;
 25     }
 26     return len;
 27 }
 28 
 29 /*setassign(a,b)用集合b给集合a赋值，不能简单的将a->first指向b的first指针指向单元*/
 30 void setassign(set a, set b)
 31 {
 32     link a, b, c;
 33     b = b->frist;
 34     a->frist = null;
 35     if (b)
 36     {
 37         a->frist = new node;
 38         a = a->frist;
 39         a->element = b->element;
 40         a->next = null;
 41         b = b->next;
 42     }
 43     while (b)
 44     {
 45         c = new node;
 46         c->element = b->element;
 47         c->next = null;
 48         b = b->next;
 49         a->next = c;
 50         a = c;
 51     }
 52 }
 53 
 54 /*setintersection(a,b)通过遍历集合a和b的链表来实现交集*/
 55 set setintersection(set a, set b)
 56 {
 57     link a, b, p, q, r;
 58     set tmp = setinit();    //创建一个临时集合
 59     a = a->frist;
 60     b = b->frist;
 61     p = new node;
 62     q = p;
 63     while (a&&b)
 64     {
 65         if (a->element == b->element)
 66         {
 67             r = new node;
 68             r->element = a->element;
 69             r->next = null;
 70             p->next = r;
 71             p = r;
 72             a = a->next;
 73             b = b->next;
 74         }
 75         else if (a->element < b->element)
 76             a = a->next;
 77         else
 78             b = b->next;
 79     }
 80     if (p != q)    //p==q,此时集合无交集
 81         tmp->frist = q->next;
 82     delete q;
 83     return tmp;
 84 }
 85 
 86 /*setinsert(x,s)将元素x插入到集合s中*/
 87 void setinsert(listitem x, set s)
 88 {
 89     link p, q, r;
 90     p = s->frist;
 91     q = p;
 92     while (p&&p->element<x)
 93     {
 94         q = p;
 95         p = p->next;
 96     }
 97     if (p&&p->element == x)
 98         return;
 99     r = new node();
100     r->element = x;
101     r->next = p;
102     if (p == q)
103         s->frist = r;
104     else
105         q->next = r;
106 }