欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

集合-用链表实现集合

程序员文章站 2022-06-07 14:36:05
集合分可分为有序集合和无序集合,可以分别用有序链表和无序链表进行表示。 以下用有序链表表示有序集合。 集合的结构定义 相关操作 ......

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

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

  • 集合的结构定义
 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 }