C語言手寫集合List的示例代碼

Posted on by

前沿

數組長度是固定的,那麼在很多時候我們並不知道到底有多少數據需要存儲,這時候我麼就需要一個可變長度的數組來進行存儲,在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);
}

到此這篇關於C語言手寫集合List的示例代碼的文章就介紹到這瞭,更多相關C語言集合內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！

推薦閱讀：