Một số nội dung cần thuộc như nước chảy. Không được nhầm lẫn. Nếu nhầm là 0 điểm luôn.
Về các đề bài về một xâu liên kết sẽ có dạng:

Cho một danh sách được tổ chức bởi cấu trúc sau:
Danh_sách: ^ Phần_tử
Phần_tử = Record;
Dữ_liệu_1: Data;
Dữ_liệu_2: Data;
...
Dữ_liệu_n: Data;
Next: List;
End

Trong đó:
Những phần chữ màu đỏ sẽ được thay bằng nội dung của đề bài, các bạn nhớ phải viết và lập luận theo nó. Phần chữ màu đen là từ khoá.

Danh sách liên kết thường được cho luôn là nó được trỏ bởi Head.

Một số phần cần thuộc luôn, để khi ứng dụng chỉ việc bê nguyên xi:

---

1. Ví dụ đề bài:
Cho một danh sách S được tổ chức bởi cấu trúc sau:

List: ^ Element;

Element = Record;

D: Data;

Next: List;

End


Tìm một phần tử có nội dung X.

---

Giả sử phần tử cần tìm là Y.
Bước 1. Cho Y bằng luôn Head, ở đây Head được gọi tên là S (Tên danh sách).
Y:=S;
Bước 2. Viết vòng lặp cho Y chạy dần qua từng phần tử, nếu dữ liệu của phần tử hiện tại (Y) mà không bằng giá trị cần tìm (X), thì chuyển sang phần tử kế tiếp.
While (Y^.D <>X) Do
Y:=Y^.Next

Kết quả, Y sẽ dừng đúng vị trí của phần tử cần tìm.

---

Hay nhầm dễ bị trừ điểm, hoặc bị đưa về mo là: Lẽ ra phải viết Y.D <> X thì lại viết Y.Data <>X
Bởi tên trường theo đầu bài là D.

Cần học thuộc luôn. Bao giờ cũng phải làm như vầy mới đủ. Giả sử có danh sách liên kết như phần trên trình bày. Bây giờ cần thêm một phần tử có giá trị B vào sau phần tử có giá trị A trong danh sách.

Thủ tục cần thực hiện:
Tìm lần lượt từng phần tử. Bằng cách sử dụng một biến con trỏ luôn chỉ vào 1 nút có trong danh sách. Nó là phần tử hiện tại. Nếu phần tử hiện tại có giá trị là A, thì phải thực hiện tạo một nút mới M. Sau đó đặt lại các giá trị trường Next giúp cho việc nối thành chuỗi được liên tục:
1. Trường Next của M sẽ chỉ theo trường Next của ô hiện tại.
2. Phần tử tìm thấy (Tức phần tử hiện tại) có trường Next chỉ vào M.
3. Chuyển ô hiện tại thành M.

Thế là xong.
Trong trường hợp thêm vào tất cả các ô có giá trị A, thì cứ lần lượt mà thực hiện:
4. Kiểm tra tiếp từ M xem giá trị có bằng B không, khi không bằng thì chuyển sang phần tử kế tiếp.

Bây giờ là bài thầy giáo giảng:
Gọi Y là con trỏ đang trỏ vào đầu danh sách.

---

Proc Insert (A: Data; VAR Y: List)
While (Y <> Null)
Begin
          IF (^Y.D = A) THEN
                    New (M)
                    M.D = B
                    M^.Next = Y^.Next
                    Y^.Next = M
IF Y<> Null THEN Y=Y^.Next
End

---

Ở đây đang tranh cãi là có cần thiết phải có IF Y<> Null THEN không? vì vòng While đã kiểm tra điều kiện Y<> Null rồi.

Xoá một phần tử trong danh sách

Bài này thầy làm theo cách đệ quy. Nghĩa là khi gặp phần tử cần xoá thì thầy cho nó luôn là phần tử kế tiếp.
Bài của thầy:

---

Proc Delete (VAR Y: List);
IF (Y <> Null) Then
          IF (Y^.D = C) Then
                    Y:= Y^.Next
IF (Y <> Null) Then Delete (Y^.Next);

---

