Mảng 1 chiều

Cấu trúc dữ liệu | Học C/C++ | Featured

Bài 41. Mảng 1 chiều trong C

ByNguyễn Văn Hiếu 25/08/201904/12/2020

This entry is part 39 of 69 in the series Học C Không Khó

Mảng 1 chiều là cấu trúc dữ liệu đầu tiên và cũng là cấu trúc dữ liệu đơn giản & phổ biến nhất. Mảng 1 chiều hay tiếng anh là One-Dimensional Array là bài viết đầu tiên trong loạt bài viết hướng dẫn về cấu trúc dữ liệu tại Blog Nguyenvanhieu.vn. Hi vọng series này cung cấp cho các bạn những kiến thức bổ ích về phần kiến thức cấu trúc dữ liệu. Bài viết hôm nay sẽ trình bày về mảng 1 chiều.

Sau bài học này, bạn có thể ghé thăm bài học “Bài tập mảng 1 chiều có lời giải” để luyện tập kiến thức nhé. Hoặc bạn có thể tự luyện tập trực tuyến nhiều bài tập khác website Luyện Code Online.

NỘI DUNG BÀI VIẾT

1. Lý thuyết về mảng 1 chiều

Mảng là một tập hợp tuần tự các phần tử có cùng kiểu dữ liệu và các phần tử được lưu trữ trong một dãy các ô nhớ liên tục trên bộ nhớ. Các phần tử của mảng được truy cập bằng cách sử dụng “chỉ số”. Mảng có kích thước N sẽ có chỉ số từ 0 tới N – 1.

Ví dụ, với N = 5, khi đó chỉ số mảng(tiếng anh là index) sẽ có giá trị từ 0 tới 4(5-1) tương ứng với 5 phần tử. Các phần tử trong mảng được truy cập bằng cách sử dụng <em>array_name[index].

Mảng 1 chiều — Hình ảnh mô phỏng cho cấu trúc mảng 1 chiều

Hãy xem xét mảng sau, kích thước của mảng là 5. Nếu bạn muốn truy cập giá trị 12, bạn có thể truy cập bằng cách gọi arr[1].

2. Khai báo mảng 1 chiều

Cú pháp khai báo mảng 1 chiều khác nhau với từng ngôn ngữ lập trình.

Chẳng hạn, trong C/C++, việc khai báo mảng cần 2 tham số sau:

Kích thước của mảng: Việc này xác định số lượng phần tử có thể được lưu trữ trong mảng.
Kiểu dữ liệu của mảng: Việc này chỉ định kiểu dữ liệu của các phần tử trong mảng; là số nguyên, số thực, ký tự hay là kiểu dữ liệu nào đó.

Một ví dụ khai báo mảng trong C/C++:

int arr[5];

1	int arr[5];

Đây là cách khai báo mảng tĩnh; cách khác là khai báo động kích thước vừa đủ dùng. Đối với mảng động, kích thước mảng sẽ tăng lên khi số lượng phần tử mảng tăng lên vượt qua kích thước cũ.

3. Khởi tạo mảng 1 chiều

Mảng có thể được khởi tạo ngay tại thời điểm khai báo mảng hoặc khởi tạo sau khi khai báo.

Cú pháp để khởi tạo mảng trong khi khai báo là:

type arr[size] = {elements}

1	type arr[size] = {elements}

Một ví dụ khai báo kèm khởi tạo mảng trong C/C++:

int arr[5] = {4, 12, 7, 15, 9};

1	int arr[5] = {4, 12, 7, 15, 9};

Mảng cũng có thể được khởi tạo sau khi khai báo xong, bằng cách gán giá trị cho từng phần tử của mảng sử dụng chỉ số:

type arr[size]
arr[index] = 12

1 2	type arr[size] arr[index] = 12

Ví dụ trên C/C++:

int arr[5];
arr[0] = 4;
arr[1] = 12;

1

2

3

int arr[5];

arr[0] = 4;

arr[1] = 12;

4. Các thao tác với mảng 1 chiều

Một thao tác đơn giản nhất và hay sử dụng nhất đó là việc lặp qua tất cả các phần tử của mảng theo cách sau:

type arr[size] = {elements}
for idx from 0 to size
    print arr[idx]

1

2

3

type arr[size] = {elements}

for idx from 0 to size

print arr[idx]

Một ví dụ trên ngôn ngữ C:

#include <stdio.h>

