Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 3 - Đỗ Bích Diệp

Bài giảng "Cấu trúc dữ liệu và giải thuật - Chương 3: Mảng và danh sách" cung cấp cho người học các kiến thức: Cấu trúc dữ liệu Mảng (lưu trữ Mảng 1 chiều, lưu trữ Mảng 2 chiều, các phép toán trên cấu trúc Mảng), danh sách tuyến tính (lưu trữ kế tiếp, Lưu trữ móc nối). Mời các bạn cùng tham khảo nội dung chi tiết.
Nội dung trích xuất từ tài liệu:
Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 3 - Đỗ Bích Diệp Cấu trúc dữ liệu và Giải thuật Cấu trúc dữ liệu và Giải thuật Chương III: Mảng và Danh sách Mảng và Danh sách Nội dung – Cấu trúc dữ liệu Mảng z Lưu trữ Mảng 1 chiều z Lưu trữ Mảng 2 chiều z Các phép toán trên cấu trúc Mảng – Danh sách tuyến tính z Lưu trữ kế tiếp z Lưu trữ móc nối Đỗ Bích Diệp- Khoa CNTT- ĐHBKHN 1 Cấu trúc dữ liệu và Giải thuật Kiểu dữ liệu trừu tượng Mảng z Đối tượng của Mảng: – Một tập các cặp (index, item) – Với mỗi giá trị của index sẽ có một giá trị tương ứng của item. – Index là một tập có thứ tự có một chiều hoặc nhiều chiều z Index 1 chiều : {0, 1, 2, …, n-1} z Index 2 chiều : {(0,0) , (0,1), (0,2), …,(0,n), (1,0), (1,1) ….} Kiểu dữ liệu trừu tượng Mảng z Các phép toán – Create(j, list) : tạo mảng có j chiều, list là một j-bộ với phần tử thứ k của list là kích thước chiều thứ k của mảng. – Retrieve(A,i) : Trả ra giá trị của phần tử nhận chỉ số i nếu có – Store(A,i,x) : Trả ra một mảng giống như mảng A đã cho ban đầu, chỉ khác là một cặp (i,x) đã được bổ sung vào vị trí đúng Đỗ Bích Diệp- Khoa CNTT- ĐHBKHN 2 Cấu trúc dữ liệu và Giải thuật Cấu trúc dữ liệu Mảng z Mảng là dãy các phần tử được đánh chỉ số z Khi cài đặt trong máy tính, mảng được lưu trữ trong một dãy các ô nhớ liên tiếp trong bộ nhớ z Kích thước của mảng được xác định khi khởi tạo và không thay đổi z Mỗi phần tử trong mảng có một chỉ số xác định z Truy xuất vào các phần tử của mảng sử dụng chỉ số của phần tử Mảng trong các ngôn ngữ lập trình – Tập chỉ số của mảng có thể khác nhau z C, Java : chỉ số là số nguyên, liên tục, bắt đầu từ 0 z Pascal : chỉ số có thể có giá trị rời rạc z Perl: cho phép chỉ số không phải là số – Mảng có thể là thuần nhất hoặc không thuần nhất – Mảng có thể có thêm các thông tin bổ sung ngoài các phần tử Đỗ Bích Diệp- Khoa CNTT- ĐHBKHN 3 Cấu trúc dữ liệu và Giải thuật Mảng 1 chiều – Khởi tạo z Cần chỉ ra số phần tử của mảng z Khai báo mảng trong C: [size] – int list[5]; – char word[25]; – Tham chiếu z Các phần tử trong mảng 1 chiều được tham chiếu đến sử dụng địa chỉ được tính – int list [5] Æ list[0] địa chỉ cơ sở = α list[1] α + sizeof(int) list[2] α + 2*sizeof(int) list[3] α + 3*sizeof(int) list[4] α + 4*sizeof(int) Mảng 1 chiều int list[] = {0, 1, 2, 3, 4}; Address Value int *ptr; int rows = 5; 1228 0 int i; ptr = list; 1230 1 printf(“Address Value\n”); 1232 2 for (i=0; i < rows; i++) 1234 3 printf(“%8u%5d\n”, ptr+i, *(ptr+i)); printf(“\n”); 1236 4 Đỗ Bích Diệp- Khoa CNTT- ĐHBKHN 4 Cấu trúc dữ liệu và Giải thuật Mảng 2 chiều – Khai báo z Cần chỉ ra số hàng, số cột z Trong C : [size1] [size2] – int table[4][5]; z Truy xuất một phần tử – table[i][ ...