Xóa phần tử trùng trong mảng C

Posted on by mtoplistChuyên mục:Top List

Hướng dẫn cách xoá phần tử trùng trong mảng C. Bạn sẽ học được 2 cách căn bản để xoá phần tử trùng trong mảng C sau bài học này.

Chúng ta có 2 cách xóa phần tử trùng trong mảng C như sau:

  • Xóa phần tử trùng trong mảng C khi mảng đã được sắp xếp
  • Xóa phần tử trùng trong mảng C khi mảng chưa được sắp xếp

Có thể xóa phần tử trùng nhau trong mảng C?

Giả sử chúng ta có mảng chứa các phần tử trùng nhau như sau:

int
 
array
= {
1
, 
2
, 
3
, 
1
, 
3
, 
2
, 
4
};

Ở mảng này, các phần tử là 1, 2 và 3 là phần tử trùng nhau, và sau khi xoá phần tử trùng nhau, mảng kết quả sẽ là {1,2,3,4}.

Tuy nhiên khác với các ngôn ngữ lập trình khác thì mảng trong C có kích thước cố định được quyết định khi khai báo mảng, và chúng ta không thể thay đổi kích thước của mảng sau khi khai báo.

Bởi vậy, chúng ta không thể xóa phần tử trong mảng C, sau khi đã tạo nó. Điều duy nhất chúng ta có thể làm, đó là dịch chuyển nội bộ các phần tử không trùng nhau về một phía của mảng và chỉ sử dụng các phần tử này trong mảng mà thôi.

Lại nữa, tốc độ xoá phần tử trùng trong mảng C khi mảng đó đã được hoặc chưa được sắp xếp là khác nhau. Và do vậy, chúng ta sẽ có 2 phương pháp khác nhau để xoá phần tử trùng nhau trong mảng C theo logic ở trên như dưới đây.

Xóa phần tử trùng trong mảng C khi mảng đã được sắp xếp

Ý tưởng ở đây là, sau khi sắp xếp mảng, thì các phần tử trùng nhau (nếu có) sẽ được xếp nằm cạnh nhau, do đó chúng ta chỉ cần kiểm tra 2 phần tử trùng nhau xem chúng có bằng nhau hay không là có thể xác định được các phần tử trùng nhau trong mảng.

Và khi tìm thấy các phần tử trùng nhau rồi, chúng ta sẽ lần lượt chuyển chúng về phía đầu mảng bằng cách ghi đè giá trị lên các phần tử ở đầu mảng. Và sau đó chỉ cần lấy toàn bộ các phần tử này từ trong mảng là chúng ta có thể hoàn thành việc xóa phần tử trùng trong mảng C rồi.

Để sắp xếp mảng, chúng ta sẽ sử dụng tới hàm qsort() mà Kiyoshi đã hướng dẫn trong bài:

  • Xem thêm: Sắp xếp mảng trong C

Và chúng ta viết hàm xóa phần tử trùng trong mảng C trong chương trình như sau:








void
 
show_array
(
int
 
array
[], 
int
 length){
  
for
(
short
 i = 
0
; i < length; i++)  
printf
(
"%d "
, 
array
[i]);  
  
printf
(
"\n"
);
}



int
 
compareIntAsc
(
const
 
void
* a, 
const
 
void
* b)
{
    
int
 aNum = *(
int
*)a;
    
int
 bNum = *(
int
*)b;

    
return
 aNum - bNum;
}



size_t
 
array_unique
(
int
* 
array
, 
size_t
 size)
{
    
size_t
 end = 
0
;  

    
for
 (
size_t
 i = 
1
; i < size; ++i) {
        
if
 (
array
[i] != 
array
[end]) { 
            ++end; 

            
array
[end] = 
array
[i]; 
        }

    }


    
return
 end + 
1
;  
}


int
 
