Home / Questions / 27074
Accepted
NaCl
Asked: 2020-10-12 10:50:51 +0800 CST 2020-10-12 10:50:51 +0800 CST

从“列表”中删除项目

  • 772

好的，

我正在学习使用 C 中的指针，我对我正在实现的算法有一个问题，该算法广泛使用malloc,realloc和free，这是代码：

列表.h

#ifndef _LIST_H_
#define _LIST_H_

typedef struct {
    int    Count;
    void **Elements;
} List;

List *list_new();
void  list_insert(List *l, void *elem);
void *list_getelem(List *l, int offset);
void  list_removeoffset(List *l, int elem);
void  list_free(List *l);
int   list_get_count(List *l);

#endif

列表.c

#include <stdio.h>
#include <stdlib.h>
#include "List.h"

List *list_new() {
    List *ptr = malloc(sizeof(List));
    ptr->Elements = malloc(sizeof(void*));
    ptr->Count = 0;
    return (ptr) ? ptr : NULL;
}
void list_insert(List *l, void *elem) {
    if (l->Count == 0) 
        l->Elements = realloc(l->Elements, sizeof(void*));
    else 
        l->Elements = realloc(l->Elements, (sizeof(void*) * l->Count));
    l->Elements[l->Count] = elem;
    l->Count++;
}
void *list_getelem(List *l, int offset) {
    if (offset < 0 || offset >= l->Count) return NULL;
    return l->Elements[offset];
}
void list_removeoffset(List *l, int elem) {
    if (elem < 0 || elem >= l->Count) return;
    l->Elements[elem] = NULL; 
    l->Count--; 
    l->Elements = realloc(l->Elements, sizeof(void*) * l->Count);   
}
void list_free(List *l) {
    if (l) {
        free(l->Elements); free(l);
    }
}
int list_get_count(List *l) {
    return l->Count;
}

我的问题出现在方法声明中list_removeoffset(...)，我无法删除offset指针数组中某个位置的元素。

main()：

List *MyList = list_new();

list_insert(MyList, (int*)3416); printf("List Count Now: %d\n", list_get_count(MyList));
list_insert(MyList, (char*)"hello world"); printf("List Count Now: %d\n", list_get_count(MyList));
list_insert(MyList, (int*)5); printf("List Count Now: %d\n", list_get_count(MyList));

这是我使用上述代码得到的结果：

List Count Now: 1
List Count Now: 2
List Count Now: 3
Element at position 1: hello world

它确实有效，但是在尝试使用以下代码删除元素时：

list_removeoffset(MyList, 1); // Intento remover el elemento en la posicion 1.

显然它被删除了，但是，以同样的方式，它释放了在这个元素之后的其他元素的内存并显示了结果0。

我怎样才能删除或释放一个项目而不是它之后的所有项目？

c

3 Answers

  1. Best Answer

    首先，对于realloc您使用的数量，您的实现在计算时间上效率很低。请注意，在最坏的情况下，它会realloc复制内存块。因此，链表上的操作O(1)在您的列表中最终是O(n). 我建议在您的列表中保留物理和逻辑大小，并且仅当逻辑大小非常接近物理大小时“向上”调整向量的大小，而当逻辑大小相对于物理大小非常小时，“向下”调整向量的大小。

    继续您的问题，realloc它确实减少了它使用的内存块的大小，但仅此而已。作为实施者，您有责任在可用空间之前“推进”剩余的列表项。从原理上讲，会发生这样的事情：

    原始向量：

    ------------------------
0: ptr to 3416
1: ptr to "hello world"
2: ptr to 5
------------------------

    重新分配l->Count和之后l->Elements[1]：

    ------------------------
0: ptr to 3416
1: NULL
2: ptr to 5
------------------------

    之后realloc：

    ------------------------
0: ptr to 3416
1: NULL
------------------------
2: ptr to 5 <<< Fuera del bloque, y la memoria ya no le pertenece a tu programa

    简而言之，发生的情况不是您要删除的向量的所有数据都被释放，而是最后一个丢失了。在您的特定情况下，由于数组只有三个元素，因此最后一个元素也是“删除的所有元素”。

    你应该做的是，而不是分配NULLto ，将（和 from to ， from to等）Elements[1]的内容复制到它。这样，在您拥有这样的向量之前：Elements[2][3][2][4][3]realloc

    ------------------------
0: ptr to 3416
1: ptr to 5 <<< Copiado de [2]
2: ptr to 5
------------------------

    之后realloc：

    ------------------------
0: ptr to 3416
1: ptr to 5
------------------------
2: ptr to 5
    • 2

  2. 通过删除，您将元素设置elem为 NULL，然后重新分配，从而丢失最后一个元素。这就是事情list_removeoffset(MyList, 1); 

    Count = 3                                 Count = 2
Elem 0 : (void*) 3416                     (void*) 3416
Elem 1 : (void*) "hello world"   =====>   (void*) NULL
Elem 2 : (void*) 5

    这就是你想要得到的：

    Count = 3                                 Count = 2
Elem 0 : (void*) 3416                     (void*) 3416
Elem 1 : (void*) "hello world"   =====>   (void*) 5
Elem 2 : (void*) 5

    为此，您必须将所有元素从elem+1末尾重新分配到数组中的较低位置：

    void list_removeoffset(List *l, int elem) {
    int i;
    if (elem < 0 || elem >= l->Count) return;
    --(l->Count);
    for( i=elem; i<l->Count; ++i ) {
      l->Elements[i] = l->Elements[i+1];
    }
    l->Elements = realloc(l->Elements, sizeof(void*) * l->Count);   
}

    请注意，您list_insert有一个错误。当 Count 等于 1 时，size 保留给一个元素，但应该保留给两个；1 表示已经存在的，1 表示新的。较大的值也会发生同样的情况。正确的方法是：

    void list_insert(List *l, void *elem) {
    l->Elements = realloc(l->Elements, sizeof(void*)*(l->Count+1));
    l->Elements[l->Count] = elem;
    ++l->Count; 
}
    • 1

  3. 我认为问题在于您正在以较小的尺寸进行重新分配。这个 C 函数是低级的，不考虑空值，所以它只是从数组末尾删除东西。顺便说一句，收缩没有定义的行为，所以你不妨从一开始就删除元素。

    您想要实现的，即使用公平内存，是通过链表实现的。唯一不好的是迭代它们比较慢，因为它们不在连续的内存位置（缓存未命中）。但是可以进行更“壮观”的近似，按块分配内存。

    • 0