Bài giảng Kỹ thuật lập trình nâng cao Chương 2: ThS. Dương Thành Phết

TRƯỜNG CAO ĐẲNG CNTT TP.HCM KHOA CÔNG NGHỆ THÔNG TIN

KỸ THUẬT LẬP TRÌNH NÂNG CAO

Chương 2 KIỂU DỮ LIỆU CÓ CẤU TRÚC

Giảng Viên: ThS. Dương Thành Phết Email: phetcm@gmail.com Website: http://www.thayphet.net Tel: 0918158670 – facebook.com/DuongThanhPhet

NỘI DUNG

1. Kiểu dữ liệu mảng 1 chiều

2. Các thao tác trên mảng 1 chiều

3. Mảng 2 chiều

4. Kiểu chuổi ký tự

5. Kiểu cấu trúc – Mảng cấu trúc

6. Kiểu tập tin - File

2 1. KIỂU DỮ LIỆU MẢNG 1 CHIỀU

 Mảng thực chất là một biến bao gồm nhiều biến thành

1.1 Khái niệm

phần được cấp phát bộ nhớ liên tục.

 Các thành phần của mảng là tập hợp các biến có cùng kiểu dữ liệu và cùng tên. Do đó để truy xuất các biến thành phần, ta dùng cơ chế chỉ mục (Vị trí).

Giá trị

9 3

Vị trí

1. KIỂU DỮ LIỆU MẢNG 1 CHIỀU

1.2. Khai báo

< Kiểu dữ liệu > < Tên mảng > [ < Số p.tử tối đa của mảng> ] ;

int a[100]; //Khai bao mang so nguyen a gom 100 phan tu float b[50]; //Khai bao mang so thuc b gom 50 phan tu char str[30]; //Khai bao mang ky tu str gom 30 ky tu

4 1. KIỂU DỮ LIỆU MẢNG 1 CHIỀU

int a[5] = {3, 6, 8, 1, 12};  a[0] = 3, a[1] = 6, a[2] = 8, … int a[10] = {0};  a[0]=a[1]=a[2]=a[3]=…=a[9]=0

1.3. Gán giá trị ban đầu cho mảng

5 1. KIỂU DỮ LIỆU MẢNG 1 CHIỀU

Vị trí

A[0] A[1] A[2] A[3] A[4]

1.4. Truy xuất

6 2. CÁC THAO TÁC TRÊN MẢNG 1 CHIỀU

1. Nhập/Xuất mảng

void NhapMang (int a[], int n){ for (int i = 0; i < n; i ++){ } }

cout<<“Nhap phan tu thu “<>a[i];

cout<

void XuatMang (int a[], int n){ for (int i = 0; i < n; i ++) }

7 2. CÁC THAO TÁC TRÊN MẢNG 1 CHIỀU

int a[MAX] , n;

