Cấu trúc dữ liệu và giải thuật 2008-2009 - Bài 2: Kiểu dữ liệu danh sách

Kiểu dữ liệu danh sách Lê Sỹ Vinh Bộ môn Khoa Học Máy Tính – Khoa CNTT ðại Học Công Nghệ - ðHQGHN Email: vinhioi@yahoo.com Danh sách Danh sách là gì? Danh sách là cấu trúc dữ liệu tuyến tính, trong ñó các phần tử dữ liệu ñược sắp xếp theo một thứ tự xác ñịnh Ví dụ: – Danh sách sinh viên – Danh sách ñiện thoại – Danh sách môn học – Danh sách bài hát – Danh sách công việc Danh sách Trừu tượng hóa cấu trúc danh sách 1. Mô tả dữ liệu A = (a0, a1, …, an) trong ñó ai là phần tử thứ i của danh sách A Ví dụ: A = (1, 2, 3, 3, 4, 5) A = (‘Vinh’, ‘Tuấn’,. ‘Ánh’) 2. Mô tả các phép toán trên cấu trúc danh sách • empty (A): Kiểm tra danh sách có rỗng hay không • length (A): Cho biết số phần tử của danh sách • element (A, i) : Trả phần tử ở vị trí thứ i của A. Ví dụ: A =(1,3,5) Element (A, 0) → 1 Element (A, 2) → 5 Danh sách • insert (A, i, x): Thêm phần tử x vào danh sách A tại vị trí i. A = (a0, a1,…, an) → A = (a0,a1,…,ai-1, x, ai,…an) Ví dụ: A = (1,3,5) insert (A, 1, 4) → A = (1, 4, 3, 5) • append (A, x): Thêm x vào ñuôi danh sách A A = (a , a ,…, a ) → A = (a ,a ,…,a , x)0 1 n 0 1 n Ví dụ: A = (1,3,5) append (A, 8) → A = (1, 3, 5, 8) • delete (A, i): Loại phần tử ở vị trí thứ i trong danh sách A A = (a0, a1,…ai-1, ai, ai+1, an) → A = (a0,a1,…,ai-1, ai+1,…an) Ví dụ: A = (1,3,5) delete (A, 1) → A = (1, 5) Cài ñặt danh sách bằng mảng Mảng (array) • Tập hợp các phần tử (các biến) có cùng một kiểu • Một phần tử cụ thể trong mảng sẽ ñược xác ñịnh và truy cập bởi một chỉ số • Trong C/C++, các phần tử của mạng ñược ñặt cạnh nhau tạo thành một khối liên tục. ðịa chỉ thấp nhất tương ứng với phần tử ñầu tiên, ñịa chỉ cao nhất tương ứng với phần tử cuối cùng • Mảng thì có thể là một chiều hoặc nhiều chiều Cài ñặt danh sách bằng mảng ↑ ↑ ↑ ↑ 0 1 . . . N Max- 1 Mảng một chiều: a0 a1 . . . a n dataType arrayName [Max]; Ví dụ: int scoreArr[100]; student studentArr[100]; Danh sách Tóm tắt về trừu tượng hóa cấu trúc danh sách • Mô tả dữ liệu • A = (a0, a1, …, an) • Mô tả các phép toán trên cấu trúc danh sách • empty (A): Kiểm tra danh sách có rỗng hay không • length (A): Cho biết số phần tử của danh sách • element (A, i) : Trả phần tử ở vị trí thứ i của A. • insert (A, i, x): Thêm phần tử x vào danh sách A tại vị trí i. • append (A, x): Thêm x vào ñuôi danh sách A • delete (A, i): Loại phần tử ở vị trí thứ i trong danh sách A Các phép toán trên cấu trúc danh sách không phụ thuộc vào kiểu dữ liệu của các phần tử trong danh sách!!! Cài ñặt danh sách trong C++ Template 1. Generic function 2. Generic class ListArr project List.h List.cpp Các phép toán khác trên danh sách • Tìm phần tử lớn nhất • ðổi chỗ hai phần tử • Sắp xếp tăng dần Con trỏ (pointer) • Là ñiểm mạnh nhất, nhưng cũng nguy hiểm nhất của C/ C++ • Chứa ñịa chỉ của một tế bào nhớ trong máy tính Giá trị trong ô nhớ 1 2 3 3 1 4 6 5 ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ðịa chỉ ô nhớ 10 11 12 13 14 15 16 17 Con trỏ (pointer) Khai báo con trỏ type * pointerVariable ví dụ: int *p Cấp phát bộ nhớ (allocate memory) pointerVariable = new type (initializer) Ví dụ: p = new int (-1) Giải phóng bộ nhớ delete pointerVariable; ví dụ: delete p (xem ví dụ chương trình) Con trỏ (pointer) Cấp phát bộ nhớ cho một ñối tượng dữ liệu pointerVariable = new objectDataType (xem ví dụ chương trình) Con trỏ (pointer) Cấp phát mảng ñộng pointerVariable = new arrayType[size] ví dụ: int* p; p = new int[10] Giải phóng mảng ñộng delete [] pointerVariable ví dụ: delete [] p; (xem ví dụ chương trình) Danh sách liên kết -1 1 3 2 ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ 11 12 13 14 15 16 17 18 19 20 21 22 Mảng int listArr[4] = {-1, 1, 3, 2} -1 1 3 2 ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ 11 12 13 14 15 16 17 18 19 20 21 22 Danh sách liên kết (-1, 15) → (1, 16) → (3, 21) → (2, NULL) head tail ↑ ↑ Cài ñặt danh sách liên kết Xem chương trình Các phép toán khác trên danh sách liên kết • Tìm phần tử lớn nhất • ðổi chỗ hai phần tử • Sắp xếp tăng dần Mảng và danh sách liên kết • Truy cập phần tử • Thêm phần tử • Xóa phần tử