我只是有一个关于 C 中数组的简单问题:
从数组中删除元素并在此过程中使数组变小的最佳方法是什么。
即:数组的大小为
n
,然后我从数组中取出元素,然后数组会随着我删除元素的数量而变小。
基本上,我将数组视为一副纸牌,一旦我从这副纸牌顶部取出一张纸牌,它就不应该再存在了。
编辑:我要在一天结束之前让自己发疯,感谢所有帮助我尝试价值交换的事情,但它工作不正常。
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
enum faces { Ace = 0, Jack = 10, Queen, King };
char *facecheck(int d);
int draw(int deck, int i);
int main() {
int deck[52], i, n;
char suits[4][9] = {
"Hearts",
"Diamonds",
"Clubs",
"Spades"
};
n = 0;
for (i = 0; i < 52; i++) {
deck[i] = n;
n++;
};
for (i = 0; i < 52; i++) {
if (i % 13 == 0 || i % 13 == 10 || i % 13 == 11 || i % 13 == 12)
printf("%s ", facecheck(i % 13));
else
printf("%d ", i % 13 + 1);
printf("of %s \n", suits[i / 13]);
}
draw(deck, i);
return 0;
}
char *facecheck(int d) {
static char *face[] = {
"Ace",
"Jack",
"Queen",
"King"
};
if (d == Ace)
return face[0];
else {
if (d == Jack)
return face[1];
else {
if (d == Queen)
return face[2];
else {
if (d == King)
return face[3];
}
}
}
}
int draw(int deck, int i) {
int hand[5], j, temp[j];
for (i = 0; i < 52; i++) {
j = i
};
for (i = 0; i < 5; i++) {
deck[i] = hand[];
printf("A card has been drawn \n");
deck[i] = temp[j - 1];
temp[j] = deck[i];
};
return deck;
}
确实有两个不同的问题。 第一个是保持数组元素的正确顺序,以便删除元素后不会出现“空洞”。 第二个实际上是调整数组本身的大小。
C 中的数组被分配为固定数量的连续元素。 无法实际删除数组中单个元素使用的内存,但可以移动元素以填充删除元素造成的空洞。 例如:
void remove_element(array_type *array, int index, int array_length)
{
int i;
for(i = index; i < array_length - 1; i++) array[i] = array[i + 1];
}
静态分配的数组无法调整大小。 动态分配的数组可以使用
realloc()
调整大小。 这可能会将整个数组移动到内存中的另一个位置,因此必须更新指向数组或其元素的所有指针。 例如:
remove_element(array, index, array_length); /* First shift the elements, then reallocate */
array_type *tmp = realloc(array, (array_length - 1) * sizeof(array_type) );
if (tmp == NULL && array_length > 1) {
/* No memory available */
exit(EXIT_FAILURE);
}
array_length = array_length - 1;
array = tmp;
如果请求的大小为 0,或者出现错误,realloc()
将返回 NULL 指针。 否则,它返回指向重新分配的数组的指针。 临时指针用于在调用 realloc()
时检测错误,因为也可以不退出,而是保留原始数组不变。 当 realloc()
重新分配数组失败时,它不会改变原始数组。
请注意,如果数组很大或者删除了很多元素,这两个操作都会相当慢。 如果优先考虑高效插入和删除,还可以使用其他数据结构,例如链表和哈希。
您需要什么解决方案取决于您是否希望数组保留其顺序。
通常,您不仅有数组指针,还有一个保存其当前逻辑大小的变量,以及一个保存其分配大小的变量。我还假设
removeIndex
在数组的范围内。有了这个,删除就很简单了:
array[removeIndex] = array[--logicalSize];
就是这样。您只需将最后一个数组元素复制到要删除的元素上,在此过程中减少数组的
logicalSize
。
如果
removeIndex == logicalSize-1
,即要删除最后一个元素,这会降级为最后一个元素的自分配,但这不是问题。
memmove(array + removeIndex, array + removeIndex + 1, (--logicalSize - removeIndex)*sizeof(*array));
稍微复杂一点,因为现在我们需要调用
memmove()
来执行元素的移动,但仍然是一行代码。同样,这也会在此过程中更新数组的 logicalSize
。
您并不真的希望每次删除某些内容时都重新分配内存。如果您知道 deck 的粗略大小,请为数组选择适当的大小,并保留指向列表当前 end 的指针。这是一个堆栈。
如果你不知道你的牌组的大小,并且认为它可能会变得非常大并且不断改变大小,那么你将不得不做一些更复杂的事情并实现一个linked-list。
在 C 中,有两种简单的方法来声明数组。
在堆栈上,作为静态数组
int myArray[16]; // Static array of 16 integers
在堆上,作为动态分配的数组
// Dynamically allocated array of 16 integers
int* myArray = calloc(16, sizeof(int));
标准 C 不允许调整这两种类型的数组的大小。您可以创建一个特定大小的新数组,然后将旧数组的内容复制到新数组,或者您可以按照上面针对不同抽象数据类型的建议之一(即:链表、堆栈、队列、等)。
有趣的是,数组可以通过索引随机访问。随机删除一个元素也可能会影响其他元素的索引。
int remove_element(int*from, int total, int index) {
if((total - index - 1) > 0) {
memmove(from+i, from+i+1, sizeof(int)*(total-index-1));
}
return total-1; // return the new array size
}
请注意,由于内存重叠,
memcpy
在这种情况下将不起作用。
删除一个随机元素的有效方法之一(比内存移动更好)是与最后一个元素交换。
int remove_element(int*from, int total, int index) {
if(index != (total-1))
from[index] = from[total-1];
return total; // **DO NOT DECREASE** the total here
}
但是移除后顺序就变了。
同样,如果删除是在循环操作中完成的,则重新排序可能会影响处理。内存移动是在删除数组元素时保持顺序的一种昂贵的替代方法。在循环中保持顺序的另一种方法是推迟删除。可以通过相同大小的有效性数组来完成。
int remove_element(int*from, int total, int*is_valid, int index) {
is_valid[index] = 0;
return total-1; // return the number of elements
}
它将创建一个稀疏数组。最后,通过进行一些重新排序,可以使稀疏数组变得紧凑(不包含两个有效元素,而它们之间包含无效元素)。
int sparse_to_compact(int*arr, int total, int*is_valid) {
int i = 0;
int last = total - 1;
// trim the last invalid elements
for(; last >= 0 && !is_valid[last]; last--); // trim invalid elements from last
// now we keep swapping the invalid with last valid element
for(i=0; i < last; i++) {
if(is_valid[i])
continue;
arr[i] = arr[last]; // swap invalid with the last valid
last--;
for(; last >= 0 && !is_valid[last]; last--); // trim invalid elements
}
return last+1; // return the compact length of the array
}
尝试这个简单的代码:
#include <stdio.h>
#include <conio.h>
void main(void)
{
clrscr();
int a[4], i, b;
printf("enter nos ");
for (i = 1; i <= 5; i++) {
scanf("%d", &a[i]);
}
for(i = 1; i <= 5; i++) {
printf("\n%d", a[i]);
}
printf("\nenter element you want to delete ");
scanf("%d", &b);
for (i = 1; i <= 5; i++) {
if(i == b) {
a[i] = i++;
}
printf("\n%d", a[i]);
}
getch();
}
我通常这样做并且总是有效。
/试试这个/
for (i = res; i < *size-1; i++) {
arrb[i] = arrb[i + 1];
}
*size = *size - 1; /*in some ides size -- could give problems*/