C.Interface.And.Implementations—set的实现

2024-08-24 18:18
文章标签 interface implementations set 实现

本文主要是介绍C.Interface.And.Implementations—set的实现，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1、A set is an  unordered collection of distinct members. 

2、The basic operations on a set are testing  for membership, adding members, and removing members. 

3、Other operations include set union, intersection, difference, and symmetric difference. 


set实现类似于table(key-value系统)的实现，采用类似的“哈希表和链表”的底层数据结构。可以参看上一章的内容。


=============================set.h==============================

#ifndef SET_INCLUDED
#define SET_INCLUDED#define T Set_T
typedef struct T *T;//exported functions
extern T      Set_new   (int hint,int cmp(const void *x, const void *y),unsigned hash(const void *x));extern void   Set_free  (T *set);
extern int    Set_length(T set);
extern int    Set_member(T set, const void *member);
extern void   Set_put   (T set, const void *member);
extern void  *Set_remove(T set, const void *member);
extern void   Set_map   (T set,void apply(const void *member, void *cl), void *cl);
extern void **Set_toArray(T set, void *end);
extern T      Set_union (T s, T t);
extern T      Set_inter (T s, T t);
extern T      Set_minus (T s, T t);
extern T      Set_diff  (T s, T t);#undef
#endif

=============================set.c============================ 

