Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 1 – Trần Minh Thái (2017)

Chia sẻ: Nguoibakhong01 Nguoibakhong01 | Ngày: | Loại File: PPTX | Số trang:67

Thêm vào BST

Báo xấu

115
lượt xem 4
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 1: Tổng quan về giải thuật và cấu trúc dữ liệu" cung cấp cho người học các kiến thức: Vai trò của cấu trúc dữ liệu trong một đề án tin học, các tiêu chuẩn đánh giá cấu trúc dữ liệu, kiểu dữ liệu, định nghĩa kiểu dữ liệu, các kiểu dữ liệu cơ bản,... Mời các bạn cùng tham khảo nội dung chi tiết.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 1 – Trần Minh Thái (2017)

CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT Trần Minh Thái Email: minhthai@huflit.edu.vn Website: www.minhthai.edu.vn 1
Nội dung Chương 1. Tổng quan về giải thuật & cấu trúc dữ liệu 1.1. Vai trò của cấu trúc dữ liệu trong một đề án tin học 1.2. Các tiêu chuẩn đánh giá cấu trúc dữ liệu 1.3. Kiểu dữ liệu 1.3.1. Định nghĩa kiểu dữ liệu 1.3.2. Các kiểu dữ liệu cơ bản 1.3.3. Các kiểu dữ liệu có cấu trúc 2
Nội dung Chương 2. Tìm kiếm và sắp xếp 2.1. Nhu cầu tìm kiếm, sắp xếp dữ liệu trong một hệ thống thông tin 2.2. Các giải thuật tìm kiếm nội 2.2.1. Tìm kiếm tuyến tính 2.2.2. Tìm kiếm nhị phân 2.3. Các giải thuật sắp xếp nội 2.3.1. Định nghĩa bài toán sắp xếp 2.3.2. Phương pháp chọn trực tiếp 3
Nội dung Các phương pháp sắp xếp tự nghiên cứu 1. Phương pháp Shaker sort 2. Phương pháp sắp xếp cây (Heap sort) 3. Phương pháp sắp xếp với độ dài bước giảm dần (Shell sort) 4. Phương pháp sắp xếp theo phương pháp trộn trực tiếp (Merge sort) 5. Phương pháp sắp xếp theo phương pháp cơ số (Radix sort) 6. Phương pháp sắp xếp đếm phân khối 4
Nội dung Chương 3. Tổ chức ngăn xếp (Stack) & Hàng đợi (Queue) trên mảng một chiều 3.1. Ngăn xếp 3.1.1. Giới thiệu 3.1.2. Các thao tác trên ngăn xếp 3.1.3. Các ứng dụng Tính các biểu thức đại số Quản lý bộ nhớ khi thi hành chương trình 3.2. Hàng đợi 3.2.1. Giới thiệu 5
Nội dung 3.2.3. Các ứng dụng • Tổ chức bộ đệm bàn phím • Quản lý các tiến trình trong các hệ điều hành • Vét cạn Nội dung sinh viên tự nghiên cứu • Khử đệ quy • Tổ chức lưu vết các quá trình tìm kiếm theo chiều rộng và quay lui 6
Nội dung Chương 4. Cấu trúc dữ liệu động 4.1. Đặt vấn đề 4.2. Kiểu dữ liệu con trỏ 4.2.1. Biến không động 4.2.2. Kiểu con trỏ 4.2.3. Biến động 4.3. Danh sách liên kết 4.3.1. Định nghĩa 4.3.2. Các hình thức tổ chức danh sách 7
Nội dung 4.4. Danh sách đơn 4.4.1. Tổ chức danh sách đơn theo cấp phát liên kết 4.4.2. Các thao tác cơ bản trên danh sách đơn 4.4.3. Sắp xếp danh sách 4.4.4. Các cấu trúc đặc biệt của danh sách đơn 4.5. Một số cấu trúc dữ liệu dạng danh sách liên kết khác 4.5.1. Danh sách liên kết kép 4.5.2. Danh sách liên kết vòng 4.5.3. Danh sách có nhiều mối liên kết 4.5.4. Danh sách tổng quát 8
Nội dung Nội dung sinh viên tự nghiên cứu • Hàng đợi • Ngăn xếp 9
Nội dung Chương 5. Cấu trúc cây 5.1. Cấu trúc cây 5.1.1. Một số khái niệm cơ bản 5.1.2. Một số ví dụ về đối tượng các cấu trúc dạng cây 5.2. Cây nhị phân 5.2.1. Một số tính chất của cây nhị phân 5.2.2. Biểu diễn cây nhị phân T 5.2.3. Duyệt cây nhị phân 5.2.4. Biểu diễn cây tổng quát bằng cây nhị phân 5.2.5. Một cách biểu diễn cây nhị phân khác 10
Nội dung 5.3. Cây nhị phân tìm kiếm. Các thao tác trên cây nhị phân tìm kiếm 5.4. Cây nhị phân cây cân bằng 5.4.1. Cây nhị phân cân bằng hoàn toàn 5.4.2. Cây nhị phân cân bằng 11
Nội dung Chương 6: Bảng băm (Hash Table) Nội dung sinh viên tự nghiên cứu 6.1. Phương pháp băm 6.2. Các hàm băm 6.3. Phương pháp giải quyết đụng độ 6.4. Phân tích bảng băm 6.5. Kết luận so sánh các phương pháp 12
Chương 1 Tổng quan về giải thuật và cấu trúc dữ liệu 13
Mục tiêu • Giới thiệu vai trò của tổ chức dữ liệu • Mối quan hệ giữa GT & CTDL • Các khái niệm và yêu cầu về CTDL • Nhắc lại các kiểu dữ liệu trong C++ • Tổng quan về đánh giá độ phức tạp GT 14
Xét đoạn chương trình sau int main() { int n; printf("Nhap vao so nguyen n: “); scanf(“%d”, &n); if(n%2==0) printf("La so chan”); else printf("La so le“); return 0; 15 }
Khái niệm về kiểu dữ liệu T = V = {Tập các giá trị} O = {Tập các thao tác xử lý} Ví dụ: Kiểu dữ liệu số nguyên int trong ngôn ngữ C T = int V = {-32768, 32767} O = {+, -, *, /, %} 16
Khái niệm về kiểu dữ liệu • Các thuộc tính của một kiểu dữ liệu gồm: • Tên • Miền giá trị • Kích thước lưu trữ • Tập các thao tác tác động lên kiểu dữ liệu đó • Các loại kiểu dữ liệu • Kiểu dữ liệu cơ bản: Cơ sở, mảng, cấu trúc cơ bản • Kiểu dữ liệu có cấu trúc hướng giải quyết vấn đề: Danh sách liên kết, hàng đợi, ngăn xếp, cây, bảng băm, … 17
Khái niệm về kiểu dữ liệu Tĩnh Động • Được định nghĩa ở thời • Được gắn kết với một điểm biên dịch. con trỏ (tại thời điểm biên dịch chưa có). • Được cấp phát ở thời • Phát sinh lúc thực thi. điểm liên kết. • Có thể có giá trị ban đầu • Không xác định giá trị ban tùy theo từng ngôn ngữ lập đầu. trình. • Tồn tại đến khi kết thúc • Được giải phóng khỏi bộ chương trình. nhớ khi cần. 18
Nhắc lại các kiểu dữ liệu C • Kiểu cơ sở: Số nguyên, số thực • Kiểu dãy (mảng), xâu ký tự • Kiểu có cấu trúc 19
Kiểu số nguyên Data type Size Value range 128 đến 127 char 1 byte hoặc 0 đến 255 (Ký tự dạng mã ASCII) unsigned char 1 byte 0 đến 255 signed char 1 byte 128 đến 127 2 hoặc 32,768 đến 32,767 int 4 bytes hoặc 2,147,483,648 đến 2,147,483,647 2 hoặc 0 đến 65,535 unsigned int 4 bytes hoặc 0 đến 4,294,967,295 short 2 bytes 32,768 đến 32,767 unsigned short 2 bytes 0 đến 65,535 long 4 bytes 2,147,483,648 đến 2,147,483,647 20 unsigned long 4 bytes 0 đến 4,294,967,295