Cấu trúc dữ liệu tuyến tính (tiếng Anh linear data structure) là cấu trúc dữ liệu trong đó các phần tử dữ liệu được tổ chức thành một chuỗi có thứ tự về mặt chỉ số. Trong một cấu trúc dữ liệu tuyến tính, ngoài phần tử đầu tiên và phần tử cuối cùng, các phần tử còn lại luôn đứng trước một phần tử và đứng sau một phần tử khác. Các phần tử của cấu trúc dữ liệu tuyến tính đều có cùng một kiểu dữ liệu, có thể là kiểu cơ bản hay phức hợp (xt. kiểu dữ liệu). Cấu trúc dữ liệu tuyến tính bao gồm hai loại chính là mảng một chiều và danh sách liên kết.
Mảng một chiều[sửa]
Mảng một chiều là một vùng nhớ trong liên tiếp của máy tính. Vùng nhớ này được chia thành các ô liên tiếp. Mỗi ô có kích cỡ, tùy theo kiểu dữ liệu của các phần tử của mảng. Thứ tự trước-sau của các phần tử dữ liệu trong mảng cũng chính là thứ tự trước-sau về mặt địa chỉ của các ô nhớ trong bộ nhớ vật lý.
Ưu điểm của mảng một chiều là không tốn thêm các vùng nhớ trung gian để thể hiện thứ tự của các phần tử. Thao tác truy cập vào một phần tử bất kỳ được thực hiện thông qua phép tính địa chỉ tương đối của phần tử so với phần tử đầu tiên của mảng.
Nhược điểm của mảng một chiều là không linh hoạt trong việc cấp phát và thu hồi bộ nhớ. Việc hoán đổi vị trí giữa các phần tử phải thực hiện thông qua việc sao chép nội dung. Điều này không thuận lợi khi các phần tử có kích thước rất lớn. Mảng một chiều thích hợp trong việc biểu diễn các tập dữ liệu có kích thước cố định.
Danh sách liên kết[sửa]
Danh sách liên kết là tập các nút dữ liệu được cấp phát động, nằm rải rác trong bộ nhớ. Mỗi nút chứa ít nhất một con trỏ (xt. Kiểu dữ liệu) để kết nối với một nút khác. Có hai kiểu danh sách liên kết cơ bản:
- Danh sách liên kết đơn: mỗi nút chỉ chứa một con trỏ để kết nối với nút đứng ngay sau nó.
- Danh sách liên kết đôi: mỗi nút chứa hai con trỏ, kết nối với nút đứng trước và ngay sau nó.
Ưu điểm của danh sách liên kết là tính linh hoạt trong việc cấp phát và giải phóng vùng nhớ. Việc hoán đổi vị trí của các phần tử có thể được thực hiện thông qua việc thay đổi giá trị của các con trỏ.
Nhược điểm của danh sách liên kết là việc truy cập vào một phần tử phải thực hiện thông qua việc duyệt qua các phần tử đứng trước (hoặc sau) nó, do đó trong một số trường hợp sẽ tốn nhiều thời gian, không hiệu quả bằng mảng một chiều. Bên cạnh đó, việc phải sử dụng thêm con trỏ để lưu trữ địa chỉ các nút khác khiến cho chương trình sử dụng danh sách liên kết phải sử dụng nhiều bộ nhớ hơn mảng một chiều.
Lịch sử[sửa]
Mảng một chiều được sử dụng ngay trong những kiến trúc máy tính đầu tiên và hợp ngữ (khoảng năm 1945). Thao tác truy cập vào một phần tử bất kỳ được thực hiện dựa trên việc tính địa chỉ thông qua địa chỉ bắt đầu của mảng và thứ tự của phần tử trong mảng. Các ngôn ngữ lập trình bậc cao đều hỗ trợ mảng một chiều như một cấu trúc cơ bản, cho phép cấp phát vùng nhớ trong quá trình biên dịch (cấp phát tĩnh) hoặc trong quá trình thực thi (cấp phát động). Danh sách liên kết ra đời muộn hơn một chút, vào khoảng giữa thập kỉ 1950, được cài đặt đầu tiên trong ngôn ngữ lập trình IPL (Information Processing Language). Các ngôn ngữ lập trình bậc cao đều hỗ trợ thao tác cấp phát vùng nhớ động hoặc cài đặt danh sách liên kết trong những thư viện hoặc lớp cơ bản.
Đến nay, cấu trúc dữ liệu tuyến tính là một trong những nội dung cơ bản nhất được giảng dạy ở phần mở đầu các môn học cơ bản của Công nghệ thông tin và Khoa học máy tính như: Cấu trúc dữ liệu và giải thuật, Ngôn ngữ lập trình.
Ứng dụng[sửa]
Cấu trúc dữ liệu tuyến tính là những thành phần cơ bản nhất để xây dựng các chương trình máy tính. Một số ứng dụng là:
- Cài đặt các tập hợp phần tử có hoặc không có thứ tự với các thao tác thêm, sửa, xóa, kiểm tra sự tồn tại của phần tử, sắp xếp các phần tử
- Cài đặt các dãy có thứ tự của các phần tử, tiêu biểu nhất là ngăn xếp và hàng đợi. Ngăn xếp là dãy các phần tử mà việc thêm phần tử vào hoặc lấy phần tử ra chỉ được tiến hành ở một đầu. Hàng đợi là dãy các phần tử mà việc thêm phần tử vào và lấy phần tử ra được tiến hành ở hai đầu khác nhau. Đây là những cấu trúc cơ bản nhất để cài đặt hầu hết các giải thuật hiện nay.
- Tùy vào cách đánh thứ tự của vùng nhớ, mảng một chiều có thể được tùy biến để trở thành mảng nhiều chiều, biểu diễn các véc tơ, ma trận, …
- Là cơ sở để cài đặt các cấu trúc dữ liệu phức tạp hơn như: bảng băm (xt. Cấu trúc dữ liệu ánh xạ), cây và đồ thị (xt. Cấu trúc dữ liệu phi tuyến).
Cấu trúc dữ liệu tuyến tính gần như được giữ nguyên cách định nghĩa và các thao tác cơ bản từ thời kỳ ban đầu của công nghệ thông tin và khoa học máy tính. Cùng với sự phát triển của ngôn ngữ lập trình và công nghệ phần mềm, các cấu trúc dữ liệu tuyến tính được cài đặt thành các thư viện và lớp, cho phép người sử dụng có thể thực hiện các thao tác cơ bản dễ dàng hơn mà không cần phải quan tâm đến việc cấp phát, thu hồi, định dạng và quản lý vùng nhớ.
Tài liệu tham khảo[sửa]
- Đỗ Xuân Lôi, Cấu trúc dữ liệu và giải thuật, Nhà xuất bản Đại học Quốc gia Hà Nội, in lần thứ 9, 2006
- Niclaus Wirth, Algorithms + Data structures = Programs, Prentice-Hall, Inc (1976).
- Donald Knuth, The Art of Computer Programming, vol. 1. Addison-Wesley, 3rd edition, 1997.
