các bạn có thể tham khảo các bài khác tại đây:
cơ sở dữ liệu và giải thuật

đây là bài tiếp nối bài 3 [phần 2:cấu trúc dữ liệu][bài 3] mảng và danh sách. mình sẽ bổ sung thêm cho các bạn các dạng khác của một danh sách móc nối :d:d:d:d
1.danh sách nối vòng:
danh sách nối vòng là cải tiến của danh sách nối đơn, đặc điểm của nó là nút cuối cùng phần link không phải là null như danh sách nối đơn mà nó mang địa chỉ của phần tử đầu danh sách

[img]data/attachments/116/116311-768d3bade87669754b5053c9815f9853.jpg[/img]


với cải tiến thành danh sách nối vòng từ danh sách nối đơn này thì ta thấy việc truy cập danh sách được linh hoat hơn rất nhiều, điểm nào cũng có thể coi là điểm đầu của danh sách và các phép loại bỏ ghép tách đều được thuận lơi. nhưng nếu xử lý không cẩn thận thì sẽ tạo ra một chu trình liên tục không thể kết thúc vì không có điểm kết thúc của danh sách, chính vì vậy ta thêm vào đầu danh sách một nút head làm nút đánh dấu với qui ước nút này là nút đầu của danh sách:

[img]data/attachments/116/116321-781d8118f527c32632fbc4a122291d93.jpg[/img]



vậy về mặt hình thức thì danh sách không bao giò bị rỗng vì luôn có một nút head. kể cả trong danh sách đơn người ta cũng hay dặt nút head làm nút đầu của danh sách.
2.danh sách nối kép:
danh sách nối kép giúp việc duyệt các phần tử trơn tru hơn không chỉ theo một chiều như danh sách nối đơn và danh sách nối vòng, mà nó duyệt theo cả 2 chiều. để có thể duyệt theo cả 2 đầu thì một phần tử trong danh sách phải chứa 2 link: 1 link là con trỏ trái trỏ vào phần tử đứng trước ta gọi là left pointer(lptr)
một link là con trỏ phải ta gọi là right pointer(rptr):


[img]data/attachments/116/116331-b95352d38335f4ee359efea7f49dc627.jpg[/img]


và danh sách nối kép sẽ có dạng như sau, với hai đầu là null vì không có phần tử tiếp theo để trỏ:


[img]data/attachments/116/116341-cca203dff487174c9f16874568b04d0e.jpg[/img]


khi danh sách rống thì hai con trỏ hai dầu danh sách sẽ bằng null.
ta xét 2 giải thuật bổ sung và loại bỏ phần tử trong danh sách nối kép ở trên:
đầu tiên ta có con trỏ chỉ nút null phía trái là l, phía phải là r:
phép bổ sung phần tử: bổ sung ở phía cực trái, phải và bổ sung ở giữa.
gọi m là con trỏ trỏ tới một phần tử bất kì nào của danh sách, và x là phần tử cần phải thêm vào:
if l=r= null (danh sách trống) then
lptr(x)=rptr(x)=null
l=r=x
else
<1>. bổ sung ở đầu: m=l
lptr(x)=null
rptr(x)=m
lptr(m)=x
l=x;
< 2>.bổ sung ở giữa chuỗi sau phần tử đc chỉ bởi m:
lptr(x)=m
rptr(x)=rptr(m)
rptr(m)=x
lptr(rptr(x))=x (ở đây rptr(x) = rptr(m) = p với p là phần tử đứng sau m lúc chưa bổ sung x, khi bổ sung x vào thi lptr(p) sẽ chỉ vào x hay lptr(p)=x <=> lptr(rptr(x) = x)
<3>.bổ sung vào điểm cực phải(giống như bổ sung vào điểm cục trái) m=r câu lệnh cũng giống như <1>.

phép loại bỏ phần tử: các bạn có thể tự làm, loại bỏ phần tử m thì ta cần dò lần lượt con trỏ đến phần tử trước m, như ở bài trước đã nói, hàm để loại bỏ m là dispose(m)(trong hàm này có công cụ để loại m chúng ta coi như đã có hàm chỉ việc gọi lại nó)


ta lại áp dụng như danh sách nối đơn, biến thành danh sách nối kép lai nối vòng, và ta cũng thêm một nút đầu tiên cho danh sách.

android.vn/attachments/untitled-png.116891/" border="0" alt="" />


bài tập:
  • cho danh sách nối đơn, nút đầu tiên được trỏ bởi l.lập giải thuật,a,tính số lượng các nút của danh sách b,tìm tới nút thứ k có trong danh sách, nếu có nút thứ k thì cho ra địa chỉ nút đó nếu không thì cho ra giá trị null c,bổ sung một nút sau k, loại bỏ một nút trước k d,đảo ngược danh sách đã cho.
  • 2 cho danh sách nối kép lai nối vong,l là con trỏ trỏ tới nút head lập giải thuật loại bỏ tất cả nút có info= k cho trước ( ví dụ rptr(l)=k thì nút kế tiếp của l có giá trin info làk)


cảm ơn các bạn đã theo doi, chúc các bạn thành công! không hiểu thì hãy cmt bên dưới mình sẽ cố gắng trả lời đầy đủ nhất cho các bạn.


có gì thắc mắc các bạn có thể liên hệ face book mình:http://www.facebook.com/linh193