Bài giảng Tin học đại cương - Bài 8: Mảng và xâu kí tự

TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI

VIỆN CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG

TIN HỌC ĐẠI CƯƠNG

Bài 8. Mảng và xâu kí tự

Nội dung

1. Mảng

2. Con trỏ

3. Xâu kí tự

2

1

Nội dung

1. Mảng

1.1. Khái niệm mảng

1.2. Khai báo và sử dụng mảng

1.3. Các thao tác cơ bản trên mảng

1.4. Tìm kiếm trên mảng

1.5. Sắp xếp trên mảng

2. Con trỏ

3. Xâu kí tự

3

1.1. Khái niệm mảng

• Tập hợp hữu hạn các phần tử cùng kiểu,

lưu trữ kế tiếp nhau trong bộ nhớ

• Các phần tử trong mảng có cùng tên (là

tên mảng) nhưng phân biệt với nhau ở chỉ

số cho biết vị trí của nó trong mảng

• Ví dụ:

– Bảng điểm của sinh viên

– Vector

– Ma trận

4

2

1.2. Khai báo và sử dụng mảng

• Khai báo mảng (một chiều)

KieuDuLieu tenMang [kích_thước];

• Trong đó

– KieuDuLieu: kiểu dữ liệu của các phần tử

trong mảng

– tenMang: tên của mảng

– kích_thước: số phần tử trong mảng

• Ví dụ

int mangNguyen[10]; // khai báo mảng 10

phần tử có kiểu dữ liệu int

5

1.2. Khai báo và sử dụng mảng

• Cấp phát bộ nhớ

– Các phần tử trong mảng được cấp phát các ô

nhớ kế tiếp nhau trong bộ nhớ

– Biến mảng lưu trữ địa chỉ ô nhớ đầu tiên

trong vùng nhớ được cấp phát

• Ngôn ngữ C đánh chỉ số các phần tử trong

mảng bắt đầu từ 0

– Phần tử thứ i trong mangNguyen được xác

định bởi mangNguyen [i-1]

mangNguyen[0] mangNguyen[1] ………..

mangNguyen[9]

mangNguyen

6

3

1.2. Khai báo và sử dụng mảng

• Khai báo mảng nhiều chiều

KieuDuLieu tenMang[size₁][size₂]…[size_k];

Trong đó

• size_ilà kích thước chiều thứ i của mảng

• Mảng một chiều và mảng nhiều chiều

– Mỗi phần tử của mảng cũng là một mảng

=> mảng nhiều chiều

• Ví dụ

– int a[6][5] ; //mảng 2 chiều

– int b[3][4][5]; // mảng 3 chiều

7

1.2. Khai báo và sử dụng mảng

• Sử dụng mảng

– Truy cập vào phần tử thông qua tên mảng và

chỉ số của phần tử trong mảng

tenMang[chỉ_số_phần_tử]

– Chú ý: chỉ số bắt đầu từ 0

• Ví dụ

– int a[4];

– phần tử đầu tiên (thứ nhất) của mảng: a[0]

– phần tử cuối cùng (thứ tư) của mảng: a[3]

– a[i]: là phần tử thứ i+1 của a

8

4

1.2. Khai báo và sử dụng mảng

• Ví dụ (tiếp)

– int b[3][4];

– phần tử đầu tiên của mảng: b[0] là một mảng

một chiều

– phần tử đầu tiên của mảng b[0]: b[0][0]

– b[i][j]: là phần tử thứ j+1 của b[i], b[i] là phần

tử thứ i+1 của b

9

Khai báo hằng số có kiểu mảng

• Sử dụng #define

#define TEN_MANG {Giá_trị_1, Giá_trị_2,... Giá_trị_n}

– Lưu ý: không thể truy cập vào phần tử của

mảng

• Sử dụng từ khóa const

const KieuDuLieu TEN_MANG[Kích_thước] = {Giá trị_1,

Giá trị_2, ..., Giá_trị_n};

Lưu ý:

– Nếu không khai báo Kích_thướcthì kích thước của

mảng là số lượng giá trị sử dụng khi khai báo

– Nếu số lượng giá trị nhỏ hơn Kích_thướcmảng, các

phần tử không được gán sẽ nhận giá trị 0

10

5

Khai báo hằng số có kiểu mảng – Ví dụ

const int CONST_ARR1[5] = {1,2,3,4,5}

