C语言动态数组实现记录

C语言动态数组实现记录目录C语言动态数组实现记录前言一、结构体二、初始化三、扩容四、释放~~free只能释放我们mallco手动分给他的内存~~五、添加元素六、删除元素七、修改元素八、获取元素这里有 Bug九、查找十、main 函数十一、改进点汇总十二、几点体会1. size 和 cap 容易混2. 下标越界是常犯的错3. free 要分清楚4. 扩容按倍数来5. 函数名和参数名要清楚十三、完整代码十四、总结前言上周写了个动态数组当时觉得没什么问题能跑就行。这周回头看了一遍发现不少地方可以改进。把代码贴出来加上现在的注释做个记录。一、结构体typedefstruct{int*data;intsize;intcap;}arr;data存放数据的连续内存size当前元素个数cap当前容量上限点评结构体叫arr变量又叫a读代码时容易混我当时是纯懒如果是自己动手练习建议改成DynamicArray。另外size和cap要分清遍历用size判断满不满用cap。二、初始化voidcreatearr(arr*a){a-data(int*)malloc(sizeof(int)*2);if(a-dataNULL)exit(1);a-size0;a-cap2;}点评没检查a是否为 NULL。如果调用者传空指针a-data会直接崩。建议开头加if(aNULL)return;exit(1)太强硬一失败程序就退出。初学可以这样但返回错误码更灵活。三、扩容voidexpend(arr*a){intnewcap(a-cap)*2;int*newdata(int*)malloc(sizeof(int)*newcap);if(newdataNULL)exit(1);for(intx0;xa-size;x){newdata[x]a-data[x];}free(a-data);a-capnewcap;a-datanewdata;}点评这里我的函数名拼错了expend应该是expand。草这个当时怎么没发现逻辑没问题翻倍 → 分配 → 拷贝 → 释放旧的 → 更新。为什么是乘 2 而不是加 1每次加 1 的话就要反复运行好多次这段代码我的建议是在空间和时间之间找个平衡。反正要么费空间省时间要么费时间省空间四、释放voidarrfree(arr*a){free(a-data);free(a);}点评这个函数把结构体本身也 free 了。如果arr是栈上的arr a;free(a)就错了栈上的内存不能 free。不过我这里这样写其实没问题啦因为我前面的arr就是堆里的free只能释放我们mallco手动分给他的内存更通用的写法是只释放内部datavoiddestroyArr(arr*a){if(aNULL)return;free(a-data);a-dataNULL;a-size0;a-cap0;}如果结构体本身也是动态分配的再单独写一个释放函数。五、添加元素voidadd(arr*a,intvalue){if(a-sizea-cap){expend(a);}a-data[a-size]value;a-size;}点评逻辑正确。开头建议加if (a NULL) return;。六、删除元素voiddelete(arr*a,intsize){if(size0||sizea-size){printf(下标越界删除失败);exit(1);}for(intisize;ia-size-1;i){a-data[i]a-data[i1];}a-size--;}点评越界判断是对的size a-size没问题。函数名delete和 C 关键字撞名建议改成deleteAt。参数名size和结构体成员重名容易混改成index。exit(1)同样建议改成返回错误码。改进intdeleteAt(arr*a,intindex){if(aNULL)return0;if(index0||indexa-size){printf(下标越界删除失败\n);return0;}for(intiindex;ia-size-1;i){a-data[i]a-data[i1];}a-size--;return1;}七、修改元素voidset(arr*a,intindex,intvalue){if(index0||indexa-size){printf(下标越界修改失败);exit(1);}a-data[index]value;}点评逻辑和边界判断都对。exit(1)可以换成返回错误码。八、获取元素这里有 Bugintget(arr*a,intindex){if(index0||indexa-size){printf(下标越界获取失败);return-1;}returna-data[index];}点评判断条件写成了index a-size应该是index a-size。合法下标是 0 到size - 1。如果index size访问的是a-data[size]这块内存没有有效数据读出来是垃圾值。正确写法if(index0||indexa-size)//这个||用来判断两边是不是都为假只要有一方为真就会运行反之则跳过。{printf(下标越界获取失败\n);return-1;}这种 off-by-one 的错误编译不会报错测试时也未必碰到只有边界情况才暴露。所以这种事情得多写多问多发现有经验之后自然会规避的九、查找intfind(arr*a,intdata){for(inti0;ia-size;i){if(a-data[i]data){printf(找到了在第%d位\n,i);returni;}}printf(没有这个数\n);return-1;}点评功能没问题但在函数里直接打印不太合适。有时候调用find只是想拿下标不想让它自己打印。建议只返回下标intfind(arr*a,intvalue){if(aNULL)return-1;for(inti0;ia-size;i){if(a-data[i]value)returni;}return-1;}调用者自己决定要不要打印。十、main 函数intmain(){arr*a(arr*)malloc(sizeof(arr));createarr(a);点评没检查malloc是否成功。加一句if(aNULL){printf(分配失败\n);return1;}intb;printf(请输入文本\n);scanf(%d,b);staticinti1;点评static int i里的static多余改成int i 1;就行。scanf没检查返回值输入字母会失败。建议if(scanf(%d,b)!1)break;printf(请输入文本\n)说的其实是数字但是当时我瞎打的改成请输入数字更准确。into0;ofind(a,b);printf(在第%d位数组首次出现\n是否需要删除输入1或者0\n,o);点评如果没找到返回 -1这里会打印在第 -1 位出现。最好先判断if(o!-1){printf(在第 %d 位出现\n,o);}else{printf(没找到\n);}arrfree(a);点评这里a是malloc来的arrfree里free(a)没问题。但如果以后改成栈上的arr a;就会出错。统一改成只释放data更保险。十一、改进点汇总位置问题建议createarr没检查a加if (a NULL) return;expend拼写错误改成expanddelete撞 C 关键字改成deleteAtdelete参数名和成员重名改成indexgetindex size应为改成find在函数内打印只返回下标arrfree会 free 栈上的结构体只 freedatamainstatic int i多余去掉static多处exit(1)太强硬改成返回错误码十二、几点体会1. size 和 cap 容易混对于新手来说要记住遍历时用size判断容量是否已满则用cap写循环时很容易顺手写错。2. 下标越界是常犯的错合法下标是0到size - 1判断条件一律是index 0 || index size。get那个 bug 就是在这里翻的车。3. free 要分清楚free只能释放malloc出来的内存栈上的变量不能 free。写destroy的时候要分清是只释放内部数据还是连结构体一起释放。4. 扩容按倍数来按倍数扩容比每次加 1 效率高。乘 2 会浪费一些内存但均摊时间代价是常数级。5. 函数名和参数名要清楚delete、expend、size这些名字自己看还行别人看容易误会。改完之后代码清爽很多。十三、完整代码#includestdio.h#includestdlib.htypedefstruct{int*data;intsize;intcap;}DynamicArray;intinitArray(DynamicArray*a){if(aNULL)return0;a-data(int*)malloc(sizeof(int)*2);if(a-dataNULL)return0;a-size0;a-cap2;return1;}intexpandArray(DynamicArray*a){if(aNULL)return0;intnewcapa-cap*2;int*newdata(int*)malloc(sizeof(int)*newcap);if(newdataNULL)return0;for(inti0;ia-size;i){newdata[i]a-data[i];}free(a-data);a-datanewdata;a-capnewcap;return1;}intaddElement(DynamicArray*a,intvalue){if(aNULL)return0;if(a-sizea-cap){if(!expandArray(a))return0;}a-data[a-size]value;a-size;return1;}intdeleteAt(DynamicArray*a,intindex){if(aNULL)return0;if(index0||indexa-size){printf(下标越界删除失败\n);return0;}for(intiindex;ia-size-1;i){a-data[i]a-data[i1];}a-size--;return1;}intsetElement(DynamicArray*a,intindex,intvalue){if(aNULL)return0;if(index0||indexa-size){printf(下标越界修改失败\n);return0;}a-data[index]value;return1;}intgetElement(DynamicArray*a,intindex,int*out){if(aNULL||outNULL)return0;if(index0||indexa-size){printf(下标越界获取失败\n);return0;}*outa-data[index];return1;}intfindElement(DynamicArray*a,intvalue){if(aNULL)return-1;for(inti0;ia-size;i){if(a-data[i]value){returni;}}return-1;}voidprintArray(DynamicArray*a){if(aNULL||a-size0){printf(数组为空\n);return;}for(inti0;ia-size;i){printf(%d ,a-data[i]);}printf(\n);}voiddestroyArray(DynamicArray*a){if(aNULL)return;free(a-data);a-dataNULL;a-size0;a-cap0;}intmain(){DynamicArray a;if(!initArray(a)){printf(初始化失败\n);return1;}intb;printf(请输入数字输入 -1 结束\n);while(scanf(%d,b)1b!-1){addElement(a,b);}printf(当前数组\n);printArray(a);printf(请输入要查找的数字\n);scanf(%d,b);intindexfindElement(a,b);if(index!-1){printf(找到了在下标 %d 处\n,index);printf(是否删除输入 1 删除0 取消\n);intchoice;scanf(%d,choice);if(choice1){deleteAt(a,index);printf(删除后数组\n);printArray(a);}}else{printf(没有找到 %d\n,b);}destroyArray(a);return0;}十四、总结写完一周后再看问题主要集中在几类空指针没检查、size和cap混用、和写错、free用得不清楚。这些问题不算难但第一次写的时候确实想不到。多写几遍、多看几遍自己的代码慢慢就有感觉了。代码有写得不对的地方欢迎评论区指出。