Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 3: Danh sách - Phạm Thanh An

Ths. Phạm Thanh AnBộ môn Khoa học máy tính - Khoa CNTTTrường Đại học Ngân hàng TP.HCMChương 3DANH SÁCHNội dung trình bàyDanh sách và các phép toán trên danh sáchDanh sách đặcĐịnh nghĩa, Cách biểu diễn và các phép toánƯu và nhược điểm của danh sách đặcTổ chức Stack và Queue theo kiểu danh sách đặcDanh sách liên kếtKhái niệm , Biểu diễn, Các phép toánƯu và nhược điểm Tổ chức Stack và Queue theo kiểu danh sách liên kếtDanh sách liên kết képDanh sáchĐịnh nghĩa danh sáchDanh sách là dãy hữu hạn có thứ tự bao gồm một số biến động các phần tử thuộc cùng một lớp đối tượng nào đó.Mô tả danh sách : L = (a1, a2, . . . ,an)Danh sách tuyến tính: là danh sách mà quan hệ lân cận giữa các phần tử được hiển thịLưu trữ danh sáchTổ chức lưu trữ danh sách trong bộ nhớSử dụng mảng - Danh sách đặcĐối tượng lớp - danh sách liên kếtMỗi node là một đối tượng lớpCác phép toán trên danh sáchThêmLoại bỏ Sắp xếp:Tìm kiếmTách GhépDuyệt:Danh sách đặc (condensed list)Định nghĩaLà danh sách có các phần tử được xếp kế tiếp nhau trong bộ nhớĐặc điểmd: chiều dài mỗi phần tử trong danh sáchl0: địa chỉ của phần tử đầu tiên địa chỉ của phần tử thứ i là: li=l0+(i-1)da1 a2a3.an-1anDanh sách đặc (condensed list)Ưu điểmNhược điểmMảng danh sách đặc phổ biếnMảng một chiều a[ ]Khai báo:Cách 1: [] tên_mảng;Tên_mảng = new [size];Ví dụ: int[] myIntArray; myIntArray = new int[5];int[] numbers; numbers = new int[] {0,1,2,3,4};Hình ảnh mảngHình ảnh một biếnMảng 2 chiềuMảng hai chiều a[,]Khai báo mảng 2 chiều:int[,] grades = new int[2,3]; // 2 hàng, 3 cộtTruy cập phần tử của mảng [dòng, cột]014125Khởi tạo mảng 2 chiềuint[,] grades = new int[,] {{1, 82, 74, 89, 100}, {2, 93, 96, 85, 86}, {3, 83, 72, 95, 89}, {4, 91, 98, 79, 88}}Ví dụ cài đặt danh sáchclass CArray { private int [] arr; private int upper; private int numElements; public CArray(int size) { arr = new int[size]; upper = size-1; numElements = 0; }Mảng danh sách đặc phổ biếnpublic void Insert(int item) { arr[numElements] = item; numElements++; }public void DisplayElements() { for(inti=0;i; p = p.Link; // chuyển sang nút kế } }Bài tậpDùng danh sách liên kết quản lý sinh viên trong lớp (mssv, họ, tên, ngày sinh, điểm tổng kết học kỳ). Thực hiện các thao tác: thêm, bớt, sắp xếp sinh viên (theo điểm tổng kết) trong danh sáchDanh sách liên kết vòngCác thao tác trên danh sách liên kết vòngGiải thuật thêm một nút vào đầu danh sáchGiải thuật thêm một nút vào danh sáchGiải thuật loại một nút ra khỏi danh sáchABXZYHeadDanh sách liên kết képMỗi nút có 2 con trỏ liên kết:Khai báo:ABCDDanh sách liên kết képKhi xóa 1 nút, không cần phải duyệt danh sách để tìm phần tử đứng trướcĐược sử dụng đối với các dữ liệu mà ta cần truy xuất theo cả 2 chiều:Bài tập: Viết các giải thuật, khởi tạo, bổ sung, tìm kiếm, duyệt, xóa trên danh sách liên kết kép.Tổ chức STACK và QUEUEbằng danh sách liên kếtSinh viên tự cài đặt.Tổ chức ngăn xếp (Stack)Tổ chức hàng đợi (Queue)Q&A