Cấu trúc dữ liệu và giải thuật (Đỗ Tuấn Anh) - Chương 3. Mảng và danh sách

Ma trận (mảng 2 chiều) là một mảng màmỗi phần tử là một mảng một chiều C lưu trữ mảng nhiều chiều theo thứ tự ưu tiên hàng–mỗi phần tửlàmột hàng Mảng nhiều chiều vẫn được lưu trữ kếtiếp như mảng một chiều.
Nội dung trích xuất từ tài liệu:
Cấu trúc dữ liệu và giải thuật (Đỗ Tuấn Anh) - Chương 3. Mảng và danh sáchCấu trúc dữ liệu và giải thuật Đỗ Tuấn Anh Email: anhdt@it-hut.edu.vnNội dung Chương 1 – Thiết kế và phân tích (5 tiết) Chương 2 – Giải thuật đệ quy (10 tiết) Chương 3 – Mảng và danh sách (5 tiết) Chương 4 – Ngăn xếp và hàng đợi (10 tiết) Chương 5 – Cấu trúc cây (10 tiết) Chương 8 – Tìm kiếm (5 tiết) Chương 7 – Sắp xếp (10 tiết) Chương 6 – Đồ thị (5 tiết)Chương 3 – Mảng và Danh sách1. Mảng2. Danh sách3. Một số phép toán trên danh sách nối đơn4. Các dạng khác của danh sách móc nối5. Sử dụng danh sách móc nối – Ví dụ bài toán cộng đa thức1. Mảng Mảng: Số phần tử cố đinh Kích thước một phần tử cố định Các phần tử mảng phải cùng kiểu Truy cập ngẫu nhiên (theo chỉ số)Mảng: Số phần tử cố địnhKích thước mảng sau khi khai báo là cố địnhVí dụ:void notAllowed ();{ int size; int arr[size]; /* không được phép, kích thước mảng phải là hằng số xác định*/ printf(“Enter the size of the array: “); scanf(“%d”, &size);}Cấu trúc lưu trữ của mảng double x[50]; … x[0] x[1] x[2] x[3] x[49] addr addr + 49 * sizeof(double)Mảng được lưu trữ kế tiếp => truy cập ngẫu nhiên sử dụngchỉ số => tốc độ truy cập tất cả các phần tử là như nhauMảng nhiều chiều double a[5][5]; Ma trận (mảng 2 chiều) làa[0] a[0][0] a[0][1] a[0][2] a[0][4] một mảng mà mỗi phần tử là một mảng một chiềua[1] a[1][0] a[1][1] C lưu trữ mảng nhiều chiều theo thứ tự ưu tiên hàng – mỗi phần tử là một hàng a[4][4]a[4] a[4][0] Mảng nhiều chiều vẫn được lưu trữ kế tiếp như mảng một chiều … a[0][0] a[0][1] a[0][2] a[0][3] a[0][4] a[4][3] a[4][4]addr addr + (i*5+j)*sizeof(double)2. Danh sách Danh sách những người đến khám bệnh Ban đầu chưa có ai Có người mới đến Có người khám xong đi về (Tạo hình ảnh động tại đây)Danh sách tuyến tính Một chuỗi các phần tử Tồn tại phần tử đầu và phần tử cuối Mỗi phần tử có phần tử trước và phần tử sauDanh sách tuyến tính Số phần tử biến đổi Một phần tử thường là một cấu trúc (struct) Thao tác thường xuyên nhất Thêm phần tử Xóa phần tử Các thao tác khác: Tìm kiếm Ghép 2 danh sách Tách 1 danh sách thành nhiều danh sách Sao chép danh sách Cập nhật Phân loại danh sách tuyến tínhNguồn: Data Structures : A Pseudocode Approach With Cby Richard F. Gilberg, Behrouz A. ForouzanThêm một phần tử mớiTìm một phần tửXóa một phần tử khỏi danh sáchLưu trữ danh sách liên kết1. Lưu trữ kế tiếp sử dụng mảng2. Lưu trữ móc nối2.1 Danh sách - Lưu trữ kế tiếp Sử dụng mảng 1 chiều Tìm kiếm dễ dàng (tuần tự hoặc tìm kiếm nhị phân) Duyệt các phần tử dễ dàng sử dụng chỉ số: for(i = 0; i Không biết trước số phần tửLưu trữ kế tiếp - Thêm một phần tử 123 Thêm một phần tử thứ i vào 125 mảng 135 155 - Chuyển các phần tửi 161 i->n xuống các vị trí 165 166 i+1 ->n+1i+1 167 - Thêm phần tử cần 167 thêm vào vị trí thứ i 169n 177 178n+1Lưu trữ kế tiếp - Xóa một phần tử 123 Xóa một phần tử thứ i khỏi 125 mảng 135 - Chuyển các phần tử 155 i+1->n vào các vị tríi 161 i ->n-1 166i+1 167 167 169n-1 177n 178Không hiệu quảViệc lưu trữ liên tiếp ⇒ thao tác thêm và xóa không hiệu quả (dịch chuyển phần tử). 7 21 56 43 22 xóa 21 n/2 lần dịch chuyển (trung bình) 7 56 43 22 Thời gian tính: O(n) Thêm 67 sau 56 Các thao tác thêm và xóa có thời 7 56 67 43 22 gian chạy là O(n).Lưu trữ kế tiếp Ưu điểm: truy cập nhanh (ngẫu nhiên, thời gian truy cập mọi phần tử là như nhau) Nhược điểm: Việc thêm, bớt phần tử rất khó khăn (phải dịch chuyển nhiều phần tử khác) Tốn bộ nhớ, cấp phát nhiều hơn cần thiết để giữ chỗ ...