Lập trình

Lập trình

Thứ Bảy, 21 tháng 11, 2015

Một ví dụ về link list trong c++

Chào các bạn hôm nay mình có một ví dụ về link list theo mình thấy khá hay :)

Ta có một structure sau :

struct NODE{
int _data;
NODE* _next;
};


và đoạn code :

        NODE* head = new NODE;
NODE* tail = head;

head = NULL;

NODE* newNode = new NODE;
newNode->_data = 3;
newNode->_next = head;
head = newNode;

tail = head;

newNode->_data = 4;
newNode->_next = tail->_next;

tail->_next = newNode;


và khi debug trên visual C++ thì ra một kết quả khá hay : trong list do head quản ly có vô số các NODE khác nhau và đều có data = 4 và con trỏ _next thì có giá trị chính bằng địa chỉ trong head tức và nó trỏ vào đầu list.




Chúng ta cùng phân tích :

Ta có các bức ảnh miêu tả các bước thực hiện :


Bước 1
        NODE* head = new NODE;
NODE* tail = head;
   
Biến head được khai báo và cho ô nhớ bên stack, sau đó được cấp phát bên heap, tail tương tự.


Bước 2
        head = NULL;


NODE* newNode = new NODE;
newNode->_data = 3;
newNode->_next = head;

Bước 3
       head = newNode;


tail = head;

newNode->_data = 4;
newNode->_next = tail->_next;
        tail->_next = newNode;




Bây giớ ta đã thấy bản chất của vấn đề : 3 con trỏ head, tail, newNode đều trỏ hay quản lý cùng một vùng nhớ, cái mà ban đầu được cấp phát cho newNode. Và sau đó qua một vài bước next ponter chưa luôn địa chỉ của vùng nhớ đó hay nói cách khác nó trỏ luôn vào vùng nhớ đang chứa chính nó. Điều này như là đệ quy, đây là lý do tại sao trong 3 con trỏ head, tail, newNode quản lý vúng nhớ gồm vô số các phần tử giống nhau và fied next pointer của nó lại là địa chỉ của vùng nhớ mà 3 con trỏ này quản lý.

Hi vọng bug trên giúp ích cho các bạn. Cảm ơn các bạn :)

Không có nhận xét nào:

Đăng nhận xét