1

2

3

4

5

CONST_ARR1:

const int CONST_ARR2[ ] = {1,2,3,4}

1

2

3

4

CONST_ARR2:

const int CONST_ARR3[5] = {1,2,3}

1

2

3

0

CONST_ARR23:

11

1.3. Các thao tác cơ bản trên mảng

a. Nhập dữ liệu cho mảng

• Khởi tạo giá trị cho mảng ngay khi khai

báo

– int a[4] = {1,4,6,2};

– int b[2][3]={ {1,2,3}, {4,5,6} }:

– Số lượng giá trị khởi tạo không được lớn hơn

số lượng phần tử trong mảng

– Nếu số lượng này nhỏ hơn, các phần tử còn

lại được khởi tạo giá trị 0

12

6

1.3. Các thao tác cơ bản trên mảng

a. Nhập dữ liệu cho mảng

– Có thể xác định kích thước mảng thông qua

số giá trị khởi tạo nếu để trống kích thước

mảng

– int array1 [8] = {2, 4, 6, 8, 10, 12, 14, 16};

– int array2 [] = {2, 4, 6, 8, 10, 12, 14, 16};

13

1.3. Các thao tác cơ bản trên mảng

a. Nhập dữ liệu cho mảng

• Nhập dữ liệu từ bàn phím bằng hàm scanf

– int a[10];

– Nhập dữ liệu cho a[1]: scanf(“%d”, & a[1]);

– Nhập dữ liệu cho toàn bộ phần tử của mảng a

=> Sử dụng vòng lặp for

• Lưu ý

– Tên mảng là một hằng (hằng con trỏ) do đó

không thể thực hiện phép toán với tên mảng

như phép gán sau khi đã khai báo

14

7

1.3. Các thao tác cơ bản trên mảng

#include <stdio.h>

#define MONTHS 12

int main(){

int rainfall[MONTHS], i;

for ( i=0; i < MONTHS; i++ ){

printf(“Nhap vao phan tu thu

%d: “, i+1);

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

}

return 0;

}

15

1.3. Các thao tác cơ bản trên mảng

a. Nhập dữ liệu cho mảng

• Lưu ý

– Nếu số phần tử của mảng được nhập từ bàn

phím và chỉ biết trước số phần tử tối đa tối đa

=> khai báo mảng với kích thước tối đa và sử

dụng biến lưu số phần tử thực sự của mảng.

– Ví dụ: Khai báo mảng số nguyên a có tối đa

100 phần tử. Nhập từ bàn phím số phần tử

trong mảng và giá trị các phần tử đó….

16

8

1.3. Các thao tác cơ bản trên mảng

#include<stdio.h>

#include<conio.h>

