Chinaunix

标题: 更改数组大小问题？？？ [打印本页]

作者: ccas 时间: 2006-08-19 22:42
标题: 更改数组大小问题？？？
今天有人问了一个关于数组的问题

如果有一个 i 行 j 列的数组，现在要增加它的行数和列数,问要怎么实现

请问这个怎么实现,对数组的类型有区别吗

如果之前分配的数组中已经分配到了数据,要怎样改变大小

作者: 默难 时间: 2006-08-19 22:51
malloc
realloc

作者: mik 时间: 2006-08-19 23:09

原帖由默难于 2006-8-19 22:51 发表
malloc
realloc

对于数组不能用realloc改变大小。数组编译器已经定好了大小

不过，基于另一种思想，可以用 malloc/realloc 分配空间，将多余数据存放这些地方，以达到增大数组的效果，我想:您是指这种方法吧！使数组变小似乎没这个办法吧

作者: 默难 时间: 2006-08-19 23:16

原帖由 mik 于 2006-8-19 23:09 发表

对于数组不能用realloc改变大小。数组编译器已经定好了大小

不过，基于另一种思想，可以用 malloc/realloc 分配空间，将多余数据存放这些地方，以达到增大数组的效果，我想:您是指这种方法吧！使数组变 ...

没错啊，这种动态存储的东西一般都是在堆上做得。
缩小空间用realloc也可以

作者: mik 时间: 2006-08-19 23:17

原帖由默难于 2006-8-19 23:16 发表

没错啊，这种动态存储的东西一般都是在堆上做得。
缩小空间用realloc也可以

LZ 所说的是数组，数组是静态的！

作者: 默难 时间: 2006-08-19 23:19

原帖由 mik 于 2006-8-19 23:17 发表

LZ 所说的是数组，数组是静态的！

……
我之所以回复malloc realloc，就是为了告诉LZ，用动态分配。我这手头有事情做，懒得说那么多话了。难道还要我把堆栈在解释一遍吗？

作者: mik 时间: 2006-08-19 23:24

原帖由默难于 2006-8-19 23:19 发表

……
我之所以回复malloc realloc，就是为了告诉LZ，用动态分配。我这手头有事情做，懒得说那么多话了。难道还要我把堆栈在解释一遍吗？

晕，大概我是误解了你的用意，你也误解了我想表达的意思，是我不对在先

这个堆栈嘛，就不用劳烦你解释了。

作者: 默难 时间: 2006-08-19 23:45

原帖由 mik 于 2006-8-19 23:24 发表

晕，大概我是误解了你的用意，你也误解了我想表达的意思，是我不对在先

这个堆栈嘛，就不用劳烦你解释了。

技术板块，没什么对不对的。

作者: ccas 时间: 2006-08-19 23:47
确实会遇到两种情况，静态分配和动态分配，请问静态分配的数组是不是就没有办法再更改大小了？

那malloc realloc 可以同时更改动态分配数组的行和列值吗，并保留原有的数据

作者: 默难 时间: 2006-08-20 00:00
如果要在栈上申请一个指定大小的空间，可以用alloca
不过这个函数不在标准C函数库里面
如果系统没有实现这个函数，可以利用内嵌的汇编来修改%esp和%eax的值来实现这个函数。不过修改%esp %eax的方法只适用于x86

malloc是用于申请一片连续的内存
所谓行和列……LZ还是再看一遍多维数组方面的内容吧

作者: x2 时间: 2006-08-20 00:01

原帖由 ccas 于 2006-8-19 22:42 发表
今天有人问了一个关于数组的问题

如果有一个 i 行 j 列的数组，现在要增加它的行数和列数,问要怎么实现

请问这个怎么实现,对数组的类型有区别吗

如果之前分配的数组中已经分配到了数据,要怎样改变大小

malloc 或 new 一个一维数组，自己计算行值和列值，将一维数组当二维数组用。

作者: flw 时间: 2006-08-20 00:04
1，数组仅在编译时存在，因此，一旦完成编译，便再也无法改变它的大小了。
2，动态分配的内存空间总是一维的。

作者: mik 时间: 2006-08-20 00:10

原帖由默难于 2006-8-20 00:00 发表
如果要在栈上申请一个指定大小的空间，可以用alloca
不过这个函数不在标准C函数库里面
如果系统没有实现这个函数，可以利用内嵌的汇编来修改%esp和%eax的值来实现这个函数。不过修改%esp %eax的方法只适用于x86 ...

