Bài giảng Cấu trúc dữ liệu và giải thuật (Data Structures and Algorithms) - Chương 2: Mảng và danh sách. Nội dung chính của chương gồm có: Mảng, danh sách, cấu trúc ngăn xếp (stack), cấu trúc hàng đợi (queue). Mời các bạn cùng tham khảo! | 22 04 22 Tìm hiểu một cấu trúc dữ liệu 1 Đặc điểm tổ chức 2 Cấu trúc lưu trữ 3 Phép toán Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 02 1 CHƯƠNG 2 MẢNG VÀ DANH SÁCH 1. Mảng Mảng là một tập hợp có thứ tự gồm một số cố định các phần tử cùng kiểu. Mỗi phần tử mảng được chỉ ra bởi chỉ số thể hiện thứ tự của phần tử trong mảng. Điều này cho phép truy nhập trực tiếp phần tử qua chỉ số. Các phần tử của mảng có thể tổ chức thành mảng 1 chiều 2 chiều 3 chiều Mảng 1 chiều có 1 chỉ số mảng 2 chiều có 2 chỉ số mảng n chiều có n chỉ số. 2 1 22 04 22 1. Mảng Mảng chỉ dùng được cấu trúc lưu trữ kế tiếp để cho phép truy nhập trực tiếp các phần tử. Dùng vec tơ lưu trữ V có n ô nhớ liên tiếp với chỉ số từ 1 đến n để lưu trữ các phần tử dữ liệu của mảng. Với mảng 1 chiều phần tử ai được lưu trữ ở ô nhớ V i Với mảng 2 chiều các phần tử được lưu trữ lần lượt hết hàng 1 đến hàng 2 Phần tử aij được lưu trữ ở ô nhớ V k k i-1 n j n là số phần tử trên hàng. 3 1. Mảng V x x x x k 1 2 3 n k i-1 n j 4 5 9 a13 gt V k 7 10 1 k 1-1 3 3 3 V 4 5 9 7 10 1 k 1 2 3 4 5 6 4 2 22 04 22 1. Mảng Có các phép tạo lập mảng tìm kiếm 1 phần tử từ mảng truy nhập một phần tử mảng. Không có phép bổ sung và loại bỏ một phần tử mảng. 5 2. Danh sách . Khái niệm Danh sách là một tập hợp có thứ tự gồm một số biến động các phần tử cùng kiểu. Ví dụ Tập hợp người đến khám bệnh cho ta một danh sách. Người đến xếp hàng khám bổ sung ở phía sau người được khám sẽ ra khỏi hàng loại bỏ ở phía trước. 6 3 22 04 22 . Khái niệm Danh sách tuyến tính là danh sách mà mối quan hệ lận cận giữa các phần tử được xác định rõ ràng. Ví dụ Véc tơ là một danh sách tuyến tính. Danh sách tuyến tính có dạng a1 a2 . an trong đó a1 là phần tử đầu an là phần tử cuối phần tử thứ i là ai. Với ai bất kỳ 1 i n thì ai 1 gọi là phần tử sau ai 2 i n thì phần tử ai-1 là phần tử trước của ai. Danh sách có thể rỗng không có phần tử nào . 7 . Khái niệm n là độ dài kích thước của danh sách n có thể thay đổi. Một phần tử trong
