Giáo trình môn Cấu trúc dữ liệu

142 trang hapham 200

Download

Bạn đang xem 20 trang mẫu của tài liệu "Giáo trình môn Cấu trúc dữ liệu", để 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:

giao_trinh_mon_cau_truc_du_lieu.doc

Nội dung text: Giáo trình môn Cấu trúc dữ liệu

GIÁO TRÌNH CẤU TRÚC DỮ LIỆU
Giáo trình Cấu trúc dữ liệu 2 LỜI NÓI ĐẦU Cấu trúc dữ liệu và Giải thuật là môn học đóng vai trò quan trọng trong quá trình đào tạo kỹ sư, cử nhân các ngành Khoa học máy tính và Công nghệ thông tin. Cuốn giáo trình này được nghiên cứu và hình thành dựa trên cơ sở mục tiêu đào tạo và đề cương chi tiết của môn học Cấu trúc dữ liệu và Giải thuật do Hội đồng nghiên cứu khoa học, tổ Tin học Khoa Kỹ thuật trường Cao đẳng Kinh tế - Kỹ thuật Hải Dương xây dựng. Cuốn giáo trình này trình bày các vấn đề có bản nhất, thiết yếu nhất về hai khái niệm DỮ LIỆU và GIẢI THUẬT, đó cũng là nền tảng quan trọng cho những ai muốn nghiên cứu trong lĩnh vực tin học. Nội dung cuốn sách gồm 5 chương * Chương 1: MỘT SỐ KHÁI NIỆM: trình bày một số khái niệm về thuật toán: Ký hiệu ô lớn và các phương pháp phân tích, đánh giá truật toán; cấu trúc dữ liệu: Các kiểu dữ liệu trừu tượng cùng các phép toán trên các kiểu dữ liệu đó. Ở đây trình bày hệ kiểu cấu trúc Dữ liệu của ngôn ngữ lập trình Pascal. * Chương 2: GIẢI THUẬT ĐỆ QUY: trình bày về đệ quy, một số thuật toán ứng dụng đệ quy. * Chương 3: CÁC THUẬT TOÁN SẮP XẾP VÀ TÌM KIẾM: trình bày nội dung, giải thuật của một số thuật toán sắp xếp, tìm kiếm cơ bản, hay gặp. So sánh, đánh giá, nhận xét ưu nhược điểm của mỗi loại thuật toán. * Chương 4: DANH SÁCH LIÊN KẾT: trình bày mô hình dữ liệu kiểu Danh sách, các cấu trúc dữ liệu cài đặt danh sách, các phép toán trên danh sách. Trong đó hai cấu trúc đặc biệt STACK và QUEUE được nghiên cứu kỹ . * Chương 5: CÂY: trình bày cấu trúc dữ liệu Cây: Biểu diễn cây cùng với các phép toán cơ bản trên cây, trong đó Cây nhị phân được đặc biệt chú ý. Đọc xong cuốn sách này người đọc được cung cấp đầy đủ các khái niệm, các thuật toán từ cơ bản đến nâng cao, phù hợp cho Giảng viên cũng như HS - SV ngành Khoa KỸ THUẬT_ Trường Cao đẳng Kinh tế - Kỹ thuật Hải Dương
Giáo trình Cấu trúc dữ liệu 3 Công nghệ Tin học nghiên cứu học tập. Toàn bộ các chương, mục đều có ví dụ, hình vẽ minh hoạ cụ thể. Cuối mỗi chương đều có phần tóm tắt lại những ý chính, những ví dụ ứng dụng và bài tập (Lý thuyết và thực hành) để bạn đọc có thể đúc rút được nội dung, củng cố được kiến thức của mỗi chương. Do tính đặc thù của ngôn ngữ lập trình Pascal nên toàn bộ các ví dụ, bài tập trong giáo trình đều được viết bằng ngôn ngữ lập trình này, vì vậy người đọc chỉ cần biết sử dụng ngôn ngữ Pascal ngoài ra không đòi hỏi các kiến thức chuyên môn khác. Chúng tôi đã có nhiều cố gắng trong việc trình bày tinh giản một khối lượng kiến thức đồ sộ, cố gắng đặt vấn đề và giải quyết vấn đề, trình bày các khái niệm thật Logic, tự nhiên, sử dụng ngôn từ trong sáng, các ví dụ sát với thực tế dễ hiểu, dễ áp dụng, các bài tập có tính khả thi cao nhưng cũng không quá khó để giúp bạn đọc dễ dàng hơn trong nghiên cứu, học tập. Tuy vậy cuốn sách chắc chắn không tránh khỏi những thiếu sót, những vấn đề cần bổ xung, những vấn đề cần lược bỏ, Chúng tôi chân thành mong nhận được ý kiến đóng góp, phê bình của độc giả để cuốn sách này có thể hoàn chỉnh hơn nữa. Thư góp ý xin gửi về địa chỉ: phamhuy_ktkt@yahoo.com Tôi xin chân thành cảm ơn Thầy chuyên gia Trịnh Nhật Tiến (Trưởng khoa Công nghệ thông tin trường ĐH Công nghệ Hà Nội) cùng các thầy giáo trong tổ bộ môn Tin học, khoa Kỹ thuật trường Cao đẳng Kinh tế - Kỹ thuật Hải Dương đã đọc bản thảo và góp nhiều ý kiến về nội dung để tôi có thể hoàn thành cuốn tài liệu này. Hải Dương, tháng 8 năm 2005 Tác giả: Khoa KỸ THUẬT_ Trường Cao đẳng Kinh tế - Kỹ thuật Hải Dương
Giáo trình Cấu trúc dữ liệu 4 PHẠM TRỌNG HUY Khoa KỸ THUẬT_ Trường Cao đẳng Kinh tế - Kỹ thuật Hải Dương
Giáo trình Cấu trúc dữ liệu 5 Chương 1: MỘT SỐ KHÁI NIỆM 1.1 Khái niệm thuật toán (Giải thuật) 1.1.1 Khái niệm. Thuật toán là một dãy hữu hạn các quy tắc ( chỉ thị, mệnh lệnh) mô tả chính xác một quá trình tính toán. Theo đó với mỗi bộ dữ liệu vào sẽ cho một kết quả ( Yêu cầu của bài toán ). Các đặc trưng của Thuật toán đơn định: * Tính đơn định: Thực hiện đúng các bước của thuật toán với một dữ liệu vào thì chỉ cho duy nhất một kết quả nghĩa là ở mỗi bước của thuật toán, các thao tác phải hết sức rõ ràng, không gây nên sự nhập nhằng, lộn xộn, đa nghĩa * Tính dừng: Thuật toán phải dừng và cho ra kết quả sau một số hữu hạn các bước. * Tính đúng: Cho ra kết quả phù hợp yêu cầu bài toán với những dữ liệu vào đúng đắn. * Tính phổ dụng: Thuật toán phải giải quyết được một lớp rộng các bài toán. * Tính khả thi: Thuật toán phải được máy tính thực hiện trong khoảng thời gian và điều kiện ( bộ nhớ ) cho phép. Để mô tả một thuật toán có thể sử dụng nhiều phương pháp khác nhau, đối với các bài toán đơn giản phải mô tả Thuật toán một cách tường minh đầy đủ, đối với các bài toán lớn mà trong đó có những thuật toán chuẩn, quen thuộc ta có thể mô tả tổng thể, những chỗ đã biết có thể chú thích hoặc có thể bỏ qua. Khi đó ta chỉ tập trung giải quyết các phần trọng điểm tránh việc làm cho mô tả Thuật toán rắc rối phức tạp. 1.1.2. Các bước phân tích bài toán. Bước đầu tiên trong việc phân tích một thuật toán là xác định đặc trưng dữ liệu sẽ được dùng làm dữ liệu nhập của thuật toán và quyết định phân tích nào là thích Khoa KỸ THUẬT_ Trường Cao đẳng Kinh tế - Kỹ thuật Hải Dương
Giáo trình Cấu trúc dữ liệu 6 hợp. Về mặt lý tưởng, chúng ta muốn rằng với một phân bố tùy ý được cho của dữ liệu nhập, sẽ có sự phân bố tương ứng về thời gian hoạt động của thuật toán. Chúng ta không thể đạt tới điều lý tưởng này cho bất kỳ một thuật toán nào, vì vậy chúng ta chỉ quan tâm đến cách cố gắng chứng minh thời gian chạy luôn luôn nhỏ hơn một “chặn trên” bất chấp dữ liệu nhập như thế nào và cố gắng tính được thời gian chạy trung bình cho dữ liệu nhập “ngẫu nhiên”. Bước thứ hai trong phân tích một thuật toán là nhận ra các thao tác trừu tượng của thuật toán để tách biệt sự phân tích với sự cài đặt. Ví dụ, chúng ta tách biệt sự nghiên cứu có bao nhiêu phép so sánh trong một thuật toán sắp xếp khỏi sự xác định cần bao nhiêu micro giây trên một máy tính cụ thể; yếu tố thứ nhất được xác định bởi tính chất của thuật toán, yếu tố thứ hai lại được xác định bởi tính chất của máy tính. Sự tách biệt này cho phép chúng ta so sánh các thuật toán một cách độc lập với sự cài đặt cụ thể hay độc lập với một máy tính cụ thể. Bước thứ ba trong quá trình phân tích thuật toán là sự phân tích về mặt toán học, với mục đích tìm ra các giá trị trung bình và trường hợp xấu nhất cho mỗi đại lượng cơ bản. Chúng ta sẽ không gặp khó khăn khi tìm một chặn trên cho thời gian chạy chương trình, vấn đề là phải tìm ra một chặn trên tốt nhất, tức là thời gian chạy chương trình khi gặp dữ liệu nhập của trường hợp xấu nhất. Trường hợp trung bình thông thường đòi hỏi một phân tích toán học tinh vi hơn trường hợp xấu nhất. Mỗi khi đã hoàn thành một quá trình phân tích thuật toán dựa vào các đại lượng cơ bản, nếu thời gian kết hợp với mỗi đại lượng được xác định rõ thì ta sẽ có các biểu thức để tính thời gian chạy. Nói chung, tính năng của một thuật toán thường có thể được phân tích ở một mức độ vô cùng chính xác, chỉ bị giới hạn bởi tính năng không chắc chắn của máy tính hay bởi sự khó khăn trong việc xác định các tính chất toán học của một vài đại lượng toán học trừu tượng. Tuy nhiên, thay vì phân tích một cách chi tiết chúng ta thường ước lượng để tránh sa vào chi tiết. 1.1.3. Phân tích Thuật toán: Khoa KỸ THUẬT_ Trường Cao đẳng Kinh tế - Kỹ thuật Hải Dương
Giáo trình Cấu trúc dữ liệu 7 Hầu hết các bài toán đều có nhiều thuật toán khác nhau để giải quyết chúng. Như vậy, làm thế nào để chọn được Thuật toán tốt nhất? Đây là một lĩnh vực được quan tâm nghiên cứu nhiều trong khoa học máy tính. Chúng ta sẽ khảo sát các kết quả nghiên cứu mô tả các tính năng của các thuật toán cơ bản cũng như so sánh các thuật toán đồng thời cũng sẽ khảo sát hướng dẫn tổng quát về phân tích thuật toán. Khi nói đến hiệu quả của một thuật toán, người ta thường quan tâm đến chi phí cần dùng để thực hiện nó. Chi phí này thể hiện qua việc sử dụng tài nguyên như bộ nhớ, thời gian sử dụng CPU, Ta có thể đánh giá thuật toán bằng phương pháp thực nghiệm thông qua việc cài đặt thuật toán rồi chọn các bộ dữ liệu thử nghiệm. Thống kê các thông số nhận được khi chạy các dữ liệu này ta sẽ có một đánh giá về thuật toán. 5 ms Xấu nhất 4 ms 3 ms Tốt nhất 2 ms Trung b ình gian chạy Thời gian 1 ms A B C D E F G Dữ liệu vào Tuy nhiên, phương pháp thực nghiệm có một số nhược điểm sau khiến nó khó có khả năng áp dụng trên thực tế: Khoa KỸ THUẬT_ Trường Cao đẳng Kinh tế - Kỹ thuật Hải Dương
Giáo trình Cấu trúc dữ liệu 8  Do phải cài đặt bằng một ngôn ngữ lập trình cụ thể nên thuật toán sẽ chịu sự hạn chế của ngôn ngữ lập trình này.  Hiệu quả của thuật toán sẽ bị ảnh hưởng bởi trình độ của người cài đặt.  Việc chọn được các bộ dữ liệu thử nghiệm đặc trưng cho tất cả tập các dữ liệu vào của thuật toán là rất khó khăn và tốn nhiều chi phí.  Các số liệu thu nhận được phụ thuộc nhiều vào phần cứng mà thuật toán được thử nghiệm trên đó. Điều này khiến cho việc so sánh các thuật toán khó khăn nếu chúng được thử nghiệm ở những máy tính khác nhau. Vì những lý do trên, người ta đã tìm kiếm những phương pháp đánh giá thuật toán hình thức hơn, ít phụ thuộc môi trường cũng như phần cứng hơn. Một phương pháp như vậy là phương pháp đánh giá thuật toán theo hướng xấp xỉ tiệm cận qua các khái niệm toán học O lớn O(); o nhỏ o(); (); (). Thông thường các vấn đề mà chúng ta giải quyết có một “kích thước” tự nhiên (thường là số lượng dữ liệu được xử lý) mà chúng ta sẽ gọi là N. Chúng ta muốn mô tả tài nguyên cần được dùng (thông thường nhất là thời gian cần thiết để giải quyết vấn đề) như một hàm số theo N. Chúng ta quan tâm đến trường hợp trung bình, tức là thời gian cần thiết để xử lý dữ liệu nhập thông thường T(n), và cũng quan tâm đến trường hợp xấu nhất, tương ứng với thời gian cần thiết khi dữ liệu rơi vào trường hợp xấu nhất có thể có. Việc xác định chi phí trong trường hợp trung bình thường được quan tâm nhiều nhất vì nó đại diện cho đa số trường hợp sử dụng thuật toán. Tuy nhiên, việc xác định chi phí trung bình này lại gặp nhiều khó khăn. Vì vậy, trong nhiều trường hợp, người ta xác định chi phí trong trường hợp xấu nhất (chặn trên) thay cho việc xác định chi phí trong trường hợp trung bình. Hơn nữa, trong một số bài toán, việc xác định chi phí trong trường hợp xấu nhất là rất quan trọng. Ví dụ, các bài toán trong hàng không, phẫu thuật, Khoa KỸ THUẬT_ Trường Cao đẳng Kinh tế - Kỹ thuật Hải Dương
Giáo trình Cấu trúc dữ liệu 9 Như đã được chú ý ở trên, hầu hết các thuật toán đều có một tham số chính là N, thông thường đó là số lượng các phần tử dữ liệu được xử lý mà ảnh hưởng rất nhiều tới thời gian chạy. Tham số N có thể là bậc của một đa thức, kích thước của một tập tin được sắp xếp hay tìm kiếm, số nút trong một đồ thị, v.v Thông thường để đánh giá thuật toán người ta dựa trên hai tiêu chuẩn sau: Tiêu chuẩn 1 Độ đơn giản, dễ hiểu, dễ cài đặt ( viết chương trình ). Tiêu chuẩn 2 Sử dụng tiết kiệm tài nguyên hệ thống và với thời gian ngắn nhất. Tuỳ từng trường hợp mà một trong hai tiêu chuẩn trên được quan tâm, chẳng hạn khi viết một chương trình chỉ để sử dụng một số ít lần, và thời gian để viết chương trình với thuật toán theo tiêu chuẩn 2 lại mất nhiều hơn một thuật toán khác đơn giản ngắn gọn hơn thì tiêu chuẩn 1 được chú trọng, ngược lại nếu một chương trình đợc sử dụng nhiều lần ( chương trình con ) hoặc nhiều người sử dụng thì tiêu chuẩn 2 lại rất quan trọng. Một ví dụ điển hình với bài toán cổ Tháp Hà nội như sau: Có 3 cọc A, B,C lúc đầu ở cọc A có m đĩa được lồng vào theo thứ tự đĩa bé ở trên, yêu cầu là phải chuyển toàn bộ số đĩa từ cọc A sang cọc B và cũng được sắp xếp theo trật tự đĩa bé ở trên. Ở đây cọc C đóng vai trò là cọc trung gian trong quá trình chuyển đĩa, các đĩa tại cọc C cũng tuân theo quy tắc đĩa bé ở trên. A C B Khoa KỸ THUẬT_ Trường Cao đẳng Kinh tế - Kỹ thuật Hải Dương
Giáo trình Cấu trúc dữ liệu 10 Hình minh hoạ bài toán Tháp Hà Nội Để chuyển m đĩa từ cọc A sang cọc B ta thực hiện thuật toán, đầu tiên chuyển m -1 đĩa ở trên cùng sang cột C, sau đó chuyển đĩa lớn nhất từ cột A sang cột B, thuật toán được thực hiện đệ quy cho đến đĩa cuối cùng. Như vậy ta thấy nếu m=1 thì cần 1 lần chuyển, nếu m=2 cần 3 lần chuyển, nếu m=3 cần 7 lần chuyển quy nạp ta được với mọi m ta cần 2 m-1 lần chuyển. Vậy nếu m lớn thì thời gian để thực hiện thuật toán là không thể. Giả sử m = 30 thì số lần chuyển là 107374824 và nếu mỗi lần chuyển mất 01 giây thì cũng cần chuyển trong khoảng 1243 ngày liên tục, như vậy thuật toán đó là bất khả thi. Hầu hết tất cả các thuật toán trong giáo trình này có thời gian chạy tiệm cận tới một trong các hàm sau: a. Hằng số: Hầu hết các chỉ thị của các chương trình đều được thực hiện một lần hay nhiều nhất chỉ một vài lần. Nếu tất cả các chỉ thị của cùng một chương trình có tính chất này thì chúng ta sẽ nói rằng thời gian chạy của nó là hằng số. Điều này hiển nhiên là điều mà ta phấn đấu để đạt được trong việc thiết kế thuật toán. b. LogN: Khi thời gian chạy của chương trình là logarit tức là thời gian chạy chương trình tiến chậm khi N lớn dần. Thời gian chạy thuộc loại này xuất hiện trong các chương trình mà giải một bài toán lớn bằng cách chuyển nó thành một bài toán nhỏ hơn, bằng cách cắt bớt kích thước một hằng số nào đó. Với mục đích của chúng ta, thời gian chạy có được xem như nhỏ hơn một hằng số “lớn“. Cơ số của logarit làm thay đổi hằng số đó nhưng không nhiều: Khi N là 1000 thì logN là 3 nếu cơ số là 10, là 10 nếu cơ số là 2; khi N là một triệu, logN được nhân gấp đôi. bất cứ khi nào N được nhân đôi, logN tăng lên thêm một hằng số. c.N: Khi thời gian chạy của một chương trình là tuyến tính, nói chung đây là trường hợp mà một số lượng nhỏ các xử lý được làm cho mỗi phần tử dữ liệu nhập. Khoa KỸ THUẬT_ Trường Cao đẳng Kinh tế - Kỹ thuật Hải Dương
Giáo trình Cấu trúc dữ liệu 11 Khi N là một triệu thì thời gian chạy cũng cỡ như vậy. Khi N được nhân gấp đôi thì thời gian chạy cũng được nhân gấp đôi. Đây là tình huống tối ưu cho một thuật toán mà phải xử lý N dữ liệu nhập (hay sản sinh ra N dữ liệu xuất). d. NlogN: Đây là thời gian chạy tăng dần lên cho các thuật toán mà giải một bài toán bằng cách tách nó thành các bài toán con nhỏ hơn, kế đến giải quyết chúng một cách độc lập và sau đó tổ hợp các lời giải. Chúng ta nói rằng thời gian chạy của thuật toán như thế là “NlogN”. Khi N là một triệu, NlogN khoảng 20 triệu. khi N được nhân gấp đôi, thời gian chạy bị nhân lên nhiều hơn gấp nhiều đôi. e.N 2: Khi thời gian chạy của một thuật toán là bậc hai, trường hợp này chỉ có ý nghĩa thực tế cho các bài toán tương đối nhỏ. Thời gian bình phương thường tăng dần lên trong các thuật toán mà xử lý tất cả các phần tử dữ liệu (có thể là hai vòng lặp lồng nhau). Khi n là một ngàn thì thời gian chạy là 1 triệu. khi N được nhân đôi thì thời gian chạy tăng lên gấp 4 lần. f.N 3: Tương tự, một thuật toán mà xử lý các bộ ba của các phần tử dữ liệu (có thể là 3 vòng lặp lồng nhau) có thời gian chạy bậc ba và cũng chí ý nghĩa thực tế trong các bài toán nhỏ. Khi N là một trăm thì thời gian chạy là một triệu. Khi N được nhân đôi thì thời gian chạy tăng lên gấp 8 lần. g. 2N: Một số ít thuật toán có thời gian chạy lũy thừa lại thích hợp trong một số trường hợp thực tế. Khi N là hai mươi thì thời gian chạy là 1 triệu. khi N tăng gấp đôi thì thời gian chạy được nâng lên luỹ thừa hai! Thời gian chạy của một chương trình cụ thể đôi khi là một hệ số hằng nhân với các số hạng nói trên (“số hạng dẫn đầu”) cộng thêm một số hạng nhỏ hơn. Giá trị của hệ số hằng và các số hạng phụ thuộc vào kết quả của sự phân tích và các chi tiết cài đặt. Hệ số của số hạng dẫn đầu liên quan tới số chỉ thị bên trong vòng lặp: Ở một tầng tùy ý của thiết kế thuật toán thì phải cẩn thận giới hạn số chỉ thị như thế. Với N lớn thì các số hạng dẫn đầu đóng vai trò chủ chốt; với N nhỏ thì các số hạng cùng đóng góp vào sự so sánh các thuật toán sẽ khó khăn hơn. Trong hầu hết các trường hợp, chúng ta sẽ gặp các chương trình có thời gian chạy là “tuyến tính”, “NlogN”, “bậc ba”, Khoa KỸ THUẬT_ Trường Cao đẳng Kinh tế - Kỹ thuật Hải Dương
Giáo trình Cấu trúc dữ liệu 12 với hiểu ngầm là các phân tích hay nghiên cứu thực tế phải được làm trong trường hợp mà tính hiệu quả là rất quan trọng. 1.1.4. Ví dụ về việc xác định độ phức tạp của thuật toán: Ví dụ với bài toán tính tổng các số nguyên dương từ 1 đến n ta có thể tính theo thuật toán sau: Input n; Tong:=0; For i:= 1 to n do Tong := Tong + i; Output Tong; Với thuật toán này thời gian tính toán tỷ lệ thuận với n, khi n càng lớn thì thời gian càng tốn hay độ phức tạp tính toán là O(n) Nếu tính tổng các số nguyên dương từ 1 đến n theo thuật toán: Input n; Tong := n*(n+1)/2; Output Tong; Thì độ phức tạp tính toán này là O(1) không phụ thuộc vào giá trị n 1.2. Khái niệm cấu trúc dữ liệu (CTDL ) Máy tính điện tử đã được phát minh với chủ đích như là một thiết bị có khả năng làm thuận tiện cho những tính toán phức tạp và tốn nhiều thời gian, nhưng cùng với sự phát triển công nghệ, ngày nay trong đa số các ứng dụng tính toán thì khả năng truy xuất và lưu trữ các khối thông tin lớn đóng vai trò chủ yếu. Thông tin được lưu trữ bao gồm một tập hợp các dữ liệu mà từ đó sau một quá trình xử lý, tổng hợp có thể thu được kết quả mong muốn. Vì vậy việc xây dựng và tổ chức thông tin trên máy tính phải đảm bảo tính xác thực của vấn đề, phù hợp với bản chất của vấn đề. Việc Khoa KỸ THUẬT_ Trường Cao đẳng Kinh tế - Kỹ thuật Hải Dương
Giáo trình Cấu trúc dữ liệu 13 chọn lựa tuỳ thuộc vào hướng giải quyết vấn đề và công cụ để giải quyết vấn đề đó. Có những vấn đề chỉ thích ứng với một cách tổ chức thông tin nhất định, đối với những cách tổ chức thông tin khác thì sẽ kém hiệu quả hoặc không thực hiện được. Cách tổ chức thông tin như vậy chính là bước xây dựng Cấu trúc dữ liệu. 1.2.1- Vai trò của cấu trúc dữ liệu trong thuật toán, chương trình: Giải một bài toán thực chất là chuyển bài toán thực tế thành một bài toán có thể giải quyết trên máy tính. Mà một bài toán thực tế bất kỳ đều bao gồm các đối tượng dữ liệu và các yêu cầu xử lý trên các đối tượng đó. Như vậy, để phản ánh được bài toán thực tế, cần chú trọng đến hai vấn đề:  Tổ chức biểu diễn các đối tượng thực tế ( Xây dựng cấu trúc dữ liệu ): Các đối tượng dữ liệu thực tế rấ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 sao cho vừa có thể phản ánh chính xác các dữ liệu thực tế đó, để vừa có thể lưu trữ và có thể dễ dàng dùng máy tính để xử lý.  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 tác động lên dữ liệu để 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. 1.2.2 Mối quan hệ giữa Giải thuật và CTDL Trên thực tế khi giải quyết một bài toán trên máy tính chúng ta thường có khuynh hướng chỉ chú trọng đến việc xây dựng giải thuật mà quên đi tầm quan trọng của việc tổ chức dữ liệu trong bài toán. Cần nhớ rằng: Giải thuật phản ánh các phép xử lý, còn đối tượng xử lý của giải thuật lại là dữ liệu, chính dữ liệu chứa đựng các thông tin cần thiết để thực hiện giải thuật. Vì vậy để xác định được giải thuật phù hợp cần phải biết nó tác động đến loại dữ liệu nào (ví dụ để làm nhuyễn các hạt đậu, người ta dùng cách xay chứ không băm bằng dao, vì đậu sẽ văng ra ngoài và sẽ mất thời gian hơn nhiều) và khi chọn lựa cấu trúc dữ liệu cũng cần phải hiểu rõ những thao tác Khoa KỸ THUẬT_ Trường Cao đẳng Kinh tế - Kỹ thuật Hải Dương
Giáo trình Cấu trúc dữ liệu 14 nào sẽ tác động đến nó (ví dụ để biểu diễn điểm số của sinh viên người ta dùng số thực thay vì chuỗi ký tự vì còn phải thực hiện thao tác tính trung bình từ những điểm số đó). Như vậy trong một bài toán, giải thuật và cấu trúc dữ liệu có mối quan hệ với nhau, chúng được thể hiện qua công thức nổi tiếng của nhà toán học người Thụy sĩ Niklaus Wirth - là tác giả của ngôn ngữ lập trình Pascal như sau: Cấu trúc dữ liệu + Giải thuật = Chương trình Với một cấu trúc dữ liệu đã chọn, sẽ có những giải thuật tương ứng, phù hợp. Khi cấu trúc dữ liệu thay đổi thường giải thuật cũng phải thay đổi theo để tránh việc xử lý gượng ép, thiếu tự nhiên trên một cấu trúc không phù hợp. Hơn nữa, một cấu trúc dữ liệu tốt sẽ giúp giải thuật xử lý trên đó có thể phát huy tác dụng tốt hơn, vừa đáp ứng nhanh vừa tiết kiệm tài nguyên, đồng thời giải thuật cũng dễ hiểu và đơn giản hơn. * Các tiêu chuẩn đánh giá cấu trúc dữ liệu: Qua phần trên ta đã thấy được vai trò và tầm quan trọng của việc lựa chọn một phương án tổ chức dữ liệu thích hợp trong một chương trình hay một đề án tin học. Một cấu trúc dữ liệu tốt phải thoả mãn các tiêu chuẩn sau: 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ế. Ví dụ: Một số trường hợp chọn cấu trúc dữ liệu sai:  Chọn một số nguyên integer để lưu trữ điểm trung bình của sinh viên (được tính theo công thức trung bình cộng của các môn học có hệ số), như vậy sẽ làm tròn mọi điểm số của sinh viên gây ra việc đánh giá sinh viên không chính xác qua điểm số. Trong 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ế cũng như phản ảnh chính xác kết quả học tập của sinh viên. Khoa KỸ THUẬT_ Trường Cao đẳng Kinh tế - Kỹ thuật Hải Dương
Giáo trình Cấu trúc dữ liệu 15  Trong một lớp có 50 học sinh, mỗi tháng đóng quỹ lớp 1.000 đồng. Ta sử dụng một biến số nguyên kiểu Word (khả năng lưu trữ 0 – 65535) để lưu trữ tổng tiền quỹ của lớp học trong tháng, nếu xảy ra trường hợp trong hai tháng liên tiếp không có chi hoặc tăng tiền đóng quỹ của mỗi học sinh lên 2.000 đồng thì tổng qũy lớp thu được là 100.000 đồng, vượt khỏi khả năng lưu trữ của biến đã chọn, gây nên tình trạng tràn bộ nhớ, sai lệch kết quả. Như vậy khi chọn biến dữ liệu ta phải tính đến trường hợp phát triển của các đại lượng chứa trong biến qua đó chọn kiểu dữ liệu thích hợp. Trong trường hợp trên ta có thể chọn kiểu LongInt (có kích thước 4 bytes, khả năng lưu trữ là -2147483648 2147483647) để lưu trữ tổng tiền quỹ lớp. Phù hợp với các thao tác xử lý: tiêu chuẩn này giúp tăng tính hiệu quả giải bài toán: 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ý. Ví dụ: trường hợp chọn cấu trúc dữ liệu không phù hợp  Khi muốn lưu một danh sách gồm 100 người với các thông số kèm theo như ( Giới tính, ngày sinh, quê quán, địa chỉ hiện nay, nghề nghiệp, ) thì không thể sử dụng cấu trúc mảng được. Vì khi đó việc tổ chức thông tin sẽ rất khó và thực tế khi có sự cập nhật thay đổi của danh sách ( ví dụ như trường địa chỉ hiện nay, nghề nghiệp ) các thao tác gặp nhiều khó khăn. 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ó hai loại tài nguyên cần lưu tâm nhất là CPU và bộ nhớ. Tiêu chuẩn này nên cân nhắc tuỳ vào tình huống cụ thể khi thực hiện đề án. Nếu tổ chức sử dụng đề án cần có những xử lý nhanh thì chọn cấu trúc dữ liệu có yếu tố tiết kiệm thời gian xử lý ưu tiên hơn tiêu chuẩn sử dụng tối ưu bộ nhớ, và ngược lại. Ví dụ: Trường hợp chọn cấu trúc dữ liệu gây lãng phí  Sử dụng biến integer (2 bytes) để lưu trữ một giá trị thông tin về ngày trong tháng. Vì một tháng chỉ có thể nhận các giá trị từ 1-31 nên chỉ cần sử dụng biến Byte (1 byte) là đủ. Khoa KỸ THUẬT_ Trường Cao đẳng Kinh tế - Kỹ thuật Hải Dương
Giáo trình Cấu trúc dữ liệu 16  Để lưu trữ danh sách nhân viên trong công ty mà sử dụng mảng 1000 phần tử. Nếu số lượng nhân viên thật sự ít hơn 1000 (bị giảm hoặc biên chế không đủ) 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. 1.1.3 Khái niệm về kiểu dữ liệu: Máy tính chỉ có thể lưu trữ dữ liệu ở dạng nhị phân sơ cấp. Để phản ảnh được dữ liệu thực tế đa dạng và phong phú, cần phải xây dựng các phép ánh xạ, những quy tắc tổ chức phức tạp che lên tầng dữ liệu thô, nhằm đưa ra những khái niệm logic về hình thức lưu trữ khác nhau thường được gọi là kiểu dữ liệu. Như đã phân tích ở mục trước, giữa hình thức lưu trữ dữ liệu và các thao tác xử lý trên đó có quan hệ mật thiết với nhau. Từ đó có thể đưa ra một định nghĩa cho kiểu dữ liệu như sau: 1.2.3.1 Đị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: Tập các giá trị hợp lệ mà một đối tượng kiểu T có thể lưu trữ. O: Tập các thao tác xử lý có thể thi hành trên đối tượng kiểu T. Ví dụ: – Giả sử có dữ liệu kiểu ký tự = với Vc = {a-z, A-Z} Oc = {lấy mã ASCII của ký tự, biến đổi ký tự thường thành ký tự hoa } – Giả sử có kiểu dữ liệu số nguyên = với Vi = {–32768 32767} Oi = {+, – , *, /, % } Như vậy, muốn sử dụng một kiểu dữ liệu cần nắm vững cả nội dung dữ liệu được lưu trữ và các xử lý tác động trên đó. Khoa KỸ THUẬT_ Trường Cao đẳng Kinh tế - Kỹ thuật Hải Dương
Giáo trình Cấu trúc dữ liệu 17 Các thuộc tính của một kiểu dữ liệu bao gồm: Tên kiểu dữ liệu Miền giá trị Kích thước lưu trữ Tập các toán tử tác động lên kiểu dữ liệu 1.2.3.2- Các kiểu dữ liệu cơ bản Các loại dữ liệu cơ bản thường là các loại dữ liệu đơn giản, không có cấu trúc. Chúng thường là các giá trị vô hướng như các số nguyên, số thực, các ký tự, các giá trị logic, Các loại dữ liệu này do tính thông dụng và đơn giản của nó, thường được các ngôn ngữ lập trình cấp cao xây dựng sẵn như một thành phần của ngôn ngữ để giảm nhẹ công việc cho người lập trình. Chính vì vậy đôi khi người ta còn gọi chúng là các kiểu dữ liệu định sẵn. Thông thường, các kiểu dữ liệu cơ bản gồm: Kiểu có thứ tự rời rạc: số nguyên, ký tự, logic, liệt kê, miền con, Kiểu không rời rạc: số thực Tùy ngôn ngữ lập trình, các kiểu dữ liệu định nghĩa sẵn có thể khác nhau đôi chút. Với ngôn ngữ C, các kiểu dữ liệu này chỉ gồm số nguyên, số thực, ký tự. Và theo quan điểm của C, kiểu ký tự thực chất cũng là kiểu số nguyên về mặt lưu trữ, chỉ khác về cách sử dụng. Ngoài ra, giá trị logic ĐÚNG (TRUE) và giá trịc logic SAI (FALSE) được biểu diễn trong Pascal như là các giá trị nguyên khác zero và zero. Trong khi đó PASCAL định nghĩa tất cả các kiểu dữ liệu cơ sở đã liệt kê ở trên và phân biệt chúng một cách chặt chẽ. Trong giáo trình này sử dụng ngôn ngữ Pascal để minh hoạ. Khoa KỸ THUẬT_ Trường Cao đẳng Kinh tế - Kỹ thuật Hải Dương
Giáo trình Cấu trúc dữ liệu 18 Các kiểu dữ liệu định sẵn trong Pascal gồm: Tên kiểu Kthước Miền giá trị Ghi chú Char 1 byte 0 255 Kiểu ký tự, không dấu Byte 1 byte 0 255 Số nguyên, không dấu Integer 2 bytes -32768 32767 Số nguyên, có dấu Word 2 byte 0 65535 Số nguyên, không dấu ShortInt 1 byte -128 127 Số nguyên, có dấu LongInt 4 bytes -232 231-1 Số nguyên, có dấu Boolean 1 byte TRUE hay FALSE Kiểu Logic Real 6 byte 2.9 E-39 2.9 E+38 Kiểu thực, có 11 số có giá trị Extended 10 byte 3.4 E-4932 1.1 E+4932 Kiểu thực 1.2.3.3- Các kiểu dữ liệu có cấu trúc Các kiểu dữ liệu cơ sở rất thô sơ, đơn giản và không phản ánh được các đối tượng tự nhiên cũng như đầy đủ yếu tố của sự vật thực tế, do đó dẫn đến nhu cầu phải xây dựng các kiểu dữ liệu mới dựa trên việc tổ chức, liên kết các thành phần dữ liệu có kiểu dữ liệu cơ sở đã được định nghĩa. Những kiểu dữ liệu được xây dựng như thế gọi là kiểu dữ liệu có cấu trúc. Hầu hết các ngôn ngữ lập trình đều cài đặt sẵn một số kiểu có cấu trúc cơ bản như mảng chuỗi, tập tin, bản ghi và cung cấp cơ chế cho lập trình viên tự định nghĩa kiểu dữ liệu mới. Ví dụ: Để mô tả một đối tượng nhân viên, cần quan tâm đến các thông tin sau: - Mã nhân viên : chuỗi ký tự Khoa KỸ THUẬT_ Trường Cao đẳng Kinh tế - Kỹ thuật Hải Dương
Giáo trình Cấu trúc dữ liệu 19 - Tên nhân viên : chuỗi ký tự - Chức vụ : chuỗi ký tự - Trình độ : chuỗi ký tự - Số năm công tác: số nguyên - Ngày sinh : kiểu ngày tháng năm - Nơi sinh : chuỗi ký tự - Lương cơ bản : số nguyên TYPE Nhansu = Record MaNV : String[5] ; HoTen : String[30] ; ChucVu : String[3] ; TrinhDo : String[15] ; SoNamCT : Byte ; NgaySinh : Record NgaySinh : 1 31 ; ThangSinh : 1 12 ; NamSinh : Integer; End ; NoiSinh : String[30] ; LuongCB : LongInt; Khoa KỸ THUẬT_ Trường Cao đẳng Kinh tế - Kỹ thuật Hải Dương
Giáo trình Cấu trúc dữ liệu 20 End ; Ở đây ta sử dụng cấu trúc bản ghi ( Record ) với mỗi trường là một thuộc tính của Danh sách các đối tượng nhân viên. Giả sử đã có cấu trúc phù hợp để lưu trữ một nhân viên, nhưng thực tế lại cần quản lý nhiều nhân viên, lúc đó nảy sinh nhu cầu xây dựng kiểu dữ liệu mới sử dụng mảng các bản ghi. Mục tiêu của việc nghiên cứu cấu trúc dữ liệu chính là tìm những phương cách thích hợp để tổ chức, liên kết dữ liệu, hình thành các kiểu dữ liệu có cấu trúc từ những kiểu dữ liệu đã được định nghĩa. 1.2.3.4 Một số kiểu dữ liệu có cấu trúc cơ bản a. Kiểu chuỗi ký tự: Chuỗi ký tự là một trong các kiểu dữ liệu có cấu trúc đơn giản nhất và thường các ngôn ngữ lập trình đều định nghĩa nó như một kiểu cơ bản. Do tính thông dụng của kiểu chuỗi ký tự các ngôn ngữ lập trình luôn cung cấp sẵn một bộ các hàm thư viện xử lý trên kiểu dữ liệu này. Chuỗi ký tự trong Pascal được cấu trúc như một chuỗi liên tiếp các ký tự nằm trong bảng mã ASCII. Kiểu ký tự được định nghĩa bởi từ khoá Char, các ký tự được đặt trong dấu nháy đơn ( ' ' ). Các thao tác trên chuỗi ký tự rất đa dạng. Sau đây là một số thao tác và hàm thông dụng: Ký hiệu Phép toán Ví dụ = So sánh bằng 'A' = 'B' False > So sánh lớn hơn 'A' > 'B' False = So sánh lớn hơn hoặc bằng 'A' >= 'B' False Khoa KỸ THUẬT_ Trường Cao đẳng Kinh tế - Kỹ thuật Hải Dương
Giáo trình Cấu trúc dữ liệu 21 So sánh khác nhau 'A' <> 'B' True Cho kết quả là thứ tự của ký tự ch Ord(ch) Ord('A') =65 trong bảng mã ASCII Cho kết quả là ký tự có số thứ tự là Chr(n), # chr(65) = 'A' n trong bảng ASCII Cho kết quả là ký tự đứng trước ký Pred(ch) Pred('B')= 'A' tự ch trong bảng ASCII Cho kết quả là ký tự đứng sau ký tự Succ(ch) Succ('A')= 'B' ch trong bảng ASCII Upcase(ch) Đổi chữ thường thành chữ hoa Upcase('a')= 'A' b. Kiểu mảng (array): Mảng là một tập hợp hữu hạn các giá trị, có sét thứ tự và có cùng kiểu cấu trúc, thường được lưu trữ liên tiếp nhau trong bộ nhớ. Mảng có thể một chiều hay nhiều chiều. Một dãy số chính là hình tượng của mảng 1 chiều, ma trận là hình tượng của mảng 2 chiều. Trong Pascal mảng được khai báo như sau: Ten_mang = Array[ Kieu_chi_dan ] Of Kieu_phan_tu; Ten_mang = Array[ KieuCD1, KieuCD2 ] Of Kieu_phan_tu; Các bài toán trên mảng thường gặp như: tìm kiếm giá trị, tính tần suất, thống kê giá trị, sắp xếp, đổi vị trí c. Kiểu Xâu kí tự (String): Khoa KỸ THUẬT_ Trường Cao đẳng Kinh tế - Kỹ thuật Hải Dương
Giáo trình Cấu trúc dữ liệu 22 Là một kiểu dữ liệu dùng để xử lý các chuỗi ký tự có chiều dài không cố định, Kiểu String có nhiều đặc điểm giống như kiểu mảng ( cũng là tập hợp các giá trị có cùng kiểu và có xét đến vị trí của mỗi phần tử ) nhưng số ký tự trong một xâu có thể thay đổi từ 0 đến giá trị cực đại được khai báo trong khi mang ký tự thi luôn có chiều dài cố định. Một số phép toán và hàm trên String Với st ( String ): Xâu ; Lo ( Location ): Vị trí; Nu ( Number ): giá trị số Val ( Value): Giá trị kiểu nguyên hoặc thực; Var_i ( Variable): biến số nguyên hoặc thực, Obj ( Object ): đối tượng hay có thể là một xâu. Hàm hoặc thủ tục Ý nghĩa Length(st); Cho độ dài thực của xâu Delete(st, lo, nu ); Xoá đi nu ký tự trong st từ vị trí lo Insert(Obj, st, lo); Chèn Obj vào xâu st tại vị trí lo Str(val, st ); Đổi giá trị số val thành giá trị xâu ký tự Val(st, var_i, code); Đổi giá trị xâu st thành giá trị số được lưu trong biến var_i, code là mã phát hiện lỗi Copy(st, Lo, Nu ); Nhận nu ký tự trong st bắt đầu từ vị trí lo Concat(st1, st2, , stn ); Ghép các xâu st thành một xâu duy nhất Pos(st1, st2); Cho vị trí của xâu st1 trong xâu st2 Các bài toán thường gặp trên xâu như: chuẩn xâu (đổi chữ thường thành chữ hoa hoặc ngược lại, bỏ những khoẩng trống thừa ), so sánh xâu, sắp xếp, thống kê d. Kiểu bản ghi ( Record ): Khoa KỸ THUẬT_ Trường Cao đẳng Kinh tế - Kỹ thuật Hải Dương
Giáo trình Cấu trúc dữ liệu 23 Là một kiểu dữ liệu với các phần tử dữ liệu có thể khác nhau nhưng có mối liên kết với nhau, là một kiểu dữ liệu linh hoạt để lưu trữ những dự liệu có dạng như Danh sách, biểu bảng thống kê có các nội dung ( trường) khác nhau, trong đó mỗi bản ghi là tập hợp dữ liệu của các trường mô tả về một đối tượng được đề cập. Các bài toán thường gặp trên kiểu dữ liệu bản ghi là: Tìm kiếm, thống kê theo tiêu chuẩn, sắp xếp theo từng trường, tính toán e. Kiểu tệp ( File ): Tập tin trong Pascal là một kiểu dữ liệu có cấu trúc. Mỗi tập tin là một tập hợp các phần tử có chung một kiểu dữ liệu được ghi xuống thiết bị lưu trữ thứ cấp ( các loại bộ nhớ ngoài). Để truy cập đến các phần tử trong tập tin, Pascal sử dụng một biến trung gian chỉ đến vị trí của tập tin trên đĩa gọi là con trỏ tệp. Tại mỗi thời điểm, con trỏ trỏ đúng vào vị trí của một phần tử nào đó trong tập tin, gọi là vị trí hiện thời của tập tin. Kiểu tập tin trong Pascal được chia làm 2 loại chính: tập tin có định kiểu (tệp tin chương trình, tệp âm thanh, tệp hình ảnh ) và tập tin văn bản. Một điểm quan trọng là đối với các kiểu dữ liệu khác, dữ liệu và giá trị các biến sử dụng chỉ tồn tại khi chương trình đang hoạt động, lần chạy chương trình sau lại phải nhập dữ liệu lại vì bộ nhớ được giải phóng khi chương trình đó ngừng hoạt động. Với dữ liệu kiểu tệp, dữ liệu nhập vào có thể được lưu trữ trên bộ nhớ và có thể sử dụng lại cho những lần chạy chương trình sau. Các hàm và thủ tục sử dụng trên dữ liệu kiểu tệp: Hàm, Thủ tục Ý nghĩa Assign(Filevar,' ten_tep_tin'); Khai báo một tên tệp tin cho biến tệp tin F, tên và nội dung tệp tin được lưu trên bộ nhớ thư cấp Rewrite(Filevar); Mở mới một tệp tin Reset(Filevar); Mở một tệp tin đã có Append( F); Mở tệp tin F đã có để nhập thêm dữ liệu Khoa KỸ THUẬT_ Trường Cao đẳng Kinh tế - Kỹ thuật Hải Dương
Giáo trình Cấu trúc dữ liệu 24 Rename(F, ' ten_moi '); Đổi tên tệp tin đang mở thành ten_moi Erase(F); Xoá tệp tin đang mở Flush(F); Giải phóng bộ nhớ bằng cách lưu tệp tin nhưng không đóng tệp tin đó Truncate(F); Cắt ngắn nội dung một tệp tin Seek(F, n); Di chuyển con trỏ tệp tin đến vị trí n Close(F); Đóng tệp tin đang mở FileSize(F); Cho biết số phần tử của tệp tin FilePos(F); Cho biết vị trí hiện tại của con trỏ tệp tin EOF(F); Cho giá trị TRUE nếu con trỏ ở cuối tệp EOLN(F); Cho giá trị TRUE nếu con trỏ ở cuối dòng Các bài toán thường gặp trên dữ liệu kiểu tệp: Lập một cơ sở dữ liệu để lưu dữ liệu dạng quản lý danh sách, hồ sơ như tìm kiếm, cập nhật dữ liệu, thêm bớt dữ liệu TÓM TẮT: Trong chương này, chúng ta đã xem xét các khái niệm về cấu trúc dữ liệu, kiểu dữ liệu. Thông thường, các ngôn ngữ lập trình luôn định nghĩa sẵn một số kiểu dữ liệu cơ bản. Các kiểu dữ liệu này thường có cấu trúc đơn giản. Để thể hiện được các đối tượng đa dạng trong thế giới thực, chỉ dùng các kiểu dữ liệu này là không đủ. Ta cần xây dựng các kiểu dữ liệu mới phù hợp với đối tượng mà nó biểu diễn. Thành phần dữ liệu luôn là một vế quan trọng trong mọi chương trình. Vì vậy, việc thiết kế cấu trúc dữ liệu tốt là một vấn đề đáng quan tâm. Vế thứ hai trong chương trình là các thuật toán (thuật giải). Một chương trình tốt phải có các cấu trúc dữ liệu phù hợp với các thuật toán hiệu quả. Khi khảo sát các thuật toán, chúng ta quan tâm đến chi phí thực hiện thuật toán. Chí phí này bao gồm Khoa KỸ THUẬT_ Trường Cao đẳng Kinh tế - Kỹ thuật Hải Dương
Giáo trình Cấu trúc dữ liệu 25 chi phí về tài nguyên và thời gian cần để thực hiện thuật toán. Nếu như những đòi hỏi về tài nguyên có thể dễ dàng xác định thì việc xác định thời gian thực hiện nó không đơn giản . Có một số cách khác nhau để ước lượng khoảng thời gian này. Tuy nhiên, cách tiếp cận hợp lý nhất là hướng xấp xỉ tiệm cận. hướng tiếp cận này không phụ thuộc ngôn ngữ, môi trường cài đặt cũng như trình độ của lập trình viên. Nó cho phép so sánh các thuật toán được khảo sát ở những nơi có vị trí địa lý rất xa nhau. Tuy nhiên, khi đánh giá ta cần chú ý thêm đến hệ số vô hướng trong kết quả đánh giá. Có khi hệ số này ảnh hưởng đáng kể đến chi phí thực của của thuật toán. Do việc đánh giá chi phí thực hiện trung bình của thuật toán thường phức tạp nên người ta thường đánh giá chi phí thực hiện thuật toán trong trường hợp xấu nhất. Hơn nữa, trong một số thuật toán, việc xác định trường hợp xấu nhất là rất quan trọng. BÀI TẬP CHƯƠNG 1 Bài tập lý thuyết: 1- Tìm thêm một số ví dụ minh hoạ mối quan hệ giữa cấu trúc dữ liệu và giải thuật. 2- Trình bày một số kiểu dữ liệu được định nghĩa sẵn trong ngôn ngữ lập trình Turbo Pasal. Cho các kiểu dữ liệu xây dựng trước này có đủ để đáp ứng mọi yêu cầu về tổ chức dữ liệu không? Ví dụ. 3- Một ngôn ngữ lập trình có nên cho phép người sử dụng tự định nghĩa thêm các kiểu dữ liệu có cấu trúc? giải thích và cho ví dụ. 4- Giả sử có một bảng giờ tàu cho biết thông tin về 20 chuyến tàu khác nhau của mạng đường sắt. Hãy biểu diễn các dữ liệu này bằng một cấu trúc dữ liệu thích hợp sao cho dễ dàng truy xuất giờ khởi hành, giờ đến của một chuyến tàu bất kỳ tại ga. Bài tập thực hành Khoa KỸ THUẬT_ Trường Cao đẳng Kinh tế - Kỹ thuật Hải Dương
Giáo trình Cấu trúc dữ liệu 26 5- Xây dựng thuật toán để giải quyết các bài toán sau: - Kiểm tra số nguyên tố. - Xắp xếp dãy số - Tìm số Min, Max. 6- Giả sử quy tắc tổ chức quản lý nhân viên của một công ty như sau:  Thông tin về một nhân viên bao gồm lý lịch và bảng chấm công: + Lý lịch nhân viên: - Mã nhân viên: chuỗi 8 ký tự - Họ, Tên nhân viên: chuỗi 30 ký tự - Tình trạng gia đình: 1 ký tự (M=Married, S=Single) - Số con: số nguyên 5 - Trình độ văn hoá: chuỗi 2 ký tự (C1 = cấp 1; C2 = cấp 2; C3 = cấp 3; DH = đại học, CH = cao học) - Lương căn bản: số nguyên 5.000.000 + Chấm công nhân viên: - Số ngày nghỉ có phép trong tháng : số nguyên 26 - Số ngày nghỉ không phép trong tháng : số nguyên 26 - Số ngày làm thêm trong tháng : số nguyên 20 - Đánh giá công việc: chuỗi 2 ký tự (TO=Tốt; BT = Đạt ; KE = Kém) - Lương thực lĩnh trong tháng : số nguyên 10.000.000 Khoa KỸ THUẬT_ Trường Cao đẳng Kinh tế - Kỹ thuật Hải Dương
Giáo trình Cấu trúc dữ liệu 27  Chức năng yêu cầu: - Cập nhật lý lịch, bảng chấm công cho nhân viên (thêm, xoá, sửa) - Xem bảng lương hàng tháng - Tìm thông tin của một nhân viên Tổ chức cấu trúc dữ liệu thích hợp để biểu diễn các thông tin trên, và cài đặt chương trình theo các chức năng đã mô tả. Lưu ý: + Nên phân biệt thông tin mang tính chất tĩnh (lý lịch) và động (chấm công hàng tháng) + Số lượng nhân viên tối đa là 50 người. Khoa KỸ THUẬT_ Trường Cao đẳng Kinh tế - Kỹ thuật Hải Dương
Giáo trình Cấu trúc dữ liệu 28 Chương 2: GIẢI THUẬT ĐỆ QUY 2.1. Khái Niệm Ta thấy nhiều ví dụ của các hàm và thủ tục có tham trỏ đến các hàm và thủ tục khác, trường hợp đặc biệt các hàm và thủ tục có thể tham chiếu đến chính hàm hay thủ tục đó ta gọi đó là tính đệ quy. Ta nói một đối tượng là đệ quy nếu nó được định nghĩa qua chính nó hoặc một đối tượng khác cùng dạng với chính nó bằng quy nạp. Định nghĩa: Định nghĩa một hàm hay thủ tục đệ quy gồm hai phần: * Phần Suy biến ( neo: Anchor): Phần này được thực hiện khi bài toán quá đơn giản có thể giải trực tiếp mà không cần phải nhờ đến một thuật toán nào. * Phần đệ quy (Hay phần quy nạp): Trong trường hợp bài toán không thể giải bằng phần neo, ta xác định những bài toán con và gọi đệ quy giải những bài toán con đó. Khi đã có lời giải của những bài toán con rồi thì phối hợp lại để giải bài toán đang quan tâm. Phần đệ quy thể hiện tính " quy nạp " của lời giải. Phần neo cũng rất quan trọng bởi nó quyết định tới tính hữu hạn dừng của lời giải. 2.2. Ví dụ về chương trình con đệ quy. 2.2.1 Hàm tính giai thừa Function Giai_thua(n:integer): integer; {nhËp sè tù nhiªn n vµ tr¶ vÒ n! } Begin if n=0 then Giai_thua :=1 (phÇn neo) else Giai_thua :=n Giai_thua(n-1); (phÇn ®Ö quy) Khoa KỸ THUẬT_ Trường Cao đẳng Kinh tế - Kỹ thuật Hải Dương
Giáo trình Cấu trúc dữ liệu 29 End; Ở đây phần neo định nghĩa kết quả hàm tại n = 0, còn phần đệ quy (ứng với n >0 ) sẽ định nghĩa kết quả hàm qua giá trị của n và giá trị giai thừa của n -1. Ví dụ : Dùng hàm này để tính 3!, trước hết ta phải đi tính 2! Bởi 3! được tính bằng tích của 3*2!. Tương tự để tính 2!, ta lại phải tính 1! Bởi 2! đợc tính bằng 2*1!. Áp dụng bước quy nạp này thêm một lần nữa, ta có 1!=1*0! , và ta đạt được trường hợp của phần neo, đến đây từ giá trị 1 của 0! Ta tính được 1!=1*1=1; từ giá trị của 1! Ta tính được 2!, từ giá trị của 2! Ta tính được 3!; Cuối cùng cho kết quả là 6: 3! = 3*2! 2! = 2*1! 1! = 1*0! 0!=1 2.2.2. Dãy số Fibonacci Dãy số Fibonacci bắt ngiồn từ bài toán cổ về việc sinh sản của loài thỏ. Bài toán dặt ra như sau: * Giả sử các con thỏ không bao giờ chết, và mỗi lần sinh sản chỉ cho một cặp thỏ con ( một đực một cái). * Hai tháng sau khi ra đời, mỗi cặp thỏ sẽ sinh một cặp thỏ con * Khi đã sinh con rồi thì cứ mỗi tháng tiếp theo chúng lại sinh một cặp con mới. Khoa KỸ THUẬT_ Trường Cao đẳng Kinh tế - Kỹ thuật Hải Dương
Giáo trình Cấu trúc dữ liệu 30 Giả sử từ tháng đầu tiên có 1 cặp mới ra đời thì đến tháng thứ n sẽ có bao nhiêu cặp thỏ. Ví dụ với n = 5 ta thấy: Tháng 1: 1 cặp (x,y) ban đầu Tháng 2: vẫn cặp (x,y) ban đầu chưa sinh sản Tháng 3: 2 cặp (x,y);(x1,y1) cặp ban đầu sinh sản thêm một cặp con Tháng 4: 3 cặp (x,y);(x1,y1),(x2,y2) cặp ban đầu tiếp tục đẻ Tháng 5: 5 cặp (x,y);(x1,y1),(x2,y2);(x3,y3);(x4,y4) cặp ban đầu (x,y) và cặp (x1,y1) cùng đẻ. Bây giờ xét tới việc tính số cặp thỏ ở tháng thứ n: (Fn) Nếu mỗi cặp thỏ ở tháng thứ n - 1 đều sinh một cặp thỏ con thì số cặp thỏ ở tháng thứ n sẽ là: F(n) = 2*F(n-1); Nhưng vấn đề không phải như vậy, trong các cặp thỏ ở tháng thứ n - 1 thì chỉ có các cặp thỏ đã có ở tháng thứ n - 2 mới sinh con ở tháng thứ n mà thôi. Do đó F(n) = F( n-1 ) + F(n - 2) (bằng số thỏ cũ F(n - 1) cộng với số thỏ mới sinh ra F(n - 2)). Vậy F(n) có thể tính theo công thức sau: F(n) = 1 ; nếu 0 < n <= 2 F(n) = F(n - 1) + F(n - 2) Đó chính là một ví dụ về tính đệ quy! Đoạn mã chương trình con xác định dãy số Fibonacci Function F(n : integer):integer; Begin Khoa KỸ THUẬT_ Trường Cao đẳng Kinh tế - Kỹ thuật Hải Dương
Giáo trình Cấu trúc dữ liệu 31 If n <=2 then F := 1 Else F := F(n - 1) + F(n - 2); End; 2.3 Hiệu lực của đệ quy Qua các ví dụ trên ta thấy đệ quy là một công cụ mạnh để giải các bài toán. Có những bài toán mà bên cạnh giải thuật đệ quy vẫn có thể giải bằng những giải thuật lặp khá đơn giản và hữu hiệu. ví dụ như bài toán tính giai thừa hay tính số Fibonacci trên. Tuy vậy, đệ quy vẫn có vai trò xứng đáng của nó. Nhưng không phải bao giờ phép đệ quy cũng có thể nhìn nhận và thiết kế dễ dàng như vậy, thế thì vấn đề gì cần lưu tâm trong phép giải đệ quy? Có thể tìm thấy câu trả lời qua việc trả lời các câu hỏi sau: - Có thể định nghĩa được bài toán dưới dạng phối hợp của những bài toán cùng loại nhưng nhỏ hơn hay không? Khái niệm nhỏ hơn là thế nào? - Trường hợp đặc biệt nào của bài toán sẽ được coi là trường hợp tầm thường và có thể giải ngay được để đưa vào phần neo của phép giải đệ quy? Có nhiều bài toán mà việc thiết kế thuật giải đệ quy đơn giản hơn nhiều so với lời giải lặp và trong một số trường hợp chương trình đệ quy hoạt động nhanh hơn chương trình viết không đệ quy. Trở lại bài toán tháp Hà nội ở ví dụ của mục 1.2.3 ta thấy có một mối quan hệ khăng khít giữa đệ quy và quy nạp toán học. Cách giải đệ quy cho một bài toán dựa trên việc định rõ lời giải cho trường hợp suy biến ( neo ) rồi thiết kế làm sao để lời giải của bài toán đợc suy ra từ lời giải của bài toán nhỏ hơn cùng loại. Tương tự quy nạp toán học chứng minh một tính chất nào đó ứng với số tự nhiên cũng bằng cách chứng minh tính chất đó đúng với trường hợp cơ sở sau đó chứng minh tính chất đó đúng với n bất kỳ nếu nó đúng với số n nhỏ hơn. Ta chứng minh số phép chuyển đĩa trong bài toán tháp Hà nội với số đĩa n là 2n -1: - Rõ ràng điều này đúng khi n bằng 1; Khoa KỸ THUẬT_ Trường Cao đẳng Kinh tế - Kỹ thuật Hải Dương
Giáo trình Cấu trúc dữ liệu 32 - Với n > 1; Giả sử để chuyển N - 1 đĩa giữa hai cột cần 2 n-1 - 1 phép chuyển đĩa, khi đó để chuyển n đĩa từ vị trí X sang vị trí Y, với thuật giải đệ quy ta thấy trong trường hợp này cần (2 n-1-1) +1 +(2n-1 - 1) = 2n - 1 phép chuyển đĩa. Tính chất được chứng minh đúng với n. BÀI TẬP 1. Viết một hàm tính ước số chung lớn nhất của hai số tự nhiên a, b không đồng thời bằng 0, xác định rõ đâu là phần neo, đâu là phần đệ quy. k 2. Viết hàm đệ quy tính Cn theo công thức truy hồi sau: 0 n * Cn Cn 1 k k 1 k * Cn Cn 1 Cn 1 Với 0<k<n n! Chứng minh rằng hàm đó cho ra giá trị C k n k!(n k)! 3. Cho bàn cờ có n×n ô. Một con Mã được phép đi trên bàn cờ theo luật cờ vua, đầu tiên con Mã được đặt ở ô có toạ độ x o:yo. Hãy xây dựng thuật giải để tìm đường đi sao cho con Mã đó có thể đi qua tất cả các ô của bàn cờ, mỗi ô đi qua đúng một lần, nghĩa là phải tính n2 -1 nước đi của con Mã đó (Bài toán Mã đi tuần Hình vẽ a. ) Khoa KỸ THUẬT_ Trường Cao đẳng Kinh tế - Kỹ thuật Hải Dương
Giáo trình Cấu trúc dữ liệu 33 4. Cho bàn cờ vua có 8×8 ô. Xây dựng thuật giải để tìm cách đặt lên bàn cờ đó 8 con cờ Hậu sao cho hai con bất kỳ không thể ăn được nhau (Bài toán 8 Hậu Hình vẽ b) 3 2 4 1 y 5 8 6 7 x Hình vẽ a Khoa KỸ THUẬT_ Trường Cao đẳng Kinh tế - Kỹ thuật Hải Dương Hình vẽ b
Giáo trình Cấu trúc dữ liệu 34 Chương 3: CÁC THUẬT TOÁN SẮP XẾP VÀ TÌM KIẾM 3.1. Các thuật toán tìm kiếm 3.1.1. Tìm tuyến tính 3.1.1.1. Giải thuật Tìm kiếm tuyến tính là một kỹ thuật tìm kiếm rất đơn giản và cổ điển. Thuật toán tiến hành so sánh giá trị cần tìm với phần tử thứ nhất, thứ hai, của dãy số cho đến khi gặp được phần tử thoả mãn. Gọi x là giá trị cần tìm và a là mảng chứa dãy số dữ liệu. Các bước tiến hành như sau: Bước 1: i=1; Bước 2 : So sánh a[i] với x, có 2 khả năng : a[i] = x: Tìm thấy. Dừng. a[i] N: hết mảng, không tìm thấy. Dừng Ngược lại: lặp lại bước 2. Trong thuật toán trên, chúng ta thấy rằng công việc tìm kiếm chỉ đơn giản thực hiện bằng một vòng lặp để duyệt qua tất cả các phần tử trong mảng. Vòng lặp chỉ kết thúc khi tìm thấy giá trị x trong mảng hoặc đã duyệt hết các phần tử có trong mảng. Như vậy khi kết thúc vòng lặp chỉ số i có 2 khả năng xảy ra: Khoa KỸ THUẬT_ Trường Cao đẳng Kinh tế - Kỹ thuật Hải Dương
Giáo trình Cấu trúc dữ liệu 35 - i = N có nghĩa là đã duyệt qua phần tử cuối cùng của mảng nhưng vẫn không tìm thấy phần tử nào có giá trị bằng với x. - i a i thì x chỉ có thể xuất hiện trong đoạn [ai+1, aN] của dãy, ngược lại nếu x < ai thì x chỉ có thể xuất hiện trong đoạn Khoa KỸ THUẬT_ Trường Cao đẳng Kinh tế - Kỹ thuật Hải Dương
Giáo trình Cấu trúc dữ liệu 36 [a1, ai-1] của dãy. Giải thuật tìm nhị phân áp dụng nhận xét trên đây để tìm các giới hạn phạm vi tìm kiếm sau mỗi lần so sánh x với một phần tử trong dãy. Ý tưởng của giải thuật là tại mỗi bước tiến hành so sánh x với phần tử nằm ở giữa của dãy tìm kiếm hiện hành, dựa vào kết quả so sánh này để quyết định giới hạn dãy tìm kiếm ở bước kế tiếp là nửa trên hay nửa dưới của dãy tìm kiếm hiện hành. Gọi x là giá trị cần tìm, a là mảng chứa các giá trị dữ liệu gồm N phần tử đã sắp xếp tăng dần, left và right là chỉ số đầu và cuối của đoạn cần tìm, midle là chỉ số của phần tử nằm giữa của đoạn cần tìm. Công việc tìm kiếm được tiến hành như sau: Bước 1: Khởi đầu xác định vùng tìm kiếm trên tất cả các phần tử ban đầu left := 1; right := N; dãy các phần tử là aleft aright Bước 2: gán midle := Int((left+right)/2); So sánh a[midle] với x, có 3 khả năng : * a[midle] = x : Tìm thấy. Dừng * a[midle] > x : Tìm tiếp giá trị x trong dãy con aleft amidle-1 với right := midle – 1; * a[midle] < x: Tìm tiếp giá trị x trong dãy con amidle+1 aright với left := midle + 1; Bước 3: Nếu left < right : Dãy tìm kiếm hiện hành vẫn còn phần tử. Lặp lại bước 2. Ngược lại : Dãy tìm kiếm hiện hành hết phần tử. Dừng. Thuật toán trên cũng chỉ đơn giản sử dụng một vòng lặp để duyệt qua các phần tử trong mảng. Tuy nhiên, vòng lặp này sẽ không duyệt qua hết tất cả các phần tử như đối với tìm kiếm tuyến tính. Tư tưởng của thuật toán này cũng giống như đối với tìm kiếm tuyến tính, nghĩa là khi kết thúc vòng lặp cũng có 2 khả năng xảy ra: Khoa KỸ THUẬT_ Trường Cao đẳng Kinh tế - Kỹ thuật Hải Dương
Giáo trình Cấu trúc dữ liệu 37 - Chỉ số left vẫn còn bé hơn hoặc bằng chỉ số right. Điều này có nghĩa là đã có một phần tử nào đó bằng với giá trị x cần tìm, cụ thể là giá trị của phân tử middle. Do đó, hàm sẽ trả về giá trị nằm trong biến middle. - Chỉ số left đã bằng hoặc vượt qua chỉ số right, nghĩa là đã duyệt qua hết các phần tử trong mảng mà không tìm thấy phần tử nào có giá trị bằng x. 3.1.2.2. Đánh giá thuật toán Trường hợp giải thuật tìm nhị phân ta có bảng phân tích sau: Trường hợp Số lần so sánh Giải thích Phần tử giữa của mảng ban đầu có giá trị Tốt nhất 1 x. Xấu nhất log2 N Phần tử cần tìm nằm ở cuối mảng Giả sử xác xuất các phần tử trong mảng Trung bình log2 N/2 nhận giá trị x là như nhau. Vậy giải thuật tìm nhị phân có độ phức tạp O(logn). Nhận xét Giải thuật tìm nhị phân phụ thuộc vào thứ tự của các phần tử trong mảng để định hướng trong quá trình tìm kiếm, do vậy chỉ áp dụng được cho những dãy đã có thứ tự. Thuật toán tìm kiếm nhị phân tiết kiếm thời gian hơn rất nhiều so với giải thuật tìm tuyến tính do Onhị phân(log2n) < Otuyến tính(n). Tuy nhiên khi muốn áp dụng giải thuật tìm nhị phân cần phải xét đến thời gian sắp xếp dãy số để thỏa điều kiện dãy số có thứ tự, thời gian này không nhỏ, và khi dãy số biến động cần phải tiến hành sắp xếp lại, tất cả các nhu cầu đó tạo ra khuyết điểm chính cho giải thuật tìm nhị phân. Khoa KỸ THUẬT_ Trường Cao đẳng Kinh tế - Kỹ thuật Hải Dương
Giáo trình Cấu trúc dữ liệu 38 3.2. Các thuật toán sắp xếp. Sắp xếp dãy số a1, , an là thực hiện việc bố trí lại vị trí các phần tử của một tập đối tượng nào đó sao cho hình thành được dãy mới ak1, ak2, akn có thứ tự (giả sử xét thứ tự tăng) trong đó a ki<=aki+1 Mà để quyết định những tình huống cần thay đổi vị trí các phần tử trong dãy, cần dựa vào kết quả của một loạt phép so sánh. Như vậy, 2 thao tác cơ bản của thuật toán sắp xếp là so sánh và đổi chổ, khi xây dựng một thuật toán sắp xếp cần chú ý tìm cách giảm thiểu những phép so sánh và đổi chỗ không cần thiết để tăng hiệu quả của thuật toán. Ðối với các dãy số được lưu trữ trong bộ nhớ chính, nhu cầu tiết kiệm bộ nhớ rất được chú ý, do vậy những thuật toán sắp xếp đòi hỏi cấp phát thêm vùng nhớ để lưu trữ dãy kết quả, ngoài vùng nhớ lưu trữ dãy số ban đầu, thường ít được quan tâm. Thay vào đó, các thuật toán sắp xếp trực tiếp trên dãy số ban đầu - gọi là các thuật toán sắp xếp tại chỗ (sắp xếp nội ) - lại được đầu tư phát triển. Phần này giới thiệu một số giải thuật sắp xếp từ đơn giản đến phức tạp có thể áp dụng thích hợp cho việc sắp xếp nội. 3.2.1. Chọn trực tiếp 3.2.1.1 Giải thuật Ý tưởng của thuật toán chọn trực tiếp mô phỏng một trong những cách sắp xếp tự nhiên nhất thực tế thường được sử dụng: Chọn phần tử nhỏ nhất trong N phần tử ban đầu, đưa phần tử này về vị trí đầu dãy hiện hành, sau đó không quan tâm đến nó nữa, xem dãy hiện hành chỉ còn N -1 phần tử của dãy ban đầu, bắt đầu từ vị trí thứ 2, lặp lại quá trình trên cho đến khi dãy hiện hành chỉ còn 1 phần tử. Dãy ban đầu có N phần tử, vậy tóm tắt ý tưởng thuật toán là thực hiện N -1 lượt việc đưa phần tử nhỏ nhất trong dãy hiện hành về vị trí đứng đầu dãy. Các bước tiến hành như sau : Bước 1: i :=1; Bước 2: Tìm phần tử a[min] nhỏ nhất trong dãy hiện hành từ a[i] đến a[N]. Bước 3: Đổi chỗ a[min]  a[i] Khoa KỸ THUẬT_ Trường Cao đẳng Kinh tế - Kỹ thuật Hải Dương
Giáo trình Cấu trúc dữ liệu 39 Bước 4: Nếu i < N -1 : i = i +1; lặp lại bước 2 Ngược lại : N -1 phần tử đã được đưa về đúng vị trí.Dừng. 3.2.1.2 Nhận xét và đánh giá giải thuật Đối với giải thuật chọn trực tiếp, có thể thấy rằng ở lượt thứ i, bao giờ cũng cần (n - i) lần so sánh để xác định phần tử nhỏ nhất hiện hành. Số lượng phép so sánh này không phụ thuộc vào tình trạng của dãy số ban đầu, do vậy trong mọi trường hợp có thể kết luận: Số lần so sánh = n(n-1)/2 Số lần hoán vị lại phụ thuộc vào tình trạng ban đầu của dãy số, ta chỉ có thể ước lượng trong từng trường hợp sau: Trường Hợp Số lần so sánh Số lần hoán vị Tốt nhất n(n-1)/2 0 Xấu nhất n(n-1)/2 n-1 Trung bình n(n-1)/2 (n-1)/2 3.2.1.3. Đoạn mã Thủ tục sắp xếp một mảng A có n phần tử Procedure Chon_truc_tiep( Var n:byte); Var i,j : Byte ; Begin For i := 1 to n - 1 do Khoa KỸ THUẬT_ Trường Cao đẳng Kinh tế - Kỹ thuật Hải Dương
Giáo trình Cấu trúc dữ liệu 40 For j := i to n do If a[j]<a[i] then Hoan_vi(a[i],a[j]); End; 3.2.2. Chèn trực tiếp ( InsertionSort ) 3.2.2.1 Giải thuật Giả sử có một dãy a 1, a2, , ai-1 đã được sắp xếp, ý tưởng chính của giải thuật sắp xếp bằng cách chèn thêm phần tử ai vào vị trí thích hợp của đoạn đã được sắp xếp để có dãy mới a1, a2, , an. Cho dãy ban đầu a1, a2, ,an, có thể xem như đã có đoạn gồm một phần tử a1 đã được sắp, sau đó thêm a2 vào đoạn a1 sẽ có đoạn a1, a2 đã được sắp; tiếp tục thêm a3 vào đoạn a1, a2 để có đoạn a1, a2, a3 được sắp; tiếp tục cho đến khi thêm xong an vào đoạn a 1, a2, , an-1 sẽ có dãy a 1, a2, , an được sắp. Các bước tiến hành như sau: Bước 1: giả sử có đoạn a[1] đã được sắp. i := 2; Bước 2: Tìm vị trí thích hợp trong đoạn a[1] đến a[i-1] để chèn a[i] vào. Bước 3: Dời chỗ các phần tử từ a[pos] đến a[i-1] sang phải một vị trí để dành chỗ cho a[i]. Bước 4: a[pos] = a[i]; kết quả có đoạn a[1] a[i] đã được sắp xếp Bước 5: i := i + 1; Nếu i < N : lặp lại bước 2. Ngược lại :Dừng. 3.2.2.2 Nhận xét và đánh giá giải thuật Khi tìm vị trí thích hợp để chèn a[i] vào đoạn a[1] đến a[i-1], do đoạn đã được sắp nên ta có thể sử dụng giải thuật tìm nhị phân để thực hiện việc tìm vị trí pos. Khi Khoa KỸ THUẬT_ Trường Cao đẳng Kinh tế - Kỹ thuật Hải Dương
Giáo trình Cấu trúc dữ liệu 41 đó, ta có thể cải thiện tốc độ của thuật toán nhờ vào tính hiệu quả của thuật toán tìm kiếm nhị phân. Ðối với giải thuật chèn trực tiếp, các phép so sánh xảy ra trong mỗi vòng lặp while để tìm vị trí thích hợp pos. Và mỗi lần xác định vị trí không thích hợp, sẽ dời chỗ phần tử a[pos] tương ứng. Thuật toán thực hiện tất cả N -1 vòng lặp while, do số lượng phép so sánh và dời chỗ này phụ thuộc vào tình trạng của dãy số ban đầu, nên chỉ có thể ước lược trong từng trường hợp như sau: Trường hợp Số lần so sánh Số lần hoán vị Tốt nhất n 1 n 1 1 n 1  2 2(n 1) i 1 i 1 Xấu nhất n 1 (n 2 n) n 1 (n 2 n 4) (i 1) 1 (i 1) 2 i 1 2 i 1 2 Trung bình (n 2 n 2) (n 2 9n 10) 4 4 3.2.2.3. Đoạn mã minh hoạ thủ tục sắp xếp kiểu chèn Procedure InsertionShort; Var i,j,tmp : Integer; Begin k[0]:= -32768;{giá trị đủ nhỏ hơn hoặc bằng các giá trị khác} { trong kiểu số nguyên Integer } for i:=2 to n do Khoa KỸ THUẬT_ Trường Cao đẳng Kinh tế - Kỹ thuật Hải Dương
Giáo trình Cấu trúc dữ liệu 42 Begin Tmp := k[i]; j := j - 1; While tmp < k[j] do Begin k[j+1] := k[j] ; j := j - 1; End; k[j+1] := tmp; End; End; 3.2.3. Phương pháp nổi bọt (Bubble Short ) 3.2.3.1. Giải thuật Ý tưởng của giải thuật là xuất phát từ cuối hoặc đầu dãy và tiến hành đổi chỗ các cặp phần tử kế cận để đưa phần tử nhỏ hoặc lớn hơn về vị trí cao nhất hoặc thấp nhất trong dãy hiện hành. Sau khi đã được chuyển về đúng vị trí thì các phần tử trên sẽ không cần xét đến ở bước tiếp theo. Lặp lại công việc trên cho đến khi không còn phần tử nào để xét. Khoa KỸ THUẬT_ Trường Cao đẳng Kinh tế - Kỹ thuật Hải Dương
Giáo trình Cấu trúc dữ liệu 43 3.2.3.2. Đoạn mã mô phỏng chương trình: Procedure Noibot( Var n:byte); Var i,j : Integer ; Begin For j := n downto 2 do For i := 1 to j - 1 do If a[i + 1] < a[i] then Hoan_vi(a[i+1],a[i]); End; 3.2.3.3. Đánh giá giải thuật Đối với giải thuật này, số lượng các phép so sánh xảy ra không phụ thuộc tình trạng của dãy số ban đầu, nhưng số lượng phép hoán vị thực hiện lại tùy thuộc vào kết quả so sánh. Có thể ước lượng trong từng trường hợp như sau: Trường hợp Số lần so sánh Số lần hoán vị Tốt nhất n 1 n n 1 0  n i 1 i 1 2 Xấu nhất n n 1 n 1 n n 1  n i 1 2 i 1 2 Khi sắp xếp bằng phương pháp nổi bọt thì các phần tử nhỏ được đưa về vị trí đúng rất nhanh, trong khi các phần tử lớn lại được đưa về vị trí đúng rất chậm. Khoa KỸ THUẬT_ Trường Cao đẳng Kinh tế - Kỹ thuật Hải Dương
Giáo trình Cấu trúc dữ liệu 44 3.2.4 Sắp xếp với độ dài bước giảm dần ( sắp xếp nhanh )– ShellSort 3.2.4.1. Giải thuật Giải thuật ShellSort dựa trên ý tưởng sắp xếp các phần tử theo phương pháp chèn nhưng với độ dài bước giảm dần. Ý tưởng của phương pháp sắp xếp là phân chia dãy ban đầu thành những dãy con các phần tử ở cách nhau h vị trí: Dãy ban đầu : a1 a2 an được xem như sự xen kẽ các dãy con sau : Dãy con thứ nhất : a1 ah+1 a2h+1 Dãy con thứ hai : a2 ah+2 a2h+2 . Dãy con thứ h : ah a2h a3h Tiến hành sắp xếp các phần tử trong cùng dãy con sẽ làm cho các phần tử được đưa về vị trí đúng tương đối ( chỉ đúng trong dãy con, so với toàn bộ các phần tử trong dãy ban đầu co thể chưa đúng ) một cách nhanh chóng, sau đó giảm khoảng cách h để tạo thành các dãy con mới ( tạo điều kiện để so sánh một phần tử với nhiều phần tử khác trước đó không ở cùng dãy con với nó ) và lại tiếp tục sắp xếp Thuật toán dừng khi h=1, lúc này bảo đảm tất cả các phần tử trong dãy ban đầu sẽ được so sánh với nhau để xác định trật tự đúng cuối cùng. Yếu tố quyết định tính hiệu quả của một thuật toán là cách chọn khoảng cách h trong từng bước sắp xếp. Giả sử quyết định sắp xếp k bước, các khoảng cách chọn phải thoả điều kiện: hi > hi+1 và hk = 1 Tuy nhiên đến nay vẫn chưa có tiêu chuẩn rõ ràng trong việc lựa chọn dãy giá trị khoảng cách tốt nhất, một số dãy được Knuth đề nghị : hi = ( hi-1 –1)/3 và hk =1, k= log3n-1 hay Khoa KỸ THUẬT_ Trường Cao đẳng Kinh tế - Kỹ thuật Hải Dương
Giáo trình Cấu trúc dữ liệu 45 hi = ( hi-1 –1)/2 và hk =1, k= log2-1 Các bước tiến hành như sau : Bước 1 : Chọn k khoảng cách h[1], h[2], ,h[k] và i=1. Bước 2 : Phân chia dãy ban đầu thành các dãy con cách nhau h[i] khoảng cách. Sắp xếp từng dãy con bằng phương pháp chèn trực tiếp. Bước 3 : i:=i+1; Nếu i>k : dừng; Nếu i<=k : lặp lại bước 2. 3.2.4.2. Nhận xét và đánh giá giải thuật Hiện nay, việc đánh giá giả thuật ShellSort dẫn đến những vấn đề toán học rất phức tạp, thậm chí một số chưa được chứng minh. Tuy nhiên hiệu quả của thuật toán con phụ thuộc vào dãy các độ dài được chọn. Trong trường hợp chọn dãy độ dài theo 1,2 2 công thức hi = ( hi-1 -1)/2 và hk =1, k= log2-1 thì giải thuật có độ phức tạp n << n . 3.2.5. Sắp xếp dựa trên phân hoạch – Quick Sort 3.2.5.1. Giải thuật Để sắp xếp dãy a1, a2 an giải thuật Quick Sort dựa trên việc phân hoạch dãy ban đầu thành 2 dãy con khác nhau : - Dãy con 1 : Gồm các phần tử a1 ai có giá trị không lớn hơn x. - Dãy con 2 : Gồm các phần tử ai an có giá trị không nhỏ hơn x. Với x là giá trị của một phần tử tuỳ ý trong dãy ban đầu. Sau khi thực hiện phân hoạch, dãy ban đầu được chia làm 3 phần : 1. ak < x, với k=1 i 2. ak = x, với k=i j Khoa KỸ THUẬT_ Trường Cao đẳng Kinh tế - Kỹ thuật Hải Dương
Giáo trình Cấu trúc dữ liệu 46 3. ak > x, với k=j N Trong đó dãy con thứ hai đã có thứ tự, nếu các dãy con 1 và 3 chỉ có 1 phần tử thì chúng cũng đã có thứ tự, khi đó dãy ban đầu đã được sắp. Ngược lại, nếu các dãy con 1 và 3 có nhiều hơn 1 phần tử thì dãy ban đầu chỉ được sắp khi các dãy con 1, 3 có thứ tự. Để sắp xếp dãy con 1 và 3, lần lượt tiến hành phân hoạch từng dãy con theo cùng phương pháp phân hoạch dãy ban đầu vừa trình bày Vấn đề còn lại bây giờ là xây dựng một thủ tục phân hoạch cho dãy ban đầu, điều này phụ thuộc nhiều vào việc xác định phần tử làm mốc ban đầu, mốc được chọn làm sao để tạo ra hai dãy con cân bằng nhau, điều này rất mất thời gian. Vì vậy người ta thường chọn phần tử đầu tiên của mảng làm mốc, giả sử dãy ban đầu là mảng gồm có các phần tử a[i] a[j], tức là lấy p= a[i] làm mốc. Sau đó sử dụng các biến L chạy từ trái sang phải bắt đầu từ vị trí thứ i, biến k chạy từ phải sang trái bắt đầu từ j +1. Biến L được tăng cho tới khi a[L] >p, còn biến k được giảm cho tới khi a[k] k. Cuối cùng ta trao đổi vị trí a[i] và a[k] để đặt mốc vào đúng vị trí của nó. 3.2.5.2. Đoạn mã thủ tục phân hoạch: Procedure Phan_hoach(i,h:integer; var x:integer); Var L:integer; P:object; Begin P := a[i]; L := i; x := j +1; Repeat L := L + 1; Khoa KỸ THUẬT_ Trường Cao đẳng Kinh tế - Kỹ thuật Hải Dương
Giáo trình Cấu trúc dữ liệu 47 Until (a[L].key > p.key) or (L>j); Repeat x := x - 1; Until (a[x].key p.key; Repeat x := x - 1; Until a[x].key <= p.key; End; Doicho(a[i],a[x]); End; Nhận xét . Về nguyên tắc, có thể chọn giá trị mốc p là một phần tử tuỳ ý trong dãy, nhưng để đơn giản, dễ diễn đạt giải thuật, phần tử có vị trí giữa thường được chọn, khi đó p :=int((i+j)/2). . Giá trị mốc p được chọn sẽ tác động đến hiệu quả thực hiện thuật toán vì nó quyết định số lần phân hoạch. Số lần phân hoạch sẽ ít nhất nếu ta chọn Khoa KỸ THUẬT_ Trường Cao đẳng Kinh tế - Kỹ thuật Hải Dương
Giáo trình Cấu trúc dữ liệu 48 được p là phần tử trung bình (median) của dãy. Tuy nhiên, trên thực tế ta khó chọn được phần tử này nên thường chọn phần tử bất kỳ hoặc phần tử nằm chính giữa dãy làm mốc với hy vọng nó có thể gần với giá trị median ( HS viết thủ tục với p nằm giữa dãy ). Giải thuật để sắp xếp một dãy al ar Có thể phát biểu giải thuật sắp xếp QuickSort một cách đệ qui như sau Bước 1 : Phân hoạch dẫy ai aj thành các dãy con : Dãy con 1 : a[i] a[L] = x Bước 2 : Nếu (i< L) Phân hoạch dãy a[i] a[L] Nếu (L<j) Phân hoạch dãy a[L] a[j] 3.2.5.2. Đoạn chương trình minh hoạ thủ tục QuickShort Procedure sap_xep_nhanh(i,j:integer); Var K;integer ; Begin If i < j then Begin Phan_hoach(i,j,k); Sap_xep_nhanh(i,k-1); Sap_xep_nhanh(k+1,j); End; Khoa KỸ THUẬT_ Trường Cao đẳng Kinh tế - Kỹ thuật Hải Dương
Giáo trình Cấu trúc dữ liệu 49 End; 3.2.5.3. Nhận xét và đánh giá giải thuật Hiệu quả của giải thuật QuickSort phụ thuộc vào việc chọn giá trị mốc. Trường hợp tốt nhất xảy ra nếu mỗi lần phân hoạch đều chọn được phần tử median làm mốc, khi đó dãy được phân chia thành 2 phần bằng nhau và chỉ cần log(n) lần phân hoạch thì sắp xếp xong. Nhưng nếu mỗi lần phân hoạch lại chọn phải phần tử có giá trị cực đại hay cực tiểu làm mốc, dãy sẽ bị phân thành 2 phần không đều: một phần chỉ có 1 phần tử, phần còn lại có (n-1) phần tử, do vậy cần phân hoạch n lần mới sắp xếp xong. Ta có bảng tổng kết : Trường hợp Độ phức tạp Trung bình n*log(n) Xấu nhất n2 3.2.5.4.Ví dụ minh họa Cho dãy số a: 4 9 3 7 5 3 8 Công việc sắp xếp dãy trên bằng thuật toán QuickSort được tiến hành như sau: Phân hoạch đoạn l = 0, r = 6, x = a[3] = 7 4 9 3 7 5 3 8 Phân hoạch đoạn l = 0, r = 2, x = a[1] = 3 Khoa KỸ THUẬT_ Trường Cao đẳng Kinh tế - Kỹ thuật Hải Dương
Giáo trình Cấu trúc dữ liệu 50 4 3 3 5 7 9 8 Phân hoạch đoạn l = 4, r = 6, x = a[5] = 9 3 3 4 5 7 9 8 Dừng 3 3 4 5 7 8 9 TÓM TẮT: Trong chương này, chúng ta đã xem xét các thuật toán tìm kiếm và sắp xếp thông dụng. Cấu trúc dữ liệu chính để minh hoạ các thao tác này chủ yếu là mảng một chiều. Đây cũng là một trong những cấu trúc dữ liệu thông dụng nhất. Khi khảo sát các thuật toán tìm kiếm, chúng ta đã làm quen với hai thuật toán. Thuật toán thứ nhất là thuật toán tìm kiếm tuần tự. Thuật toán này có độ phức tạp tuyến tính (O(n)). Ưu điểm của nó là tổng quát và có thể mở rộng để thực hiện các bài toán tìm kiếm đa dạng. Tuy nhiên, chi phí thuật toán khá cao nên ít khi được sử dụng. Thuật toán thứ hai là thuật toán nhị phân tìm kiếm. Thuật toán này có ưu điểm là tìm kiếm rất nhanh (độ phức tạp là log2N). Nhưng chỉ có thể áp dụng đối với dữ liệu đã có thứ tự theo khoá tìm kiếm. Do đòi hỏi của thực tế, thao tác tìm kiếm phải nhanh vì đây là thao tác có tần suất sử dụng rất cao nên thuật toán nhị phân tìm kiếm thường được dùng hơn thuật toán tìm tuần tự. Chính vì vậy xuất hiện nhu cầu phát triển các thuật toán sắp xếp hiệu quả. Khoa KỸ THUẬT_ Trường Cao đẳng Kinh tế - Kỹ thuật Hải Dương
Giáo trình Cấu trúc dữ liệu 51 Phần tiếp theo của chương này trình bày các thuật toán sắp xếp thông dụng theo thứ tự từ đơn giản đến phức tạp (từ chi phí cao đến chi phí thấp). Phần lớn các thuật toán sắp xếp cơ bản dựa trên sự so sánh giá trị giữa các phần tử. Bắt đầu từ nhóm các thuật toán cơ bản, đơn giản nhất. Đó là các thuật toán chọn trực tiếp, chèn trực tiếp, nổi bọt, đổi chỗ trực tiếp. Các thuật toán này đều có một điểm chung là chi phí thực hiện tỷ lệ với n2. Tiếp theo, chúng ta khảo sát một số cải tiến của các thuật toán trên. Nếu như các thuật toán chèn nhị phân (cải tiến của chèn trực tiếp), shaker sort (cải tiến của nổi bọt) ; tuy chi phí có ít hơn các thuật toán gốc nhưng chúng vẫn chỉ là các thuật toán thuộc nhóm có độ phức tạp O(n2), thì thuật toán Shellsort (cải tiến của chèn trực tiếp), lại có độ phức tạp nhỏ hơn hẳn thuật toán gốc. Thuật toán shell sort có độ phức tạp O(nx) với 1<x<2. Thuật toán Quick sort, như tên gọi của mình được đánh giá là thuật toán sắp xếp nhanh nhất trong số các thuật toán sắp xếp dựa trên nền tảng so sánh giá trị của các phần tử. Từ thuật toán quick sort, ta cũng có thể xây dựng được một thuật toán hiệu quả tìm phần tử trung vị (median) của một dãy số. Người ta cũng chứng minh được rằng O(nlog2n) là ngưỡng chặn dưới của các thuật toán sắp xếp dựa trên nền tảng so sánh giá trị của các phần tử. Để vượt qua ngưỡng này, ta cần phát triển thuật toán mới theo hướng khác các thuật toán trên. Radix sort là một thuật toán như vậy. Nó được phát triển dựa trên sự mô phỏng qui trình phân phối thư của những người đưa thư. Thuật toán này đại diện cho nhóm các thuật toán sắp xếp có độ phức tạp tuyến tính. Tuy nhiên, thường thì các thuật toán này không thích hợp cho việc cài đặt trên cấu trúc dữ liệu mảng một chiều. Trên thực tế dữ liệu cần thao tác có thể rất lớn do vậy không thông thường thì các dữ liệu được lưu trên bộ nhớ thứ cấp, tức trên các đĩa từ. Việc thực hiện các thao tác sắp xếp trên các dữ liệu này đòi hỏi phải có các phương pháp khác thích hợp. Tuy nhiên trong khuôn khổ giáo trình này, các thuật toán trên là tương đối khó. Do vậy, chúng tôi chỉ giới thiệu qua các phương pháp sắp xếp ngoài như là bài đọc thêm trong phần phụ lục ở cuối sách. Khoa KỸ THUẬT_ Trường Cao đẳng Kinh tế - Kỹ thuật Hải Dương
Giáo trình Cấu trúc dữ liệu 52 BÀI TẬP CHƯƠNG 3 Bài tập lý thuyết 1- Xét mảng các số nguyên có nội dung như sau: -9 -9 -5 -2 0 3 7 7 10 15 a- Tính số lần so sánh để tìm ra phần tử X = -9 bằng phương pháp: Tìm tuyến tính Tìm nhị phân Nhận xét và so sánh 2 phương pháp tìm nêu trên trong trường hợp này và trong trường hợp tồng quát. b- Trong trường hợp tìm nhị phân, phần tử nào sẽ được tìm thấy (thứ 1 hay 2) 2- Xây dựng thuật toán tìm phần tử nhỏ nhất (lớn nhất) trong một mảng các số nguyên. 3- Trong 3 phương pháp sắp xếp cơ bản (chọn trực tiếp, chèn trực tiếp, nổi bọt) phương pháp nào thực hiện sắp xếp nhanh nhất với một dãy đã có thứ tự? Giải thích. 4- Hãy xây dựng thuật toán tìm phần tử trung vị (median) của một dãy số a 1, a2, , an dựa trên thuật toán QuickSort. Cho biết độ phức tạp của thuật toán này. Bài tập thực hành 5- Cài đặt các thuật toán tìm kiếm và sắp xếp đã trình bày. Thể hiện trực quan các thao tác của thuật toán. Tính thời gian thực hiện của mỗi thuật toán. 6- Hãy viết hàm tìm tất cả các số nguyên tố nằm trong mảng một chiều a có n phần tử. Khoa KỸ THUẬT_ Trường Cao đẳng Kinh tế - Kỹ thuật Hải Dương
Giáo trình Cấu trúc dữ liệu 53 7- Hãy viết hàm tìm dãy con tăng dài nhất của mảng một chiều a có n phần tử (dãy con là một dãy liên tiếp các phần tử của a). 8- Hãy viết hàm trộn hai mảng một chiều có thứ tự tăng A và B có m và n phần tử thành mảng một chiều C cũng có thứ tự tăng. 9- Cho một danh sách thí sinh gồm n người, Mỗi người cho biết tên và điểm thi hãy chọn ra m người có điểm cao nhất. Khoa KỸ THUẬT_ Trường Cao đẳng Kinh tế - Kỹ thuật Hải Dương
Giáo trình Cấu trúc dữ liệu 54 Chương 4: DANH SÁCH LIÊN KẾT 4.1. Giới thiệu Với các cấu trúc dữ liệu được xây dựng từ các kiểu cơ sở như: kiểu thực, kiểu kí tự, hoặc từ các cấu trúc đơn giản khác như tệp tin, tập hợp, mảng là các kiểu dữ liệu đã được xác định trước một cách rõ ràng lúc mô tả kiểu và khai báo biến, các đối tượng dữ liệu được xác định thuộc những kiểu dữ liệu này có đặc điểm chung là không thay đổi được kích thước, thời gian tồn tại của chúng cũng là thời gian tồn tại của khối chương trình có chứa khai báo này, do đó thường cứng ngắt, gò bó, tốn nhiều tài nguyên hệ thống khiến đôi khi khó diễn tả được thực tế vốn sinh động, phong phú. Các kiểu dữ liệu kể trên được gọi là các kiểu dữ liệu tĩnh. Nhằm đáp ứng nhu cầu thể hiện sát thực tế, bản chất của dữ liệu cũng như xây dựng các thao tác hiệu quả trên dữ liệu, cần phải tìm cách tổ chức kết hợp dữ liệu với những kích thước linh động hơn, có thể thay đổi kích thước, cấu trúc trong suốt thời gian sử dụng. Các hình thức tổ chức dữ liệu như vậy được gọi là cấu trúc dữ liệu động. 4.2- Kiểu con trỏ 4.2.1- Biến không động (biến tĩnh) Khi xây dựng chương trình, lập trình viên có thể xác định được ngay những đối tượng dữ liệu cần sử dụng, thông qua nhu cầu thay đổi về số lượng, kích thước. Do đó có thể xác định cách thức lưu trữ chúng ngay từ đầu. Các đối tượng dữ liệu này sẽ được khai báo như các biến không động. Biến không động là những biến có một số tính chất sau : . Ðược khai báo tường minh (được xác định rõ ràng lúc mô tả kiểu hay khai báo biến ). Khoa KỸ THUẬT_ Trường Cao đẳng Kinh tế - Kỹ thuật Hải Dương
Giáo trình Cấu trúc dữ liệu 55 . Tồn tại khi vào phạm vi khai báo và chỉ mất khi ra khỏi phạm vi này. Thường là tồn tại trong suốt quá trình chương trình đó hoạt động. . Ðược cấp phát vùng nhớ trong vùng dữ liệu (Data segment) hoặc Stack (đối với biến cục bộ). . Kích thước không thay đổi trong suốt chu trình sống. Do được khai báo tường minh, các biến không động có một định danh đã được kết nối với địa chỉ vùng nhớ lưu trữ biến và được truy xuất trực tiếp thông qua định danh đó. Ví dụ: Var so_nguyen : Integer ; Ky_tu : Char; K_tra : Boolean; 4.2.2. Biến động Là những biến được tạo ra một cách linh hoạt trong chương trình, theo mục đích nhu cầu của người lập trình. Các biến động không được gán tên ( vì việc đặt tên thực chất là gán cho nó một địa chỉ xác định trong vùng nhớ), việc truy xuất đến biến động không thông qua tên mà thông qua các biến con trỏ. Các biến con trỏ được định nghĩa như một biến tĩnh ngay từ đầu chương trình và được dùng để chứa địa chỉ các biến động. Việc tạo ra một biến động hay xóa bỏ biến đó ( cấp phát hay thu hồi lại vùng nhớ đối với biến động đó ) được thực hiện nhờ các thủ tục có sẵn là NEW ( cấp phát mới ) và DISPOSE ( thu hồi ). 4.2.3. Kiểu con trỏ Cho trước kiểu T= . Kiểu con trỏ, ký hiệu "T P", chỉ đến các phần tử có kiểu "T" được định nghĩa : Khoa KỸ THUẬT_ Trường Cao đẳng Kinh tế - Kỹ thuật Hải Dương
Giáo trình Cấu trúc dữ liệu 56 TP = Trong đó : .V P = {các địa chỉ lưu trữ những đối tượng có kiểu T, NIL} (với NIL là một giá trị đặc biệt tượng trưng cho một giá trị không biết hoặc không quan tâm ở đây ta gọi là giá trị vô cùng). .O P = { tập các thao tác xác định địa chỉ của một đối tượng thuộc kiểu T khi biết con trỏ chỉ đến đối tượng đó} (Thường gồm các thao tác tạo một con trỏ chỉ đến một đối tượng thuộc kiểu T; huỷ một đối tượng dữ liệu thuộc kiểu T khi biết con trỏ chỉ đến đối tượng đó). Nói một cách dễ hiểu, kiểu con trỏ là kiểu cơ sở dùng lưu địa chỉ của một đối tượng khác.Biến thuộc kiểu con trỏ T P 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ị NIL. Lưu ý : Kích thước của biến con trỏ tuỳ thuộc vào quy ước số byte địa chỉ trong từng mô hình bộ nhớ của từng ngôn ngữ lập trình cụ thể. 4.3. Danh sách Danh sách là một dãy hữu hạn các phần tử thuộc cùng một lớp các đối tượng, ví dụ như danh sách lớp, danh sách Nhân viên, bảng lương Giả sử L là một danh sách có n phần tử ( n >=0 ) L = (a1, a2, , an ) Ta gọi n là độ dài của danh sách, nếu n >=1 thì a1 được coi là phần tử đầu danh sách, còn an coi là phần tử cuối danh sách. Nếu n = 0 nghĩa là danh sách không có phần tử nào (danh sách rỗng). Khoa KỸ THUẬT_ Trường Cao đẳng Kinh tế - Kỹ thuật Hải Dương
Giáo trình Cấu trúc dữ liệu 57 Các phần tử của danh sách được sắp tuyến tính, nếu danh sách có n (n>1) phần tử thì phần tử a1 đứng trước phần tử a2 phần tử a2 đứng trước phần tử a3 khi đó ta coi phần tử ai là phần tử đứng vị trí thứ i của danh sách. 4.3.1. Các phép toán trên danh sách Ðể thiết lập kiểu dữ liệu trừu tượng danh sách (hay ngắn gọn là danh sách) ta phải định nghĩa các phép toán trên danh sách. Và như chúng ta sẽ thấy trong toàn bộ giáo trình, không có một tập hợp các phép toán nào thích hợp cho mọi ứng dụng (application). Vì vậy ở đây ta sẽ định nghĩa một số phép toán cơ bản nhất trên danh sách. Ðể thuận tiện cho việc định nghĩa ta giả sử rằng danh sách gồm các phần tử có kiểu là kiểu phần tử, vị trí của các phần tử trong danh sách có kiểu là kiểu vị trí và vị trí sau phần tử cuối cùng trong danh sách L là ENDLIST(L). Cần nhấn mạnh rằng khái niệm vị trí là do ta định nghĩa, nó không phải là giá trị của các phần tử trong danh sách. Vị trí có thể là đồng nhất với vị trí lưu trữ phần tử hoặc không. Các phép toán được định nghĩa trên danh sách là: INSERT_LIST(p,x,L) xen phần tử x ( kiểu ElementType ) vào danh sách L tại vị trí p. Tức là nếu danh sách là a1, , ap-1, ap, ap+1, , an thì sau khi xen ta có kết quả a1, , ap-1, x, ap, ap+1 , , an. Nếu vị trí p không tồn tại trong danh sách thì phép toán không được định nghĩa. LOCATE(x,L) thực hiện việc định vị phần tử x trong danh sách L. Locate trả kết quả là vị trí của phần tử x trong danh sách. Nếu x không có trong danh sách thì vị trí sau phần tử cuối cùng của danh sách được trả về, tức là ENDLIST(L). RETRIEVE(p,L) lấy giá trị của phần tử thứ p của danh sách L; nếu vị trí p không có trong danh sách thì kết quả không xác định. DELETE_LIST(p,L) thủ tục thực hiện việc xoá phần tử thứ p của danh sách. Nếu vị trí p không có trong danh sách thì phép toán không được định nghĩa và danh sách L sẽ không thay đổi Khoa KỸ THUẬT_ Trường Cao đẳng Kinh tế - Kỹ thuật Hải Dương
Giáo trình Cấu trúc dữ liệu 58 NEXT(p,L) cho kết quả là vị trí của phần tử đi sau phần tử thứ p; nếu p là phần tử cuối cùng trong danh sách L thì NEXT(p,L) cho kết quả là ENDLIST(L). Next không xác định nếu p không phải là vị trí của một phần tử trong danh sách. PREVIOUS(p,L) cho kết quả là vị trí của phần tử đứng trước phần tử p trong danh sách. Nếu p là phần tử đầu tiên trong danh sách thì Previous(p,L) không xác định. Previous cũng không xác định trong trường hợp p không phải là vị trí của phần tử nào trong danh sách. FIRST(L) cho kết quả là vị trí của phần tử đầu tiên trong danh sách. Nếu danh sách rỗng thì ENDLIST(L) được trả về. PRINT_LIST(L) liệt kê các phần tử của L theo thứ tự xuất hiện của chúng trong danh sách. EMPTY_LIST(L) cho kết quả TRUE nếu danh sách có rỗng, ngược lại nó cho giá trị FALSE. MAKENULL_LIST(L) khởi tạo một danh sách L rỗng. LENGTH(L) Xác định độ dài của danh sách. EMPTY(L) Kiểm tra xem danh sách có rỗng hay không. FULL(L) Kiểm tra danh sách có đầy hay không SEARCH(x,L) Tìm xem trong danh sách có chứa phần tử x hay không Khoa KỸ THUẬT_ Trường Cao đẳng Kinh tế - Kỹ thuật Hải Dương
Giáo trình Cấu trúc dữ liệu 59 4.4. Danh sách liên kết Danh sách được định nghĩa là một tập hợp hữu hạn các phần tử có cùng một lớp đối tượng, các phần tử này có một mối quan hệ với nhau, tùy vào đặc điểm của mối quan hệ ta có hai loại danh sách: Danh sách đơn và danh sách kép. 4.4.1. Danh sách đơn 4.4.1.1 Tổ chức danh sách đơn Danh sách nối đơn gồm các phần tử nối với nhau theo một chiều, mỗi phần tử của danh sách đơn là một cấu trúc bao gồm hai thành phần chính: - Thành phần Info: lưu trữ các thông tin về bản thân phần tử (giá trị). - Thành phần Next: lưu trữ địa chỉ của phần tử kế tiếp trong danh sách ( còn gọi là thành phần liên kết ), hoặc lưu trữ giá trị NIL nếu là phần tử cuối danh sách. Nếu biết được địa chỉ của phần tử đầu tiên trong danh sách đơn thì có thể dựa vào thông tin Next của nó để truy xuất đến phần tử thứ hai của dãy, và lại dựa vào thông tin Next của phần tử thứ hai để truy xuất phần tử thứ ba. Nghĩa là để quản lý một danh sách đơn chỉ cần biết địa chỉ phần tử đầu tiên. Thường một con trỏ Head sẽ được dùng để lưu trữ địa chỉ phần tử đầu danh sách, nên ta gọi Head là đầu dãy. Position Head Khoa KỸ THUẬT_ Trường Cao đẳng Kinh tế - Kỹ thuật Hải Dương
Giáo trình Cấu trúc dữ liệu 60 4.4.1.2. Các thao tác cơ bản trên danh sách đơn Các khai báo cần thiết là CONST maxlength= ;{số nguyên thích hợp chỉ độ dài của danh sách} TYPE elementType = ; {kiểu của phần tử trong danh sách}; position=integer; {kiểu vị trí cuả các phần tử} list= record {mảng chứa các phần tử của danh sách} elements: array[1 maxlength] of elementtype; last:integer; { giữ độ dài danh sách } END; * Khởi tạo danh sách rỗng Danh sách rỗng có độ dài bằng 0. Theo cài đặt ở trên, biến Last chỉ vị trí của phần tử cuối cùng trong danh sách và đó cũng độ dài hiện tại của danh sách, vì vậy để khởi tạo danh sách rỗng ta chỉ việc gán Last := 0. Procedure MAKENULL_LIST(var L:LIST); Khoa KỸ THUẬT_ Trường Cao đẳng Kinh tế - Kỹ thuật Hải Dương
Giáo trình Cấu trúc dữ liệu 61 begin L.last:=0; end; * Kiểm tra danh sách rỗng Danh sách rỗng nếu độ dài của danh sách bằng 0. Function empty_LIST(L:list):boolean; Begin empty_list:=(L.last=0); End; * Chèn một phần tử vào danh sách ( danh sách cài đặt bằng mảng ) Khi chèn thêm một phần tử vào danh sách sẽ có 3 trường hợp sảy ra: phần tử được chèn nằm ở đầu danh sách, phần tử được chèn vào cuối danh sách và được chèn vào vị trí bất kỳ của danh sách. Ta có hình vẽ minh hoạ cho hai trường hợp đầu như sau ( Sinh viên tự xây dựng chương trình con thực hiện 2 thủ tục này): phần tử được chèn vào đầu danh sách Trường hợp chèn phần tử x vào vị trí p bất kỳ của danhLast sách ta có mấy khả năng sau:  Mảng đầy: mọi phần tử của mảng đều chứa phần tử của danh sách, tức là phần tửphần cuối cùngtử được của danhchèn sáchvào nằmcuối ởdanh vị trí sách cuối cùng trong mảng. Nói cách khác, Khoa KỸ THUẬT_ Trường Cao đẳng Kinh tế - Kỹ thuật Hải Dương
Giáo trình Cấu trúc dữ liệu 62 độ dài của danh sách bằng độ dài tối đa của mảng, ta không còn chỗ cho phần tử mới, vì vậy việc xen là không thể thực hiện được, thủ tục gặp lỗi.  Ngược lại ta tiếp tục xét, nếu p không hợp lệ (p > last +1 hoặc p =maxlength then writeln('Loi: danh sach day') else if (p>L.last+1) or (p<1) then writeln('Loi: vi tri khong hop le') else Begin Khoa KỸ THUẬT_ Trường Cao đẳng Kinh tế - Kỹ thuật Hải Dương
Giáo trình Cấu trúc dữ liệu 63 {doi cac phan tu tu vi tri p den cuoi danh sach xuong 1 vi tri} for q:=l.last downto p do L.element[q+1]:=L.element[q]; {do dai danh sach tang len 1} L.last:=L.last+1;{dat x vao vi tri p} L.element[p]:=x; End; End; * Xoá một phần tử của danh sách Xoá một phần tử của danh sách ta làm công việc ngược lại với xen nghĩa là phải dời các phần tử từ vị trí p+1 đến cuối danh sách lên một vị trí và độ dài danh sách giảm đi 1 phần tử. Nếu p không phải là một vị trí hợp lệ thì thủ tục bị lỗi. p Procedure delete_list(p:position;var L:list); Var q:position; Begin Khoa KỸ THUẬT_ Trường Cao đẳng Kinh tế - Kỹ thuật Hải Dương
Giáo trình Cấu trúc dữ liệu 64 if (p>L.last) or (p<1) then writeln('Loi: vi tri cua phan tu xoa khong hop le') else Begin {doi cac phan tu tu vi tri p+1 den cuoi danh sach len 1 vi tri } for q:=p+1 to L.last do L.element[q-1]:=L.element[q]; L.last:=L.last-1; End; End; * Ðịnh vị một phần tử trong danh sách Ðể định vị một phần tử x trong danh sách, ta tiến hành duyệt tìm từ đầu danh sách. Nếu tìm thấy x thì vị trí của phần tử tìm thấy được trả vê, nếu không tìm thấy thì hàm trả về vị trí sau vị trí của phần tử cuối cùng trong danh sách, tức là Last+1 được trả về (chú ý ENDLIST(L)= L.last+1). Trong trường hợp có nhiều phần tử cùng giá trị x trong danh sách thì vị trí của phần tử được tìm thấy đầu tiên được trả về. Function locate(x:elementtype; L:list):position; Var p:position; Khoa KỸ THUẬT_ Trường Cao đẳng Kinh tế - Kỹ thuật Hải Dương
Giáo trình Cấu trúc dữ liệu 65 Begin p:=1; while (p x) do p:=p+1; locate:=p; End; Các phép toán khác cũng dễ dàng cài đặt nên xem như bài tập dành cho bạn đọc. 4.4.2 Danh sách liên kết vòng Danh sách liên kết vòng tròn ( gọi tắt là danh sách liên kết vòng ) là một danh sách đơn có con trỏ của phần tử cuối cùng của danh sách không trỏ vào NIL mà trỏ vào thành phần đầu tiên của danh sách tạo thành một vòng tròn. Đặc điểm của Danh sách liên kết vòng là các thành phần của danh sách đều bình đẳng, mỗi thành phần đều có thành phần đứng sau và thành phần đứng trước. Nếu xuất phát từ một thành phần bất kỳ thuộc danh sách đều có thể truy xuất đến một thành phần bất kỳ khác trong danh sách hay nói cách khác là từ một thành phần bất kỳ ta có thể duyệt toàn bộ danh sách. Các phép toán trên một danh sách liên kết vòng cũng tương tự như trên danh sách liên kết đơn, chỉ khác một điều là trong phép toán chèn thêm phần tử, xoá một phần tử ta không phải xử lý trường hợp phần tử đó là ở các vị trí đầu hoặc cuối danh sách. Khoa KỸ THUẬT_ Trường Cao đẳng Kinh tế - Kỹ thuật Hải Dương
Giáo trình Cấu trúc dữ liệu 66 4.4.3 Danh sách liên kết kép Danh sách liên kết kép là một danh sách mà mỗi phần tử trong danh sách có thể kết nối với 1 phần tử đứng trước và 1 phần tử đứng sau nó. Khác với danh sách liên kết đơn và danh sách liên kết vòng là khi duyệt các thành phần của danh sách chỉ theo một chiều nhất định, danh sách liên kết kép có thể duyệt theo hai chiều. Điều này được thông qua hai con trỏ: Prev trỏ tới phần tử đứng trước, Next trỏ tới phần tử đứng sau. Các phép toán trên danh sách liên kết kép được thực hiện dễ dàng và linh hoạt hơn, việc duyệt được danh sách theo hai chiều làm giảm thời gian để duyệt danh sách, việc tìm kiếm, thêm, bớt cũng dễ hơn. Ví dụ các thao tác trên danh sách liên kết đơn đều cần phải biết phần tử đứng trước trong khi đó ta có thể dễ dàng thao tác trên danh sách liên kết kép. Minh hoạ thêm một phần tử vào danh sách kép Minh hoạ bớt một phần tử từ danh sách kép Khoa KỸ THUẬT_ Trường Cao đẳng Kinh tế - Kỹ thuật Hải Dương
Giáo trình Cấu trúc dữ liệu 67 Phần xây dựng các thủ tục thực hiện các phép toán trên danh sách liên kết vòng và danh sách liên kết kép sẽ là bài tập dành cho Sinh viên. 4.4.4 Danh sách có nhiều mối liên kết Danh sách có nhiều mối liên kết là danh sách mà mỗi phần tử có nhiều khoá và chúng được liên kết với nhau theo từng loại khoá. Danh sách có nhiều mối liên kết thường được sử dụng trong các ứng dụng quản lý một cơ sở dữ liệu lớn với nhu cầu tìm kiếm dữ liệu theo từng khoá khác nhau. Ðể quản lý danh mục điện thoại thuận tiện cho việc in danh mục theo những trình tự khác nhau: tên khách hàng tăng dần, số điện thoại tăng dần, thời gian lắp đặt giảm dần. Ta có thể tổ chức dữ liệu theo dạng sau : một danh sách với 3 mối liên kết: một cho họ tên khách hàng, một cho số điện thoại và một cho thời gian lắp đặt. Các thao tác trên một danh sách đa liên kết được tiến hành tương tự như trên danh sách đơn nhưng được thực hiện làm nhiều lần và mỗi lần cho một liên kết. 4.5 Ngăn xếp ( Stack ) và hàng đợi ( Queue) 4.5.1 Ngăn xếp Stack là một danh sách mà hai phép thêm và loại bỏ đều được thực hiện trên một đầu hay còn gọi là đỉnh (Top ) của Stack. Như vậy, phần tử nào thêm vào sau sẽ bị loại bỏ trước, nên Stack còn được gọi là danh sách LIFO (Last In First Our list) hoặc Pushdown list. Có thể hình dung ngăn xếp như một chương trình Pascal mà chương trình A gọi chương trình B, chương trình B gọi chương trình C. Khi chương trình C được thực hiện xong thì sự điều khiển chương trình sẽ trở về thực hiện chương trình B, rồi khi chương trình B được thực hiện xong thì sự điều khiển chương trình sẽ trở về thực hiện chương trình A. Như vậy chương trình B được gọi sau sẽ được trở về Khoa KỸ THUẬT_ Trường Cao đẳng Kinh tế - Kỹ thuật Hải Dương
Giáo trình Cấu trúc dữ liệu 68 thực hiện trước chương trình A. Đó là nhờ điểm nhập (entry point) trở về của các chương trình được chứa trong Stack. Mô tả Stack và các thao tác cơ bản trên Stack a) Với Stack được mô tả bằng mảng: o Việc thêm một phần tử vào Stack tương đương với việc thêm một phần tử vào cuối mảng. o Việc bớt một phần tử của Stack tương đương với việc loại bỏ một phần tử ở cuối mảng. o Stack bị tràn khi bổ xung phần tử vào mảng đã đầy o Stack rỗng khi số phần tử thực sự trong mảng bằng 0. Program StackByArray; Const max = 10000; Var Stack : Array[1 max] of Integer; Khoa KỸ THUẬT_ Trường Cao đẳng Kinh tế - Kỹ thuật Hải Dương
Giáo trình Cấu trúc dữ liệu 69 Last : Integer; Khoa KỸ THUẬT_ Trường Cao đẳng Kinh tế - Kỹ thuật Hải Dương
Giáo trình Cấu trúc dữ liệu 70 Procedure StackInit; {khoi tao danh sach rong} Begin Last := 0; End; Procedure Push(v:integer);{dua gia tri v vao Stack} Begin If Last = max then Write('Stack da day !') Else Begin Inc(last); Stack(last) := V; End; End; Function Pop:integer; Begin If last = 0 then Write('Stack rong !') Else Begin Pop := Stack(last); Khoa KỸ THUẬT_ Trường Cao đẳng Kinh tế - Kỹ thuật Hải Dương
Giáo trình Cấu trúc dữ liệu 71 Dec(last); End; End; Khi cài đặt Stack bằng mảng tuy các thao tác hết sức đơn giản nhưng ta vẫn chia thành các chương trình con, mỗi chương trình con mô tả một thao tác, để từ đó về sau ta chỉ cần biết rằng chương trình của ta có cấu trúc Stack, và khi cài đặt Stack bằng các cấu trúc dữ liệu khác chỉ cần sửa lại thủ tục StackInit, Push, Pop mà thôi. b) Với Stack được mô tả bằng danh sách nối đơn. Khi cài đặt Stack bằng danh sách nối đơn kiểu LIFO thì Stack bị tràn vùng không gian nhớ dùng cho các biến động không còn đủ để thêm một phần tử mới, điều này phụ thuộc vào mỗi máy tính và ngôn ngữ lập trình. Ví dụ với Pascal khi vùng Heap còn trống 80 byte thì cũng chỉ đủ chỗ cho 10 biến, mỗi biến 6 byte, mặt khác không gian bộ nhớ dành cho các biến động thường rất lớn nên việc cài đặt ở đây ta bỏ qua việc kiểm tra việc Stack tràn. Việc cài đặt ngăn xếp bởi danh sách liên kết giống như chúng ta làm đối với danh sách. Đỉnh của ngăn xếp là đầu của danh sách liên kết. Program StackByLinkedList; Type PNode = ^ TNode; { Con tro tro toi mot nut cua danh sach } TNode = record { Cau truc mot nut cua danh sach } Value : integer; Link : PNode; End; Var Khoa KỸ THUẬT_ Trường Cao đẳng Kinh tế - Kỹ thuật Hải Dương
Giáo trình Cấu trúc dữ liệu 72 Last : PNode; Procedure StackInit; { Khoi tao Stack rong } Begin Last := NIL; End; Procedure Push( v : Integer ); { Day gia tri V vao Stack } Var P : PNode; Begin New(P); P^.Value := V; { Tao ra mot nut moi } P^.Link := Last; Last := P; { Moc noi nut do vao danh sach} End; Function Pop: Integer; { Lay ra mot phan tu ra khoi Stack } Var P : PNode; Khoa KỸ THUẬT_ Trường Cao đẳng Kinh tế - Kỹ thuật Hải Dương
Giáo trình Cấu trúc dữ liệu 73 Begin If Last = NIL then Write(' Stack is Empty ! ') Else Begin Pop := Last^.Value; { gan ket qua ham } P := Last^.Link; { Giu lai nut duoc day vao danh sach truoc nut Last^ } Dispose(Last); Last := P; {Giai phong bo nho cap cho Last^, cap nhat lai Last moi} End; End; Last Last Phép toán Push Phép toán Pop Khoa KỸ THUẬT_ Trường Cao đẳng Kinh tế - Kỹ thuật Hải Dương
Giáo trình Cấu trúc dữ liệu 74 4.5.2 Hàng đợi (Queue) Hàng đợi là một danh sách mà phép thêm vào được thực hiện ở đầu này và loại bỏ được thực hiện ở đầu kia. Như vậy, phần tử nào vào trước sẽ được loại bỏ trước, phần tử nào vào sau sẽ được loại bỏ sau, nên hàng đợi còn được gọi là danh sách FIFO (First In First Out list). Vì vậy hàng đợii là cấu trúc thích hợp để lưu trữ các dữ liệu được xử lý theo thứ tự mà chúng tạo ra. a) Với Queue được mô tả bằng mảng: Khi mô tả hàng đợi bằng mảng, ta có hai chỉ số First và Last, First lưu chỉ số phần tử đầu của hàng đợi, Last lưu chỉ số phần tử cuối cùng của hàng đợi. khởi tạo một hàng đợi rỗng: First := 1, Last := 0; o Để thêm một phần tử vào hàng đợi ta tăng Last lên 1 và đưa giá trị đó vào phần tử thứ Last. o Để loại một phần tử khỏi hàng đợi, ta lấy giá trị ở vị trí First và tăng giá trị này lên 1. o Khi tăng Last lên hết khoảng chỉ số của mảng thì mảng đầy, không thể thêm nữa. o Khi First > Last tức là hàng đợi đang rỗng. Như vậy chỉ những phần tử của mảng từ vị trí First tới vị trí Last được sử dụng làm hàng đợi. Program QueueByArray; Const max = 10000; Var Khoa KỸ THUẬT_ Trường Cao đẳng Kinh tế - Kỹ thuật Hải Dương
Giáo trình Cấu trúc dữ liệu 75 Queue : Array[1 max] of Integer; First, Last : Integer; Procedure QueueInit; {khoi tao hang doi rong} Begin First:=1; Last := 0; End; Procedure Push(v:integer);{dua gia tri v vao Queue} Begin If Last = max then Write('Queue da day !') Else Begin Inc(Last); Queue[Last] := V; End; End; Function Pop:integer; Begin If First > Last then Write('Queue rong !') Else Khoa KỸ THUẬT_ Trường Cao đẳng Kinh tế - Kỹ thuật Hải Dương
Giáo trình Cấu trúc dữ liệu 76 Begin Pop := Queue[First]; Inc( First); End; End; Để ý ta thấy khi cài đặt một Stack bằng một mảng có kích thước tối đa là 10000 phần tử thì khi ta thực hiện 6000 lần Push rồi 6000 lần Pop, sau đó lai thực hiện 6000 lần Push thì vẫn không có lỗi xảy ra, lý do là chỉ số Last lưu đỉnh của Stack được tăng lên 6000 rồi lại giảm về 0 rồi lại tăng lên 6000. Nhưng đối với cách cài đặt Queue như trên thì máy sẽ báo lỗi tràn mảng bởi mỗi lần Push, chỉ số cuối hàng đợi Last cũng tăng lên mà không bao giờ giảm. Đó chính là một điểm chú ý khi cài đặt và thao tác với hàng đợi, chỉ có các phần tử từ vị trí First tới vị trí Last là có nghĩa còn các phần tử từ 1 tới First - 1 là vô nghĩa. Để khắc phục điều này người ta mô tả hàng đợi bằng một danh sách vòng: Coi như các phần tử của mảng được xếp xung quang một vòng tròn theo chiều kim đồng hồ. Các phần tử nằm trên cung tròn từ vị trí First đến vị trí Last là các thành phần của Queue và có thêm một biến n để lưu số phần tử của Queue. Việc thêm phần tử vào Queue tương đương với việc ta dịch chỉ số Last theo chiều kim đồng hồ một vị trí rồi đặt giá trị mới vào đó. Việc loại bỏ một phần tử trong Queue tương đương với việc lấy ra phần tử tại vị trí First rồi dịch First theo chiều kim đồng hồ một vị trí. Last Khoa KỸ THUẬT_ Trường Cao đẳng Kinh tế - Kỹ thuật Hải Dương First
Giáo trình Cấu trúc dữ liệu 77 Lưu ý là trong thao tác Push và Pop phải kiểm tra Queue tràn hay Queue rỗng nên phải cập nhật lại biến n. (Thực ra ở đây dùng thêm biến n cho dễ hiểu chứ thực tế chỉ cần hai biến Last và First là ta có thể kiểm tra được Queue tràn hay cạn rồi.) Program QueueByCircleList; Const max = 10000; Var Queue : Array[1 max] of Integer; I, n, First, Last : Integer; Procedure QueueInit; {khoi tao hang doi rong} Begin First:=1; Last := 0; N:=0; End; Procedure Push(v:integer);{dua gia tri v vao Queue} Khoa KỸ THUẬT_ Trường Cao đẳng Kinh tế - Kỹ thuật Hải Dương
Giáo trình Cấu trúc dữ liệu 78 Var NewLast: Integer; Begin If n = max then Write('Queue da day !') Else Begin If Last = Max then Last := 1 else inc(Last); Queue[Last] := V; Inc(n); {n := n +1 } End; End; Function Pop:integer; Begin If n=0 then Write('Queue rong !') Else Begin Pop := Queue[First]; Khoa KỸ THUẬT_ Trường Cao đẳng Kinh tế - Kỹ thuật Hải Dương
Giáo trình Cấu trúc dữ liệu 79 If First = max then First := 1 Else Inc( First); Dec(n); End; End; b) Cài đặt Hàng đợi bằng Danh sách liên kết đơn kiểu FIFO Tương tự như cài đặt Stack bằng danh sách nối đơn kiểu LIFO (giả sử không gian bộ nhớ đủ để cấp phát cho các thành phần mới được đưa vào hàng đợi), nên ta cũng không cần kiểm tra Hàng đợi tràn trong trường hợp mô tả Hàng đợi bằng danh sách nối đơn kiểu FIFO. Đièu kiện để hàng đợi rỗng là Queue.First = Nil. First Last . . . . . Các thủ tục và hàm thực hiện các phép toám trên Hàng đợi được mô tả như sau: Program QueueByLinkedList; Type PNode = ^TNode;{kieu con tro tro toi mot nut cua DS} TNode = Record {Cau truc mot nut cua DS} Value: Integer; Khoa KỸ THUẬT_ Trường Cao đẳng Kinh tế - Kỹ thuật Hải Dương
Giáo trình Cấu trúc dữ liệu 80 Link: PNode; End; Var First, Last: PNode; {Hai con tro tro toi nut dau va nut cuoi cua DS} Khoa KỸ THUẬT_ Trường Cao đẳng Kinh tế - Kỹ thuật Hải Dương
Giáo trình Cấu trúc dữ liệu 81 Procedure QueueInit; {Khoi tao Queue rong} Begin First := Nil End; Function Empty:Boolean; {Kiem tra Queue rong} Begin If First = Nil then Empty := True Else Empty := False; End; Procedure Push(V: Integer); {Dua gia tri V vao Queue} Var P: PNode; Begin New(p); P^.Value := V; {tao ra mot nut moi} P^.Link := Nil; If First := Nil Then First := P {Moc nut do vao DS} Else Last^.Link := P; Last := P; {Nut moi tro thanh nut cuoi va cap nhat lai con tro Last} End; Khoa KỸ THUẬT_ Trường Cao đẳng Kinh tế - Kỹ thuật Hải Dương
Giáo trình Cấu trúc dữ liệu 82 Function Pop: Integer; Var P: PNode; Begin If First := Nil then Write('Queue is Empty !') Else Begin Pop := First^.Value; P := First^.Link; {Giu lai nut tiep theo First^ - Nut duoc day vao DS ngay sau First^} Dispose(First);{Giai phong bo nho cap cho First^} First := P; {Cap nhat lai First moi} End; End; TÓM TẮT Trong chương này chúng ta đã nghiên cứu một kiểu Dữ liệu mới - Danh sách, một trong những mô hình dữ liệu quan trọng nhất, được sử dụng thường xuyên trong các thuật toán. Có rất nhiều cách, nhiều phương pháp khác nhau để cài đặt một danh sách, tương ứng với mỗi cách cài đặt lại có các phép toán riêng. Tại mỗi phương pháp cài đặt chúng tôi đều phân tích và đưa ra các phép toán tương ứng, có ví dụ, hình vẽ Khoa KỸ THUẬT_ Trường Cao đẳng Kinh tế - Kỹ thuật Hải Dương
Giáo trình Cấu trúc dữ liệu 83 minh hoạ kèm theo. Các phép toán cơ bản đều có đoạn chương trình mẫu hướng dẫn và giải thích cụ thể. Trong Kiểu dữ liệu danh sách có hai kiểu dữ liệu trừu tượng đặc biệt quan trọng là Ngăn xếp (Stack) và hàng đợi (Queue). Là một cấu trúc dữ liệu được dùng khá phổ biến trong thiết kế giải thuật. Bất kỳ nơi nào ta cần quản lý dữ liệu, quá trình theo kiểu vào sau - ra trước hay vào trước-ra trước đều có thể ứng dụng ngăn xếp hay hàng đợi. Ví dụ rất dễ thấy là quản lý in trên mạng, nhiều máy tính yêu cầu in đồng thời và ngay cả một máy tính cũng yêu cầu in nhiều lần. Nói chung có nhiều yêu cầu in dữ liệu, nhưng máy in không thể đáp ứng tức thời tất cả các yêu cầu đó nên chương trình quản lý in sẽ thiết lập một hàng đợi để quản lý các yêu cầu. Yêu cầu nào mà chương trình quản lý in nhận trước nó sẽ giải quyết trước. Một ví dụ khác là duyệt cây theo mức được trình bày chi tiết trong chương sau. Các giải thuật duyệt theo chiều rộng một đồ thị có hướng hoặc vô hướng cũng dùng hàng đợi để quản lý các nút đồ thị. BÀI TẬP CHƯƠNG 4 Bài tập lý thuyết 1- Phân tích ưu, khuyết điểm của xâu liên kết so với mảng. Tổng quát hoá các trường hợp nên dùng xâu liên kết. 2- Xây dựng một cấu trúc dữ liệu thích hợp để biểu diễn đa thức P(x) có dạng: P(x) = c1xn-1 + c2xn-2 + + ckxn-k Biết rằng: - Các thao tác xử lý trên đa thức bao gồm: + Thêm một phần tử vào cuối đa thức Khoa KỸ THUẬT_ Trường Cao đẳng Kinh tế - Kỹ thuật Hải Dương
Giáo trình Cấu trúc dữ liệu 84 + In danh sách các phần tử trong đa thức theo: Thứ tự nhập vào Ngược với thứ tự nhập vào + Huỷ một phần tử bất kỳ trong danh sách - Số lượng các phần tử không hạn chế - Chỉ có nhu cầu xử lý đa thức trong bộ nhớ chính. Giải thích lý do chọn CTDL đã định nghĩa. Viết chương trình con ước lượng giá trị của đa thứcP(x) khi biết x. Viết chương trình con rút gọn biểu thức (gộp các phần tử cùng số mũ) 3- Hãy cho biết nội dung của stack sau mỗi thao tác trong dãy: EAS*Y QUE ST I*ON Với một chữ cái tượng trưng cho thao tác thêm chữ cái tương ứng vào stack, dấu * tượng trưng cho thao tác lấy nội dung một phần tử trong stack in lên màn hình.Hãy cho biết sau khi hoàn tất chuỗi thao tác, những gì xuất hiện trên màn hình? 4- Hãy cho biết nội dung của hàng đợi sau mỗi thao tác trong dãy: EAS*Y QUE ST I*ON Với một chữ cái tượng trưng cho thao tác thêm chữ cái tương ứng vào hàng đợi, dấu * tượng trưng cho thao tác lấy nội dung một phần tử trong hàng đợi in lên màn hình.Hãy cho biết sau khi hoàn tất chuỗi thao tác, những gì xuất hiện trên màn hình? Bài tập thực hành Khoa KỸ THUẬT_ Trường Cao đẳng Kinh tế - Kỹ thuật Hải Dương
Giáo trình Cấu trúc dữ liệu 85 1. Viết khai báo và các thủ tục cài đặt danh sách bằng mảng. Dùng các thủ tục này để viết: a. Thủ tục nhận một dãy các số nguyên nhập từ bàn phím và lưu trữ trong danh sách theo thứ tự nhập vào. b. Thủ tục nhận một dãy các số nguyên nhập từ bàn phím và lưu trữ trong danh sách theo thứ tự ngược với thứ tự nhập vào. c. Viết thủ tục in ra màn hình các phần tử trong danh sách theo thứ tự trong danh sách. 2. Tương tự như bài tập 1. nhưng cài đặt bằng con trỏ. 3. Viết thủ tục thêm một phần tử trong danh sách liên kết đã có thứ tự sao cho ta vẫn có một danh sách có thứ tự. 4. Viết các chương trình con: EmptyQ, CreateQ, AddQ, RemoveQ để a. Tìm phần tử ở cuối hàng đợi, để lại hàng đợi rỗng. b. Tìm phần tử thứ n của hàng đợi, làm cho hàng đợi không còn n phần tử đầu tiên. c. Tìm phần tử ở đầu hàng đợi nhưng không xoá nó khỏi hàng đợi d. Tìm phần tử thứ n của hàng đợi nhưng không làm thay đổi giá trị của hàng đợi. 5. Dùng các phép toán cơ bản của Stack và Queue viết một thuật toán đảo ngược các phần tử của hàng đợi. 6. Mô phỏng việc tạo buffer in một file ra máy in. Buffer xem như là một hàng, khi ra lệnh in file máy tính sẽ thực hiện một cách lặp quá trình sau cho đến hết file: - Ðưa nội dung của tập tin vào buffer cho đến khi buffer đầy hoặc hết file. - In nội dung trong buffer ra máy in cho tới khi hàng rỗng. Khoa KỸ THUẬT_ Trường Cao đẳng Kinh tế - Kỹ thuật Hải Dương