esp 的值是不能随便更改的，会破坏栈结构

作者: 默难 时间: 2006-08-20 00:21

原帖由 mik 于 2006-8-20 00:10 发表

esp 的值是不能随便更改的，会破坏栈结构

……你看一下我前面说的，我的目的是在栈上申请指定数目的空间

作者: mik 时间: 2006-08-20 00:28

原帖由默难于 2006-8-20 00:21 发表

……你看一下我前面说的，我的目的是在栈上申请指定数目的空间

但凡分配空间，当然是有指定数目，难道随机数目的空间吗？

由程序员来改变 esp 值，只会令栈结构维护更难，你要去考虑销栈问题，这样只会徒然增加工作量

作者: 默难 时间: 2006-08-20 00:37

原帖由 mik 于 2006-8-20 00:28 发表

但凡分配空间，当然是有指定数目，难道随机数目的空间吗？

由程序员来改变 esp 值，只会令栈结构维护更难，你要去考虑销栈问题，这样只会徒然增加工作量

-_-||

那你就把你函数库里的alloca函数删除吧，否则太难维护了……

我说是随机数目了吗？我说的是实现一个接口和alloca函数匹配的函数

函数返回之后esp就会返回成调用前的值了……

算了……我懒得解释了，你google一下吧……谁有闲功夫就帮忙解释一下

[ 本帖最后由默难于 2006-8-20 00:38 编辑 ]

作者: flw 时间: 2006-08-20 00:39
这几天对 mik 有了更多的认识。
to mik：
现阶段你应该以继续学习为主、泡论坛为辅。

作者: mik 时间: 2006-08-20 00:40

原帖由默难于 2006-8-20 00:37 发表

-_-||
我说是随机数目了吗？我说的是实现一个接口和alloca函数匹配的函数

那你就把你函数库里的alloca函数删除吧，否则太难维护了……

算了……我懒得解释了，你google一下吧……谁有闲功夫就帮忙解释一下

汗~~ 这种讨论格格不入，基本上好象对牛弹琴一样（没贬的意思）

那就STOP了

作者: mik 时间: 2006-08-20 00:41

原帖由 flw 于 2006-8-20 00:39 发表
这几天对 mik 有了更多的认识。
to mik：
现阶段你应该以继续学习为主、泡论坛为辅。

老大，请指正啥地方错误了

作者: 默难 时间: 2006-08-20 00:47
算了……只能怪我好心 + 爱管闲事 + 较真 + 好为人师 ...
替你google了一下子
你自己看看这里吧：
http://www.opensource.apple.com/darwinsource/Current/emacs-59/emacs/src/alloca.s
这里是alloca在68000和16000上面的实现，大同小异，关键部位给你截下来了：

_alloca
move.l (sp)+,a0 ; pop return addr from top of stack
move.l (sp)+,d0 ; pop size in bytes from top of stack
add.l #ROUND,d0 ; round size up to long word
and.l #MASK,d0 ; mask out lower two bits of size
;;;;;;;;;;;;;;;;;;;;;;;;注意这里;;;;;;;;;;;;;;;;;;;;;;;;;
sub.l d0,sp ; allocate by moving stack pointer
;;;;;;;;;;;;;;;;;;;;;;;;注意这里;;;;;;;;;;;;;;;;;;;;;;;;;
tst.b PROBE(sp) ; stack probe to allocate pages
move.l sp,d0 ; return pointer
add.l #-4,sp ; new top of stack
jmp (a0) ; not a normal return

复制代码

代码看不懂看注释，注释不明白我帮你翻译一下：通过移动栈指针申请栈上的空间
如果还不明白……你就继续google吧

作者: 默难 时间: 2006-08-20 00:50
看到了一个x86上实现的alloca，mik你看一下吧……今天我有点较真……

alloca.s
.text
.globl alloca
.align 4
alloca:
popl %edx / return address
popl %eax / nbytes
movl %esp,%ecx
subl %eax,%esp / calculate new esp
andl $-4,%esp / make sure stack is 4 byte aligned
movl %esp,%eax / return pointer to new memory in eax
pushl 8(%ecx) / copy saved registers
pushl 4(%ecx)
pushl 0(%ecx)
pushl %ecx / we need to push a fake argument here
/ since alloca's caller will attempt to
/ clean up the stack
jmp *%edx / return

复制代码

作者: flw 时间: 2006-08-20 00:53

