Kỹ thuật lập trình - Tuần 6: Các cấu trúc dữ liệu cơ bản

9/26/2016 1 Tuần 6 - Các cấu trúc dữ liệu cơ bản (tiếp) Giáo viên: Hà Đại Dương duonghd@mta.edu.vn Kỹ thuật lập trình 9/26/2016 1 Nội dung • Mảng (array) - Bài trước • Con trỏ (pointer) • Xâu ký tự (string) 9/26/2016 2 9/26/2016 2 Con trỏ (Pointer) 9/26/2016 3 Con trỏ • Cho phép quản lý vùng nhớ: Ghi, đọc dữ liệu từ vùng nhớ này (như biến) • Biến thông thường int a; float b; char c a,b,c: Biến (thường), lưu giá trị • Biến con trỏ (con trỏ): lưu địa chỉ của vùng nhớ. 9/26/2016 4 9/26/2016 3 Khai báo • Cú pháp Kiểu * Tên_Biến; • Ví dụ: int *pa; float *pb; char *pc; 9/26/2016 5 Địa chỉ và giá trị • Ô nhớ: Được xác định bằng 1 địa chỉ và có 1 giá trị nào đó. • Ví dụ: – Tại địa chỉ: FF01 có giá trị là 678 – Tại địac chỉ FF02 có giá trị là 34.1 9/26/2016 6 Địa chỉ Giá trị FF01 678 FF02 34.1 9/26/2016 4 Địa chỉ và giá trị • Biến thường int a; float b; char c Quan tên của nó -> Biết giá trị • Con trỏ: int *pa; float *pb; char *pc; Qua tên của nó -> Biết địa chỉ ô nhớ 9/26/2016 7 Địa chỉ Giá trị FF01 678 FF02 34.1 Địa chỉ và giá trị • Toán tử &: Tác động đến địa chỉ của 1 biến (thường) – Cú pháp: &Tên_Biến_Thường – Ví dụ: &a, &b, &c • Toán tử *: Tác động đến giá trị ô nhớ tại địa chỉ biến con trỏ – Cú pháp: *Tên_Biến_Con_trỏ – Ví dụ: *pa, *pb, *pc 9/26/2016 8 9/26/2016 5 Ví dụ 1 9/26/2016 9 Ví dụ 1 9/26/2016 10 9/26/2016 6 Ví dụ 2 9/26/2016 11 Ví dụ 2 9/26/2016 12 9/26/2016 7 Cấp phát bộ nhớ • Xét chương trình sau: 9/26/2016 13 Cấp phát bộ nhớ • Khi chạy báo lỗi Sử dụng pa khi chưa khởi tạo 9/26/2016 14 9/26/2016 8 Lý do • Khi gặp khai báo con trỏ -> chương trình chưa dành chỗ (ô nhớ) để lưu giá trị nên Báo lỗi • Ở ví dụ trước 9/26/2016 15 có pa = &a nên *pa=190; Không báo lỗi Hàm malloc() • Con trỏ: Cho phép quản lý vùng nhớ (Ghi, đọc dữ liệu từ vùng nhớ này) • Hàm malloc(n) – Cú pháp: void * malloc(n) – Trả về địa chỉ (đầu) vùng nhớ n byte cấp phát được (dạng void *) – Ví dụ: pa = (int *) malloc(4); pa = (int *) malloc(sizeof(int)); 9/26/2016 16 9/26/2016 9 Hàm calloc() • Hàm calloc(k,n) – Cú pháp: void * calloc(k,n) – Trong đó: • k: số phần tử • N: kích thước (byte) mỗi phần tử – Trả về địa chỉ (đầu) vùng nhớ k*n (bytes) cấp phát được. – Ví dụ: pb = (float*) calloc(5,4) (hàm malloc(), calloc() có trong thư viện malloc.h ) 9/26/2016 17 Ví dụ 3 9/26/2016 18 9/26/2016 10 Ví dụ 3 9/26/2016 19 Quản lý mảng bằng con trỏ • Trong ví dụ 3, lệnh Cấp phát 5 “ô” nhớ, mỗi ô nhớ cho phép lưu trữ 1 giá trị float. • Khi đó pb quản lý danh sách 5 ô nhớ như là 1 mảng. 9/26/2016 20 9/26/2016 11 Quản lý mảng bằng con trỏ • Phép cộng/trừ con trỏ với 1 số nguyên – Phép công: pb + N cho phép truy cập đến phần tử (ô nhớ) thứ N+1 tính từ địa chỉ con trỏ pb. – Phép công: pb - N cho phép truy cập đến phần tử (ô nhớ) trước con trỏ pb N. 9/26/2016 21 Ví dụ 4 9/26/2016 22 9/26/2016 12 Ví dụ 4 9/26/2016 23 Ví dụ 5 • Sử dụng con trỏ, viết chương trình cho phép nhập vào một mảng, sắp xếp tăng dần và in kết quả ra màn hình. • Viết chương trình (10 phút) 9/26/2016 24 9/26/2016 13 Cấp phát bộ nhớ động • Biến thường và mảng khi khai báo chương trình sẽ cấp phát vùng nhớ có kích thước cố định đủ để lưu trữ dữ liệu các biến đó -> Cấp phát tĩnh. • Con trỏ cho phép tạo và quản lý vùng nhớ với kích thước có thể thay đổi được -> Cấp phát động. 9/26/2016 25 Cấp phát bộ nhớ động • Cấp phát vùng nhớ: – malloc(), – calloc() • Khi không cần có thể thu hồi (giải phóng) vùng nhớ: – free(); • Nếu thiếu có thể cấp phát thêm: – realloc() 9/26/2016 26 9/26/2016 14 Hàm free() • Cú pháp: void free(void *p) • Ý nghĩa: Giải phóng vùng nhớ quản lý bởi con trỏ p. • Ví dụ: 9/26/2016 27 Hàm realloc() • Cú pháp: void * realloc(void *p, N) • Ý nghĩa: cấp phát lại vùng nhớ quản lý bởi con trỏ p với kích thước mới là N (bytes). • Ví dụ 6: 9/26/2016 28 9/26/2016 15 9/26/2016 29 Ví dụ 6 9/26/2016 30 9/26/2016 16 Lưu ý • Hằng con trỏ NULL: NULL - Không trỏ đến đâu ví dụ: pb = NULL • Trừ 2 con trỏ cùng kiểu Cho 1 số là khoảng cách (số phần tử) giữa 2 con trỏ đó • Không cộng 2 con trỏ. 9/26/2016 31 Bài tập 9/26/2016 32 9/26/2016 17 Bài tập (Sử dụng con trỏ thay vì dùng mảng) 1. Viết chương trình chuyển số thập phân về bát phân, thập lục phân. 2. Viết chương trình chuyển số nhị phân, bát phân, thập lục phân về dạng thập phân. 3. Viết chương trình tính ma trận tổng C = A + B 4. Viết chương trình tính ma trận tích C = A * B 9/26/2016 33 Bài tập về nhà • Biểu diễn mảng hai chiều sử dụng con trỏ như thế nào? 9/26/2016 34 9/26/2016 18 Xâu ký tự (string) 9/26/2016 35 Định nghĩa • Xâu ký tự (hay chuỗi ký tự) là một dãy (hoặc mảng) các ký tự liên tiếp được kết thúc bằng ký tự ‘\0’ (còn được gọi là ký tự NULL trong bảng mã ASCII). • Hằng xâu ký tự là dãy ký tự nằm trong cặp “” • Ví dụ: “Ky thuat lap trinh” “Hoc vien Ky thuat Quan su” 9/26/2016 36 9/26/2016 19 Xâu ký tự • Trong C++: có kiểu xâu ký tự string. • Trong C: xâu là cách tổ chức dữ liệu (không phải kiểu) – Xâu là mảng các ký tự: char Ten[50]; char Ten[] =“Ky thuat lap trinh”; – Xâu là con trỏ ký tự char * Ten; (Trong phần này chỉ xem xét dưới khía cạnh of C) 9/26/2016 37 Nhập/Xuất xâu • Hàm puts(s) – Ý nghĩa: In (xuất) xâu ký tự s ra màn hình – Cú pháp: puts(s); • Hàm gets(s) – Ý nghĩa: Đọc (nhập) xâu ký tự từ bàn phím – Cú pháp: gets(s); – Ví dụ 9/26/2016 38 9/26/2016 20 9/26/2016 39 Ví dụ 7 • Đến số ký tự trống (space bar) trong xâu vừa nhập. • Hàm strlen(s): trả về số ký tự của xâu s • Viết chương trình (10 phút) 9/26/2016 40 9/26/2016 21 Ví dụ 7 9/26/2016 41 Xâu ký tự • Khi xử lý từng ký tự -> Xâu là mảng các ký tự. • Hơn thế: Xâu ký tự không chỉ là mảng các ký tự: – Các ký tự trong xâu có quan hệ với nhau (khác với phần tử của mảng) – Cộng 2 xâu: “Sinh Vien” và “Hoc vien KTQS” để được “Sinh Vien Học vien KTQS” (khác với 2 mảng) – . 9/26/2016 42 Xâu không chỉ là mảng các ký tự 9/26/2016 22 Các hàm xử lý xâu • Hàm strcat() – Ý nghĩa: Cộng (nối) 2 xâu thành một – Cú pháp char *strcat(char *des, const char *source) – Nối xâu 2 vào xâu 1. – Ví dụ 9/26/2016 43 9/26/2016 44 9/26/2016 23 9/26/2016 45 Các hàm xử lý xâu • Chuyển 1 ký tự thành ký tự hoa – char toupper(char c) • Chuyển 1 xâu thành hoa – char *strupr(char *s) • Chuyển 1 xâu thành in thường – char *strlwr(char *s) • Sao chép (copy) 1 xâu – char *strcpy(char *Des, const char *Source) 9/26/2016 46 9/26/2016 24 Các hàm xử lý xâu • Sao chép n ký tự đầu tiên – char *strncpy(char *Des, const char *Source, size_t n) • Tìm kiếm nội dung – char *strstr(const char *s1, const char *s2) – Tìm kiếm sự xuất hiện đầu tiên của chuỗi s2 trong chuỗi s1 – Kết quả trả về của hàm là một con trỏ chỉ đến phần tử đầu tiên của chuỗi s1 có chứa chuỗi s2 hoặc giá trị NULL nếu chuỗi s2 không có trong chuỗi s1 9/26/2016 47 Ví dụ 9/26/2016 48 9/26/2016 25 Các hàm xử lý xâu • So sánh 2 xâu – int strcmp(const char *s1, const char *s2) – Hàm strcmp trả về: • Số âm: s1 < s2 • Không: s1 = s2 • Dương: s1>s2 • 9/26/2016 49 Ví dụ 8 • Đổi năm dương lịch thành năm âm lịch – Xem lại chương trình đã viết ở tuần 2 – Chương trình 9/26/2016 50 9/26/2016 26 Ví dụ 8 9/26/2016 51 Ví dụ 9 • Viết chương trình đếm số từ đơn trong 1 xâu. Ví dụ: “Ky thuat lap trinh” có 4 từ đơn. • Viết chương trình (10) (Kiểm tra và thảo luận) 9/26/2016 52 9/26/2016 27 Ví dụ 10 • Tạo dòng chữ chạy trên màn hình. • Cách làm ?: Ví dụ với xâu “Ky thuat lap trinh ” – Chạy qua bên trái “Ky thuat lap trinh ” “y thuat lap trinh K” “ thuat lap trinh Ky” “thuat lap trinh Ky ” “huat lap trinh Ky t” . 9/26/2016 53 Ví dụ 10 9/26/2016 54 9/26/2016 28 Ví dụ 10 • Để cảm nhận dòng chữ chạy ngang trên màn hình thì cần viết các dòng “Ky thuat lap trinh ” “y thuat lap trinh K” “ thuat lap trinh Ky” cùng 1 vị trí. • Lệnh system(“cls”) trong thư viện stdlib.h; cho phép xoá màn hình và đưa con trỏ về góc trên bên trái 9/26/2016 55 9/26/2016 56 9/26/2016 29 Ví dụ 10 • Chưa thêm system(“cls”) • Thêm vào system(“cls”) 9/26/2016 57 Ví dụ 10 • Để thực sự tạo hiệu ứng dòng chữ chạy ngang màn hình cần viết ra liên tục, liên tục các dong “Ky thuat lap trinh ” “y thuat lap trinh K” “ thuat lap trinh Ky” ở cùng 1 vị trí • Viết chương trình hoàn chỉnh (10 phút) 9/26/2016 58 9/26/2016 30 Ví dụ 10 9/26/2016 59 Ví dụ 10 • Chương trình trên đến khi nào dừng? • Muốn dừng khi người sử dụng nhấn 1 phím bất kỳ? Làm thế nào? • Để tốc độ chữ chạy chậm hơn? Làm thế nào? • Để chữ chạy từ qua phải làm thế nào? 9/26/2016 60 9/26/2016 31 Bài tập 9/26/2016 61 Bài tập 1. Viết chương trình thể hiện dòng chữ chạy ngang trên màn hình từ phải qua trái. 2. Chuẩn hoá xâu họ tên người việt 3. Đổi ngày tháng năm thành chữ. Ví dụ 27/9/2016 đổi thành dòng chữ “Ngày hai mươi bảy tháng chín năm hai nghìn không trăm mười sáu”. 4. Nhập vào 1 biểu thức đơn giản gồm 2 toán hạng và 1 toán tử, tính kết quả biểu thức đó. 9/26/2016 62 9/26/2016 32 Bài tập về nhà • Sử dụng hàm scanf() để đọc xâu ký tự thì có khó khăn gì? • Tìm hiểu và làm bài tập cho tất cả các hàm trong string.h • Tìm hiểu trong VS C/C++ làm thế nào để biết người sử dụng đã nhấn 1 phím bất kỳ. • Tìm hiểu trong VS C/C++ làm thế nào để giữ chậm 1 khoảng thời gian nào đó? 9/26/2016 63