Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 1: Tổng quan về Cấu trúc dữ liệu và giải thuật - Ngô Quang Thạch

CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT NGÔ QUANG THẠCH Email: thachnq@gmail.com ĐT: 01273984123 CHƯƠNG 1: Tổng quan về CTDL và GT Khái niệm giải thuật Các kiểu dữ liệu cơ bản Các kiểu dữ liệu trừu tượng Các cấu trúc dữ liệu cơ bản Mối quan hệ giữa CTDL và giải thuật Giải bài toán bằng phần mềm 1 • Xác định bài toán 2 • Tìm cấu trúc dữ liệu biểu diễn bài toán 3 • Tìm thuật toán 4 • Lập trình 5 • Kiểm thử phần mềm 6 • Tối ưu chương trình Giải thuật Giải thuật hay Thuật toán dùng để chỉ phương pháp hay cách thức (method) để giải quyết vấn đề. Thuật toán là một chuỗi hữu hạn các lệnh, mỗi lệnh có một ngữ nghĩa rõ ràng và có thể được thực hiện với một lượng hữu hạn tài nguyên trong một khoảng hữu hạn thời gian. Giải thuật có thể được minh họa bằng ngôn ngữ tự nhiên (natural language), bằng sơ đồ (flow chart) hoặc bằng mã giả (pseudo code)  Các tính chất của giải thuật Hữu hạn (finiteness): giải thuật phải luôn luôn kết thúc sau một số hữu hạn bước. Xác định (definiteness): mỗi bước của giải thuật phải được xác định rõ ràng và phải được thực hiện chính xác, nhất quán. Hiệu quả (effectiveness): các thao tác trong giải thuật phải được thực hiện trong một lượng thời gian hữu hạn. – Ngoài ra một giải thuật còn phải có đầu vào (input) và đầu ra (output). Ngôn ngữ tự nhiên Giải thuật giải PT bậc nhất dạng ax + b = 0 như sau: Bước 1: Nhận giá trị của các tham số a, b Bước 2: Xét giá trị của a xem có bằng 0 hay không? Nếu a = 0 thì làm bước 3, nếu a khác không thì làm bước 4. Bước 3: (a bằng 0) Nếu b bằng 0 thì ta kết luận phương trình vô số nghiệm, nếu b khác 0 thì ta kết luận phương trình vô nghiệm. Bước 4: ( a khác 0) Ta kết luận phương trình có nghiệm x = -b/a Flowchart Flow chart thể hiện nét phát thảo cấu trúc căn bản và tính logic của chương trình Các ký hiệu sử dụng trong Flowchart TT KÝ HIỆU DIỄN GIẢI 1 Bắt đầu chương trình, Kết thúc chương trình 2 Luồng xử lý 3 Điều khiển lựa chọn 4 Nhập 5 Xuất 6 Xử lý, tính toán hoặc gán 7 Trả về giá trị (return) 8 Điểm nối liên kết tiếp theo Ví dụ: Nhập vào 3 Bắt đầu số nguyên a, b, c và xuất ra màn hình a, b, c với giá trị a=a*a bình phương b=b*b của mỗi số. c=c*c a, b, c Kết thúc Ví dụ: If else Sai Biểu thức Đúng điều kiện Cấu trúc lặp for / while (Kiểm tra điều kiện trước khi lặp) Thực hiện liên tục 1 lệnh hay tập lệnh với số Sai Điều kiện Đúng lần lặp dựa vào lặp điều kiện. Lặp sẽ kết thúc khi điều kiện không thỏa. Cấu trúc lặp do while (Thực hiện lặp trước khi kiểm tra điều kiện) Thực hiện liên tục 1 lệnh hay tập lệnh với số lần lặp dựa vào điều kiện. Lặp sẽ kết thúc khi điều kiện không thỏa. Sai Điều kiện Đúng lặp Ví dụ Giải và biện luận phương trình: ax+b=0. Bắt đầu a, b Sai Đúng a=0 Sai Đúng b=0 x=-b/a Vô nghiệm Vô số nghiệm Kết thúc Mã giả (pseudocode) Một cách khác để diễn tả giải thuật là sử dụng mã giả pseudocode . Giả lập, thường là dễ hiểu, không chi tiết đến các kỹ thuật lập trình . Ở cấp độ hết sức tổng quát: gần ngôn ngữ tự nhiên . Hoặc rất chi tiết: như dùng ngôn ngữ lập trình Pascal, C, Một đoạn mã giả của phương trình bậc hai if Delta > 0 then begin x1=(-b-sqrt(delta))/(2*a) x2=(-b+sqrt(delta))/(2*a) xuất kết quả : phương trình có hai nghiệm là x1 và x2 end else if delta = 0 then xuất kết quả : phương trình có nghiệm kép là -b/(2*a) else {trường hợp delta < 0 } xuất kết quả : phương trình vô nghiệm Mã giả của bubble sort Giải thuật 1 Giải thuật 2 Algorithm Bubble sort Algorithm Bubble sort Input: The list A of n elements is given Input: The list A of n elements is given Output: The list A is sorted Output: The list A is sorted 1. loop for n time 1. for outter in 0..(n-2) 1.1. for inner in 0..(n-2- outter) 1.1. for each pair in the list 1.1.1. if Ainner+1 < Ainner 1.1.1. if it is not in ordered 1.1.1.1. swap Ainner, Ainner+1 1.1.1.1. exchange them End Bubble sort End Bubble sort Giải thuật bằng ngôn ngữ lập trình Giải thuật 1: Pascal Giải thuật 2: C++ procedure BubbleSort(var A: list); void BubbleSort(list A) var i,j: int; { begin int i, j; for i := 1 to n-1 do for (i=0; i < n-2; i++) for j := 1 to (n-1-i) do for (j=0; j<(n-2-i); j++) if A[j+1] < A[j] then if (A[j+1] < A[j]) { begin tmp = A[j]; tmp := A[j]; A[j] = A[j+1]; A[j] := A[j+1]; A[j+1] = tmp; A[j+1] := tmp; } end; } end; Định nghĩa kiểu dữ liệu Kiểu dữ liệu T được xác định bởi một bộ với: . V: là tập các giá trị hợp lệ để đối tượng kiểu T có thể lưu trữ . O: là tập các thao tác xử lý để có thể thực hiện trên các đối tượng kiểu T đó Ví dụ . Kiểu số nguyên SN= với . Vi = {-3276832767} . Oi = {+, -, *, /, mod, div} Khái niệm kiểu dữ liệu Máy tính chỉ lưu trữ dữ liệu ở dạng nhị phân => Để mô tả các loại dữ liệu để máy hiểu phải đưa ra khái niệm về mặt hình thức để lưu trữ và được gọi là “Kiểu dữ liệu” Các kiểu dữ liệu cơ sở: . Kiểu số nguyên: 1 byte, 2 bytes, 4 bytes . Kiểu số thực: 4 bytes, 6 bytes, 8 bytes, 10 bytes . Kiểu ký tự: 1 byte, 2 bytes . Kiểu chuỗi ký tự: Có kích thước tùy vào ngôn ngữ lập trình . Kiểu lý luận: 1 byte Các kiểu dữ liệu cơ bản Loại dữ liệu Tên kiểu Số ô nhớ Miền giá trị Kí tự char 1 byte － 128 .. 127 unsigned char 1 byte 0 .. 255 Số nguyên int 2 byte － 32768 .. 32767 unsigned int 2 byte 0 .. 65535 short 2 byte － 32768 .. 32767 long 4 byte － 215 .. 215 – 1 Số thực float 4 byte ± 10 -37 . . ± 10 +38 double 8 byte ± 10 -307 . . ± 10 +308 Các kiểu dữ liệu có cấu trúc Tùy vào từng ngôn ngữ lập trình, thường có các loại sau: . Kiểu chuỗi ký tự . Kiểu mảng . Kiểu bản ghi hay mẫu tin Các kiểu dữ liệu có cấu trúc Kiểu chuỗi ký tự: là kiểu dữ liệu có cấu trúc đơn giản nhất và thường các NNLT đều định nghĩa nó như một kiểu cơ bản. Trong C các hàm xử lý chuỗi được đặt trong thư viện string.lib. VD: char S[10] ;// chuỗi ký tự S có chiều dài tối đa là 10 (kể cả ký tự kết thúc) char S[] = ”ABCDEF” ; char *S = “ABCDEF”; Các kiểu dữ liệu có cấu trúc Kiểu mảng: là kiểu dữ liệu trong đó mỗi phần tử của nó là một tập hợp có thứ tự các giá trị có cùng cấu trúc được lưu trữ liên tiếp nhau trong bộ nhớ. Mảng một chiều : []; Mảng nhiều chiều : [] [<Số phần tử 2>].; Kiểu mảng Mảng 1 chiều Pt[1] Pt[2] Pt[n] Mảng 2 chiều Pt[1][1] Pt[1][2] Pt[1][n] Pt[2][1] Pt[2][2] Pt[2][n] Pt[m][1] Pt[m][2] Pt[m][n] Kiểu mẫu tin Kiểu mẫu tin: Kiểu mẫu tin cũng tương tự như mảng nhưng 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 thường được dùng để mô tả những đối tượng có cấu trúc phức tạp. Ví dụ : struct PERSON { char Hoten[]; int NamSinh; char NoiSinh[]; char GioiTinh; // 0:Nữ, 1: Nam char DiaChi[]; } Các kiểu dữ liệu có cấu trúc Là kiểu tạo ra từ các thành phần cơ sở khác nhau bằng cách kết hợp theo nguyên tắc nào nó  struct. Cú pháp khai báo struct struct tên_cấu_trúc { //mô tả các thành phần }; struct date { int ngay; int thang; int nam; }; Kiểu bản ghi Bảng thông tin cá nhân Họ tên Giới tính Ngày sinh Điện thoại Địa chỉ Nguyễn Thị A Nữ 21/7/1995 0987828601 TP. Quảng Ngãi Nguyễn Văn B Nam 12/9/1995 0987828603 TP. Quảng Ngãi Nguyễn Văn C Nam 02/5/1995 0987828602 TP. Quảng Ngãi Các kiểu dữ liệu khác Kiểu dữ liệu con trỏ (Pointer) . Kiểu con trỏ là kiểu dữ liệu cơ sở dùng lưu địa chỉ của một đối tượng dữ liệu khác. . Biến thuộc kiểu con trỏ Tp là biến mà giá trị của nó là địa chỉ của một vùng nhớ ứng với một biến kiểu T, hoặc là giá trị NULL . Cú pháp định nghĩa dữ liệu kiểu con trỏ typedef * ; Kiểu dữ liệu tập tin (File) Biến kiểu con trỏ Ví dụ 1: Khai báo 2 biến a,b có kiểu int và 2 biến pa, pb là 2 biến con trỏ kiểu int. int a, b, *pa, *pb; Ví dụ 2: Khai báo biến f kiểu float và biến pf là con trỏ float float f, *pf; Các thao tác trên con trỏ  a. Gán địa chỉ của biến cho biến con trỏ . Cú pháp: =& Giải thích: Ta gán địa chỉ của biến Tên biến cho con trỏ Tên biến con trỏ. Ví dụ: Gán địa chỉ của biến a cho con trỏ pa, gán địa chỉ của biến b cho con trỏ pb. pa=&a; pb=&b;  b. Nội dung của ô nhớ con trỏ chỉ tới . Để truy cập đến nội dung của ô nhớ mà con trỏ chỉ tới, ta sử dụng cú pháp: * Cấu trúc dữ liệu Là một cách tổ chức và lưu trữ dữ liệu hợp lý để sử dụng một cách hiệu quả, Tập các thao tác để truy cập các thành phần dữ liệu. Ví dụ: . Mảng (Array) . Danh sách liên kết (Linked List) . Hàng đợi (Queue) . Ngăn xếp (Stack) . Cây (Tree) . Mối quan hệ giữa CTDL và giải thuật • Khi có cấu trúc dữ liệu tốt và giải thuật phù hợp thì xây dựng chương trình chỉ phụ thuộc thời gian. • Một chương trình máy tính chỉ hoàn thiện khi có đầy đủ cấu trúc dữ liệu và giải thuật. CTDL + Thuật toán = Chương trình Các yếu tố khi xây dựng chương trình Xây dựng chương trình cần chú ý đến các yếu tố: Tổ chức biểu diễn các đối tượng thực tế Xây dựng các thao tác xử lý dữ liệu Tổ chức biểu diễn các đối tượng thực tế Các thành phần dữ liệu thực tế đa dạng, phong phú và thường chứa đựng những quan hệ nào đó với nhau, do đó trong mô hình tin học của bài toán, cần phải tổ chức, xây dựng các cấu trúc thích hợp nhất sao cho vừa có thể phản ánh chính xác các dữ liệu thực tế này, vừa có thể dễ dàng dùng máy tính để xử lý. ==> Công việc này được gọi là xây dựng cấu trúc dữ liệu cho bài toán Xây dựng các thao tác xử lý dữ liệu Từ những yêu cầu xử lý thực tế, cần tìm ra các giải thuật tương ứng để xác định trình tự các thao tác máy tính phải thi hành để cho ra kết quả mong muốn, đây là bước xây dựng giải thuật cho bài toán Ví dụ Một chương trình quản lý điểm thi của sinh viên cần lưu trữ các điểm số của sinh viên. Do mỗi sinh viên có điểm số ứng với những môn học khác nhau nên dữ liệu có dạng bảng như sau: Sinh viên Môn 1 Môn 2 Môn 3 Môn 4 SV 1 7 8 9 10 SV 2 5 6 7 8 SV 3 6 7 8 9 Chọn phương án cho bài toán quản lý điểm Phương án: Dùng mảng để giải quyết bài toán . Mảng 1 chiều . Mảng 2 chiều Dùng các phương án khác . Thiết kế cấu trúc, bản ghi . Các tiêu chuẩn đánh giá cấu trúc dữ liệu Phản ánh đúng thực tế của bài toán Phù hợp với các thao tác dữ liệu Tiết kiệm tài nguyên hệ thống (bộ nhớ trong) Các tiêu chuẩn đánh giá cấu trúc dữ liệu Phản ánh đúng thực tế : Đây là tiêu chuẩn quan trọng nhất, quyết định tính đúng đắn của toàn bộ bài toán. Cần xem xét kỹ lưỡng cũng như dự trù các trạng thái biến đổi của dữ liệu trong chu trình sống để có thể chọn cấu trúc dữ liệu lưu trữ thể hiện chính xác đối tượng thực tế. Các tiêu chuẩn đánh giá cấu trúc dữ liệu Ví dụ: Một số tình huống chọn cấu trúc lưu trữ sai : - Chọn một biến số nguyên int để lưu trữ tiền thưởng bán hàng (được tính theo công thức tiền thưởng bán hàng = trị giá hàng * 5%), do vậy sẽ làm tròn mọi giá trị tiền thưởng gây thiệt hại cho nhân viên bán hàng. =>Trường hợp này phải sử dụng biến số thực để phản ánh đúng kết quả của công thức tính thực tế. - Trong trường trung học, mỗi lớp có thể nhận tối đa 28 học sinh. Lớp hiện có 20 học sinh, mỗi tháng mỗi học sinh đóng học phí $10. Chọn một biến số nguyên unsigned char ( khả năng lưu trữ 0 - 255) để lưu trữ tổng học phí của lớp học trong tháng, nếu xảy ra trường hợp có thêm 6 học sinh được nhận vào lớp thì giá trị tổng học phí thu được là $260, vượt khỏi khả năng lưu trữ của biến đã chọn, gây ra tình trạng tràn, sai lệch. Các tiêu chuẩn đánh giá cấu trúc dữ liệu Phù hợp với các thao tác trên đó: Tiêu chuẩn này giúp tăng tính hiệu quả của đề án: việc phát triển các thuật toán đơn giản, tự nhiên hơn; chương trình đạt hiệu quả cao hơn về tốc độ xử lý. Các tiêu chuẩn đánh giá cấu trúc dữ liệu Ví dụ: Một tình huống chọn cấu trúc lưu trữ không phù hợp:  Cần xây dựng một chương trình soạn thảo văn bản, các thao tác xử lý thường xảy ra là chèn, xoá sửa các ký tự trên văn bản.  Trong thời gian xử lý văn bản, nếu chọn cấu trúc lưu trữ văn bản trực tiếp lên tập tin thì sẽ gây khó khăn khi xây dựng các giải thuật cập nhật văn bản và làm chậm tốc độ xử lý của chương trình vì phải làm việc trên bộ nhớ ngoài.  Trường hợp này nên tìm một cấu trúc dữ liệu có thể tổ chức ở bộ nhớ trong để lưu trữ văn bản suốt thời gian soạn thảo.  LƯU Ý : Đối với mỗi ứng dụng , cần chú ý đến thao tác nào được sử dụng nhiều nhất để lựa chọn cấu trúc dữ liệu cho thích hợp. Các tiêu chuẩn đánh giá cấu trúc dữ liệu Tiết kiệm tài nguyên hệ thống: Cấu trúc dữ liệu chỉ nên sử dụng tài nguyên hệ thống vừa đủ để đảm nhiệm được chức năng của nó. Thông thường có 2 loại tài nguyên cần lưu tâm nhất : CPU và bộ nhớ. Nếu tổ chức sử dụng đề án cần có những xử lý nhanh thì khi chọn cấu trúc dữ liệu yếu tố tiết kiệm thời gian xử lý phải đặt nặng hơn tiêu chuẩn sử dụng tối ưu bộ nhớ, và ngược lại. Các tiêu chuẩn đánh giá cấu trúc dữ liệu Ví dụ: Một số tình huống chọn cấu trúc lưu trữ lãng phí: - Sử dụng biến int (2 bytes) để lưu trữ một giá trị cho biết tháng hiện hành . Biết rằng tháng chỉ có thể nhận các giá trị từ 1-12, nên chỉ cần sử dụng kiểu char (1 byte) là đủ. - Để lưu trữ danh sách học viên trong một lớp, sử dụng mảng 50 phần tử (giới hạn số học viên trong lớp tối đa là 50). Nếu số lượng học viên thật sự ít hơn 50, thì gây lãng phí. Trường hợp này cần có một cấu trúc dữ liệu linh động hơn mảng- ví dụ danh sách liên kết Một số câu lệnh cơ bản trong C Tự đọc tài liệu tham khảo Bài tập 1: Vẽ biểu đồ luồng tiến trình cho việc tính sau: Tính tổng: S = 1 + 2 + 3 +...+ n , với n>0 Bài tập 2: Vẽ biểu đồ luồng tiến trình cho việc tính sau:  = + + + + , với n>0 Bài tập 3 Tìm cấu trúc dữ liệu lưu trữ 2 số nguyên lớn a, b Số nguyên lớn ở đây là số có thể có đến vài nghìn chữ số Ví dụ: a=999999999999999999999999999999999999999999 999999999999999999999999999999999999999999999 999999999999999999999999999999999999999999999 b=888888888888888888888888888888888888888888 888888888888888888888888888888888888888888888 888888888888888888888888888888888888888888888 Bài tập 4 Tìm phương án tổ chức cấu trúc dữ liệu cho thời khoá biểu của sinh viên: Tiết Thứ 2 Thứ 3 Thứ 4 Thứ 5 Thứ 6 Thứ 7 CN Tiết 1 Tiết 2 Tiết 3 Tiết 4 Tiết 5 Tiết 6 Tiết 7 Tiết 8 Tiết 9 Tiết 10