守望者--AIR技术交流

 找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

搜索
热搜: ANE FlasCC 炼金术
查看: 2684|回复: 0

[C语言] 快速学习C语言四: 造轮子,ArrayList

[复制链接]
  • TA的每日心情
    擦汗
    2018-4-10 15:18
  • 签到天数: 447 天

    [LV.9]以坛为家II

    1742

    主题

    2094

    帖子

    13万

    积分

    超级版主

    Rank: 18Rank: 18Rank: 18Rank: 18Rank: 18

    威望
    562
    贡献
    29
    金币
    52619
    钢镚
    1422

    开源英雄守望者

    发表于 2015-1-3 14:00:51 | 显示全部楼层 |阅读模式
    高级语言里的列表是最常用的数据结构,在C里造个轮子玩玩,C没有泛型,先用int练习。
    Collection的ADT一般有hasnext,next,add, remove操作,List一般还加了removeat, insert等,然后Stack有push和pop,Queue有enqueue和dequeue。列表有种实现, ArrayList和LinkedList,总体来说ArrayList更常用一些,就先用数组实现个列表。
    ArrayList在末尾的添加和删除还是挺快的(O(1)),所以当栈来用挺好,Push和Pop都在末尾。 当队列的话,Enqueue在数组头部放入元素,所有右边的元素都要向右移动(O(N)),比较耗 时,不如LinkedList。另外获取指定索引数据或设置指定索引的数据是O(1)复杂度, 比LinkedList快,如果要想查看是否有指定数据,或删除指定数据,要扫描全表,复杂度 是O(N)。哦,删除指定位置的数据复杂度也是O(N), 因为删除后右边的数据要全部向 左移动。
    可以开始了,首先定义一个结构来保存状态
    1. struct arr_list {
    2.     int * arr;      // 内部数组
    3.     int index;      // 实际数据大小
    4.     int size;       // 预分配空间大小
    5. };
    复制代码
    创建一个array list
    1. struct arr_list* create_arr_list(n) {
    2.     if (n < 1) {
    3.         n = 10;
    4.     }
    5.     struct arr_list *arr = (struct arr_list*)malloc(sizeof(struct arr_list));
    6.     arr->arr = (int*)malloc(sizeof(int) * n);
    7.     arr->size = n;
    8.     arr->index = 0;
    9.     return arr;
    10. }
    复制代码
    空间不足时自动扩容,默认策略是空间不够时申请双倍大小空间, 然后把原有数据拷贝到 新空间,并把原有空间释放掉, 该函数一般是新增元素前调用,所以判断条件是当实际 所用空间已经等于或大于(应该不可能)预分配空间时扩容。
    1. static void expand_space(struct arr_list *arr) {
    2.     int *tmp, i, *p, *q;

    3.     if (arr->index >= arr->size) {
    4.         tmp = (int *)malloc(sizeof(int) * arr->size * 2);
    5.         p = arr->arr;
    6.         q = tmp;
    7.         for (i = 0; i < arr->index; i++) {
    8.             *q++ = *p++;
    9.         }
    10.         free(arr->arr);
    11.         arr->arr = tmp;
    12.         arr->size = arr->size * 2;
    13.     }
    14. }
    复制代码
    在指定位置插入新元素,现有元素向右移,O(N)
    1. int list_insert(struct arr_list *arr, int index, int obj) {
    2.     int i;

    3.     if (index < 0 || index > arr->index) {
    4.         return -1;
    5.     }
    6.     expand_space(arr);

    7.     for (i = arr->index; i > index ; i--) {
    8.         arr->arr[i] = arr->arr[i - 1];
    9.     }
    10.     arr->arr[index] = obj;
    11.     arr->index++;
    12.     return 0;
    13. }
    复制代码
    在array list 末尾插入数据, O(1)
    1. int list_push(struct arr_list *arr, int obj) {
    2.     return list_insert(arr, arr->index, obj);
    3. }
    复制代码
    删除指定位置的数据,O(N), 删除数据后,所有数据向左移动
    1. int list_removeat(struct arr_list *arr, int index) {
    2.     int i;
    3.     if (index < 0 || index >= arr->index) {
    4.         return -1;
    5.     }
    6.     for (i = index; i < arr->index - 1; i++) {
    7.         arr->arr[index] = arr->arr[index + 1];
    8.     }
    9.     arr->index--;
    10.     return 0;
    11. }
    复制代码
    移除并返回末尾的数据, O(1)
    1. int list_pop(struct arr_list *arr) {
    2.     return list_removeat(arr, arr->index - 1);
    3. }
    复制代码
    判断 array list里是否包含某个数据, O(N)
    1. int list_index(const struct arr_list *arr, int obj) {
    2.     int i;
    3.     for (i = 0; i < arr->index; i++) {
    4.         if (arr->arr[i] == obj) {
    5.             return i;
    6.         }
    7.     }
    8.     return -1;
    9. }
    复制代码
    删除某个数据项,O(N), 只删第一次出现的位置, 删除后所有数据向左移动
    1. int list_remove(struct arr_list *arr, int obj) {
    2.     int i, index;
    3.     index = list_index(arr, obj);
    4.     if (index != -1) {
    5.         for (i = index; i < arr->index - 1; i++) {
    6.             arr->arr[i] = arr->arr[i + 1];
    7.         }
    8.         arr->index--;
    9.     }
    10.     return index;
    11. }
    复制代码
    释放一个array list的内存
    1. int free_arr_list(struct arr_list *arr){
    2.     free(arr->arr);
    3.     free(arr);
    4.     return 0;
    5. }
    复制代码
    从头打印一个arr list
    1. void print_arr_list(const struct arr_list *arr) {
    2.     int i, t;
    3.     printf("size=%d,index=%d\n", arr->size, arr->index);
    4.     for (i = 0; i < arr->index; i++) {
    5.         list_get(arr, i, &t);
    6.         printf("list[%d]=%d\n", i, t);
    7.     }
    8. }
    复制代码
    最后整体测试一下
    1. int main(void)
    2. {
    3.     struct arr_list *arr;
    4.     int r;

    5.     arr = create_arr_list(3);
    6.     printf("list push: 5, 6, 7\n");
    7.     list_push(arr, 5);
    8.     list_push(arr, 6);
    9.     list_push(arr, 7);
    10.     print_arr_list(arr);

    11.     printf("list push: 8, will auto expand\n");
    12.     list_push(arr, 8);
    13.     print_arr_list(arr);

    14.     printf("list remove at 2\n");
    15.     list_removeat(arr, 2);
    16.     print_arr_list(arr);

    17.     printf("list pop \n");
    18.     list_pop(arr);
    19.     print_arr_list(arr);

    20.     printf("list insert 0\n");
    21.     list_insert(arr, 0, 3);
    22.     print_arr_list(arr);

    23.     r = list_index(arr, 3);
    24.     printf("list index 3:%d\n", r);
    25.     r = list_index(arr, 7);
    26.     printf("list index 7:%d\n", r);

    27.     printf("list remove 3\n");
    28.     list_remove(arr, 3);
    29.     print_arr_list(arr);

    30.     printf("list set index 0 = 3\n");
    31.     list_set(arr, 0, 3);
    32.     print_arr_list(arr);

    33.     free_arr_list(arr);
    34.     return 0;
    35. }
    复制代码
    小结
    用C实现一下高级语言里常用的数据结构,可以对它们有更深的理解。


    守望者AIR技术交流社区(www.airmyth.com)
    回复

    使用道具 举报

    您需要登录后才可以回帖 登录 | 立即注册

    本版积分规则

    
    关闭

    站长推荐上一条 /4 下一条

    QQ|手机版|Archiver|网站地图|小黑屋|守望者 ( 京ICP备14061876号

    GMT+8, 2024-3-28 23:24 , Processed in 0.071192 second(s), 35 queries .

    守望者AIR

    守望者AIR技术交流社区

    本站成立于 2014年12月31日

    快速回复 返回顶部 返回列表