Bài viết của Nguyễn Huỳnh Quý Nam

Lớp : KHMT05

Trong bài viết hôm nay, tôi sẽ cùng bạn tìm hiểu về một cấu trúc dữ liệu khá phổ biến trong lập trình và cách cài đặt trong C#. Đó là danh sách liên kết (DSLK) đơn.

 

Tổng quan

DSLK đơn (Single Linked List) : là một loại cấu trúc dữ liệu động, đơn giản và khá thông dụng trong lập trình. Mỗi danh sách bao gồm nhiều phần tử, gọi là node, tạo thành một dãy. Mỗi node có 2 thành phần ch

ính :

  • Thông tin (info) : chứa thông tin cần lưu trữ, đó có thể là
  • các kiểu dữ liệu cơ bản hoặc các kiểu dữ liệu do người dùng tự định nghĩa
  • Liên kết (link) : chứa thông tin kết nối đến một phần tử khác trong danh sách (thường là con trỏ)

Ngoài ra, còn có 2 con trỏ đặc biệt (Head và Tail) dùng để xác định vị trí của phần tử đầu và cuối của danh sách. Phần tử cuối danh sách sẽ trỏ tới hằng null, mang ý nghĩa "kết thúc danh sách".

clip_image002

Ưu và nhược điểm của DSLK đơn

Ưu điểm :

  • Bộ nhớ được cấp phát động : mỗi phần tử trong DSLK chỉ được tạo và cấp phát bộ nhớ khi có yêu cầu từ phía người dùng. Do đó, ta không cần phải biết trước số lượng phần tử cần lưu trữ. Đây chính là điểm yếu của mảng (Array), vì khi sử dụng mảng ta phải xác định trước số phần tử cần lưu trữ (kể cả mảng động)
  • Đối với mảng, khi cấp phát bộ nhớ, cần phải có một dãy các ô nhớ liền kề còn trống. Điều này sẽ gây khó khăn vì không phải lúc nào các ô nhớ còn trống cũng nằm kề nhau. DSLK thì ngược lại, các ô nhớ được cấp phát có thể nằm rời rạc (lộn xộn) trong bộ nhớ. Chỉ cần còn ô nhớ trống là có thể cấp phát.
  • Các thao tác thêm, chèn, xóa được thực hiện dễ dàng hơn trên DSLK, bởi vì chỉ cần thay đổi các liên kết giữa các phần tử. Trong khi đó với mảng, khi thực hiện ta phải dịch chuyển các phần tử liên quan (VD : chèn, xóa,…)

Nhược điểm :

  • Chỉ được phép truy xuất tuần tự. Về phần này thì mảng tiện lợi hơn. Ta có thể truy xuất bất kỳ phần tử nào trong mảng một cách trực tiếp (truy xuất ngẫu nhiên). Còn trong DSLK, ta phải duyệt qua từng phần tử một.
  • Khó cài đặt một số thuật toán tìm kiếm, sắp xếp. Điều này chính là do hạn chế về khả năng truy xuất ngẫu nhiên của DSLK bởi vì các thuật toán tìm kiếm, sắp xếp phải cần tới truy xuất ngẫu nhiên. Tuy nhiên, thuật toán QuickSort và MergeSort lại tỏ ra khá hiệu quả và dễ cài đặt hơn so với trên mảng. Đây là 1 thế mạnh vì đây là 2 thuật toán sắp xếp thông dụng nhất.

Với các ưu nhược điểm trên, có thể thấy rằng DSLK đơn là một cấu trúc khá hay và hiệu quả, tuy nhiên việc cài đặt nó khá dài dòng. Chính vì vậy mà ta phải cân nhắc giữa ưu và nhược điểm của DSLK đơn khi sử dụng. Với các bài toán cần không gian lưu trữ nhỏ, ta nên dùng mảng cho "gọn nhẹ". Còn với các bài toán lớn, cần nhiều không gian bộ nhớ thì DSLK đơn là một lựa chọn "không tồi".

Mở rộng và ứng dụng

