BỘ GIÁO DỤC VÀ ĐÀO TẠO ĐẠI HỌC CÔNG NGHỆ TP.HCM Tuc HANH CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT Biên Soạn: TS. Nguyễn Thị Hải Bình www.vn THỰC HÀNH CẤU TRUC DU LIEU VA GIAI THUAT CATT *1.C0S8321* Các ý kiến đóng góp về tài liệu học tập này, xin gửi về e-mail của ban biên tập: tailieuhoctap@hutech.vn Mục Lục mm MỤC LỤC MỤC LỤC. SH HH HT III BÀI 1: MANG — DE QUY «0.1 TOM TAT LÝ THUYẾT .---< ST HT 1 In na .2 THỰC HÀNH CƠ BẢN.1 Mảng dãy số nguyên I0. LEELA EEE E EA EE EEE A EE EEE AEE Staab EEE 10 1.3 THỰC HÀNH NÂNG CAO.
LH TH HH TH HH TH HA HH, 12 -. 15 châu hy nai 0 ẻẽẽ.1 Cấu trúc danh SáCH. -- HH HH HT TS tu tu xE 15 2.2 cấu trúc danh sách liên kết đƠïn. - Qui ch xẻ 16 rà 09) se.1 DSLK đơn với dãy SỐ ngUyÊn.
«cà nh cọ cọ gi ch 17 2.2 DSLK đơn với danh sách sinh VÍÊn.3 THỰC HÀNH NÂNG CAO.-- LH HH HH Hàn HH HH HH Hàn HA, 22 BÀI 3: CẤU TRÚC QUEUE VÀ STACK. 1S S111 ng ng ng ngu 24 chà co hy 0àa án ẽ ẽ ẽ. -- --- HH ng ch ch chớ 24 3.2 THỰC HÀNH CƠ BẢN .--- SH TH TH HH ng 25 3.1 Ứng dụng SIACK. ch TH TH HH HH ch 25 3.2 Ứng dụng QUe€U.
LH HH ng 27 BÀI 4: CẤU TRÚC CÂY — CAY NHI PHAN TIM KIẾM .1 TOM TAT LY THUYET 6 ố ẽẽ. 28 L6? nong ng eeốeeằeeMH.2 THỰC HÀNH CƠ BẢN .-- HH TH HH HH TH HH HH HH Hi, 29 4.1 Cây nhị phâT. co ch TH HH 0 T0 1 tk 880 54 29 29 )0. 30 BÀI 5: CÂY NHỊ PHÂN TÌM KIẾM CÂN BẰNG.---- Ăn HH ng re 34 5.1 TOM TAT hai 0ì 6 .1 Khái niệm mm Mục Lục 5.
- cọ SH TH TH KT ng Si ki ki ki tk rề 5.2 THỰC HÀNH CƠ BẢN 5.3 KIỂM TRA THỰC HÀNH.-- HH HH HH HH HH HH Hà HH 45 863001. 46 HƯỚNG DẪN ia HƯỚNG DẪN MO TA MON HỌC Môn Thực hành cấu trúc dữ liệu cung cấp cho sinh viên những kỹ năng thực hành nâng cao về ngôn ngữ lập trình C. Cung cấp các phương pháp tổ chức và những thao tác cơ sở trên từng cấu trúc dữ liệu, kết hợp với việc phát triển tư duy giải thuật để hình thành nên các ứng dụng thực tế. Học xong môn này, sinh viên phải nắm được các vấn đề sau: — Mảng một và hai chiều, cài đặt các giải thuật đệ quy.
- Cấu trúc dữ liệu danh sách, các phương pháp cài đặt danh sách. Trong đó, chú trọng vào kiểu dữ liệu danh sách liên kết. — Cấu trúc dữ liệu Stack và một số bài toán ứng dụng thực tế của Stack. — Cấu trúc dữ liệu Queue và một số bài toán ứng dụng thực tế của Queue.
— Cấu trúc dữ liệu cây: cây nhị phân, cây nhị phân tìm kiếm, cây nhị phân tìm kiếm cân bằng. NỘI DUNG MÔN HỌC —_ Bài 1: MẢNG - ĐỆ QUY. -_ Bài 2: DANH SÁCH LIÊN KẾT. — Bai 3: CAU TRUC QUEUE VA STACK.
— Bai 4: CAU TRÚC CÂY - CÂY NHI PHAN TIM KIẾM — Bai 5: CAY NHI PHAN TIM KIEM CAN BANG YEU CAU MON HOC Có tư duy tốt về logic và kiến thức toán học cơ bản. Có kiến thức cơ bản về nhập môn lập trình và kĩ thuật lập trình. HƯỚNG DẪN CACH TIEP NHAN NOI DUNG MON HOC Để học tốt môn này, người học cần tập trung tiếp thu bài giảng của môn Cấu trúc dữ liệu và giải thuật, làm tất cả các ví dụ và bài tập. Người học phải dự học đầy đủ các buổi thực hành tại lớp, nắm và cài đặt được các cấu trúc dữ liệu và thuật toán đã thực hành.
Thực hành lại các bài tập cơ bản và nâng cao ở nhà, nghiên cứu tài liệu trước khi đến lớp và gạch chân những vấn đề không hiểu khi đọc tài liệu để đến lớp trao đổi. PHƯƠNG PHÁP ĐÁNH GIÁ MÔN HỌC Môn học được đánh giá gồm: — Điểm quá trình: 30%. Hình thức và nội dung do GV quyết định, phù hợp với quy chế đào tạo và tình hình thực tế tại nơi tổ chức học tập. Hình thức bài thi thực hành.
Nội dung gồm các bài tập liên quan đến kiến thức thuộc bài thứ 1 đến bài thứ 5. BÀI 1: MẢNG - ĐỆ QUY ta BAI 1: MANG - ĐỆ QUY Sau khi thực hành xong bài này, sinh viên có thể nắm được: - _ Ôn lại cách viết một chương trình C dang ham -_ Nắm vững cấu trúc dữ liệu mảng 1 chiều -_ Nắm vững cách thức lập trình đệ quy 1.1 Hàm Cấu trúc chương trình C theo ham: Cấu trúc chương trình C Cấu trúc chương trình C theo ham đơn giản „ „ (không có hàm con) Cách 1 Cách 2 Khai báo thư viện Khai báo thư viện Khai báo thư viện Định nghĩa hằng số Định nghĩa hằng số Định nghĩa hằng số Khai báo các hàm con Các hàm con (nguyên mẫu hàm); Ham main() Ham main() Ham main() { { { Các câu lệnh; Các câu lệnh (bao Các câu lệnh (bao } gồm câu lệnh gọi hàm gồm câu lệnh gọi hàm con ra thực hiện); con ra thực hiện); } } Các hàm con Pa BAI 1: MANG — DE QUY Cach dinh nghia ham: - Binh nghia mét ham bao gồm: Khai báo kiểu hàm, Tên hàm, e Các tham số, e Cac câu lệnh để thực hiện chức năng của hàm. - 2 loai ham: e Ham không trả về giá trị Mẫu hàm Ví dụ nclu tdio.h void xuat(int a) { if (a>0) - printf("Gia tri cua a la: %d", a); void Ten_Ham(danh sach } tham so neu co) t int main() Các câu lệnh; { } int a; printf("Nhap vao mot so nguyen: "); scanf("%d", &a); xuat(a); j ham return 0; } e Ham tra vé gia tri BÀI 1: MẢNG - ĐỆ QUY a Mẫu hàm Ví dụ #Hinclude <stdio.h> int TinhTong(int a, int b) { int kq; kq = a + b; KieuDL Ten_Ham (danh sach ì return kq; tham so neu co) { // Ham ma KieuDL kq; _ main() Các câu lệnh; int a, b, kq; return kq; : : printf("Nhap vao hai so nguyen: "); } scanf("%dXd", 8a, &b); kq = TinhTong(a, b); j ng printf("Tong cua %d va %d la: %d", a, b, kq); return 0; } Tham số của hàm: Loại tham số | Ý nghĩa Ví dụ Giá trị của tham số đầu vào không thay đổi sau khi hàm thực hiện xong. Tham trị // Ham tinh tong hai so nguyen int TinhTong(int a, int b) { int kq; kq = a + b; return kq; | 4 | BAI 1: MANG — DE QUY Loại tham số Ý nghĩa Ví dụ Tham biến Giá trị của tham số đầu vào thay đổi sau khi hàm thực hiện xong.2 Mảng Mảng là một tập hợp các phần tử cố định có cùng một kiểu dữ liệu, gọi là kiểu phần tử.
Kiểu phần tử có thể là có các kiểu bất kỳ: ký tự, số, chuỗi ký tự.; cũng có khi ta sử dụng kiểu mảng để làm kiểu phần tử cho một mảng (trong trường hợp này ta gọi là mảng của mảng hay mảng nhiều chiều). Ta có thể chia mảng làm 2 loại: mảng một chiều và mảng nhiều chiều. Cách khai báo mảng: + Khai báo tường minh (số phần tử xác định): Cú pháp: <kiểu dữ liệu> <tên mảng> [<số phần tử >]; Ý nghĩa: -_ «Tên mảng>: được đặt đúng theo quy tắc đặt tên của danh biểu. Tên này cũng mang ý nghĩa là tên của biến mảng.
BÀI 1: MẢNG - ĐỆ QUY Ra - <Kiéu dữ liệu >: là kiểu dữ liệu của mỗi phần tử của mang + Khai báo không tường minh (số phần tử không xác định) Cú pháp: <kiểu dữ liệu> <tên mảng> [ ]; Kiểu khai báo này thường được áp dụng trong các trường hợp: vừa khai báo vừa gán giá trị, hoặc khai báo mảng là tham số hình thức của hàm.3 Đệ quy Khái niệm: Vấn đề đệ quy là vấn đề được định nghĩa bằng chính nó. Điều kiện để bài toán có thể giải được bằng đệ quy là bài toán tồn tại bước đệ quy và phải có điều kiện dừng. Ví dụ: Bài toán tính tổng S(n) = 1 + 2 +. + n có thể giải bằng đệ quy.+(n- 1) > S(n) = S(n - 1) +n > tồn tại bước đệ quy.
- Khin =0: S(0) = 0 > Có điều kiện dừng. Ham đệ quy trong ngôn ngữ lập trình C: Một hàm được gọi là đệ quy nếu bên trong thân của hàm đó có lời gọi lại chính nó. Cấu trúc hàm đệ quy: Một hàm đệ quy thông thường gồm 2 phần như sau: <Kiểu dữ liệu> <Tên hàm>(<Danh sách tham sốỗ)> { // Phần dừng: xác định điểm kết thúc của thuật toán if (<Điều kiện dừng>}) { return <gia tri>; } // Phần đệ quy Lời gọi tới chính hàm đang định nghĩa. a BAI 1: MANG — DE QUY 1.2 THUC HANH CO’ BAN 1.1 Mang day số nguyên Bài 1: Viết chương trình thực hiện: a.
Nhập mảng gồm n số nguyên (n > 0). Xuất mảng ra màn hình. Tính tổng và trung bình cộng các phần tử của mảng. Sắp xếp mảng theo chiều tăng dần.
Tìm phần tử có giá trị X trong mảng, nếu có cho biết vị trí xuất hiện của X trong mảng. Hướng dẫn: -_ Chương trình minh hoạ nhập xuất mảng số nguyên #include <stdio.h> #define MAX 100 *Hàm nhập số lượng phần tử cho mảng */ void NhapSL(int &n) { dof printf (‘Nhap so phan tu 0<sl<%d: “, MAX); scanf (“ %d ", &n); }while (n<=0 || n>MAX); *Hàm nhập giá trị cho từng phần tử trong mảng */ void NhapMang (int a[], int n) { for (int i = 0; i < nj; i ++) { printf (“ a[%od] = “, i); scanf (" %d *, &a[i]); BÀI 1: MẢNG - ĐỆ QUY } /* wee ee eee ee ee ee ee ee ee ee eee eee *Hàm xuất các phần tử của mảng ra màn hình */ void XuatMang (int a[], int n) { printf (“\nMang gom cac phan tu:\n “); for (int i = 0; i < n; i ++) printf (“ %5d", a[i]); } ( crTrrrrcrrrrrrerrrrrrrrrrrrerrrreer int TinhTong(int a[], int n){.} int main() { int a[MAX], n; NhapMang (a,n); XuatMang (a,n); //goi thực hiện tính tổng và trung bình cộng của các phần tử int tong = TinhTong(a, n); float tbc = TinhTrungBinhCong(a, n); printf("Tong cac phan tu = %od\n”, tong); printf( "Trung binh cong cac phan tu = %0.3f\n”, tbc); int X; printf("Nhap gia tri can tim: "); scanf("%d", &X); //goi thực hiện tìm kiếm X bằng phương pháp tìm tuyến tính int vt=TimTuyenTinh(a,n,X); if (vt==-1) printf("Khong tim thay"); tm BAI 1: MANG — DE QUY else printf("Tim thay %d tai vi tri %d",X, vt); //goi thuc hién sắp xếp mảng sapxep(a,n); printf("Mang sau khi sap tang dan:"); XuatMang(a,n); printf("Nhap gia tri can tim: "); scanf("%d", &X); vt=TimNhiPhan(a,n,X); //tương tự.