Ở đây, biến được truyền là một phần tử của chuỗi tên là Y. Nên thủ tục này sẽ làm việc với 1 phần tử hiện tại. Nếu thoả mãn cần xoá thì thay phần tử đang xét bằng phần tử kế tiếp mà nó trỏ đến.

Cho 2 danh sách liên kết A, B có cấu trúc như trên viết thủ tục để có được danh sách C có thể là

[You must be registered and logged in to see this image.] Cộng 2 danh sách, ở đây những phần tử trùng nhau về giá trị, cả ở trong A và B sẽ chỉ được đưa vào danh sách C 1 lần. Có lời giải của thầy.

[You must be registered and logged in to see this image.] Trừ 2 danh sách, những phần tử có trong A mà cũng có trong B sẽ bị loại đi. Chỉ còn một phần của A. Có lời giải của thầy.

[You must be registered and logged in to see this image.] Tạo danh sách là những phần tử giống nhau của cả A và B. Tự viết.

[You must be registered and logged in to see this image.] Tạo danh sách là những phần tử không giống nhau của cả A và B. Tự viết.

(Sở dĩ phải gõ lên đây để sẽ có lúc chúng ta cần đến, hoặc những đồng chí nghỉ học có cái mà tham khảo)

Ở đây thầy đưa ra một hàm phải thiết kế đó là hàm thuộc. Nếu xét một danh sách liên kết, có một phần tử có giá trị x thì trả về giá trị đúng, ngược lại là sai.

---

Cách 1: Giả sử A là con trỏ đang chỉ ra phần tử hiện tại.
Func Thuoc (X: Data, A: List);
While (^A.D <> x ) A:= A^.Next
return A!= Null;

Cách 2:
While A <>Null Do
IF A^.D = x return True
else A:= A^.Next
Return False

---

Đây là nội dung hàm CONG
C:=A;
While B <> Null do
IF B !thuộc (B^.D, C)
New (M); M^.D = B^.D;
M^.Next :=C;
C:=M
B:= B^.Next

---

Đây là nội dung hàm TRU

C:=Null;
While (A<> Null)
IF !Thuộc (A^D, B)
New (M); M^.D = A^.D;
A:=A^.Next


Các bạn căn cứ để viết hàm lại cho hoàn chỉnh nha. Bạn nào làm xong chia sẻ chút nha.

Sử dụng đệ quy để thêm một phần tử vào danh sách
Đây là bài thầy ra về nhà làm.

---

Proc THEM (A, B: Data, Y: List)
IF (Y^.D = A) then
New (M);
M.D = B;
M^.Next = Y^.Next
Y^.Next = M
IF (Y<> Null) THEN
THEM (A, B, Y^.Next)
End.

Tìm một phần tử có nội dung X.

---

Giả sử phần tử cần tìm là Y.
Bước 1. Cho Y bằng luôn Head, ở đây Head được gọi tên là S (Tên danh sách).
Y:=S;
Bước 2. Viết vòng lặp cho Y chạy dần qua từng phần tử, nếu dữ liệu của phần tử hiện tại (Y) mà không bằng giá trị cần tìm (X), thì chuyển sang phần tử kế tiếp.
While (Y^.D <>X) Do
Y:=Y^.Next

Kết quả, Y sẽ dừng đúng vị trí của phần tử cần tìm.

Nếu không tìm thấy X thì Y sẽ đi về đâu?

Sở dĩ tôi đưa lại vấn đề này vì danh sách liên kết là bài đáng được tranh luận để rút ra cái đúng nhất. Nhiều người trong lớp chúng ta không phải là học sinh cũ của HV nên có cách lưu trữ và tiếp cận với vấn đề này khác nhau. Về đây học kiến thức của HV là học những gì tiên tiến nhất, hiện tại chúng ta đang tự mâu thuẫn là không biết tiếp cận kiểu gì, khi mà sách và lời giảng trên lớp của thầy có nhiều chỗ được trình bày và triển khai theo 2 hướng khác nhau. Vấn đề này, lớp mình cũng đã tranh luận nhiều chưa đến hồi phân giải. Bởi theo nguyên tắc, nếu phần này chưa thống nhất, thì tất cả những bài tập về sau nếu dữ liệu ra kiểu này thì mỗi người sẽ hiểu một phách. Mà cách đánh giá của các thầy chỉ có một loại đáp án. Học theo đáp án của thầy thì cần làm rõ như thế nào?
Tham gia làm rõ phần này, đề nghị các đ/c chuyên viên có bình luận để tìm ra xem những gì ta đang quan niệm và những gì là bài giảng để tìm ra và làm theo nội dung chuẩn theo đáp án của đáp án chấm thi hơn.

