Công cụ bảo vệ mã nguồn .NET mạnh nhất, không thể unpack, miễn phí cho các khách hàng đầu tiên đăng ký.
Trang 1 trên tổng số 2 12 Cuối cùngCuối cùng
Từ 1 tới 10 trên tổng số 14 kết quả

Đề tài: Danh sách liên kết cơ bản | Linked list basic

  1. #1
    Ngày gia nhập
    07 2006
    Nơi ở
    Hanoi, Vietnam
    Bài viết
    2,750

    Mặc định Danh sách liên kết cơ bản | Linked list basic

    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:

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

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

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

    4. Các đoạn mã ví dụ
      1. AppendNode()
      2. AppendNode() sử dụng Push()
      3. CopyList()
      4. CopyList() with Push()
      5. CopyList() With Dummy Node
      6. CopyList() With Local References
      7. CopyList() Recursive

    5. Other implementations



    Linked list basic

    Khai báo linked list:

    C Code:
    1. struct node {
    2.      int data;
    3.      struct node* next;
    4. };
    5. struct node* head;

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

    C Code:
    1. /*
    2.  Given a linked list head pointer, compute
    3.  and return the number of nodes in the list.
    4. */
    5. int Length(struct node* head) {
    6.     struct node* current = head;
    7.     int count = 0;
    8.     while (current != NULL) {
    9.         count++;
    10.         current = current->next;
    11.     }
    12.     return count;
    13. }

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

    C Code:
    1. struct node* current = head;
    2. while (current != NULL) {
    3.     // do something with *current node
    4.     current = current->next;
    5. }

    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
    C Code:
    1. struct node* newNode;
    2. newNode = malloc(sizeof(struct node));
    3. 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.
    C Code:
    1. void WrongPush(struct node* head, int data) {
    2.      struct node* newNode = malloc(sizeof(struct node));
    3.      newNode->data = data;
    4.      newNode->next = head;
    5.      head = newNode;
    6. }

    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.
    C Code:
    1. /*
    2. Takes a list and a data value.
    3. Creates a new link with the given data and pushes
    4. it onto the front of the list.
    5. The list is not passed in by its head pointer.
    6. Instead the list is passed in as a "reference" pointer
    7. to the head pointer -- this allows us
    8. to modify the caller's memory.
    9. */
    10. void Push(struct node** headRef, int data) {
    11.      struct node* newNode = malloc(sizeof(struct node));
    12.      newNode->data = data;
    13.      newNode->next = *headRef; // The '*' to dereferences back to the real head
    14.      *headRef = newNode;          
    15. }

    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++
    C++ Code:
    1. /*
    2.  Push() in C++ -- we just add a '&' to the right hand
    3.  side of the head parameter type, and the compiler makes
    4.  that parameter work by reference. So this code changes
    5.  the caller's memory, but no extra uses of '*' are necessary --
    6.  we just access "head" directly, and the compiler makes that
    7.  change reference back to the caller.
    8. */
    9. void Push(struct node*& head, int data) {
    10.      struct node* newNode = malloc(sizeof(struct node));
    11.      newNode->data = data;
    12.      newNode->next = head; // No extra use of * necessary on head -- the compiler
    13.      head = newNode; // just takes care of it behind the scenes.
    14. }

    Techniques

    Duyệt xuống (Iterate down)

    C Code:
    1. struct node* current = head;
    2. while (current != NULL) {
    3.      /* Do sth here */
    4.      current = current->next;
    5. }

    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
    C Code:
    1. // Change the passed in head pointer to be NULL
    2. // Uses a reference pointer to access the caller's memory
    3. void ChangeToNull(struct node** headRef) {
    4.      // Takes a pointer to the value of interest
    5.      *headRef = NULL; // use '*' to access the value of interest
    6. }

    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
    C Code:
    1. struct node* AddAtHead() {
    2.     struct node* head = NULL;
    3.     int i;
    4.     for (i=1; i<6; i++) {
    5.         Push(&head, i);
    6.     }
    7.     // head == {5, 4, 3, 2, 1};
    8.     return(head);
    9. }

    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
    C Code:
    1. newNode->next = NULL;
    2. tail->next = newNode;
    3. 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.
    C Code:
    1. struct node* BuildWithSpecialCase() {
    2.     struct node* head = NULL;
    3.     struct node* tail;
    4.     int i;
    5.     // Deal with the head node here, and set the tail pointer
    6.     Push(&head, 1);
    7.     tail = head;
    8.  
    9.     // Do all the other nodes using 'tail'
    10.     for (i=2; i<6; i++) {
    11.         Push(&(tail->next), i); // add node at tail->next
    12.         tail = tail->next; // advance tail to point to last node
    13.     }
    14.     return(head); // head == {1, 2, 3, 4, 5};
    15. }

    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.
    C Code:
    1. struct node* BuildWithDummyNode() {
    2.     struct node dummy; // Dummy node is temporarily the first node
    3.     struct node* tail = &dummy; // Start the tail at the dummy.
    4.     // Build the list on dummy.next (aka tail->next)
    5.     int i;
    6.     dummy.next = NULL;
    7.     for (i=1; i<6; i++) {
    8.         Push(&(tail->next), i);
    9.         tail = tail->next;
    10.     }
    11.     // The real result list is now in dummy.next
    12.     // dummy.next == {1, 2, 3, 4, 5};
    13.     return(dummy.next);
    14. }

    Ở 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.
    C Code:
    1. struct node* BuildWithLocalRef() {
    2.     struct node* head = NULL;
    3.     struct node** lastPtrRef= &head; // Start out pointing to the head pointer
    4.     int i;
    5.     for (i=1; i<6; i++) {
    6.         Push(lastPtrRef, i); // Add node at the last pointer in the list
    7.         lastPtrRef= &((*lastPtrRef)->next); // Advance to point to the
    8.                             // new last pointer
    9.     }      
    10.     // head == {1, 2, 3, 4, 5};
    11.     return(head);
    12. }

    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()

    C Code:
    1. struct node* AppendNode(struct node** headRef, int data) {
    2.     struct node* current = *headRef;
    3.     struct node* newNode;
    4.     newNode = malloc(sizeof(struct node));
    5.     newNode->data = data;
    6.     newNode->next = NULL;
    7.  
    8.     // special case for length 0
    9.     if (current == NULL) {
    10.         *headRef = newNode;
    11.     } else {
    12.         // Locate the last node
    13.         while (current->next != NULL) {
    14.             current = current->next;
    15.         }
    16.         current->next = newNode;
    17.     }
    18. }

    AppendNode() sử dụng Push()

    C Code:
    1. struct node* AppendNode(struct node** headRef, int data) {
    2.     struct node* current = *headRef;
    3.     // special case for the empty list
    4.     if (current == NULL) {
    5.         Push(headRef, data);
    6.     } else {
    7.         // Locate the last node
    8.         while (current->next != NULL) {
    9.             current = current->next;
    10.         }
    11.         // Build the node after the last node
    12.         Push(&(current->next), data);
    13.     }
    14. }

    CopyList()

    C Code:
    1. struct node* CopyList(struct node* head) {
    2.     struct node* current = head; // used to iterate over the original list
    3.     struct node* newList = NULL; // head of the new list
    4.     struct node* tail = NULL; // kept pointing to the last node in the new list
    5.     while (current != NULL) {
    6.         if (newList == NULL) { // special case for the first new node
    7.             newList = malloc(sizeof(struct node));
    8.             newList->data = current->data;
    9.             newList->next = NULL;
    10.             tail = newList;
    11.         } else {
    12.             tail->next = malloc(sizeof(struct node));
    13.             tail = tail->next;
    14.             tail->data = current->data;
    15.             tail->next = NULL;
    16.         }
    17.         current = current->next;
    18.     }
    19.     return(newList);
    20. }

    CopyList() with Push()

    C Code:
    1. // Variant of CopyList() that uses Push()
    2. struct node* CopyList2(struct node* head) {
    3.     struct node* current = head; // used to iterate over the original list
    4.     struct node* newList = NULL; // head of the new list
    5.     struct node* tail = NULL; // kept pointing to the last node in the new list
    6.     while (current != NULL) {
    7.         if (newList == NULL) { // special case for the first new node
    8.             Push(&newList, current->data);
    9.             tail = newList;
    10.         } else {
    11.             Push(&(tail->next), current->data); // add each node at the tail
    12.             tail = tail->next; // advance the tail to the new last node
    13.         }
    14.         current = current->next;
    15.     }
    16.     return(newList);
    17. }

    CopyList() With Dummy Node

    C Code:
    1. // Dummy node variant
    2. struct node* CopyList(struct node* head) {
    3.     struct node* current = head; // used to iterate over the original list
    4.     struct node* tail; // kept pointing to the last node in the new list
    5.     struct node dummy; // build the new list off this dummy node
    6.     dummy.next = NULL;
    7.     tail = &dummy; // start the tail pointing at the dummy
    8.     while (current != NULL) {
    9.         Push(&(tail->next), current->data); // add each node at the tail
    10.         tail = tail->next; // advance the tail to the new last node
    11.         current = current->next;
    12.     }
    13.     return(dummy.next);
    14. }

    CopyList() With Local References

    C Code:
    1. // Local reference variant
    2. struct node* CopyList(struct node* head) {
    3.     struct node* current = head; // used to iterate over the original list
    4.     struct node* newList = NULL;
    5.     struct node** lastPtr;
    6.     lastPtr = &newList; // start off pointing to the head itself
    7.     while (current != NULL) {
    8.         Push(lastPtr, current->data); // add each node at the lastPtr
    9.         lastPtr = &((*lastPtr)->next); // advance lastPtr
    10.         current = current->next;
    11.     }
    12.     return(newList);
    13. }

    CopyList() Recursive

    C Code:
    1. // Recursive variant
    2. struct node* CopyList(struct node* head) {
    3.     if (head == NULL) return NULL;
    4.     else {
    5.         struct node* newList = malloc(sizeof(struct node)); // make the one node
    6.         newList->data = current->data;
    7.         newList->next = CopyList(current->next); // recur for the rest
    8.         return(newList);
    9.     }
    10. }

    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)
    Công cụ bảo vệ mã nguồn .NET mạnh nhất hiện tại, miễn phí cho các khách hàng đầu tiên đăng ký.
    Email: admin[@]congdongcviet.com | CC to: info[@]congdongcviet.com
    Phone: 0972 89 7667 (Office: 04 6329 2380)
    Yahoo & Skype: dreaminess_world (Vui lòng chỉ rõ mục đích ngay khi liên hệ, cảm ơn!)

    Một người nào đó coi thường ý thức kỷ luật cũng có nghĩa là người đó đã coi thường tương lai số phận của chính bản thân người đó. Những người coi thường ý thức kỷ luật sẽ không bao giờ có được sự thành công trong sự nghiệp!

  2. #2
    Ngày gia nhập
    12 2010
    Nơi ở
    hà thành
    Bài viết
    37

    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
    Code:
    struct node
    {
          int info;
                struct node *next;
    };

  3. #3
    Ngày gia nhập
    11 2010
    Nơi ở
    hell
    Bài viết
    165

    Trích dẫn Nguyên bản được gửi bởi vncoder Xem bài viết
    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
    Code:
    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.
    HT117-5277

  4. #4
    Ngày gia nhập
    12 2010
    Nơi ở
    hà thành
    Bài viết
    37

    Trích dẫn Nguyên bản được gửi bởi treatmaster Xem bài viết
    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

  5. #5
    Ngày gia nhập
    11 2010
    Nơi ở
    hell
    Bài viết
    165

    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.
    Code:
    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
    }
    HT117-5277

  6. #6
    Ngày gia nhập
    03 2011
    Nơi ở
    Hà Nội
    Bài viết
    89

    Mặc định Danh sách liên kết cơ bản | Linked list basic

    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
    Đã được chỉnh sửa lần cuối bởi fithou91192 : 01-11-2011 lúc 11:32 AM.

  7. #7
    Ngày gia nhập
    05 2010
    Bài viết
    29

    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:
    C Code:
    1. struct node
    2.  {
    3.    int data;
    4.    struct node* next;
    5.  }

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

    Mong mọi người chỉ giáo.
    Đã được chỉnh sửa lần cuối bởi vipbk09 : 18-08-2012 lúc 07:52 AM.

  8. #8
    Ngày gia nhập
    04 2009
    Bài viết
    3

    Theo mình thì hai cách khai báo đó đều đúng, và chúng không khác nhau gì cả

  9. #9
    Ngày gia nhập
    01 2011
    Bài viết
    36

    Trích dẫn Nguyên bản được gửi bởi vncoder Xem bài viết
    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
    Code:
    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

  10. #10
    Ngày gia nhập
    12 2012
    Nơi ở
    TIN5A - UNETI
    Bài viết
    167

    mình thì lại chẳng cần hiểu cứ code lên chạy là được rồi
    Công cụ bảo vệ mã nguồn .NET mạnh nhất hiện tại, miễn phí cho các khách hàng đầu tiên đăng ký.

