本文小编为大家详细介绍“怎么用C语言手写集合List”，内容详细，步骤清晰，细节处理妥当，希望这篇“怎么用C语言手写集合List”文章能帮助大家解决疑惑，下面跟着小编的思路慢慢深入，一起来学习新知识吧。
数组长度是固定的,那么在很多时候我们并不知道到底有多少数据需要存储,这时候我么就需要一个可变长度的数组来进行存储,在C语言中需要我们自己进行定义,我们称为集合
typedef struct charlist {
char **str;
int len;
int capacity;
}CharList;
typedef int boolean;//定义一个布尔类型
#define TRUE 1
#define FALSE 0//创建一个空节点, 可以指定容量默认为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);
}读到这里，这篇“怎么用C语言手写集合List”文章已经介绍完毕，想要掌握这篇文章的知识点还需要大家自己动手实践使用过才能领会，如果想了解更多相关内容的文章，欢迎关注亿速云行业资讯频道。
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
