Bài giảng Cấu trúc dữ liệu và giải thuật: Bài 4 - Hoàng Thị Điệp (2014)

Bài giảng "Cấu trúc dữ liệu và giải thuật - Bài 4: Kiểu dữ liệu trừu tượng danh sách" cung cấp cho người học các kiến thức: Kiểu dữ liệu trừu tượng danh sách - đặc tả, cài đặt bằng mảng tĩnh. 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: Bài 4 - Hoàng Thị Điệp (2014)Bài 4: KDLTT danh sáchcài đặt bằng mảng tĩnhGiảng viên: Hoàng Thị ĐiệpKhoa Công nghệ Thông tin – Đại học Công NghệCấu trúc dữ liệu và giải thuậtHKI, 2013-2014Nội dung chính KDLTT danh sách: đặc tả Cài đặt bằng mảng tĩnh2diepht@vnuDanh sách 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 Danh sách thuần nhất: các phần tử cùng một kiểu 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ệc3diepht@vnuTrừu tượng hóa danh sách1.Đặc tả dữ liệuLà một dãy hữu hạn các phần tử L = (a0, a1, … , an-1)2.Đặc tả các phép toánKiểm tra danh sách có rỗng hay khôngĐếm số phần tử của danh sáchTrả về phần tử ở vị trí thứ i của danh sáchThêm phần tử x vào vị trí i trong danh sáchThêm phần tử x vào đuôi danh sáchLoại phần tử ở vị trí thứ i trong danh sách Ta muốn thiết kế lớp danh sách để người lập trình dùng lớp này cóthể biểu diễn danh sách các phần tử có kiểu tùy ý Generic programming Template trong C++4diepht@vnuTrừu tượng hóa danh sách51.Đặc tả dữ liệuL = (a0, a1, …, an-1)trong đó ai là phần tử thứ i+1 của danh sách LVí dụ:L = (1, 2, 3, 3, 4, 5)L = (‘Vinh’, ‘Tuấn’, ‘Ánh’)2.Đặc tả các phép toánKiểm tra danh sách có rỗng hay không: empty(L)Đếm số phần tử của danh sách: length(L)Trả về phần tử ở vị trí thứ i của danh sách: element(L, i)Thêm phần tử x vào vị trí i trong danh sách: insert(L, i, x)Thêm phần tử x vào đuôi danh sách: append(L, x)Loại phần tử ở vị trí thứ i trong danh sách: erase(L, i)diepht@vnu