PDA

View Full Version : Danh sách liên kết cơ bản | Linked list basic



Kevin Hoang
04-01-2010, 09:34 PM
Lấy từ tài liệu tuyệt vời về linked list của trường ******** mà tôi muốn khái lược lại bằng những đoạn mã trong đó. Danh sách liên kết (linked list) là một kiến thức rất cơ bản của cấu trúc dữ liệu và giải thuật. Hiểu được những ưu và khuyết điểm của nó sẽ giúp chúng ta hiểu các vấn đề về thời gian, không gian bộ nhớ và cấu trúc dữ liệu nói chung. Hơn thế nữa học về linked list là một cách rất tốt để hiểu về pointer. Những bài toán về linked list là sự kết hợp rất “đẹp” giữa giải thuật (algorithms) và các phép toán với con trỏ (pointer manipulation). Linked list là cách các lập trình viên luyện tập để thực sự hiểu về pointer và bạn sẽ thấy ngôn ngữ C “đẹp” vô cùng.

Mục lục:


Linked list basic

Khai báo linked list:
Hàm length() lấy số phần tử của danh sách
Duyệt danh sách sử dụng một con trỏ local


Linked List Building

3 bước để thêm một node vào đầu linked list
Hàm Push()


Techniques

Duyệt xuống (Iterate down)
Đổi một pointer bằng một tham chiếu tới pointer (reference pointer)
Build list sử dụng thêm node vào đầu bằng hàm Push
Build list sử dụng con trỏ tail
Build list sử dụng con trỏ tail có xử lý trường hợp đặc biệt
Build list sử dụng dummy node
Build list sử dụng tham chiếu cục bộ (local references)


Các đoạn mã ví dụ

AppendNode()
AppendNode() sử dụng Push()
CopyList()
CopyList() with Push()
CopyList() With Dummy Node
CopyList() With Local References
CopyList() Recursive


Other implementations



Linked list basic

Khai báo linked list:


struct node {
int data;
struct node* next;
};
struct node* head;

Hàm length() lấy số phần tử của danh sách


/*
Given a linked list head pointer, compute
and return the number of nodes in the list.
*/
int Length(struct node* head) {
struct node* current = head;
int count = 0;
while (current != NULL) {
count++;
current = current->next;
}
return count;
}

Duyệt danh sách sử dụng một con trỏ local


struct node* current = head;
while (current != NULL) {
// do something with *current node
current = current->next;
}

Linked List Building

3 bước để thêm một node vào đầu linked list

Cấp phát vùng nhớ cho node mới

struct node* newNode;
newNode = malloc(sizeof(struct node));
newNode->data = data_client_wants_stored;

Kết nối trường next của node mới vào đầu danh sách
newNode->next = head;

Đưa con trỏ head trỏ vào node mới
head = newNode;

Hàm Push()

Có vẻ từ 3 bước trên thì việc viết hàm Push() để thêm một node vào đầu danh sách rất dễ dàng. Hãy xem hàm sau và tìm chỗ sai trước khi xem lời giải.

void WrongPush(struct node* head, int data) {
struct node* newNode = malloc(sizeof(struct node));
newNode->data = data;
newNode->next = head;
head = newNode;
}

Thực ra sai ở dòng
head = newNode; // NO this line does not work!

Hãy sửa lại hàm Push() trước khi xem tiếp.

/*
Takes a list and a data value.
Creates a new link with the given data and pushes
it onto the front of the list.
The list is not passed in by its head pointer.
Instead the list is passed in as a "reference" pointer
to the head pointer -- this allows us
to modify the caller's memory.
*/
void Push(struct node** headRef, int data) {
struct node* newNode = malloc(sizeof(struct node));
newNode->data = data;
newNode->next = *headRef; // The '*' to dereferences back to the real head
*headRef = newNode;
}

Với C++ thì có hỗ trợ truyền tham chiếu (reference &) vào hàm, nên hàm Push có thể viết như sau với C++

/*
Push() in C++ -- we just add a '&' to the right hand
side of the head parameter type, and the compiler makes
that parameter work by reference. So this code changes
the caller's memory, but no extra uses of '*' are necessary --
we just access "head" directly, and the compiler makes that
change reference back to the caller.
*/
void Push(struct node*& head, int data) {
struct node* newNode = malloc(sizeof(struct node));
newNode->data = data;
newNode->next = head; // No extra use of * necessary on head -- the compiler
head = newNode; // just takes care of it behind the scenes.
}

Techniques

Duyệt xuống (Iterate down)


struct node* current = head;
while (current != NULL) {
/* Do sth here */
current = current->next;
}

