Giáo trình Cấu trúc dữ liệu và Giải thuật - Chương 1-6 - Hồ Sĩ Đàm

CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬTGiảng viên : Hồ Sĩ ĐàmBộ môn Mạng và truyền thông máy tínhTrường ĐH Công Nghệ - ĐH Quốc Gia Hà Nội Email damhs@vnu.edu.vn Mob. 0913580373 Giới thiệu môn họcCung cấp : - Các kiến thức cơ bản về cấu trúc dữ liệu và thuật toán; - Kĩ năng xây dựng, lựa chọn các cấu trúc dữ liệu và các thuật toán hợp lí. Giới thiệu môn họcChương I : Thuật toán và phân tích thuật toánChương II : Đệ quyChương III : Các dữ liệu có cấu trúc Chương IV : Danh sáchChương V : CâyChương VI * : Bảng bămChương VII : Sắp xếpChương VIII : Tìm kiếmChương IX : Đồ thịChương X : Các kỹ thuật thiết kế thuậ toán Tài liệu tham khảoThomas H. Cormen, Introduction to Algorithms, MIT Press, 1990R. Sedgevick,Algorithms Addison- Wesley, Bản dịch tiếng Việt: Cẩm nang thuật toán ( tập 1, 2).Hồ Sĩ Đàm, Nguyễn Việt Hà, Bùi Thế DuyĐinh Mạnh Tường, Đỗ Xuân LôiCHƯƠNG I: THUẬT TOÁN VÀ PHÂN TÍCH THUẬT TOÁNGiải bài toán trên máy tínhMô hình dữ liệuCấu trúc dữ liệuBài toán và thuật toán 1 Giai bài toán trên máy tínhBước 1. Xác định bài toán -Tập Input và OutputBước 2. Lựa chọn/ thiết kế thuật toána) Lựa chọn/ thiết kế thuật toánGiải bài toán  nhiều thuật toánKhông gian ? Thời gian ?; Cài đặt ?	b) Diễn tả thuật toán Input: Hai số nguyên dương a và b; Output: q và r : a= bq+r.  Ý tưởng: 	- Nếu a b thì a giảm đi b và q tăng lên 1. Lặp cho đến khi a Max thì thay giá trị Max= ai.4. Bài toán và thuật toán4. Bài toán và thuật toán4.3. Mô tả thuật toán a) Cách liệt kêBước 1. Nhập N và dãy a1, ..., anBước 2. Đặt Max = a1, i = 2;Bước 3. Nếu i > N thì đến B. 5;Bước 4.	4.1. N ếu ai > Max thì Max = ai.	4.2. Đặt i=i+1 rồi quay B.3;Bước 5. Đưa ra Max rồi kết thúc. 4. Bài toán và thuật toánb) Sơ đồ khốiDùng: Ovan, Chữ nhật, Hìn thoi,Mũi tên,4. Bài toán và thuật toánc) Ngôn ngữ điều khiểnDùng các ký hiệu và quy tắcCách thiết lập thứ tự các thao tác cấu trúc điều khiển ( 03 ) BIỂU DIỄN BẰNG CẤU TRÚC ĐIỀU KHIỂNTrong khi m  n thì lặp lại khối sau:Cho tới khi m = n thì tuyên bố USCLN chính là giá trị chung của m và nInt Horner(int a[],int x){ int result = a[n]; for (i=n-1; i>=0;--1) result= result*x+a[i]; return result;}Chương trình trong C++Điều chỉnh lại giá trị của m và n Nếu m > n thì   Nếu ngược lại thì   Bớt m đi một lượng là nBớt n đi một lượng là m4. Bài toán và thuật toán4.4. Các đặc trưng chính của thuật toána)Tính kết thúc (tính đóng)b)Tính xác định (đơn nghĩa)	Có đúng một thao tác để được thực hiện hoặc dừng4. Bài toán và thuật toánc)Tính chi tiếtPhụ thuộc vào đối tượng thực hiệnd)Tính phổ dụng	với input thay đổie) Đại lượng vào f) Đại lượng ra4. Bài toán và thuật toáng) Tính hiệu quảThời gian: Tốc độ xử lý Không gian: Dung lượng lưu trữ4. Bài toán và thuật toán4.5. Độ phức tạp thuật toána) Lựa chọn thuật toánDễ hiểu, dễ cài đặt và dễ ghi chép ? Sử dụng các tài nguyên hiệu quả.? đặc tính của bài toán Phân tích theo kinh nghiệmThực hiện và kết luận  dễ mắc lỗi Kích thước dữ liệu là quan trọng: T(n)4. Bài toán và thuật toánb) Ký phápGiả sử T(n) là thời gian thực hiện TT và f(n), g(n), h(n) là các hàm xác định dương. Hàm Theta lớn: T(n) là hàm Theta lớn của g(n): T(n) =Θ(g(n))nếu  các hằng số dương c1 ,c2 ,n0 sao cho với mọi n>= n0 : c1 g(n) = n0 T(n) >= c.g(n)4. Bài toán và thuật toán Hàm O lớn: T(n) hàm Omega lớn của g(n), T(n) =O (g(n)) nếu  c và n0 sao cho với mọi n>= n0 : T(n) =1, ta có T(n)= n2+1 0 và n0 >0 để T(n) = n0.	Đặt c=c0.c1 ta có điều cần CM 4. Bài toán và thuật toánQuy tắc lấy Max	Nếu P có T(n)= O( f(n)+g(n)) thì P có độ phức tạp là O( max ( f(n), g(n))).CM: T(n) = O( f(n)+g(n)) nên tồn tại n0>0 và c>0 để T(n) = n0 vậy T(n) =n0.	Từ đó suy điều cần CM. 4. Bài toán và thuật toánQuy tắc cộng	Nếu P1 có T1 (n) = O( f(n) và P2 có T2(n)= O(g(n)), khi đó: T1(n) +T2(n) = O(f(n) +g(n)).CM: Vì T1(n)= O(f(n)) nên  các hàng số c1 và n1 sao cho T(n) = n1.	Vì T2(n) =O(g(n)) nên  các hàng số c2 và n2 sao cho T(n) = n2	Chọn c= max (c1,c2) và n0 = max(n1,n2) ta có n: n n>= n0:	T(n) = T1(n) + T2(n) =0 và nk >0 để k(n) = nkcT>=0 và nT >0 để T(n) = nT	Vậy với mọi n >= max(nT,nk) ta có k(n)T(n) Rear thì EmptyQueue2. Biểu diễn danh sách trong máy tínhQueue vòng trònCác phần tử xếp quanh vòng tròn theo một hướng. Các phần tử nằm trên cung tròn từ vị trí Front đến Rear là thuộc Queue. 2. Biểu diễn danh sách trong máy tínhKhi thêm :dịch chuyển chỉ số Rear theo vòng tròn 1 ví trí rồi đặt giá trị cần thêm vào đó.- Khi lấy ra : lấy phần tử có chỉ số là Front rồi dịch chuyển chỉ số Front theo vòng tròn 1 vị trí. VnVn-1V2V12. Biểu diễn danh sách trong máy tínhĐể cài đặt : 	(i) Một phương tiện để chia bộ nhớ thành các nút, mỗi nút có phần lưu trữ data, phần lưu trữ các liên kết (con trỏ) và cách cài đặt cho con trỏ 	(ii) Cài đặt các thao tác để truy nhập giá trị (cả data và pointer). 	(iii) Một phương tiện nào đó để “đánh dấu” vùng bộ nhớ3. Một số nhận xétCài đặt danh sách bằng mảng tạo ra hạn chế:Độ dài của danh sách.Kiểm tra “tràn” và “rỗng” khi thực hiện chèn và xóa.Khi thực hiện “chèn“ và “Xóa” đều phải thực hiện phép “dịch chuyển”.3. Một số nhận xétTrong các cấu trúc DS, để thực hiện các thao tác cơ bản cần các thao tác tối thiểu:Định vị phần tử đầu tiên của DSCho trước vị trí của một phần tử bất kì trong DS, xác định được phần tử tiếp theo.4. Kiểu dữ liệu con trỏ và việc cấp phát/thu hồi bộ nhớ độngĐể khắc phục, cầnMột thủ tục tiền định để cấp phát bộ nhớ ( New (p) trong TP, trong C có các hàm Void * calloc, * void maloc ) và một thủ tục để giải phóng bộ nhớ ( Dispose(p) trong Tp và hàm Void Free trong C)Dùng biến con trỏ để truy cập đến vùng nhớ này. CHƯƠNG V CẤU TRÚC DỮ LiỆU BẢNG BĂMBảng băm mở	1.1. Bảng băm	1.2. Hàm băm	1.3. Xung đột	1.4. Một số hàm băm thông dụngBảng băm đóng	2.1. Băm lại tuyến tính.	2.2. Băm lại bình phương	2.3. Băm lại bằng cách tạo vùng mớiCHƯƠNG VI: CẤU TRÚC DỮ LiỆU BẢNG BĂM1. Bảng băm mởBảng băm (Hash Table): - Mảng B gồm m phần tử -Lưu trữ chỉ số định vị phần tử dữ liệu có khóa phân biệt thuộc tập số nguyên { 0,1,2m-1}1. Bảng băm mởHàm băm (Hash function): H(x) cho giá trị là một chỉ số phần tử của B1. Bảng băm mởXung đột (collision): x1x2 nhưng H(x1)=H(x2)1. Bảng băm mởXung đột:1. Bảng băm mởXung đột:Giải quyết: liên kết các danh sách có các khóa khác nhau nhưng có cùng giá trị hàm băm thành một danh sáchliên kết trong bẳng băm B sẽ trỏ tới danh sách đầu tiên. CHƯƠNG VI: CẤU TRÚC DỮ LiỆU BẢNG BĂM1. Bảng băm mởMột số hàm băm thông dụng:Hàm cắt bỏ bỏ bớt một phần nào đó của khóa.Ví dụ: x=842615, bỏ bớt chẳng hạn các chữ số hàng lẻ (1,3,5), số còn lại sẽ là 821. Vậy H(x) = H(842615) = 821.Nhận xét: khó có phân bố đều.Hàm gấp chia số nguyên đó thành một số đoạn tùy chọn, sau đó kết hợp Ví dụ: Số các hàng lẻ: 465 và số các hàng chẵn: 821, vậy H(x)=465+821=1286.Nhận xét: Tính chất thứ hai có thể thỏa mãn tốt hơn1. Bảng băm mởHàm phần dư của phép chia x/mNên chọn m là số nguyên tố. Nhận xét: Các cách lấy phần dư cho khả năng tránh hiện tượng xung độtCHƯƠNG VI: CẤU TRÚC DỮ LiỆU BẢNG BĂM2. Bảng băm đóngBảng băm mở: chỉ dùng để lưu trữ các liên kết trỏ đến các thành phần dữ liệu có khóa tương ứng. Bảng băm đóng: bảng băm mà mỗi thành phần của nó lưu trữ chính các thành phần dữ liệu. CHƯƠNG VI: CẤU TRÚC DỮ LiỆU BẢNG BĂM2. Bảng băm đóngCác phương pháp xử lý:a) Băm lại tuyến tínhHi (x) = (H(x)+i) mod mNhận xét Các giá trị hàm băm xếp thành từng đoạn con, nên việc tìm kiếm ví trí rỗng sẽ rất chậm. CHƯƠNG VI: CẤU TRÚC DỮ LiỆU BẢNG BĂM2. Bảng băm đóng2. Bảng băm đóngb) Băm lại bình phương	Hi(x) = ( H(x)+i2) mod m 2. Bảng băm đóngc) Băm lại bằng cách tạo vùng mớiNgoài bảng B cần tạo ra một vùng không gian mới