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

Đăng ngày | Thể loại: | Lần tải: 0 | Lần xem: 0 | Page: 78 | FileSize: M | File type: PDF
of x

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,.... Cũng như các giáo án bài giảng khác được bạn đọc giới thiệu hoặc do sưu tầm lại và giới thiệu lại cho các bạn với mục đích tham khảo , chúng tôi không thu tiền từ thành viên ,nếu phát hiện tài liệu phi phạm bản quyền hoặc vi phạm pháp luật xin thông báo cho website ,Ngoài thư viện tài liệu này, bạn có thể download giáo án miễn phí phục vụ tham khảo Vài tài liệu tải về mất font không hiển thị đúng, có thể máy tính bạn không hỗ trợ font củ, bạn download các font .vntime củ về cài sẽ xem được.

https://tailieumienphi.vn/doc/bai-giang-cau-truc-du-lieu-va-thuat-toan-chuong-3-11obuq.html

Nội dung


Chương 3 : Các cấu trúc dữ liệu cơ bản
Trịnh Anh Phúc
1 Bộ

1

mô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 2015

Trịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, Viện CNTT & TT, Trường thuật
Cấu trúc dữ liệu và giải Đại Học Bách Khoa Hà Nội. ) 3 năm 2015
Ngày 20 tháng

1 / 78

Giới thiệu

Các khái niệm
Kiểu dữ liệu trừu tượng
Cấu trúc dữ liệu
Con trỏ
2 Mảng
3 Danh sách
Định nghĩa
Các cách cài đặt danh sách tuyến tính
4 Ngăn xếp
Định nghĩa
Các cách cài đặt ngăn xếp
Ngăn xếp và đệ qui
Ứng dụng
5 Hàng đợi
Định nghĩa
Các cách cài đặt hàng đợi
Ứng dụng
6 Tổng kết
Trịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, Viện CNTT & TT, Trường thuật
Cấu trúc dữ liệu và giải Đại Học Bách Khoa Hà Nội. ) 3 năm 2015
Ngày 20 tháng
1

2 / 78

Các khái niệm
Kiểu dữ liệu
Các kiểu dữ liệu được đặc trưng bởi
Tậ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 C
Kiểu

Bits

Giá trị nhỏ nhất

Giá trị lớn nhất

char
short
unsigned int
long
float
double

8
16
16
32
32
64

-128
-32768
0
−231
−3.4 × 1038
−1.7 × 10308

127
32767
65535
231 − 1
3.4 × 1038
1.7 × 10308

Trịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, Viện CNTT & TT, Trường thuật
Cấu trúc dữ liệu và giải Đại Học Bách Khoa Hà Nội. ) 3 năm 2015
Ngày 20 tháng

3 / 78

Các khái niệm
Kiểu dữ liệu trừu tượng
Kiể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ượng
Kiểu

Đối tượng

Phép toán

Mảng
Danh sách
Đồ thị
Ngăn xếp
Hàng đợi
Cây

các phần tử
các phần tử
đỉnh, cạnh
các phần tử
các phần tử
gốc, lá, cành

khở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ật
Cấu trúc dữ liệu và giải Đại Học Bách Khoa Hà Nội. ) 3 năm 2015
Ngày 20 tháng

4 / 78

Các khái niệm

Cấ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ệu
khá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 hay
phứ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ật
Cấu trúc dữ liệu và giải Đại Học Bách Khoa Hà Nội. ) 3 năm 2015
Ngày 20 tháng

5 / 78

1116935

Tài liệu liên quan


Xem thêm