-3

考虑一个具有以下属性的动态表:

  • 元素存储在动态数组中
  • 容量是动态数组的大小
  • 大小定义为存储在数组中的元素个数

将元素插入此动态表中。如果大小等于 push_back() 之前的容量,则容量加倍

不要使用 malloc 或 calloc 函数。

输入:(n,元素)
9
6 7 8 12 4 10 11 1 15
输出:
容量 = 1;大小 = 1; 元素 = 6
容量 = 2;大小 = 2; 元素 = 6 7
容量 = 4;大小 = 3; 元素 = 6 7 8
容量 = 4;大小 = 4; 元素 = 6 7 8 12
容量 = 8;大小 = 5; 元素 = 6 7 8 12 4
容量 = 8;大小 = 6; 元素 = 6 7 8 12 4 10
容量 = 8;大小 = 7; 元素 = 6 7 8 12 4 10 11
容量 = 8;大小 = 8; 元素 = 6 7 8 12 4 10 11 1
容量 = 16;大小 = 9; 元素 = 6 7 8 12 4 10 11 1 15

#include <stdio.h>
int size=0;
int capacity=0;

int * double_capacity(int *a) {
    int l=0;
    if(capacity==0) capacity++;
    capacity=capacity*2;
    int b[capacity];
    for(l;l<size;l++){
        //printf("%d : %d \n",l,a[l]);
        b[l]=a[l];
    }
    return b;
}

int * push_back(int *a,int j) {
    if(size==capacity)
        a=double_capacity(a);
    a[size]=j;
    size++;
    int k=0;
    printf("capacity = %d; size = %d; elements = ",capacity,size);
    for(k=0;k<size;k++) {
        printf(" %d",*(a+k));
    }
    printf("\n");
    return a;
}


main() {
    int *a;
    int n,i,j,k,l;
    scanf("%d",&n);
    int temp[n];
    for(i=0; i<n; i++) {
        scanf("%d",&temp[i]);
    }

    for(i=0; i<n; i++) {
        a=push_back(a,temp[i]);
    }
}

它显示编译错误,如
\temp.c: In function 'double_capacity':
temp.c:16:2: warning: function returns address of local variable [-Wreturn-local-addr]
return b;
^


即使我运行这个

当我给输入
3 3 2 1
输出
容量 = 1; 大小 = 1; 元素 = 3
容量 = 2;大小 = 2; 元素 = 3 2
容量 = 4;大小 = 3; 元素 = 3 2 1

当我给输入
5 5 4 3 2 1
输出
容量 = 1; 大小 = 1; 元素 = 5
容量 = 2;大小 = 2; 元素 = 5 4
容量 = 4;大小 = 3; 元素 = 5 4 3
容量 = 4;大小 = 4; 元素 = 0 0 -2128976676 2
容量 = 8;大小 = 5; 元素 = 0 0 -2128976676 32524 1

4

1 回答 1

1

这不会按您希望的方式工作:

int * double_capacity(int *a) 
{
  int l=0;

  if(capacity==0) 
    capacity++;

  capacity=capacity*2;
  int b[capacity];
  for(l;l<size;l++)
  {
    //printf("%d : %d \n",l,a[l]);
    b[l]=a[l];
  }
  return b;
}

该数组b仅在double_capacity函数的生命周期内存在;一旦函数退出,b不再存在,任何指向它的指针现在都无效

您不能以这种方式使用 VLA。

我注意到你的说明没有提到realloc函数......

编辑

如果您不能使用任何标准的内存管理函数(malloccallocrealloc),那么我能想到的唯一真正的替代方法是创建您自己的内存池并从中分配您的表元素。

基本上,你会unsigned char像这样声明一个大的 at 文件范围数组:

#define HEAP_SIZE 8192 // 8 KB heap, use whatever size you need
static unsigned char heap[HEAP_SIZE];

然后你会抓住这个数组的块来构建你的表。您需要做一些簿记来管理可用和分配的块、它们在该数组中的地址和大小等。如果您知道自己在做什么,这取决于您想要它的健壮程度,这需要一天左右的时间成为。

再说一次,我可能忘记了一些更简单的事情。我只是暂时想不出来。

于 2015-09-01T20:19:25.747 回答