void main ( ){ cout<<“Nhap kich thuoc mang: “; cin>>n; NhapMang (a,n); cout<<“Cac gia tri cua mang vua nhap: ”<

8 2. CÁC THAO TÁC TRÊN MẢNG 1 CHIỀU

Xuất các phần tử thỏa điều kiện

for (int i = 0; i

Mẫu 1: void LietKeXXX(int a[], int n){ }

if (a[i] thỏa điều kiện so với x)

for (int i = 0; i

9 Mẫu 2: void LietKeXXX(int a[], int n, int x){ }

2. CÁC THAO TÁC TRÊN MẢNG 1 CHIỀU

Ví dụ 1: Liệt kê các phần tử có giá trị chẵn trong mảng

cout<

void LietKeChan(int a[], int n){ }

for (int i = 0; i

10 2. CÁC THAO TÁC TRÊN MẢNG 1 CHIỀU

Ví dụ 2: Liệt kê các phần tử có giá trị lớn hơn x trong mảng

cout<

void LietKeLonHonX(int a[], int n, int x){ }

for (int i = 0; i x)

11 2. CÁC THAO TÁC TRÊN MẢNG 1 CHIỀU

int d = 0; for (int i = 0; i

2.2. Đếm Mẫu 1: int DemXXX(int a[], int n){ if (a[i] thỏa điều kiện) return d; }

d++;

int d = 0; for (int i = 0; i

12

Mẫu 2: int DemXXX(int a[], int n, int x){ if (a[i] thỏa điều kiện so với x) return d; }

2. CÁC THAO TÁC TRÊN MẢNG 1 CHIỀU Ví dụ 1: Đếm các phần tử có giá trị là số nguyên tố

int d = 0;

bool LaSNT(int k) { int d = 0; for (int i = 1; i <= k; i++) if (k % i == 0) d++; return (d == 2); } int DemSNT(int a[], int n){ for (int i = 0; i

2. CÁC THAO TÁC TRÊN MẢNG 1 CHIỀU

int DemNhoHonX(int a[], int n, int x){ int d = 0; for (int i = 0; i

Ví dụ 2: Đếm các phần tử có trong mảng mà giá trị nhỏ hơn x

2. CÁC THAO TÁC TRÊN MẢNG 1 CHIỀU

int vtmax = 0; for (int i = 0; i < n; i++) if (a[i] > a[vtmax]) vtmax = i;

2.3. Tìm kiếm

Mẫu 1: Tìm và trả về vị trí phần tử có giá trị lớn nhất int TimVTMax(int a[], int n){ return vtmax; }

return i;

15 Mẫu 2: Tìm vị trí phần tử có giá trị x (nếu x không xuất hiện trong mảng trả về -1) int TimVTX(int a[], int n, int x){ for (int i = 0; i < n; i++) if (a[i] == x) return -1; }

2. CÁC THAO TÁC TRÊN MẢNG 1 CHIỀU

2.4. Kiểm tra mảng có thỏa đk cho trước

Trường hợp 1: Kiểm tra tồn tại một phần tử trong mảng thỏa điều kiện nào đó cho trước  tìm phần tử thỏa điều kiện để kết luận.

return true;

for (int i = 0; i

Mẫu 1: bool KiemTraTonTaiXXX(int a[], int n){ return false; }

16 2. CÁC THAO TÁC TRÊN MẢNG 1 CHIỀU

Trường hợp 2: Kiểm tra tất cả các phần tử thỏa điều kiện nào đó cho trước  tìm phần tử không thỏa điều kiện để kết luận mảng không thỏa điều kiện.

for (int i = 0; i

Mẫu 2: bool KiemTraXXX(int a[], int n){ return true; }

17 2. CÁC THAO TÁC TRÊN MẢNG 1 CHIỀU

bool KiemTraTonTaiLe(int a[], int n){ foreach (int giatri in a) if (giatri % 2 != 0) return true; return false; }

Ví dụ 1: Kiểm tra xem mảng có tồn tại số lẻ không?

18 2. CÁC THAO TÁC TRÊN MẢNG 1 CHIỀU

Ví dụ 2: Kiểm tra xem mảng có toàn giá trị âm không? (true: có/ false: không)

return false;

bool KiemTraToanAm(int a[], int n){ for (int i = 0; i= 0) return true; }

19 2. CÁC THAO TÁC TRÊN MẢNG 1 CHIỀU

2.5. Tính toán các phần tử trong mảng

int s = 0; for (int i = 0; i

Mẫu tính tổng: int TongXXX(int a[], int n){ if (a[i] thỏa điều kiện) s += a[i]; return s; }

20 2. CÁC THAO TÁC TRÊN MẢNG 1 CHIỀU

int TongLe(int a[], int n) { int s = 0; for (int i = 0; i

Ví dụ: Tính tổng các phần tử có giá trị lẻ trong mảng

21 2. CÁC THAO TÁC TRÊN MẢNG 1 CHIỀU

int s = 0; int d = 0; for (int i = 0; i

Mẫu tính trung bình: float TrungBinhXXX(int a[], int n){ return 0; return (float) s / d; }

22 2. CÁC THAO TÁC TRÊN MẢNG 1 CHIỀU

Ví dụ: Tính giá trị trung bình các phần tử có giá trị âm trong mảng

23

float TrungBinhAm(int a[], int n){ long s = 0; int d = 0; for (int i = 0; i

2. CÁC THAO TÁC TRÊN MẢNG 1 CHIỀU

2.6. Sắp xếp

Minh họa thuật toán

i=1

i=2 j=2

i=3 j=3

i=4 j=4

i=5 j=5

i=6 j=6

i=7 j=7

2 8 5 1 6 4 12

24 2. CÁC THAO TÁC TRÊN MẢNG 1 CHIỀU

HoanVi(a[i], a[j]);

int tam = a; a = b; b = tam;

for(int j = i+1; j < n; j ++) if (a[i] > a[j]) for (int i = 0; i < n-1; i ++)

Mẫu phương thức sắp thứ tự tăng: void SapTang(int a[], int n){ } void HoanVi(int &a, int &b){ }

25 3. MẢNG 2 CHIỀU

3.1 Giới thiệu

 Mảng hai chiều thực chất là mảng một chiều trong đó mỗi phần tử của mảng là một mảng một chiều, và được truy xuất bởi hai chỉ số dòng và cột.

 Từ khái niệm trên ta có thể đưa ra một khái niệm về mảng nhiều chiều như sau: mảng có từ hai chiều trở lên gọi là mảng nhiều chiều.

3. MẢNG 2 CHIỀU 3.2. Khai báo Cách 1:

int A[5][10]; // Khai báo mảng int gồm 5 dòng, 10 cột float b[7][8]; // Khai báo mảng float gồm 7 dòng, 8 cột

// Khai báo mảng động 2 chiều kiểu int

< Kiểu dữ liệu > < Tên mảng > [< Số dòng][]; Ví dụ: Cách 2 : < Kiểu dữ liệu > **; Ví dụ : int **A ; float **B ; // Khai báo mảng động 2 chiều kiểu float

3. MẢNG 2 CHIỀU

3.3. Truy xuất

Để truy xuất các thành phần của mảng hai chiều ta phải dựa vào chỉ số dòng và chỉ số cột.

Với các khai báo như trên ta có:

Ví dụ: int A[3][4] = { {2,3,9,4} , {5,6,7,6} , {2,9,4,7} };

A[0][0] = 2; A[0][1] = 3;

A[1][1] = 6; A[1][3] = 6;

3. MẢNG 2 CHIỀU

3.4. Các thao tác

 Nhập/ xuất

 Tìm kiếm

 Đếm

 Tính tổng/ trung bình

 Sắp xếp dòng/ cột

 Xóa dòng/ cột

 Chèn thêm dòng/ cột

3. MẢNG 2 CHIỀU

3.4. Ma trận vuông

 Số dòng = Số cột

 Đường chéo chính của ma trận vuông:

chỉ số dòng = chỉ số cột

 Đường chéo phụ của ma trận vuông:

chỉ số cột + chỉ số dòng = kích thước - 1

Chéo chính

Chéo phụ

4. CHUỖI KÝ TỰ

4.1. Giới thiệu

Chuỗi ký tự là một dãy các phần tử, mỗi phần tử có kiểu ký tự. Khai báo cách 1: char < Tên chuỗi > [ < Số ký tự tối đa của chuỗi > ] ; Ví dụ: char chuoi[25]; Khai báo 1 mảng kiểu ký tự tên là chuoi có 25 phần tử (lưu được 24 ký tự, ký tự 25 là ký tự kết thúc chuỗi „\0‟ )

Khai báo cách 2:

char *chuoi; Ví dụ :  Chuỗi ký tự không giới hạn chiều dài

char *< Tên chuỗi >;

4. CHUỖI KÝ TỰ

4.2. Nhập

cin.getline(chuoi, số ký tự tối đa);

Ví dụ: char *str; str = new char [30]; cin.getline(str, 30);

4. CHUỖI KÝ TỰ

4.3. Các hàm thư viện –

 Tính độ dài của chuỗi s

 Sao chép nội dung chuỗi nguồn vào chuỗi đích

strcpy(char đích[], char nguồn[]);

 Chép n ký tự từ chuỗi nguồn sang chuỗi đích. Nếu chiều dài nguồn < n thì hàm sẽ điền khoảng trắng cho đủ n ký tự vào đích

int strlen(char s[]);

strncpy(char đích[], char nguồn[], int n);

4. CHUỖI KÝ TỰ

 Nối chuỗi s2 vài chuỗi s1

 Nối n ký tự đầu tiên của chuỗi s2 vào chuỗi s1

strcat(char s1[],char s2[]);

 So sánh 2 chuỗi s1 và s2 theo nguyên tắc thứ tự.

strncat(char s1[],char s2[],int n);

Phân biệt chữ hoa và thường. Trả về:

0: nếu s1 bằng s2.

>0: nếu s1 lớn hơn s2.

int strcmp(char s1[],char s2[]);

<0: nếu s1 nhỏ hơn s2.

4. CHUỖI KÝ TỰ

 So sánh n ký tự đầu tiên của s1 và s2, giá trị trả về

tương tự hàm strcmp()

 So sánh chuỗi s1 và s2 nhưng không phân biệt hoa

int strncmp(char s1[],char s2[], int n);

thường, giá trị trả về tương tự hàm strcmp()

 So sánh n ký tự đầu tiên của s1 và s2 nhưng không phân biệt hoa thường, giá trị trả về tương tự hàm strcmp()

int strnicmp(char s1[],char s2[], int n);

int stricmp(char s1[],char s2[]);

4. CHUỖI KÝ TỰ

 Tìm sự xuất hiện đầu tiên của ký tư c trong chuỗi s.

Trả về:

NULL: nếu không có

char *strchr(char s[], char c);

 Tìm sự xuất hiện đầu tiên của chuỗi s2 trong chuỗi

Địa chỉ c: nếu tìm thấy

s1. Trả về:

NULL: nếu không có

char *strstr(char s1[], char s2[]);

Ngược lại: Địa chỉ bắt đầu chuỗi s2 trong s1

4. CHUỖI KÝ TỰ

Tách chuỗi: Nếu s2 có xuất hiện trong s1: Tách chuỗi s1

thành hai chuỗi: Chuỗi đầu là những ký tự cho đến khi

gặp chuỗi s2 đầu tiên, chuỗi sau là những ký tự còn lại

của s1 sau khi đã bỏ đi chuỗi s2 xuất hiện trong s1.

Nếu s2 không xuất hiện trong s1 thì kết quả chuỗi tách vẫn là s1.

char *strtok(char s1[], char s2[]);

5. KIỂU CÓ CẤU TRÚC

5.1. Giới thiệu

Cấu trúc thực chất là một kiểu dữ liệu do người dùng định nghĩa bằng cách sử dụng các kiểu dữ liệu cơ sở thành một kiểu dữ liệu phức hợp nhiều thành phần

5. KIỂU CÓ CẤU TRÚC

5.2. Khai báo Cú pháp 1:

struct SinhVien { char MSSV[6] ; char HoTenSV[30]; bool Phai ; float Toan, Ly, Hoa; }; struct SinhVien SV; struct { ; ; …….. ; }; struct

5. KIỂU CÓ CẤU TRÚC

5.2. Khai báo Cú pháp 2:

typedef struct { char MSSV[6] ; char HoTenSV[30]; bool Phai ; float Toan, Ly, Hoa; }Sinhvien; SinhVien SV;

typedef struct { ; ; …….. ; } ;

5. KIỂU CÓ CẤU TRÚC

5.3. Khởi tạo cấu trúc

 Việc khởi tạo cấu trúc có thể được thực hiện trong

lúc khai báo biến cấu trúc.

 Các trường của cấu trúc được khởi tạo được đặt giữa 2 dấu { và }, chúng được phân cách nhau bởi dấu phẩy (,).

struct SinhVien SV={„sv01‟,‟nguyen thi lan‟,0,6.0,7.5,8.0};

5. KIỂU CÓ CẤU TRÚC

5.4. Truy xuất từng trường trong biến cấu trúc

Cú pháp:

s = SV.HoTenSV; //nguyen thi lan

. ;

5. KIỂU CÓ CẤU TRÚC

5.5. Mảng cấu trúc

 Cách khai báo tương tự như mảng một chiều hay ma trận (Kiểu dữ liệu nhưng kiểu dữ liệu của mỗi phần tử là kiểu dữ liệu có cấu trúc).

 Cách truy cập phần tử trong mảng cũng như truy cập trên mảng một chiều hay ma trận. Nhưng do từng phần tử có kiểu cấu trúc nên phải chỉ định rõ cần lấy thành phần nào.

5. KIỂU CÓ CẤU TRÚC

struct PhanSo { int tu, mau; }; struc PhanSo ps; void main() { int n; //Kích thước của mảng PhanSo a[100]; //Mảng các phân số //Các lệnh }

5. KIỂU CÓ CẤU TRÚC

 Do kiểu dữ liệu có cấu trúc thường chứa rất nhiều thành phần nên khi viết chương trình loại này ta cần lưu ý:

 Xây dựng hàm xử lý cho một kiểu cấu trúc.

 Muốn xử lý cho mảng cấu trúc, ta gọi lại hàm xử lý cho một kiểu cấu trúc đã được xây dựng bằng cách dùng vòng lặp.

5. KIỂU CÓ CẤU TRÚC

char Hoten[40]; float Diem; char Loai[10];

Bài tập 1. Định nghĩa kiểu: struct Hoso{ }

Điểm 7,8  Khá

Viết chương trình nhập thôn tin của n học sinh (Họ tên, điểm), xếp loại như sau: Điểm 9,10  Giỏi Điểm 5,6  Trung bình Điểm <5  Không đạt In DS như sau:

Họ tên Nguyen Thi Lan Tran Van Diep

Diem 8 4

Xep loai Khá Khong dat

XEP LOAI VAN HOA