Để chỉ ra những điểm không thống nhất giữa sách của thầy viết và bài giảng của thầy, tôi chịu khó gõ lại nội dung sách lên đây, vì tôi biết chúng ta tranh luận ở lớp bao phen rồi vẫn bất phân thắng bại, và cuối cùng nếu vẫn không biết theo cái nào, thì sẽ viết biên bản gửi lên khoa, đề nghị xem cách nào là đúng để chúng ta học cho chuẩn với đáp án chấm thi.

Tôi gõ chính xác từng chữ, kể cả những chữ mà các đồng chí bảo là sai chính tả. Những chữ này sẽ được tô màu. Việc gõ này phục vụ khi tranh luận, các đồng chí chỉ việc copy, đỡ phải gõ lại.
Phần nền màu hồng, để che đi chống dàn trải bài viết, khi nào cần đọc các đ/c nháy chuột vào đó.

Nội dung sách "Cấu trúc dữ liệu và giải thuật" của Học viện KTQS, tài liệu ôn thi Cao học ngành CNTT, sản xuất năm 2005, Chương 3, trang 19.
Danh sách liên kết

I. Danh sách liên kết đơn

1. Định nghĩa:

Mỗi nút của danh sách được lưu trữ trong một phần tử nhớ - gọi là nút (nude) của danh sách. Mỗi nút chiếm một số ô nhớ nhất định. Trong mỗi nút, ngoài các ô nhớ dành để lưu trữ thông tin của phần tử tương ứng, còn một số ô nhớ chứa địa chỉ của phần tử đứng ngay sau nó trong danh sách. Cách tổ chức dữ liệu theo kiểu móc nối các phần tử trong danh sách như vậy giải thích cho cách đặt tên kiểu cấu trúc dữ liệu. Có thể hình dung một cách đại khái một nút như sau:

Data

Next

Trường Data chứa thông tin phần tử, trường Next chứa địa chỉ của nút tiếp theo. Trường Next của nút cuối cùng chứa địa chỉ đặc biệt, dùng để đánh dấu kết thúc danh sách, ký hiệu Nil.
Ví dụ, định nghĩa danh sách dữ liệu về một nhân sự:

Ví dụ, định nghĩa danh sách dữ liệu về một nhân sự:

Một phần tử trong danh sách đơn là một biến động sẽ được yêu cầu cấp phát khi cần. Và danh sách đơn chính là sự liên kết các biến động này với nhau. Từ cách tổ chức như vậy, dễ thấy được, nếu 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ứ 2 trong xâu, và lại dựa vào thông tin Next của phần tử thứ 2 để truy xuất đến phần tử thứ 3... Nghĩa là để quản lý một xâu đơn, chỉ cần biết địa chỉ phần tử đầu xâu. Thường một con trỏ Head sẽ được dùng để lưu trữ phần tử đầu xâu, ta gọi Head là đầu xâu. Ta có thể khai báo:
Head: LINK;
Nếu dùng mũi tên để chỉ mối liên kết thông thường qua trường Next, ta có thể hình dung một danh sách móc nối đơn như sau:

2. Các phép toán:
1. Tìm một phần tử có nội dung X

• Danh sách được trỏ bởi Head
  
• X là dữ liệu cần tìm
  
• R là nút cần tìm
  

                    1) R: = Head;
                    2) While (R^.Data ≠ X) Do R:=R^.Next;
2. Bổ sung một nút mới vào danh sách móc nối đơn để chứa phần tử X.

• Danh sách được trỏ bởi Head;
  
• R là con trỏ, trỏ tới một nút đang có trong danh sách
  
• X chứa dữ liệu cần bổ sung vào
  
