C语言集合
胡安民 人气:6前沿
数组长度是固定的,那么在很多时候我们并不知道到底有多少数据需要存储,这时候我么就需要一个可变长度的数组来进行存储,在C语言中需要我们自己进行定义,我们称为集合
定义结构
typedef struct charlist { char **str; int len; int capacity; }CharList; typedef int boolean;//定义一个布尔类型 #define TRUE 1 #define FALSE 0
创建List
//创建一个空节点, 可以指定容量默认为10 CharList *createCharList(int size) { if (size < 10) { size = 10; } //初始化结构体和一个2级指针 CharList *charList = (CharList *) calloc(1, sizeof(CharList)); charList->str= (char **) calloc(size, sizeof(char *)); charList->len = 0; charList->capacity = size; return charList; }
扩容
//扩容 static void dilatation(CharList **pCharList) { CharList *charList = *pCharList; int capacity1 =charList->capacity;//获取当前节点的容积 int size = capacity1 + (capacity1 * 0.75);//容积增加 charList->capacity= size;//更新容积 char **p1 = (char **) realloc(charList->str,size*sizeof(char *)); charList->str=p1; }
创建数据节点
static char *createData(char *data){ //插入数据 char *pData = (char *) calloc(strlen(data) + 1,sizeof(char) ); //为啥要+1因为字符串结尾需要有一个空字符 strcpy(pData,data); return pData; }
给集合添加值
//添加一个值 ,容量不够会自动在原有基础上进行扩容*0.75 void addCharList(CharList **pCharList, char *value) { CharList *charList = *pCharList; int len1 = charList->len;//获取当前节点的长度 int capacity1 =charList->capacity;//获取数组的容量 if (len1 == capacity1) { dilatation(pCharList);//扩容 } charList->str[len1] = createData(value);//插入数据 charList->len++; }
删除集合内指定的值
void deleteCharList(CharList **pCharList, char *value) { CharList *charList = *pCharList; int len1 = charList->len;//获取当前节点的长度 for (int i = 0; i < len1; ++i) { if (strcmp(charList->str[i],value)==0) {//找到了 free(charList->str[i]);//释放内存 for (int j = i; j < len1 - 1; ++j) {//后面的节点向前移动 charList->str[j] = charList->str[j + 1]; } charList->len--; break; } } }
删除集合内指定下标的值
//删除集合内指定下标的值 void deleteCharListByIndex(CharList **pCharList, int index) { CharList *charList = *pCharList; int len1 = charList->len;//获取当前节点的长度 if (index < 0 || index >= len1) { return; } free(charList->str[index]);//释放内存 for (int j = index; j < len1 - 1; ++j) {//后面的节点向前移动 charList->str[j] = charList->str[j + 1]; } charList->len--; }
打印集合
//打印所有节点 void printCharList(CharList *pCharList) { int len1 = pCharList->len; for (int i = 0; i < len1; i++) { printf("%s\n", pCharList->str[i]); } }
迭代器
先这样简单的使用,如果有需要可以自己定义一套迭代机制
void charListIterator(CharList *pCharList,void (*func)(char *)) { int len1 = pCharList->len; for (int i = 0; i < len1; i++) { func(pCharList->str[i]); } }
查询指定元素的下标(第一个)
//查询指定元素的下标 ,没有找到返回-1 int charListIndexOf(CharList *pCharList, char *value) { int len1 = pCharList->len; for (int i = 0; i < len1; i++) { if (strcmp(pCharList->str[i],value)==0) { return i; } } return -1; }
末尾查询指定元素下标(第一个)
int charListLastIndexOf(CharList *pCharList, char *value) { int len1 = pCharList->len; for (int i = len1 - 1; i >= 0; i--) { if (strcmp(pCharList->str[i],value)==0) { return i; } } return -1; }
判断数组是否有序
/** * 判断数组是否有序 * @param pCharList * @param type TRUE: 按照ASCII码排序 FALSE: 安装字符长度排序 * @return */ boolean charListIsSorted(CharList *pCharList,boolean type) { int len1 = pCharList->len; boolean result; //返回结果 if(type){//按照ASCII码排序方式进行判断 //从小到大 for (int i = 0; i < len1 - 1; i++) { if (strcmp(pCharList->str[i],pCharList->str[i + 1])>0) { result=FALSE; break; } } //从大到小 for (int i = 0; i < len1 - 1; i++) { if (strcmp(pCharList->str[i],pCharList->str[i + 1])<0) { result=FALSE; break; } } }else{ //从小到大 for (int i = 0; i < len1 - 1; i++) { if (strlen(pCharList->str[i])>strlen(pCharList->str[i + 1])) { result=FALSE; break; } } //从大到小 for (int i = 0; i < len1 - 1; i++) { if (strlen(pCharList->str[i])<strlen(pCharList->str[i + 1])) { result=FALSE; break; } } } return result; }
二分查询
/** * 二分查询,没有找到返回-1 以ASCII码查询 * @param pCharList * @param value * @return 找到返回下标,没有找到返回-1 */ int charListBinarySearch(CharList *pCharList, char *value) { if(!charListIsSorted(pCharList,TRUE)){ //判断是否是排序的数组,如果不是那么我们给排序 //二分查询需要是有序的数组,所以需要先排序 以ASCII码进行排序 charListSort(pCharList,1); } int len1 = pCharList->len; int low = 0; int high = len1 - 1; while (low <= high) { int mid = (low + high) / 2;//中间下标 if (strcmp(pCharList->str[mid],value)==0) {//找到了 return mid; } if (strcmp(pCharList->str[mid],value)>0) {//中间值比查找值大 high = mid - 1;//向左找 } else {//比中间值比差值值小 low = mid + 1;//向右找 } } return -1; }
修改集合指定元素的值
//修改指定元素的值 void charListSet(CharList *pCharList, char *value, int index) { int len1 = pCharList->len; if (index < 0 || index >= len1) { return; } free(pCharList->str[index]); pCharList->str[index] = createData(value); }
快速排序
//快速排序 (根据ASCII码排序,从小到大) static void quickSort(char **str, int left, int right) { if (left >= right) { return; } char *p = str[left]; int i = left; int j = right; while (i < j) { while (i < j && strcmp(str[j],p)>=0) { j--; } str[i] = str[j]; while (i < j && strcmp(str[i],p)<=0) { i++; } str[j] = str[i]; } str[i] = p; quickSort(str, left, i - 1); quickSort(str, i + 1, right); } //快速排序(根据长度排序,从小到大) static void quickSortByLen(char **str, int left, int right) { if (left >= right) { return; } char *p = str[left]; int i = left; int j = right; while (i < j) { while (i < j && strlen(str[j])>=strlen(p)) { j--; } str[i] = str[j]; while (i < j && strlen(str[i])<=strlen(p)) { i++; } str[j] = str[i]; } str[i] = p; quickSortByLen(str, left, i - 1); quickSortByLen(str, i + 1, right); } /** * 根据ASCII码排序,从小到大,或者根据长度排序,从小到大 * @param pCharList * @param type TRUE就是ASCII码排序, FALSE就是根据长度排序 */ void charListSort(CharList *pCharList, boolean type) { if(type){ quickSort(pCharList->str, 0, pCharList->len-1); }else{ quickSortByLen(pCharList->str, 0, pCharList->len-1); } }
集合去重
//去重 void charListDistinct(CharList *pCharList) { int len1 = pCharList->len; for (int i = 0; i < len1; i++) { for (int j = i + 1; j < len1; j++) { if (strcmp(pCharList->str[i],pCharList->str[j])==0) { free(pCharList->str[j]);//释放内存 for (int k = j; k < len1 - 1; ++k) {//将后面的内容向前移动 pCharList->str[k] = pCharList->str[k + 1]; } //去除结尾的元素 pCharList->str[len1 - 1]=NULL; len1--; pCharList->len--;//长度减1 j--;//重新比较 } } } }
集合复制
//集合复制,返回新集合 CharList *charListCopy(CharList *pCharList) { int len1 = pCharList->len; CharList *pNewCharList = createCharList(len1); for (int i = 0; i < len1; i++) { char *p = createData(pCharList->str[i]); addCharList(&pNewCharList, p); } return pNewCharList; }
集合合并
//集合合并,返回新集合 CharList *charListMerge(CharList *pCharList1, CharList *pCharList2) { int len1 = pCharList1->len; int len2 = pCharList2->len; CharList *pNewCharList = createCharList(len1 + len2); for (int i = 0; i < len1; i++) { char *p = createData(pCharList1->str[i]); addCharList(&pNewCharList, p); } for (int i = 0; i < len2; i++) { char *p = createData(pCharList2->str[i]); addCharList(&pNewCharList, p); } return pNewCharList; }
集合差集
记A,B是两个集合 ,A集合中不存在B集合的元素,那么A集合就是B集合的差集
//集合差集,返回新集合 CharList *charListDifference(CharList *pCharList1, CharList *pCharList2) { int len1 = pCharList1->len; int len2 = pCharList2->len; CharList *pNewCharList = charListCopy(pCharList1); for (int i = 0; i < len2; i++) { int index = charListIndexOf(pNewCharList, pCharList2->str[i]); if (index != -1) { free(pNewCharList->str[index]);//释放内存 for (int j = index; j < len1 - 1; ++j) {//将后面的内容向前移动 pNewCharList->str[j] = pNewCharList->str[j + 1]; } //去除结尾的元素 pNewCharList->str[len1 - 1]=NULL; len1--; pNewCharList->len--;//长度减1 i--;//重新比较 } } return pNewCharList; }
集合补集
对于两个给定集合A、B, 如果A集合中不存在B集合元素,那么B集合就是A集合的补集,当然反过来也可以说A集合是B集合的补集
//集合补集,返回新集合 CharList *charListComplement(CharList *pCharList1, CharList *pCharList2) { CharList *pCharlist1 = charListDifference(pCharList1, pCharList2); CharList *pCharlist2 = charListDifference(pCharList2, pCharList1); CharList *pCharlist = charListMerge(pCharlist1, pCharlist2); return pCharlist; }
集合并集
对于两个给定集合A、B,由两个集合所有元素构成的集合,叫做A和B的并集。(需要去重只保留一个)
//集合并集,返回新集合 CharList *charListUnion(CharList *pCharList1, CharList *pCharList2) { CharList *pCharlist1 = charListDifference(pCharList1, pCharList2); CharList *pCharlist2 = charListMerge(pCharlist1, pCharList2); return pCharlist2; }
集合交集
对于两个给定集合A、B,属于A又属于B的所有元素构成的集合,叫做A和B的交集。
//集合交集,返回新集合 CharList *charListIntersection(CharList *pCharList1, CharList *pCharList2) { int len2 = pCharList2->len; CharList *pNewCharList = createCharList(len2/2); for (int i = 0; i < len2; ++i){ int of = charListIndexOf(pCharList1, pCharList2->str[i]); if(of!=-1){ addCharList(&pNewCharList, pCharList2->str[i]); } } return pNewCharList; }
销毁集合
// 释放内存 void charListClean(CharList *pCharList) { //清理数组内元素 for (int i = 0; i < pCharList->len; ++i) { free(pCharList->str[i]); } //清除数组 free(pCharList); }
加载全部内容