Top Ad unit 728 × 90

Latest news

recent

Ý tưởng sử dụng mảng động (Dynamic Array)

Khi làm việc với cấu trúc dữ liệu mảng, một vấn đề thường xảy ra là kích thước của nó không thể được thay đổi trong suốt quá trình chạy của chương trình sau khi vùng nhớ đã được cấp phát. Không có một giải pháp triệt để nào cho nhược điểm này, ngoại trừ một số kiểu dữ liệu cao cấp chỉ được hỗ trợ bởi các nền tảng mới như List trong .Net. Tuy nhiên vì chúng tôi hướng tới việc triển khai thuật tóan trên nền C do đó một giải pháp nhằm quản lý dung lượng lưu trử của mảng sẽ được đề xuất.

Chi tiết ý tưởng

Ý tưởng khá đơn giản. Ứng dụng sẽ cấp phát một lượng bộ nhớ nhất định cho mảng dữ liệu và ngầm định một cách logic chia nó thành 2 phần. Một phần chứa dữ liệu hiện sử dụng và phần khác là không gian trống. Khi khởi tạo ban đầu tòan bộ không gian nhớ là trống. Trong quá trình thuật tóan hay chương trình chạy, ranh giới phân biệt giữa vùng đang sử dụng và vùng trống sẽ thay đổi liên tục. Trong trường hợp không đủ vùng trống để sử dụng, vùng nhớ cấp phát cần được mở rộng bằng cách tạo ra mảng mới có kích thước lớn hơn và chép nội dung từ mảng củ vào vùng nhớ mới được cấp phát lại.Hình dưới đây biểu diển cho mô hình này:
Nguồn từ: IEEV

Từ lý giải trên, trong thực hành chúng ta dễ dàng nhận ra việc cần phải khai báo một con trỏ và cấp phát bộ nhớ, cũng như khởi tạo giá trị trống cho nó. Mặt khác cũng cần một biến lưu giữ vị trí biên của vùng đang được sử dụng và vùng nhớ còn trống. Khi giá trị biên lọt ra ngoài kích thước mảng thì cũng là lúc cần cấp phát lại vùng nhớ to hơn cho mảng.
Đây là kỹ thuật được sử dụng rất nhiều trong quá trình triển khai thuật toán, dù không có gì khó tuy nhiên tôi thấy cũng cần nhắc tới. Hy vọng sẽ giúp ích cho những người mới!




Binh Nguyen - Bioz
Ý tưởng sử dụng mảng động (Dynamic Array) Reviewed by Bioz Nguyen on 8:51:00 PM Rating: 5
All Rights Reserved by IEEV © 2009 - 2016
Powered By Blogger, Designed by Sweetheme

Contact Form

Name

Email *

Message *

Powered by Blogger.