Tài liệu Bồi dưỡng học sinh giỏi tin học thpt chuyên đề danh sách liên kết – cấu trúc dữ liệu đệ quy

DANH SÁCH LIÊN KẾT – CẤU TRÚC DỮ LIỆU ĐỆ QUY Trong quá trình học tập, việc chuyển từ các cấu trúc dữ liệu đơn giản chuyển sang các cấu trúc dữ liệu nâng cao là một bước khá khó khăn đối với học sinh mới nhất là giai đoạn đầu. Việc hướng dẫn một cách tỉ mỉ và dễ hiểu dựa trên những kiến thức đã được học sẽ giúp cho quá trình tiếp cận của học sinh thêm dễ dàng và thêm hứng thú. Với các học sinh đã tiếp cận với giải thuật đệ quy, tôi xin trình bày trong chuyên đề này về cấu trúc dữ liệu danh sách liên kết (linked list) theo tiếp cận như một cấu trúc dữ liệu đệ quy. Với cách tiếp cận này, có thể thấy được cấu trúc danh sách liên kết quen thuộc, dễ hiểu hơn và dễ cài đặt hơn và có thể “nhận thấy” danh sách liên kết có rất nhiều ứng dụng trong quá trình giải quyết bài toán. Phần lý thuyết tương đối ít, trình bày theo mạch bài giảng nên kiến thức ứng dụng bài toán cụ thể chưa có nhiều. Mục đích chính của chuyên đề là nổi bật được cấu trúc đệ quy của danh sách liên kết. Một số bài tập nhỏ, câu hỏi chỉ với mục đích giúp học sinh có thể tự cài đặt được một danh sách liên kết đơn giản. Contents DANH SÁCH LIÊN KẾT – CẤU TRÚC DỮ LIỆU ĐỆ QUY ............................1 1. Đặt vấn đề ............................................................................................................1 Phương pháp biểu diễn dãy dữ liệu có thứ tự: ................................................1 Phương pháp cài đặt bởi một mảng ..................................................................2 Phương pháp cài đặt bởi cấu trúc danh sách liên kết (linked list) ................2 Ví dụ về lưu trữ bằng danh sách liên kết .........................................................4 2. Một danh sách liên kết là một cấu trúc dữ liệu đệ quy...................................4 Sử dụng vòng lặp để duyệt qua danh sách liên kết .........................................7 Xóa một phần tử ở vị trí thứ i trong danh sách liên kết .................................8 Chèn thêm một phần tử vào vị trí thứ i trong danh sách liên kết ..................8 3. Bài tập đề nghị: ...................................................................................................9 1. Đặt vấn đề Phương pháp biểu diễn dãy dữ liệu có thứ tự: Dãy dữ liệu có thứ tự là một tập hợp các phần tử có sắp thứ tự có thể được biểu diễn bằng một số cấu trúc dữ liệu như: danh sách (list), hàng đợi (queue), ngăn xếp (stack). 1 Phương pháp cài đặt bởi một mảng Những lợi ích khi biểu diễn bằng mảng - - Dễ dàng truy cập tới bất kì phần tử nào trong mảng một cách hiệu quả (Tính chất này của mảng còn được gọi là truy cập ngẫu nhiên)  Item[i] biểu diễn phần tử thứ i trong dãy  Mọi phần tử đều có thể truy cập với độ phức tạp như nhau. Cài đặt rất gọn Những nhược điểm khi cài đặt bẳng mảng: - Khi cài đặt nhất thiết phải chỉ định kích thước tối đa cho mảng, và khi cần thiết phải điều chỉnh kích thước tối đa đó. Khi thực hiện các thao tác chèn (insert) hay xóa (delete) phần tử trong dãy thì hơi khó khăn. Ví dụ: chèn phần tử có giá trị 63 vào giữa hai phần tử số 52 và 73 Phương pháp cài đặt bởi cấu trúc danh sách liên kết (linked list) - Ví dụ về danh sách liên kết: - Một danh sách liên kết lưu trữ dãy các phần tử có thứ tự trong các nút độc lập gọi là nút (node). Cấu trúc một nút gồm: -  Một phần chứa giá trị  Một liên kết (link) trỏ tới nút khác chứa giá trị phần tử tiếp theo. Nút cuối cùng trong danh sách liên kết chứa giá trị trường liên kết link là rỗng. Danh sách liên kết được thể hiện bằng một biến chứa giá trị trỏ tới nút đầu tiên. So sánh Mảng và Danh sách liên kết - Thể hiện trong bộ nhớ: o Khi khai báo một mảng, các phần tử chiếm các vị trí ô nhớ liên tiếp trong bộ nhớ máy tính: 2 o Trong một danh sách liên kết, mỗi nút là một đối tượng khác biệt trong trong bộ nhớ. Các nút không nhất thiết phải nối tiếp nhau trên bộ nhớ như đối với biểu diễn mảng. Đó là lý do mà chúng ta cần phải có một liên kết (link) để có thể truy cập từ phần tử này tới phần tử kế tiếp Hình ảnh dưới đây thể hiện lưu trữ danh sách liên kết ở ví dụ trên thực sự trong bộ nhớ máy tính. Những ưu điểm của danh sách liên kết - Danh sách liên kết có thể chứa được số lượng phần tử bất kì (chỉ hạn chế bởi bộ nhớ máy tính) Rất dễ dàng thực hiện các thao tác Chèn/Xóa một nút vào danh sách mà không cần phải dịch chuyển các phần tử khác. 3 Nhược điểm của danh sách liên kết - - Không hỗ trợ tính chất truy cập ngẫu nhiên như mảng: khi muốn truy cập tới một phần tử nào đó trong dãy, bắt buộc phải duyệt qua tất cả các phần tử đứng trước nó. Trường liên kết (link) trong mỗi nút sẽ cần thêm không gian nhớ. Ví dụ về lưu trữ bằng danh sách liên kết Một xâu kí tự có thể xem như một danh sách liên kết của các kí tự - Mỗi nút trong danh sách đó biểu diễn một kí tự. Khai báo danh sách liên kết cho một nút Type Pnode = ^Tnode; Tnode = Record Ch: char; Next: PNode; End; - Một xâu kí tự được biểu diễn bẳng danh sách liên kết được thể hiện bằng một biến, biến đó chứa phẩn tử trỏ tới nút chứa kí tự đầu tiên trong chuỗi. Ví dụ: Var str1: TNode; Biểu diễn một chuỗi rỗng bằng một biến có giá trị NIL Var str1: TNode = NIL; Khi cài đặt các hàm/ thủ tục thao tác trên chuỗi, có thể đặt xâu làm tham số ví dụ length(str1) 2. Một danh sách liên kết là một cấu trúc dữ liệu đệ quy 1. Định nghĩa đệ quy cho một danh sách liên kết: một danh sách liên kết là: a. Một danh sách rỗng hoặc b. Một nút đơn + một danh sách liên kết 2. Khi xem xét danh sách liên kết theo hướng đệ quy như vậy cho phép chúng ta viết các thủ tục đệ quy khi thao tác với danh sách liên kết. o Ví dụ về độ dài của xâu kí tự:  Độ dài xâu ‘cat’ = 1 + độ dài xâu ‘at’  Độ dài xâu ‘at’ = 1 + độ dài xâu ‘t’  Độ dài xâu ‘t’ = 1 + độ dài xâu rỗng (=0) Function length(TNode str): integer; Begin If (str = nil) then exit(0) Else exit(1+length(str.next)); End; - Truy viết hàm length 4 o o Thể hiện bằng stack (ngăn xếp) - Lấy giá trị phần tử thứ i trong danh sách liên kết Hàm getNode(str,i): cho phép trả về giá trị phần tử thứ i trong danh sách liên kết (i=0 nếu phần tử đầu tiên của danh sách) Phương án đệ quy: o Nút ở vị trí số 2 trong danh sách liên kết thể hiện chuỗi ‘linked’  = nút ở vị trí số 1 trong danh sách liên kết thể hiện chuỗi ‘inked’  = nút ở vị trí số 0 trong danh sách liên kết thể hiện chuỗi ‘nked’ Bài tập: viết hàm thực hiện việc trả về giá trị phần tử thứ i trong danh sách liên kết? Bài tập: thực hành chỉ ra giá trị và địa chỉ ô nhớ khi tiến hành câu lệnh sau: Str.next.next sẽ có giá trị là bao nhiêu? ở địa chỉ nào? Hoạt động của phép gán Var1 := Var2; Chương trình sẽ lấy giá trị của Var2, sao chép nó tới một vị trí bộ nhớ của biến Var1. Thực hành 1: cho hình vẽ sau biểu diễn danh sách liên kết: Điều gì xảy ra nếu ta thực hiện các phép gán sau: 1) str.next := temp.next; 2) temp := temp.next; Thực hành 2: Nếu biến temp không trỏ tới nút chứa giá trị ‘o’, viết câu lệnh gán phù hợp để temp trỏ tới nút ‘o’ đó? 5 Ví dụ: Tạo một bản sao của danh sách liên kết - Hàm copy(str) cho phép tạo ra một bản sao của str và trả về một biểu diễn tới nó. - Tiếp cận đệ quy: o Neo: nếu str rỗng, trả về NIL o Đệ quy: sao chép phần tử đầu tiên, gọi đệ quy để sao chép phần còn lại. Code: Function copy(TNode str): TNode; Var copyFirst: TNode; Begin If (str=nil) exit(nil) Else begin copyFirst := new TNode(str,ch,nil); copyFirst.next = copy(str.next); end; exit(copyFirst); End. 6 Sử dụng vòng lặp để duyệt qua danh sách liên kết - Rất nhiều bài toán yêu cầu phải duyệt qua toàn bộ danh sách liên kết. Chúng ta vừa thực hiện thao tác duyệt danh sách liên kết theo hướng đệ quy Ngoài ra, có thể sử dụng vòng lặp để thực hiện việc đó Tạo biến Trav để lưu vị trí hiện thời đang duyệt đến của danh sách liên kết: o While (trav <>NiL) do  Trav:=trav.next; Ví dụ: duyệt qua toàn bộ xâu kí tự, chuyển tất cả các kí tự trong xâu thành chữ hoa Gợi ý: duyệt lần lượt qua các phần tử của danh sách liên kết, sử dụng biến trav để lưu vị trí hiện thời, tại mỗi nút, đổi giá trị kí tự thành kí tự hoa, chuyển con trỏ sang phần tử tiếp theo. Dừng khi con trỏ là NIL 7 Kết quả: Xóa một phần tử ở vị trí thứ i trong danh sách liên kết Có hai trường hợp: 1) Nếu i=0, xóa phần tử đầu tiên bằng cách str:=str.next 2) Nếu i>0: chuyển con trỏ sang phần tử kế tiếp Hỏi: câu lệnh sẽ như thế nào? Chèn thêm một phần tử vào vị trí thứ i trong danh sách liên kết Trường hợp 1: i=0 (chèn vào đầu danh sách) Hỏi: viết câu lệnh tạo nút mới? Hỏi: Câu lệnh nào cho phép chèn nút vào danh sách? Trường hợp 2: i>0 - Duyệt đến vị trí của nút i-1 8 - Hỏi: viết câu lệnh chèn kí tự ‘m’ vào nút mới khởi tạo? và câu lệnh gắn nút mới vào vị trí thứ i? Một số biến thể của danh sách liên kết: Danh sách liên kết kép - Danh sách liên kết với một nút rỗng ở trước 3. Bài tập đề nghị: 1. Viết giải thuật delete() với tham số đầu vào là một giá trị k kiểu interger. Phương thức delete() sẽ thực hiện xóa phần tử thứ k (nếu có) trong Linked List. 2. Cài đặt phương thức find() với tham số đầu vào là một khóa key kiểu String. Kết quả trả về là true nếu tìm thấy trong Linked List. Ngược lại thì false. 3. Giả sử x là một Node trong linked list. Đoạn mã nguồn sau thực hiện việc gì? x.next = x.next.next; 4. Giả sử x là một Node trong danh sách liên kết. Đoạn code sau thực hiện điều gì? t.next = x.next; x.next = t; 5. Tại sao đoạn code sau không cho ra cùng kết quả giống như đoạn code ở câu 4. x.next = t; t.next = 9 x.next; 6. Viết phương thức removeAfter() với tham số đầu vào là một Node x trong Linked list. Yêu của của phương thức là xóa node ngay sau node x. 7. Viết phương thức insertAfter() với tham số đầu vào là 2 Node. Yêu cầu của phương thức là thêm Node thứ 2 vào sau node thứ 1 (node thứ 1 đã có sẵn trong linked list). Trường hợp node null thì không thực hiện gì. 8. Cài đặt phương thức remove() với tham số đầu vào là một linked list và một khóa key kiểu String. Yêu cầu của phương thức là xóa hết tất cả các node trong linked list có khóa là key. 9. Cài đặt phương thức tìm giá trị lớn nhất trong danh sách liên kết.. 10. Sử dụng giải thuật đệ quy để cài đặt giải thuật trong câu 8, 9. 11. Sử dụng giải thuật đệ quy để in ra các phần tử trong linked list theo thứ tự ngược. Trên đây là một chút kinh nghiệm của bản thân trong quá trình dạy về cấu trúc dữ liệu danh sách liên kết cho học sinh lớp 10 muốn chia sẻ cùng với các đồng nghiệp. Rất mong các thầy cô góp ý, chỉ bảo thêm. 10