Đang cập nhật

Nội Dung

1. Giới Thiệu
2. Phương Pháp
2.1 Node
2.2 Danh Sách Liên Kết
2.2.1 Danh Sách Liên Kết Đơn
2.2.2 Danh Sách Liên Kết Kép
2.2.3 Danh Sách Liên Kết Vòng

I. DANH SÁCH LIÊN KẾT

    Danh sách liên kết được phát triển từ 1955-1956 bởi Allen Newell , Cliff Shaw và Herbert A. Simon tại RAND Corporation giống như chính cấu trúc dữ liệu cho họ Information Processing Language. IPL đã được sử dụng bởi các tác giả để phát triển một số chương trình trí tuệ nhân tạo, bao gồm cả Logic Máy Lý thuyết, các General Problem Solver, và một chương trình cờ vua máy tính. Báo cáo về công việc của họ xuất hiện trong giao dịch IRE trên Lý thuyết thông tin trong năm 1956, và một số biên bản hội nghị 1957-1959, bao gồm Kỷ yếu của Hội thảo Máy tính phần phương Tây trong năm 1957 và 1958, và xử lý thông tin (Kỷ yếu đầu tiên UNESCO Hội nghị quốc tế về xử lý thông tin ) trong năm 1959. Sơ đồ bây giờ cổ điển bao gồm các khối đại diện cho danh sách các nút mũi tên trỏ đến các nút trong danh sách, xuất hiện trong "Lập trình Logic Lý thuyết máy" của Newell và Shaw trong Proc. WJCC, tháng 2 năm 1957. Newell và Simon đã được công nhận với ACM Turing Award vào năm 1975 vì đã "có những đóng góp cơ bản cho trí tuệ nhân tạo, tâm lý của nhận thức con người, và xử lý danh sách". Các vấn đề của máy dịch thuật cho ngôn ngữ tự nhiên , chế biến dẫn Victor Yngve tại Viện Công nghệ Massachusetts (MIT) để sử dụng danh sách liên kết như cấu trúc dữ liệu trong ngôn ngữ lập trình COMIT mình cho nghiên cứu máy tính trong lĩnh vực ngôn ngữ học . Một báo cáo về ngôn ngữ này mang tên "Một ngôn ngữ lập trình cho dịch cơ" xuất hiện trong Cơ dịch trong năm 1958.

1. Giới Thiệu
- Danh sách liên kết (Linked list) là một cấu trúc dữ liệu (Data Structeres) bao gồm tập hợp các nút (Node) mà chúng cùng nhau đại diện cho một chuỗi. Trong đó mỗi nút bao gồm một phần dữ liệu và phần kia à liên kết đến nút kế tiếp trong chuỗi. DSLK có nhiều biến thể như: DSLK đơn, DSLK Kép (đôi), DSLK Vòng . . . . .

- Danh sách liên kết là một trong những cấu trúc dữ liệu đơn giản và phổ biến. Chúng có thể được sử dụng để thực hiện một số phổ biến như: kiểu dữ liệu trừu tượng(the abstract data type), ngăn xếp (Stacks), hàng đợi (Queues) . . . .

2. Phương Pháp
2.1 Node
- Phương pháp của cách tổ chức dữ liệu này thì mỗi phần tử của danh sách được lưu trữ trong một ô nhớ mà ta tạm gọi ở đây là Node. Về cơ bản mỗi Node sẽ có hai trường như sau:

Value: Chứa giá trị của phần tử node đó
Next: Địa chỉ Node kế tiếp

- Riêng Node cuối cùng sẽ không có địa chỉ Node tiếp theo nữa nên ta tạm gán cho Next của Node này là Null
- Muốn truy cập vào danh sách bạn cần phải biết được Node đầu tiên, hoặc cuối (dslk kép) dựa vào đó mới có thể truy xuất các Node tiếp theo và các Node này có thể nằm mọi nơi trên bộ nhớ.

2.2 Danh Sách Liên Kết
Danh sách này chúng ta dùng nó để chứa các Node ở trên, về cơ bản ta có hai trường cần xây dựng tại class này là: Node đầu, Node cuối để nhận dạng vị trí đầu cuối của danh sách.

Hình trên mô tả danh sách chứa các Node, ta chỉ quan tâm tới Node đầu và cuối còn các nút ở giữa thì bao nhiều cũng ko cần quan tâm

2.2.1 Danh Sách Liên Kết Đơn

A singly linked list

Ở hình trên:

- Từ 2.1 và 2.2 để khởi tạo một danh sách liên kết đơn bạn chỉ cần nhớ hai điều chúng ta cần làm:
+ Xây dựng class Node, dùng để khởi tạo các Node
+ Xây dựng class LikedList, dùng để chứa các Node trên
=>Vậy ta đã có một danh sách liên kết dùng để chứa các Node, việc còn lại là viết các hàm thao tác với danh sách.
- Nhưng danh sách dùng chứa các Node, mà các Node này lưu trữ dữ liệu gì ?
Ở đây ta xây dựng class sinhvien, mỗi sinh viên có các thuộc tính: MaSv, HoTen, DiaChi, DienThoai
Bây giờ lưu thông tin mỗi sinh viên vào một Node, bạn phải chú ý rằng trong một Node gồm 2 trường (một lưu thông tin SV, một lưu liên kết SV kế tiếp, và Node cuối sẽ có trường liên kết là NULL)
Xây dựng code cho lớp node
- Chúng ta cần xây dựng 2 lớp: Node Và Danh sách chứa các Node đó. Trước tiên chúng ta sẽ xây dưng lớp Node
public class Node
{
public int Value {get; private set}
public Node Next {get; set;}
public Node(int value)
{
this.Value =value;
}
}
Xây dựng code cho lớp danh sách

public class LinkedList
{
public Node First {get; private set;}
public Node Last {get; private set;}
public int Count {get; private set;}

// Xây dựng các hàm AddFirst, AddLast, RemoveFirst, RemoveLast, Find, Clear. . . . tại đây
}

Xây dựng code cho lớp Sinh Viên

public class Student
{
public int Id {get; private set;}
public string FullName {get; private set;}
public string Address {get; private set;}
public string PhoneNumber {get; private set;}

public Student(int id, string fullname, string address, string phonenumber)
{
this.Id = id;
this.FullName = fullname;
this.Address = address;
this.PhoneNumber = phonenumber;
}

public string PrintInfo()
{
return this.Id.ToString() + ‘\t’
+ this.FullName + ‘\t’ + ‘\t’
+ this.Address + ‘\t’ + ‘\t’
+ this.PhoneNumber
}
}

2.2.2 Danh Sách Liên Kết Kép

- Trong liên kết kép, thì một Node ngoài có các trường như liên kết đơn còn có
thêm trường liên kết tới Node đằng trước nó. Hai node First và Last sẽ có giá trị như dưới hình.

A doubly linked list
Xây dựng code cho lớp Node
public class Node
{
public SinhVien Value {get; private set;}
public Node Next {get; set;}
public Node Previous {get; set;}
public Node(SinhVien value)
{
this.Value = value;
}
}
Xây dựng code cho lớp LinkedList
public class LinkedList
{
public Node First {get; set;}
public Node Last {get; set;}
public int Count {get; set;}
// Các hàm thao tác với danh sách bạn xây dựng ở đây
}

2.2.3 Danh Sách Liên Kết Vòng

A circular linked list

Đang cập nhật . . .

---

[TLM1]Bảng này đưa ra cái nhìn tổng quan về ưu và nhược điểm của hai kiểu cấu trúc dữ liệu ở bên.
Dấu Tick tức là loại đó có Ưu/Nhược điểm như thể và ngược lại
[TLM2]Cơ bản ở đây là dslk đơn nếu là dslk kép sẽ có thêm trường địa chỉ Previous
[TLM3]Giá trị này của dữ liệu trong bài này, chúng ta sẽ thiết lập mặc định lúc xây dựng code. Tức là người dùng có thể tùy biến nó, họ muốn kiểu int, string hoặc đối tượng SinhVien . . . thì có thể nhập vào. Sẽ thấy rõ trong demo bên dưới
[TLM4]Trường này của node sẽ lưu địa chỉ Node kế tiếp
[TLM5]Trường (field) chứa dữ liệu
[TLM6]Trường chứa link tới Node kế tiếp
[TLM7]Đây là Constructor của class Node.
Chúng ta chỉ cần xây dựng giá trị cho trường Value, trường Next sẽ được SET trong class LinkedList !

[TLM8]Trường này dùng để xác định Node đầu tiên trong danh sách
[TLM9]Tương tự trường này dùng để xác định Node cuối cùng trong danh sách
[TLM10]Trường này là biến đếm số Node có trong danh sách
[TLM11]Các hàm này ta sẽ tham khảo code đi kèm Source. Các hàm này đơn giản là thêm mới node, tìm kiếm, xóa node, xuất ra danh sách . . .và một số hàm theo yêu cầu bài toán.
[TLM12]Nếu gán private ở đây thì quyền SET chỉ thực hiện được trong class mà cụ thể là Constructor
[TLM13]Bốn trường này là thuộc tính của một sinh viên, chúng ta cần lưu thông tin một sinh viên vào một node
[TLM14]Constructor này dùng để SET giá trị cho các trường của class SinhVien
[TLM15]Riêng DSLK Kép chỉ thêm trường liên kết tới Node đằng trước node đó. Cũng tương tự hai trường liên kết tới hai node trước và sau sẽ được SET tại class LikedList

---

PDF:

Read now

SRC:
Download 

Danh Sách Liên Kết - Data Structures

Related Tags :
WritingObsolete