Dựa trên DSLK đơn, các nhà lập trình đã phát triển nhiều loại cấu trúc khác phức tạp nhưng hiệu quả hơn như : danh sách liên kết kép (Doubly Linked List), danh sách liên kết xoay vòng (Circular Linked List), cây (Tree),…

Chính tính chất động đã đem lại cho DSLK đơn khá nhiều ứng dụng. Một trong số các ứng dụng quan trọng là dùng để cài đặt Stack, Queue. Ngoài ra còn một số ứng dụng khác.

Cài đặt trong C#

Như đã giới thiệu, mỗi DSLK đơn gồm nhiều node, mỗi node có chứa thông tin và một con trỏ liên kết tới phần tử kế tiếp trong danh sách. Nhưng trong C#, việc dùng con trỏ rất "không an toàn", có thể gây ra những lỗi ngoài tầm kiểm soát nếu cấp phát bộ nhớ không đúng. Tuy nhiên, ta biết rằng trong C#, mọi đối tượng (object) đều là kiểu tham chiếu (reference type). Nghĩa là khi một đối tượng được cấp phát, một con trỏ tới đối tượng này sẽ được tạo ra trong bộ nhớ Stack, còn bản thân nó thì lại được lưu trong bộ nhớ Heap. Điều này cũng tương tự như con trỏ. Do đó ta hoàn toàn có thể cài đặt DSLK đơn bằng C#.

clip_image004

Ở đây, tôi sẽ minh họa bằng việc lưu trữ một dãy các vector và thực hiện các thao tác trên chúng.

Đầu tiên ta sẽ tạo lớp Vector bao gồm các thông tin của một vector :

Code

1. //Lớp vector 2D

2. class Vector

3. {

4. public int X { get; set; } //hoành độ

5. public int Y { get; set; } //tung độ

6. //Hàm khởi tạo

7. public Vector()

8. {

9.         X = Y = 0;

10. }

11. //Hàm khởi tạo overload

12. public Vector(int x, int y)

13. {

14.         X = x;

15.         Y = y;

16. }

17. //Hàm xuất ra chuỗi tọa độ vector

18. public override string ToString()

19. {

20. return string.Format("({0},{1})", X, Y);

21. }

22. //Nạp chồng toán tử so sánh ==

23. public static bool operator ==(Vector A, Vector B)

24. {

25. return (A.X == B.X && A.Y == B.Y);

26. }

27. //Nạp chồng toán tử so sánh !=

28. public static bool operator !=(Vector A, Vector B)

29. {

30. return (A.X != B.X || A.Y != B.Y);

31. }

32. public override bool Equals(object obj)

33. {

34. return base.Equals(obj);

35. }

36. public override int GetHashCode()

37. {

38. return base.GetHashCode();

39. }

40. }

 

Tiếp theo, ta cài đặt lớp Node, đại diện cho một vector trong danh sách. Lớp này bao gồm 2 phần :

  • Phần thông tin : chứa một vector
  • Phần liên kết : chứa một đối tượng kiểu Node (con trỏ tới Node khác)

Code

1. class Node

2. {

3. public static uint Count;           //Số lượng node đã tạo ra

4. public Vector Value { get; set; } //Phần thông tin

5. public Node Next { get; set; } //Phần liên kết

6. //Hàm khởi tạo

7. public Node()

8. {

9.         Value = new Vector();

10.         Next = null;

11.         Count++;

12. }

13. //Hàm khởi tạo nạp chồng (overload)

14. public Node(Vector V)

15. {

16.         Value = V;

17.         Next = null;

18. }

19. //Hàm hủy

20.     ~Node() { Count–; }

21. }

Cuối cùng là lớp SingleLinkedList. Lớp này lưu trữ 2 con trỏ Head và Tail lần lượt trỏ tới phần tử đầu và cuối danh sách. Danh sách rỗng khi Head = Tail = null. Ngoài ra, còn có một số thao tác xử lý trên danh sách. Các thao tác này chủ yếu dựa vào việc thay đổi liên kết giữa các phần tử.

Code

1. class SingleLinkedList

