Bài giảng Cấu trúc dữ liệu và Giải thuật - Chương 1: Tổng quan về CTDL> - Trần Minh Thái

CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬTTrần Minh TháiEmail: minhthai@huflit.edu.vnWebsite: www.minhthai.edu.vn 1Nội dungChương 1. Tổng quan về giải thuật & cấu trúc dữ liệu1.1. Vai trò của cấu trúc dữ liệu1.2. Các tiêu chuẩn đánh giá cấu trúc dữ liệu1.3. Kiểu dữ liệu1.3.1. Định nghĩa kiểu dữ liệu1.3.2. Các kiểu dữ liệu cơ bản1.3.3. Các kiểu dữ liệu có cấu trúc1.3.4. Một số kiểu dữ liệu có cấu trúc cơ bản1.4. Đánh giá độ phức tạp giải thuật2Nội dungChương 2. Tìm kiếm và sắp xếp2.1. Nhu cầu tìm kiếm, sắp xếp dữ liệu trong một hệ thống thông tin2.2. Các giải thuật tìm kiếm nội2.2.1. Tìm kiếm tuyến tính2.2.2. Tìm kiếm nhị phân2.3. Các giải thuật sắp xếp nội2.3.1. Định nghĩa bài toán sắp xếp2.3.2. Phương pháp chọn trực tiếp3Nội dungCác phương pháp sắp xếp do sinh viên tự nghiên cứu và thuyết trìnhPhương pháp Shaker sortPhương pháp sắp xếp cây (Heap sort)Phương pháp sắp xếp với độ dài bước giảm dần (Shell sort)Phương pháp sắp xếp theo phương pháp trộn trực tiếp (Merge sort)Phương pháp sắp xếp theo phương pháp cơ số (Radix sort)Phương pháp sắp xếp đếm phân khối4Nội dungChương 3. Tổ chức ngăn xếp (Stack) & Hàng đợi (Queue) trên mảng một chiều3.1. Ngăn xếp3.1.1. Giới thiệu3.1.2. Các thao tác trên ngăn xếp3.1.3. Các ứng dụng- Tính các biểu thức đại số- Quản lý bộ nhớ khi thi hành chương trình3.2. Hàng đợi3.2.1. Giới thiệu3.2.2. Các thao tác trên hàng đợi5Nội dung3.2.3. Các ứng dụngTổ chức bộ đệm bàn phímQuản lý các tiến trình trong các hệ điều hànhVét cạn Nội dung sinh viên tự nghiên cứu và thuyết trìnhKhử đệ quyTổ chức lưu vết các quá trình tìm kiếm theo chiều rộng và quay lui6Nội dungChương 4. Cấu trúc dữ liệu động4.1. Đặt vấn đề4.2. Kiểu dữ liệu con trỏ4.2.1. Biến không động4.2.2. Kiểu con trỏ4.2.3. Biến động4.3. Danh sách liên kết4.3.1. Định nghĩa4.3.2. Các hình thức tổ chức danh sách7Nội dung4.4. Danh sách đơn4.4.1. Tổ chức danh sách đơn theo cấp phát liên kết4.4.2. Các thao tác cơ bản trên danh sách đơn4.4.3. Sắp xếp danh sách4.4.4. Các cấu trúc đặc biệt của danh sách đơn4.5. Một số cấu trúc dữ liệu dạng danh sách liên kết khác4.5.1. Danh sách liên kết kép4.5.2. Danh sách liên kết vòng4.5.3. Danh sách có nhiều mối liên kết4.5.4. Danh sách tổng quát8Nội dungNội dung sinh viên tự nghiên cứu & thuyết trìnhHàng đợi Ngăn xếp9Nội dungChương 5. Cấu trúc cây5.1. Cấu trúc cây5.1.1. Một số khái niệm cơ bản5.1.2. Một số ví dụ về đối tượng các cấu trúc dạng cây5.2. Cây nhị phân5.2.1. Một số tính chất của cây nhị phân5.2.2. Biểu diễn cây nhị phân T5.2.3. Duyệt cây nhị phân5.2.4. Biểu diễn cây tổng quát bằng cây nhị phân5.2.5. Một cách biểu diễn cây nhị phân khác10Nội dung5.3. Cây nhị phân tìm kiếm. Các thao tác trên cây nhị phân tìm kiếm5.4. Cây nhị phân cây cân bằng5.4.1. Cây nhị phân cân bằng hoàn toàn5.4.2. Cây nhị phân cân bằng11Nội dungChương 6: Bảng băm (Hash Table)Nội dung sinh viên tự nghiên cứu & thuyết trình6.1. Phương pháp băm6.2. Các hàm băm6.3. Phương pháp giải quyết đụng độ6.4. Phân tích bảng băm6.5. Kết luận so sánh các phương pháp12Chương 1Tổng quan về giải thuật và cấu trúc dữ liệu13Mục tiêuGiới thiệu tổng quanVai trò của tổ chức dữ liệuMối quan hệ giữa GT & CTDLCác khái niệm và yêu cầu về CTDLNhắc lại các kiểu dữ liệu trong C#Tổng quan về đánh giá độ phức tạp GT14Phân tích thiết kế hướng đối tượngNguyên tắc là chia nhỏ vấn đề Xây dựng các lớp phù hợp: cung cấp các đối tượng có hành vi được mong đợiChương trình là một kịch bản gồm các lời gọi các hành vị của đối tượng lúc cần thiếtCác lớp đóng vai trò trung tâm trong việc hiện thực giải thuật15Phân tích thiết kế hướng đối tượngĐiểm mạnh: tính đóng gói và tính kế thừaGồm các lớp: CTDL, lớp đồ hoạ, lớp điều khiển, Đặc trưng của lớp CTDL: lưu trữ và trả về dữ liệu, gồm các thao tác: thêm, xoá, tìm kiếm và truy xuất16Vai trò của CTDL & GT17Phương thứcCấu trúc dữ liệuGiải thuậtQuá trình phân tích hướng đối tượngXác định các lớp với các chức năng mong đợiXác định kịch bản/ giải thuật chính: sự tương tác giữa các đối tượngHiện thực các lớp18Xây dựng lớp CTDL1. Từ mô hình/ nhu cầu thực tế  các chức năng cần có của lớp2. Đặc tả các phương thức giao tiếp với bên ngoài:Kiểu dữ liệu trả về của phương thứcCác thông số vào / raCác tiền kiện (precondition)Các hậu kiện (postcondition)Các lớp, hàm có sử dụng trong phương thức (uses)3. Tìm hiểu phương án hiện thực lớp: phụ thuộc cách thức tổ chức dữ liệu bên trong, các giải thuật liên quan4. Chọn phương án hiện thực19Các tiêu chuẩn đánh giá CTDLPhản ánh đúng thực tếPhù hợp với thao tácTiết kiệm tài nguyên hệ thống 20Khái niệm về kiểu dữ liệu (KDL)T = V = {Tập các giá trị}O = {Tập các thao tác xử lý}Ví dụ: KDL số nguyên short trong ngôn ngữ C# T = short V = {-32768, 32767} O = {+, -, *, /, %}21Khái niệm về KDLMột KDL là một tập hợp, các phần tử của tập hợp này được gọi là các trị của KDLCác thuộc tính của một KDL gồm:TênMiền giá trịKích thước lưu trữTập các thao tác tác động lên KDL đóCác loại KDLKDL nguyên tố (atomic) : có trị đơnKDL có cấu trúc (structured type): chứa nhiều KDL nguyên tố/ lồng các KDL có cấu trúc22Nhắc lại các kiểu dữ liệu C#KDL nguyên tố: Số nguyên, số thực và kiểu logicKiểu mảng, xâu ký tựKDL có cấu trúc23Số nguyên24C#KíchThước(byte).NETMiền giá trịMô tảbyte1Byte[0..255]Số nguyên dương không dấusbyte1Sbyte[-128..127]Số nguyên có dấushort 2Int16[0..65.535]Số nguyên không dấuint4Int32 Từ -2.147.483.647 đến 2.147.483.646Số nguyên có dấuuint4Uint32Từ 0 đến 4.294.967.295Số nguyên không dấulong8Int64Từ -9.223.370.036.854.775.808đến 9.223.370.036.854.775.807Số nguyên có dấuulong8Uint64Từ 0 đến 0xffff ffff ffff ffffSố nguyên không dấuKý tự và logic25C#Kích thước (byte).NETMiền giá trịMô tảbool1Booleantrue hoặc falseGiá trị logicchar2CharKý tự UnicodeSố thực26C#Kích thước (byte).NETMiền giá trịMô tảfloat4SingleTừ 3,4E-38 đến 3,4E+38Kiểu dấu chấm động, với 7 chữ số có nghĩadouble8DoubleTừ 1,7E308 đến 1,7E+308Kiểu dấu chấm động có độ chính xác gấp đôi, với 15 chữ số có nghĩadecimal8DecimalCó độ chính xác đến 28 con số, phải có hậu tố “m” hoặc “M” theo sau giá trịXâu ký tự (string)27Kiểu String có thể chứa nội dung không giới hạn, vì đây là KDL đối tượng được chứa ở bộ nhớ heap. Khai báo: string s = “Nguyen Van A”;Kiểu mảng (Array)28Mảng là một tập hợp các phần tử cùng một kiểu dữ liệu liên tiếp nhau và được truy xuất thông qua chỉ số.Chỉ số bắt đầu từ 0.Mảng 1 chiều29Mảng một chiều []=new [Số phần tử];VD: Khai báo mảng số nguyên arr gồm 5 phần tử int [] arr = new int [5];Mảng 2 chiều30Mảng hai chiều [,]=new [Số dòng, số cột];VD: Khai báo ma trận số nguyên mt gồm 5 dòng và 3 cột long [ ,] mt = new long [5, 3];Kiểu có cấu trúc31Struct dùng để nhóm các dữ liệu cùng liên quan đến một đối tượng nào đóKhai báo :struct { Danh sách các thuộc tính;}Truy xuất: .thuộc tínhKiểu có cấu trúc32 struct SV { public string ten; public string maso; } static void Main(string[] args) { SV a; a.ten = "Le Van Teo"; a.maso = "002"; Console.WriteLine("Ten: "+a.ten+" Ma so: "+a.maso); Console.ReadLine(); }Các cấu trúc điều khiển trong C#Rẽ nhánh : ifelseLựa chọn : switchcaseLặp : for, while, dowhile, foreach Cấu trúc rẽ nhánhif (biểu thức điều kiện){ ;}Nếu biểu thức điều kiện cho kết quả khác không (true) thì thực hiện khối lệnh. Cấu trúc rẽ nhánh (tt)if (biểu thức điều kiện){ ;}else{ ;}Nếu biểu thức điều kiện cho kết quả khác không thì thực hiện khối lệnh 1, ngược lại thì cho thực hiện khối lệnh thứ 2. Cấu trúc lựa chọnswitch (biểu thức) case n1: các câu lệnh ; break ; case n2: các câu lệnh ; break ; case nk: ; break ; [default: các câu lệnh] break; KQ phải là nguyênCấu trúc lặpwhilefordowhileforeachCấu trúc lặp while và forHoạt động cấu trúc lặp while và forBước 1: Thực hiện khởi gánBước 2: Kiểm tra biểu thức điều kiệnNếu kết quả là true thì cho thực hiện các lệnh của vòng lặp, thực hiện biểu thức tăng/ giảm. Quay trở lại bước 2.Ngược lại kết thúc vòng lặp.Cấu trúc lặp while;while () lệnh/ khối lệnh; ;Cấu trúc lặp forfor (;;){ ;}Cấu trúc lặp dowhiledo{ ;} while (biểu thức ĐK);Thực hiện khối lệnh cho đến khi biểu thức điều kiện là falseCấu trúc lặp foreachSử dụng cho mảngforeach ( in ){ Khối lệnh;} Xét từng phần tử trong mảngKDL trừu tượngLớp CTDL ngoài khả năng chứa dữ liệu, nó còn có các hành vi đặc trưng riêng (các thao tác cho phép cập nhập, truy xuất các giá trị dữ liệu cho từng đối tượng)KDL trừu tượng (abstract data type): - Chưa có dữ liệu bên trong, chưa dùng được - Chỉ dùng để thiết kế ý niệm44Cấu trúc dữ liệuTổ chức & 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ệuVí dụ:Mảng (Array)Danh sách liên kết (Linked List)Ngăn xếp (Stack)/ Hàng đợi (Queue)Cây (Tree)45Hiện thực KDL trừu tượngClass: hiện thực của abstract data typeĐịnh nghĩa các dữ liệuĐịnh nghĩa các phương thức + hàm phụ trợ (nội bộ)Định nghĩa các constructor và destructorĐối tượng = một thể hiện (instance) của một classThông điệp (message): dùng tương tác lẫn nhau (gọi phương thức của các đối tượng)46Định nghĩa lớp (class) C# class { các thuộc tính; phương thức () { Định nghĩa phương thức }}47Từ khóa truy xuấtprivate (mặc định): Truy xuất trong nội bộ lớp (thường sử dụng cho thuộc tính)protected: Truy xuất trong nội bộ lớp/ lớp con (được sử dụng cho lớp cơ sở)public: Truy xuất mọi nơi (thường sử dụng cho phương thức)static: truy xuất không cần khởi tạo đối tượng của lớp48VD: Định nghĩa lớp CHocSinh gồm dữ liệu họ tên, điểm văn và điểm toán. Các thao tác nhập, tính điểm trung bình và in kết quảpublic class CHocSinh{ private string hoten; private int toan, van; private float dtb; public void Nhap() { Console.Write("Nhap ho ten: "); hoten = Console.ReadLine(); Console.Write("Nhap diem van: "); van = int.Parse(Console.ReadLine()); Console.Write("Nhap diem toan: "); toan = int.Parse(Console.ReadLine()); dtb = (float)(toan + van) / 2; } public void Xuat() { Console.WriteLine("Diem trung binh: {0:0.00}", dtb); }}49Tạo và sử dụng đối tượng50Tạo đối tượng TênĐốiTượng = new ();VD: CHocSinh hsA = new CHocSinh();Sử dụng đối tượng TênĐốiTượng.TênPhươngThức([tham số]);VD: hsA.Nhap(); hsA.Xuat(); Bài tậpXây dựng lớp CMyArray dùng để biểu diễn cấu trúc mảng một chiều số nguyên và các thao tác cần thiết.51Các phương pháp mô tả giải thuậtLưu đồMã giảMã tự nhiên52Các ký hiệu lưu đồBắt đầu/ kết thúcRẽ nhánhLuồng xử lýKhối xử lýNhập/ XuấtĐiều kiệnGiá trị trả vềĐiểm nối53Ký hiệu mã giảIF THEN ENDIFIF THEN ... ELSE ... ENDIFWHILE DO ENDWHILEDO UNTIL DISPLAY RETURN 54Ví dụ mô tả giải thuậtTìm ước số chung lớn nhất của 2 số nguyên dương a và bĐầu vào: 2 số nguyên dương a và bĐầu ra: ước số chung lớn nhất của a và b55Mô tả bằng mã tự nhiênBước 1: Nếu a = b thì kết luận a là ước số chung lớn nhất, kết thúcBước 2: Nếu a > b thì a = a – b; Ngược lại thì b = b – a;Bước 3: Quay trở lại Bước 156Mô tả bằng mã giảWHILE a ≠ b DO IF a>b THEN a=a-b ELSE b=b-a ENDIFENDWHILEDISPLAY a57Mô tả bằng lưu đồ58Các nguyên tắc xây dựng lớp CTDLĐịnh nghĩa CTDL và đặc tả các thao tác một cách rõ ràng (KDL trả về, thông số vào/ ra, tiền kiện, hậu kiện, có sử dụng hàm và lớp khác)Dữ liệu chỉ nên được truy xuất thông qua phương thức khác, dữ liệu lưu phải được kiểm tra hợp lệDữ liệu: private/ protectedNên được khởi tạo ban đầu là đối tượng rỗng59Kỹ thuật lập trìnhVấn đề cung cấp cơ chế xử lý lỗi khi sử dụng lớp trong chương trình: dừng/ tiếp tụcTính nhất quá trong các giá trị trả về của phương thứcTruyền nhận dữ liệu giữa các đối tượngVấn đề KDL: dùng template (C++) hay GeneticThao tác cho phép giao tiếp với bên ngoài dùng public, những thao tác còn lại là private/ protected60Đánh giá độ phức tạp giải thuậtPhụ thuộc vào ngôn ngữ lập trìnhPhụ thuộc vào người lập trìnhPhụ thuộc vào bộ dữ liệu thửPhụ thuộc vào phần cứng61Q&A62?