Chuyển đến nội dung chính

Danh Sách Liên Kết Đơn

STL là viết tắt của cụm từ Standard Template Library, là bộ thư viện chuẩn của C++, STL cung cấp các lớp cài đặt sẵn, cho phép thao tác với các kiểu dữ liệu cơ bản cũng như các kiểu dữ liệu tự định nghĩa, việc thành thạo sử dụng thư viện STL sẽ giúp bạn tiếp kiệm thời gian trong lập trình.

Giới thiệu

Các bạn đã sử dụng qua array(mảng) để chứa dữ liệu trong từng phần tử trong một array và có thể duyệt qua từng phần tử đó để làm việc với các dữ liệu đó. Nhược điểm của array là khi sử dụng các bạn khởi tạo với một số lượng phần tử nhất định, thì giới hạn này sẽ không thể bị phá vỡ bởi quy tắc của kiểu dữ liệu này, kể cả với ::cấp phát động. List ra đời để hỗ trợ cho các lập trình viên một kiểu dữ liệu mới để quản lý việc các phần tử được thêm mới và xóa khỏi vùng nhớ một các dễ dàng.

Tổ chức danh sách liên kết đơn

Cũng giống như mảng, danh sách liên kết cũng bao gồm các phần tử, có mối liên hệ với nhau. Tôi gọi mỗi phần tử đó là một Node. Node được xem là trái tim của danh sách liên kết, mỗi Node sẽ lưu trữ 2 thông tin:
  • Thông tin dữ liệu: Lưu trữ các thông tìn về chính Node đó.
  • Thông tin liên kết: Lưu trữ địa chỉ của phần tử kế tiếp trong danh sách, hoặc lưu trữ giá trị NULL nếu phần tử đó nằm cuối danh sách. 
ss_1
Một cách tổng quát ta có:
    

  1. struct SNode
    2. 

  2. {
    3. 

  3.  Data Info;
    4. 

  4.  SNode* pNext;
    5. 

  5. };
    6.
Mỗi phần tử trong trong danh sách liên kết đơn là một biến động sẽ được yêu cầu cấp phát khi cần thiết, danh sách liên kết đơn chính là sự liên kết các biến này với nhau do đó ta hoàn toàn chủ động về số lượng các phần tử.
Để đơn giản, trong bài viết này tôi sẽ lấy ví dụ danh sách liên kết đơn lưu trữ các số nguyên.
Node của danh sách liên kết sẽ được định nghĩa như sau:
    

  1. struct SNode
    2. 

  2. {
    3. 

  3.  int Data;
    4. 

  4.  SNode* pNext;
    5. 

  5. };
    6.
Tôi sử dụng một phương thức GetNode để cấp phát động một Node khi cần thiết:
    

  1. SNode* GetNode(int x)
    2. 

  2. {
    3. 

  3.  SNode *p = new SNode;
    4. 

  4.  
    5. 

  5.  p->Data = x;
    6. 

  6.  p->pNext = NULL;
    7. 

  7.  
    8. 

  8.  return p;
    9. 

  9. }
    10.
Bây giờ chúng ta bắt đầu tìm hiểu một số phương thức đơn giản tạo nên sự liên kết các Node để tạo ra một danh sách liên kết đơn hoàn chỉnh.

Một số thao tác cơ bản trên danh sách liên kết đơn

Trong danh sách liên kết đơn, các Node sẽ không được lưu liên tiếp nhau trên bộ nhớ, Node trước sẽ mang thông tin địa chỉ của Node sau, như vậy nếu bạn xử lý lỗi một Node sẽ dẫn đến tính huống xấu nhất, ta sẽ mất toàn bộ thông tin của các Node phía sau.
Chúng ta sẽ bắt đầu làm việc với các thao tác cơ bản trên một danh sách liên kết đơn. Giả sử tôi có định nghĩa sau:
    

  1. struct SNode
    2. 

  2. {
    3. 

  3.  int Data;
    4. 

  4.  SNode* pNext;
    5. 

  5. };
    6. 

  6.  
    7. 

  7. struct SList
    8. 

  8. {
    9. 

  9.  SNode* pHead;
    10. 

  10.  SNode* pTail;
    11. 

  11.  
    12. 

  12.  SList(){}
    13. 

  13.  SList(SNode* Head, SNode* Tail)
    14. 

  14.  {
    15. 

  15.   this->pHead = Head;
    16. 

  16.   this->pTail = Tail;
    17. 

  17.  }
    18. 

  18. };
    19.