Có thể thay vòng lặp bằng
for (current = head; current != NULL; current = current->next) {

Đổi một pointer bằng một tham chiếu tới pointer (reference pointer)

Nhiều hàm cần phải thay đổi con trỏ head mặc dù nó được truyền vào hàm số theo kiểu pass-by-value. Để làm điều này trong C thì hãy truyền một pointer đến head pointer thay vì chỉ truyền head pointer. Kiểu pointer chỉ đến một pointer khác thường được gọi là reference pointer.
Hãy xem hàm ChangeToNull để cho con trỏ head trỏ vào NULL

// Change the passed in head pointer to be NULL
// Uses a reference pointer to access the caller's memory
void ChangeToNull(struct node** headRef) {
// Takes a pointer to the value of interest
*headRef = NULL; // use '*' to access the value of interest
}

Build list sử dụng thêm node vào đầu bằng hàm Push

Phương pháp này làm cho đoạn mã xây dựng list rất ngắn và chạy rất nhanh

struct node* AddAtHead() {
struct node* head = NULL;
int i;
for (i=1; i<6; i++) {
Push(&head, i);
}
// head == {5, 4, 3, 2, 1};
return(head);
}

Build list sử dụng con trỏ tail

Cũng có thể thêm một node mới vào cuối cùng của list. Chúng ta sẽ cần một con trỏ tail trỏ vào node cuối cùng của list và trường next của nó sẽ trỏ vào null. Khi thêm một node mới vào

newNode->next = NULL;
tail->next = newNode;
tail = tail->next;

Tuy nhiên thì có một trường hợp đặc biệt khi phần tử mới thêm vào danh sách là phần tử đầu tiên của list. Hãy xem xét tiếp các kỹ thuật sau.
Build list sử dụng con trỏ tail có xử lý trường hợp đặc biệt

Khi build một danh sách bằng cách thêm một node mới vào cuối danh sách thì điểm khó là node đầu tiên phải được thêm vào head pointer và các node khác thì được thêm vào sau node cuối cùng sử dụng tail pointer. Cách đơn giản nhất để xử lý cả điều này là viết hai đoạn code riêng rẽ xử lý chúng. Đầu tiên là đoạn mã thêm vào head pointer cho phần tử đầu tiên và tiếp đó là một vòng lặp sử dụng tail pointer để thêm tất cả các node khác. Trông nó có vẻ “xấu” nhưng đơn giản và chạy nhanh.

struct node* BuildWithSpecialCase() {
struct node* head = NULL;
struct node* tail;
int i;
// Deal with the head node here, and set the tail pointer
Push(&head, 1);
tail = head;

// Do all the other nodes using 'tail'
for (i=2; i<6; i++) {
Push(&(tail->next), i); // add node at tail->next
tail = tail->next; // advance tail to point to last node
}
return(head); // head == {1, 2, 3, 4, 5};
}

Build list sử dụng dummy node

Một giải pháp khác là sử dụng một dummy node tạm thời ở đầu danh sách. Dummy node sẽ đóng vai trò là phần tử đầu tiên và tất cả các node “thực sự” sẽ được thêm vào sau dummy node.

struct node* BuildWithDummyNode() {
struct node dummy; // Dummy node is temporarily the first node
struct node* tail = &dummy; // Start the tail at the dummy.
// Build the list on dummy.next (aka tail->next)
int i;
dummy.next = NULL;
for (i=1; i<6; i++) {
Push(&(tail->next), i);
tail = tail->next;
}
// The real result list is now in dummy.next
// dummy.next == {1, 2, 3, 4, 5};
return(dummy.next);
}

Ở ví dụ trên ta thấy dummy node sẽ không ở trong list khi ra khỏi hàm. Nhưng có một vài cách thể hiện linked list luôn giữ lại dummy node trong suốt quá trình sử dụng nó. Với cách tiếp cận đó thì sẽ không bao giờ có một danh sách rỗng (empty list). Thay vì đó thì danh sách luôn có một dummy node ở đầu. Tuy nhiên thì tôi không khuyến khích phương pháp tiếp cận đó. Phương án sử dụng dummy node tạm thời nên được sử dụng hơn.
Build list sử dụng tham chiếu cục bộ (local references)

Cuối cùng đây là một giải pháp rất “mẹo mực” mà không phải sự dụng dummy node. Đó là sử dụng một local “reference pointer” mà luôn trỏ vào pointer cuối cùng của list chứ không phải node cuối cùng.

struct node* BuildWithLocalRef() {
struct node* head = NULL;
struct node** lastPtrRef= &head; // Start out pointing to the head pointer
int i;
for (i=1; i<6; i++) {
Push(lastPtrRef, i); // Add node at the last pointer in the list
lastPtrRef= &((*lastPtrRef)->next); // Advance to point to the
// new last pointer
}
// head == {1, 2, 3, 4, 5};
return(head);
}

Kỹ thuật này rất ngắn nhưng bên trong vòng lặp thật “kinh hoàng”.
Cả hai giải pháp sử dụng temporary-dummy và reference pointer có hơi chút “không bình thường” nhưng nó rất tốt để chắc chắn rằng chúng ta hiểu về pointer bởi vì chúng sử dụng pointer theo cách “không bình thường”.
Các đoạn mã ví dụ

AppendNode()


struct node* AppendNode(struct node** headRef, int data) {
struct node* current = *headRef;
struct node* newNode;
newNode = malloc(sizeof(struct node));
newNode->data = data;
newNode->next = NULL;

// special case for length 0
if (current == NULL) {
*headRef = newNode;
} else {
// Locate the last node
while (current->next != NULL) {
current = current->next;
}
current->next = newNode;
}
}

AppendNode() sử dụng Push()


struct node* AppendNode(struct node** headRef, int data) {
struct node* current = *headRef;
// special case for the empty list
if (current == NULL) {
Push(headRef, data);
} else {
// Locate the last node
while (current->next != NULL) {
current = current->next;
}
// Build the node after the last node
Push(&(current->next), data);
}
}

CopyList()


struct node* CopyList(struct node* head) {
struct node* current = head; // used to iterate over the original list
struct node* newList = NULL; // head of the new list
struct node* tail = NULL; // kept pointing to the last node in the new list
while (current != NULL) {
if (newList == NULL) { // special case for the first new node
newList = malloc(sizeof(struct node));
newList->data = current->data;
newList->next = NULL;
tail = newList;
} else {
tail->next = malloc(sizeof(struct node));
tail = tail->next;
tail->data = current->data;
tail->next = NULL;
}
current = current->next;
}
return(newList);
}

CopyList() with Push()


// Variant of CopyList() that uses Push()
struct node* CopyList2(struct node* head) {
struct node* current = head; // used to iterate over the original list
struct node* newList = NULL; // head of the new list
struct node* tail = NULL; // kept pointing to the last node in the new list
while (current != NULL) {
if (newList == NULL) { // special case for the first new node
Push(&newList, current->data);
tail = newList;
} else {
Push(&(tail->next), current->data); // add each node at the tail
tail = tail->next; // advance the tail to the new last node
}
current = current->next;
}
return(newList);
}

CopyList() With Dummy Node


// Dummy node variant
struct node* CopyList(struct node* head) {
struct node* current = head; // used to iterate over the original list
struct node* tail; // kept pointing to the last node in the new list
struct node dummy; // build the new list off this dummy node
dummy.next = NULL;
tail = &dummy; // start the tail pointing at the dummy
while (current != NULL) {
Push(&(tail->next), current->data); // add each node at the tail
tail = tail->next; // advance the tail to the new last node
current = current->next;
}
return(dummy.next);
}

CopyList() With Local References


// Local reference variant
struct node* CopyList(struct node* head) {
struct node* current = head; // used to iterate over the original list
struct node* newList = NULL;
struct node** lastPtr;
lastPtr = &newList; // start off pointing to the head itself
while (current != NULL) {
Push(lastPtr, current->data); // add each node at the lastPtr
lastPtr = &((*lastPtr)->next); // advance lastPtr
current = current->next;
}
return(newList);
}

CopyList() Recursive


// Recursive variant
struct node* CopyList(struct node* head) {
if (head == NULL) return NULL;
else {
struct node* newList = malloc(sizeof(struct node)); // make the one node
newList->data = current->data;
newList->next = CopyList(current->next); // recur for the rest
return(newList);
}
}

Other implementations

Hãy tham khảo thêm trong tài liệu
Dummy header
Circular
Tail pointer
Head struct
Doubly-linked
Chunk list
Dynamic array


Tài liệu được cung cấp bởi Hoang Tran(openandfree.org)

vncoder
19-10-2011, 10:18 PM
cho mình hỏi làm sao *next có thể hoạt động đc nhỉ? làm sao nó lại trỏ đến phần tử tiếp theo đc? xon giải thích giúp

struct node
{
int info;
struct node *next;
};

treatmaster
19-10-2011, 11:08 PM
cho mình hỏi làm sao *next có thể hoạt động đc nhỉ? làm sao nó lại trỏ đến phần tử tiếp theo đc? xon giải thích giúp

struct node
{
int info;
struct node *next;
};

bạn hiểu cấu trúc của một node trên ko.rồi con trỏ là gì.nếu hiểu thì chả có gì để nói nữa.

vncoder
20-10-2011, 12:13 AM
bạn hiểu cấu trúc của một node trên ko.rồi con trỏ là gì.nếu hiểu thì chả có gì để nói nữa.

theo mình nghĩ node là 1 cái nút gì đó để liên kết , còn con trỏ để lưu địa chỉ của 1 biến ,khi trỏ tới mảng thì trỏ vào cái đầu tiên .
và rồi mình có hiểu đâu

treatmaster
20-10-2011, 12:37 AM
thế bạn có biết toa tàu ko.có phải bên trong toa tàu là để chứa đồ, còn ở ngoài nó có 1 cái rơ móc để nối với cái toa khác.


struct Node // toa tàu
{
data info ; // tương tự như hàng hóa trong toa tàu
Node *pNext ; // cái rơ móc để nối vs toa khác, con trỏ trỏ tới node kế tiếp
}

fithou91192
01-11-2011, 10:16 AM
ta dùng *next để trỏ tới node tiếp theo .vậy các anh cho em hỏi *p<=>*current dùng để làm gì và ý nghĩa của nó là gì vậy? em không hiểu cho lắm
(D:)>

vipbk09
18-08-2012, 06:43 AM
1. Link để download ebook "Linked list basic" của đại học ********: _http://cslibrary.********.edu/103/LinkedListBasics.pdf

2. Em có thắc mắc sau:

Giả sử em khai báo 1 struct:


struct node
{
int data;
struct node* next;
}


Khai báo: struct node* next khác gì so với: struct node *next

Mong mọi người chỉ giáo.

quyld
26-09-2012, 02:23 PM
Theo mình thì hai cách khai báo đó đều đúng, và chúng không khác nhau gì cả

vipnho0209
09-05-2013, 04:18 PM
cho mình hỏi làm sao *next có thể hoạt động đc nhỉ? làm sao nó lại trỏ đến phần tử tiếp theo đc? xon giải thích giúp

struct node
{
int info;
struct node *next;
};

hi , thực ra là khai báo kiểu dữ liệu mới tên node gồm 2 thành phần: 1-chứa thông tin dữ liệu "info" 2-khai báo 1 con trỏ trỏ vào 1 node
tại sao struct node *next lại trỏ vào đc node tiếp theo : vì cái trường con trỏ next này chứa địa chỉ của node tiếp theo, và muốn xác định đựoc node tiếp theo đó thì người ta dựa vào con trỏ next đó ( thông qua giá trị mà next chứa ) => nên người ta gọi là nó trỏ đến node tiếp theo cũng gần giống như việc 1 con trỏ int* p, a = 10; p = &a; => lúc này p chứa địa chỉ biến a nên nói p trỏ vào a :)

