Cấu trúc dữ liệu là một cách có hệ thống để tổ chức dữ liệu để sử dụng nó một cách hiệu quả. Các thuật ngữ sau đây là các điều khoản nền tảng của một cấu trúc dữ liệu.
- Giao diện - Mỗi cấu trúc dữ liệu có một giao diện. Giao diện đại diện cho tập hợp các hoạt động mà cấu trúc dữ liệu hỗ trợ. Một giao diện chỉ cung cấp danh sách các hoạt động được hỗ trợ, loại tham số họ có thể chấp nhận và trả về loại của các hoạt động này.
- Triển khai - Triển khai cung cấp biểu diễn bên trong của cấu trúc dữ liệu. Việc thực hiện cũng cung cấp định nghĩa về các thuật toán được sử dụng trong các hoạt động của cấu trúc dữ liệu.
Đặc điểm của cấu trúc dữ liệu
- Tính chính xác - Việc thực hiện cấu trúc dữ liệu phải thực hiện đúng giao diện của nó.
- Độ phức tạp thời gian - Thời gian chạy hoặc thời gian thực hiện các hoạt động của cấu trúc dữ liệu phải càng nhỏ càng tốt.
- Độ phức tạp không gian - Việc sử dụng bộ nhớ của một hoạt động cấu trúc dữ liệu nên càng ít càng tốt.
Cần cấu trúc dữ liệu
Khi các ứng dụng ngày càng phức tạp và giàu dữ liệu, có ba vấn đề phổ biến mà các ứng dụng phải đối mặt bây giờ - một ngày.
- Tìm kiếm dữ liệu - Xem xét khoảng không quảng cáo của 1 triệu (10 6 ) mặt hàng của một cửa hàng. Nếu ứng dụng là để tìm kiếm một mục, nó phải tìm kiếm một mục trong 1 triệu (10 6 ) mục mỗi khi làm chậm tìm kiếm. Khi dữ liệu phát triển, tìm kiếm sẽ trở nên chậm hơn.
- Tốc độ của bộ xử lý - Tốc độ của bộ xử lý mặc dù rất cao, bị giới hạn nếu dữ liệu tăng lên hàng tỷ bản ghi.
- Nhiều yêu cầu - Vì hàng ngàn người dùng có thể tìm kiếm dữ liệu đồng thời trên một máy chủ web, ngay cả máy chủ nhanh cũng bị lỗi trong khi tìm kiếm dữ liệu.
Để giải quyết các vấn đề nêu trên, các cấu trúc dữ liệu đến để giải cứu. Dữ liệu có thể được sắp xếp theo cấu trúc dữ liệu theo cách mà tất cả các mục có thể không được yêu cầu tìm kiếm và dữ liệu cần thiết có thể được tìm kiếm gần như ngay lập tức.
Thời gian thực hiện
Có ba trường hợp thường được sử dụng để so sánh thời gian thực hiện của cấu trúc dữ liệu khác nhau theo cách tương đối.
- Trường hợp xấu nhất - Đây là tình huống trong đó một hoạt động cấu trúc dữ liệu cụ thể mất thời gian tối đa có thể. Nếu thời gian trường hợp xấu nhất của một hoạt động là ƒ (n) thì hoạt động này sẽ không mất nhiều hơn (n) thời gian trong đó ƒ (n) đại diện cho chức năng của n.
- Trường hợp trung bình - Đây là kịch bản mô tả thời gian thực hiện trung bình của một hoạt động của cấu trúc dữ liệu. Nếu một hoạt động mất (n) thời gian thực hiện, thì m hoạt động sẽ mất mƒ (n) thời gian.
- Trường hợp tốt nhất - Đây là kịch bản mô tả thời gian thực hiện ít nhất có thể của một hoạt động của cấu trúc dữ liệu. Nếu một hoạt động mất (n) thời gian thực hiện, thì hoạt động thực tế có thể mất thời gian là số ngẫu nhiên sẽ tối đa là (n).
Thuật ngữ cơ bản
- Dữ liệu - Dữ liệu là các giá trị hoặc tập hợp các giá trị.
- Mục dữ liệu - Mục dữ liệu đề cập đến một đơn vị giá trị.
- Mục nhóm - Các mục dữ liệu được chia thành các mục phụ được gọi là Mục nhóm.
- Mục sơ cấp - Các mục dữ liệu không thể phân chia được gọi là Mục sơ cấp.
- Thuộc tính và thực thể - Một thực thể chứa các thuộc tính hoặc thuộc tính nhất định, có thể được gán các giá trị.
- Bộ thực thể - Các thực thể của các thuộc tính tương tự tạo thành một bộ thực thể.
- Trường - Trường là một đơn vị thông tin cơ bản duy nhất đại diện cho một thuộc tính của thực thể.
- Bản ghi - Bản ghi là tập hợp các giá trị trường của một thực thể nhất định.
- Tệp - Tệp là tập hợp các bản ghi của các thực thể trong một tập thực thể nhất định.
Được cập nhật: 15 tháng 4 lúc 12:07:29 | Lượt xem: 457
