tailieunhanh - Ebook Cấu trúc dữ liệu và giải thuật: Phần 2 - ThS. An Văn Minh, ThS. Trần Hùng Cường

Ebook Cấu trúc dữ liệu và giải thuật: Phần 2 trình bày danh sách tuyến tính - một loại cấu trúc dữ liệu rất phổ biến trong các bài toán tin học và cây - một dạng cấu trúc dữ liệu phi tuyến tính. Đây là tài liệu dành cho sinh viên ngành công nghệ thông tin. | Chương 4 DANH SÁCH TUYÊN TÍNH Trong chương này. chúng ta sẽ nghiên cứu danh sách tuyến tính một trong các mô hình dừ liệu quan trọng nhất được sử dụng thường xuyên trong việc cài đặt các bài toán ứng dụng. Các phương pháp cài đặt danh sách khác nhau sẽ được xem xét. Hai kiểu dữ liệu trừu tượng đặc biệt quan trọng là ngăn xếp Stack vả hàng đợi Queue sẽ được nghiên cứu. Chương này cũng sẽ trình bày một số ứng dụng phổ biến của danh sách. 1. KHÁI NIỆM DANH SÁCH TUYÊN TÍNH . Khái niệm danh sách về mặt toán học danh sách là một dãy hữu hạn các phần tử thuộc cùng một lớp đối tượng nào đó. Chang hạn. danh sách sinh viên cùa một lớp danh sách các số nguyên danh sách các báo xuất bản hàng ngày ờ thú đô . Giá sứ L à một danh sách có n phàn tử n - 0 . L - al a2 . an Ta gọi n là độ dài của danh sách. Neu n - 1 thì al được gọi là phần từ đầu tiên an được gọi là phần tử cuổi cùng của danh sách L. Neu n 0 thì danh sách L được gọi là danh sách rỗng. Một tính chất quan trọng của danh sách là các phàn tử của nó được sắp tuyến tính neu n 1 thì phần tử a đi trước phần từ aj i. Ta gọi a i 1 2 . n là phần tử ở vị trí thứ i của danh sách. Nghĩa là một danh sách mà quan hệ lân cận giữa các phần tử được hiển thị ra thì danh sách đó được gọi là danh sách tuyến tính. 84 Câu trúc dữ liệu và giai thuật . Các phép toán trên danh sách Khi mô tà một mô hình dữ liệu chúng ta can xác định các phép toán có thể thực hiện trên mô hình toán học được dùng làm cở sở cho mô hình dữ liệu. Có rất nhiều phép toán trên danh sách. Trong các ứng dụng thông thường chúng ta chỉ sử dụng một nhóm các phép toán nào đó. Sau đây là một số phép toán cơ bân trên danh sách tuyến tính. Giả sử L là một danh sách các phần tứ cùa nó có kiểu Item k là vị trí của một phần tử trong danh sách. Các phép toán sẽ được mô tả bởi cảc hàm sau đây ỉ. Khởi tạo danh sách rong void Initialize is L 2. Xác định độ dài cùa danh sách int Length Lứ L 3. Loại phần tử ở vị trí thứ k cùa danh sách void Dc e . int k List L 4. Xen phần từ