Cấu trúc dữ liệu của danh sách liên kết đơn

Posted on Updated on by adminChuyên mục:Kiến thức Internet

Trong hướng dẫn này mình sẽ giới thiệu đến các bạn danh sách liên kết đơn là gì, cũng như cấu trúc dữ liệu của nó và cách khai báo danh sách.

test php

banquyen png

Bài viết này được đăng tại

freetuts.net

, không được copy dưới mọi hình thức.

Danh sách liên kết đơn là loại DSLK đơn thuần và dễ thiết lập nhất trong 3 loại mà tất cả chúng ta sẽ học trong series cấu trúc tài liệu. Để hiểu được nó thì bạn phải có kỹ năng và kiến thức nền tảng C + + hoặc C nhé .

1. Danh sách liên kết đơn là gì?

Danh sách liên kết đơn là một cấu trúc tài liệu động sử dụng con trỏ để setup và trỏ đến những thành phần trong danh sách .

Trong DSLK đơn thì mỗi phần tử sẽ liên kết với phần tử đứng sau nó trong danh sách, ta gọi là các phần tử đó là Node. Mỗi node có hai thông số cần quan tâm, đó là:

  • Giá trị (data)
  • Mối liên kết tới node khác (pNext).

dslk don la gi PNG

Như hình trên, ở node thứ hai có liên kết với node thứ nhất trải qua pNext, tựa như như vậy node thứ ba liên kết với node thứ hai cũng trải qua pNext .

2. Cấu trúc dữ liệu của DSLK đơn – quản lý bằng pHead

Trong danh sách liên kết đơn ta có mỗi thành phần liên kết với thành phần đứng sau nó trong danh sách. Mỗi thành phần gồm một Node và mỗi Node có hai thông tin : Giá trị ( data ) và con trỏ pNext trỏ tới thành phần tiếp nối .
Ở phần này tất cả chúng ta sẽ quản trị danh sách liên kết bằng 1 con trỏ pHead ( trỏ tới thành phần đầu ) .

Ví dụ: ta có một danh sách liên kết đơn sử dụng pHead để quản lý

dslk don 2 PNG

Trong danh sách ta cần xác lập những thông tin sau :

  • pHead là Node đầu của danh sách liên kết đơn.
  • Các giá trị 8, 9, 5 phía bên trái gạch đỏ là giá trị (data) của Node.
  • pNext là con trỏ, trỏ đến phần tử sau.

Dựa vào những thông tin trên, ta có cấu trúc tài liệu sử dụng pHead để quản trị :

/* Khai báo giá trị data và con trỏ pNext trỏ tới phần tử kế tiếp */
struct Node
{
  int data;// giá trị data của node
  Node *pNext;// con trỏ pNext
};
/* Khai báo Node đầu pHead */
struct SingleList
{
  Node *pHead; //Node đầu pHead
};
/* khởi tạo giá trị cho Node */
void Initialize(SingleList &list)
{
  list.pHead=NULL;// khởi tạo giá trị cho Node là Null
}

Như vậy là tất cả chúng ta đã khai báo những thông tin có trong một danh sách liên kết đơn sử dụng pHead để quản trị .

3. Cấu trúc dữ liệu của DSLK đơn – quản lý bằng pHead và pTail

Về cơ bản việc sử dụng pHead và pTail để quản trị DSLK đơn tựa như như việc sử dụng pHead. Tuy nhiên khi tất cả chúng ta sử dụng pHead và pTail thì việc insertLast ( ) sẽ rất thuận tiện và thuận tiện .
Minh họa danh sách liên kết đơn sử dụng 2 con trỏ pHead và pTail. pHead luôn luôn quản trị node đầu, pTail luôn luôn quản trị node cuối .

cau truc du lieu pheadandptail PNG

Ta có pHead quản trị Node đầu và pTail quản trị Node cuối, vì thế khi khai báo ở cấu trúc SingleList ( ) tất cả chúng ta sẽ khai báo cả pHead và pTail .

/* Khai báo Node đầu pHead và Node cuối pTail*/
struct SingleList
{
  Node *pHead; //Node đầu pHead
  Node *pTail; // Node cuối pTail
};

Cũng như khi khởi tạo giá trị, thì tất cả chúng ta sẽ phải khởi tạo cho cả pHead và pTail bằng Null .

void Initialize(SingleList &list)
{
  list.pHead=list.pTail=NULL;// khởi tạo giá trị cho Node đầu và Node cuối là Null
}

Full code: cấu trúc dữ liệu trong DSLK đơn

/* Khai báo giá trị data và con trỏ pNext trỏ tới phần tử kế tiếp */
struct Node
{
  int data;// giá trị data của node
  Node *pNext;// con trỏ pNext
};
/* Khai báo Node đầu pHead và Node cuối pTail*/
struct SingleList
{
  Node *pHead; //Node đầu pHead
  Node *pTail; // Node cuối pTail
};
/* khởi tạo giá trị cho Node đầu và Node cuối */
void Initialize(SingleList &list)
{
  list.pHead=list.pTail=NULL;// khởi tạo giá trị cho Node đầu và Node cuối là Null
}

Việc sử dụng pHead và pTail có ưu điểm là không cần phải duyệt DSLk khi insertLast, nhưng bù lại điểm yếu kém của nó sẽ tốn bộ nhớ để khởi tạo biến pTail. Vì vậy những bạn hãy kiểm soát và điều chỉnh việc sử dụng hai cách quản trị này cho tương thích với bài toán .

Kết luận

Trong bài viết này mình đã ra mắt về danh sách liên kết đơn và cấu trúc tài liệu của nó. Ở bài tiếp theo tất cả chúng ta sẽ cùng nhau triển khai tạo Node trong danh sách liên kết đơn. Các bạn hãy quan tâm theo dõi nhé .

admin