Nếu biết được địa chỉ đầu tiên trong danh sách liên kết ta có thể dựa vào thông tin pNext để truy xuất đến các phần tử còn lại, do đó ta sẽ dùng một con trỏ pHead để lưu lại địa chỉ Node đầu tiên của danh sách. Trong một số trường hợp ta cũng cần thao tác trên phần tử cuối cùng của danh sách, nên tôi dùng thêm một con trỏ pTail để lưu trữ địa chỉ của Node cuối cùng trong danh sách.

Chèn vào đầu danh sách

Như đã trình bày ở trên, khi thao tác với mỗi Node trên danh sách liên kết ta cần thực hiện cẩn thận, đúng thứ tự để tránh mất thông tin của các Node phía sau. Dưới đây là thứ tự các bước chèn một phần tử vào đầu mảng.
Bước 1: cấp phát một Node mới (new_element).
Bước 2: gán pNext của Node mới trỏ đến Node đầu (cũ).
    

  1. new_element->pNext = pHead;
    2.
Bước 3: cập nhập lại giá trị pHead
    

  1. pHead = new_element;
    2.
Lưu đồ bên dưới thể hiện từng bước để thêm vào một Node mới ở đầu danh sách
ss_2

Chèn vào cuối danh sách

Tương tự với thao tác chèn vào đầu danh sách, chèn vào cuối danh sách chúng ta chỉ cần cập nhập lại con trỏ pTail.
Bước 1: cấp phát một Node mới (new_element).
Bước 2: gán lại pNext của Node cuối cùng (cũ) sẽ trỏ đến Node mới. 
    

  1. pTail->pNext = new_element;
    2.
Bước 3: cập nhập lại giá trị pTail, bây giờ Node cuối của danh sách là Node chúng ta vừa thêm.
    

  1. pTail = new_element;
    2.
Đây là lưu đồ thứ tự thực hiên các bước ở trên
ss_3

Chèn vào danh sách sau một phần tử q

Chèn vào danh sách sau một phần tử q nào đó, chèn vào giữa danh sách không cần cập nhập lại hai con trỏ pHead và pTail tuy nhiên chúng ta cần hết sức cần thận để tránh mất dữ liệu phía sau.
Bước 1: cấp phát một Node mới - new_element.
Bước 2: gán pNext của Node mới bằng địa chỉ của Node sau q.
    

  1. new_element ->pNext = q-> pNext;
    2.
Bước 3: cập nhập lại pNext của Node q trỏ đến Node mới.
    

  1. q-> pNext = new_element;
    2.
ss_4

Xóa một phần tử đầu danh sách

Xóa 1 phần tử ở đầu danh sách không chỉ đơn giản là cập nhập lại biến con trỏ pHead, mà ta phải giải phóng được vùng nhớ của Node cần xóa.
Bước 1: Khai báo một con trỏ p để lưu lại địa chỉ của Node đầu tiên.
    

  1. SNode* p = pHead;
    2.
Bước 2: cập nhập lại giá trị của pHead.
    

  1. pHead = pHead->pNext;
    2.
Bước 3: giải phóng vùng nhớ của Node cần xóa.
    

  1. delete p;
    2.
ss_5

Xóa một phần tử đứng sau phần tử q

Tương tự như thao tác xóa phần tử đầu danh sách, để xóa một phần tử đứng sau phần tử q, ta thực hiện các bước sau:
Bước 1: Khai báo một con trỏ p để lưu lại địa chỉ của Node đầu tiên.
    

  1. SNode* p = q->pNext;
    2.
Bước 2: cập nhập lại giá trị pNext của Node q.
    

  1. q->pNext = p->pNext;
    2.
Bước 3: giải phóng vùng nhớ của Node cần xóa.
    

  1. delete p;
    2.
ss_6

Duyệt danh sách

Khi có được giá trị của pHead ta có thể dựa và thông tin pNext để duyệt lần lượt các phần tử của danh sách.
    

  1. SNode* p;
    2. 

  2.  
    3. 

  3. p = list.pHead;
    4. 

  4. while (p != NULL)
    5. 

  5. {
    6. 

  6.  // Process Node
    7. 

  7.  p = p->pNext;
    8. 

  8. }
    9.

Lời kết

Source code được viết theo hướng cấu trúc để các bạn chưa có khái niệm về hướng đối tượng có thể tiếp cận một cách dễ dàng.
Có thể thấy được, danh sách liên kết đã khắc phục được nhược điểm của mảng - đó là kích thước cố định.Với bài viết này, hy vọng các bạn đã có cái nhìn tổng quát hơn về danh sách liên kết và các thao tác liên quan như: thêm phần tử, xóa phần tử ... và có thể ứng dụng được vào các dự án của mình.
Nhãn:

