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

9/24/2016 1 Tuần 5 - Các cấu trúc dữ liệu cơ bản Giáo viên: Hà Đại Dương duonghd@mta.edu.vn Kỹ thuật lập trình 9/24/2016 1 Bài trước • Fundamental Types of the C/C++ Language – Kiểu nguyên (Integral) – Kiểu thực (Floating point) Tham khảo: https://msdn.microsoft.com/en-us/library/cc953fe1.aspx • Kích thước bộ nhớ, miền giá trị của các kiểu dữ liệu. Tham khảo: https://msdn.microsoft.com/en-us/library/s3f49ktz.aspx 9/24/2016 2 9/24/2016 2 9/24/2016 3 https://msdn.microsoft.com/en-us/library/cc953fe1.aspx 9/24/2016 4 https://msdn.microsoft.com/en-us/library/cc953fe1.aspx 9/24/2016 3 9/24/2016 5 https://msdn.microsoft.com/en-us/library/s3f49ktz.aspx 9/24/2016 6 https://msdn.microsoft.com/en-us/library/s3f49ktz.aspx 9/24/2016 4 Một số bài toán • Tìm số lớn nhất trong 1 danh sách có 100, 1000 phần tử. • Bài toán quản lý sinh viên? • Bài toán kiểm soát giao thông? • Các kiểu số thực, số nguyên có thể mô tả dữ liệu cho bài toán nêu ra? 9/24/2016 7 Nội dung • Mảng (array) • Con trỏ (pointer) • Xâu ký tự (string) 9/24/2016 8 9/24/2016 5 Mảng (array, list) 9/24/2016 9 Mô tả • Cho phép mô tả (lưu trữ) một danh sách (các biến) với: – Cùng một tên (identifier), – Cùng kiểu dữ liệu và – Mỗi phần tử được phân biệt bằng chỉ số (số thứ tự) của phần tử trong mảng. • Mảng (về mặt hình thức) – 1 chiều: dùng 1 chỉ số để truy xuất đến phần tử – nhiều chiều: dùng nhiều chỉ số 9/24/2016 10 9/24/2016 6 Mảng một chiều • Cú pháp (khai báo): Kiểu Tên_Biến[N]; hoặc Kiểu Tên_Biến[] ={Gt1, Gt2, , GtN}; • Trong đó: – Kiểu: Kiểu dữ liệu mỗi phần tử của mảng – N: Số phần tử của mảng, chỉ số của mảng bắt đầu từ 0 đến N-1 – Gt1, Gt2, , GtN: giá trị các phần tử của mảng 9/24/2016 11 Hình ảnh trong bộ nhớ • Ví dụ: int a[10]; float b[50]; • Khi gặp khai báo int a[10]; chương trình sẽ tạo ra 10 “ô” nhớ liên tiếp như sau: • Mỗi “ô” nhớ có kích thước (byte) bằng kích thước kiểu dữ liệu mỗi phần tử của mảng. 9/24/2016 12 Chỉ số 0 1 2 3 4 5 6 7 8 9 Ô nhớ 9/24/2016 7 Truy xuất các phần tử • Viết chỉ số phần tử trong cặp dấu [, ] sau tên biến mảng. • Ví dụ: – a[0], a[3] , b[1], b[i] – Đọc bằng scanf: scanf(“%d”, &a[i]); – Ghi ra màn hình bằng printf: printf(“Phan tu thu %d la %d”, i, a[i]); 9/24/2016 13 Ví dụ 1 • Viết chương trình nhập vào danh sách điểm môn kỹ thuật lập trình của lớp. Tìm điểm lớn nhất. 9/24/2016 14 9/24/2016 8 Ví dụ 1 9/24/2016 15 Ví dụ 1 • Kết quả 9/24/2016 16 Chỉ số Phù hợp với chỉ số của mảng Không phù hợp với cách hiểu thông thường Sửa lại chương trình ??? 9/24/2016 9 Ví dụ 2 • Đổi số hệ thập phân thành số ở hệ nhị phân. • Cách đổi: – Chia cho 2, lấy thương chia 2 và tiếp tục cho đến khi thương thu được = 0 – Viết các số dư của phép chia theo chiều ngược lại -> Số nhị phân. – Ví dụ: 3710 -> 1001012 9/24/2016 17 Ví dụ 2 • Viết chương trình chuyển số thập phân -> nhị phân. – Dùng mảng để lưu kết quả phần dư của phép chia – Mỗi phần tử có kiểu là??? – Số phần tử (tối đa) của mảng là ??? – Sử dụng vòng lặp (đã học) – Viết chương trình (10 phút) 9/24/2016 18 9/24/2016 10 Ví dụ 2 9/24/2016 19 Ví dụ 3 • Sắp xếp danh sách điểm (ví dụ 1) theo thứ tự giảm dần. • Ý tưởng: – Tìm số lớn nhất trong N số cho về đầu, còn lại N-1 số; – Tìm số lớn nhất trong N-1 số còn lại cho về đầu, còn N-2 số – Còn 1 số: ở nguyên vị trí cuối Danh sách đã sắp xếp giảm 9/24/2016 20 9/24/2016 11 Ví dụ 3 • Dãy số: 8, 6, 9, 7, 5 – Số lớn nhất trong 8, 6, 9, 7, 5 là 9 -> 9, 6, 8, 7, 5 – Số lớn nhất trong 6, 8, 7, 5 là 8 -> 9, 8, 6, 7, 5 – Số lớn nhất trong 6, 7, 5 là 7 -> 9, 8, 7, 6, 5 – Số lớn nhất trong 6, 5 là 6 -> 9, 8, 7, 6, 5 – Số lớn nhất trong 5 là 5 -> 9, 8, 7, 6, 5 • Lưu ý: Khi tìm được phần tử lớn nhất thì đổi chỗ phần tử đang xem xét với phần tử lớn nhất 9/24/2016 21 9/24/2016 22 Vừa khai báo vừa gán giá trị 9/24/2016 12 Ví dụ 3 • Kết quả 9/24/2016 23 Ví dụ 4 • Sắp xếp danh sách điểm (ví dụ 1) theo thứ tự tăng dần. – Viết chương trình (10 phút) 9/24/2016 24 9/24/2016 13 Một số lưu ý • Có thể đọc những phần tử nằm ngoài giới hạn của mảng. Ví dụ 9/24/2016 25 Phần tử: 5,6,7,8,9 Ngoài giới hạn mảng Một số lưu ý • Có thể ghi những phần tử nằm ngoài giới hạn của mảng. Ví dụ 9/24/2016 26 Phần tử: 5,6,7,8,9 Ngoài giới hạn mảng 9/24/2016 14 Một số lưu ý • Có thể ghi những phần tử nằm ngoài giới hạn của mảng. Khi kết thúc chương trình hiển thị thông báo lỗi 9/24/2016 27 Mảng nhiều chiều • Mảng 2, 3, chiều • Khai báo Kiểu Tên_Biến[N1][N2][] • Trong đó: – N1: Số phần tử theo chiều thứ nhất – N2: Số phần tử theo chiều thứ 2 – • Thường dùng đến mảng 2, 3 chiều. 9/24/2016 28 9/24/2016 15 Mảng 2 chiều • Ví dụ: Tính ma trận tổng C của hai ma trận A, B • Khai báo: – float A[3][3], B[3][3], C[3][3]; int i2[5][7] • Tổ chức mảng 2 chiều 9/24/2016 29 Ví dụ 5 • Tính ma trận tổng C – Nhập/In ma trận A – Ma trận tổng: C[i][j] = A[i][j] + B[i][j] 9/24/2016 30 9/24/2016 16 Ví dụ 5 • Tính ma trận tổng C: • Nhập và in ma trận A 9/24/2016 31 Ví dụ 5 • Tính ma trận tổng C – Nhập/In ma trận A – Viết chương trình hoàn chỉnh (10 phút) (Nhập B, Tính C, In A, B, C) (A) (B) (C) 1 3 5 3 4 1 4 7 6 2 2 4 + 1 4 2 = 3 6 6 3 4 5 4 2 4 7 6 9 9/24/2016 32 9/24/2016 17 Ví dụ 6 • Tính ma trận tích C = A*B • Biết: – C[i][j] = Sumk=1..N(A[i][k]*B[k][j]) • Viết chương trình (10 phút) 9/24/2016 33 9/24/2016 34 9/24/2016 18 Một số lưu ý • Khai báo không tường minh (số phần tử theo 1 chiều nào đó) không cho phép đối với chiều cuối. Ví dụ, khai báo sau; int A[][] ={{1,2,3},{4,5,6},{7,8,9}} là không hợp lệ. 9/24/2016 35 Bài tập 9/24/2016 36 9/24/2016 19 Bài tập 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. 9/24/2016 37 Bài tập về nhà 1. Tính ma trận tổng C, in kết quả như sau: 2. Tính ma trận tích C = A*B. Kiểm tra điều kiện để nhận được A*B. 3. Tính định thức của ma trận. 4. Tính ma trận nghịc đảo. 9/24/2016 38 9/24/2016 20 Bài tập về nhà 5. Giải hệ phương trình bậc nhất N ẩn bằng phương pháp Gauss. 6. Xét trên chương trình ở ví dụ 3 viết ra giá trị của mảng sau mỗi bước lặp j khi mảng d[] ={5, 7, 3, 8, 6} 9/24/2016 39