• Tạo một nút mới ngay sau R để lưu giá trị X
  

                    1) New (P); Khởi tạo một nút mới
                    2) P^.Data := X;
                    3) P^.Next := R^.Next;
                    4) R^.Next := P;

Nháy vào phần hồng hồng này để ẩn hiện hình vẽ minh hoạ:

3. Loại bỏ một nút ra khỏi danh sách đơn

• Danh sách được trỏ tới bởi Head
  
• R là con trỏ trỏ tới một nút đang có trong danh sách
  
• Loại bỏ nút R
  

          IF R:= Head Then Head:= Head^.Next;
                    ELSE
                    Begin
                              1) P := Head;
                              2) While (P^.Next ≠ R) Do P := P^.Next;
                              3) P^.Next := R^.Next;
                    End;

Nháy vào phần hồng hồng này để ẩn hiện hình vẽ minh hoạ:

4. Ghép hai danh sách đơn

• Cho hai danh sách được trỏ bởi Head và P
  
• Ghép P vào cuối Head
  

                    1) New (R);
                    2) R := Head;
                    3) While (R^.Next ≠ Nil) Do R := R^.Next;
                    4) R^. Next := P;

anh ơi . cho em hỏi trường hợp cần loại phần tử cuối cùng trong danh sách P thì làm thế nào?
Đây chỉ nói chung chung là loại một phần tử bất kỳ nên em chưa rõ lằm nhờ anh chị hướng dẫn?
em cảm ơn nhiều.

BQT:
Câu này đã được trả lời ít nhất 2 lần ở 2 topic gần đây:
[You must be registered and logged in to see this image.] [You must be registered and logged in to see this link.] [You must be registered and logged in to see this link.]

Đề nghị search trước khi hỏi cho đỡ mất công

xin lỗi em hỏi mọi người một câu hơi ngớ ngấn một chút: kí hiệu" ^ "trong các bước gán có nghĩa là gì vậy ? Hix! Quả thật khi vào ôn trường mình em mới biết tới kí hiệu này.

Ban QT:
Bạn đã lập trình với biến con trỏ chưa? Nếu bạn chưa học đến biến con trỏ sẽ không hiểu ký hiệu biến con trỏ để làm gì. Nó là ký hiệu để bạn lập trình chỉ ra vị trí của giá trị trong ô nhớ thôi.

Ví dụ cho bạn dễ hiểu. Lẽ ra bạn phải gán giá trị cho biến x bằng 5000 chẳng hạn. Cách lập trình thông thường là ngửa cái biến x ra, rồi phụt vào đấy giá trị = 5000 đúng không. Sau đó cập nhật lại giá trị vào cái danh sách địa chỉ ghi x = 5000.
Còn cách lập trình với biến con trỏ là lập trình trong bộ nhớ địa chỉ. Giống như bạn lãnh đạo vậy đó. Ghi x^ = b. Nghĩa là đổ vào biến x giá trị mà giá trị đó lưu ở vị trí b. Lúc này trong b là 1 tỷ hay 1 triệu thì x sẽ có giá trị 1 triệu hay 1 tỷ. Thay vì cộng trừ các giá trị 1 tỷ hay 1 triệu (chạy qua bộ nhớ, tốn thời gian và công sức) thì ta chỉ báo nó là đổi giá trị trong địa chỉ thôi. Sau này cộng trừ triệt tiêu địa chỉ thì ta chỉ lấy giá trị cuối cùng ở một địa chỉ khác, thay vì phụt giá trị trực tiếp vào.
Như bạn đó, lẽ ra bạn giải quyết xong việc phải đếm tiền ăn ngay, thì thay vào việc đó ta dùng biến chon trỏ để trả tiền trong tài khoản vậy thôi.
Thế nhé! Nếu bạn lập trình tốt thông qua biến con trỏ thì bạn thấy tốc độ máy chạy nhanh hơn nhiều. Các cấu trúc bây giờ người ta đưa ra một dạng dữ liệu có con trỏ thì có dấu mũ đó bạn!