int main()
{
    // Array declaration and initialization
    int arr[5] = {4, 12, 7, 15, 9};
    // Iterate over the array
    for(int idx=0; idx<5; idx++)
    {
        // Print out each element in a new line
        printf("%d\n", arr[idx]);
    }
    return 0;
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

#include <stdio.h>

int main()

{

// Array declaration and initialization

int arr[5] = {4, 12, 7, 15, 9};

// Iterate over the array

for(int idx=0; idx<5; idx++)

{

// Print out each element in a new line

printf("%d\n", arr[idx]);

}

return 0;

}

Để cho code chúng ta được tối ưu hơn, sau đây tôi xin chia mỗi chức năng thành 1 hàm riêng biệt:

4.1. Thao tác nhập mảng 1 chiều

Hàm này nhận vào các đối số là mảng kiểu nguyên a, và số lượng phần tử n. Hàm không trả về giá trị gì nên có kiểu là void.

void NhapMang(int a[], int n){
    for(int i = 0;i < n; ++i){
        printf("\nNhap phan tu a[%d] = ", i);
        scanf("%d", &a[i]);
    }
}

1

2

3

4

5

6

void NhapMang(int a[], int n){

for(int i = 0;i < n; ++i){

printf("\nNhap phan tu a[%d] = ", i);

scanf("%d", &a[i]);

}

}

4.2. Thao tác xuất mảng 1 chiều

Tương tự như hàm nhập, hàm XuatMang cũng nhận vào mảng kiểu nguyên a và số lượng phần tử n. Hàm có giá trị trả về là kiểu void.

void XuatMang(int a[], int n){
    for(int i = 0;i < n; ++i){
        printf("\nPhan tu a[%d] = %d", i, a[i]);
    }
}

1

2

3

4

5

void XuatMang(int a[], int n){

for(int i = 0;i < n; ++i){

printf("\nPhan tu a[%d] = %d", i, a[i]);

}

}

4.3. Chức năng tìm kiếm trong mảng 1 chiều

Vẫn nhận vào các đối số như 2 hàm nhập và xuất, và nhận thêm một đối số khác nữa là giá trị cần tìm kiếm v. Tuy nhiên, hàm này sẽ trả về chỉ số đầu tiên mà giá trị tại đó giá trị bằng với v. Nếu không có giá trị nào thỏa mãn, hàm trả về giá trị -1.

int TimKiem(int a[], int n, int v){
    for(int i = 0;i < n; ++i){
        if(a[i] == v){
            return i;
        }
    }
    return -1;
}

1

2

3

4

5

6

7

8

int TimKiem(int a[], int n, int v){

for(int i = 0;i < n; ++i){

if(a[i] == v){

return i;

}

}

return -1;

}

Đây là một hàm thực hiện tìm kiếm tuyến tính có độ phức tạp O(n). Bằng cách duyệt qua từng phần tử của mảng để kiểm tra.

Full source code và lời gọi hàm trong hàm main:

#include <stdio.h>

const int MAX = 100;


void NhapMang(int a[], int n){
    for(int i = 0;i < n; ++i){
        printf("\nNhap phan tu a[%d] = ", i);
        scanf("%d", &a[i]);
    }
}

void XuatMang(int a[], int n){
    for(int i = 0;i < n; ++i){
        printf("\nPhan tu a[%d] = %d", i, a[i]);
    }
}

int TimKiem(int a[], int n, int v){
    for(int i = 0;i < n; ++i){
        if(a[i] == v){
            return i;
        }
    }
    return -1;
}

int main(){
    int arr[MAX];
    int n;
    printf("\nNhap so luong phan tu: ");
    do{
        scanf("%d", &n);
        if(n <= 0 || n > MAX){
            printf("\nNhap lai so luong phan tu: ");
        }
    }while(n <= 0 || n > MAX);
    printf("\n======NHAP MANG=====\n");
    NhapMang(arr, n);
    printf("\n======XUAT MANG=====\n");
    XuatMang(arr, n);
    printf("\n======TIM KIEM======\n");
    int v;
    printf("\nNhap vao gia tri can tim: ");
    scanf("%d", &v);
    printf("\nTim thay so %d tai chi so %d!", v, TimKiem(arr, n, v));
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

#include <stdio.h>

const int MAX = 100;

void NhapMang(int a[], int n){

for(int i = 0;i < n; ++i){

printf("\nNhap phan tu a[%d] = ", i);

scanf("%d", &a[i]);

}

}

void XuatMang(int a[], int n){

for(int i = 0;i < n; ++i){

printf("\nPhan tu a[%d] = %d", i, a[i]);

}

}

int TimKiem(int a[], int n, int v){

for(int i = 0;i < n; ++i){

if(a[i] == v){

return i;

}

}

return -1;

}

int main(){

int arr[MAX];

int n;

printf("\nNhap so luong phan tu: ");

do{

scanf("%d", &n);

if(n <= 0 || n > MAX){

printf("\nNhap lai so luong phan tu: ");

}

}while(n <= 0 || n > MAX);

printf("\n======NHAP MANG=====\n");

NhapMang(arr, n);

printf("\n======XUAT MANG=====\n");

XuatMang(arr, n);

printf("\n======TIM KIEM======\n");

int v;

printf("\nNhap vao gia tri can tim: ");

scanf("%d", &v);

printf("\nTim thay so %d tai chi so %d!", v, TimKiem(arr, n, v));

}

Chạy thử chương trình:

Nhap so luong phan tu: 5

======NHAP MANG=====

Nhap phan tu a[0] = 1

Nhap phan tu a[1] = 2

Nhap phan tu a[2] = 3

Nhap phan tu a[3] = 4

Nhap phan tu a[4] = 5

======XUAT MANG=====

Phan tu a[0] = 1
Phan tu a[1] = 2
Phan tu a[2] = 3
Phan tu a[3] = 4
Phan tu a[4] = 5
======TIM KIEM======

Nhap vao gia tri can tim: 2

Tim thay so 2 tai chi so 1!

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

Nhap so luong phan tu: 5

======NHAP MANG=====

Nhap phan tu a[0] = 1

Nhap phan tu a[1] = 2

Nhap phan tu a[2] = 3

Nhap phan tu a[3] = 4

Nhap phan tu a[4] = 5

======XUAT MANG=====

Phan tu a[0] = 1

Phan tu a[1] = 2

Phan tu a[2] = 3

Phan tu a[3] = 4

Phan tu a[4] = 5

======TIM KIEM======

Nhap vao gia tri can tim: 2

Tim thay so 2 tai chi so 1!

5. Bài tập thực hành

Bài tập mảng cơ bản

Cho kích thước và các phần tử của mảng A. Hãy in các phần tử của mảng A theo thứ tự ngược lại.

Input:

Dòng đầu tiên là số N – số lượng phần tử của mảng A
N dòng tiếp theo, mỗi dòng là một số nguyên, tương ứng với phần tử thứ i của mảng A, 0 <= i < N.

Output:

In ra tất cả các phần tử của mảng A theo thứ tự ngược lại, mỗi phần tử trên một dòng.

SAMPLE INPUT

SAMPLE OUTPUT

5

4

1

2

7

15

9

9

15

7

2

1

4

5

Ràng buộc:

1 <= N <= 100
0 <= A[i] <= 1000

Bài tập mảng nâng cao

Một số vấn đề có vẻ khó nhưng thực chất chúng rất đơn giản. Hôm này Admin Hiếu gặp khó khăn với bài toán truy vấn phạm vi. Anh ấy có một mảng 1 chiều cứa các giá trị nhị phân 0 và 1. Có 2 kiểu truy vấn:

0 L R: Kiểm tra số được hình thành từ L tới R là số chẵn hay lẻ. Số được hình thành từ L tới R là giá trị thập phân của các số nhị phân từ L tới R kết hợp lại.

1 X: Đổi giá trị nhị phân tại chỉ số thứ X.

Input:

Dòng đầu tiên chứa 2 số N và Q. Dòng tiếp theo chứa N số 0 hoặc 1 cách nhau bởi 1 dấu cách. Q dòng tiếp theo, mỗi dòng là 1 truy vấn.

Ouput:

Với các truy vấn có dạng 0 L R in ra giá trị thập phân được tạo thành từ L tới R là chẵn hay lẻ. Chẵn thì in ra “EVEN“, lẻ thì in ra “ODD” không kèm dấu nháy.

Ràng buộc:

1<= N <= 10^6
0<= L <= R < N
1 <= Q <= 10^6

SAMPLE INPUT	SAMPLE OUTPUT
5 2 1 0 1 1 0 1 2 0 1 4	EVEN

Giải thích: Truy vấn đầu tiên là 1 2, do đó ta đổi giá trị tại chỉ số mảng 2 từ 1 thành 0, khi đó mảng mới là: 1 0 0 1 0. Truy vấn thứ 2 là 0 1 4, khi đó 0110₂ = 02^0 + 12^1 + 1*2^2 = 6₁₀ là số chẵn; Do đó, đáp án là EVEN.

Lưu ý: Các bạn nộp bài tập xuống mục bình luận của bài học. Admin sẽ chữa bài và đánh giá lời giải giúp các bạn.

Subscribe

21 Bình luận

Inline Feedbacks

View all comments

21

0

Would love your thoughts, please comment.x

()