int main(){

int a[100];

int n, i;

do{

printf(“\n Cho biet so phan tu cua mang: “);

scanf(“%d”,&n);

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

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

printf(“a[%d] = ", i);

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

}

getch();

return 0;

17

}

1.3. Các thao tác cơ bản trên mảng

b. Hiển thị dữ liệu trong mảng

– Dùng hàm printf()

– Để hiển thị tất cả các phần tử: dùng vòng for

• Ví dụ

– Hiển thị một phần tử bất kì

– Hiển thị tất cả các phần tử, mỗi phần tử trên

một dòng

– Hiển thị tất cả các phần tử trên một dòng,

cách nhau 2 vị trí

– Hiển thị từng k phần tử trên một dòng

18

9

1.3. Các thao tác cơ bản trên mảng

#include <stdio.h>

#define MONTHS 12

int main(){

int rainfall[MONTHS], i;

for ( i=0; i < MONTHS; i++ ){

printf(“Nhap vao phan tu thu

%d: “, i+1);

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

}

for ( i=0; i < MONTHS; i++ )

printf( "%2d ” , rainfall[i]);

printf("\n");

return 0;

}

19

1.3. Các thao tác cơ bản trên mảng

c. Tìm giá trị lớn nhất, nhỏ nhất

• Tìm giá trị lớn nhất

– Giả sử phần tử đó là phần tử đầu tiên

– Lần lượt so sánh với các phần tử còn lại

– Nếu lớn hơn hoặc bằng => so sánh tiếp

– Nếu nhỏ hơn => coi phần tử này là phần tử

lớn nhất và tiếp tục so sánh

– Cách làm?

• Tìm giá trị nhỏ nhất: tương tự

20

10

1.4. Tìm kiếm trên mảng

• Bài toán

– Cho mảng dữ liệu a và một giá trị k

– Tìm các phần tử trong mảng a có giá trị bằng

(giống) với k. Nếu có in ra vị trí (chỉ số) các

phần tử này. Ngược lại thông báo không tìm

thấy

• Cách làm

– Duyệt toàn bộ các phần tử trong mảng

– Nếu a[i] bằng (giống) k thì lưu lại chỉ số i

– Sử dụng một biến để xác định tìm thấy hay

không tìm thấy

21

1.4. Tìm kiếm trên mảng

• Phân tích

– Duyệt toàn bộ các phần tử

• Vòng lặp for (while, do while)

– Lưu lại i nếu a[i] bằng (giống) k

• Sử dụng mảng lưu chỉ số

– Biến xác định tìm thấy hay không tìm thấy

• Biến nhận giá trị 0 hoặc 1

• Biến nhận giá trị 0 hoặc >=1 (tìm thấy thì tăng giá

trị)

22

11

1.4. Tìm kiếm trên mảng

#include <stdio.h>

#include <conio.h>

int main(){

int a[100], chi_so[100];

int n;//n la số phần tử trong mảng

int i, k, kiem_tra;

printf(“Nhap vao so phan tu cua mang:”);

scanf(“%d”,&n);

printf(“Nhap vao giá trị tim kiem:”);

scanf(“%d”,&k);

23

1.4. Tìm kiếm trên mảng

kiem_tra = 0;

// Duyệt qua tất cả các phần tử

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

if(a[i] == k)

{

chi_so[kiem_tra] = i;

kiem_tra ++;

}

24

12

1.4. Tìm kiếm trên mảng

if(kiem_tra > 0){

printf(“Trong mang co %d phan tu co

gia tri bang %d”,kiem_tra,k);

printf(“\nChi so cua cac phan tula:“);

for(i = 0;i < kiem_tra;i++)

printf(“%3d”,chi_so[i]);

} else

printf(“\n Trong mang khong co phan

tu nao co gia tri bang %d”,k);

getch();

return 0;

25

}

1.5. Sắp xếp mảng

• Bài toán

– Cho mảng a gồm n phần tử. Sắp xếp các

phần tử của mảng a theo thứ tự tăng

dần/giảm dần

26

13

1.5. Sắp xếp mảng

• Giải thuật sắp xếp

– Sắp xếp thêm dần (insertion sort)

– Sắp xếp lựa chọn (selection sort)

– Sắp xếp nổi bọt (bubble sort)

– Sắp xếp vun đống (heap sort)

– Sắp xếp nhanh (quick sort)

– Sắp xếp trộn (merge sort)

– ….

27

Giải thuật sắp xếp lựa chọn

Ý tưởng

• Lần sắp xếp thứ 1:

– Đoạn đã được sắp xếp: chưa có phần tử nào

– Đoạn chưa được sắp xếp: có n phần tử tử a₀, a₁,…,

a_n-1

– So sánh a₀với a_j(1≤ j ≤ n-1). Nếu a₀> a_jthì đổi chỗ

– Sau lượt sắp xếp này a₀đã đúng thứ tự

• Lần sắp xếp thứ 2:

– Đoạn đã được sắp xếp: a₀

– Đoạn chưa được sắp xếp: a₁, a₂, …, a_n-1

– So sánh a₁với a_j(2 ≤ j ≤ n-1). Nếu a₁> a_jthì đổi chỗ

– Sau lượt sắp xếp này a₁đã đúng thứ tự

28

14

Giải thuật sắp xếp lựa chọn

• Lần sắp xếp thứ i:

– Đoạn đã được sắp xếp: a_0,a₁,…,a_i-2

– Đoạn chưa được sắp xếp: a_i-1, a_i, …, a_n-1

– So sánh a_i-1với a_j(i ≤ j ≤ n-1). Nếu a_i> a_jthì đổi chỗ

– Sau lượt sắp xếp này a_i-1đã đúng thứ tự

• Thuật toán dừng khi dãy chưa được sắp

xếp chỉ có 1 phần tử

29

1.5. Sắp xếp mảng

• A = { 12, 5, 3, 4 };

Lượt 1

Lượt 2

Lượt 3

12

5

3

12

3

4

3

4

3

4

5

4

12

5

12

30

15

Lưu đồ thuật toán sắp xếp lựa chọn

31

1.5. Sắp xếp mảng

//Khai bao cac bien

int a[100];

int i, j, tmp;

//Sap xep

for (i = 0; i < n-1; i++)

for (j = i+1; j <n ; j++)

if ( a[i] > a[j]){

tmp = a[i];

a[i]= a[j];

a[j]= tmp;

32

}

16

Nội dung

1. Mảng

2. Con trỏ

2.1. Khái niệm, khai báo con trỏ

2.2. Toán tử địa chỉ, toán tử nội dung

2.3. Phép toán trên con trỏ

2.4. Con trỏ và mảng

3. Xâu kí tự

33

2.1. Khái niệm, khai báo con trỏ

• Địa chỉ và giá trị của một biến

– Bộ nhớ như một dãy các byte nhớ.

– Các byte nhớ được xác định một cách duy

nhất qua một địa chỉ.

– Biến được lưu trong bộ nhớ.

– Khi khai báo một biến

• Chương trình dịch sẽ cấp phát cho biến đó một số ô nhớ liên

tiếp đủ để chứa nội dung của biến. Ví dụ một biến số nguyên

(int) được cấp phát 2 byte.

• Địa chỉ của một biến chính là địa chỉ của byte đầu tiên trong

số đó.

34

17

Địa chỉ và giá trị của một biến (tiếp)

• Một biến luôn có 2 đặc tính:

– Địa chỉ của biến

– Giá trị của biến

• Ví dụ

int i, j;

i = 3;

Biến

Địa chỉ

FFEC

Giá trị

i

j

3

4

FFEE

j = i + 1;

35

Khái niệm và khai báo con trỏ

• Con trỏ là một biến mà giá trị của nó là địa chỉ

của một vùng nhớ

• Khai báo con trỏ:

KieuDuLieu *tenBienConTro;

• Một con trỏ chỉ có thể trỏ tới một đối tượng cùng

kiểu.

• Ví dụ:

int i = 3;

int *p;

Biến

Địa chỉ

FFEC

Giá trị

i

p

3

p = &i;

FFEE

FFEC

36

18

2.2. Toán tử địa chỉ và toán tử nội dung

• Toán tử &: Trả về địa chỉ của biến.

• Toán tử *: Trả về giá trị chứa trong vùng nhớ

được trỏ bởi con trỏ.

• Cả hai toán tử * và & có độ ưu tiên cao hơn tất

cả các toán tử số học ngoại trừ toán tử đảo dấu.

• Ví dụ:

int main()

{

int i = 3, *p;

p = &i;

printf("p = %X và &i = %X \n", p, &i);

printf("*p = %d và i = %d \n", *p, i);

getch();

return 0;

37

}

2.2. Toán tử địa chỉ và toán tử nội dung

• Một biến con trỏ có thể được gán bởi:

• Địa chỉ của một biến khác:

bienConTro = &bienKhac;

• Giá trị của một con trỏ khác (tốt nhất là cùng

kiểu):

bienConTro1 = bienConTro2;

• Giá trị NULL (số 0):

bienConTro = 0;// hoặc bienConTro = NULL

• Gán giá trị cho biến con trỏ:

*bienConTro= GIA_TRI;

38

19

Ví dụ 1

Biến Địa chỉ

Giá trị

int main()

{

i

FFEC

FFEE

FFDA

FFDC

3

6

j

int i = 3, j = 6;

P1

p2

FFEC

FFEE

int *p1, *p2;

p1 = &i;

p2 = &j;

*p1 = *p2;

getch();

Biến Địa chỉ

Giá trị

i

FFEC

FFEE

FFDA

FFDC

6

return 0;

j

6

}

P1

p2

FFEC

FFEE

39

Ví dụ 1

Biến Địa chỉ

Giá trị

int main()

{

i

FFEC

FFEE

FFDA

FFDC

3

j

6

int i = 3, j = 6;

P1

p2

FFEC

FFEE

int *p1, *p2;

p1 = &i;

p2 = &j;

*p1 = *p2;

getch();

Biến Địa chỉ

Giá trị

i

FFEC

FFEE

FFDA

FFDC

3

return 0;

j

6

}

P1

p2

FFEE

40

20

Bài giảng Tin học đại cương - Bài 8: Mảng và xâu kí tự - Bùi Trọng Tùng