Mình hiểu là như vậy :)

ANHMATTROI
10-05-2013, 02:37 PM
mình thì lại chẳng cần hiểu cứ code lên chạy là được rồi

prog10
10-05-2013, 05:31 PM
mình thì lại chẳng cần hiểu cứ code lên chạy là được rồi
Hóa ra là vậy, toàn thấy dùng Interchange Sort :|

khac.y.win
19-11-2016, 03:14 PM
while (current != NULL) {
count++;
current = current->next;
}
chỗ current=current->next là trỏ tới vị trí tiếp theo nhưng cách hoạt động của nó là gì vậy????

prog10
19-11-2016, 06:18 PM
while (current != NULL) {
count++;
current = current->next;
}
chỗ current=current->next là trỏ tới vị trí tiếp theo nhưng cách hoạt động của nó là gì vậy????
Code này duyệt toàn bộ DSLK, rất cơ bản :)

Con trỏ next trỏ tới node tiếp theo nên cứ hiểu là nó qua node mới là đc.

bachgist
20-11-2016, 10:26 PM
Trong một Nút có: Giá trị của nó và ĐỊA CHỈ của Nút khác (ví dụ như: địa chỉ số nhà của ai đó chẳng hạn)
.
Giờ bạn phải đi thăm tất cả các Nút.
Hiện tại bạn đang đứng thăm ở Nút current. Vậy làm sao để đi thăm tiếp nhà khác đây ?.
Ồ, tại vị trí bạn đang đứng là Nút, đang có 1 thông tin next là ĐỊA CHỈ của Nút khác. Khà khà. Giờ ta vào thăm Nút mới này thôi. Và đương nhiên current = current->next (tôi đi vào cái Địa chỉ của ai đó mà tôi đang có)