time 
设为首页】【收藏本站
当前位置: 主页 > 程序设计 > C\C++\VC > C语言 > C语言实现动态数组对象

C语言实现动态数组对象

时间:2015-03-04 10:31 点击:2697次 字体:[ ]




对于习惯使用高级语言编程的人来说,使用 C 语言编程最头痛的问题之一就是在使用数组需要事先确定数组长度。

  C 语言本身不提供动态数组这种数据结构,本文将演示如何在 C 语言编程中实现一种对象来作为动态数组。

 

 基本的 C 数组

  

  C 语言编程中声明一个基本数组如下:

int main() {
    // 声明一个容纳 3000 个整数的数组
    int my_array[3000];
}

   

  以上代码做了两件事:

  ● 在栈区开辟内存空间。准确说来是在函数 main 的栈区空间开辟一个 3000 * sizeof(int) 个字节的内存空间。通过这种方式开辟的内存空间会在程序运行到当前区块终点时(对本例而言就是 main 函数的底部)被自动释放掉。

  ● 创建一个指针指向新开辟的内存区域,并将该指针赋给变量 my_array 保存。我们可以通过下标的方式来访问数组里的成员,例如 my_array[271] 可以访问到第 272 个成员。你也可以通过另一种方式来访问数组里的成员,即 *(my_array + 271)。

 

  由此可以看出,C 语言的数组实质就是内存管理操作,下标索引只是一种语法糖。

      C 语言的数组有两个雾区:

  ● 很难随着数据的增加自动扩大数组。事实是你可以使用 realloc 函数扩大开辟在堆区的数组大小,当然我们想要的是能自动调整大小的数组对象。

  ● 你可以索引到数组边界以外的区域。由于在 C 语言并不检查数组的边界,也就是说你的确可以访问数组边界以外区域的内存地址,例如 my_array[5000] 语法上是可行的。因为下标索引只是一种语法糖,它实际上所做的是从指针 my_array 开始向后移动 5000 次并读取它停在的那个内存地址所保存的数据。当你索引数据边界以外区域时相当于读取尚未分配的内存上的内容,但这不是你真的想要的,并且可能带来潜在的严重后果。

 

  如果我们可以忍受一些速度和内存空间上的牺牲,那么我们可以通过实现某种数据结构作为所谓的 “动态数组”。本文我们将这种数据结构称为 Vector,但这种数据结构不能解决我们在操作数集时遇到的所有问题,它适合于向其中追加成员,但不适合做插入和删除操作,如果你需要大量的插入和删除操作,链表这种数据结构更能符合你的需求,但链表也有它的问题,我们就不在这里做过多讨论。

 

 

 定义 Vector 对象

  

  本文我们将创建一个容纳整数的 “动态数组”,让我们将这种数据结构命名为 Vector。首先我们使用一个头文件 vector.h 来定义数据结构 Vector

  1. // 首先定义一个常量,该常量表示 Vector 内部一个数组对象的初始大小。  
  2. #define VECTOR_INITIAL_CAPACITY 100  
  3.  
  4.  
  5. // 定义数据结构 Vector  
  6. typedef struct {  
  7.     int size;               // 数组在用长度  
  8.     int capacity;           // 数组最大可用长度  
  9.     int *data;              // 用来保存整数对象的数组对象  
  10. } Vector;  
  11.  
  12. // 该函数负责初始化一个 Vector 对象,初始数组在用长度为 0,最大长度为 VECTOR_INITIAL_CAPACITY。  
  13. // 开辟适当的内存空间以供底层数组使用,空间大小为 vector->capacity * sizeof(int) 个字节。   
  14. void vector_init(Vector *vector);  
  15.  
  16. // 该函数负责追加整数型的成员到 vector 对象。如果底层的数组已满,则扩大底层数组容积来保存新成员。  
  17. void vector_append(Vector *vector, int value);  
  18.  
  19. // 返回 vector 指定位置所保存的值。如果指定位置小于 0 或者大于 vector->size - 1,则返回异常。  
  20. int vector_get(Vector *vector, int index);  
  21.  
  22. // 将指定值保存到指定位置,如果指定位置大于 vector->size,则自动翻倍 vector 内部的数组容积直到可以容纳指定多的位置。  
  23. // 扩大的数组中间使用 0 填满那些空位置。  
  24. void vector_set(Vector *vector, int index, int value);  
  25.  
  26. // 将 vector 内部数组容积翻倍。  
  27. // 因为更改数组体积的开销是十分大的,采用翻倍的策略以免频繁更改数组体积。  
  28. void vector_double_capacity_if_full(Vector *vector);  
  29.  
  30. // 释放 vector 内部数组所使用的内存空间。  
  31. void vector_free(Vector *vector); 

 



本文地址 : http://www.fengfly.com/plus/view-215782-1.html
标签: 对象 动态数组 C语言
------分隔线----------------------------
最新评论 查看所有评论
发表评论 查看所有评论
请自觉遵守互联网相关的政策法规,严禁发布色情、暴力、反动的言论。
评价:
表情:
验证码:
本栏分类