Cấu trúc và hiện thực của bảng tuần tự

Cấu trúc bảng tuần tự

Thông tin đầy đủ của một bảng tuần tự bao gồm hai phần, một phần là tập hợp các phần tử trong bảng, một phần là thông tin cần ghi lại để thao tác chính xác, tức là thông tin về tình hình chung của bảng. Phần thông tin này chủ yếu bao gồm dung lượng của khu vực lưu trữ phần tử. Và số phần tử trong bảng hiện tại .

Hai cách cơ bản để nhận ra bảng trình tự

Hình a cho thấy một cấu trúc tích hợp. Đơn vị lưu trữ thông tin bảng và vùng lưu trữ phần tử được sắp xếp liên tục trong một vùng lưu trữ. Hai phần dữ liệu tạo thành một đối tượng bảng tuần tự hoàn chỉnh.

Cấu trúc tích hợp có tính toàn vẹn mạnh mẽ và dễ dàng quản lý. Nhưng vì vùng lưu trữ phần tử dữ liệu là một phần của đối tượng bảng nên sau khi bảng tuần tự được tạo, vùng lưu trữ phần tử được cố định.

Hình b cho thấy một cấu trúc được phân tách. Chỉ thông tin liên quan đến toàn bộ bảng (tức là dung lượng và số phần tử) được lưu trữ trong đối tượng bảng. Các phần tử dữ liệu thực tế được lưu trữ trong một vùng lưu trữ phần tử độc lập khác và được liên kết với đối tượng bảng cơ bản thông qua các liên kết.

Thay thế khu vực lưu trữ phần tử

Cấu trúc tích phân Vì vùng thông tin bảng tuần tự và vùng dữ liệu liên tục được lưu cùng nhau, nên nếu bạn muốn thay thế vùng dữ liệu, bạn chỉ có thể di chuyển nó một cách tổng thể, tức là toàn bộ đối tượng bảng tuần tự (đề cập đến vùng lưu trữ thông tin cấu trúc của bảng tuần tự).

Nếu bạn muốn thay thế vùng dữ liệu bằng cấu trúc đã phân tách, bạn chỉ cần cập nhật địa chỉ liên kết của vùng dữ liệu trong vùng thông tin bảng, và đối tượng bảng tuần tự không thay đổi.

Mở rộng khu vực lưu trữ phần tử

Sử dụng bảng tuần tự có cấu trúc riêng biệt, nếu vùng dữ liệu được thay thế bằng không gian lưu trữ lớn hơn, vùng lưu trữ dữ liệu có thể được mở rộng mà không cần thay đổi đối tượng bảng và tất cả những nơi sử dụng bảng này không cần phải sửa đổi. Miễn là môi trường hoạt động của chương trình (hệ thống máy tính) còn lưu trữ miễn phí, cấu trúc bảng này sẽ không làm cho các hoạt động bị lỗi vì nó đầy. Người ta gọi bảng tuần tự do công nghệ này thực hiện là bảng tuần tự động vì dung lượng của nó có thể thay đổi động trong quá trình sử dụng.

Hai chiến lược để mở rộng

• Mỗi lần mở rộng thêm một số lượng vị trí lưu trữ cố định. Ví dụ: mỗi lần mở rộng thêm 10 vị trí phần tử. Chiến lược này có thể được gọi là tăng trưởng tuyến tính.

  Tính năng: Tiết kiệm dung lượng, nhưng thao tác mở rộng thường xuyên và nhiều thao tác.

• Mỗi lần mở rộng tăng gấp đôi dung lượng, chẳng hạn như tăng gấp đôi không gian lưu trữ mỗi lần mở rộng.

  Tính năng: Giảm số lần thực thi các hoạt động mở rộng, nhưng có thể lãng phí tài nguyên không gian. Cách đề xuất để giao dịch không gian cho thời gian.