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

trungndm

VIP Members
24/08/2016
11
7 bài viết
Cơ bản về cấu trúc dữ liệu và giải thuật - Danh sách P2
cau-truc-du-lieu_2.png

Ở 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ụ:

1-png.1331


Ở đ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)

2-png.1332


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


3-png.1333


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

4-png.1334



5-png.1335



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

6-png.1336



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
 
Bên trên