zunia.vn

Tuyển sinh 2024 dành cho Gen-Z

zunia.vn

» Công Nghệ Thông Tin

» Cơ sở dữ liệu

Bài giảng Ôn thi tốt nghiệp: Cấu trúc dữ liệu - Trần Ngọc Bảo

Chia sẻ: Năm Tháng Tĩnh Lặng | Ngày: | Loại File: PDF | Số trang:27

Báo xấu

91
lượt xem 7
download

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

Bài giảng Ôn thi tốt nghiệp: Cấu trúc dữ liệu do giảng viên Trần Ngọc Bảo biên soạn giúp người học ôn tập và cũng cố kiến thức về cấu trúc dữ liệu mảng, danh sách liên kết và cấu trúc dữ liệu cây. Đây là tài liệu hữu ích dành cho các bạn sinh viên chuyên ngành Công nghệ thông tin dùng để ôn tập kiến thức chuyên ngành của mình một cách hiệu quả.

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 Ôn thi tốt nghiệp: Cấu trúc dữ liệu - Trần Ngọc Bảo

Đại Học Sư Phạm Tp. Hồ Chí Minh Khoa Toán – Tin Học Ô THI TỐT ÔN Ố NGHIỆP Ệ Cấu ấ trúc dữ liệu Trần Ngọc Bảo Email: tnbao.dhsp@gmail.com
Đại Học Sư Phạm Tp. Hồ Chí Minh Khoa Toán – Tin Học CẤU TRÚC DỮ LIỆU • Cấu trúc dữ liệu mảng • Danh sách liên kết • Cấu trúc dữ liệu cây
Đại Học Sư Phạm Tp. Hồ Chí Minh Khoa Toán – Tin Học CẤU TRÚC DỮ LIỆU • Cấu trúc dữ liệu mảng • Danh sách liên kết • Cấu trúc dữ liệu cây
Cấu trúc mảng một chiều • Các giải thuật tìm kiếm – Tìm kiếm tuần tự (Sequence Search) BÀI GIẢNG ÔN THI TỐT NGHIỆP – Tìm kiếm nhị phân (Binary Search) DỮ LIỆU U • Các giải thuật sắp xếp – Sắp xếp đổi chỗ trực tiếp TRÚC D – Sắp xếp chọn trực tiếp – Sắp xếp chèn trực tiếp CẤU T – Sắp ắ xếp nổi bọt – Sắp xếp nổi bọt cải tiến – Shell sort – Heap sort – Quick sort – Merge sort 4 TRẦN NGỌC BẢO KHOA TOÁN -TIN HỌC ĐẠI HỌC SƯ PHẠM TP.HCM (4)
Cấu trúc mảng một chiều • Yêu Yê cầu ầ BÀI GIẢNG ÔN THI TỐT NGHIỆP – Trình bày ý tưởng giải thuật DỮ LIỆU U – Cho ví dụ minh họa – Biểu diễn giải thuật TRÚC D • Biểu diễn giải thuật bằng mã giả • Biểu diễn giải thuật bằng sơ đồ khối CẤU T – Cài đặt bằng ngôn ngữ C/C++ – Cho biết kết quả thực hiện chạy từng bước giải thuật 5 TRẦN NGỌC BẢO KHOA TOÁN -TIN HỌC ĐẠI HỌC SƯ PHẠM TP.HCM (5)
Giải thuật tìm kiếm tuần tự • Bài toán t á BÀI GIẢNG ÔN THI TỐT NGHIỆP – Cho mảng a có n số nguyên (n ≤ DỮ LIỆU U 100) – Yêu u cầu: u choo biết số nguyên guy x có ó TRÚC D tồn tại trong mảng a không ? • Nếu có cho biết vị trí đầu tiên x xuất CẤU T hiện trong mảng • Ngược g ợ lại ạ thông g báo x không g tồn tại ạ trong mảng. 6 TRẦN NGỌC BẢO KHOA TOÁN -TIN HỌC ĐẠI HỌC SƯ PHẠM TP.HCM (6)
Giải thuật tìm kiếm tuần tự • Ví dụ d BÀI GIẢNG ÔN THI TỐT NGHIỆP – Cho mảng a có 6 phần tử (n = 6) như sau: DỮ LIỆU U 1 5 4 2 3 7 – Yêu Yê cầu: ầ TRÚC D • Tìm x = 3 ? • Tìm x = 10 ? CẤU T – Kết quả: • X = 3 xuất hiện ở vị trí thứ 5 trong mảng • X = 10 không tồn tại trong mảng 7 TRẦN NGỌC BẢO KHOA TOÁN -TIN HỌC ĐẠI HỌC SƯ PHẠM TP.HCM (7)
Giải thuật tìm kiếm tuần tự • Ý tưở tưởng giải iải thuật th ật BÀI GIẢNG ÔN THI TỐT NGHIỆP – Cho mảng a có 6 phần tử (n = 6) như sau: DỮ LIỆU U 1 5 4 2 3 7 TRÚC D CẤU T X= 3 X = 3 xuất hiện ở vị trí thứ 5 trong mảng 8 TRẦN NGỌC BẢO KHOA TOÁN -TIN HỌC ĐẠI HỌC SƯ PHẠM TP.HCM (8)
Giải thuật tìm kiếm tuần tự • Ý tưở tưởng giải iải thuật th ật BÀI GIẢNG ÔN THI TỐT NGHIỆP – Cho mảng a có 6 phần tử (n = 6) như sau: DỮ LIỆU U 1 5 4 2 3 7 TRÚC D CẤU T X= 10 X = 10 không tồn tại trong mảng 9 TRẦN NGỌC BẢO KHOA TOÁN -TIN HỌC ĐẠI HỌC SƯ PHẠM TP.HCM (9)
Giải thuật tìm kiếm tuần tự • Ví dụ – Cho mảng a có 6 phần tử (n = 6) như sau: BÀI GIẢNG ÔN THI TỐT NGHIỆP 1 5 4 2 3 7 DỮ LIỆU U – Yêu cầu: • Tìm x = 3 ? TRÚC D – Kết quả: Lần lặp i a[i] = x ? Kết quả CẤU T 1 0 a[0]=1 ≠ x=3 i=i+1 =1 2 1 a[1]=5 ≠ x=3 i=i+1 =2 3 2 a[2]=4 ≠ x=3 i=i+1 =3 4 3 a[3]=2 ≠ x=3 i=i+1 =4 5 4 a[0]=3 = x=3 Kết thúc gt X = 3 xuất hiện ở vị trí thứ 5 trong mảng TRẦN NGỌC BẢO KHOA TOÁN -TIN HỌC ĐẠI HỌC SƯ PHẠM TP.HCM (10 10))
BÀI GIẢNG ÔN THI TỐT NGHIỆP DỮ LIỆU TRÚC D CẤU T U Giải thuật tìm kiếm tuần tự TRẦN NGỌC BẢO KHOA TOÁN -TIN HỌC ĐẠI HỌC SƯ PHẠM TP.HCM (11 11))
Giải thuật tìm kiếm nhị phân • Bài toán t á BÀI GIẢNG ÔN THI TỐT NGHIỆP – Cho mảng a có n số nguyên (n ≤ DỮ LIỆU U 100) – Yêu u cầu: u choo biết số nguyên guy x có ó TRÚC D tồn tại trong mảng a không ? • Nếu có cho biết vị trí đầu tiên x xuất CẤU T hiện trong mảng • Ngược g ợ lại ạ thông g báo x không g tồn tại ạ trong mảng. – Điều kiện: Mảng a đã đượ đượcc sắp thứ tự tăng TRẦN NGỌC BẢO KHOA TOÁN -TIN12 HỌC ĐẠI HỌC SƯ PHẠM TP.HCM (12 12))
Giải thuật tìm kiếm tuần tự • Ví dụ d BÀI GIẢNG ÔN THI TỐT NGHIỆP – Cho mảng a có 6 phần tử (n = 6) như sau: DỮ LIỆU U 1 2 3 4 5 7 – Yêu Yê cầu: ầ TRÚC D • Tìm x = 3 ? – Kết quả: ả CẤU T • X = 3 xuất hiện ở vị trí thứ 5 trong mảng TRẦN NGỌC BẢO KHOA TOÁN -TIN13 HỌC ĐẠI HỌC SƯ PHẠM TP.HCM (13 13))
Giải thuật tìm kiếm nhị phân • Ví dụ – Cho mảng a có 6 phần tử (n = 6) như sau: BÀI GIẢNG ÔN THI TỐT NGHIỆP 1 2 3 4 5 7 DỮ LIỆU U – Yêu cầu: • Tìm x = 4 ? TRÚC D – Kết quả: Lần lặp l r m=[(l+r)/2] a[m] = x ? Kết quả CẤU T 1 0 5 [(0+5)/2]=2 a[2]=3 < x=4 l=m+1 =3 2 3 5 [(3+5)/2]=4 a[4]=5 > x=4 r=m-1 =3 3 3 3 [(3+3)/2]=3 [( )/ ] a[3]=4 [ ] = x=4 Kết thúc g gt X = 4 xuất hiện ở vị trí thứ 4 trong mảng TRẦN NGỌC BẢO KHOA TOÁN -TIN HỌC ĐẠI HỌC SƯ PHẠM TP.HCM (14 14))
BÀI GIẢNG ÔN THI TỐT NGHIỆP DỮ LIỆU TRÚC D CẤU T U Giải thuật tìm kiếm nhị phân TRẦN NGỌC BẢO KHOA TOÁN -TIN HỌC ĐẠI HỌC SƯ PHẠM TP.HCM (15 15))
Cấu trúc mảng một chiều • Các giải thuật tìm kiếm – Tìm kiếm tuần tự (Sequence Search) BÀI GIẢNG ÔN THI TỐT NGHIỆP – Tìm kiếm nhị phân (Binary Search) DỮ LIỆU U • Các giải thuật sắp xếp – Sắp xếp đổi chỗ trực tiếp TRÚC D – Sắp xếp chọn trực tiếp – Sắp xếp chèn trực tiếp CẤU T – Sắp ắ xếp nổi bọt – Sắp xếp nổi bọt cải tiến – Shell sort – Heap sort – Quick sort – Merge sort TRẦN NGỌC BẢO KHOA TOÁN -TIN16 HỌC ĐẠI HỌC SƯ PHẠM TP.HCM (16 16))
Các giải thuật sắp xếp trên mảng 1 chiều • Yêu Yê cầu ầ BÀI GIẢNG ÔN THI TỐT NGHIỆP – Trình bày ý tưởng giải thuật DỮ LIỆU U – Cho ví dụ minh họa – Biểu diễn giải thuật TRÚC D • Biểu diễn giải thuật bằng mã giả • Biểu diễn giải thuật bằng sơ đồ khối CẤU T – Cài đặt bằng ngôn ngữ C/C++ – Cho biết kết quả thực hiện chạy từng bước giải thuật Demo TRẦN NGỌC BẢO KHOA TOÁN -TIN17 HỌC ĐẠI HỌC SƯ PHẠM TP.HCM (17 17))
Struct và sắp xếp mảng struct • Struct – Cho thông tin học sinh, sinh viên,…là 1 BÀI GIẢNG ÔN THI TỐT NGHIỆP struct có nhiều thông tin DỮ LIỆU U • Sắp xếp danh sách (mảng struct) – Chọn 1 trong các giải thuật sắp xếp trên mảng TRÚC D 1 chiều để sắp xếp các phần tử trong danh sách theo một hoặc nhiều tiêu chí (điều kiện) • Sắp xếp danh sách sinh viên theo họ tên CẤU T • Sắp xếp danh sách sinh viên giảm dần theo điểm tốt nghiệp • Sắp xếp danh sách sinh viên theo họ tên, điểm thi tốt nghiệp Ví dụ TRẦN NGỌC BẢO KHOA TOÁN -TIN HỌC ĐẠI HỌC SƯ PHẠM TP.HCM (18 18))
Đại Học Sư Phạm Tp. Hồ Chí Minh Khoa Toán – Tin Học CẤU TRÚC DỮ LIỆU • Cấu trúc dữ liệu mảng • Danh sách liên kết • Cấu trúc dữ liệu cây
Danh sách liên kết • Cấu trúc tự trỏ – Thành phần dữ liệu: data BÀI GIẢNG ÔN THI TỐT NGHIỆP – Thành phần con trỏ: Next, Previous • Các DỮ LIỆU U á loại l i danh d h sách á h liên liê kết kế – Danh sách liên kết đơn – Danh sách liên kết đôi TRÚC D – Danh sách vòng – Danh sách đa liên kết – Stack/Queue /Q CẤU T • Các thao tác trên sách liên kết – Thêm phần tử – Xóa phần tử – Tìm phần tử trong danh sách – Sắp xếp các phần tử trong danh sách Demo TRẦN NGỌC BẢO KHOA TOÁN -TIN HỌC ĐẠI HỌC SƯ PHẠM TP.HCM (20 20))

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN

TRỢ GIÚP

HỖ TRỢ KHÁCH HÀNG

Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.