trangmeomeo đã viết:xin lỗi em hỏi mọi người một câu hơi ngớ ngấn một chút: kí hiệu" ^ "trong các bước gán có nghĩa là gì vậy ? Hix! Quả thật khi vào ôn trường mình em mới biết tới kí hiệu này.

Bó tay chấm com... [You must be registered and logged in to see this image.]

trời. Bó tay thì bác cũng phải giả thích cho em hiểu chứ :(

Ban QT:
Nếu em có gì không hiểu thì điện thoại cho anh [You must be registered and logged in to see this link.], hoặc [You must be registered and logged in to see this link.] Quản trị và Chuyên viên diễn đàn nhé. 0976.096.086, 0982.601.369 bọn anh cũng chưa có vợ đâu!

Đó là ký hiệu con trỏ... Em nhé!

theo như mình biết thì node trong danh sách gồm có 2 phần: một là giá trị(key) và hai là chứa link ( NEXT )đến node kế tiếp.vậy thì muốn thao tác trên phần nào(key, link) thì phải trỏ tới nó đúng ko?
vậy thì ký hiệu ^: mang ý nghĩa là trỏ tới 1 phần tử nào đó.
vd: M^.Next tức là nude M trỏ tới phần NEXT (link đến node tiếp theo trong danh sách liên kết)

mình có quyển cẩm nang thuật toán(ko dùng nữa) nếu bạn cần thì mình có thể cho bạn để ôn tập
PS: anh phạm thái hưng chưa có gia đình( nhưng đã có người iu)

thinhdh1588 đã viết:theo như mình biết thì node trong danh sách gồm có 2 phần: một là giá trị(key) và hai là chứa link ( NEXT )đến node kế tiếp.vậy thì muốn thao tác trên phần nào(key, link) thì phải trỏ tới nó đúng ko?
vậy thì ký hiệu ^: mang ý nghĩa là trỏ tới 1 phần tử nào đó.
vd: M^.Next tức là nude M trỏ tới phần NEXT (link đến node tiếp theo trong danh sách liên kết)

mình có quyển cẩm nang thuật toán(ko dùng nữa) nếu bạn cần thì mình có thể cho bạn để ôn tập
PS: anh phạm thái hưng chưa có gia đình( nhưng đã có người iu)

Thanks các anh đã giải thích cho em hiểu. Nhưng có thể giúp em giải thích thêm về Điều kiện trong if của cấu trúc dưới đây được không ạ:

Proc Insert (A: Data; VAR Y: List)
WHILE (Y <> Null)
Begin
IF (^Y.D = A) THEN
New (M)
M.D = B
M^.Next = Y^.Next
Y^.Next = M
IF Y<> Null THEN Y=Y^.Next
End


à quên mất bạn thinhdh1588 bảo cho mình quyển cẩm nang thuật toán à. vậy thì còn gì bằng, nhưng làm sao để mình lấy được đây????????

ah mình xin giải thích giùm bạn như sau:
trước hết đây là thủ tục chèn một nude mới vào danh sách :D(chèn có điều kiện). Bài toán là chèn một nude mới vào sau nude có giá trị =A

WHILE (Y <> Null) // đây là câu lệnh dùng để duyệt danh sách, vòng lặp sẽ dừng khi ta ở cuối
danh sách (tức là Y=Null)
Begin
IF (Y^.D = A) THEN // câu lệnh này dùng để kiểm tra xem nếu nude hiện thời có giá trị =A thì
chèn thêm 1 nude mới vào

New (M) // thủ tục tạo mới nude M

M.D = B // gán giá trị B cho nude M

M^.Next = Y^.Next // nude link (NEXT) của M sẽ trỏ vào nude đứng sau nude hien thời( nút đứng
sau nút chứa giá trị A)

Y^.Next = M // nude chứa giá trị A sẽ trỏ tới( link tới) nude M

IF Y<> Null THEN Y=Y^.Next // câu lệnh này mình nghĩ không cần thiết.
End



PS: sáng thứ 4: 27-6 bọn mình thi môn của thầy lâm. nếu rảnh thì bạn có thể lên tầng 10( phòng 1013 tòa nhà S1 bên xuân phương) mình sẽ mang cho. hoặc không thì liên hệ với mình theo số: 097.909.1368