Nhận xét

Đăng nhận xét

Bài đăng phổ biến từ blog này

Entry Test của FPT

IQ - Kiểm tra tư duy logic (8/20) - GMAT- Kiểm tra khả năng tính toán trong thời gian ngắn (8/20) - Tiếng Anh (18-> 25/50) - Các bài thi chuyên môn - FE (8/20) IQ: lên mạng tìm "IQ test" là ra đầy. + GMAT: Những câu trắc nghiệm tính toán đơn giản kiểu như sau:  1 . Một shop thời trang sale off quần jeans 15 %, quần jeans giá 450 $, người mua đưa 500 $, hỏi cashier trả lại bao nhiêu $ tiền thừa.? 2 . 100 % là 180 , vậy 150 là bao nhiêu %? Tiếng anh: Cỡ như thi TOEIC thôi. Chuyên môn: Mobile thì trắc nghiệm Java. Qúa trình tuyển như sau :v Lần 1: Test IQ, Tiếng Anh( mình làm í ẹ khoảng 50% mà vẫn được) , Java Lân 2: được gọi điện lên :)) + Gioi thiệu bản thân + Họ chỉ hỏi các câu căn bản như: -. OOP: là gì, 4 tính chất, ví dụ, khác nhau giữa interface và abstract - CODE: hầu toàn các bài toán vòng for :)) , cẩn thận mấy câu kế thừa. SQL (distinct, view, function, cursor, store procedure, ...v.v.), nhớ có câu cộng 2 số int không dùng biến đệm hơi khoai haha + Nói ch...
Đăng nhận xét
Đọc thêm

Java: Java Package-Thư viện trong Java

Giới thiệu về Package Các bạn mới học lập trình Java thường không dể ý tới package vì các bạn toàn tạo file .java vào cùng 1 chỗ, không cần sắp xếp, không cần quản lý truy nhập. Nhưng để tăng kỹ năng lập trình với Java, các bạn cần phải tìm hiểu về package trong Java. Các bạn có thể tham khảo định nghĩa sau: Package được dùng để đóng gói các lớp trong chương trình lại với nhau thành một khối. Đây là cách tốt nhất để lưu trữ các lớp gần giống nhau hoặc có cùng một module thành một khối thống nhất – để đáp ứng 1 khối chức năng. Từ đây mình sẽ giới thiệu thêm với các bạn các câu lệnh nhâp khẩu,nó có định dạng như sau : Định dạng :  import javaPackageNameImport;    Nó giống như khai báo thư viện ở các ngôn ngữ lập trình khác.Như vậy,chỉ khi các bạn nhập khẩu chúng,các bạn mới có thể sử dụng thư viện mà chúng cung cấp cho ta. VD :    import java.util.Date;   import java.text.SimpleDateFormat; Lưu ý : -Các câu lệnh nhập khẩu rất nhiều và...
Đăng nhận xét
Đọc thêm

phỏng vấn Embedded C và C++?

Có vài điểm rất nhỏ, các bạn không để ý có thể dẫn đến bất lợi (nếu không muốn nói là rớt) ở vòng hồ sơ hoặc khi đi phỏng vấn. Mình liệt kê rất cụ thể ra những chuyện mình đã thấy qua nhiều lần (người thật, việc thật), hy vọng cho các bạn thêm kinh nghiệm. Lưu ý: Những chuyện này rất chủ quan, có thể chỉ đúng trong môi trường của mình và hoàn toàn không đúng trong môi trường khác. Gửi email CV đến không có Cover Letter, chỉ đính kèm mỗi file PDF là cái CV. CV ghi : tiếng Anh: Trung Bình, C: Trung Bình,... nhưng bên dưới lại ghi ưu điểm_:  là người ham học hỏi... CV bằng tiếng Việt và lại viết sai chính tả tiếng Việt. CV ghi quá nhiều về các hoạt động tình nguyện, hiến máu, blah blah... nhưng phần kĩ thuật lại có 3 dòng thôi. Mặc đồ thể dục của trường và đi dép lê đến PV. Đến muộn PV (em ấy bảo bị kẹt xe). Đưa yêu cầu, em ấy không hiểu đề nhưng ngại không dám hỏi lại, dẫn đến viết hoàn toàn sai. Hỏi ngay câu căn bản đầu tiên em ấy đã nói không biết và  đổ do trường kh...
Đăng nhận xét
Đọc thêm