原帖由 mik 于 2006-8-20 00:40 发表

汗~~ 这种讨论格格不入，基本上好象对牛弹琴一样（没贬的意思）

那就STOP了

哦，倒不是说你什么错了，
你说错的还是很少的，
不过往往都没有分清对象。

作者: mik 时间: 2006-08-20 00:58

原帖由默难于 2006-8-20 00:47 发表
算了……只能怪我好心 + 爱管闲事 + 较真 + 好为人师 ...
替你google了一下子
你自己看看这里吧：
http://www.opensource.apple.com/ ... /emacs/src/alloca.s
这里是alloca在68000和 ...

晕S~~ 算了，啥都不要说了

这个68000的汇编码，我确实没接触过，看不懂。

说到层次及底层上，你是比不上我的。

只是，我说的东西和表达出来的东东，别人不理解而已，个人表达问题。

以上关于 esp 的言论，我从头到尾只是说：由程序员来维护将是增加成本。这些函数代码是编译器产生的，编译器作出栈分配栈销栈工作。

如果，你用汇编写码，这个工作当然是由程序员来做~~~

汗~~~~~

作者: mik 时间: 2006-08-20 01:01

原帖由默难于 2006-8-20 00:50 发表
看到了一个x86上实现的alloca，mik你看一下吧……今天我有点较真……
[code]
alloca.s
      .text
      .globl  alloca
      .align  4
alloca:
      popl %edx          / return addre ...

别用这些汇编代码来抛我~ 我写汇编码的时候，或许你还没接触过。

作者: mik 时间: 2006-08-20 01:02

原帖由 flw 于 2006-8-20 00:53 发表

哦，倒不是说你什么错了，
你说错的还是很少的，
不过往往都没有分清对象。

其实，我真的很想知道哪错了？请指正一下，让我纠正纠正

作者: 默难 时间: 2006-08-20 01:04
算了……今天我也真是犯贱了……
mik底层开发能力确实很强，这一点我已经深刻地体会到了

作者: mik 时间: 2006-08-20 01:09
只怪我表达不清~~~ 说明我与人沟通方面有问题

今晚又犯贱了，又挨批了~

作者: ccas 时间: 2006-08-20 01:12
只是技术上的讨论，不要往其它方面发展

作者: foolfoolbird 时间: 2006-08-20 01:44
咋改阿？？？？

作者: gotop167 时间: 2006-08-20 09:58
首先都不能通过编译

作者: harly 时间: 2006-08-20 12:46
这个 alloca.s　有意思。。

作者: 默难 时间: 2006-08-20 14:38
……莫非大家都不用alloca这个函数

作者: jeffshia 时间: 2006-08-20 15:06

原帖由默难于 2006-8-20 00:37 发表

-_-||

那你就把你函数库里的alloca函数删除吧，否则太难维护了……

我说是随机数目了吗？我说的是实现一个接口和alloca函数匹配的函数

函数返回之后esp就会返回成调用前的值了……

算了……我懒得解 ...

动不动就是懒得....
看来你是很牛啊
呵呵

作者: 默难 时间: 2006-08-20 15:17

原帖由 jeffshia 于 2006-8-20 15:06 发表

动不动就是懒得....
看来你是很牛啊
呵呵

你没发现真正的牛人都根本不再关注这个帖子了吗……否则也不致于为了这么个简单问题在这里纠缠不清了。
我之所以说懒得，完全是因为这种基本概念可以google出来，而且google出来的东西比我讲得清楚多了
其实这个问题的详细解释，我已经通过站内短信，给对这个问题感兴趣的人讲解了。
这种基础问题我觉得没有必要在坛子里头大张旗鼓地帖帖子。当然了，要是有需求，我可以发帖子解释

这个帖子已经完全脱离了技术帖子的范畴了。斑竹看到后有必要做一些处理。

关于alloca的问题，要是有个明白人出来解释一下也好，免得这个帖子误人子弟。

作者: x2 时间: 2006-08-20 17:11
realloc
http://www.opengroup.org/onlinep ... ctions/realloc.html

至于如何将一维数组当二维数组使要自己想办法了。

[ 本帖最后由 x2 于 2006-8-20 17:15 编辑 ]

作者: harly 时间: 2006-08-20 18:45
呵呵，支持　默难。
这个函数还是很好用的，我想 mik　朋友，只要你好好理解了程序运行时的堆栈桢，想清楚这些东西应该不成问题的，还记得你都是写汇编器的高人了，怎么不认真考虑下这个函数的优势和劣势及其使用场合呢？

