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

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ệu trong một đề án tin học1.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 tự nghiên cứuPhươ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ụngTí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ứuKhử đệ 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ứuHà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ứu6.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 vai 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 GT14Xét đoạn chương trình sauint main(){int n;printf("Nhap vao so nguyen n: “);scanf(“%d”, &n);if(n%2==0)printf("La so chan”);elseprintf("La so le“); return 0;}15Khái niệm về kiểu dữ liệuT = V = {Tập các giá trị}O = {Tập các thao tác xử lý}Ví dụ: Kiểu dữ liệu số nguyên int trong ngôn ngữ C T = int V = {-32768, 32767} O = {+, -, *, /, %}16Khái niệm về kiểu dữ liệuCác thuộc tính của một kiểu dữ liệu 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 kiểu dữ liệu đóCác loại kiểu dữ liệuKiểu dữ liệu cơ bản: Cơ sở, mảng, cấu trúc cơ bảnKiểu dữ liệu có cấu trúc hướng giải quyết vấn đề: Danh sách liên kết, hàng đợi, ngăn xếp, cây, bảng băm, 17Khái niệm về kiểu dữ liệuTĩnh Được định nghĩa ở thời điểm biên dịch. Được cấp phát ở thời điểm liên kết. Có thể có giá trị ban đầu tùy theo từng ngôn ngữ lập trình. Tồn tại đến khi kết thúc chương trình.Động Được gắn kết với một con trỏ (tại thời điểm biên dịch chưa có). Phát sinh lúc thực thi. Không xác định giá trị ban đầu. Được giải phóng khỏi bộ nhớ khi cần.18Nhắc lại các kiểu dữ liệu CKiểu cơ sở: Số nguyên, số thựcKiểu dãy (mảng), xâu ký tựKiểu có cấu trúc1920Kiểu số nguyênData typeSizeValue rangechar1 byte-128 đến 127 hoặc 0 đến 255 (Ký tự dạng mã ASCII)unsigned char1 byte0 đến 255signed char1 byte-128 đến 127int2 hoặc 4 bytes-32,768 đến 32,767 hoặc -2,147,483,648 đến 2,147,483,647unsigned int2 hoặc 4 bytes0 đến 65,535 hoặc 0 đến 4,294,967,295short2 bytes-32,768 đến 32,767unsigned short2 bytes0 đến 65,535long4 bytes-2,147,483,648 đến 2,147,483,647unsigned long4 bytes0 đến 4,294,967,29521Kiểu số thựcSttTên kiểuGhi chúKích thước1float 4 bytes2double 8 bytes3long double 8 bytesKiểu mảng 1 chiềuKhai báo [];VD: int a[100];Gán giá trị ban đầuVD1: int a[100] = {0};VD2: int a[5] = {3, 6, 2, 10, 17}; hoặc: int a[] = {3, 6, 2, 10, 17};22Giá trị57103112Vị trí012n-2n-1Kiểu mảng 1 chiềuPhát sinh ngẫu nhiên Khởi tạo phát sinh ngẫu nhiên srand((unsigned int)time(NULL));Phát sinh giá trị ngẫu nhiên int x = rand()%k; k: Số nguyên dương x  [0..k-1]VD: Phát sinh 1 số nguyên có giá trị từ 0 đến 50 srand((unsigned int)time(NULL)); int x = rand()%51;23Kiểu xâu ký tựKhai báochar [] ;VD: char hoten[50];Xem lại các hàmgets, fflush, flushallstrcpy, strcat, strlenstrcmp, stricmpstrchr, strstr24Kiểu mảng/ xâu ký tự – Con trỏ Mảng 1 chiều *;VD: int *a; Xâu ký tựchar *;VD: char *hoten;25Kiểu mảng/ xâu ký tự – Con trỏLưu ý khi sử dụng phải cấp phát biến con trỏ bằng lệnh calloc (hoặc malloc), hủy bằng lệnh freeVD: int *a; int n = 10; a = (int *) calloc (n, sizeof (int)); //Hoặc a = (int *) malloc (n); .. free(a);26Kiểu dữ liệu có cấu trúcstruct tên_struct{ khai báo các thuộc tính;};typedef struct tên_struct tên_kiểu;27Ví dụ kiểu dữ liệu có cấu trúcstruct ttDate{ char thu[9]; unsigned char ngay; unsigned char thang; int nam;};typedef struct ttDate DATE;28Truy cập thành phần có cấu trúcBiến cấu trúc kiểu tĩnh.thành phần cấu trúcVD: DATE d; d.nam = 2012;29Truy cập thành phần có cấu trúcBiến cấu trúc kiểu con trỏ->thành phần cấu trúcVD: DATE *d;d->nam = 2012;30Vai trò của CTDL & GT31Chương trìnhCấu trúc dữ liệuGiải thuậtNiklaus WirthCấu trúc dữ liệu?Cách thức liên kết/ tổ chức các KDL cơ sở/ KDL có cấu trúc hợp lý để sử dụng một cách hiệu quả (phương pháp lưu trữ trên máy tính)Tập các thao tác để truy cập/ xử lý các thành phần dữ liệu  Cần giải thuậtVí dụ:Danh sách liên kết (Linked List)Ngăn xếp (Stack)/ Hàng đợi (Queue)Cây (Tree)32Cá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 33Khái niệm về giải thuậtLà một thủ tục tính toán xác định (well-defined) nhận các giá trị hoặc một tập các giá trị (input) và sinh ra một vài giá trị hoặc tập giá trị (output)Cách thức/ quy trình thực hiện hoàn thành một công việc xác định cụ thể nào đó. VD Cộng 2 số, tính tổng dãy Fibonaci, 34Các phương pháp mô tả giải thuậtLưu đồMã giảMã tự nhiên35Cá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ối36Ký hiệu mã giảIF THEN ENDIFIF THEN ... ELSE ... ENDIFWHILE DO ENDWHILEDO UNTIL DISPLAY RETURN 37Ví 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à b38Mô 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 139Mô tả bằng mã giảWHILE a ≠ b DO IF a>b THEN a=a-b ELSE b=b-a ENDIFENDWHILEDISPLAY a40Mô tả bằng lưu đồ41Bài tập 2Mô tả giải thuật tìm và in ra tất cả các ước số của số nguyên dương theo 3 hình thức:Mã tự nhiênMã giảLưu đồ42Đặc trưng của giải thuậtTính đúng đắnTính dừngTính xác địnhTính hiệu quảTính phổ quát43Đặc trưng của giải thuật[1] Tính đúng đắn * Đảm bảo kết quả đúng sau khi thực hiện đối với bộ dữ liệu đầu vào[2] Tính dừng Dừng  Sau một vài bước thực hiện44Đặc trưng của giải thuật[3] Tính xác định - Rõ ràng, cụ thể - Không nhập nhằng, gây hiểu lầm  hiểu, cài đặt[4] Tính hiệu quả - Giải quyết trong thời gian, điều kiện cho phép - Đáp ứng yêu cầu người dùng[5] Tính phổ quát Có thể giải quyết được một lớp bài toán tương tự45Tiêu chuẩn đánh giá giải thuậtĐánh giá độ tốt/ xấu của các thuật toán cùng loạiĐơn giản, dễ hiểu, dễ cài đặtThời gian thực hiện và tài nguyên sử dụng46Đá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ứng47Đánh giá độ phức tạp giải thuậtThông thường so sánh các thuật toán dựa vào độ phức tạp về thời gian thực thi: độ phức tạp của giải thuật (algorithm complexity)  ước lượng số phép tính cần thực hiện48Thời gian thực thi chương trìnhThời gian thực hiện một chương trình là một hàm của kích thước dữ liệu vào, ký hiệu T(N) trong đó N là kích thước (độ lớn) của dữ liệu vàoVD: Chương trình tính tổng của N số có thời gian thực hiện (số phép tính) là T(N) = c.N trong đó c là một hằng sốThời gian thực thi chương trình là một hàm không âm, tức là T(n) 0 n049Khái niệm độ phức tạp giải thuậtHàm T(N) có tỷ suất tăng (growth rate) là f(n) nếu tồn tại các hằng số c và N0 sao cho T(N) ≤ f(N) với mọi N ≥ N0 VD: Giả sử T(0) = 1, T(1) = 4 và tổng quát T(N) = (N+1)2. Đặt N0 = 1 và c = 4 thì với mọi N ≥ 1 chúng ta dễ dàng chứng minh rằng T(N) = (N+1)2 ≤ 4N2 với mọi N ≥ 1, tức là tỷ suất tăng của T(N) là N2VD: Tỷ suất tăng của hàm T(N) = 3N3 + 2N2 là N3. Đặt N0 = 0 và c = 5 ta dễ dàng chứng minh rằng với mọi N ≥ 0 thì 3N3 + 2N2 ≤ 5N350Khái niệm độ phức tạp giải thuật 51Hàm mũQuy tắc tính độ phức tạp giải thuậtQuy tắc cộngNếu T1(N) và T2(N) là thời gian thực hiện của hai đoạn chương trình P1 và P2; và T1(N)=O(f(N)), T2(N)=O(g(N)  thời gian thực hiện của đoạn hai chương trình đó nối tiếp nhau là T(N)=O(max(f(N), g(N)))52Quy tắc tính độ phức tạp giải thuậtQuy tắc nhânNếu T1(N) và T2(N) là thời gian thực hiện của hai đoạn chương trình P1và P2 và T1(N) = O(f(N)), T2(N) = O(g(N))thời gian thực hiện của đoạn hai đoạn chương trình đó lồng nhau là T(N) = O(f(N).g(N))53Bài tập 1Bước 1: i = 1; Bước 2: j = N; Trong khi (j > i) thực hiện: Nếu a[j] ;}Nếu biểu thức điều kiện cho kết quả true thì thực hiện khối lệnh bên trong if. Cấu trúc rẽ nhánh57if (biểu thức điều kiện){ ;}else{ ;}Nếu biểu thức điều kiện cho kết quả true 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ứ 2Có thể lồng các cấu trúc ifelse vào bên trong if/ elseCấu trúc lựa chọn58switch (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] Trường hợp giá trị biểu thức bằng n1Trường hợp giá trị biểu thức bằng n2Các trường hợp còn lại (nếu có)Có giá trị là hằng ký tự/ số nguyênCấu trúc lặp59Cấu trúc lặp while;while () lệnh/ khối lệnh; ;60Cấu trúc lặp forfor (;;){ ;}61Cấu trúc lặp dowhile62;do{ ; ;} while (điều kiện);Bài tập 3Cài đặt hàm nhập mảng số nguyên, n phần tử Cài đặt hàm phát sinh n phần tử ngẫu nhiên cho mảng số nguyênCài đặt hàm phát sinh n phần tử ngẫu nhiên có giá trị tăng dần cho mảng số nguyên63Bài tập 4Viết lại các hàm trong Bài tập 3 dùng khai báo kiểu con trỏ64Bài tập 5Viết hàm nhập và hàm xuất thông tin của một sinh viên gồm các thông tin:Mã sốHọ tênĐiểm trung bình65Bài tập 6Viết lại các hàm trong Bài tập 5 sử dụng khai báo biến kiểu con trỏ cấu trúc66Q&A67?