黑马程序员技术交流社区

标题: 怎么实现可变数组 [打印本页]

作者: 于振发 时间: 2013-9-28 17:44
标题: 怎么实现可变数组
不太清楚可变数组的实现,请结合代码讲解,各位谢谢啦

作者: Jam-l 时间: 2013-9-28 18:02
数组一旦创建是不可改变的，集合就是可变的

作者: 罗凯健 时间: 2013-9-28 18:51
集合中实现可变长度的原理是，新增一个长度为（忘记了）的数组，数组满了之后，新建一个比这个长度还长的数组（具体多长看不同子类对象），然后把原数组的东西复制进去。你可以参照这个方法来建立自己的可变数组啊。当然直接用集合就更爽了

作者: Jam-l 时间: 2013-9-28 19:37
本帖最后由 Jam-l 于 2013-9-28 19:40 编辑

集合可变长度的原理：

集合中的空白空间
拥有给定数量对象的各种集合的开销并不是内存开销的全部。前文的示例中的度量假设集合已经得到了准确的大小调整。然而，对于大多数集合来说，这种假设都是不成立的。大多数集合在创建时都指定给定的初始容量，数据将置入集合之中。这也就是说，集合拥有的容量往往大于集合中存储的数据容量，这造成了额外的开销。

考虑一个 StringBuffer 的示例。其默认容量是 16 个字符条目，大小为 72 字节。初始情况下，72 个字节中未存储任何数据。如果您在字符数组中存储了一些字符，例如 "MY STRING" ，那么也就是在 16 个字符的数组中存储了 9 个字符。图 1 展示了 32 位 Java 运行时中的一个包含 "MY STRING" 的 StringBuffer 的内存使用和布局：

图 1. 32 位 Java 运行时中的一个包含 "MY STRING" 的 StringBuffer 的内存使用

如图 1 所示，数组中有 7 个可用的字符条目未被使用，但占用了内存，在本例中，这造成了 112 字节的额外开销。对于这个集合，您在 16 的容量中存储了 9 个条目，因而填充率为 0.56。集合的填充率越低，因多余容量而造成的开销就越高。
集合的扩展和重新调整在集合达到容量限制时，如果出现了在集合中存储额外条目的请求，那么会重新调整集合，并扩展它以容纳新条目。这将增加容量，但往往会降低填充比，造成更高的内存开销。
各集合所用的扩展算法各有不同，但一种通用的做法就是将集合的容量加倍。这也是 StringBuffer 采用的方法。对于前文示例中的 StringBuffer，如果您希望将 " OF TEXT" 添加到缓冲区中，生成 "MY STRING OF TEXT"，则需要扩展集合，因为新的字符集合拥有 17 个条目，当前容量 16 无法满足其要求。图 2 展示了所得到的内存使用：

图 2. 32 位 Java 运行时中的一个包含 "MY STRING OF TEXT" 的 StringBuffer 的内存使用

现在，如图 2 所示，您得到了一个 32 个条目的字符数组，但仅仅使用了 17 个条目，填充率为 0.53。填充率并未显著下滑，但您现在需要为多余的容量付出 240 字节的开销。
对于小字符串和集合，低填充率和多余容量的开销可能并不会被视为严重问题，而在大小增加时，这样的问题就会愈加明显，代价也就愈加高昂。例如，如果您创建了一个 StringBuffer，其中仅包含 16MB 的数据，那么（在默认情况下）它将使用大小设置为可容纳 32MB 数据的字符数组，这造成了以多余容量形式存在的 16MB 的额外开销。

作者: HM代景康 时间: 2013-9-28 20:30
1.变长一维数组

  这里说的变长数组是指在编译时不能确定数组长度，程序在运行时需要动态分配内存空间的数组。实现变长数组最简单的是变长一维数组，你可以这样做：

  //文件名: array01.cpp
  #include<iostream>
  using namespace std;

  int main()
  {
int len;
cin>>len;
//用指针p指向new动态分配的长度为len*sizeof(int)的内存空间
int *p=new int[len];
...........
delete[] p;
return 0;
  }

2.变长n维数组
  变长的n维数组实现起来有些麻烦，但是在工程与软件设计应用中常使用的是二维数组，所以在这里着重介绍变长的二维数组，变长的n维数组可以按照类似的方法实现。首先看一个经典的用C实现变长二维数组的例子：

  //文件名: array03.c
  #include    <stdio.h>
  #include    <malloc.h>

  void    main()

  {
                     int    x,y,i,j;
                     float    **a,*b;
                                             printf("请输入你所求解的线性方程组的行数x：x=");
                     scanf("%d",&x);
                                             printf("请输入你所求解的线性方程组的列数y：y=");
                     scanf("%d",&y);

            a=(float    **)malloc(sizeof(float    *)    *x);
            b=(float    *)malloc(sizeof(float)    *x);
                     for(i=0;i<x;i++)
                     {
                                             *(a+i)=(float    *)malloc(sizeof(float)    *y);
                     }



                     printf("请按行的顺序依次输入系数的值(共%d项)：",x*y);
                     for(i=0;i<=x-1;i++)
                                             for(j=0;j<=y-1;j++)
                                                                     scanf("%f",&a[i][j]);
                     printf("请按列的顺序依次输入常数的值(共%d项)：",x);
                     for(j=0;j<=x-1;j++)
                                                                     scanf("%f",&b[j]);

                     printf("您输入方程组的增广矩阵为：\n");
                     for(i=0;i<=x-1;i++)
                     {
                                             for(j=0;j<=y-1;j++)
                                                                     printf("%.5f       ",a[i][j]);
                                             printf("%.5f       ",b[i]);
                                             printf("\n");
                     }
                     free(b);
                     for(i=0;i<x;i++)
                                             free    (*(a+i));

  }

  那么用C++怎样实现呢？在C++中可以通过new和delete运算符动态开辟和释放空间，其中new与C中malloc函数的功能相似，delete与C中free函数的功能相似。用C++实现变长二维数组时可以采用两种方法：双指针方法和使用STL中vector（向量）的方法。