#include <limits.h>
#include <stddef.h>
#include "mem.h"
#include "assert.h"
#include "arith.h"
#include "set.h"#define T Set_T//types
struct T{int length;unsigned timestamp;int (*cmp)(const void *x, const void *y);unsigned (*hash)(const void *x);int size;struct member{struct member *link;const void *member;} **buckets;
}//static functions
static int cmpatom(const void *x, const void *y){return x != y;
}static unsigned hashatom(const void *x){return (unsigned long)x>>2;
}static T copy(T t, int hint){T set;assert(t);set = Set_new(hint, t->cmp, t->hash);{int i;struct member *q;for(i = 0; i < t->size; ++i){for(q = t->buckets[i]; q; q = q->link){struct member *p;const void *member = q->member;int i = (*set->hash)(member)%set->size;NEW(p);p->member = member;p->link = set->buckets[i];set->buckets[i] = p;set->length++;}}}return set;
}//functions
T Set_new(int hint,int cmp(const void *x, const void *y),unsigned hash(const void *x)){T set;int i;static int primes[] = { 509, 509, 1021, 2053, 4093,8191, 16381, 32771, 65521, INT_MAX };assert(hint >= 0);for(i = 1; primes[i] < hint; ++i){;set = ALLOC(sizeof(*set) +primes[i-1]*sizeof(set->buckets[0]));set->size = primes[i-1];set->cmp = cmp ? cmp : cmpatom;set->hash = hash ? hash : hashatom;set->buckets = (struct member **)(set + 1);for(i = 0; i < set->size; ++i){set->buckets[i] = NULL;}set->length = 0;set->timestamp = 0;return set;
}int Set_member(T set, const void *member){int i;struct member *p;assert(set);assert(member);//search set for memberi = (*set->hash)(member)%set->size;for(p = set->buckets[i]; p; p = p->link){if((*set->cmp)(member, p->member) == 0)break;}return p != NULL;
}void Set_put(T set, const void *member){int i;struct member *p;assert(set);assert(member);//search set for memberi = (*set->hash)(member)%set->size;for(p = set->buckets[i]; p; p = p->link){if((*set->cmp)(member, p->member) == 0)break;}if(p == NULL){//add member to setNEW(p);p->member = member;p->link = set->buckets[i];set->buckets[i] = p;set->length++;}else{p->member = member;}set->timestamp++;
}void *Set_remove(T set, const void *member){int i;struct member **pp;assert(set);assert(member);set->timestamp++;i = (*set->hash)(member)%set->size;for(pp = &set->buckets[i]; *pp; pp = &(*pp)->link){if((*set->cmp)(member, (*pp)->member) == 0){struct member *p = *pp;*pp = p->link;member = p->member;FREE(p);set->length--;retunr (void *)member;}}return NULL;
}int Set_length(T set){assert(set);return set->length;
}void Set_free(T *set){assert(set && *set);if((*set)->length > 0){int i;struct member *p; *q;for(i = 0; i < (*set)->size; ++i){for(p = (*set)->buckets[i]; p; p = q){q = p->link;FREE(p);}}}FREE(*set);
}void Set_map(T set,void apply(const void *member,  void *cl), void *cl){int i;unsigned stamp;struct member *p;assert(set);assert(apply);stamp = set->timestamp;for(i = 0; i < set->size; ++i){for(p = set->buckets[i]; p; p = p->link){apply(p->member, cl);assert(set->timestamp == stamp);}}
}void **Set_toArray(T set, void *end){int i, j = 0;void **array;struct member *p;assert(set);array = ALLOC((set->length + 1)*sizeof(*array));for(i = 0; i < set->size; ++i){for(p = set->buckets[i]; p; p = p->link){array[j++] = (void *)p->member;}}array[j] = end;return array; 
}T Set_union(T s, T t){if(s == NULL){assert(t);return copy(t, t->size);}else if( t == NULL){return copy(s, s->size);}else{T set = copy(s, Arith_max(s->size, t->size));assert(s->cmp == t->cmp && s->hash == t->hash);{//for each member q in tint i;struct member *q;for(i = 0; i < t->size; ++i){for(q = t->buckets[i]; q; q = q->link){Set_put(set, q->member);}}}return set;}
}T Set_inter(T s, T t){if(s == NULL){assert(t);return Set_new(t->size, t->cmp, t->hash);}else if( t == NULL){return Set_new(s->size, s->cmp, s->hash);}else if(s->length < t->length){return Set_inter(t, s);}else{T set = Set_new(Arith_min(s->size, t->size), s->cmp, s->hash);assert(s->cmp == t->cmp && s->hash == t->hash);{int i;struct member *q;for(i = 0; i < t->size; ++i){for(q = t->buckets[i]; q; q = q->link){if(Set_member(s, q->member)){struct member *pconst void *member = q->member;int i = (*set->hash)(member)%set->size;NEW(p);p->member = member;p->link = set->buckets[i];set->buckets[i] = p;set->length++;}}}}return set;}
}T Set_minus(T t, T s){if(t == NULL){assert(s);return Set_new(s->size, s->cmp, s->hash);}else if(s == NULL){return copy(t, t->size);}else{T set = Set_new(Arith_min(s->size, t->size),s->cmp, s->hash);assert(s->cmp == t->cmp && s->hash == t->hash);{int i;struct member *q;for(i = 0; i < t->size; ++i){for(q = t->buckets[i]; q; q = q->link){if(!Set_member(s, q->member)){struct member *p;const void *member = q->member;int i = (*set->hash)(member)%set->size;NEW(p);p->member = member;p->link = set->buckets[i];set->buckets[i] = p;set->length++;}}}}return set;}
}T Set_diff(T s, T t){if(s == NULL){assert(t);return copy(t, t->size);}else if(t == NULL){return copy(s, s->size);}else{T set = Set_new(Arith_min(s->size, t->size),s->cmp, s->hash);assert(s->cmp == t->cmp && s->hash == t->hash);{int i;struct member *q;for(i = 0; i < t->size; ++i){for(q = t->buckets[i]; q; q = q->link){if(!Set_member(s, q->member)){struct member *p;const void *member = q->member;int i = (*set->hash)(member)%set->size;NEW(p);p->member = member;p->link = set->buckets[i];set->buckets[i] = p;set->length++;}}}}{T u = t; t = s; s = u;}{int i;struct member *q;for(i = 0; i < t->size; ++i){for(q = t->buckets[i]; q; q = q->link){if(!Set_member(s, q->member)){struct member *p;const void *member = q->member;int i = (*set->hash)(member)%set->size;NEW(p);p->member = member;p->link = set->buckets[i];set->buckets[i] = p;set->length++;}}}}return set;}
}


这篇关于C.Interface.And.Implementations—set的实现的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1103235。

相关文章

hdu1043（八数码问题，广搜 + hash（实现状态压缩） ）

hdu1043（八数码问题，广搜 + hash（实现状态压缩） ）

利用康拓展开将一个排列映射成一个自然数，然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu
阅读更多...
【C++】_list常用方法解析及模拟实现

【C++】_list常用方法解析及模拟实现

相信自己的力量，只要对自己始终保持信心，尽自己最大努力去完成任何事，就算事情最终结果是失败了，努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一：什么是list？ •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二：list常用接口 •🌰1.默认成员函数 🔥构造函数（⭐） 🔥析构函数 •🌰2.list对象
阅读更多...
【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

✨✨ 欢迎大家来到景天科技苑✨✨ 🎈🎈 养成好习惯，先赞后看哦~🎈🎈 🏆 作者简介：景天科技苑 🏆《头衔》：大厂架构师，华为云开发者社区专家博主，阿里云开发者社区专家博主，CSDN全栈领域优质创作者，掘金优秀博主，51CTO博客专家等。 🏆《博客》：Python全栈，前后端开发，小程序开发，人工智能，js逆向，App逆向，网络系统安全，数据分析，Django，fastapi
阅读更多...
让树莓派智能语音助手实现定时提醒功能

让树莓派智能语音助手实现定时提醒功能

最初的时候是想直接在rasa 的chatbot上实现，因为rasa本身是带有remindschedule模块的。不过经过一番折腾后，忽然发现，chatbot上实现的定时，语音助手不一定会有响应。因为，我目前语音助手的代码设置了长时间无应答会结束对话，这样一来，chatbot定时提醒的触发就不会被语音助手获悉。那怎么让语音助手也具有定时提醒功能呢？ 我最后选择的方法是用threading.Time
阅读更多...
Android实现任意版本设置默认的锁屏壁纸和桌面壁纸（两张壁纸可不一致）

Android实现任意版本设置默认的锁屏壁纸和桌面壁纸（两张壁纸可不一致）

客户有些需求需要设置默认壁纸和锁屏壁纸  在默认情况下 这两个壁纸是相同的  如果需要默认的锁屏壁纸和桌面壁纸不一样 需要额外修改 Android13实现 替换默认桌面壁纸： 将图片文件替换frameworks/base/core/res/res/drawable-nodpi/default_wallpaper.*  （注意不能是bmp格式） 替换默认锁屏壁纸： 将图片资源放入vendo
阅读更多...
C#实战|大乐透选号器[6]：实现实时显示已选择的红蓝球数量

C#实战|大乐透选号器[6]：实现实时显示已选择的红蓝球数量

哈喽，你好啊，我是雷工。 关于大乐透选号器在前面已经记录了5篇笔记，这是第6篇； 接下来实现实时显示当前选中红球数量，蓝球数量； 以下为练习笔记。 01 效果演示 当选择和取消选择红球或蓝球时，在对应的位置显示实时已选择的红球、蓝球的数量； 02 标签名称 分别设置Label标签名称为：lblRedCount、lblBlueCount
阅读更多...
Kubernetes PodSecurityPolicy：PSP能实现的5种主要安全策略

Kubernetes PodSecurityPolicy：PSP能实现的5种主要安全策略

Kubernetes PodSecurityPolicy：PSP能实现的5种主要安全策略 1. 特权模式限制2. 宿主机资源隔离3. 用户和组管理4. 权限提升控制5. SELinux配置 💖The Begin💖点点关注，收藏不迷路💖 Kubernetes的PodSecurityPolicy（PSP）是一个关键的安全特性，它在Pod创建之前实施安全策略，确保P
阅读更多...
poj 3050 dfs + set的妙用

poj 3050 dfs + set的妙用

题意: 给一个5x5的矩阵，求由多少个由连续6个元素组成的不一样的字符的个数。 解析： dfs + set去重搞定。 代码： #include <iostream>#include <cstdio>#include <set>#include <cstdlib>#include <algorithm>#include <cstring>#include <cm
阅读更多...
工厂ERP管理系统实现源码（JAVA）

工厂ERP管理系统实现源码（JAVA）

工厂进销存管理系统是一个集采购管理、仓库管理、生产管理和销售管理于一体的综合解决方案。该系统旨在帮助企业优化流程、提高效率、降低成本，并实时掌握各环节的运营状况。 在采购管理方面，系统能够处理采购订单、供应商管理和采购入库等流程，确保采购过程的透明和高效。仓库管理方面，实现库存的精准管理，包括入库、出库、盘点等操作，确保库存数据的准确性和实时性。 生产管理模块则涵盖了生产计划制定、物料需求计划、
阅读更多...
C++——stack、queue的实现及deque的介绍

C++——stack、queue的实现及deque的介绍

目录 1.stack与queue的实现 1.1stack的实现  1.2 queue的实现 2.重温vector、list、stack、queue的介绍 2.1 STL标准库中stack和queue的底层结构  3.deque的简单介绍 3.1为什么选择deque作为stack和queue的底层默认容器  3.2 STL中对stack与queue的模拟实现 ①stack模拟实现
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2