main
(
void
)
{
    
int
 array1[] = { 
7
, 
2
, 
6
, 
7
, 
4
, 
9
, 
8
 };
    
int
 array2[] = { 
7
, 
2
, 
6
, 
7
, 
7
 };
    
int
 array3[] = { 
7
, 
7
, 
7
 };

    

    qsort(array1, SIZE_OF_ARRAY(array1), 
sizeof
(
int
), compareIntAsc);
    qsort(array2, SIZE_OF_ARRAY(array2), 
sizeof
(
int
), compareIntAsc);
    qsort(array3, SIZE_OF_ARRAY(array3), 
sizeof
(
int
), compareIntAsc);

    

    
size_t
 size1 = array_unique(array1, SIZE_OF_ARRAY(array1));
    
size_t
 size2 = array_unique(array2, SIZE_OF_ARRAY(array2));
    
size_t
 size3 = array_unique(array3, SIZE_OF_ARRAY(array3));

    

    show_array(array1, size1);

    show_array(array2, size2);

    show_array(array3, size3);


    
return
 
0
;
}

Kết quả chương trình xóa phần tử trùng trong mảng C:

2 4 6 7 8 9 

2 6 7 

7

Ở phần trên chúng ta đã di chuyển các phần tử không trùng nhau lên đầu mảng ban đầu. Nếu bạn muốn lấy riêng các phần tử trùng nhau ra, hãy viết thêm xử lý lấy các phần tử này và gán vào một mảng mới nhé.

Xóa phần tử trùng trong mảng C khi mảng chưa được sắp xếp

Trong mảng C, cũng có những mảng mà chúng ta không thể sắp xếp mảng, hoặc là không có quyền sắp xếp mảng đó. Khi đó, chúng ta sẽ cần tới cách không sắp xếp mảng mà vẫn có thể xoá được phần tử trùng nhau trong mảng đó.

Để kiểm tra phần tử trùng trong mảng C, chúng ta có thể lấy lần lượt từng phần tử và so sánh xem có phần tử nào giống nó trong chuỗi ban đầu hay không.

Nếu tồn tại dù chỉ một cặp phần tử giống nhau, điều đó có nghĩa là tồn tại phần tử trùng nhau trong mảng ban đầu, và ngược lại nếu tất cả đều khác nhau thì không tồn tại phần tử trùng nhau trong mảng ban đầu.

Để làm được điều đó, chúng ta cần dùng tới một vòng lặp lồng để lấy và kiểm tra từng phần tử trong mảng ban đầu.

Và cách xóa phần tử trùng trong mảng C khi mảng chưa được sắp xếp như sau:








void
 
show_array
(
int
 
array
[], 
int
 length){
  
for
(
short
 i = 
0
; i < length; i++)  
printf
(
"%d "
, 
array
[i]);  
  
printf
(
"\n"
);
}



size_t
 
array_unique
(
int
* 
array
, 
size_t
 size)
{
    
for
 (
size_t
 i = 
0
; i < size - 
1
; ++i) {
        
for
 (
size_t
 j = i + 
1
; j < size; ++j) {
            
if
 (
array
[i] == 
array
[j]) { 

                

                memmove(&
array
[j], &
array
[j + 
1
], 
sizeof
(
int
) * (size - j - 
1
));

                --size; 


                

                

                --j;

            }

        }

    }


    
return
 size;
}



int
 
main
(
void
)
{
    
int
 array1[] = { 
7
, 
2
, 
6
, 
7
, 
4
, 
9
, 
8
 };
    
int
 array2[] = { 
7
, 
2
, 
6
, 
7
, 
7
 };
    
int
 array3[] = { 
7
, 
7
, 
7
 };

    

    
size_t
 size1 = array_unique(array1, SIZE_OF_ARRAY(array1));
    
size_t
 size2 = array_unique(array2, SIZE_OF_ARRAY(array2));
    
size_t
 size3 = array_unique(array3, SIZE_OF_ARRAY(array3));

    

    show_array(array1, size1);

    show_array(array2, size2);

    show_array(array3, size3);


    
return
 
0
;
}

Kết quả chương trình xóa phần tử trùng trong mảng C:

2 4 6 7 8 9 

2 6 7 

7

Tổng kết

Trên đây Kiyoshi đã hướng dẫn bạn cách xoá phần tử trùng trong mảng C rồi. Để nắm rõ nội dung bài học hơn, bạn hãy thực hành viết lại các ví dụ của ngày hôm nay nhé.

Và hãy cùng tìm hiểu những kiến thức sâu hơn về C trong các bài học tiếp theo.

mtoplist