Cấu trúc dữ liệu - Chương 1: Mở ñầu về cấu trúc dữ liệu

ðại Học Sư Phạm Tp. Hồ Chí Minh Chương 01: Mở ñầu về CTDL CẤU TRÚC DỮ LIỆU 1 Thông tin giảng viên • LƯƠNG TRẦN HY HIẾN • Bộ Môn Tin Học • Khoa Toán – Tin học • Phone: 0989 366 990 • Email: hienlth@hcmup.edu.vn Chương 1. Giới thiệu về cấu trúc dữ liệu 1.1 Vai trò của cấu trúc dữ liệu 1.2 Một số tiêu chuẩn chọn CTDL 1.3 Kiểu dữ liệu 1.4 ðộ phức tạp giải thuật 1.1 Vai trò của cấu trúc dữ liệu Bài toán thực tế Thông tin nghiệp vụ thực tế Thao tác nghiệp vụ Bài toán trên máy tính ðối tượng dữ liệu Yêu cầu xử lý 1.1 Vai trò của cấu trúc dữ liệu Bài toán trên máy tính ðối tượng dữ liệu Yêu cầu xử lý Khi giải quyết các bài toán thực tế cần quan tâm:
Tổ chức biểu diễn các ñối tượng thực tế Chọn cấu trúc dữ liệu phù hợp
Xây dựng các thao tác xử lý dữ liệu Tìm giải thuật giải quyết bài toán. Cấu trúc dữ liệu + giải thuật = chương trình 1.1 Vai trò của cấu trúc dữ liệu  Ví dụ 1: Chương trình quản lý ñiểm sinh viên của một khóa học. Mỗi sinh viên học 4 môn học và các ñiểm tương ứng như sau: Cấu trúc dữ liệu + giải thuật = chương trình Môn 1 Môn 2 Môn 3 Môn 4 Sinh viên 1 7 8 5 6 Sinh viên 2 8 6 4 5 Sinh viên 3 3 7 9 5 Sinh viên 4 9 7 6 5 1.1 Vai trò của cấu trúc dữ liệu  Phân tích ví dụ 1 Môn 1 Môn 2 Môn 3 Môn 4 Sinh viên 1 7 8 5 6 Sinh viên 2 8 6 4 5 Sinh viên 3 3 7 9 5 Sinh viên 4 9 7 6 5 Chương trình quản lý ñiểm ðối tượng dữ liệu Yêu cầu xử lý
Nhập ñiểm
Xuất danh sách ñiểm
Tính ñiểm trung bình
Thống kê tỉ lệ ñậu, hỏng
Các thao tác tìm kiếm theo ñiểm 1.1 Vai trò của cấu trúc dữ liệu  Phương án 1 Dùng mảng một chiều lưu trữ ñiểm của tất cả các sinh viên Môn 1 Môn 2 Môn 3 Môn 4 Sinh viên 1 7 8 5 6 Sinh viên 2 8 6 4 5 Sinh viên 3 3 7 9 5 Sinh viên 4 9 7 6 5 ðối tượng dữ liệu 7 8 5 6 8 6 4 5 3 7 9 5 9 7 6 5 Sinh viên 1 Sinh viên 2 Sinh viên 3 Sinh viên 4 R R[I] = Bảng ñiểm( dòng (I / số môn) , cột (I % số môn) ) 1.1 Vai trò của cấu trúc dữ liệu  Phương án 1 7 8 5 6 8 6 4 5 3 7 9 5 9 7 6 5R R[I] = Bảng ñiểm(I / số môn , I % số môn) int R[16] = {7,8,5,6,8,6,4,5,3,7,9,5,9,7,6,5}; int SO_MON = 4; int SO_SV = 4; void xuat() { for( int I =0 ; I < SO_MON*SO_SV ; I++){ int SV = I / SO_MON; int MON = I % SO_MON; cout<<“Diem mon “<<MON<<“ cua sv “<<SV<<“ = “<<R[I]; } } 1.1 Vai trò của cấu trúc dữ liệu  Phương án 2 Dùng mảng hai chiều lưu trữ ñiểm của tất cả các sinh viên Môn 1 Môn 2 Môn 3 Môn 4 Sinh viên 1 7 8 5 6 Sinh viên 2 8 6 4 5 Sinh viên 3 3 7 9 5 Sinh viên 4 9 7 6 5 ðối tượng dữ liệu Cột 0 Cột 1 Cột 2 Cột 3 Dòng 0 R[0][0]=7 R[0][1]=8 R[0][2]=5 R[0][3]=6 Dòng 1 R[1][1]=8 R[0][1]=6 R[0][1]=4 R[0][3]=5 Dòng 2 R[2][1]=3 R[0][1]=7 R[0][1]=9 R[0][3]=5 Dòng 3 R[3][1]=9 R[0][1]=7 R[0][1]=6 R[0][3]=5 R R[I][J] = Bảng ñiểm( dòng I , cột J ) 1.1 Vai trò của cấu trúc dữ liệu  Phương án 2 int R[4][4] = {{7,8,5,6}, {8,6,4,5}, {3,7,9,5}, {9,7,6,5}}; int SO_MON = 4; int SO_SV = 4; void xuat() { for( int I=0 ; I < SO_SV ; ++I) for( int J=0 ; J < SO_MON ; ++J) cout<<“Diem mon“<<J<<“ cua sv “<<I<<“ = ”<<R[I][J]; } R[I][J] = Bảng ñiểm( dòng I , cột J ) 1.1 Vai trò của cấu trúc dữ liệu  Phương án 3 Dùng mảng một chiều, các phần tử có kiểu cấu trúc nhằm lưu trữ ñiểm của tất cả các sinh viên Môn 1 Môn 2 Môn 3 Môn 4 Sinh viên 1 7 8 5 6 Sinh viên 2 8 6 4 5 Sinh viên 3 3 7 9 5 Sinh viên 4 9 7 6 5 ðối tượng dữ liệu R[0].Mon1=7 R[1].Mon1=8 R[2].Mon1=3 R[3].Mon1=9 R[0].Mon2=8 R[1].Mon2=6 R[2].Mon2=7 R[3].Mon2=7 R[0].Mon3=5 R[1].Mon3=4 R[2].Mon3=9 R[3].Mon3=6 R[0].Mon4=3 R[1].Mon4=5 R[2].Mon4=5 R[3].Mon4=5 R[ I ] lưu trữ tất cả các ñiểm của sinh viên thứ I R 1.1 Vai trò của cấu trúc dữ liệu  Phương án 3 struct DiemSV { int Mon1,Mon2,Mon3,Mon4; }; DiemSV R[4]; int SO_SV = 4; void xuat() { for( int I=0 ; I < SO_SV ; ++I) { cout<<“Diem mon 1 cua sv “<<I<<“ = ”<<R[I].Mon1; cout<<“Diem mon 2 cua sv “<<I<<“ = ”<<R[I].Mon2; cout<<“Diem mon 3 cua sv “<<I<<“ = ”<<R[I].Mon3; cout<<“Diem mon 4 cua sv “<<I<<“ = ”<<R[I].Mon4; } } R[I][J] = Bảng ñiểm( dòng I , cột J ) 1.2 Một số tiêu chí chọn cấu trúc dữ liệu a. CTDL phải phản ánh ñúng thực tế. ðây là yếu tố quyết ñịnh tính ñúng ñắn của bài toán. Cần xem xét trạng thái biến ñổi của dữ liệu nhằm chọn CTDL phù hợp. b. CTDL phải phù hợp với thao tác trên ñó. Tiêu chuẩn này giúp tăng tính hiệu quả của bài toán.Mỗi CTDL có các thao tác ñi tương ứng. Nên chọn CTLD sao cho các thao tác ñược xử lý ñược ñơn giản và tự nhiên. c. CTDL phải tiết kiệm tài nguyên hệ thống. CTDL nên sử dụng tài nguyên vừa ñủ ñể ñảm nhiệm chức năng của nó. 1.3 Kiểu dữ liệu 1.3.1 ðịnh nghĩa kiểu dữ liệu Kiểu dữ liệu T ñược xác ñịnh bởi bộ với: V : tập các giá trị hợp lệ mà ñố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 ñó ví dụ 1: Giả sử có kiểu dữ liệu Alphabet = V = {a – z, A – Z} O = {lấy mã ASCII của ký tự, ñổi ký tự sang dạng chữ hoa, chữ thường} Giả sử có kiểu dữ liệu Number = V = {0..255} O = { + , - , * , / , %} 1.3 Kiểu dữ liệu 1.3.1 ðịnh nghĩa kiểu dữ liệu ví dụ 2: Giả sử có kiểu dữ liệu Contact = V = {Họ và tên, ñịa chỉ, số ñiên thoại} O = {Gán giá trị, so sánh} Giả sử có kiểu dữ liệu ContactList = V = {danh sách các ñối tượng có kiểu Contact} O = { Thêm, xóa, sửa, so sánh, tìm kiếm, sắp xếp} 1.3 Kiểu dữ liệu 1.3.1 ðịnh nghĩa kiểu dữ liệu Các thuộc tính cần quan tâm về kiểu dữ liệu:
Tên kiểu dữ liệu
Miền giá trị
Kích thước lưu trữ
Tập các toán tử, thao tác xử lý tác ñộng lên ñối tượng có kiểu dữ liệu 1.3 Kiểu dữ liệu 1.3.2 Các kiểu dữ liệu cơ bản
Kiểu dữ liệu có thứ tự rời rạc: Số nguyên, ký tự, logic, liệt kê, miền con
Kiểu dữ liệu không rời rạc: số thực Một số kiểu dữ liệu cơ bản trong ngôn ngữ C Tên kiểu dữ liệu Kích thước Miền giá trị char 01 Byte -128 ñến 127 unsign char 01 Byte 0 ñến 255 int 02 byte 0 ñến 65535 long 04 byte -231 ñến 231 -1 unsign long 04 byte 0 ñến 232 - 1 float 04 Byte 3.4E-38 ñến 3.4E38 double 08 byte 1.7E-308 ñến 1.7E308 long double 10 byte 3.4E-4932 ñến 1.1E4932 1.3 Kiểu dữ liệu 1.3.2 Các kiểu dữ liệu có cấu trúc Ví dụ: ðể mô tả thông tin sinh viên cần quan tâm ñến thông tin sau: Mã số sinh viên : 12 ký tự Tên sinh viên : 30 ký tự Ngày sinh : kiểu ngày Nơi sinh : 255 ký tự ðiểm trung bình : Số thực a. Kiểu chuỗi ký tự Chuỗi ký tự trong là một dãy các ký tự liên tiếp kết thúc bằng ký tự có mã ASCII bằng 0. Chuỗi ký tự có tối ña 65535 ký tự Ví dụ: char S[10]; char S[] = “ABC”; char *S = “ABC”; 1.3 Kiểu dữ liệu 1.3.2 Các kiểu dữ liệu có cấu trúc Các thao tác trên chuỗi Tên hàm Công dụng strcmp(s1,s2) So sánh 2 chuỗi s1 và s2 strcpy(dest,src) Sao chép src vào dest strstr(s1,s2) Kiểm tra s2 có nằm trong chuỗi s1 khong? itoa(n,s,c) ðổi số nguyên n thành chuỗi ở dạng cơ số c atoi(sn) ,atof(sf), atol(sl) ðổi 1 chuỗi thành số gets(st) Nhập một chuỗi puts(st) Xuất một chuỗi 1.3 Kiểu dữ liệu b. Kiểu mảng Mảng là kiểu dữ liệu lưu trữ các phần tử cùng kiểu. Mỗi phần tử ñược xác ñịnh bởi một vị trí trí của nó trong mảng. Khai báo mảng 1 chiều []; int a[100]; int a[5]={4, 3, 6, 7, 2}; int a[ ] = {1, 4 , -3, 5, 6}; Khai báo mảng 2 chiều [][]; int a[10][10]; int a[3][2]={{4, 3},{ 6, 7},{2,3}}; 1.3 Kiểu dữ liệu c. Kiểu mẩu tin(cấu trúc) Kiểu mẫu tin là kiểu dữ liệu mà mỗi phần tử của nó là tập hợp các giá trị có thể khác cấu trúc. Kiểu mẫu tin cho phép mô tả các ñối tượng có cấu trúc phức tạp. Khai báo struct { ; ; . }; 1.3 Kiểu dữ liệu d. Kiểu Union Kiểu Union giống như Struct, nhưng các trường dùng chung vùng nhớ. Khai báo union { ; ; . }; 1.4 ðánh giá ñộ phức tạp của thuật toán Phương pháp thực nghiệm:  Cài ñặt thuật toán, chọn các bộ dữ liệu thử, thống kê các thông số nhận ñược. Một số nhược ñiểm:  Phụ thuộc vào ngôn ngữ lập trình dùng ñể cài ñặt  Phụ thuộc vào trình ñộ của người cài ñặt  Việc chọn ra bộ dữ liệu thử ñặc trưng cho tất cả các trường hợp rất khó khăn.  Phụ thuộc vào phần cứng khi thực thi thuật toán Phương pháp hình thức:  ðây là phương pháp ñánh giá ít phụ thuộc vào môi trường cũng như phần cứng.ðánh giá theo hướng xấp xỉ tiệm cận thông qua khái niệm toán học O-lớn O().  Thời gian tính toán sẽ phụ thuộc vào kích thước của dữ liệu ñầu vào(thường gọi là N) và ñánh giá theo 3 trường hợp:  Trường hợp tốt nhất  Trường hợp xất nhất  Trường hợp trung bình 1.4 ðánh giá ñộ phức tạp của thuật toán Sự phân lớp các ñộ phức tạp của thuật toán
ðộ phức tạp là hằng số O(1)
ðộ phức tạp là logN O(logN)
ðộ phức tạp là N O(N)
ðộ phức tạp là NlogN O(NlogN)
ðộ phức tạp là N2 O(N2)
ðộ phức tạp là N3 O(N3)
ðộ phức tạp là 2N O(2N)
ðộ phức tạp là N! O(N!) 1.4 ðánh giá ñộ phức tạp của thuật toán 27 Câu hỏi và thảo luận