您好,登錄后才能下訂單哦!
本文小編為大家詳細(xì)介紹“怎么用C語言手寫集合List”,內(nèi)容詳細(xì),步驟清晰,細(xì)節(jié)處理妥當(dāng),希望這篇“怎么用C語言手寫集合List”文章能幫助大家解決疑惑,下面跟著小編的思路慢慢深入,一起來學(xué)習(xí)新知識(shí)吧。
數(shù)組長(zhǎng)度是固定的,那么在很多時(shí)候我們并不知道到底有多少數(shù)據(jù)需要存儲(chǔ),這時(shí)候我么就需要一個(gè)可變長(zhǎng)度的數(shù)組來進(jìn)行存儲(chǔ),在C語言中需要我們自己進(jìn)行定義,我們稱為集合
typedef struct charlist { char **str; int len; int capacity; }CharList; typedef int boolean;//定義一個(gè)布爾類型 #define TRUE 1 #define FALSE 0
//創(chuàng)建一個(gè)空節(jié)點(diǎn), 可以指定容量默認(rèn)為10 CharList *createCharList(int size) { if (size < 10) { size = 10; } //初始化結(jié)構(gòu)體和一個(gè)2級(jí)指針 CharList *charList = (CharList *) calloc(1, sizeof(CharList)); charList->str= (char **) calloc(size, sizeof(char *)); charList->len = 0; charList->capacity = size; return charList; }
//擴(kuò)容 static void dilatation(CharList **pCharList) { CharList *charList = *pCharList; int capacity1 =charList->capacity;//獲取當(dāng)前節(jié)點(diǎn)的容積 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){ //插入數(shù)據(jù) char *pData = (char *) calloc(strlen(data) + 1,sizeof(char) ); //為啥要+1因?yàn)樽址Y(jié)尾需要有一個(gè)空字符 strcpy(pData,data); return pData; }
//添加一個(gè)值 ,容量不夠會(huì)自動(dòng)在原有基礎(chǔ)上進(jìn)行擴(kuò)容*0.75 void addCharList(CharList **pCharList, char *value) { CharList *charList = *pCharList; int len1 = charList->len;//獲取當(dāng)前節(jié)點(diǎn)的長(zhǎng)度 int capacity1 =charList->capacity;//獲取數(shù)組的容量 if (len1 == capacity1) { dilatation(pCharList);//擴(kuò)容 } charList->str[len1] = createData(value);//插入數(shù)據(jù) charList->len++; }
void deleteCharList(CharList **pCharList, char *value) { CharList *charList = *pCharList; int len1 = charList->len;//獲取當(dāng)前節(jié)點(diǎn)的長(zhǎng)度 for (int i = 0; i < len1; ++i) { if (strcmp(charList->str[i],value)==0) {//找到了 free(charList->str[i]);//釋放內(nèi)存 for (int j = i; j < len1 - 1; ++j) {//后面的節(jié)點(diǎn)向前移動(dòng) charList->str[j] = charList->str[j + 1]; } charList->len--; break; } } }
//刪除集合內(nèi)指定下標(biāo)的值 void deleteCharListByIndex(CharList **pCharList, int index) { CharList *charList = *pCharList; int len1 = charList->len;//獲取當(dāng)前節(jié)點(diǎn)的長(zhǎng)度 if (index < 0 || index >= len1) { return; } free(charList->str[index]);//釋放內(nèi)存 for (int j = index; j < len1 - 1; ++j) {//后面的節(jié)點(diǎn)向前移動(dòng) charList->str[j] = charList->str[j + 1]; } charList->len--; }
//打印所有節(jié)點(diǎn) void printCharList(CharList *pCharList) { int len1 = pCharList->len; for (int i = 0; i < len1; i++) { printf("%s\n", pCharList->str[i]); } }
先這樣簡(jiǎn)單的使用,如果有需要可以自己定義一套迭代機(jī)制
void charListIterator(CharList *pCharList,void (*func)(char *)) { int len1 = pCharList->len; for (int i = 0; i < len1; i++) { func(pCharList->str[i]); } }
//查詢指定元素的下標(biāo) ,沒有找到返回-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; }
/** * 判斷數(shù)組是否有序 * @param pCharList * @param type TRUE: 按照ASCII碼排序 FALSE: 安裝字符長(zhǎng)度排序 * @return */ boolean charListIsSorted(CharList *pCharList,boolean type) { int len1 = pCharList->len; boolean result; //返回結(jié)果 if(type){//按照ASCII碼排序方式進(jìn)行判斷 //從小到大 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 找到返回下標(biāo),沒有找到返回-1 */ int charListBinarySearch(CharList *pCharList, char *value) { if(!charListIsSorted(pCharList,TRUE)){ //判斷是否是排序的數(shù)組,如果不是那么我們給排序 //二分查詢需要是有序的數(shù)組,所以需要先排序 以ASCII碼進(jìn)行排序 charListSort(pCharList,1); } int len1 = pCharList->len; int low = 0; int high = len1 - 1; while (low <= high) { int mid = (low + high) / 2;//中間下標(biāo) 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); }
//快速排序 (根據(jù)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); } //快速排序(根據(jù)長(zhǎng)度排序,從小到大) 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); } /** * 根據(jù)ASCII碼排序,從小到大,或者根據(jù)長(zhǎng)度排序,從小到大 * @param pCharList * @param type TRUE就是ASCII碼排序, FALSE就是根據(jù)長(zhǎng)度排序 */ 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]);//釋放內(nèi)存 for (int k = j; k < len1 - 1; ++k) {//將后面的內(nèi)容向前移動(dòng) pCharList->str[k] = pCharList->str[k + 1]; } //去除結(jié)尾的元素 pCharList->str[len1 - 1]=NULL; len1--; pCharList->len--;//長(zhǎng)度減1 j--;//重新比較 } } } }
//集合復(fù)制,返回新集合 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是兩個(gè)集合 ,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]);//釋放內(nèi)存 for (int j = index; j < len1 - 1; ++j) {//將后面的內(nèi)容向前移動(dòng) pNewCharList->str[j] = pNewCharList->str[j + 1]; } //去除結(jié)尾的元素 pNewCharList->str[len1 - 1]=NULL; len1--; pNewCharList->len--;//長(zhǎng)度減1 i--;//重新比較 } } return pNewCharList; }
對(duì)于兩個(gè)給定集合A、B, 如果A集合中不存在B集合元素,那么B集合就是A集合的補(bǔ)集,當(dāng)然反過來也可以說A集合是B集合的補(bǔ)集
//集合補(bǔ)集,返回新集合 CharList *charListComplement(CharList *pCharList1, CharList *pCharList2) { CharList *pCharlist1 = charListDifference(pCharList1, pCharList2); CharList *pCharlist2 = charListDifference(pCharList2, pCharList1); CharList *pCharlist = charListMerge(pCharlist1, pCharlist2); return pCharlist; }
對(duì)于兩個(gè)給定集合A、B,由兩個(gè)集合所有元素構(gòu)成的集合,叫做A和B的并集。(需要去重只保留一個(gè))
//集合并集,返回新集合 CharList *charListUnion(CharList *pCharList1, CharList *pCharList2) { CharList *pCharlist1 = charListDifference(pCharList1, pCharList2); CharList *pCharlist2 = charListMerge(pCharlist1, pCharList2); return pCharlist2; }
對(duì)于兩個(gè)給定集合A、B,屬于A又屬于B的所有元素構(gòu)成的集合,叫做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; }
// 釋放內(nèi)存 void charListClean(CharList *pCharList) { //清理數(shù)組內(nèi)元素 for (int i = 0; i < pCharList->len; ++i) { free(pCharList->str[i]); } //清除數(shù)組 free(pCharList); }
讀到這里,這篇“怎么用C語言手寫集合List”文章已經(jīng)介紹完畢,想要掌握這篇文章的知識(shí)點(diǎn)還需要大家自己動(dòng)手實(shí)踐使用過才能領(lǐng)會(huì),如果想了解更多相關(guān)內(nèi)容的文章,歡迎關(guān)注億速云行業(yè)資訊頻道。
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。