›
›

Giáo trình Cấu trúc dữ liệu và giải thuật - Nguyễn Thị Thu Hà

pdf 60 trang huongle 440
Download
Bạn đang xem 20 trang mẫu của tài liệu "Giáo trình Cấu trúc dữ liệu và giải thuật - Nguyễn Thị Thu Hà", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfgiao_trinh_cau_truc_du_lieu_va_giai_thuat_nguyen_thi_thu_ha.pdf

Nội dung text: Giáo trình Cấu trúc dữ liệu và giải thuật - Nguyễn Thị Thu Hà

  1. TRƯỜNG CAO ĐẲNG NGHỀ ĐẮK LẮK KHOA ĐIỆN TỬ - TIN HỌC GIÁO TRÌNH CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT NGHỀ: CƠNG NGHỆ THƠNG TIN TRÌNH ĐỘ: CAO ĐẲNG NGHỀ - TRUNG CẤP NGHỀ Người biên soạn: Nguyễn Thị Thu Hà Lưu hành nội bộ - 2014
  2. 1 Lời nĩi đầu Hiện nay, tại Trường chưa cĩ giáo trình Cấu trúc dữ liệu & giải thuật. Đặc biệt trên thị trường khơng cĩ tài liệu học tập, tham khảo phù hợp với chương trình khung Cao đẳng nghề, trung cấp nghề thuộc nghề Cơng nghệ thơng tin (CNTT) trong quá trình đào tạo nghề hiện nay. Nhĩm tác giả biên soạn giáo trình lập trình cơ bản nhằm mục đích giúp học sinh, sinh viên (HSSV) sử dụng giáo trình làm tài liệu nghiên cứu và học tập một cách thuận tiện. Chương trình mơn học được sử dụng để giảng dạy cho sinh viên cao đẳng nghề Cơng nghệ thơng tin (ứng dụng phần mềm) và làm tài liệu tham khảo cho các nghề thuộc các ngành nghề kỹ thuật. Vậy, rất mong được sự gĩp ý của bạn đọc để tài liệu này ngày càng được hồn thiện hơn, chúng tơi xin chân thành cảm ơn. Đắk Lắk, ngày 02 tháng 09 năm 2014 Tham gia biên soạn Chủ biên: Nguyễn Thị Thu Hà ThS. Lê Văn Tùng
  3. 2 CHƯƠNG TRÌNH MƠN HỌC CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT Mã số của mơn học: MH 12; Thời gian của mơn học: 75 giờ; (Lý thuyết: 24 giờ; Thực hành: 51 giờ) I. VỊ TRÍ, TÍNH CHẤT CỦA MƠN HỌC: Cấu trúc dữ liệu và giải thuật là mơn cơ sở nghề bắt buộc, được học sau các mơn học Tin học, Lập trình căn bản. II. MỤC TIÊU CỦA MƠN HỌC: - Hiểu được mối quan hệ giữa cấu trúc dữ liệu và giải thuật trong việc xây dựng chương trình; - Hiểu được ý nghĩa, cấu trúc, cách khai báo, các thao tác của các loại cấu trúc dữ liệu: mảng, danh sách liên kết, cây và các giải thuật cơ bản xử lý các cấu trúc dữ liệu đĩ; - Xây dựng được cấu trúc dữ liệu và mơ tả tường minh các giải thuật cho một số bài tốn ứng dụng cụ thể; - Cài đặt được một số giải thuật trên ngơn ngữ lập trình C; Coi việc học mơn này là một nền tảng cho các mơn học chuyên mơn tiếp theo, nghiêm túc và tích cực trong việc học lý thuyết và làm bài tập, chủ động tìm kiếm các nguồn tài liệu liên quan đến mơn học. III. NỘI DUNG MƠN HỌC: 1. Nội dung tổng quát và phân bổ thời gian: Thời gian Tên chương, mục Số Thực Kiểm tra* TT Tổng Lý hành, (LT hoặc số thuyết Bài tập TH) I Thiết kế và phân tích giải thuật 15 4 11 0 II Các kiểu dữ liệu cơ sở 8 2 6 0 Mảng, danh sách và các kiểu dữ liệu III 20 5 13 2 trừu tượng IV Cây 7 3 4 0 V Sắp xếp 15 5 10 0 VI Tìm kiếm 10 3 5 2 Tổng cộng 75 22 49 4
  4. 3 Chương 1: Thiết kế và phân tích giải thuật 1. Mở đầu: Cĩ thể nĩi rằng khơng cĩ một chương trình máy tính nào mà khơng cĩ dữ liệu để xử lý. Dữ liệu cĩ thể là dữ liệu đưa vào (input data), dữ liệu trung gian hoặc dữ liệu đưa ra (output data). Do vậy, việc tổ chức để lưu trữ dữ liệu phục vụ cho chương trình cĩ ý nghĩa rất quan trọng trong tồn bộ hệ thống chương trình. Việc xây dựng cấu trúc dữ liệu quyết định rất lớn đến chất lượng cũng như cơng sức của người lập trình trong việc thiết kế, cài đặt chương trình. 2. Thiết kế giải thuật: Khái niệm giải thuật hay thuật giải mà nhiều khi cịn được gọi là thuật tốn dùng để chỉ phương pháp hay cách thức (method) để giải quyết vần đề. 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). Trong thực tế, giải thuật thường được minh họa hay thể hiện bằng mã giả tựa trên một hay một số ngơn ngữ lập trình nào đĩ (thường là ngơn ngữ mà người lập trình chọn để cài đặt thuật tốn), chẳng hạn như C, Pascal, ? Khi đã xác định được cấu trúc dữ liệu thích hợp, người lập trình sẽ bắt đầu tiến hành xây dựng thuật giải tương ứng theo yêu cầu của bài tốn đặt ra trên cơ sở của cấu trúc dữ liệu đã được chọn. Để giải quyết một vấn đề cĩ thể cĩ nhiều phương pháp, do vậy sự lựa chọn phương pháp phù hợp là một việc mà người lập trình phải cân nhắc và tính tốn. Sự lựa chọn này cũng cĩ thể gĩp phần đáng kể trong việc giảm bớt cơng việc của người lập trình trong phần cài đặt thuật tốn trên một ngơn ngữ cụ thể. 3. Phân tích giải thuật: Mối quan hệ giữa cấu trúc dữ liệu và Giải thuật cĩ thể minh họa bằng đẳng thức: Cấu trúc dữ liệu + Giải thuật = Chương trình Như vậy, khi đã cĩ cấu trúc dữ liệu tốt, nắm vững giải thuật thực hiện thì việc thể hiện chương trình bằng một ngơn ngữ cụ thể chỉ là vấn đề thời gian. Khi cĩ cấu trúc dữ liệu mà chưa tìm ra thuật giải thì khơng thể cĩ chương trình và ngược lại khơng thể cĩ Thuật giải khi chưa cĩ cấu trúc dữ liệu. Một chương trình máy tính chỉ cĩ thể được hồn thiện khi cĩ đầy đủ cả Cấu trúc dữ liệu để lưu trữ dữ liệu và Giải thuật xử lý dữ liệu theo yêu cầu của bài tốn đặt ra. 3.1 Đánh giá cấu trúc dữ liệu và giải thuật 3.1.1. Các tiêu chuẩn đánh giá cấu trúc dữ liệu Để đánh giá một cấu trúc dữ liệu chúng ta thường dựa vào một số tiêu chí sau: - Cấu trúc dữ liệu phải tiết kiệm tài nguyên (bộ nhớ trong), - Cấu trúc dữ liệu phải phản ảnh đúng thực tế của bài tốn, - Cấu trúc dữ liệu phải dễ dàng trong việc thao tác dữ liệu. 3.2. Đánh giá độ phức tạp của thuật tốn Việc đánh giá độ phức tạp của một thuật tốn quả khơng dễ dàng chút nào. Ở dây, chúng ta chỉ muốn ước lượng thời gian thực hiện thuận tốn T(n) để cĩ thể cĩ sự so sánh tương đối giữa các thuật tốn với nhau. Trong thực tế, thời gian thực hiện một thuật tốn cịn phụ thuộc rất nhiều vào các điều kiện khác như cấu
  5. 4 tạo của máy tính, dữ liệu đưa vào, ở đây chúng ta chỉ xem xét trên mức độ của lượng dữ liệu đưa vào ban đầu cho thuật tốn thực hiện. Để ước lượng thời gian thực hiện thuật tốn chúng ta cĩ thể xem xét thời gian thực hiện thuật tốn trong hai trường hợp: - Trong trường hợp tốt nhất: Tmin - Trong trường hợp xấu nhất: Tmax Từ đĩ chúng ta cĩ thể ước lượng thời gian thực hiện trung bình của thuật tốn: Tavg 4. Một số giải thuật cơ bản: 4.1: Thuật tốn đơn giản Cĩ thể nĩi rằng khơng cĩ một chương trình máy tính nào mà khơng cĩ dữ liệu để xử lý. Dữ liệu cĩ thể là dữ liệu đưa vào (input data), dữ liệu trung gian và dữ liệu ra (output data). Ví dụ: Nhập vào một số 3 chữ số, in ra tổng của 3 chữ số đĩ. #include int n, dv, ch, tr, tong; void main() { printf(“Nhap vao mot so 3 chu so:”); scanf(“%d”, &n); dv = n mod 10; ch = (n div 10) mod 10; tr = (n div 100) mod 10; tong = dv+ ch+ tr; printf(“Tong 3 so la: %d”, tong); getchar(); } 4.2: Thuật tốn phức tạp: Ví dụ : Dãy số Fibonacci 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, Bắt đầu bằng 0 và 1, các số tiếp theo bằng tổng hai số đi trước. Dãy Fibonacci được khai báo đệ quy như sau: Fibonacci(0) = 0 Fibonacci(1) = 1 Fibonacci(n) = Fibonacci(n – 1) + Fibonacci(n – 2) 4.3: Giải thuật đệ quy: Bất cứ một hàm nào đĩ cĩ thể triệu gọi hàm khác, nhưng ở đây một hàm nào đĩ cĩ thể tự triệu gọi chính mình. Kiểu hàm như thế được gọi là hàm đệ quy.
  6. 5 Phương pháp đệ quy thường dùng phổ biến trong những ứng dụng mà cách giải quyết cĩ thể được thể hiện bằng việc áp dụng liên tiếp cùng giải pháp cho những tập hợp con của bài tốn. Ví dụ 1: tính n! n! = 1*2*3* *(n-2)*(n-1)*n với n >= 1 và 0! = 1. /* Ham tinh giai thua */ #include #include void main(void) { int in; long giaithua(int); printf("Nhap vao so n: "); scanf("%d", &in); printf("%d! = %ld.\n", in, giaithua(in)); getch(); } long giaithua(int in) { int i; long ltich = 1; if (in == 0) return (1L); else { for (i = 1; i <= in; i++) ltich *= i; return (ltich); } } � Kết quả in ra màn hình Nhap vao so n: 5 5! = 120. _ Thử lại chương trình với số liệu khác. Với n! = 1*2*3* *(n-2)*(n-1)*n, ta viết lại như sau: (1*2*3* *(n-2)*(n-1))*n = n*(n-1)! = n*(n-1)*(n-2)! � Ta viết lại hàm giaithua bằng đệ quy như sau: /* Ham tinh giai thua */ long giaithua(int in) { int i; if (in == 0) return (1L); else
  7. 6 return (in * giaithua(in – 1)); } � Chạy lại chương trình, quan sát, nhận xét và đánh giá kết quả � Giải thích hoạt động của hàm đệ quy giaithua Ví dụ giá trị truyền vào hàm giaithua qua biến in = 5. • Thứ tự gọi thực hiện hàm giaithua giaithua(in) return(in * giaithua(in – 1)) 5 * giaithua(4) = 5 * ? 4 * giaithua(3) = 4 * ? 3 * giaithua(2) = 3 * ? 2 * giaithua(1) = 2 * ? 1 * giaithua(0) = 1 * ? Khi tham số in = 0 thì return về giá trị 1L (giá trị 1 kiểu long). Lúc này các giá trị ? bắt đầu định trị theo thứ tự ngược lại. • Định trị theo thứ tự ngược lại giaithua(in) return(in * giaithua(in – 1)) 1 * giaithua(0) = 1 * 1 = 1 2 * giaithua(1) = 2 * 1 = 2 3 * giaithua(2) = 3 * 2 = 6 4 * giaithua(3) = 4 * 6 = 24 5 * giaithua(4) = 5 * 24 = 120 Kết quả sau cùng ta cĩ 5! = 120. Thứ tự gọi đệ quy Định trị theo thứ tự ngược lạiA 4.4. Bài tập 1. Viết hàm đệ quy tính tổng n số nguyên dương đầu tiên: tong (n) = n + tong (n – 1). 2. Viết hàm đệ quy tính N! 3. Viết hàm đệ qui.
  8. 7 Chương 2: Các kiểu dữ liệu cơ sở 1. Khái niệm về kiểu dữ liệu Kiểu dữ liệu T cĩ thể xem như là sự kết hợp của 2 thành phần: - Miền giá trị mà kiểu dữ liệu T cĩ thể lưu trữ: V, - Tập hợp các phép tốn để thao tác dữ liệu: O. T = Mỗi kiểu dữ liệu thường được đại diện bởi một tên (định danh). Mỗi phần tử dữ liệu cĩ kiểu T sẽ cĩ giá trị trong miền V và cĩ thể được thực hiện các phép tốn thuộc tập hợp các phép tốn trong O. Để lưu trữ các phần tử dữ liệu này thường phải tốn một số byte(s) trong bộ nhớ, số byte(s) này gọi là kích thước của kiểu dữ liệu. 2. Các kiểu dữ liệu cơ bản Kiểu số nguyên là kiểu dữ liệu dùng để lưu các giá trị nguyên hay cịn gọi là kiểu đếm được. Kiểu số nguyên trong C được chia thành các kiểu dữ liệu con, mỗi kiểu cĩ một miền giá trị khác nhau 2.1. Kiểu số nguyên 1 byte (8 bits) Kiểu số nguyên một byte gồm cĩ 2 kiểu sau: 1. unsigned char Từ 0 đến 255 (tương đương 256 ký tự trong bảng mã ASCII) 2. char Từ -128 đến 127 Kiểu unsigned char: lưu các số nguyên dương từ 0 đến 255. => Để khai báo một biến là kiểu ký tự thì ta khai báo biến kiểu unsigned char. Mỗi số trong miền giá trị của kiểu unsigned char tương ứng với một ký tự trong bảng mã ASCII . Kiểu char: lưu các số nguyên từ -128 đến 127. Kiểu char sử dụng bit trái nhất để làm bit dấu. => Nếu gán giá trị > 127 cho biến kiểu char thì giá trị của biến này cĩ thể là số âm (?). 2.2. Kiểu số nguyên 2 bytes (16 bits) Kiểu số nguyên 2 bytes gồm cĩ 4 kiểu sau: 1. enum Từ -32,768 đến 32,767 2. unsigned int Từ 0 đến 65,535 3. short int Từ -32,768 đến 32,767 4. int Từ -32,768 đến 32,767 Kiểu enum, short int, int : Lưu các số nguyên từ -32768 đến 32767. Sử dụng
  9. 8 bit bên trái nhất để làm bit dấu. => Nếu gán giá trị >32767 cho biến cĩ 1 trong 3 kiểu trên thì giá trị của biến này cĩ thể là số âm. Kiểu unsigned int: Kiểu unsigned int lưu các số nguyên dương từ 0 đến 65535. 2.3. Kiểu số nguyên 4 byte (32 bits) Kiểu số nguyên 4 bytes hay cịn gọi là số nguyên dài (long) gồm cĩ 2 kiểu sau: 1. unsigned long Từ 0 đến 4,294,967,295 2. long Từ -2,147,483,648 đến 2,147,483,647 Kiểu long : Lưu các số nguyên từ -2147483658 đến 2147483647. Sử dụng bit bên trái nhất để làm bit dấu. => Nếu gán giá trị >2147483647 cho biến cĩ kiểu long thì giá trị của biến này cĩ thể là số âm. Kiểu unsigned long: Kiểu unsigned long lưu các số nguyên dương từ 0 đến 4294967295 Kiểu số thực thường được thực hiện với các phép tốn: O =?{+, -, *, /, , =, =, ?}? 2.4. Kiểu số thực: Kiểu số thực dùng để lưu các số thực hay các số cĩ dấu chấm thập phân gồm cĩ 3 kiểu sau: 1. float 4 bytes Từ 3.4 * 10-38 đến 3.4 * 1038 2. double 8 bytes Từ 1.7 * 10-308 đến 1.7 * 10308 3. long double 10 bytes Từ 3.4 *10-4932 đến 1.1 *104932 Mỗi kiểu số thực ở trên đều cĩ miền giá trị và độ chính xác (số số lẻ) khác nhau. Tùy vào nhu cầu sử dụng mà ta cĩ thể khai báo biến thuộc 1 trong 3 kiểu trên. Ngồi ra ta cịn cĩ kiểu dữ liệu void, kiểu này mang ý nghĩa là kiểu rỗng khơng chứa giá trị gì cả. Kiểu số nguyên thường được thực hiện với các phép tốn: O =?{+, -, *, /, DIV, MOD, , =, =, ?}? 2.5. Kiểu ký tự: Cĩ thể cĩ các kích thước sau: + Kiểu ký tự byte + Kiểu ký tự 2 bytes Kiểu ký tự thường được thực hiện với các phép tốn: O =??{+, -, , =, =, ORD, CHR, ?}? - Kiểu chuỗi ký tự: Cĩ kích thước tùy thuộc vào từng ngơn ngữ lập trình Kiểu chuỗi ký tự thường được thực hiện với các phép tốn: O =??{+,???, , =, =, Length, Trunc, ?}? - Kiểu luận lý: Thường cĩ kích thước 1 byte Kiểu luận lý thường được thực hiện với các phép tốn: O =?{NOT, AND, OR, XOR, , =, =, ?}?
  10. 9 3. Các kiểu dữ liệu cĩ cấu trúc 3.1 Khái niệm: Kiểu cấu trúc (Structure) là kiểu dữ liệu bao gồm nhiều thành phần cĩ kiểu khác nhau, mỗi thành phần được gọi là một trường (field) Sự khác biệt giữa kiểu cấu trúc và kiểu mảng là: các phần tử của mảng là cùng kiểu cịn các phần tử của kiểu cấu trúc cĩ thể cĩ kiểu khác nhau. Hình ảnh của kiểu cấu trúc được minh họa: 3.2 Định nghĩa kiểu cấu trúc struct { ; ; ; }; Trong đĩ: - : là một tên được đặt theo quy tắc đặt tên của danh biểu; tên này mang ý nghĩa sẽ là tên kiểu cấu trúc. - (i=1 n): mỗi trường trong cấu trúc cĩ dữ liệu thuộc kiểu gì (tên của trường phải là một tên được đặt theo quy tắc đặt tên của danh biểu). Ví dụ 1: Để quản lý ngày, tháng, năm của một ngày trong năm ta cĩ thể khai báo kiểu cấu trúc gồm 3 thơng tin: ngày, tháng, năm. struct NgayThang { unsigned char Ngay; unsigned char Thang; unsigned int Nam; }; typedef struct {
  11. 10 unsigned char Ngay; unsigned char Thang; unsigned int Nam; } NgayThang; Ví dụ 2: Mỗi sinh viên cần được quản lý bởi các thơng tin: mã số sinh viên, họ tên, ngày tháng năm sinh, giới tính, địa chỉ thường trú. Lúc này ta cĩ thể khai báo một struct gồm các thơng tin trên. struct SinhVien { char MSSV[10]; char HoTen[40]; struct NgayThang NgaySinh; int Phai; char DiaChi[40]; }; typedef struct { char MSSV[10]; char HoTen[40]; NgayThang NgaySinh; int Phai; char DiaChi[40]; } SinhVien; 3.3 Khai báo biến cấu trúc Việc khai báo biến cấu trúc cũng tương tự như khai báo biến thuộc kiểu dữ liệu chuẩn. Cú pháp: - Đối với cấu trúc được định nghĩa theo cách 1: struct [, ]; - Đối với các cấu trúc được định nghĩa theo cách 2: [, ]; Ví dụ: Khai báo biến NgaySinh cĩ kiểu cấu trúc NgayThang; biến SV cĩ kiểu cấu trúc SinhVien. struct NgayThang NgaySinh; struct SinhVien SV; NgayThang NgaySinh; SinhVien SV; 4. kiểu tập hợp: 4.1. khái niệm: Đối với các kiểu dữ liệu ta đã biết như kiểu số, kiểu mảng, kiểu cấu trúc thì dữ liệu kiểu tập hợp (typedef) là kiểu dữ liệu bao gồm nhiều thành phần cĩ kiểu dữ liệu giống hoặ khác nhau, mỗi thành phần được gọi là một trường (field).
  12. 11 4.2.Khai báo biến tập hợp: Sử dụng từ khĩa typedef (Type definitions) để định nghĩa kiểu: Typedef struct { ; ; ; } ; Trong đĩ: - typedef (Type definitions): là kiểu do người dùng định nghĩa. - : là một tên được đặt theo quy tắc đặt tên của danh biểu; tên này mang ý nghĩa sẽ là tên kiểu cấu trúc. (i=1 n): mỗi trường trong cấu trúc cĩ dữ liệu thuộc kiểu dữ liệu cơ bản. Ví dụ 1: Để quản lý ngày, tháng, năm của một ngày trong năm ta cĩ thể khai báo kiểu cấu trúc gồm 3 thơng tin: ngày, tháng, năm. Typedef struct { unsigned char Ngay; unsigned char Thang; unsigned int Nam; } NgayThang; Ví dụ 2: Mỗi sinh viên cần được quản lý bởi các thơng tin: mã số sinh viên, họ tên, ngày tháng năm sinh, giới tính, địa chỉ thường trú. Lúc này ta cĩ thể khai báo một struct gồm các thơng tin trên. typedef struct { char MSSV[10]; char HoTen[40]; NgayThang NgaySinh; int Phai; char DiaChi[40]; } SinhVien; 4.3 Khai báo biến kiểu tập hợp: Việc khai báo biến tập hợp cũng tương tự như khai báo biến thuộc kiểu dữ liệu chuẩn. Cú pháp: - Đối với cấu trúc được định nghĩa theo cách 1: struct [, ]; - Đối với các cấu trúc được định nghĩa theo cách 2: [, ]; Ví dụ: Khai báo biến NgaySinh cĩ kiểu cấu trúc NgayThang; biến SV cĩ kiểu
  13. 12 cấu trúc SinhVien. struct NgayThang NgaySinh; struct SinhVien SV; NgayThang NgaySinh; SinhVien SV; 5.Câu hỏi và Bài tập 1. Trình bày tầm quan trọng của Cấu trúc dữ liệu và Giải thuật đối với người lập trình? 2. Các tiêu chuẩn để đánh giá cấu trúc dữ liệu và giải thuật? 3. Khi xây dựng giải thuật cĩ cần thiết phải quan tâm tới cấu trúc dữ liệu hay khơng? Tại sao? 4. Liệt kê các kiểu dữ liệu cơ sở, các kiểu dữ liệu cĩ cấu trúc trong C, Pascal?
  14. 13 Chương 3: Mảng, danh sách và các kiểu dữ liệu trìu tượng 1. Mảng: Mỗi biến chỉ cĩ thể biểu diễn một giá trị. Để biểu diễn một dãy số hay một bảng số ta cĩ thể dung nhiều biến nhưng cách này khơng thuận lợi. trong trường hợp này ta cĩ khái niệm về mảng. khái niệm về mảng trong ngơn ngữ C cũng giống như khái niệm về ma trận trong đại số tuyến tính. Mảng cĩ thể hiểu là một tập hợp nhiều phần tử cĩ cùng kiểu giá trị và cùng cùng chung một tên. Mỗi phần tử mảng biểu diễn được một giá trị. Cĩ bao nhiêu kiểu biến thì cĩ bấy nhiêu kiểu mảng. mảng cần được khai báo để định rõ: loại mảng: int, float, double, . Tên mảng. Số chiều dài và kích thước mỗi chiều. Khái niệm về kiểu mảng và tên mảng cũng giống như khái niệm về kiểu biến và tên biến. ta sẽ giải thích về số chiều và kích thước mỗi chiều thong qua các ví dụ cụ thể dưới đây. Các khai báo: int a[10],b[4][2]; float x[5],y[3][3]; Chú ý: Các phần tử của mảng được cấp phát các khoản nhớ lien tiếp nhau trong bộ nhớ. Nĩi cách khác, các phần tử của mảng liên tiếp nhau. Trong bộ nhớ, các phần tử của mảng hai chiều được sắp xếp theo hang. Chỉ số mảng: Một phần tử cụ thể của mảng được xác định nhờ các chỉ số của nĩ. Chỉ số của mảng phải cĩ giá trị int khơng vượt quá kích thước tương ứng. số chỉ số bằng số chiều của mảng. Giả sử z,b,x,y được khai báo như trên, và giả sử i,j là các biến nguyên trong đĩ i=2, J=1, khi đĩ: a[j+i-1] là a[2] b[j+i][2-i] là b[3][0] y[i][j] là y[2][1] Chú ý: Mảng cĩ bao nhiêu chiều thì ta phải viết bấy nhiêu chỉ số. vì thế nếu ta viết như sau sẽ là sai: y[i]( vì y là mảng hai chiều),vv Biểu thức dung làm chỉ số cĩ thể thực hiện. khi đĩ phần nguyên của biểu thức thực sẽ là chỉ số mảng. Ví dụ: A[2.5] là a[2]
  15. 14 B[1.9] là a[1] *Khi chỉ số vượt ra ngồi kích thước mảng, máy sẽ vẫn khơng báo lỗi, nhưng nĩ sẽ truy cập đến một vùng nhớ bên ngồi mảng và cĩ thể làm loạn chương trình. 2. Khái niệm về danh sách: Danh sách là tập hợp các phần tử cĩ kiểu dữ liệu xác định và giữa chúng cĩ một mối liên hệ nào đĩ. Số phần tử của danh sách gọi là chiều dài của danh sách. Một danh sách cĩ chiều dài bằng 0 là một danh sách rỗng. 2.1. Danh sách liên kết (Linked List) 2.1.1 Định nghĩa Danh sách liên kết là tập hợp các phần tử mà giữa chúng cĩ một sự nối kết với nhau thơng qua vùng liên kết của chúng. Sự nối kết giữa các phần tử trong danh sách liên kết đĩ là sự quản lý, ràng buộc lẫnnhau về nội dung của phần tử này và địa chỉ định vị phần tử kia. Tùy thu ộc vào mức độvà cách thức nối kết mà danh sách liên kết cĩ thể chia ra nhiều loại khác nhau: - Danh sách liên kết đơn; - Danh sách liên kết đơi/kép; - Danh sách đa liên kết; - Danh sách liên kết vịng (vịng đơn, vịng đơi). Mỗi loại danh sách sẽ cĩ cách biểu diễn các phần tử (cấu trúc dữ liệu)riêng và cá cthao tác trên đĩ. Trong tài liệu này chúng ta chỉ trình bày 02 loại danh sách liên kết cơbản là danh sách liên kết đơn và danh sách liên kết đơi. 2.1. Danh sách liên kết (Linked List) 2.1.1 Định nghĩa Danh sách liên kết là tập hợp các phần tử mà giữa chúng cĩ một sự nối kết với nhau thơng qua vùng liên kết của chúng. Sự nối kết giữa các phần tử trong danh sách liên kết đĩ là sự quản lý, ràng buộc lẫnnhau về nội dung của phần tử này và địa chỉ định vị phần tử kia. Tùy thu ộc vào mức độvà cách thức nối kết mà danh sách liên kết cĩ thể chia ra nhiều loại khác nhau: - Danh sách liên kết đơn; - Danh sách liên kết đơi/kép; - Danh sách đa liên kết; - Danh sách liên kết vịng (vịng đơn, vịng đơi). Mỗi loại danh sách sẽ cĩ cách biểu diễn các phần tử (cấu trúc dữ liệu)riêng và cá cthao táctrên đĩ. Trong tài liệu này chúng ta chỉ trình bày 02 loại danh sách liên kết cơbản là danh sách liên kết đơn. 2.1. Danh sch lin kết (Linked List) 2.1.1 Định nghĩa
  16. 15 Danh sch lin kết l tập hợp cc phần tử m giữa chng cĩ một sự nối kết với nhau thơng qua vng lin kết của chng. Sự nối kết giữa cc phần tử trong danh sch lin kết đĩ l sự quản lý, rng buộc lẫnnhau về nội dung của phần tử ny v địa chỉ định vị phần tử kia. Ty thuộc v o mức độv cch thức nối kết m danh sch lin kết cĩ thể chia ra nhiều loại khc nhau: - Danh sch lin kết đơn; - Danh sch lin kết đơi/kp; - Danh sch đa lin kết; - Danh sch lin kết vịng (vịng đơn, vịng đơi). Mỗi loại danh sch sẽ cĩ cch biểu diễn cc phần tử (cấu trc dữ liệu)ring v ccthao tc trn đĩ. Trong ti liệu ny chng ta chỉ trình by 02 loại danh sch lin kết cơbản l danh sc h lin kết đơn v danh sch lin kết đơi. typedef SLL_OneNode * SLL_Type; Để quản lý một danh sách liên kết chúng ta cĩ thể sử dụng nhiều phương pháp khácnhau và tương ứng với các phương pháp này chúng ta sẽ cĩ các cấu trúc dữ liệukhác nhau, cụ thể: - Quản lý địa chỉ phần tử đầu danh sách: SLL_Type SLList1; Hình ảnh minh họa: SLList1 N ULL 15 10 20 18 40 35 30 - Quản lý địa chỉ phần tử đầu và cuối danh sách: typedef struct SLL_PairNode { SLL_Type SLLFirst; SLL_Type SLLLast; } SLLP_Type; SLLP_Type SLList2; Hình ảnh minh họa: SLLFirst SLLLast NULL 15 10 20 18 40 35 30 - Quản lý địa chỉ phần tử đầu, địa chỉ phần tử cuối và số phần tử trong danh sách: typedef struct SLL_PairNNode { SLL_Type SLLFirst; SLL_Type SLLLast; unsigned NumNode; } SLLPN_Type; SLLPN_Type SLList3; Hình ảnh minh họa:
  17. 16 SLLFirst SLLLast NULL 15 10 20 18 40 35 30 NumNode = 7 B. Các thao tác trên danh sách liên kết đơn: Với mỗi cách quản lý khác nhau của danh sách liên kết đơn , các thao tác cũng sẽcĩ sự khác nhau về mặt chi tiết song nội dung cơ bản ít cĩ sự khác nhau. Do vậy, ơ đây chúng ta chỉ trình bày các thao tác theo cách quản lý thứ nhất (quản lý địa chỉcủa phần tử đầu danh sách liên kết đơn), các cách quản lý khác sinh viên tự vận dụng để điều chỉnh cho thích hợp. a. Khởi tạo danh sách (Initialize): Trong thao tác này chỉ đơn giản là chúng ta cho giá trị con trỏ quản lý địa ch ỉ phầntử đầu danh sách về con trỏ NULL. Hàm khởi tạo danh sách liên kết đơn như sau: void SLL_Initialize(SLL_Type First) First = NULL; return; Hình ảnh minh họa: pNext Kiểu dữ liệu Data Con trỏ kiểu Node Ví dụ: Quản lý sinh vin struct Data { int MaSV; char HoTen[30]; }; b. Tạo mới một phần tử / nút: Nút đầu, nút cuối: +Phía sau nút cuối khơng cĩ nút nào khác nên con trỏ pNext của nút cuối cĩ giá trị Null +Nút đầu được quản lý bởi con trỏ pHead. Ta khai báo một cấu trúc List giữ con trỏ pHead này pHead NULL struct Data { // Thuộc tính của data }; struct Node { Data info; Node *pNext; };
  18. 17 struct List { Node * pHead; }; c. Thêm một phần tử vào trong danh sách: Giả sử chúng ta cần thêm một phần tử cĩ giá trị thành phần dữ liệu là NewDa ta vàotrong danh sách. Việc thêm cĩ thể diễn ra ở đầu, cuối hay ở giữa danh sách liên kết. Do vậy, ở đây chúng ta trình bày 3 thao tác thêm riêng biệt nhau: a) Thêm phần tử mới vào đầu danh sách void ChenDau(List <, Data x) { Node* pNew = new Node; pNew->Info= x; pNew->pNext= lt.pHead; lt.pHead= pNew; } void main() { Data x; x.MaSV = 123; strcpy(x.HoTen, “Nam”); ChenDau(lop49, x); } a) Thêm phần tử mới vào cuối danh sách NULL
  19. 18 void ChenCuoi(List <, Data x) { Node* pNew = new Node; pNew->Info= x; pNew->pNext= NULL; if (lt.pHead==NULL) lt.pHead= pNew; else{ Node* p = lt.pHead; while (p->pNext!=NULL) p = p->pNext; p->pNext = pNew; }} e. Tìm kiếm một phần tử trong danh sách: Thực hiện tìm tuần tự (LinearSearch) Ví dụ: cần tìm một sinh viên cĩ mã số là x Node* TimKiem(List <, int x) { Node* p = lt.pHead; NULL while (p!=NULL) { if (p->info.MaSV == x) return p; p = p->pNext; } return NULL; X g. Hủy danh sách: * Xĩa phần tử đầu tiên trong danh sách: NULL p Thực hiện tìm tuần tự (LinearSearch) Ví dụ: cần tìm một sinh viên cĩ mã số là x Node* TimKiem(List <, int x) { Node* p = lt.pHead; while (p!=NULL) { if (p->info.MaSV == x) return p;
  20. 19 p = p->pNext; } return NULL; } Xĩa tồn bộ danh sách Lần lượt xĩa các phần tử đầu danh sách cho đến khi danh sách trống void XoaDanhSach() { Node* p; while (lt.pHead!=NULL) { p = lt.pHead; lt.pHead = p->pNext; delete p; } } k. Sao chép một danh sách: Thực chất thao tác này là chúng ta tạo mới danh sách NewList bằng cách duyệt quacác nút của SLList để lấy thành phần dữ liệu rồi tạo thành một nút mới và bổ sung nút mới này vào cuối danh sách NewList. - Thuật toán: B1: NewList = NULL B2: CurNode = SLList B3: IF (CurNode = NULL) Thực hiện Bkt B4: SLL_Add_Last(NewList, CurNode->Key) B5: CurNode = CurNode->NextNode B6: Lặp lại B3 Bkt: Kết thúc k. Sắp xếp thứ tự các phần tử trong danh sách:
  21. 20 Thao tác này chúng ta cĩ thể vận dụng các thuật tốn sắp xếp đã trình bày trongChương 3 để sắp xếp dữ liệu trong danh sách liên kết đơn. Ở đây chúng ta chỉ trìnhbày sự vận dụng thuật tốn trộn tự nhiên để sắp xếp.Cũng cần lưu ý rằng đối với thao tác hốn vị hai phần tử thì chúng ta cĩ thể hốn vịhồn tồn hai nút hoặc chỉ hốn vị phần dữ liệu. Tuy nhiên việc hốn vị hồn tồnhai nút sẽ phức tạp hơn. - Thuật tốn sắp xếp trộn tự nhiên: B1: IF (SLL_Split(SLList, TempList) = NULL) Thực hiện Bkt B2: SLL_Merge(SLList, TempList, SLList) B3: Lặp lại B1 Bkt: Kết thúc 2.2. Danh sách liên kết vịng: Nút cuối của danh sách liên kết vịng khơng trỏ đến NULL mà trỏ về lại nút đầu. 2.3. Danh sách liên kết kép (Doubly Linked List) A. Cấu trúc dữ liệu: Nếu như vùng liên kết của danh sách liên kết đơn cĩ 01 mối liên kết với 01 phần tửkhác trong danh sách thì vùng liên kết trong danh sá ch liên đơi cĩ 02 mối liên kếtvới 02 phần tử khác trong danh sách, cấu trú c dữ liệu của mỗi nút trong danh sáchliên kết đơi như sau: typedef struct DLL_Node { T Key; InfoType Info; DLL_Node * NextNode; // Vùng liên kết quản lý địa chỉ phần tử kế tiếp nĩDLL_Node * PreNode; // Vùng liên kết quản lý địa chỉ phần tử trước nĩ } DLL_OneNode;
  22. 21 Ở đây chúng ta cũng giả thiết rằng vùng dữ liệu của mỗi phần tử trong danh sáchliên kết đơi chỉ bao gồm một thành phần khĩa nhậ n diện (Key) cho phần tử đĩ. Dovậy, cấu trúc dữ liệu trên cĩ thể viết lại đơn giản như sau: typedef struct DLL_Node { T Key; DLL_Node * NextNode; // Vùng liên kết quản lý địa chỉ phần tử kế tiếp nĩ DLL_Node * PreNode; // Vùng liên kết quản lý địa chỉ phần tử trư ớc nĩ } DLL_OneNode; typedef DLL_OneNode * DLL_Type; Cĩ nhiều phương pháp khác nhau để quản lý các danh sách liên kết đơi và tươngứng với các phương pháp này sẽ cĩ các cấu trúc dữ liệu khác nhau, cụ thể: - Quản lý địa chỉ phần tử đầu danh sách: Cách này hồn tồn tương tự như đối với danh sách liên kết đơn. DLL_Type DLL_List1; Hình ảnh minh họa: DLL_List1 NULL 15 10 20 18 40 30 NULL - Quản lý địa chỉ phần tử đầu và cuối danh sách: typedef struct DLL_PairNode { DLL_Type DLL_First; DLL_Type DLL_Last; } DLLP_Type; DLLP_Type DLL_List2; Hình ảnh minh họa: DLL_List2 DLL_First DLL_Last NULL
  23. 22 15 10 20 18 40 30 Quản lý địa chỉ phần tử đầu, địa chỉ phần tử cuối v à số phần tử trong danh sách: typedef struct DLL_PairNNode { DLL_Type DLL_First; DLL_Type DLL_Last; unsigned NumNode; } DLLPN_Type; DLLPN_Type DLL_List3; Hình ảnh minh họa: DLL_List3 DLL_First NumNode=6 DLL_Last N ULL 15 10 20 18 40 30 NULL 3. Các kiểu dữ liệu trìu tượng: 3.1. Ngăn xếp (Stack) A. Khái niệm - Cấu trúc dữ liệu: Ngăn xếp là một danh sách mà trong đĩ thao tác thêm một phần tử vào trong danhvà thao tác lấy ra một phần tử từ trong danh sách được thực hiện ở cùng một đầu. Như vậy, các phần tử được đưa vào trong ngăn xếp sau cùng sẽ được lấy ra trướctiên, phần tử đưa vào trong hàng đợi trước tiên s ẽ được lấy ra sau cùng. Do đĩ màngăn xếp cịn được gọi là danh sác h vào sau ra trước (LIFO List) và cấu trúc dữ liệunày cịn được gọi là cấu trúc LIFO (Last In – First Out). Tương tự như hàng đợi, cĩ nhiều cách để biểu diễn và tổ chức các ngăn xếp - Sử dụng danh sách đặc, - Sử dụng danh sách liên kết, Do ở đây cả hai thao tác thêm vào và lấy ra đều được thực hiện ở một đầu nênchúng ta chỉ cần quản lý vị trí đầu của danh sách dùng làm mặt cho ngăn xếp thơngqua biến chỉ số bề mặt SP (Stack Point er). Chỉ số này cĩ thể là cùng chiều (đầu)
  24. 23 hoặc ngược chiều (cuối) với thứ tự các phần tử trong mảng và tron g danh sách liênkết. Điều này cĩ nghĩa là bề mặt ngăn xếp cĩ thể là đầu mảng, đầu danh sách liênkết mà cũng cĩ thể là cuối mảng, cuối danh sách liên kết. Để thuận tiện, ở đâychúng ta giả sử bề mặt của ngăn xếp là đầu mảng, đầu danh sách liên kết. Trường hợp ngược lại, sinh viên tự áp dụng tương tự. Ở đây chúng ta cũng sẽ biểu diễn và tổ chức hàng đợi bằng danh sách đặc và bằngdanh sách liên kết đơn được quản lý bởi con trỏ đầu danh sách. Do vậy cấu trúc dữliệu của ngăn xếp và các thao tác trên đĩ sẽ được trình bày thành hai trường hợpkhác nhau. - Biểu diễn và tổ chức bằng danh sách đặc: typedef struct S_C { int Size; // Kích thước ngăn xếp int SP; T * List;// Nội dung ngăn xếp } C_STACK; C_STACK CS_List; - Biểu diễn và tổ chức bằng danh sách liên kết đơn; typedef struct S_Element { T Key; S_Element * Next; // Vùng liên kết quản lý địa chỉ phần tử kế tiếp } S_OneElement; typedef S_OneElement * S_STACK; S_STACK S_SP; Hình ảnh minh họa: 4) Ứng dụng của ngăn xếp (Biểu thức hậu tố - ký pháp Ba Lan) a) Biểu thức trung tố: Ví dụ: 6+7, A*B, 3^8, 9-2
  25. 24 Thứ tự ưu tiên các phép tốn? • Phép mũ • Phép nhân, chia • Phép cộng, trừ b)Biểu thức hậu tố: Bài tập: 1. Tính:     2. Tính:     3.2. Hàng đợi (Queue) A. Khái niệm - Cấu trúc dữ liệu:
  26. 25 Hàng đợi là một danh sách mà trong đĩ thao tác thêm một phần t ử vào trong danhsách được thực hiện ở một đầu này và thao tác lấ y ra một phần tử từ trong danhsách lại được thực hiện ở đầu kia Như vậy, các phần tử được đưa vào trong hàng đợi trước sẽ được lấy ra trước, phầntử đưa vào trong hàng đợi sau sẽ được lấy ra sau . Do đĩ mà hàng đợi cịn được gọilà danh sách vào trước ra trước (F IFO List) và cấu trúc dữ liệu này cịn được gọi làcấu trúc FIFO (First In – First Out). Cĩ nhiều cách để biểu diễn và tổ chức các hàng đợi: - Sử dụng danh sách đặc, - Sử dụng danh sách liên kết, Tuy nhiên, điều quan trọng và cần thiết là chúng ta phải quản lý vị trí hai đầu củahàng đợi thơng qua hai biến: Biến trước (Front) và Biến s au (Rear). Hai biến này cĩthể cùng chiều hoặc ngược chiều với thứ tự c ác phần tử trong mảng và trong danhsách liên kết. Điều này cĩ nghĩa là đầu hàng đợi cĩ thể là đầu mảng, đầu danh sáchliên kết mà cũng cĩ th ể là cuối mảng, cuối danh sách liên kết. Để thuận tiện, ở đâychúng ta giả sử đầu hàng đợi cũng là đầu mảng, đầu danh sách liên kết. Trường hợp ngược lại, sinh viên tự áp dụng tương tự. Ở đây chúng ta sẽ biểu diễn và tổ chức hàng đợi bằng danh sách đ ặc
  27. 26 và bằng danhsách liên kết đơn được quản lý bởi hai con trỏ đầu v à cuối danh sách. Do vậy cấutrúc dữ liệu của hàng đợi cũng như các thao tác trên hàng đợi sẽ được trình bàythành hai trường hợp khác nhau - Biểu diễn và tổ chức bằng danh sách đặc: typedef struct Q_C { int Len; // Chiều dài hàng đợi int Front, Rear; T * List;// Nội dung hàng đợi } C_QUEUE; C_QUEUE CQ_List; - Biểu diễn và tổ chức bằng danh sách liên kết đơn; typedef struct Q_Element { T Key; Q_Element * Next; // Vùng liên kết quản lý địa chỉ phần tử kế tiếp } Q_OneElement; typedef Q_OneElement * Q_Type; typedef struct QP_Element { Q_Type Front; Q_Type Rear; } S_QUEUE; S_QUEUE SQ_List; Hình ảnh minh họa: B. Các thao tác trên hàng đợi tổ chức bằng danh sách đặc: Do hạn chế của danh sách đặc cho nên mỗi hàng đợi đều cĩ một ch iều dài cố định. Do vậy, trong quá trình thao tác trên hàng đợi cĩ thể xảy ra hiện t ượng hàng đợi bịđầy hoặc hàng đợi bị tràn.
  28. 27 Khi hàng đợi bị đầy: số phần tử của hàng đợi bằng chiều dài cho phép của hàngđợi. Lúc này chúng ta khơng thể thêm bất kỳ một phần tử nào vào hàng đợi.Khi hàng đợi bị tràn: số phần tử của hàng đợi nhỏ hơn chiều dài cho phép củahàng đợi nhưng Rear = Len. Lúc này chúng ta phải khắc phục tình trạng trànhàng đợi bằng cách dịch tất cả các phần tử của hàng đợi ra phía trước Front-1 vị trí hoặc xoay vịng để Rear chuyển lên vị trí đầu danh sách đặc. Trong phầnnày chúng ta sử dụng phương pháp xoay vịng. Như vậ y theo phương pháp này,hàng đợi bị đầy trong các trường hợp sau: + Front = 1 và Rear = Len, khi: Front < Rear + Rear + 1 = Front, khi: Rear < Front Ghi chú: Nếu chúng ta khắc phục hàng đợi bị tràn bằng phương pháp dịch tất cả các phần tửcủa hàng đợi ra phía trước Front=1 vị trí thì hàng đợi b ị đầy khi thỏa mãn điều kiện: Front = 1 và Rear = Len (Ở đây ta luơn luơn cĩ: Front ≤ Rear). 4.Câu hỏi và Bài tập 1.Trình bày khái niệm của các loại danh sách? Ưu, nhược điểm và ứng dụng của mỗi loại danh sách? 2. Hãy đưa ra các cấu trúc dữ liệu để quản lý các loại danh sách vừa kể trên? Mỗi loạibạn hãy chọn ra một cấu trúc dữ liệu mà theo bạn là hay nhất? Giải thích sự lựachọn đĩ? 3. Trình bày thuật tốn và cài đặt tất cả các thao tác trên danh sách li ên kết đơn trongtrường hợp quản lý bằng con trỏ đầu và cuối trong danh s ách? 4. Trình bày thuật tốn và cài đặt tất cả các thao tác trên danh sách l iên kết đơi trongtrường hợp chỉ quản lý bằng con trỏ đầu trong danh sá ch? 5. Trình bày thuật tốn và cài đặt tất cả các thao tác trên hàng đợi, ngă n xếp biểu diễnbởi danh sách liên kết đơi trong hai trường hợp: Danh sách liên kết cùng chiều vàngược chiều với hàng đợi, ngăn xếp? 6. Vận dụng các thuật tốn sắp xếp đã học, hãy cài đặt các hàm s ắp
  29. 28 xếp trên danhsách liên kết đơn, liên kết đơi theo hai cách quản lý: - Quản lý địa chỉ nút đầu danh sách; - Quản lý địa chỉ nút đầu và cuối danh sách. Theo bạn thuật tốn sắp xếp nào dễ vận dụng hơn trên danh sách l iên kết đơn, liênkết đơi trong hai trường hợp này? 7. Sử dụng Stack, viết chương trình chuyển đổi một số nguyên N tro ng hệ thập phân(hệ 10) sang biểu diễn ở: a. Hệ nhị phân (hệ 2) b. Hệ thập lục phân (hệ 16) 8. Viết chương trình mơ phỏng cho bài tốn “Tháp Hà nội” và “Tháp Saigon” với cấu trúc dữ liệu như sau: a. Sử dụng danh sách liên kết để lưu trữ các cột tháp; b. Sử dụng Stack để lưu trữ các cột của tháp Cĩ nhận xét gì cho từng trường hợp? 9. Vận dụng Stack để gỡ đệ quy cho thuật tốn QuickSort? 10. Vận dụng danh sách liên kết vịng để giải bài tốn Josephus. Chương 4: Cây (TREE) 1. Khái niệm-biểu biễn cây: 1.1. Định nghĩa cây: Ví dụ: cĩ mối quan hệ họ hàng sau: . Ơng Nam cĩ 3 người con là Hùng, Huân , Hải . Ơng Hùng cĩ 2 người con là Sơn, Hậu . Ơng Huân cĩ 2 người con là Trang, Minh
  30. 29 Cây là một tập hợp các phần tử (các nút) được tổ chức và cĩ các đặc đi ểm sau: - Hoặc là một tập hợp rỗng (cây rỗng) Hoặc là một tập hợp khác rỗng trong đĩ cĩ một nút duy nhất đ ược làm nút gốc(Root’s Node), các nút cịn lại được phân thành các nhĩm trong đĩ mỗi nhĩm lại là một cây gọi là cây con (Sub-Tree). Như vậy, một cây con cĩ thể là một tập rỗng các nút và cũng cĩ th ể là một tập hợpkhác rỗng trong đĩ cĩ một nút làm nút gốc cây con. Định nghĩa cây: Cây là một tập hợp các phần tử liên kết với nhau qua một quan hệ phân cấp gọi là quan hệ cha con. Tồn tại một phần tử (nút) khơng là con của bất cứ nút nào, gọi là nút gốc. Định nghĩa đệ quy: • Một nút được gọi là một cây và là nút gốc của cây đĩ. • Nếu T1, T2, , Tk là các cây và n1, n2, , nk lần lượt là các nút gốc. n là một nút và n là cha của các nút con n1, n2, , nk. Hình thành nên một cây T và n là nút gốc của cây T này.
  31. 30 Ví dụ: Cây thư mục trên một đĩa cứng 1.2. Một số khái niệm liên quan a. Bậc của một nút: Bậc của một nút (node’s degree) là số cây con của nút đĩ Ví dụ: Bậc của nút OS trong cây trên bằng 2 b. Bậc của một cây: Bậc của một cây (tree’s degree) là bậc lớn nhất của các nút trong cây.
  32. 31 Cây cĩ bậc N gọi là cây N-phân (N-Tree) Ví dụ: Bậc của cây trên bằng 4 (bằng bậc của nút gốc) và cây tr ên gọi là cây tứ phân (Quartz-Tree) c. Nút gốc: Nút gốc (root’s node) là nút khơng phải là nút gốc cây con của bất kỳ một cây con nào khác trong cây (nút khơng làm nút gốc cây con). Ví dụ: Nút \ của cây trên là các nút gốc. d. Nút kết thúc: Nút kết thúc hay cịn gọi là nút lá (leaf’s node) là nút cĩ bậc bằng 0 (nút khơng cĩ nút cây con). Ví dụ: Các nút DOS, WINDOWS, BIN, INCLUDE, BGI, DOC, P ICTURE, SHEET, NC, NU của cây trên là các nút lá. e. Nút trung gian: Nút trung gian hay cịn gọi là nút giữa (interior’s node) là nút khơn g phải là nút gốcvà cũng khơng phải là nút kết thúc (nút cĩ bậc khá c khơng và là nút gốc cây con của một cây con nào đĩ trong cây). Ví dụ: Các nút OS, PROGRAMS, APPLICATIONS, UTILITIES, PASCAL, C, WORD, EXCEL của cây trên là các nút trung gian. f. Mức của một nút: Mức của một nút (node’s level) bằng mức của nút gốc cây con ch ứa nĩ cộng thêm 1, trong đĩ mức của nút gốc bằng 1. Ví dụ: Mức của các nút DOS, WINDOWS, PASCAL, C, WORD, EXCEL, NC, NU củacây trên bằng 3; mức của các nút BIN, IN CLUDE, BGI, DOC, PICTURE, SHEET, của cây trên bằng 4. g. Chiều cao hay chiều sâu của một cây: Chiều cao của một cây (tree’s height) hay chiều sâu của một cây (tree’s depth) là mức cao nhất của các nút trong cây. Ví dụ: Chiều cao của cây trên bằng 4. h. Nút trước và nút sau của một nút: Nút T được gọi là nút trước (ancestor’s node) của nút S nếu cây c on cĩ gốc là Tchứa cây con cĩ gốc là S. Khi đĩ, nút S được gọi là nút sa u (descendant’s node) của nút T. Ví dụ: Nút PROGRAMS là nút trước của các nút BIN, BGI, INCL UDE, PASCAL, C vàngược lại các nút BIN, BGI, INCLUDE, P ASCAL, C là nút sau của nút PROGRAMS trong cây trên. i. Nút cha và nút con của một nút:
  33. 32 Nút B được gọi là nút cha (parent’s node) của nút C nếu nút B là nút trước của nút Cvà mức của nút C lớn hơn mức của nút B là 1 mức. Khi đĩ, nút C được gọi là nút con (child’s node) của nút B. Ví dụ: Nút PROGRAMS là nút cha của các nút PASCAL, C v à ngược lại các nútPASCAL, C là nút con của nút PROGRAMS trong cây trên. j. Chiều dài đường đi của một nút: Chiều dài đường đi của một nút là số đỉnh (số nút) tính từ nút gốc để đi đến nút đĩ. Như vậy, chiều dài đường đi của nút gốc luơn luơn bằng 1, chiều dài đường đi tới một nút bằng chiều dài đường đi tới nút cha nĩ cộng thêm 1. Ví dụ: Chiều dài đường đi tới nút PROGRAMS trong cây trên là 2. k. Chiều dài đường đi của một cây: Chiều dài đường đi của một cây (path’s length of the tree) là tổng tất cả các chiều dài đường đi của tất cả các nút trên cây. Ví dụ: Chiều dài đường của cây trên là 65. Ghi chú: Đây là chiều dài đường đi trong (internal path’s length) của c ây. Để cĩ đượcchiều dài đường đi ngồi (external path’s length) của c ây người ta mở rộng tất cảcác nút của cây sao cho tất cả các nút của cây cĩ cùng bậc bằng cách thêm vàocác nút giả sao cho tất cả các nú t cĩ bậc bằng bậc của cây. Chiều dài đường đingồi của cây bằng tổng chiều dài c ủa tất cả các nút mở rộng. l. Rừng: Rừng (forest) là tập hợp các cây. Như vậy, một cây khi mất nút gốc sẽ trở thành một rừng. 1.3. Biểu diễn cây Cĩ nhiều cách để biểu diễn cây: - Sử dụng đồ thị: Như ví dụ về cây thư mục ở trên. - Sử dụng giản đồ tập hợp Sử dụng dạng phân cấp chỉ số: Như bảng mục lục trong các tài liệu, giáo
  34. 33 trình, - Biểu diễn cây trong bộ nhớ máy tính: Để biểu diễn cây trong bộ nhớ máy tính chúng ta cĩ thể sử dụng dan h sách liên kết. Như vậy, để biểu diễn cây Nphân chúng ta sử dụng danh sách cĩ N mối liên kết đểquản lý địa chỉ N nút gốc cây con. Như vậy cấu trúc d ữ liệu của cây N-phân tương tự như cấu trúc dữ liệu của danh sách đa liên kết: const int N = 100; typedef struct NT_Node { T Key; NT_Node * SubNode[N]; // Vùng liên kết quản lý địa chỉ N nút gốc cây con } NT_OneNode; typedef NT_OneNode * NT_Type; Để quản lý các cây chúng ta chỉ cần quản lý địa chỉ nút gốc của cây: NT_Type NTree; Trong phạm vi phần này chúng ta sẽ trình bày các thao tác trê n cây nhị phân (Binary Tree) là cây phổ biến và thơng dụng nhất. 2. Cây nhị phân (Binary tree): 2.1. Khái niệm: Cây nhị phân là cây mà mỗi nút cĩ tối đa là 2 nút con. Hai nút được phân biệt nhau là nút bên trái và nút bên phải.
  35. 34 A. Biểu diễn cây nhị phân: Để biểu diễn cây nhị phân trong bộ nhớ máy tính chúng ta cĩ thể s ử dụng danh sáchcĩ 2 mối liên kết để quản lý địa chỉ của 2 nút gố c cây con (cây con trái và cây conphải). Như vậy cấu trúc dữ liệu của cây nh ị phân tương tự như cấu trúc dữ liệu củadanh sách liên kết đơi nhưng về cách thức liên kết thì khác nhau: typedef struct BinT_Node { T Key; BinT_Node * BinT_Left; // Vùng liên kết quản lý địa chỉ nút gốc c ây con trái BinT_Node * BinT_Right; // Vùng liên kết quản lý địa chỉ nút gốc cây con phải } BinT_OneNode; typedef BinT_OneNode * BinT_Type; Để quản lý các cây nhị phân chúng ta cần quản lý địa chỉ nút gốc của c ây: BinT_Type BinTree;
  36. 35 3. Một số bài tốn ứng dụng: • Duyệt danh sách liên kết là thăm các nút của danh sách từ nút đầu đến nút cuối. • Duyệt cây là thăm tất cả các nút của cây. • Cĩ nhiều cách để duyệt cây theo thứ tự duyệt giữa nút cha, nút con bên trái và nút con bên phải. • Các phép duyệt được thực hiện đệ quy a,Duyệt theo thứ tự trước NLR (Node – Left – Right) Thăm nút gốc duyệt cây con bên trái theo NLR duyệt cây con bên phải theo NLR Kết quả duyệt LNR: E B H F A G J D I void DuyetLNR(Tree t) { if (t!=NULL) { DuyetLNR(t->pLeft); XuLy(t->info); DuyetLNR(t->pRight); } b,Duyệt theo thứ tự giữa LNR (Left – Node – Right) Duyệt cây con bên trái theo LNR Thăm nút gốc Duyệt cây con bên phải theo LNR
  37. 36 Ví dụ: xét cây sau Kết quả duyệt NLR: A B E F H D G J I void DuyetNLR(Tree t) { if (t!=NULL) { XuLy(t->info); DuyetNLR(t->pLeft); DuyetNLR(t->pRight); } } void main() { DuyetNLR(Root); } } c,Duyệt theo thứ tự sau LRN (Left – Right – Node ) Duyệt cây con bên trái theo LRN Thăm nút gốc Duyệt cây con bên phải theo LRN
  38. 37 Kết quả duyệt LRN: E H F B J G I D A void DuyetLRN(Tree t) { if (t!=NULL) { DuyetLRN(t->pLeft); DuyetLRN(t->pRight); XuLy(t->info); } } 4. cây nhị phân tìm kiếm: 4.1.Định nghĩa Cây nhị phân tìm kiếm là cây nhị phân mà ứng với mỗi nút: • Giá trị của nút lớn hơn giá trị của các nút trong cây con bên trái. • Giá trị của nút nhỏ hơn giá trị của các nút trong cây con bên phải. Để đơn giản, ta sử dụng một cấu trúc nút trong đĩ info cĩ kiểu nguyên struct Node {
  39. 38 int Info; // dùng int thay vì struct Data Node *pLeft; Node *pRight; }; typedef Node* Tree; Tree Root; 4.2. Tìm kiếm trên cây nhị phân tìm kiếm Cách thức tìm kiếm giá trị X trên cây nhị phân tìm kiếm định nghĩa đệ quy như sau: • Thăm nút gốc của cây . Nếu giá trị nút gốc là X tìm thấy nút . Nếu giá trị nút gốc lớn hơn X tìm đệ quy trong cây con bên trái . Nếu giá trị nút gốc nhỏ hơn X tìm đệ quy trong cây con bên phải • Điều kiện dừng là khi đến nút lá
  40. 39 a,Cài đặt thuật tốn khơng đệ quy: Node* TimCayNPTK(Tree t, int x) { Node *p = t; while (p!=NULL) { if (x == p->info) return p; else if (x info) p = p->pLeft; else p = p->pRight; } return NULL; } void main() { // Nhap x TimCayNPTK(Root, x); } b,Cài đặt thuật tốn theo đệ quy: Node* TimCayNPTK2(Tree t, int x) { if (t==NULL) return NULL; else
  41. 40 { if (x == t->info) return t; else if (x info) return TimCayNPTK2(t->pLeft, x); else return TimCayNPTK2(t->pRight, x); } } void main() { // Nhap x TimCayNPTK2(Root, x); } 4.3.Thêm phần tử mới vào cây nhị phân tìm kiếm Yêu cầu: Phần tử mới thêm vào phải bảo đảm tính chất của cây nhị phân tìm kiếm. Ví dụ: thêm số nút vào cây
  42. 41 Cách thực hiện: thêm giá trị X vào cây • Giả sử X đã tồn tại trong cây, như vậy X phải cĩ một nút cha p, tìm nút cha này. • Tạo một nút t cĩ giá trị là X và cho con trỏ bên trái hay bên phải của nút cha p trỏ tới nút t này int ChenNut(Tree *&t, int x) { if (t!=NULL) { if (t->info = x) return 0; // đã cĩ if (t->info pLeft, x); else return ChenNut(t->pRight, x); } t= new Node; t->info= x; t->pLeft= t->pRight= NULL; return 1; } void main() { ChenNut(Root, 4); } 4.4.Xĩa phần tử khỏi cây nhị phân tìm kiếm Yêu cầu: Khi xĩa một phần tử các phần tử cịn lại cũng phải bảo đảm tính chất của cây nhị phân tìm kiếm.
  43. 42 Cĩ 3 trường hợp của nút cần xĩa X: a) Trường hợp 1: X là nút lá Chỉ cần hủy mĩc nối từ nút cha đến nút X b)Trường hợp 2: X chỉ cĩ một nút con • Cho nút cha của X chỉ đến nút con của X • Xĩa nút X c)Trường hợp 3: X cĩ hai nút con
  44. 43 Khơng thể xĩa X và cho nút cha trỏ đến 2 con của X được. • Thay vì xĩa X tìm nút Y thế mạng cho X (Y chỉ cĩ tối đa 1 nút con) • Gán info của Y cho X • Xĩa nút Y theo trường hợp 1 hay 2 Cĩ thể chọn nút Y là nút nhỏ Nhất trong cây con bên phải Của X. Như vậy Y tối đa chỉ cĩ 1 nút con
  45. 44 int XoaNut(Tree &t, int x) { if (t== NULL) return 0; // khơng tìm thấy nút x if (t->info pLeft, x); if (t->info > x) return XoaNut(t->pRight, x); Node *p = t; if (p->pLeft== NULL) t = p->pRight; else if (p->pRight== NULL) t = p->pLeft; else { p = TimNutTheMang(p->pRight); t->info= p->info; } delete p; return 1; } Node* TimNutTheMang(Tree &tr) { Node* tm; if (tr->pLeft== NULL){
  46. 45 tm = tr; tr= tr->pRight; } else{ Node *q = tr; Node *p = q->pLeft; while (p->pLeft!=NULL){ q= p; p = p->pLeft; } tm= p; q->pLeft= p->pRight; } return tm; } void main() { XoaNut(Root, 10); } 4.5. Xĩa tồn bộ cây nhị phân Việt xĩa cây nhị phân được thực hiện đệ quy như sau: • Xĩa cây con bên trái • Xĩa cây con bên phải • Xĩa nút gốc void XoaCay(Tree &t)
  47. 46 { if (t!= NULL){ XoaCay(t->pLeft); XoaCay(t->pRight); delete t; } } void main() { XoaCay(Root); } 5. Bài tập: 1.Trình bày thuật tốn và cài đặt tất cả các thao tác trên cây nhị phân tìm kiếm, câynhị phân tìm kiếm cân bằng trong trường hợp chấp nh ận sự trùng khĩa nhận diện của các nút trong cây? 2. Trình bày tất cả các thuật tốn và cài đặt tất cả các thuật tốn để thực hiện việc hủymột nút trên cây nhị phân tìm kiếm nếu cây cĩ 02 cây con? Theo bạn, thuật tốn nào là đơn giản? Cho nhận xét về mỗi thuật tốn? 3. Trình bày và cài đặt tất cả các thuật tốn để thực hiện các thao tá c trên cây nhịphân tìm kiếm, cây nhị phân tìm kiếm cân bằng trong hai trường hợp: Chấp nhận vàKhơng chấp nhận sự trùng lắp về khĩa của các nút bằng cách khơng sử dụng thuật_tốn đệ quy (Trừ các thao tác đã trình bày trong tài liệu)? 4. Trình bày thuật tốn và cài đặt chương trình thực hiện các cơng việc sau trên cây nhị phân: a) Tính số nút lá của cây. b) Tính số nút trung gian của cây. c) Tính chiều dài đường đi tới một nút cĩ khĩa là K trên cây. d) Cho biết cấp của một nút cĩ khĩa là K trên cây.
  48. 47 6. Trình bày thuật tốn và cài đặt chương trình thực hiện cơng việc tạo cây nhị phântìm kiếm mà khĩa của các nút là khĩa của các nút t rong một danh sách liên kết đơisao cho tối ưu hĩa bộ nhớ. Biết rằng, d anh sách liên kết đơi ban đầu khơng cần thiết sau khi tạo xong cây nhị phân tìm kiếm và giả sử khơng cho phép sự trùng khĩa giữa các nút trong cây. 7. Với yêu cầu trong bài tập 8 ở trên, trong trường hợp nếu danh sách l iên kết cĩ nhiềunút cĩ thành phần dữ liệu giống nhau, bạn hãy đề xu ất phương án giải quyết đểkhơng bị mất dữ liệu sau khi tạo xong cây nhị phân tìm kiếm. 8. Trình bày thuật tốn và cài đặt chương trình thực hiện cơng việc chuyển cây nhị_phân tìm kiếm thành danh sách liên kết đơi sao cho tối ưu hĩa bộ nhớ. Biết rằng,cây nhị phân tìm kiếm ban đầu khơng cần thiết_sau khi tạo xong danh sách liên kết (ngược với yêu cầu trong bài tập 8).
  49. 48 Chương 5: Các phương pháp Sắp xếp 1. Khái quát về sắp xếp: Để thuận tiện và giảm thiểu thời gian thao tác mà đặc biệt là để tìm kiếm dữ liệu dễ dàng và nhanh chĩng, thơng thường trước khi thao tác thì dữ liệu trên mảng, trên tập tin đã cĩ thứ tự. Do vậy, thao tác sắp xếp dữ liệu là một trong những thao tác cần thiết và thường gặp trong quá trình lưu trữ, quản lý dữ liệu. Thứ tự xuất hiện dữ liệu cĩ thể là thứ tự tăng (khơng giảm dần) hoặc thứ tự giảm (khơng tăng dần). Trong phạm vi chương này chúng ta sẽ thực hiện việc sắp xếp dữ liệu theo thứ tự tăng. Việc sắp xếp dữ liệu theo thứ tự giảm hồn tồn tương tự. Cĩ rất nhiều thuật tốn sắp xếp song chúng ta cĩ thể phân chia các thuật tốn sắp xếp thành hai nhĩm chính căn cứ vào vị trí lưu trữ của dữ liệu trong máy tính, đĩ là: - Các giải thuật sắp xếp thứ tự nội (sắp xếp thứ tự trên dãy/mảng), - Các giải thuật sắp xếp thứ tự ngoại (sắp xếp thứ tự trên tập tin/file). 2. Các giải thuật sắp xếp cơ bản (Sắp xếp trên dãy/mảng) Ở đây, tồn bộ dữ liệu cần sắp xếp được đưa vào trong bộ nhớ trong (RAM). Do vậy, số phần tử dữ liệu khơng lớn lắm do giới hạn của bộ nhớ trong, tuy nhiên tốc độ sắp xếp tương đối nhanh. Các giải thuật sắp xếp nội bao gồm các nhĩm sau: - Sắp xếp bằng phương pháp đếm (counting sort), - Sắp xếp bằng phương pháp đổi chỗ (exchange sort), - Sắp xếp bằng phương pháp chọn lựa (selection sort), - Sắp xếp bằng phương pháp chèn (insertion sort), - Sắp xếp bằng phương pháp trộn (merge sort). Trong phạm vi của giáo trình này chúng ta chỉ trình bày một số thuật tốn sắp xếp tiêu biểu trong các thuật tốn sắp xếp ở các nhĩm trên và giả sử thứ tự sắp xếp N phần tử cĩ kiểu dữ liệu T trong mảng M là thứ tự tăng. 2.1. Sắp xếp bằng phương pháp đổi chỗ (Exchange Sort) Các thuật tốn trong phần này sẽ tìm cách đổi chỗ các phần tử đứng sai vị trí (so với mảng đã sắp xếp) trong mảng M cho nhau để cuối cùng tất cả các phần tử trong mảng M đều về đúng vị trí như mảng đã sắp xếp.
  50. 49 Các thuật tốn sắp xếp bằng phương pháp đổi chỗ bao gồm: - Thuật tốn sắp xếp nổi bọt (bubble sort), - Thuật tốn sắp xếp lắc (shaker sort), - Thuật tốn sắp xếp giảm độ tăng hay độ dài bước giảm dần (shell sort), - Thuật tốn sắp xếp dựa trên sự phân hoạch (quick sort). Ở đây chúng ta trình bày hai thuật tốn phổ biến là thuật tốn sắp xếp nổi bọt và sắp xếp dựa trên sự phân hoạch. a. Thuật tốn sắp xếp nổi bọt (Bubble Sort): - Tư tưởng: + Đi từ cuối mảng về đầu mảng, trong quá trình đi nếu phần tử ở dưới (đứng phía sau) nhỏ hơn phần tử đứng ngay trên (trước) nĩ thì theo nguyên tắc của bọt khí phần tử nhẹ sẽ bị "trồi" lên phía trên phần tử nặng (hai phần tử này sẽ được đổi chỗ cho nhau). Kết quả là phần tử nhỏ nhất (nhẹ nhất) sẽ được đưa lên (trồi lên) trên bề mặt (đầu mảng) rất nhanh. + Sau mỗi lần đi chúng ta đưa được một phần tử trồi lên đúng chỗ. Do vậy, sau N-1 lần đi thì tất cả các phần tử trong mảng M sẽ cĩ thứ tự tăng. - Thuật tốn: B1: First = 1 B2: IF (First = N) Thực hiện Bkt B3: ELSE B3.1: Under = N B3.2: If (Under = First) Thực hiện B4 B3.3: Else B3.3.1: if (M[Under] < M[Under - 1]) Swap(M[Under], M[Under - 1]) B3.3.2: Under B3.3.3: Lặp lại B3.2 B4: First++ B5: Lặp lại B2 Bkt: Kết thúc - Cài đặt thuật tốn: Hàm BubbleSort cĩ prototype như sau: void BubbleSort(T M[], int N);
  51. 50 //Đổi chỗ 2 phần tử cho nhau Hàm thực hiện việc sắp xếp N phần tử cĩ kiểu dữ liệu T trên mảng M theo thứ tự tăng dựa trên thuật tốn sắp xếp nổi bọt. Nội dung của hàm như sau: void BubbleSort(T M[], int N) { for (int I = 0; I I; J ) if (M[J] < M[J-1]) Swap(M[J], M[J-1]); return; }? Hàm Swap cĩ prototype như sau: void Swap(T????X, T????Y); Hàm thực hiện việc hốn vị giá trị của hai phần tử X và Y cho nhau. Nội dung của hàm như sau: void Swap(T????X, T????Y) { T Temp = X; X = Y; Y = Temp; return; }? - Ví dụ minh họa thuật tốn: Giả sử ta cần sắp xếp mảng M cĩ 10 phần tử sau (N = 10): M: 15 10 2 20 10 5 25 35 22 30 Ta sẽ thực hiện 9 lần đi (N - 1 = 10 - 1 = 9) để sắp xếp mảng M: - Phân tích thuật tốn: + Trong mọi trường hợp: Số phép gán: G = 0 Số phép so sánh: S = (N-1) + (N-2) + ? + 1 = ½N(N-1) + Trong trường hợp tốt nhất: khi mảng ban đầu đã cĩ thứ tự tăng Số phép hốn vị: Hmin = 0 + Trong trường hợp xấu nhất: khi mảng ban đầu đã cĩ thứ tự giảm Số phép hốn vị: Hmin = (N-1) + (N-2) + ? + 1 = ½N(N-1) + Số phép hốn vị trung bình: Havg = ¼N(N-1) - Nhận xét về thuật tốn nổi bọt: + Thuật tốn sắp xếp nổi bọt khá đơn giản, dễ hiểu và dễ cài đặt.
  52. 51 + Trong thuật tốn sắp xếp nổi bọt, mỗi lần đi từ cuối mảng về đầu mảng thì phần tử nhẹ được trồi lên rất nhanh trong khi đĩ phần tử nặng lại "chìm" xuống khá chậm chạp do khơng tận dụng được chiều đi xuống (chiều từ đầu mảng về cuối mảng). + Thuật tốn nổi bọt khơng phát hiện ra được các đoạn phần tử nằm hai đầu của mảng đã nằm đúng vị trí để cĩ thể giảm bớt quãng đường đi trong mỗi lần 2.2. sắp_xếp_chọn: Vấn đề xếp tiền : Cĩ một xấp tiền gồm nhiều tờ cĩ mệnh giá khác nhau đang để lộn xộn, cần xếp lại theo thứ tự tiền nhỏ trước, tiền lớn sau. Phương pháp xếp tiền là: lần lượt chọn ra các tờ tiền từ nhỏ đến lớn để xếp cho đến khi hết xấp tiền. Đối với mảng, các bước thực hiện là: • Trong N phần tử của mảng, chọn phần tử bé nhất, chuyển lên đầu mảng • Trong N-1 phần tử cịn lại, chọn phần tử bé nhất, chuyển vào vị trí thứ 2 • Tiếp tục cho đến khi sắp xếp hết. 2.3. sắp xếp chèn: Phương pháp: • Giống như cách xếp bài khi được chia quân bài. • Quân bài mới nhận được chèn vào những quân bài đã cĩ trên tay. • Các quân bài trên tay luơn được sắp xếp. • Thuật tốn: void InsertionSort(int a[], int N) { int i, j, temp; for(i = 1; i =0)&&(a[j]>a[j+1])) { a[j+1] = a[j]; j ;
  53. 52 } if (j!=i-1) a[j+1] = temp; } 2.4. Sắp xếp phân đoạn: – Phương pháp: Dùng giải pháp đệ quy (chia để trị) • Bước 1: Phân hoạch mảng A ban đầu thành 2 mảng con B và C sao cho bi cj  bi B, cj C. • Bước 2: Sắp xếp mảng con B bằng đệ quy • Bước 3: Sắp xếp mảng con C bằng đệ quy • Điều kiện dừng: khi mảng con cần sắp chỉ cĩ 1 phần tử xem như được sắp. • Vì B, C được sắp và bi cj nên mảng A là được sắp 2.5. Sắp xếp hịa nhập: – Phương pháp: Cũng sử dụng giải pháp chia để trị • Bước 1: Chia mảng A ban đầu thành 2 mảng con B và C. • Bước 2, 3: Sắp xếp mảng con B và C bằng đệ quy (Điều kiện dừng: khi mảng con cần sắp chỉ cĩ 1 phần tử) • Bước 4: Trộn (merge) 2 mảng con đã sắp B, C thành mảng A được sắp. Thuật tốn: int Partition(int a[], int p, int r) { int t; // phân hoạch return t; } void QuickSort(int a[], int p, int r) { int t = Partition(a, p, r); if (p< t-1) QuickSort(a, p, t-1); if (t+1< r) QuickSort(a, t+1, r);
  54. 53 } Chương 6: Tìm Kiếm 1. Khái quát về tìm kiếm Trong thực tế, khi thao tác, khai thác dữ liệu chúng ta hầu như lúc nào cũng phải thực hiện thao tác tìm kiếm. Việc tìm kiếm nhanh hay
  55. 54 chậm tùy thuộc vào trạng thái và trật tự của dữ liệu trên đĩ. Kết quả của việc tìm kiếm cĩ thể là khơng cĩ (khơng tìm thấy) hoặc cĩ (tìm thấy). Nếu kết quả tìm kiếm là cĩ tìm thấy thì nhiều khi chúng ta cịn phải xác định xem vị trí của phần tử dữ liệu tìm thấy là ở đâu? Trong phạm vi của chương này chúng ta tìm cách giải quyết các câu hỏi này. Trước khi đi vào nghiên cứu chi tiết, chúng ta giả sử rằng mỗi phần tử dữ liệu được xem xét cĩ một thành phần khĩa (Key) để nhận diện, cĩ kiểu dữ liệu là T nào đĩ, các thành phần cịn lại là thơng tin (Info) liên quan đến phần tử dữ liệu đĩ. Như vậy mỗi phần tử dữ liệu cĩ cấu trúc dữ liệu như sau: typedef { T struct DataElement Key; InfoType } DataType; Info; Trong tài liệu này, khi nĩi tới giá trị của một phần tử dữ liệu chúng ta muốn nĩi tới giá trị khĩa (Key) của phần tử dữ liệu đĩ. Để đơn giản, chúng ta giả sử rằng mỗi phần tử dữ liệu chỉ là thành phần khĩa nhận diện. Việc tìm kiếm một phần tử cĩ thể diễn ra trên một dãy/mảng (tìm kiếm nội) hoặc diễn ra trên một tập tin/ file (tìm kiếm ngoại). Phần tử cần tìm là phần tử cần thỏa mãn điều kiện tìm kiếm (thường cĩ giá trị bằng giá trị tìm kiếm). Tùy thuộc vào từng bài tốn cụ thể mà điều kiện tìm kiếm cĩ thể khác nhau song chung quy việc tìm kiếm dữ liệu thường được vận dụng theo các thuật tốn trình bày sau đây. 2. Tìm tuần tự (Linear Search) Thuật tốn tìm tuyến tính cịn được gọi là Thuật tốn tìm kiếm tuần tự (Sequential Search). a. Tư tưởng: Lần lượt so sánh các phần tử của mảng M với giá trị X bắt đầu từ phần tử đầu tiên cho đến khi tìm đến được phần tử cĩ giá trị X hoặc đã duyệt qua hết tất cả các phần tử của mảng M thì kết thúc. b. Thuật tốn: B1: k = 1 B2: IF M[k]?? X AND k?? N B2.1: k++
  56. 55 B2.2: Lặp lại B2 B3: IF k?? N Tìm thấy tại vị trí k B4: ELSE //Duyệt từ đầu mảng //Nếu chưa tìm thấy và cũng chưa duyệt hết mảng Khơng tìm thấy phần tử cĩ giá trị X B5: Kết thúc c. Cài đặt thuật tốn: Hàm LinearSearch cĩ prototype: int LinearSearch (T M[], int N, T X); Hàm thực hiện việc tìm kiếm phần tử cĩ giá trị X trên mảng M cĩ N phần tử. Nếu tìm thấy, hàm trả về một số nguyên cĩ giá trị từ 0 đến N-1 là vị trí tương ứng của phần tử tìm thấy. Trong trường hợp ngược lại, hàm trả về giá trị -1 (khơng tìm thấy). Nội dung của hàm như sau: int LinearSearch (T M[], int N, T X) { int k = 0; while (M[k] != X??? k < N) k++; if (k < N) return (k); return (-1); }? d. Phân tích thuật tốn: - Trường hợp tốt nhất khi phần tử đầu tiên của mảng cĩ giá trị bằng X: Số phép gán: Gmin = 1 Số phép so sánh: Smin = 2 + 1 = 3 - Trường hợp xấu nhất khi khơng tìm thấy phần tử nào cĩ giá trị bằng X: Số phép gán: Gmax = 1 Số phép so sánh: Smax = 2N+1 - Trung bình: Số phép gán: Gavg = 1 Số phép so sánh: Savg = (3 + 2N + 1) : 2 = N + 2 e. Cải tiến thuật tốn: Trong thuật tốn trên, ở mỗi bước lặp chúng ta cần phải thực hiện 2 phép so sánh để kiểm tra sự tìm thấy và kiểm sốt sự hết mảng trong quá trình duyệt mảng. Chúng ta cĩ thể giảm bớt 1 phép so sánh nếu chúng ta thêm vào cuối mảng một phần tử cầm canh (sentinel/stand
  57. 56 by) cĩ giá trị bằng X để nhận diện ra sự hết mảng khi duyệt mảng, khi đĩ thuật tốn này được cải tiến lại như sau: B1: k = 1 B2: M[N+1] = X B3: IF M[k]?? X B3.1: k++ B3.2: Lặp lại B3 B4: IF k < N Tìm thấy tại vị trí k B5: ELSE //Phần tử cầm canh //k = N song đĩ chỉ là phần tử cầm canh Khơng tìm thấy phần tử cĩ giá trị X B6: Kết thúc Hàm LinearSearch được viết lại thành hàm LinearSearch1 như sau: int LinearSearch1 (T M[], int N, T X) { int k = 0; M[N] = X; while (M[k] != X) k++; if (k < N) return (k); return (-1); }? f. Phân tích thuật tốn cải tiến: - Trường hợp tốt nhất khi phần tử đầu tiên của mảng cĩ giá trị bằng X: Số phép gán: Gmin = 2 Số phép so sánh: Smin = 1 + 1 = 2 - Trường hợp xấu nhất khi khơng tìm thấy phần tử nào cĩ giá trị bằng X: Số phép gán: Gmax = 2 Số phép so sánh: Smax = (N+1) + 1 = N + 2 - Trung bình: Số phép gán: Gavg = 2 Số phép so sánh: Savg = (2 + N + 2) : 2 = N/2 + 2 - Như vậy, nếu thời gian thực hiện phép gán khơng đáng kể thì thuật tốn cải tiến sẽ chạy nhanh hơn thuật tốn nguyên thủy.
  58. 57 3. Tìm nhị phân (Binary Search) Thuật tốn tìm tuyến tính tỏ ra đơn giản và thuận tiện trong trường hợp số phần tử của dãy khơng lớn lắm. Tuy nhiên, khi số phần tử của dãy khá lớn, chẳng hạn chúng ta tìm kiếm tên một khách hàng trong một danh bạ điện thoại của một thành phố lớn theo thuật tốn tìm tuần tự thì quả thực mất rất nhiều thời gian. Trong thực tế, thơng thường các phần tử của dãy đã cĩ một thứ tự, do vậy thuật tốn tìm nhị phân sau đây sẽ rút ngắn đáng kể thời gian tìm kiếm trên dãy đã cĩ thứ tự. Trong thuật tốn này chúng ta giả sử các phần tử trong dãy đã cĩ thứ tự tăng (khơng giảm dần), tức là các phần tử đứng trước luơn cĩ giá trị nhỏ hơn hoặc bằng (khơng lớn hơn) phần tử đứng sau nĩ. Khi đĩ, nếu X nhỏ hơn giá trị phần tử đứng ở giữa dãy (M[Mid]) thì X chỉ cĩ thể tìm thấy ở nửa đầu của dãy và ngược lại, nếu X lớn hơn phần tử M[Mid] thì X chỉ cĩ thể tìm thấy ở nửa sau của dãy. a. Tư tưởng: Phạm vi tìm kiếm ban đầu của chúng ta là từ phần tử đầu tiên của dãy (First = 1) cho đến phần tử cuối cùng của dãy (Last = N). So sánh giá trị X với giá trị phần tử đứng ở giữa của dãy M là M[Mid]. Nếu X = M[Mid]: Tìm thấy Nếu X M[Mid]: Rút ngắn phạm vi tìm kiếm về nửa sau của dãy M (First = Mid+1) Lặp lại quá trình này cho đến khi tìm thấy phần tử cĩ giá trị X hoặc phạm vi tìm kiếm của chúng ta khơng cịn nữa (First > Last). b. Thuật tốn đệ quy (Recursion Algorithm): B1: First = 1 B2: Last = N B3: IF (First > Last) B3.1: Khơng tìm thấy B3.2: Thực hiện Bkt B4: Mid = (First + Last)/ 2 B5: IF (X = M[Mid]) //Hết phạm vi tìm kiếm B5.1: Tìm thấy tại vị trí Mid B5.2: Thực hiện Bkt
  59. 58 B6: IF (X M[Mid]) Tìm đệ quy từ First = Mid + 1 đến Last Bkt: Kết thúc c. Cài đặt thuật tốn đệ quy: Hàm BinarySearch cĩ prototype: int BinarySearch (T M[], int N, T X); Hàm thực hiện việc tìm kiếm phần tử cĩ giá trị X trong mảng M cĩ N phần tử đã cĩ thứ tự tăng. Nếu tìm thấy, hàm trả về một số nguyên cĩ giá trị từ 0 đến N-1 là vị trí tương ứng của phần tử tìm thấy. Trong trường hợp ngược lại, hàm trả về giá trị -1 (khơng tìm thấy). Hàm BinarySearch sử dụng hàm đệ quy RecBinarySearch cĩ prototype: int RecBinarySearch(T M[], int First, int Last, T X); Hàm RecBinarySearch thực hiện việc tìm kiếm phần tử cĩ giá trị X trên mảng M trong phạm vi từ phần tử thứ First đến phần tử thứ Last. Nếu tìm thấy, hàm trả về một số nguyên cĩ giá trị từ First đến Last là vị trí tương ứng của phần tử tìm thấy. Trong trường hợp ngược lại, hàm trả về giá trị -1 (khơng tìm thấy). 4.Câu hỏi và Bài tập 1. Trình bày tư tưởng của các thuật tốn tìm kiếm: Tuyến tính, Nhị phân, Chỉ mục? Các thuật tốn này cĩ thể được vận dụng trong các trường hợp nào? Cho ví dụ? 2. Cài đặt lại thuật tốn tìm tuyến tính bằng các cách: - Sử dụng vịng lặp for, - Sử dụng vịng lặp do while? Cĩ nhận xét gì cho mỗi trường hợp? Trong trường hợp các phần tử của dãy đã cĩ thứ tự tăng, hãy cải tiến lại thuật tốn tìm tuyến tính? Cài đặt các thuật tốn cải tiến? Đánh giá và so sánh giữa thuật tốn nguyên thủy với các thuật tốn cải tiến. 4. Trong trường hợp các phần tử của dãy đã cĩ thứ tự giảm, hãy trình bày và cài đặt lại thuật tốn tìm nhị phân trong hai trường hợp: Đệ quy và Khơng đệ quy? 5. Vận dụng thuật tốn tìm nhị phân, hãy cải tiến và cài đặt lại thuật tốn tìm kiếm dựa theo tập tin chỉ mục? Đánh giá và so sánh giữa thuật tốn nguyên thủy với các thuật tốn cải tiến?
  60. 59 6. Sử dụng hàm random trong C để tạo ra một dãy (mảng) M cĩ tối thiểu 1.000 số nguyên, sau đĩ chọn ngẫu nhiên (cũng bằng hàm random) một giá trị nguyên K. Vận dụng các thuật tốn tìm tuyến tính, tìm nhị phân để tìm kiếm phần tử cĩ giá trị K trong mảng M. Với cùng một dữ liệu như nhau, cho biết thời gian thực hiện các thuật tốn. 7. Trình bày và cài đặt thuật tốn tìm tuyến tính đối với các phần tử trên mảng hai chiều trong hai trường hợp: - Khơng sử dụng phần tử “Cầm canh”. - Cĩ sử dụng phần tử “Cầm canh”. Cho biết thời gian thực hiện của hai thuật tốn trong hai trường hợp trên. 8. Sử dụng hàm random trong C để tạo ra tối thiểu 1.000 số nguyên và lưu trữ vào mot tập tin cĩ tên SONGUYEN.DAT, sau đĩ chọn ngẫu nhiên (cũng bằng hàm random) một giá trị nguyên K. Vận dụng thuật tốn tìm tuyến tính để tìm kiếm phần tử cĩ giá trị K trong tập tin SONGUYEN.DAT.