作者: harly 时间: 2006-08-20 23:39
现在我重新实现了ualloca函数，因为我找不到glibc下这个函数的实现,而　默难　贴的代码改变了edx寄存器的值。大家来讨论讨论，我觉得这个函数很有意义，为了不与系统的函数重名，函数名前面加了个u，汇编代码为：
/*ualloca.S*/
.text
   .global ualloca
   .align 4

ualloca:
xchgl %ebx, (%esp)    　　　/* so I have change old eip with ebp*/

movl 4(%esp), %eax 　　　　　/*param*/
addl $3,  %eax
andl $-4, %eax 　　　　　　　/*  get the off size, considering align*/

subl %eax, %esp       　　　 /* allocate space*/

pushl $0             　　　　　　/* for the caller balance stack,no real use*/
pushl %ebx          　　　　　　/* return address*/

movl 8(%esp,%eax),%ebx 　/* recover ebx*/

leal 16(%esp), %eax    　　 /*return value*/

ret

测试用的C函数代码：
#include <stdio.h>
#include <string.h>
#include <stddef.h>

extern void * ualloca(size_t size);

const char* prompt = "yes, Hello, I want to test alloca function\n" ;

int main()
{
   int i = 4;
   printf("%p\n", &i);

   char *p = (char*)ualloca( strlen(prompt) +1);


   strcpy(p, prompt);
   printf("%p\n", p);
   printf("%s", p);

   printf("the prompt length = %d\n the p lenthg = %d\n",strlen(prompt),strlen(p));

   int j = 6;
   printf("%d",j);

   getchar();
   return 0;
}

以上代码我在windows下用dev-cpp和rh9下测试通过，不过在dev-cpp下面要将汇编代码ualloca改成_ualloca

[ 本帖最后由 harly 于 2006-8-21 16:33 编辑 ]

作者: connet 时间: 2006-08-21 11:33
通常应该避免使用 alloca 吧， stack overflow 不是好玩的。
特别是大型程序。
apache 2.0.48 中只有 poll 中一个地方使用 alloca
php 511 中是 #define YYSTACK_ALLOC alloca 只有 3处使用。
而且都是 #define alloca __buildin_alloca, 使用 inlined code

作者: harly 时间: 2006-08-21 12:35
GCC下面是用的这个宏，但愿变长数组真正取代alloca吧，不过好像也避免不了stack overflow

[ 本帖最后由 harly 于 2006-8-21 16:34 编辑 ]

作者: ccas 时间: 2006-08-23 18:45
如果我定义了一个数组
  int int_ary[3][3]={{1,1,1},
                           {2,2,2},
                           {3,3,3}};
现在要把它扩展成 4行4列，
  int int_ary[4][4]={{1,1,1,NULL},
                           {2,2,2,NULL},
                           {3,3,3,NULL},
                           {NULL,NULL,NULL,NULL}};
用分配空间的语句(alloc,malloc,remalloc等)要怎么写

作者: harly 时间: 2006-08-24 10:01
其实还是先要算出你的二维数组占用的总空间，然后用这个长度alloca,malloc等，最后按照将你原来的复制过来，当然不能简单地memcpy就行了，要根据维数对应地memcpy。

作者: 羽人 时间: 2006-08-24 11:43

原帖由 ccas 于 2006-8-23 18:45 发表
如果我定义了一个数组
  int int_ary[3][3]={{1,1,1},
                           {2,2,2},
                           {3,3,3}};
现在要把它扩展成 4行4列，
  int int_ary[4][4]={{1,1,1,NULL},
                           {2,2,2,NULL},
                           {3,3,3,NULL},
                           {NULL,NULL,NULL,NULL}};
用分配空间的语句(alloc,malloc,remalloc等)要怎么写

我个人认为，你所说的“扩展”这个词的含义，其实很值得推敲。
按你的代码中所表现的意思，应该是指“数组的名称不变，但是大小变化了”，不知道我理解的对不对？

如果是这样的话，那么我觉得任何一个函数恐怕都帮不上忙。
因为无论从堆里还是从栈里重新分配一个buffer，你都无法将这个buffer的首地址赋给已经分配了的数组“int_ary”。因为“int_ary”是不能被作为左值来使用的。也就是说它无法被重新赋值，它永远只能指向初始化时被分配的首地址。

