Chương 2 có thể giúp người học biết được các khái niệm về mảng và danh sách, các phép toán trên danh sách, lưu trữ kế tiếp cho danh sách tuyến tính, cấu trúc ngăn xếp (Stack), lưu trữ kế tiếp, các phép toán trên ngăn xếp, các phép toán trên ngăn xếp, . Mời các bạn cùng tham khảo. | CHƯƠNG 2 MẢNG VÀ DANH SÁCH 1. Mảng 2. Danh sách 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. Mảng l 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. l Một 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. l Các phần tử của mảng có thể được tổ chức thành mảng 1 chiều 2 chiều 3 chiều Ví dụ Véc tơ là mảng 1 chiều có 1 chỉ số i . Ma trận là mảng 2 chiều có 2 chỉ số i j . Không gian 3 chiều là mảng 3 chiều có 3 chỉ số. Không gian n chiều là mảng n chiều có n chỉ số. 1. Mảng l 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ử. l 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. l Với mảng 1 chiều phần tử ai được lưu trữ ở ô nhớ V i l 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 1. Mảng l Mảng 2 chiều có m 2 hàng n 3 cột. Tính chỉ số k truy nhập vào ô nhớ chứa phần tử aij. 4 5 9 7 10 1 4 5 9 7 10 1 gt k i-1 n j l 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. l Không có phép bổ sung hoặc loại bỏ một phần tử mảng. 2. Danh sách . Khái niệm l 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. l Phép loại bỏ bổ sung 1 phần tử là phép thường xuyên tác động lên danh sách. l 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. . Khái niệm l Danh sách tuyến tính Một danh sách mà quan hệ lận cận giữa các phần tử được xác định rõ ràng thì được gọi là danh sách tuyến tính. Véc tơ là một danh sách tuyến tính. l Danh sách tuyến tính hoặc rỗng không có phần tử nào hoặc có dạng a1 a2 . an với ai 1 i n là các phần tử. l Trong danh sách tuyến tính tồn tại phần tử đầu là a1 phần tử cuối là an 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ử
