Giáo trình Lập trình nâng cao - Chương 4: Các kiểu dữ liệu

Nội dung text: Giáo trình Lập trình nâng cao - Chương 4: Các kiểu dữ liệu

1. CHƢƠNG 4 CÁC KIỂU DỮ LIỆU
2. Kiểu dữ liệu  Kiểu dữ liệu T đƣợc xác định bởi một bộ , với :  V : tập các giá trị hợp lệ mà một đối tượng kiểu T có thể lưu trữ  O : tập các thao tác xử lý có thể thi hành trên đối tượng kiểu T  Ví du 1: Giả sử có kiểu dữ liệu mẫu tự = với  Vc = { a-z, A-Z}  Oc = {lấy mã ASCII của ký tự, biến đổi ký tự thƣờng thành ký tự hoa }  Ví dụ 2: Giả sử có kiểu dữ liệu số nguyên = với  Vi = { -32768 32767}  Oi = { +, -, *, /, %}  Nhƣ vậy, muốn sử dụng một kiểu dữ liệu cần nắm vững cả nội dung dữ liệu đƣợc phép lƣu trữ và các xử lý tác động trên đó 2
3. Kiểu dữ liệu Các thuộc tính của 1 KDL bao gồm:  Tên KDL.  Miền giá trị.  Kích thƣớc lƣu trữ.  Tập các toán tử tác động lên KDL. 3
4. Các loại kiểu dữ liệu  Kiểu dữ liệu cơ bản Là những kiểu dữ liệu đơn giản, không có cấu trúc thƣờng đƣợc các ngôn ngữ lập trình cấp cao xây dựng sẵn nhƣ một thành phần của ngôn ngữ để giảm nhẹ công việc cho ngƣời lập trình.  Kiểu có thứ tự rời rạc: số nguyên, ký tự  Kiểu có thứ tựkhông rời rạc: số thực. Các kiểu cơ sở rất đơn giản và không thể hiện rõ sự tổ chức dữ liệu trong một cấu trúc, thƣờng chỉ đƣợc sử̉ dụng làm nền để xây dựng các kiểu dữ̃ liệu phức tạp khác. 4
5. Kiểu dữ liệu  Kiểu dữ liệu có cấu trúc cơ bản  Mảng  Chuỗi ký tự  Cấu trúc  Kiểu dữ liệu hƣớng giải quyết vấn đề Những kiểu dữ liệu có cấu trúc hƣớng tới vấn đề cần giải quyết đƣợc xây dựng bằng cách kết nối các cấu trúc dữ liệu cơ bản  Danh sách  Hàng đợi  Ngăn xếp  Cấu trúc cây Nếu dữ liệu đƣợc xữ lý theo thứ tự nhập thì hàng đợi đƣợc sử dụng. Tƣơng tự nếu dữ liệu cần xữ lý theo thứ tự ngƣợc với thứ tự nhập (tức nhập sau cùng xữ lý trƣớc) có thể dùng ngăn xếp, Vì thế cấu trúc dữ liệu hƣớng vấn đề đƣợc xác định bởi thuật 5 toán tƣơng ứng.
6. Mảng 1 chiều  Mảng thực chất là một biến đƣợc cấp phát bộ nhớ liên tục và bao gồm nhiều biến thành phần.  Các thành phần của mảng là tập hợp các biến có cùng kiểu dữ liệu và cùng tên. Do đó để truy xuất các biến thành phần, ta dùng cơ chế chỉ mục. 6
7. Khai báo mảng Cách 1: Con trỏ hằng  Cú pháp: [ ] ;  Ví dụ: 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  Khởi gán giá trị ban đầu cho mảng: [ ] = {Giá trị}; Ví dụ: int a[5] = {0}; 7
8. Khai báo mảng Cách 2: Con trỏ  Ý nghĩa: Khi ta khai báo một mảng với kiểu dữ liệu bất kì (int, float, char, ) thì tên của mảng thực chất là một hằng địa chỉ của phần tử đầu tiên.  Cú pháp: * ;  Ví dụ: int *p; // khai bao con tro p int b[100]; p = new int [100]; p = b; // p tro vao phan tu 0 cua mang b  Với cách viết nhƣ trên thìta có thể hiểu các cách viết sau là tƣơng đƣơng p[i]  *(p + i)  b[i]  *(b+i)  Cấp phát: new  Giải phóng delete 8
9. Các thao tác  Nhập / xuất  Tìm kiếm  Sắp xếp  Tăng dần, giảm dần  Số lẻ tăng (giảm) dần  Kiểm tra  Đếm  Phần tử x, Số nguyên tố, Mảng con tăng (giảm)  Thêm / xóa  Tính tổng, giá trị trung bình, 9
10. Bài tập thực hành  18. Viết hàm sắp xếp các phần tử lẻ tăng dần.  19. Viết hàm sắp xếp các phần tử tại vị trí lẻ tăng dần.  20. Viết hàm xoá phần tử tại vị trí lẻ trong mảng.  21. Viết hàm xoá phần tử có giá trị lớn nhất trong mảng.  22. Nhập vào giá trị X. Viết hàm xoá tất cả các phần tử có giá trị nhỏ hơn X.  23. Nhập vào giá trị X. Viết hàm xoá phần tử có giá trị gần X nhất.  24. Viết hàm loại bỏ tất cả các phần tử có giá trị trùng nhau(chỉ giữ lại một phần tử trong số các phần tử trùng)  25. Viết hàm chèn phần tử có giá trị X vào vị trí đầu tiên của mảng.  26. Viết hàm chèn phần tử có giá trị X vào phía sau phần tử có giá trị lớn nhất trong mảng.  27. Viết hàm chèn phần tử có giá trị X vào trƣớc phần tử có giá trị là số nguyên tố đầu tiên trong mảng. 10
11. Chuỗi ký tự  Chuỗi ký tự là một dãy các phần tử, mỗi phần tử có kiểu ký tự  Khai báo:  Cách 1: Con trỏ hằng char [ ] ; Ví dụ: char chuoi[25];  Ý nghĩa khai báo 1 mảng kiểu ký tự tên là chuoi có 25 phần tử (nhƣ vậy tối đa ta có thể nhập 24 ký tự vì phần tử thứ 25 đã chứa ký tự kết thúc chuỗi ‘\0’ )  Lưu ý: Chuỗi ký tự được kết thúc bằng ký tự ‘\0’. Do đó khi khai báo độ dài của chuỗi luôn luôn khai báo dư 1 phần tử để chứa ký tự ‘\0’. 11
12. Khai báo  Cách 2: Con trỏ char * ; Ví dụ : char *chuoi; 12
13. Nhập  cin.getline(chuoi, số ký tự tối đa);  Ví dụ: char *str; str = new char [30]; cin.getline(str, 30); 13
14. Các hàm thƣ viện –  Tính độ dài của chuỗi s int strlen(char s[]);  Sao chép nội dung chuỗi nguồn vào chuỗi đích strcpy(char đích[], char nguồn[]);  Chép n ký tự từ chuỗi nguồn sang chuỗi đích. Nếu chiều dài nguồn < n thì hàm sẽ điền khoảng trắng cho đủ n ký tự vào đích strncpy(char đích[], char nguồn[], int n); 14
15. Các hàm thƣ viện – (tt)  Nối chuỗi s2 vài chuỗi s1 strcat(char s1[],char s2[]);  Nối n ký tự đầu tiên của chuỗi s2 vào chuỗi s1 strncat(char s1[],char s2[],int n);  So sánh 2 chuỗi s1 và s2 theo nguyên tắc thứ tự từ điển. Phân biệt chữ hoa và thường. Trả về: 0 : nếu s1 bằng s2. >0: nếu s1 lớn hơn s2. <0: nếu s1 nhỏhơn s2. int strcmp(char s1[],char s2[]); 15
16. Các hàm thƣ viện – (tt)  So sánh n ký tự đầu tiên của s1 và s2, giá trị trả về tƣơng tự hàm strcmp() int strncmp(char s1[],char s2[], int n);  So sánh chuỗi s1 và s2 nhƣng không phân biệt hoa thƣờng, giá trị trả về tƣơng tự hàm strcmp() int stricmp(char s1[],char s2[]);  So sánh n ký tự đầu tiên của s1 và s2 nhƣng không phân biệt hoa thƣờng, giá trị trả về tƣơng tự hàm strcmp() int strnicmp(char s1[],char s2[], int n); 16
17. Các hàm thƣ viện – (tt)  Tìm sự xuất hiện đầu tiên của ký tƣ c trong chuỗi s. Trả về: NULL: nếu không có Địa chỉc : nếu tìm thấy char *strchr(char s[], char c);  Tìm sự xuất hiện đầu tiên của chuỗi s2 trong chuỗi s1. Trả về: NULL: nếu không có Ngƣợc lại: Địa chỉ bắt đầu chuỗi s2 trong s1 char *strstr(char s1[], char s2[]); 17
18. Các hàm thƣ viện – (tt)  Tách chuỗi:  Nếu s2 có xuất hiện trong s1: Tách chuỗi s1 thành hai chuỗi: Chuỗi đầu là những ký tự cho đến khi gặp chuỗi s2 đầu tiên, chuỗi sau là những ký tự còn lại của s1 sau khi đã bỏ đi chuỗi s2 xuất hiện trong s1.  Nếu s2 không xuất hiện trong s1 thì kết quả chuỗi tách vẫn là s1. char *strtok(char s1[], char s2[]); 18
19. Bài tập  28. Đếm có bao nhiêu khoảng trắng trong chuỗi.  29. Nhập vào một chuỗi, hãy loại bỏ những khoảng trắng thừa trong chuỗi.  30. Nhập vào hai chuỗi s1 và s2, nối chuỗi 2s vào s1. Xuất chuỗi s1 ra màn hình.  31. Đổi tất cả các ký tự có trong chuỗi thành chữ thƣờng (không dùng hàm strlwr).  32. Đổi tất cả các ký tự trong chuỗi sang chữ in hoa (không dùng hàm struppr).  33. Viết chƣơng trình đổi những ký tự đầu tiên của mỗi từ thành chữ in hoa. 19
20. Kiểu dữ liệu có cấu trúc Cấu trúc thực chất là một kiểu dƣ̃ liệu do ngƣời dùng định nghĩa bằng cách gom nhóm các kiểu dƣ̃ liệu cơ bản có sẵn trong C thành một kiểu dƣ̃ liệu phức hợp nhiều thành phần  Khai báo struct tên_struct { khai báo các thuộc tính; }; typedef struct tên_struct tên_kiểu;  Ví dụ: struct ttDate { char thu[5]; unsigned char ngay; unsigned char thang; int nam; }; 20 typedef struct ttDate DATE;
21. Truy cập các thuộc tính cấu trúc  Biến kiểu cấu trúc tên_kiểu tên_biến; tên_biến.tên_thuộc_tính; Ví dụ: DATE x ; // khai bao bien x kieu DATE x.ngay = 5 ; // gan ngay bang 5  Biến con trỏ kiểu cấu trúc tên_kiểu *tên_biến_con_trỏ; tên_biến_con_trỏ->tên_thuộc_tính; Ví dụ: DATE *x ; // khai bao bien x kieu con tro DATE x -> ngay = 5 ; // gan ngay bang 5 21
22.  Khai báo đệ qui struct tên_struct { khai báo các thuộc tính; struct tên_struct *tên_thuộc_tính_đệ_qui; };  Ví dụ: struct ttNode { int key; struct ttNode *pNext; }; 22
23. Bài tập 55. Viết chƣơng trình sử dụng kiểu dữ liệu cấu trúc để hiển thị giờ, phút, giây ra màn hình.  Tính khoảng cách giữa 2 mốc thời gian và so sánh 2 mốc thời gian và cho biết kết quả. 56. Viết chƣơng trình sử dụng kiểu dữ liệu cấu trúc thể hiện ngày, tháng, năm ra màn hình.  Tính khoảng cách giữa 2 ngày và so sánh 2 ngày và cho biết kết quả. 57. Viết chƣơng trình khai báo kiểu dữ liệu để biểu diễn một phân số. Hãy viết hàm thực hiện những công việc sau:  Tính tổng, hiệu, tích, thƣơng hai phân số.  Rút gọn phân số.  Qui đồng hai phân số.  So sánh hai phân số. 23
24. 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 bây giờ là kiểu dữ liệu có cấu trúc).  Cách truy cập phần tử trong mảng cũ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ử có kiểu cấu trúc nên phải chỉ định rõ cần lấy thành phần nào, tức là phải truy cập đến thành phần cuối cùng có kiểu là dữ liệu cơ bản (xem lại bảng các kiểu dữ liệu cơ bản) 24
25. Nguyên tắc lập trình trên mảng cấu trúc Do kiểu dƣ̃ liệu có cấu trúc thƣờng chứa rất nhiều thành phần nên khi viết chƣơng trình loại này ta cần lƣu ý:  Xây dựng hàm xƣ̉ lý cho một kiểu cấu trúc.  Muốn xƣ̉ lý cho mảng cấu trúc, ta gọi lại hàm xƣ̉ lý cho một kiểu cấu trúc đã đƣợc xây dựng bằng cách dùng vòng lặp. 25
26. Mảng 2 chiều  Mảng hai chiều thực chất là mảng một chiều trong đó mỗi phần tử của mảng là một mảng một chiều, và đƣợc truy xuất bởi hai chỉ số dòng và cột.  Từ khái niệm trên ta có thể đƣa ra một khái niệm về mảng nhiều chiều nhƣ sau: mảng có từ hai chiều trở lên gọi là mảng nhiều chiều. 26
27. Khai báo Cách 1: Con trỏ hằng [ ][ ];  Ví dụ: int A[10][10]; // Khai báo mảng2 chiều kiểu int gồm10 dòng, 10 cột float b[10][10]; // Khai báo mảng2 chiều kiểu float gồm10 dòng, 10 cột Cách 2 : Con trỏ ;  Ví dụ : int A ; // Khai báo mảng động2 chiều kiểu int float B ; // Khai báo mảng động2 chiều kiểu float 27
28. Truy xuất Để truy xuất các thành phần của mảng hai chiều ta phải dựa vào chỉ số dòng và chỉ số cột. Ví dụ: int A[3][4] = { {2,3,9,4} , {5,6,7,6} , {2,9,4,7} }; Với các khai báo nhƣ trên ta có: A[0][0] = 2; A[0][1] = 3; A[1][1] = 6; A[1][3] = 6; 28
29. 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 dòng/ cột  Xóa dòng/ cột  Chèn thêm dòng/ cột 29
30. 1. Nhập/xuất ma trận void NhapMT(int a[][MAX], int dong, int cot) { for(int i=0;i >a[i][j]; } } } void XuatMT(int a[][MAX], int dong, int cot) { for(int i=0;i<dong;i++) { for(int j=0;j<cot;j++) cout<<a[i][j]<<" "; cout<<"\n"; } 30 }
31. 2. Tìm kiếm Tìm phần tử có giá trị lớn nhất trong ma trận int PhanTuMax(int a[][MAX], int dong, int cot) { int max=a[0][0]; for(int i=0;i max) max=a[i][j]; return max; } 31
32. 3. Đếm VD: đếm số lượng phần tử âm trong ma trận int DemPTAm(int a[][MAX], int dong, int cot) { int dem=0; for(int i=0;i<dong;i++) for(int j=0;j<cot;j++) if(a[i][j]<0) dem++; return dem; } 32
33. 4. Tính tổng/ trung bình VD: Tính tổng các phần tử lẻ int TongPTLe(int a[][MAX], int dong, int cot) { int tong=0; for(int i=0;i<dong;i++) for(int j=0;j<cot;j++) if(a[i][j]%2!=0) tong=tong+a[i][j]; return tong; } 33
34. BÀI TẬP - IN 1. Viết hàm nhập ma trận các số nguyên dƣơng (nhập sai báo lỗi và không cho nhập). 2. Viết chƣơng trình in ra các phần tử nằm trên 2 đƣờng chéo. 3. Viết hàm in ra các phần tử nằm phía trên đƣờng chéo phụ của ma trận vuông các số nguyên. 4. Viết hàm in ra các phần tử nằm phía dƣới đƣờng chéo phụ của ma trận vuông các số nguyên. 5. Viết hàm in ra các phần tử nằm phía trên đƣờng chéo chính của ma trận vuông các số nguyên. 6. Viết hàm in ra các phần tử nằm phía dƣới đƣờng chéo chính của ma trận vuông các số nguyên. 34
35. BÀI TẬP – TÌM - TỔNG – ĐẾM 9. Viết hàm tính tổng các phần tử trên cùng một dòng. 10. Viết hàm tính tổng các phần tử nằm trên đƣờng chéo chính của ma trận vuông. 11. Viết hàm tính giá trị trung bình của các phần tử nhỏ nhất trên mỗi cột. 12. Viết hàm tìm vị trí phần tử lớn nhất trong ma trận các số nguyên. 13. Viết hàm tìm vị trí phần tử chẵn cuối cùng trong ma trận các số nguyên. 14. Viết hàm tìm phần tử chẵn dƣơng và nhỏ nhất trong ma trận. 15. Viết hàm tìm dòng có tổng lớn nhất trong ma trận các số thực. 16. Viết hàm đếm các giá trị nhỏ hơn x trong ma trận các số thực. 17. Viết hàm đếm các giá trị âm, dƣơng trong ma trận các số thực. 35
36. Ma trận vuông  Đƣờng chéo chính: chỉ số dòng = chỉ số cột  Đường chéo phụ: chỉ số cột + chỉ số dòng = kích thước - 1 36
37. Đƣờng chéo Ma trận vuông 37