如果你真的想实现“数组的名称不变，但是大小变化”，其实方法也很简单，那就是什么都不用做！
因为C编译器虽然分配了固定内存给数组，但通常并不阻止你使用超过这个数组界限的内存空间。举例如下：

int i;
int arr[10];
for(i=0; i<15; i++) {
arr[i] = i;
}
for(i=0; i<15; i++) {
printf("%d\n",arr[i]);
}

复制代码

这个程序是可以编译通过的，而且会按照我们设想的输出。
二维数组和一维一样都是连续的内存空间，所以可以用同样的方法。只不过实现起来会麻烦一些，你可能需要先把原数组的内容拷贝到别的内存空间，然后再按照某种方法拷贝回来并重新组织。

但是从编程的角度来说，上面的方法应该是被摒弃的！原因嘛大家肯定都很清楚，我就不多说了。

作者: harly 时间: 2006-08-24 12:35
嗯，你说的不错，是可以有技巧的。不过如果这样写，在函数里会出现堆栈溢出的，如果在数据区分配的也不怎么行吧。呵呵，你说的对，我们应该摒弃这种写法。
      int    i;
      int    arr[10];

      for(i=0; i<15; i++) {
            arr[i] = i;
      }
      for(i=0; i<15; i++) {
            printf("%d\n",arr[i]);
      }

作者: 羽人 时间: 2006-08-24 13:46

原帖由 harly 于 2006-8-24 12:35 发表
嗯，你说的不错，是可以有技巧的。不过如果这样写，在函数里会出现堆栈溢出的，如果在数据区分配的也不怎么行吧。呵呵，你说的对，我们应该摒弃这种写法。
int i;
int arr[10];

...

这种方法对于函数内部的数组（分配在栈内）和全局数组（分配在数据区内）都是可用的。

这种程序可能你运行很长时间都不会有问题，突然有一天却coredump了。
像我这种写法，在做代码review时很容易被发现。但是如果把这个数组名作为一个指针使用，就很可能会忽略掉边界检查。

作者: harly 时间: 2006-08-24 14:13

原帖由羽人于 2006-8-24 13:46 发表

这种方法对于函数内部的数组（分配在栈内）和全局数组（分配在数据区内）都是可用的。

这种程序可能你运行很长时间都不会有问题，突然有一天却coredump了。
像我这种写法，在做代码review时很容易被发现 ...

兄弟，不一定噢，刚才情况不溢出，是你的循环次数少了点，我改成了55，就覆盖了堆栈里面的eip了，你运行下看看。

#include<stdio.h>

int main()
{

      int    arr[10];
      int    i;
      for(i=0; i<55; i++) {
            *(arr+i) = i;
      }
      for(i=0; i<55; i++) {
            printf("%d\n",*(arr+i));
      }
      printf("It can not be run in my os\n" ) ;
      getchar();
}

兄弟，帮个忙，告诉我怎么贴代码。。

[ 本帖最后由 harly 于 2006-8-24 14:15 编辑 ]

作者: 羽人 时间: 2006-08-24 16:22

原帖由 harly 于 2006-8-24 14:13 发表

兄弟，不一定噢，刚才情况不溢出，是你的循环次数少了点，我改成了55，就覆盖了堆栈里面的eip了，你运行下看看。

#include<stdio.h>

int main()
{

int arr[10];
in ...

是这样的。
所以我在帖子里说“这种程序可能你运行很长时间都不会有问题，突然有一天却coredump了”，就是说的这种情况。当超出数组的界限小的时候，不会有问题；超出的多了，肯定出错。

粘贴“代码”的方法，我通过站内短信发给你了。

作者: harly 时间: 2006-08-24 17:33

兄弟，谢谢你了噢。现在终于明白了:lol:

复制代码

作者: hxs880 时间: 2006-08-24 19:51
vector

作者: happer_xc 时间: 2006-08-24 21:05
用 realloc 能保证原来数组中的值还在正确的位置上吗？

作者: harly 时间: 2006-08-24 21:12

原帖由 happer_xc 于 2006-8-24 21:05 发表
用 realloc 能保证原来数组中的值还在正确的位置上吗？

To: happer_xc

如果是实现多维数组转化成一维用malloc等来实现，用realloc不能让新生成的多维满足原来维数间的对应关系。因此你要手工复制，所以我觉得没必要用realloc，可以继续考虑用malloc。

欢迎光临 Chinaunix (http://bbs.chinaunix.net/)