Các đề tài tương tự

  1. Danh sách liên kết vòng (Circular Linked List)
    Gửi bởi iamvtn trong diễn đàn Thủ thuật, Tutorials CTDL & Giải thuật
    Trả lời: 2
    Bài viết cuối: 14-06-2014, 11:06 PM
  2. vấn đề liên quan giữa Tree và Linked List.!!
    Gửi bởi nhocconan.91 trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 10
    Bài viết cuối: 14-11-2010, 02:44 PM
  3. tạo 1 danh sách liên kết đơn(Linked List) mới ntn???
    Gửi bởi nhocconan.91 trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 2
    Bài viết cuối: 15-10-2010, 06:36 AM
  4. linked list | Danh sách liên kết | Lỗi do đâu?
    Gửi bởi xai1lanroibo trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 12
    Bài viết cuối: 03-05-2009, 03:01 PM
  5. In ra danh sách rỗng khi đã nhập danh sách - Linked List trong lập trình C++
    Gửi bởi dieucay555 trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 6
    Bài viết cuối: 05-03-2008, 11:38 PM

Quyền hạn của bạn

  • Bạn không thể gửi đề tài mới
  • Bạn không thể gửi bài trả lời
  • Bạn không thể gửi các đính kèm
  • Bạn không thể chỉnh sửa bài viết của bạn