Xóa các phần tử khỏi mảng trong C

Question

Tôi chỉ có một câu hỏi đơn giản về mảng trong C

Cách tốt nhất để loại bỏ các phần tử khỏi mảng là gì và làm cho mảng nhỏ hơn.

tức là mảng có kích thước n, sau đó tôi lấy các phần tử ra khỏi mảng và sau đó mảng tăng lên nhỏ hơn theo số lượng mà tôi đã loại bỏ.

về cơ bản tôi đang xử lý mảng giống như một cỗ bài và một khi tôi lấy thẻ ra khỏi boong tàu, nó không còn ở đó nữa.

EDIT: Tôi sẽ lái xe bản thân mình điên trước khi kết thúc ngày, cảm ơn tất cả sự giúp đỡ Tôi đang cố gắng trao đổi giá trị điều nhưng nó không hoạt động đúng.

#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; 
} 

Answer 1

Bạn thực sự không muốn tạo lại bộ nhớ mỗi lần xóa thứ gì đó. Nếu bạn biết kích thước thô của boong sau đó chọn kích thước phù hợp cho mảng của mình và giữ một con trỏ đến kết thúc hiện tại mới nhất của danh sách. Đây là stack.

Nếu bạn không biết kích thước sàn tàu của mình và nghĩ rằng nó có thể to lớn cũng như giữ kích thước thay đổi, thì bạn sẽ phải làm điều gì đó phức tạp hơn và thực hiện linked-list.

Trong C, bạn có hai cách đơn giản để khai báo mảng.

1. Trên đống, như một mảng tĩnh

   int myArray[16]; // Static array of 16 integers 
   

2. Trên đống, như một mảng cấp phát động

   // Dynamically allocated array of 16 integers 
   int* myArray = calloc(16, sizeof(int)); 
   

chuẩn C không cho phép mảng của một trong hai các loại này được thay đổi kích thước. Bạn có thể tạo một mảng mới có kích thước cụ thể, sau đó sao chép nội dung của mảng cũ sang mảng mới hoặc bạn có thể làm theo một trong các đề xuất ở trên cho một kiểu dữ liệu trừu tượng khác (ví dụ: danh sách được nối kết, ngăn xếp, hàng đợi, v.v.)

Answer 2

Có hai vấn đề riêng biệt. Đầu tiên là giữ các phần tử của mảng theo đúng thứ tự sao cho không có "lỗ hổng" sau khi loại bỏ một phần tử. Thứ hai là thực sự thay đổi kích thước mảng chính nó.

Mảng trong C được phân bổ dưới dạng số cố định các phần tử tiếp giáp. Không có cách nào để thực sự loại bỏ bộ nhớ được sử dụng bởi một phần tử riêng lẻ trong mảng nhưng các phần tử có thể được dịch chuyển để lấp đầy lỗ được tạo ra bằng cách loại bỏ một phần tử. Ví dụ:

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]; 
} 

Không thể thay đổi kích thước mảng được phân bổ tĩnh. Các mảng được phân bổ động có thể được thay đổi kích thước bằng realloc(). Điều này sẽ có khả năng di chuyển toàn bộ mảng đến một vị trí khác trong bộ nhớ, vì vậy tất cả các con trỏ tới mảng hoặc các phần tử của nó sẽ phải được cập nhật. Ví dụ:

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; 

realloc sẽ trả về một con trỏ NULL nếu kích thước yêu cầu là 0, hoặc nếu có một lỗi. Nếu không, nó sẽ trả về một con trỏ tới mảng được phân bổ lại.Con trỏ tạm thời được sử dụng để phát hiện lỗi khi gọi realloc bởi vì thay vì thoát nó cũng có thể chỉ để lại mảng ban đầu như nó được. Khi realloc không tái phân bổ một mảng, nó không thay đổi mảng ban đầu.

Lưu ý rằng cả hai thao tác này sẽ khá chậm nếu mảng lớn hoặc nếu nhiều phần tử bị xóa. Có những cấu trúc dữ liệu khác như danh sách liên kết và băm có thể được sử dụng nếu chèn và xóa hiệu quả là ưu tiên.

Answer 3

Có thể truy cập ngẫu nhiên mảng theo chỉ mục. Và việc loại bỏ ngẫu nhiên một phần tử cũng có thể ảnh hưởng đến các chỉ mục của các phần tử khá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 
    } 

Lưu ý rằng memcpy sẽ không hoạt động trong trường hợp này do bộ nhớ chồng chéo.

Một trong những cách hiệu quả (tốt hơn di chuyển bộ nhớ) để loại bỏ một phần tử ngẫu nhiên đang trao đổi với phần tử cuối cùng.

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 
    } 

Nhưng thứ tự được thay đổi sau khi xóa.

Một lần nữa nếu việc loại bỏ được thực hiện trong hoạt động vòng lặp thì việc sắp xếp lại có thể ảnh hưởng đến việc xử lý. Bộ nhớ di chuyển là một thay thế đắt tiền để giữ trật tự trong khi loại bỏ một phần tử mảng. Một cách khác để giữ trật tự trong khi lặp lại là trì hoãn việc loại bỏ. Nó có thể được thực hiện bằng mảng hợp lệ có cùng kích thước.

int remove_element(int*from, int total, int*is_valid, int index) { 
      is_valid[index] = 0; 
      return total-1; // return the number of elements 
    } 

Nó sẽ tạo một mảng thưa thớt. Cuối cùng, mảng thưa thớt có thể được tạo nhỏ gọn (không chứa hai phần tử hợp lệ có chứa phần tử không hợp lệ giữa chúng) bằng cách làm một số sắp xếp lại.

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 
    }