Bài giảng Cấu trúc dữ liệu và thuật toán: Chương 3

Bài giảng Cấu trúc dữ liệu và thuật toán: Chương 3 Các cấu trúc dữ liệu cơ bản trình bày các nội dung chính như; Kiểu dữ liệu trừu tượng, các cách cài đặt danh sách tuyến tính, các cách cài đặt hàng đợi, kiểu dữ liệu được đặc trưng,...
Nội dung trích xuất từ tài liệu:
Bài giảng Cấu trúc dữ liệu và thuật toán: Chương 3Chương 3 : Các cấu trúc dữ liệu cơ bảnTrịnh Anh Phúc1 Bộ1môn Khoa Học Máy Tính, Viện CNTT & TT,Trường Đại Học Bách Khoa Hà Nội.Ngày 20 tháng 3 năm 2015Trịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, Viện CNTT & TT, Trường thuậtCấu trúc dữ liệu và giải Đại Học Bách Khoa Hà Nội. ) 3 năm 2015Ngày 20 tháng1 / 78Giới thiệuCác khái niệmKiểu dữ liệu trừu tượngCấu trúc dữ liệuCon trỏ2 Mảng3 Danh sáchĐịnh nghĩaCác cách cài đặt danh sách tuyến tính4 Ngăn xếpĐịnh nghĩaCác cách cài đặt ngăn xếpNgăn xếp và đệ quiỨng dụng5 Hàng đợiĐịnh nghĩaCác cách cài đặt hàng đợiỨng dụng6 Tổng kếtTrịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, Viện CNTT & TT, Trường thuậtCấu trúc dữ liệu và giải Đại Học Bách Khoa Hà Nội. ) 3 năm 2015Ngày 20 tháng12 / 78Các khái niệmKiểu dữ liệuCác kiểu dữ liệu được đặc trưng bởiTập các giá trịCách biểu diễn dữ liệu được sử dụng chung cho tất cả các giá trịTập các phép toán có thể thực hiện trên tất cả các giá trị này.Ví dụ các kiểu dữ liệu trong CKiểuBitsGiá trị nhỏ nhấtGiá trị lớn nhấtcharshortunsigned intlongfloatdouble81616323264-128-327680−231−3.4 × 1038−1.7 × 103081273276765535231 − 13.4 × 10381.7 × 10308Trịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, Viện CNTT & TT, Trường thuậtCấu trúc dữ liệu và giải Đại Học Bách Khoa Hà Nội. ) 3 năm 2015Ngày 20 tháng3 / 78Các khái niệmKiểu dữ liệu trừu tượngKiểu dữ liệu trừu tượng bao gồm :Tập các giá trịTập các phép toán có thể thực hiện trên tất cả các giá trị này.Rõ ràng không có cách biểu diễn dữ liệu chung cho dữ liệu trừu tượngKiểuĐối tượngPhép toánMảngDanh sáchĐồ thịNgăn xếpHàng đợiCâycác phần tửcác phần tửđỉnh, cạnhcác phần tửcác phần tửgốc, lá, cànhkhởi tạo (create), chèn (insert), ...chèn (insert), xóa (delete), tìm (search), ...duyệt (traverse), tìm đường (search path), ...gắp (pop), ấn (push), kiểm tra rỗng, ...vào hàng (enqueue), ra khỏi hàng (dequeue),duyệt (traverse), tìm kiếm (search), ...Trịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, Viện CNTT & TT, Trường thuậtCấu trúc dữ liệu và giải Đại Học Bách Khoa Hà Nội. ) 3 năm 2015Ngày 20 tháng4 / 78Các khái niệmCấu trúc dữ liệuĐịnh nghĩa : Cấu trúc dữ liệu là một họ các biến, có thể có kiểu dữ liệukhác nhau, được liên kết lại theo một cách thức nào đó.Ô (cell) là đơn vị cơ sở cấu thành cấu trúc dữ liệu. Có thể hình dungô như cái hộp đựng giá trị phát sinh từ một kiểu dữ liệu cơ bản hayphức hợp.Cấu trúc dữ liệu đc tạo nhờ đặt tên cho một nhóm (group) các ô vàđặt giá trị cho một số ô để mô tả sự liên kết giữa các ô.Trịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, Viện CNTT & TT, Trường thuậtCấu trúc dữ liệu và giải Đại Học Bách Khoa Hà Nội. ) 3 năm 2015Ngày 20 tháng5 / 78