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

hứ 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