集合-用链表实现集合
程序员文章站
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 }