Dạng cơ bản của bảng tuần tự

Dạng cơ bản của bảng tuần tự

Hình a cho thấy dạng cơ bản của bảng tuần tự. Bản thân các phần tử dữ liệu được lưu trữ liên tục và kích thước đơn vị lưu trữ mà mỗi phần tử chiếm giữ là cố định và giống nhau. Chỉ số con của phần tử là địa chỉ logic của nó và địa chỉ vật lý của phần tử lưu trữ (địa chỉ bộ nhớ thực) có thể là Được tính bằng địa chỉ bắt đầu Loc (e 0 ) của vùng lưu trữ cộng với tích của địa chỉ logic (phần tử thứ i) và kích thước đơn vị lưu trữ (c), cụ thể là:

Loc (e i ) = Loc (e 0 ) + c * i

Do đó, không cần phải duyệt lại từ đầu khi truy cập phần tử được chỉ định và địa chỉ tương ứng có thể nhận được thông qua tính toán, và độ phức tạp thời gian là O (1).

Nếu kích thước của các phần tử không đồng nhất, bạn phải sử dụng dạng các phần tử bên ngoài trong Hình b để lưu trữ các phần tử dữ liệu thực tế một cách riêng biệt, và mỗi vị trí đơn vị trong bảng tuần tự lưu trữ thông tin địa chỉ (tức là các liên kết) của các phần tử tương ứng. Vì mỗi liên kết yêu cầu cùng một lượng lưu trữ, thông qua công thức trên, vị trí lưu trữ của liên kết phần tử có thể được tính toán và sau đó phần tử dữ liệu được lưu trữ thực tế có thể được tìm thấy dọc theo liên kết. Lưu ý rằng c trong Hình b không còn là kích thước của phần tử dữ liệu nữa mà là dung lượng cần thiết để lưu trữ một địa chỉ liên kết, thường là rất nhỏ.

Một bảng tuần tự như Hình b còn được gọi là chỉ mục cho dữ liệu thực, đây là cấu trúc chỉ mục đơn giản nhất.