Danh sách liên kết đơn trong ngôn ngữ lập trình C/C++
Về bản chất thì danh sách liên kết đơn có chức năng giống như một mảng nhưng nó có nhiều ưu điểm hơn so với mảng. Để làm việc với danh sách liên kết đơn, trước tiên các bạn cần phải nắm rõ các kiến thức về con trỏ vì danh sách liên kết có sử dụng con trỏ khá nhiều. Nếu các bạn chưa hiểu rõ về con trỏ thì hãy tham khảo bài viết về con trỏ trong ngôn ngữ lập trình C/C++ của Isinhvien trước khi đọc bài này nhé!
Biễu diễn danh sách liên kết đơn
Các phần tử trong danh sách liên kết đơn được kết nối với nhau nhớ các vùng liên kết, chỉ có sự kết nối giữa phần tử phía trước với phần tử phía sau.
Đầu tiên, ta phải khởi tạo một kiểu bản ghi (struct) sẽ gồm có dữ liệu và trường liên kết để liên kết đến phần tử đứng sau nó. Ở ví dụ dưới đây, Isinhvien sẽ khai báo một bản ghi với dữ liệu đơn giản kiểu int và con trỏ *next để trỏ đến phần tử tiếp theo.
struct element
{
int data;
element *next;
};
typedef element *List;
List F; // hoặc element *F;
Trong đó:
- Kiểu con trỏ List dùng để chỉ đến một phần tử kiểu element.
- Biến con trỏ F luôn luôn chỉ đến phần tử đầu tiên trong danh sách liên kết.
Xem hình ảnh minh họa dưới đây để dễ hiểu hơn nhé!
Các phép toán trên danh sách liên kết đơn
1. Khởi tạo danh sách liên kết đơn
Khi mới khởi tạo danh sách là rỗng ta cho F nhận giá trị NULL.
void Create(List &F)
{
F=NULL;
}
2. Liệt kê phần tử trong danh sách
Ta liệt kê các phần tử kể từ phần tử đầu tiên được chỉ bởi biến con trỏ F và dựa vào trường liên kết next để lần lượt liệt kê các phần tử tiếp theo. Biến con trỏ p lần lượt chỉ đến từng phần tử trong danh sách bắt đầu từ phần tử đầu tiên chỉ bởi F trở đi
void Display(List F)
{
List p;
p=F;
while (p != NULL)
{
cout << (*p).data;
p=(p).next;
}
}
3. Thêm một phần tử vào đầu danh sách
Thêm một phần tử có data = x vào đầu danh sách đang có, biến con trỏ p chỉ đến phần tử mới cần thêm vào, sau đó trả lại phần tử ban đầu của danh sách liên kết cho F.
void InsertFirst(List &F, int x) {
List p;
p=new element;
(*p).data=x;
(p).next=F;
F=p;
}
4. Thêm một phần tử vào danh sách đã có thứ tự
Thêm một phần tử có data=x vào danh sách trước đó đã có thứ tự tăng dần. Biến con trỏ p chỉ đến phần tử mới cần thêm vào, các biến con trỏ before và after lần lượt chỉ đến phần tử đứng ngay trước và ngay sau phần tử mới. Để tìm after thì ta tìm bắt đầu từ phần tử đầu tiên chỉ bởi F trở đi cho đến khi gặp được phần tử đầu tiên có họ tên lớn hơn x thì dừng, rồi chèn phần tử mới vào.
void InsertSort(List &F, int x)
{
List p, before, after;
p=new element; (*p).data=x;
after=F;
while ( (after!=NULL) && ((*after).data<x ) )
{
before=after;
after=(*after).next;
}
(*p).next=after;
if (F==after) F=p;
else (*before).next=p;
}
5. Xóa một phần tử ở đầu danh sách
Biến con trỏ p chỉ đến phần tử cần xóa. Ta cho F chỉ đến phần tử tiếp theo.
void DeleteFirst(List &F)
{
List p;
if (F!=NULL)
{
p=F;
F=(*p).next;
delete p;
}
}
6. Xóa phần tử trỏ bởi biến con trỏ nào đó
Biến con trỏ before chỉ đến phần tử đứng ngay trước phần tử cần xóa, biến con trỏ after chỉ đến phần tử đứng ngay sau phần tử chỉ bởi biến before.
void DeleteElement(List &F, List t)
{
List before, after;
after=F;
while ( ( after!=NULL) && (after!=t) )
{
before = after;
after=(*after).next;
}
if (after!=NULL)
{
if (F==t) F=(*t).next;
else (*before).next=(*t).next;
delete t;
}
}
7. Tìm kiếm một phần tử trong danh sách
Ta tìm bắt đầu từ phần tử đầu tiên được chỉ bởi F trở đi cho đến khi tìm được phần tử cần tìm hoặc đã kiểm tra xong phần tử cuối cùng mà không có thì dừng. Hàm Search(F, x) kiểu List, tìm và trả về địa chỉ của phần tử đầu tiên tìm được hoặc trả về giá trị NULL nếu tìm không có.
List Search(List F, int x)
{
List p;
p=F;
while ( (p!=NULL) && (*p).data !=x )
{
p= (*p).next;
}
return p;
}
Cảm ơn các bạn đã theo dõi bài viết trên của Isinhvien. Hy vọng bài viết này sẽ giúp đỡ cho các bạn phần nào trong công việc cũng như trong học tập. Nhớ theo dõi Isinhvien để cập nhật thêm nhiều kiến thức mỗi ngày nhé, chúc các bạn thật nhiều sức khỏe và thành công trong cuộc sống!
