C語言手寫集合List的示例代碼
更新時間：2022年08月24日 14:43:33 作者：胡安民
數(shù)組長度是固定的,那么在很多時候我們并不知道到底有多少數(shù)據(jù)需要存儲,這時候我么就需要一個可變長度的數(shù)組來進行存儲,在C語言中需要我們自己進行定義,我們稱為集合。本文將用C語言實現(xiàn)手寫集合，需要的可以參考一下
前沿
數(shù)組長度是固定的,那么在很多時候我們并不知道到底有多少數(shù)據(jù)需要存儲,這時候我么就需要一個可變長度的數(shù)組來進行存儲,在C語言中需要我們自己進行定義,我們稱為集合
定義結構
typedef struct charlist {
char **str;
int len;
int capacity;
}CharList;
typedef int boolean;//定義一個布爾類型
#define TRUE 1
#define FALSE 0
創(chuàng)建List
//創(chuàng)建一個空節(jié)點, 可以指定容量默認為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;//獲取當前節(jié)點的容積
int size = capacity1 + (capacity1 * 0.75);//容積增加
charList->capacity= size;//更新容積
char **p1 = (char **) realloc(charList->str,size*sizeof(char *));
charList->str=p1;
}創(chuàng)建數(shù)據(jù)節(jié)點
static char *createData(char *data){
//插入數(shù)據(jù)
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;//獲取當前節(jié)點的長度
int capacity1 =charList->capacity;//獲取數(shù)組的容量
if (len1 == capacity1) {
dilatation(pCharList);//擴容
}
charList->str[len1] = createData(value);//插入數(shù)據(jù)
charList->len++;
}
刪除集合內(nèi)指定的值
void deleteCharList(CharList **pCharList, char *value) {
CharList *charList = *pCharList;
int len1 = charList->len;//獲取當前節(jié)點的長度
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é)點向前移動
charList->str[j] = charList->str[j + 1];
}
charList->len--;
break;
}
}
}
刪除集合內(nèi)指定下標的值
//刪除集合內(nèi)指定下標的值
void deleteCharListByIndex(CharList **pCharList, int index) {
CharList *charList = *pCharList;
int len1 = charList->len;//獲取當前節(jié)點的長度
if (index < 0 || index >= len1) {
return;
}
free(charList->str[index]);//釋放內(nèi)存
for (int j = index; j < len1 - 1; ++j) {//后面的節(jié)點向前移動
charList->str[j] = charList->str[j + 1];
}
charList->len--;
}
打印集合
//打印所有節(jié)點
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;
}
判斷數(shù)組是否有序
/**
* 判斷數(shù)組是否有序
* @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)){ //判斷是否是排序的數(shù)組,如果不是那么我們給排序
//二分查詢需要是有序的數(shù)組,所以需要先排序 以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);
}
快速排序
//快速排序 (根據(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ù)長度排序,從小到大)
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ù)長度排序,從小到大
* @param pCharList
* @param type TRUE就是ASCII碼排序, FALSE就是根據(jù)長度排序
*/
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)容向前移動
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]);//釋放內(nèi)存
for (int j = index; j < len1 - 1; ++j) {//將后面的內(nèi)容向前移動
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;
}
銷毀集合
// 釋放內(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的示例代碼的文章就介紹到這了,更多相關C語言集合內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
這篇文章主要介紹了C++關鍵字之likely和unlikely,C++20之前的，likely和unlikely只不過是一對自定義的宏，而C++20中正式將likely和unlikely確定為屬性關鍵字，本文給大家詳細講解，需要的朋友可以參考下2022-10-10
C語言數(shù)據(jù)結構順序表中的增刪改(頭插頭刪)教程示例詳解
這篇文章主要為大家介紹了C語言數(shù)據(jù)結構順序表中增刪改關于頭插頭刪的教程示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步2022-02-02
C++命名空間?缺省參數(shù)?const總結?引用總結?內(nèi)聯(lián)函數(shù)?auto關鍵字詳解
這篇文章主要介紹了C++命名空間?缺省參數(shù)?const總結?引用總結?內(nèi)聯(lián)函數(shù)?auto關鍵字詳解的相關資料,需要的朋友可以參考下2023-01-01
這篇文章主要為大家詳細介紹了C語言函數(shù)的可重入性，文中介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-08-08
這篇文章主要為大家介紹了C語言Tinyhttpd服務器源碼剖析,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進步,早日升職加薪2023-09-09
引用是C++一個很重要的特性,顧名思義是某一個變量或對象的別名，對引用的操作與對其所綁定的變量或對象的操作完全等價,這篇文章主要給大家總結介紹了C++中引用的相關知識點,需要的朋友可以參考下2022-05-05
這篇文章主要介紹了MFC設置對話框焦點的方法簡述,主要講述了兩種實現(xiàn)方法,需要的朋友可以參考下2014-10-10
這篇文章主要介紹了C++ 如何實現(xiàn)順序棧(使用模板類)，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2022-07-07
本文簡單的介紹一下C++語言中如何識別圖片文件的類型，以及各圖片類型之間的轉換方法，并提供相關的源碼供大家參考，感興趣的朋友快來看看吧2021-11-11
參數(shù)傳遞有傳值、傳址和傳引用這三種,本文主要介紹了C++傳值、傳址、傳引用的區(qū)別和選擇小結,具有一定的參考價值,感興趣的可以了解一下2024-07-07