怎么用C语言手写集合List(c语言,list,开发技术)

本文小编为大家详细介绍“怎么用C语言手写集合List”，内容详细，步骤清晰，细节处理妥当，希望这篇“怎么用C语言手写集合List”文章能帮助大家解决疑惑，下面跟着小编的思路慢慢深入，一起来学习新知识吧。

前沿

数组长度是固定的,那么在很多时候我们并不知道到底有多少数据需要存储,这时候我么就需要一个可变长度的数组来进行存储,在C语言中需要我们自己进行定义,我们称为集合

定义结构

typedefstructcharlist{char**str;intlen;intcapacity;}CharList;typedefintboolean;//定义一个布尔类型#defineTRUE1#defineFALSE0

创建List

//创建一个空节点,可以指定容量默认为10CharList*createCharList(intsize){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;returncharList;}

扩容

//扩容staticvoiddilatation(CharList**pCharList){CharList*charList=*pCharList;intcapacity1=charList->capacity;//获取当前节点的容积intsize=capacity1+(capacity1*0.75);//容积增加charList->capacity=size;//更新容积char**p1=(char**)realloc(charList->str,size*sizeof(char*));charList->str=p1;}

创建数据节点

staticchar*createData(char*data){//插入数据char*pData=(char*)calloc(strlen(data)+1,sizeof(char));//为啥要+1因为字符串结尾需要有一个空字符strcpy(pData,data);returnpData;}

给集合添加值

//添加一个值,容量不够会自动在原有基础上进行扩容*0.75voidaddCharList(CharList**pCharList,char*value){CharList*charList=*pCharList;intlen1=charList->len;//获取当前节点的长度intcapacity1=charList->capacity;//获取数组的容量if(len1==capacity1){dilatation(pCharList);//扩容}charList->str[len1]=createData(value);//插入数据charList->len++;}

删除集合内指定的值

voiddeleteCharList(CharList**pCharList,char*value){CharList*charList=*pCharList;intlen1=charList->len;//获取当前节点的长度for(inti=0;i<len1;++i){if(strcmp(charList->str[i],value)==0){//找到了free(charList->str[i]);//释放内存for(intj=i;j<len1-1;++j){//后面的节点向前移动charList->str[j]=charList->str[j+1];}charList->len--;break;}}}

删除集合内指定下标的值

//删除集合内指定下标的值voiddeleteCharListByIndex(CharList**pCharList,intindex){CharList*charList=*pCharList;intlen1=charList->len;//获取当前节点的长度if(index<0||index>=len1){return;}free(charList->str[index]);//释放内存for(intj=index;j<len1-1;++j){//后面的节点向前移动charList->str[j]=charList->str[j+1];}charList->len--;}

打印集合

//打印所有节点voidprintCharList(CharList*pCharList){intlen1=pCharList->len;for(inti=0;i<len1;i++){printf("%s\n",pCharList->str[i]);}}

迭代器

先这样简单的使用,如果有需要可以自己定义一套迭代机制

voidcharListIterator(CharList*pCharList,void(*func)(char*)){intlen1=pCharList->len;for(inti=0;i<len1;i++){func(pCharList->str[i]);}}

查询指定元素的下标(第一个)

//查询指定元素的下标,没有找到返回-1intcharListIndexOf(CharList*pCharList,char*value){intlen1=pCharList->len;for(inti=0;i<len1;i++){if(strcmp(pCharList->str[i],value)==0){returni;}}return-1;}

末尾查询指定元素下标(第一个)

intcharListLastIndexOf(CharList*pCharList,char*value){intlen1=pCharList->len;for(inti=len1-1;i>=0;i--){if(strcmp(pCharList->str[i],value)==0){returni;}}return-1;}

判断数组是否有序

/***判断数组是否有序*@parampCharList*@paramtypeTRUE:按照ASCII码排序FALSE:安装字符长度排序*@return*/booleancharListIsSorted(CharList*pCharList,booleantype){intlen1=pCharList->len;booleanresult;//返回结果if(type){//按照ASCII码排序方式进行判断//从小到大for(inti=0;i<len1-1;i++){if(strcmp(pCharList->str[i],pCharList->str[i+1])>0){result=FALSE;break;}}//从大到小for(inti=0;i<len1-1;i++){if(strcmp(pCharList->str[i],pCharList->str[i+1])<0){result=FALSE;break;}}}else{//从小到大for(inti=0;i<len1-1;i++){if(strlen(pCharList->str[i])>strlen(pCharList->str[i+1])){result=FALSE;break;}}//从大到小for(inti=0;i<len1-1;i++){if(strlen(pCharList->str[i])<strlen(pCharList->str[i+1])){result=FALSE;break;}}}returnresult;}

二分查询

/***二分查询,没有找到返回-1以ASCII码查询*@parampCharList*@paramvalue*@return找到返回下标,没有找到返回-1*/intcharListBinarySearch(CharList*pCharList,char*value){if(!charListIsSorted(pCharList,TRUE)){//判断是否是排序的数组,如果不是那么我们给排序//二分查询需要是有序的数组,所以需要先排序以ASCII码进行排序charListSort(pCharList,1);}intlen1=pCharList->len;intlow=0;inthigh=len1-1;while(low<=high){intmid=(low+high)/2;//中间下标if(strcmp(pCharList->str[mid],value)==0){//找到了returnmid;}if(strcmp(pCharList->str[mid],value)>0){//中间值比查找值大high=mid-1;//向左找}else{//比中间值比差值值小low=mid+1;//向右找}}return-1;}

修改集合指定元素的值

//修改指定元素的值voidcharListSet(CharList*pCharList,char*value,intindex){intlen1=pCharList->len;if(index<0||index>=len1){return;}free(pCharList->str[index]);pCharList->str[index]=createData(value);}

快速排序

//快速排序(根据ASCII码排序,从小到大)staticvoidquickSort(char**str,intleft,intright){if(left>=right){return;}char*p=str[left];inti=left;intj=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);}//快速排序(根据长度排序,从小到大)staticvoidquickSortByLen(char**str,intleft,intright){if(left>=right){return;}char*p=str[left];inti=left;intj=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码排序,从小到大,或者根据长度排序,从小到大*@parampCharList*@paramtypeTRUE就是ASCII码排序,FALSE就是根据长度排序*/voidcharListSort(CharList*pCharList,booleantype){if(type){quickSort(pCharList->str,0,pCharList->len-1);}else{quickSortByLen(pCharList->str,0,pCharList->len-1);}}

集合去重

//去重voidcharListDistinct(CharList*pCharList){intlen1=pCharList->len;for(inti=0;i<len1;i++){for(intj=i+1;j<len1;j++){if(strcmp(pCharList->str[i],pCharList->str[j])==0){free(pCharList->str[j]);//释放内存for(intk=j;k<len1-1;++k){//将后面的内容向前移动pCharList->str[k]=pCharList->str[k+1];}//去除结尾的元素pCharList->str[len1-1]=NULL;len1--;pCharList->len--;//长度减1j--;//重新比较}}}}

集合复制

//集合复制,返回新集合CharList*charListCopy(CharList*pCharList){intlen1=pCharList->len;CharList*pNewCharList=createCharList(len1);for(inti=0;i<len1;i++){char*p=createData(pCharList->str[i]);addCharList(&pNewCharList,p);}returnpNewCharList;}

集合合并

//集合合并,返回新集合CharList*charListMerge(CharList*pCharList1,CharList*pCharList2){intlen1=pCharList1->len;intlen2=pCharList2->len;CharList*pNewCharList=createCharList(len1+len2);for(inti=0;i<len1;i++){char*p=createData(pCharList1->str[i]);addCharList(&pNewCharList,p);}for(inti=0;i<len2;i++){char*p=createData(pCharList2->str[i]);addCharList(&pNewCharList,p);}returnpNewCharList;}

集合差集

记A，B是两个集合 ,A集合中不存在B集合的元素,那么A集合就是B集合的差集

//集合差集,返回新集合CharList*charListDifference(CharList*pCharList1,CharList*pCharList2){intlen1=pCharList1->len;intlen2=pCharList2->len;CharList*pNewCharList=charListCopy(pCharList1);for(inti=0;i<len2;i++){intindex=charListIndexOf(pNewCharList,pCharList2->str[i]);if(index!=-1){free(pNewCharList->str[index]);//释放内存for(intj=index;j<len1-1;++j){//将后面的内容向前移动pNewCharList->str[j]=pNewCharList->str[j+1];}//去除结尾的元素pNewCharList->str[len1-1]=NULL;len1--;pNewCharList->len--;//长度减1i--;//重新比较}}returnpNewCharList;}

集合补集

对于两个给定集合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);returnpCharlist;}

集合并集

对于两个给定集合A、B，由两个集合所有元素构成的集合,叫做A和B的并集。(需要去重只保留一个)

//集合并集,返回新集合CharList*charListUnion(CharList*pCharList1,CharList*pCharList2){CharList*pCharlist1=charListDifference(pCharList1,pCharList2);CharList*pCharlist2=charListMerge(pCharlist1,pCharList2);returnpCharlist2;}

集合交集

对于两个给定集合A、B，属于A又属于B的所有元素构成的集合，叫做A和B的交集。

//集合交集,返回新集合CharList*charListIntersection(CharList*pCharList1,CharList*pCharList2){intlen2=pCharList2->len;CharList*pNewCharList=createCharList(len2/2);for(inti=0;i<len2;++i){intof=charListIndexOf(pCharList1,pCharList2->str[i]);if(of!=-1){addCharList(&pNewCharList,pCharList2->str[i]);}}returnpNewCharList;}

销毁集合

//释放内存voidcharListClean(CharList*pCharList){//清理数组内元素for(inti=0;i<pCharList->len;++i){free(pCharList->str[i]);}//清除数组free(pCharList);}

读到这里，这篇“怎么用C语言手写集合List”文章已经介绍完毕，想要掌握这篇文章的知识点还需要大家自己动手实践使用过才能领会，如果想了解更多相关内容的文章，欢迎关注亿速云行业资讯频道。