2. {

3. public Node Head { get; set; } //con trỏ Head

4. public Node Tail { get; set; } //con trỏ Tail

5. //hàm khởi tạo mặc định

6. public SingleLinkedList()

7. {

8.         Head = Tail = null;     //khởi tạo danh sách rỗng

9. }

10. //hàm khởi tạo sao chép

11. public SingleLinkedList(SingleLinkedList L)

12. {

13.         RemoveAll();

14.         Node p = L.Head;

15. while (p != null)

16. {

17.             AddTail(p.Value);

18.             p = p.Next;

19. }

20. }

21.     …

22. }

Các thao tác cơ bản trên DSLK đơn

Chèn phần tử vào đầu danh sách :

clip_image006

Code

1. //Hàm thêm vào đầu ds

2. //Trả về true nếu thành công

3. public bool AddHead(Vector V)

4. {

5.     Node p = new Node(V);

6. if (p == null) return false;

7. if (Head == null)

8.         Tail = p;

9. else

10.         p.Next = Head;

11.     Head = p;

12. return true;

13. }

14. //Hàm thêm vào đầu ds

15. //Trả về true nếu thành công

16. public bool AddHead(Node p)

17. {

18. if (p == null) return false;

19. if (Head == null)

20.         Tail = p;

21. else

22.         p.Next = Head;

23.     Head = p;

24. return true;

25. }

Chèn phần tử vào cuối danh sách :

clip_image008

Code

1. //Hàm thêm vào cuối ds

2. //Trả về true nếu thêm thành công

3. public bool AddTail(Vector V)

4. {

5.     Node p = new Node(V);

6. if (p == null) return false;

7. if (Tail == null) Head = p;

8. else Tail.Next = p;

9.     Tail = p;

10. return true;

11. }

Chèn phần tử vào sau một phần tử :

clip_image010

Code

1. //Hàm thêm phần tử vào sau nút q

2. //Trả về true nếu thêm thành công

3. public bool AddAfter(Vector V, Node q)

4. {

5. if (q == null) return AddHead(V);

6. else if (q == Tail) return AddTail(V);

7.     Node p = new Node(V);

8. if (p == null) return false;

9.     p.Next = q.Next;

10.     q.Next = p;

11. return true;

12. }

Xóa phần tử đầu danh sách :

clip_image012

Code

1. //Hàm xóa phần tử đầu ds

2. public void RemoveHead()

3. {

4. if (Head == null) return;

5.     Node p = Head;

6.     Head = p.Next;

7. if (p == Tail) Tail = null;

8.     p = null;

9.     GC.Collect();

10. }

Xóa phần tử đứng sau một phần tử :

clip_image014

Code

1. //Hàm xóa phần tử sau nút q

2. public void RemoveAfter(Node q)

3. {

4. if (q == null) RemoveHead();

5. else if (q == Tail) return;

6. else

7. {

8.         Node p = q.Next;

9.         q.Next = p.Next;

10. if (p == Tail) Tail = q;

11.         p = null;

12.         GC.Collect();

13. }

14. }

Xóa hết danh sách :

Code

1. //Hàm xóa hết phần tử trong list

2. public void RemoveAll()

3. {

4. while (Head != null) RemoveHead();

5. }


Tìm kiếm :

Code

1. //Hàm tìm kiếm phần tử trong danh sách

2. public Node Find(Vector V)

3. {

4.     Node p = Head;

5. while (p != null)

6. {

7. if (p.Value == V) return p;

8.         p = p.Next;

9. }

10. return p;

11. }

Ngoài các thao tác cơ bản trên, bạn có thể cài đặt thêm nhiều hàm khác như nhập, xuất danh sách, sắp xếp, đảo danh sách,…

Lớp SingleLinkedList đầy đủ :

Code

1. class SingleLinkedList

