Bài giảng Kỹ Thuật lập trình - Chương 2: Giải thuật và cấu trúc dữ liệu - Vũ Thị Hương Giang

CHƯƠNG II. GIẢI THUẬT yÀ CÂU TRÚC DỮ LIỆU • với mỗi bài toán, làm thế nào để: Thiết kê' giải thuật nhằm giải quyết bài toán đó Cài đặt giải thuật bằng một chương trình máy tính 1. Analyze Requirements 6. Doi Hãy thiết kế giải thuật hay Lnhat có thể: đơn giản hóa bài toán đặt ra Sau đó hãy nghĩ tới việc viết mã nguồn 4. Implementation 3. Design Mở đầu Các bài toán thực tế thường phức tạp Hiểu bài toán đặt ra == để giải quyết bài toán, cần làm gì, không cần làm gì. Do đó, phải xác định được: Các dữ liệu liên quan đến bài toán Các thao tác cần thiết để giải quyết bài toán Làm chủ ngôn ngữ lập trình để cài đặt giải pháp thành chương trình máy tính - Tìm kiếm thông tin về 1 nhân viên ví dụ: Bài toán quản một cơ quan • Cần quản lỵ những thông tin nào ? - Thông tin về nhân viên: tên^ngàỵ sinh, số bảo hiemTxa hôi, phòng ban làm việc, ... -ì nhân viên ảo'  lý nhân viên của Cần thực hiện những thao tá'c quán lý nàố ? Tạo ra hồ sơ cho nhân viên mới vào làm Cập nhật một sô\ thong tín trông hồ sơ • Ai được phép thực hiện thao tác nào? ví dụ: tính tổng của n số tự nhiên kể từ m void main() { long n,m,i, sum ; cout << ' vào n ' ; cin << n; cout << ' vào m ' ; cin << m; sum =0; for(i = m ; i < m + n; i++) sum += i; cout << ' Tống = ' <<sum; void main() long n,m , sum ; cout << ' vào n ' ; cin << n; cout << ' vào m ' ; cin << m; sum =(m + m + n) * n / 2; cout << ' Tông = ' <<sum; GIẢI THUẬT Đặc trưng của giải thuật Đầu vào (Input): dữ liệu nào, lấy từ đâu Đầu ra (Output): dữ liệu đầu ra tương ứng với dữ liệu đầu vào và các bước xử lý Độ chính xác (Precision): các bước xử lý được mô tả chính xác Hữu hạn (Finiteness): tạo ra đầu ra sau một số hữu hạn các bước xử lý Đơn trị (Uniqueness): Các kết quả trung gian của từng bước xử lý là duy nhất, không thể thay đổi Tổng quát (Generality): có thể áp dụng cho các bài toán đồng dạng I, Giải thuật Tìm kiếm • Input: Một tập các phần tử dữ liệu có cấu trúc Một khóa cần tìm • Process: - Tìm phần tử có chứa khóa trùng với khóa cần tìm • Output: - Vị trí của phần tử có chứa khóa (nếu có) Phần tử dữ liệu có cấu trúc và khóa • Phần tử dữ liệu có cấu trúc: Dữ liệu khóa Các dữ liệu thành phần khác / Leblanc \ 7 Johnson - So sánh được • Có thể là giá trị của phần tử Khóa: • Có thể là dữ liệu thành phần của phần tử Thường là số • Trích khóa từ các phần tử dữ liệu có cấu trúc: So sánh các dữ liệu thành phần Các giải thuật tìm kiếm phô biến Tìm kiêm tuân tự Các phần tử trong tập đầu vào không được sắp xếp theo khóa tìm kiếm Quá trình xử lý Duyệt tập đầu vào So sánh với khóa cần tìm tới khi tìm thấy khóa hoặc duyệt qua hết tập đầu vào mà chưa tìm thấy  Tìm kiêm nhị phân Các phần tử trong tập đầu vào được sắp xềp theo khóa tìm kiếm Quá trình xử lý So sánh khóa cần tìm với phần tử giữa. Nếu nó nhỏ hơn thì tìm bên trái tập đầu vào. Ngược lại tìm bên phải tập đầu vào. Lặp lại động tác này. 2. Sắp xếp Chương n. Nâng cao vẽ„ giải thuật, câu trúc dữ liệu va ngôn ngữ lập trình I. Giải thuật sắp thứ tự: Đầu vào: tập các phần tử dữ liệu Đầu ra: danh sách có thứ tự tăng (hoặc giảm) theo khóa Phân loại: sắp thứ tự theo khóa ngoài (external sort): tập tin Sắp thứ tự theo khóa chính (internal sort): bộ nhớ Giả thiết: sắp thứ tự theo khóa chính Sắp tăng dần Các giải thuật sắp xếp phổ biến Insertion sort Selection sort Bubble sort Merge sort Quick sort Heap sort 3. Độ phức tạp tính toán I, Giải thuật g(n) = 1 g(n) = log n g(n) = n g(n) = n2 g(n) = n3 g(n) = 2n So sánh với các hàm cơ bản: Constant function Logarithmic function Linear function Quadratic function Cubic function Exponential function Độ tăng của các hàm chung n 1 IgH lì M Ig n n2 n3 2" 1 1 0.00 1 0 1 1 2 10 1 3.32 10 33 100 1000 1024 100 1 6.64 100 664 10,000 1,000,000 1.27 X 1O30 1000 1 9.97 1000 9970 1,000,000 109 1.07 X 1O301 Độ phức tạp tính bằng tiệm cận Tn /(//) f(n) has strictly smaller order of magnitude than g(/ỉ). Definition If lim — - = 0 then: M-*oo g(n) If lim ■ is finite and nonzero then: n->oo £(n) /(/?) has the same order of magnitude as g(n). If lim ' = 00 then: n^oo g(n) f(n) has strictly greater order of magnitude than g(n). Ký pháp f(n)e Bậc của f so với g limn.>00 (f(n)/g(n) o(g(n)) < : nhỏ hơn hẳn 0 0(g(n)) < : nhỏ hơn hoặc bằng a 0(g(n)) = : bằng a 5*0 Đ(g(n)) > : lớn hơn hoặc bằng a # 0 hoặc là 00 Thứ tư tăng dần về đô lởn: 0(1) 0(lg n) O(n) 0(n Ig n) O(n2) 0(n3) O(2n) II. CÂU TRÚC DỮ LIỆU a. Cấu trúc dữ liệu Chương n. Nâng cao ve^ giải thuật, câu trúc dữ liệu và ngôn ngữ lập trình Giải thuật Cấu trúc dữ liệu 1. Các khái niệm cơ bàn Cấu trúc dữ liệu là cách tổ chức và thao tác có hệ thống trên dữ liệu 1 cấu trúc dữ liệu : Mô tả Các dữ liệu cấu thành Mối liên kết về mặt cấu trúc giữa các dữ liệu đó Cung cấp các thao tác trên dữ liệu đó Đặc trưng cho 1 kiểu dữ liệu b. Kiểu dữ liệu Kiểu dữ liệu cơ bản (primitive'data type) Đại diện cho các dữ liêu giồng nhau, không thể phân chia nhỏ hơn được nữa Thường được các ngôn ngữ lập trình định nghĩa san Ví dụ: C/C+ + : int, long, char, boolean, v.v. Thao tác trên các số nguyên: +-*/... Kiểu dữ liệu có câu trúc (structured data type) Được xây dựng từ các kiểu dữ liệu (cơ bản, có cấu trúc) khác Có thể được các ngôn ngữ lập trình định nghĩa sẵn hoặc do lập trình viên tự định nghĩa ADT Operations Interface c. Kiểu dữ liệu trừu tượng (Abstract data type) 1 ADT là' một kiếu dữ liệu đi' kèm ’vớị các thạp tác trên các dữ liệu kiểu đó 1JXDT mô hinhj'ioa các dữ liệu cùng kiểu thẹo cặclíkhông phu thuộc vào ngôn ngữ lập trình hay môi trương’cài đặt Các ngôn ngữ lập trình hướng 'đối tượng cho phép cài đặt ì ADT dưới dạng 1 lớp(class) Mảng (Array) Tập các cặp (index, element) Với mỗi giá trị của index sẽ có một giá trị tương ứng của element • Cài đặt: Sử dụng một không gian nhớ liên tiếp Index: kiểu giá trị phụ thuộc vào ngôn ngữ lập trình c, Java : kiểu sổ nguyên, tăng liên tục, bẳt đầu từ 0 Pascal : kiểu số nguyên Perl: chì số không nhất thiết phải là kiểu số element: kiểu giá trị bất kỳ (kiểu dựng sẵn hoặc kiểu có cấu trúc) Tất cà các phần tử cùng kiểu: màng thuần nhất. NgƯỢc lại: màng không thuần nhất SizeOf(element) . 1 Index: chỉ số chỉ thứ tự Element: phần tử Mảng (Array) Các kiểu mảng Mảng 1 chiều Mảng 2 chiều Thao tác trên mảng: Khởi tạo mảng (create) Tính kích thước (sizeOf) Lấy một phần tử tại một vị trí cụ thế (retrieve) Thay thế giá trị của một phần tử tại một vị trí cụ thể (replace) Bài tập: Khởi tạo giá trị cho mảng y[5] = {3.2,1.2,4.5,6.0,3.6}; m[6][2] = {{1,1},{1,2},{2,1},{2,2},{3,1},{3,2}}; char sl[6] ={ , JaJ, JnJ, *OJ,'i?, J\0J}; //Hoac char sl[] = "DH Bach Khoa Hanoi”; //length = int m[][] = {{1,2,3},{4,5,6}}; int m[4]; m[0] = 1, m[l] = 2; m[2] = 3; m[3] = 4; Danh sách (List) Danh sách : Tập hợp các phần tử cùng kiểu Số lượng các phần tử của danh sách không cố định Phân loại: Danh sách tuyến tính: Có phần tử đầu tiên, phần tử cuổi cùng Thứ tự trước / sau cùa các phần tư được xác định rõ ràng, ví dụ sắp theo thứ tự tăng dần, giảm dần hay thứ tự trong bàng chữ cái Các thao tác trên danh sách phải không làm ảnh hưởng đến trật tự này Danh sách không tuyến tính: các phần tử trong danh sách không được sắp thứ tự CÓ nhiều hình thức lưu trữ danh sách Danh sách kế tiếp: sử dụng vùng các ô nhớ liên tiếp trong bộ nhớ Danh sách liên kết: sử dụng vùng các ô nhớ không liên tiếp trong bộ nhớ Danh sách nối đơn Danh sách nối kép Danh sách nối vòng Danh sách (List) • Thao tác trên danh sách tuyến tính Khởi tạo danh sách (create) Kiếm tra danh sách rỗng (isEmpty) Kiểm tra danh sách đầy (isFull) Tính kích thước (sizeOf) Xóa rỗng danh sách (clear) Thêm một phần tử vào danh sách tại một ví trí cụ thể (insert) Loại bỏ một phần tử tại một vị trí cụ thể khỏi danh sách (remove) Lấy một phần tử tại một vị trí cụ thể (retrieve) Thay thế giá trị của một phần tử tại một vị trí cụ thể (replace) Duyệt danh sách và thực hiện một thao tác tại các vị trí trong danh sách (traverse) So sánh các hình thức lưu trữ danh sách Sử dụng vùng các ô nhớ liên tiếp: thích hỢp khi Sử dụng vùng các ô nhớ khống liến tiếp: thích hỢp khi - Kích thước từng phần tử là rất nhỏ Kích thước của cả danh sách (số phần tử) đã biết khi lập trình Có ít sự thêm vào hay loại bỏ ở giữa danh sách Hình thức truy cập trực tiếp là quan trọng - Kích thước từng phần tử là lớn Kích thước của danh sách không biết trước Có nhiều sự thêm vào, loại bỏ, hay sắp xếp cac phần tứ trong danh sách Cấu trúc dữ liệu đệ quy • Đôi khi LTV cần đến các cấu trúc dữ liệu đệ quy (cấu trúc chứa chính nó) • Ví dụ: từ điển điện tử, mỗi từ trong từ điển được biểu diên bằng một cấu trúc dữ liệu, trong đó, mục từ đồng nghĩa cũng là từ có cùng cấu trúc C: làm thê' nào để một cấu trúc có thể chứa chính nó Trong ngôn ngữ lập trình c, một cấu trúc (struct) không thể chứa chính nó Nhưng một cấu trúc có thể chứa con trỏ trỏ đến cấu trúc cùng kiểu struct silly_struct { /* This doesn't work */ struct silly_struct si; in struct good_struct { /* This does work */ struct *good_struct s2; }; Danh sách liên kết: cách biểu diễn đơn giản cấu trúc dữ liệu đệ quy • ví dụ: cần đọc các dòng trong một tệp tin, nhưng không biết cần đọc bao nhiêu dòng -> cần một cấu trúc có thê’ tự mở rộng head of list information information information nextptr. nextptr nextptr= NULL 30 sổ địa chỉ cài đặt bằng danh sách nối đơn typedef struct list { char name[MAXLEN]; char address[MAXLEN]; char phone[MAXLEN]; struct list *next; } ADDRESS; ADDRESS *hol= NULL; /* Set the head of the list */ Cây nhị phân (binary tree) Định nghĩa cây rỗng Hoặc có một nút gọi là gốc (root) và 2 cây con gọi là cây con trái và cây con phải Ví dụ: Cây rỗng: Cây có 1 nút: là nút gốc Cây có 2 nút: Phép duyệt cây Duyệt qua từng nút của cây (mỗi nút 1 lần) Cách duyệt: Thứ tự trước (preorder hay NLR) Thứ tự giữa (inorder hay LNR) Thứ tự sau (postorder hay LRN) Kết quả: Kết quả: Kết quả: Các loại cây nhị phân • cây nhị phân liên kết - Mỗi nút trên cây liên kết đến nút gốc của cây con bên trái và bên phải Cây nhị phân tìm kiếm (BST) Khóa của nút gốc lớn (hay nhỏ) hơn khóa của tất cả các nút của cây con bên trái (hay bên phải) Các cây con (bên trái, phải) là BST Cây cân bằng (AVL) - BST - Tại nút bất kỳ, chiều cao nhánh trái và nhánh phải chênh nhau không quá 1. Bảng băm (hash table) Bảng băm Bảng Vị trí của 1 phần tử được tính bằng hàm băm Hàm băm: Đầu vào: giá trị cần băm (giá trị phần tử đầu vào) Đầu ra: giá trị băm (khóa, giúp xác định vị trí của giá trị cần băm) Có khả năng trùng khóa (đụng độ), ví dụ f(x) = X % m; Cần tìm hàm băm sao cho khả năng đụng độ là nhỏ nhất (luôn luôn tìm ra đúng giá trị phần tử đầu vấo khi sử dụng khóa) Đảm bảo 0(1) Ví dụ: f(x) = X % m; f('abc') = (char_index('a')*base_number2 + char_index('b')*base_numberl + char_index('c')*base_numberO) % hash_size ví dụ dùng bảng băm Không có