KHOA KHOA HỌC MÁY TÍNH – BỘ MƠN LẬP TRÌNH BÀI GIẢNG CẤU TRÚC DỮ LIỆU (BẬC CAO ĐẲNG) Chương1: NHẬP MÔN CẤU TRÚC DỮ LIỆU Nguyễn Thanh Cẩm NỘI DUNG TRÌNH BÀY Ý nghĩa cấu trúc liệu Cấu trúc liệu vấn đề liên quan Thuật toán Ý nghĩa cấu trúc liệu DATA STRUCTURE + ALGORITHM = PROGRAM Niklaus wirth • Để giải tốn máy tính: cần thuật tốn • Thuật tốn phản ánh phép xử lý • Dữ liệu biểu diễn thông tin cần thiết tốn • vd: •Cấu trúc liệu thay đổi thuật toán thay đổi theo Cấu trúc liệu vấn đề liên quan a Dữ liệu lưu trữ liệu b Các kiểu liệu đơn giản c Các kiểu liệu cấu trúc Cấu trúc liệu vấn đề liên quan a Dữ liệu lưu trữ liệu Dữ liệu vật mang thơng tin chuẩn hóa Cần phân biệt liệu với thông tin: - Dữ liệu tồn khác quan - Thơng tin có ý nghĩa chủ quan Cấu trúc liệu vấn đề liên quan a Dữ liệu lưu trữ liệu Trong toán, liệu gồm tập phần tử sở, gọi liệu nguyên tử Nó chữ số, ký tự, từ,…tùy vào toán cụ thể Trên sở liệu nguyên tử, cung cách liên kết chúng với dẫn tới cấu trúc liệu khác Cấu trúc liệu vấn đề liên quan a Dữ liệu lưu trữ liệu - Khi chọn cấu trúc liệu phải nghĩ tới phép toán tác động lên cấu trúc ngược lại - Cách biểu diễn cấu trúc liệu nhớ gọi cấu trúc lưu trữ (storage structure) - Có thể có nhiều CTLT khác cho CTDL, có nhiều CTDL khác mà cài đặt nhớ kiểu cấu trúc lưu trữ - CTDL CTDL Cấu trúc liệu vấn đề liên quan a Dữ liệu lưu trữ liệu b Các kiểu liệu đơn giản c Các kiểu liệu cấu trúc Cấu trúc liệu vấn đề liên quan b Dữ liệu lưu trữ liệu Các kiểu liệu Các kiểu liệu đơn giản Các kiểu liệu cấu trúc Kích thước: 1Byte Kiểu lơgic Kiểu char Kiểu int Kiểu float PVBD: True, False Kích thước: 1Byte PVBD: -128 ->127 Kích thước: 2Byte PVBD: -32768 -> 32767 Kích thước: 4Byte PVBD: 3.4E-38 ->3.4E+38 Cấu trúc liệu vấn đề liên quan a Dữ liệu lưu trữ liệu b Các kiểu liệu đơn giản c Các kiểu liệu cấu trúc 10 Thuật tốn c Chương trình Hàm có kiểu Là chương trình con, xử lý tính tốn với mục đích trả giá trị đối tượng Khai báo: (danh sách tham số hình thức) { … return KQ; } Gọi hàm: tên_hàm(danh sách tham số thực sự); 19 Thuật tốn c Chương trình Hàm khơng kiểu (thủ tục) Là chương trình con, xử lý tính tốn cơng việc Khai báo: (danh sách tham số hình thức) { … } Gọi hàm: Tên_hàm(danh sách tham số thực sự); 20 KHOA KHOA HỌC MÁY TÍNH – BỘ MƠN LẬP TRÌNH Chúc bạn thành công ! 21 BÀI TẬP Viết chương trình giải phương trình bậc ax + b = Viết chương trình tìm UCLN BCNN hai số nguyên dương nhập từ bàn phím Viết chương trình tính tích hai ma trận A(nxm) B(mxp) In kết ma trận tích C(nxp) Viết hàm thay chuỗi chuỗi chuỗi khác Dúng cấu trúc mảng Viết chương trình quản lý danh sách sinh viên (gồm họ tên, mã sinh viên) Chương trình có khả thêm, bớt, tìm kiếm 22 Viết chương trình giải phương trình bậc ax + b = /* Bai tap1 - Giai phuong trinh bac nhat AX + B = */ #include void main() { float a, b; printf("\nGiai phuong trinh bac nhat AX + B = 0"); printf("\nCho biet cac he so A B : "); scanf("%f%f", &a, &b); if (a==0) if (b!=0) printf("Phuong trinh vo nghiem"); else printf("Phuong trinh co vo so nghiem"); else printf(“Nghiem x = %f", -b/a); getch(); } 23 Viết chương trình tìm UCLN BCNN hai số nguyên dương nhập từ bàn phím #include unsigned int UCLN (unsigned int n, unsigned int m) { while (n != && m != 0) if (n>m) n -= m; else m -= n; if (n == 0) return m; else return n; } Unsigned int BCNN (unsigned int n, unsigned int m) { return n * m / UCLN(n, m); } void main() { unsigned int n, m; printf("\nNhap hai vao so nguyen duong : "); scanf("%u%u", &n, &m); printf("\nUCLN cua %u va %u = %u", n, m, UCLN(n,m)); printf("\nBCNN cua %u va %u = %u", n, m, BCNN(n,m)); getch(); } 24 Viết chương trình tính tích hai ma trận A(nxm) B(mxp) In kết ma trận tích C(nxp) #include #define MAX 10 void in_ma_tran(int A[MAX][MAX], int n, int m, char id) { int i, j; printf("\nMa tran %c : ", id); for (i=0; i