作者: HM代景康 时间: 2013-9-28 20:31
首先介绍一下双指针方法，在这里双指针就是指像指针的指针，比如你可以这样声明一个数组：
  int **p = new int*[num1];
  而对每一个*p（一共num1个*p）申请一组内存空间：
  for(int i=0; i<num1; ++i)
p[i] = new int[num2];
  其中，num1是行数，num2是数组的列数。测试的源程序如下：

  //文件名: array04.cpp
  #include <iostream>
  #include <iomanip>
  using namespace std;

  int main()
  {
int num1,//行数
         num2;//列数

cout<<"Please enter the number for row and column: "<<endl;
cin >> num1 >> num2;

//为二维数组开辟空间
int **p = new int*[num1];
for(int i=0; i<num1; ++i)
   p[i] = new int[num2];

for(int j=0;j<num1;j++)
{
   for(int k=0;k<num2;k++)
   {
      p[j][k]=(j+1)*(k+1);
      cout<<setw(6)<<p[j][k]<<':'<<setw(8)<<&p[j][k];
   }
   cout<<endl;
}

//释放二维数组占用的空间
for(int m=0;m<num1;m++)
   delete[] p[m];
delete[] p;

return 0;
  }

  以下是运行结果：

  Please enter the number for row and column:
  4 5
         1:004915F0          2:004915F4          3:004915F8          4:004915FC          5:00491600
         2:00491180          4:00491184          6:00491188          8:0049118C       10:00491190
         3:00491140          6:00491144          9:00491148       12:0049114C       15:00491150
         4:00491100          8:00491104       12:00491108       16:0049110C       20:00491110
  Press any key to continue

  程序清单array04.cpp可以显示分配的内存空间单元的地址，大家可以看到，由于数组空间是动态分配的，数组行之间的地址空间是不连续的，因为不同行的数组元素的地址空间是用不同的new来分配的。而每一行之中列之间的地址空间是连续的。

  那么用vector（向量）怎样实现二维数组呢？以下给出源程序：

  //文件名: array05.cpp
  #include <iostream>
  #include <vector>
  #include <iomanip>
  using namespace std;
  int main()
  {
int i,
         j,
         m, //行数
         n; //列数

cout << "input value for m,n:";
cin>>m>>n;

//注意下面这一行：vector<int后两个">"之间要有空格！否则会被认为是重载">>"。
vector<vector<int> > vecInt(m, vector<int>(n));
for (i = 0; i < m; i++)
   for (j = 0; j < n; j++)
      vecInt[i][j] = i*j;

for (i = 0; i < m; i++)
{
   for (j = 0; j < n; j++)
      cout<<setw(5)<<vecInt[i][j]<<":"<<setw(9)<<&vecInt[i][j];
   cout<<endl;
}

return 0;
  }

  以下是运行结果：

  input value for m,n:3 4
      0: 00491180       0: 00491184       0: 00491188       0: 0049118C
      0: 00491140       1: 00491144       2: 00491148       3: 0049114C
      0: 00491100       2: 00491104       4: 00491108       6: 0049110C
  Press any key to continue

  大家可以看到，这里vector中元素的内存的地址分配也有同双指针实现的二维数组有同样的特点。不过用vector的方法比使用双指针简单地多，分配内存空间时会更安全，数组初始化代码也更简单，所以本人建议使用STL中的vector来实现变长多维数组。以下是一个变长三维数组：）

  //文件名: array06.cpp
  #include <iostream>
  #include <vector>
  #include <iomanip>
  using namespace std;
  int main()
  {
int i,
   j,
   k,
   m, //一维坐标
   n, //二维坐标
   l; //三维坐标


cout << "input value for m,n,l:";
cin>>m>>n>>l;
vector<vector<vector<int> > > vecInt(m, vector<vector<int> >(n, vector<int>(l)));
for (i = 0; i < m; i++)
   for (j = 0; j < n; j++)
      for(k = 0; k < l; k++)
      vecInt[i][j][k] = i+j+k;

for (i = 0; i < m; i++)
{
   for (j = 0; j < n; j++)
   {
      for(k = 0; k<l; k++)
      cout<<setw(5)<<vecInt[i][j][k]<<":"<<setw(9)<<&vecInt[i][j][k];
      cout<<endl;
   }
   cout<<endl;
}

return 0;
  }

  运行结果：
  input value for m,n,l:2 3 4
      0: 00492FE0       1: 00492FE4       2: 00492FE8       3: 00492FEC
      1: 00492FA0       2: 00492FA4       3: 00492FA8       4: 00492FAC
      2: 00492F60       3: 00492F64       4: 00492F68       5: 00492F6C

      1: 00492EC0       2: 00492EC4       3: 00492EC8       4: 00492ECC
      2: 00492E80       3: 00492E84       4: 00492E88       5: 00492E8C
      3: 00492E40       4: 00492E44       5: 00492E48       6: 00492E4C

欢迎光临黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2