Cơ bản về cấu trúc dữ liệu và giải thuật - Danh sách P2

Thảo luận trong 'ACM/Programming' bắt đầu bởi trungndm, 23/04/17, 10:04 PM.

  1. trungndm

    trungndm VIP Members

    Tham gia: 24/08/16, 09:08 PM
    Bài viết: 7
    Đã được thích: 6
    Điểm thành tích:
    3
    Ở phần này. Mình sẽ hướng dẫn cài đặt 1 số phương thức trên danh sách liên kết. Đó là

    Insertion(thêm)Deletion(xóa)

    Đối với các thư viện dựng sẵn, tất nhiên bạn không cần phải cài đặt mà có thể sử dụng các API có sẵn. Mục đích của bài viết là để các bạn có thể nắm đc cách hoạt động cơ bản của các API đó.

    Đối với mảng, việc thêm hay xóa một phần tử nằm ở giữa của mảng tốn rất nhiều tài nguyên và thời gian.

    Ví dụ:

    [​IMG]

    Ở đoạn code trên, ta thấy có 1 số vấn đề sau:

    - Đầu tiên cần cung cấp 1 vùng nhớ nhất định cho mảng. Điều này có thể khiến chương trình có thể cấp phát thừa hoặc thiếu

    - Cần phải gán lại các phần tử phía sau phần tử được thêm hay xóa. Điều này khiến chương trình mất khá nhiều thời gian và tài nguyên

    Trong khi đó, đối với danh sách liên kết, việc này trở nên khá đơn giản.

    Ở phần trước, có giới thiệu cấu trúc của 1 phần tử trong dách sách liên kết( ở đây tạm dùng danh sách liên kết đơn)

    [​IMG]

    Ta định nghĩa cấu trúc đó là một kiểu con trỏ: PointerType


    [​IMG]

    Khi đó việc thêm một phần tử được biểu diễn theo sơ đồ sau:

    [​IMG]


    [​IMG]


    Tương tự với hàm xóa:

    [​IMG]


    Trên đây là 2 cài đặt cơ bản nhất với 1 danh sách liên kết. Ở phần tiếp theo mình sẽ hướng dẫn thêm 1 số cài đặt khác
     

    Các file đính kèm:

    • 1.png
      1.png
      Kích thước:
      8.7 KB
      Đọc:
      612
    • 2.png
      2.png
      Kích thước:
      3.5 KB
      Đọc:
      519
    • 3.png
      3.png
      Kích thước:
      4.3 KB
      Đọc:
      518
    • 4.png
      4.png
      Kích thước:
      15.6 KB
      Đọc:
      534
    • 5.png
      5.png
      Kích thước:
      8.9 KB
      Đọc:
      528
    • 6.png
      6.png
      Kích thước:
      10 KB
      Đọc:
      527
    Mời các bạn tham gia Group WhiteHat để thảo luận và cập nhật tin tức an ninh mạng hàng ngày.
    Lưu ý từ WhiteHat: Kiến thức an ninh mạng để phòng chống, không làm điều xấu. Luật pháp liên quan
    NgMSon and whf like this.