Bài giảng Kỹ thuật lập trình nâng cao: Chương 4 - ThS. Phạm Đào Minh Vũ

Chia sẻ: Pojdb Pojdb | Ngày: | Loại File: PDF | Số trang:38

Thêm vào BST

Báo xấu

53
lượt xem 3
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Chương 4 - Các kiểu dữ liệu. Chương này gồm có những nội dung chính sau: Kiểu dữ liệu, các loại kiểu dữ liệu, mảng 1 chiều, khai báo mảng, các thao tác với mảng, chuỗi ký tự, các hàm thư viện, kiểu dữ liệu có cấu trúc,... Mời các bạn cùng tham khảo.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Kỹ thuật lập trình nâng cao: Chương 4 - ThS. Phạm Đào Minh Vũ

CHƢƠNG 4 CÁC KIỂU DỮ LIỆU
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
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
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 trúc thƣờng đƣợc các ngôn ngữ lập trình cấp cao xây dựng sẵn nhƣ một thành phần của ngôn ngữ để giảm nhẹ công việc cho ngƣời lập trì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 trúc, thƣờng chỉ đƣợ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
Kiểu dữ liệu  Kiểu dữ liệu có cấu trúc cơ bản  Mảng  Chuỗi ký tự  Cấu trúc  Kiểu dữ liệu hƣớng giải quyết vấn đề Những kiểu dữ liệu có cấu trú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 trúc dữ liệu cơ bản  Danh sách  Hàng đợi  Ngăn xếp  Cấu trúc cây Nếu dữ liệu đƣợc xữ lý theo thứ tự nhập thì 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 cùng xữ lý trƣớc) có thể dùng ngăn xếp, … Vì thế cấu trúc dữ liệu hƣớng vấn đề đƣợc xác định bởi thuật 5 toán tƣơng ứng.
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ó cùng kiểu dữ liệu và cùng tên. Do đó để truy xuất các biến thành phần, ta dùng cơ chế chỉ mục. 6
Khai báo mảng Cách 1: Con trỏ hằng  Cú pháp: [] ;  Ví dụ: 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 mảng: [] = {Giá trị}; Ví dụ: int a[5] = {0}; 7
Khai báo mảng Cách 2: Con trỏ  Ý nghĩa: Khi ta khai báo một mảng với kiểu dữ liệu bất kì (int, float, char,…) thì tên của mảng thực chất là một hằng địa chỉ của phần tử đầu tiên.  Cú pháp: < Kiểu dữ liệu > *< Tên mảng >;  Ví dụ : 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 thì 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
Các thao tác  Nhập / xuất  Tì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 bình, … 9
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ị nhỏ 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 bỏ tất cả các phần tử có giá trị trù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
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 trỏ hằng char < Tên chuỗi > [ < Số ký tự tối đa của chuỗi > ] ; Ví dụ: char chuoi[25];  Ý nghĩa khai báo 1 mả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ự vì phần tử thứ 25 đã chứa ký tự kết thúc chuỗi ‘\0’ )  Lưu ý: Chuỗi ký tự được kết thúc bằng ký tự ‘\0’. Do đó khi khai báo độ dài của chuỗi luôn luôn khai báo dư 1 phần tử để chứa ký tự ‘\0’. 11
Khai báo  Cách 2: Con trỏ char *< Tên chuỗi >; Ví dụ : char *chuoi; 12
Nhập  cin.getline(chuoi, số ký tự tối đa);  Ví dụ: char *str; str = new char [30]; cin.getline(str, 30); 13
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 thì hàm sẽ điền khoảng trắng cho đủ n ký tự vào đích strncpy(char đích[], char nguồn[], int n); 14
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 và thường. Trả về: 0 : nếu s1 bằng s2. >0: nếu s1 lớn hơn s2.
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
Các hàm thƣ viện – (tt)  Tì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 chỉ c: nếu tìm thấy char *strchr(char s[], char c);  Tì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 chỉ bắt đầu chuỗi s2 trong s1 char *strstr(char s1[], char s2[]); 17
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ự còn lại của s1 sau khi đã bỏ đ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 là s1. char *strtok(char s1[], char s2[]); 18
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 bỏ 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 s2 vào s1. Xuất chuỗi s1 ra màn hình.  31. Đổi tất cả các ký tự có trong chuỗi thành chữ thƣờng (không dùng hàm strlwr).  32. Đổi tất cả các ký tự trong chuỗi sang chữ in hoa (không dùng hàm struppr).  33. Viết chƣơng trình đổi những ký tự đầu tiên của mỗi từ thành chữ in hoa. 19
Kiểu dữ liệu có cấu trúc Cấu trúc thực chất là một kiểu dƣ̃ liệu do ngƣời dùng định nghĩ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;