2. {

3. public Node Head { get; set; } //con trỏ Head

4. public Node Tail { get; set; } //con trỏ Tail

5. //hàm khởi tạo mặc định

6. public SingleLinkedList()

7. {

8.         Head = Tail = null;     //khởi tạo danh sách rỗng

9. }

10. //hàm khởi tạo sao chép

11. public SingleLinkedList(SingleLinkedList L)

12. {

13.         RemoveAll();

14.         Node p = L.Head;

15. while (p != null)

16. {

17.             AddTail(p.Value);

18.             p = p.Next;

19. }

20. }

21. //Hàm thêm vào đầu ds

22. //Trả về true nếu thành công

23. public bool AddHead(Vector V)

24. {

25.         Node p = new Node(V);

26. if (p == null) return false;

27. if (Head == null)

28.             Tail = p;

29. else

30.             p.Next = Head;

31.         Head = p;

32. return true;

33. }

34. //Hàm thêm vào đầu ds

35. //Trả về true nếu thành công

36. public bool AddHead(Node p)

37. {

38. if (p == null) return false;

39. if (Head == null)

40.             Tail = p;

41. else

42.             p.Next = Head;

43.         Head = p;

44. return true;

45. }

46. //Hàm thêm vào cuối ds

47. //Trả về true nếu thêm thành công

48. public bool AddTail(Vector V)

49. {

50.         Node p = new Node(V);

51. if (p == null) return false;

52. if (Tail == null) Head = p;

53. else Tail.Next = p;

54.         Tail = p;

55. return true;

56. }

57. //Hàm thêm phần tử vào sau nút q

58. //Trả về true nếu thêm thành công

59. public bool AddAfter(Vector V, Node q)

60. {

61. if (q == null) return AddHead(V);

62. else if (q == Tail) return AddTail(V);

63.         Node p = new Node(V);

64. if (p == null) return false;

65.         p.Next = q.Next;

66.         q.Next = p;

67. return true;

68. }

69. //Hàm xóa phần tử đầu ds

70. public void RemoveHead()

71. {

72. if (Head == null) return;

73.         Node p = Head;

74.         Head = p.Next;

75. if (p == Tail) Tail = null;

76.         p = null;

77.         GC.Collect();

78. }

79. //Hàm xóa phần tử sau nút q

80. public void RemoveAfter(Node q)

81. {

82. if (q == null) RemoveHead();

83. else if (q == Tail) return;

84. else

85. {

86.             Node p = q.Next;

87.             q.Next = p.Next;

88. if (p == Tail) Tail = q;

89.             p = null;

90.             GC.Collect();

91. }

92. }

93. //Hàm xóa hết phần tử trong list

94. public void RemoveAll()

95. {

96. while (Head != null) RemoveHead();

97. }

98. //Hàm tìm kiếm phần tử trong danh sách

99. public Node Find(Vector V)

100. {

101.         Node p = Head;

102. while (p != null)

103. {

104. if (p.Value == V) return p;

105.             p = p.Next;

106. }

107. return p;

108. }

109. //Hàm nhập vector vào danh sách

110. public void Input()

111. {

112.         Console.WriteLine("Nhap cac vector vao danh sach (bo trong de ket thuc)");

113. while (true)

114. {

115.             Console.Write("Nhap toa do (x,y) : ");

116. string line = Console.ReadLine();

117. if (line.Trim() == "") return;

118. string[] xy = line.Trim().Split();

119. if (xy.Length == 2)

120.                 AddTail(new Vector(int.Parse(xy[0]), int.Parse(xy[1])));

121. else

122.                 Console.WriteLine("Vector khong hop le");

123. }

124. }

125. //Hàm xuất danh sách ra màn hình

126. public void Output()

127. {

128.         Node p = Head;

129. while (p != null)

130. {

131.             Console.Write("{0} ",p.Value.ToString());

132.             p = p.Next;

133. }

134.         Console.WriteLine();

135. }

136. }

Hy vọng qua bài viết này, các bạn – những người mới chập chững bước vào môn cấu trúc dữ liệu có thể hiểu được 1 cấu trúc dữ liệu rất hay dùng trong tin học

Các bạn có thể download code tại đây nhưng nhớ là tôn trọng bản quyền bạn nhé Open-mouthed smile

 

Nguyễn Huỳnh Quý Nam

About these ads

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s