Bài giảng 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ử