Đề tài Quản lý sinh viên bằng cây nhị phân

TRƯỜNG ĐẠI HỌC DUY TÂN KHOA CÔNG NGHỆ THÔNG TIN ĐỒ ÁN CƠ SỞ CHUYÊN NGÀNH CÔNG NGHỆ PHẦN MỀM TÊN ĐỀ TÀI QUẢN LÝ SINH VIÊN BẰNG CÂY NHỊ PHÂN Giáo viên hưỡng dẫn: Ths. NGUYỄN TẤN THUẬN Người thực hiện: NGUYỄN MINH TRUNG Mã số SV: 162123079 Đà Nẵng,4/2012 TÊN ĐỀ TÀI Chuyên ngành: Công nghệ phần mềm Ngày bắt đầu: 10/4/2012 Ngày kết thúc:10/5/2012 Giảng viên hướng dẫn: THs. Nguyễn Tấn Thuận Sinh viên thực hiện: Nguyễn Minh Trung Mã số: 162123079 Ngày nộp/ nhận xét: Ngày bảo vệ: 29/5/2012 NHẬN XÉT CỦA GIẢNG VIÊN HƯỚNG DẪN LỜI MỞ ĐẦU Trong thế giới hiện nay công nghệ thông tin ngày càng phát triển vượt bậc và ngày càng đạt được thành tựu to lớn trong việc phát triển kinh tế.Trên hầu hết tất cả lĩnh vực thì đều có mặt ngành công nghệ thông tin trong đó, nó đã trở thành một phần thiết yếu trong cuộc sống. Chương trình tin học ứng dụng ngày càng nhiều góp phần thay đổi cuộc sống,nâng cao khả năng chính xác và hoàn thành công việc nhanh chóng. Để có được những chương trình như vậy đòi hỏi người làm tin học phải biết phân tích thiết kế hệ thống, xây dựng một phần mềm quản lý ứng dụng đó. Và những phần mềm đó sẽ trở thành những công cụ hỗ trợ đắt lực nhằm đáp ứng những công việc quản lý nhờ những công cụ có sẵn. Chương trình quản lý sinh viên là một chương trình xây dựng nhằm đáp ứng những nhu cầu quản lý như ghi danh , tìm kiếm, lưu thông tin…và rất nhiều công việc một cách chính xác và nhanh chóng. Với đề tài này giúp chúng ta củng cố lại những kiến thức về cây nhị phân. Đồ án thực hiện dựa trên những kiến thức đã học và tìm kiếm trên internet. Do kiến thức và trình độ còn non kém nên em chưa hoàn thành đầy đủ các công tác quản lý.Trong quá trình thực hiện nếu có sai sót mong thầy cô thông cảm. CHƯƠNG I: CƠ SỞ LÝ THUYẾT 1.1. Lý thuyết đệ quy 1.1.1 Khái niệm: a. Đệ quy: Mặc dù lý thuyết đệ quy đã tồn tại rất lâu từ khi toán học ra đời và phát triển nhưng nó chỉ cho thấy tầm quan trọng và ứng dụng của mình khi con người phát minh ra máy vi tinh và tin học. Trong toán tin một đối tượng là đệ quy nếu nó được định nghĩa qua chính nó hoặc một đối tượng khác cùng dạng bằng quy nạp. vd: Công thức truy hồi của dãy fibonacci.nÎN Nếu n=0 hoặc n=1 thì Fn=1, nếu n>1 thì Fn=Fn-1+Fn-2 b. Thuật toán đệ quy trong tin học: Thuật toán đệ quy là một thuật ngữ tin học chỉ các bước thực hiện giải bài toán, hoặc đối tượng nào đó bằng đệ quy.Một bài toán giải được thông qua cách xác định những trường hợp đặc biệt và tính quy nạp của nó được gọi là bài toán đệ quy. Nói cách khác giải một bài toán đệ quy là việc chia nhỏ lời giải thành những bài toán con “tầm thường” dễ giải hơn.Và thuật toán tương ứng với lời giải như vậy gọi là thuật toán đệ quy. c. Cấu trúc của thuật toán đệ quy: Định nghĩa một hàm đệ quy gồm hai phần: - Phần neo: Xác định những trường hợp đăc biệt của bài toán, đối tượng.Là phần thực hiện những công việc rất đơn giản, có thể giải trực tiếp mà không cần đến bài toán con nào cả. Phần này cũng quyết định tính hữu hạn của thuật toán. - Phần đệ quy: Để gọi đệ quy những bài toán con và phối hợp chúng lại nhằm tìm ra lời giải chính trong trường hợp chưa giải được bằng phần neo. vd: Trong công thức của dãy fibonacci phần neo là trường hợp n=0 và n=1,phần để gọi đệ quy chính là công thức Fn=Fn-1+Fn-2. d.Các loại đệ quy: Có 2 loại: Đệ quy trực tiếp và đệ quy gián tiếp - Đệ quy trực tiếp là loại đệ quy mà đối tượng được mô tả trực tiếp qua nó: A mô tả qua B, C,.. trong đó B, C, … không chứa A. - Đệ quy gián tiếp là loại đệ quy mà đối tượng được mô tả gián tiếp qua nó: A mô tả qua A1, A2, …, An. Trong đó có một Ai được mô tả qua A. 1.1.2. Ưu và nhược điểm của thuật toán đệ quy: Bên cạnh nhiều giải thuật khác như giải lặp, quy hoạch động, vét cạn...đệ quy vẫn là một công cụ rất hữu ích để xử lý các số liệu.Một ưu điểm quan trọng là không giới hạn số vòng lặp nên sẽ mở rộng được khả năng xử lý số liệu đầu vào.Ngoài ra, có nhiều đối tượng mà việc xây thuật toán đệ quy đơn giản hơn nhiều so với các các thuật toán khác như lặp. Mặc dù vậy một số bài toán hay đối tượng khi được lập trình trên máy tính bằng thuật toán đệ quy thì gây tốn bộ nhớ và thời gian thực hiện quá lâu đối với những số liệu lớn.Nguyên nhân cơ bản là vì bản chất của đệ quy thực chất là một dây chuyền mà trong đó các lệnh đệ quy khi thực hiện thì trình dịch phải chuyển các mã lệnh thành các thủ tục được xếp chồng lên nhau rồi mới xử lý chúng theo thứ tự. Nếu một thuật toán đệ quy đòi hỏi máy tính thực hiện số lượng lớn các thủ tục đặc biệt như các hàm mũ thị thời gian thực hiện và bộ nhớ tương đương cũng phải lớn. 1.2. Cấu trúc dữ liệu cây 1.2.1. Cây tổng quát: A B C D D D C D D a. Khái niệm: Cây là một cấu trúc lưu trữ trong đó các phân tử của cây (gọi là các nốt) có cùng kiểu dữ liệu. Mỗi nốt gồm dữ liệu và các liên kiết đến nốt khác.Giữa các nốt có quan hệ phân cấp gọi là “quan hệ cha con”. Trong cây có một nốt đặc biệt gọi là node gốc không là con của bất kỳ nốt nào. Cây có thể định nghĩa bằng đệ quy như sau: - Mỗi nốt là một cây, nó cũng là nốt gốc của cây đó. - Nếu n là một nốt và n1,n2,...nk lượt là nốt gốc của các cây T1,T2,...Tk .Và cho nốt n trở thành nốt cha của các nốt n1,n2,...nk thì ta sẽ được một cây mới T. Cây này có nốt gốc là n, các cây T1,T2,...Tk trở thành các cây con của nốt gốc n. - Cây không có nốt nào gọi là cây rỗng. b. Các khái niệm liên quan: Mức của cây: Người ta quy ước nốt gốc có mức 1, nếu nốt cha có mức i thì nốt con có mức i+1. Chiều cao của cây: Là mức cao nhất của các nốt trong cây. Bậc của nốt: là số nốt con của cây đó. Bậc của cây: là số bậc cao nhất của các nốt trong cây. Nốt lá: là nốt không có cây con (bậc bằng 0). Nốt nội (nốt trong): là nốtt trên cây có ít nhất một con. c. Các cách biểu diễn cây: Có 2 cách thông dụng để biểu diễn cấu trúc cây trên máy tính là bằng mảng hoặc bằng cấu trúc liên kết.Ở đây ta chỉ quan tâm tới biểu diễn bằng cấu trúc liên kết. A B D C A B C E Hình 2: bằng cấu trúc liên kết Hình 3: Bằng mảng Khi biểu diễn bằng cấu trúc liên kết mỗi nốt trong cây là một trường gồm các ghi trong đó: -Trường data chứa dữ liệu lưu tại nút đó.Dữ liệu có thể là một giá trị đơn giản hoặc một cấu trúc dữ liệu phức tạp. - Trường liên kết chứa thông tin đến các cây con khác.Tuỳ vào loại cây mà số thường liên kết có thể thay đổi. 2.2. Cây nhị phân: a.Khái niệm: data Cây nhị phân là một trường hợp quan trọng của cấu trúc cây. Mọi nốt trên cây nhị phân đều có tối đa hai cây con có phân biệt thứ tự là cây con trái và cây con phải.Cấu trúc như sau: - Trường data : chứa dữ liệu right left - Trường left : chứa liên kết tới nốt con trái.Trường hợp không có con trái trường này được gán 1 giá trị đặc biệt (trong ngôn ngữ C là NULL). - Trường right : chứa liên kết tới nốt con phải.Trường hợp không có con phải trường này được gán 1 giá trị đặc biệt (trong ngôn ngữ C là NULL). b. Các dạng đặc biệt của cây nhị phân: Hình 4: Một nốt của cây nhi phân Cây nhị phân suy biến: các nốt không phải là lá chỉ có một nhánh con. Các trường hợp của cây nhị phân suy biến : 4 6 5 4 3 2 1 2 3 Hình 5: Cây lệch trái Hình 6: Cây lệch phải Hình 7:Cây zích zắc Cây nhị phân hoàn chỉnh: Các mức nhỏ hơn h-1 đều có 2 con (với h là chiều cao của cây). Cây cân bằng: Là cây nhị phân thoả mãn điều kiện với mọi nốt của cây thì chiều cao con trái và chiều cao con phải hơn kém nhau không quá 1. 2.3. Cây nhị phân tìm kiếm (BST): a.Định nghĩa: Cây nhị phân tìm kiếm là cây nhị phân có giá trị khoá tìm kiếm (key) tại mỗi nốt đều lớn hơn giá trị key của mọi nốt thuộc cây con trái và nhỏ hơn giá trị key của mọi nốt thuộc cây con phải. b. Các tính chất: - Với cây thông thường để tìm 1 giá trị trong cây có n nốt thì độ phức tạp sẽ là O(n). Còn đối với cây BST thì số lần tìm kiếm tối đa bằng chiều cao của cây tương đương với độ phức tạp O(log2n) rất thuận tiện cho thao tác tìm kiếm. - Cây BST khi duyệt trung tự thì các giá trị được sắp xếp tăng dần. - Giá trị nhỏ nhất trong cây nằm ở bên trái nhất, giá trị lớn nhất nằm phía bên phải nhất của cây. 3.Thuật toán và sơ đồ khối: Cây Nhị phân tìm kiếm (BST): 3.1. Tạo cây BST: -Hàm chèn một giá tri vào cây BST: Sơ đồ khối: end begin T=NULL T=new SinhVien T->info=x T->left=T->right=null T->info>x T=T->left T->right<x T=T->right S Đ S Đ S S Đ Thuật toán: B1: Nếu cây rỗng. B1.1: Tạo nốt mới. B1.2: Gán cây bằng nốt vừa tạo. B2: Ngược lại nếu giá trị chèn nhỏ hơn giá trị của cây thì chèn vào bên trái của cây. B3: Ngược lại nếu giá trị chèn lớn hơn giá trị của cây thì chèn vào bên phải của cây. B4: trùng giá trị đã có thì báo đã có trong cây. Ví dụ : Chèn giá trị 5 vào cây BST sau : Hình 38: Chèn BST. - Khi gọi hàm chèn vì 5 <8 nên hàm gọi đệ quy chèn bên trái của cây 8. - Tương tự 5>4 nên hàm tiếp tục gọi đệ quy chèn bên phải cây 4. - 5<6 chèn bên trái cây 6. Hình 39: Chèn BST. -Vì con trái của 6 rỗng nên hàm tạo nốt mới có giá trị bằng 5 và gán vào con trái của 6. - Kết thúc. -Hàm tạo cây BST: Đầu vào: Cây T rỗng. Đầu ra: Cây BST không chứa giá trị 0. Thuât toán: B1: Khai báo biến nhập. B2: Tạo một cây rỗng. B3: Lặp cho tới khi biến nhập = 0. B3.1: Nhâp giá trị chèn. B3.2: Gọi hàm chèn. 3.2. Các phép duyệt : Đầu vào: Cây nhị phân lưu các số nguyên. Kết quả: xuất ra màn hình 1 dãy các giá trị của cây cần duyệt. 3.2.1 Duyệt tiền tự: Sơ đồ khôi: begin end T!=null T=T->left T->info T=T->right T==null S Đ S Đ Thuật toán: B1: Trong khi cây khác rỗng: B1.1: xuất ra giá trị của cây. B1.2: gọi hàm đệ quy duyệt cây con trái. B1.3: gọi hàm đệ quy duyệt cây con phải. 3.2.2 Duyệt trung tự: Sơ đồ khối: begin end T!=null T=T->left T->info T=T->right T==null S Đ S Đ Thuật toán: B1: Trong khi cây khác rỗng: B1.1: gọi hàm đệ quy duyệt cây con trái. B1.2: xuất ra giá trị của cây. B1.3: gọi hàm đệ quy duyệt cây con phải. 3.2.2 Duyệt hậu tự: Sơ đồ khối: begin end T!=null T=T->left T->info T=T->right T==null S Đ S Đ Thuật toán: B1: Trong khi cây khác rỗng: B1.1: gọi hàm đệ quy duyệt cây con trái. B1.2: gọi hàm đệ quy duyệt cây con phải. B1.3: xuất ra giá trị của cây. Ví dụ minh hoạ thuật toán: Hình 12:Ví dụ về duyệt cây Duyệt tiền tự : Gọi hàm duyệt tiền tự cây T. Xuất số 10 ra màn hình. Gọi hàm duyệt tiền tự quy T->left đến nốt 20 (hàm con đệ quy của nốt 10). Xuất số 20 ra màn hình. Gọi hàm duyệt tiền tự T->left đến nốt 30 (hàm con đệ quy của nốt 20). Xuất số 30 ra màn hình. Gọi hàm duyệt tiền tự T->left đến NULL. Gọi hàm duyệt tiền tự T->right đến NULL. Gọi hàm duyệt tiền tự T->right đến nốt 40 (hàm con đệ quy của nốt 20). Xuất 40 ra màn hình. Gọi duyệt tiền tự T->left đến NULL. Gọi hàm duyệt tiền tự T->right đến NULL. Gọi hàm duyệt tiền tự T->right đến 50 (hàm con của nốt 10). Xuất 50 ra màn hình. Gọi hàm duyệt tiền tự T->left đến NULL. Gọi hàm duyệt tiền tự T->right đến 60 (hàm con của nốt 50). Xuất 60 ra màn hình. Gọi hàm duyệt tiền tự T->left đến NULL. Gọi hàm duyệt tiền tự T->right đến NULL. Kết thúc. Vây kết quả sau khi duyệt tiền tự cây T sẽ là:10 20 30 40 50 60 Tương tự ta với hàm duyệt trung tự kết quả là: 30 20 40 10 50 60 Duyệt hậu tự : 30 40 20 60 50 10 3.3. Các thao tác đếm : Đầu vào: Cây nhị phân lưu các số nguyên Đầu ra: Trả về số lượng các nốt tương ứng (tất cả, số nốt lá,nốt nội...)tuỳ vào các hàm dưới đây. 3.3.1. Đếm tất cả các nốt trên cây: Để tính số nốt của cây ta cần tính số nốt của cây con trái và phải.Khi đó tổng nốt sẽ bằng tổng nốt của các cây con cộng thêm 1. Sơ đồ khối: begin end T!=null T->left!=null T=T->left T->right!=null T=T->right d=1 d++ Đ S S Đ S Đ Thuật toán : B1: Nếu cây rỗng trả về 0. B2: Ngược lại trả về 1 cộng với hàm đếm nốt cây con trái cộng tiếp với hàm đếm số nốt cây con phải. Ví dụ minh hoạ thuật toán : Đếm số nốt của cây T. Hình 13: Đếm tất cả các nốt. 1. Số nốt của cây T=1+ số nốt cây con trái 20 + số nốt cây con phải 50. 2. Số nốt cây 20 = 1+ số nốt cây con trái 30 + số nốt con phải 40. 3. Số nốt cây 30 = 1 + 0 (cây rỗng ) + 0 (cây rỗng). 4. Số nốt cây 30=1. 5. Số nốt cây 40 = 1 + 0 (cây rỗng ) + 0 (cây rỗng). 6. Số nốt cây 40=1. 7. Số nốt cây 20=3. 8. Số nốt cây 50 = 1+ 0(cây rỗng) + số nốt con phải 60. 9. Số nốt cây 60 = 1 + 0 (cây rỗng ) + 0 (cây rỗng). 10. Số nốt cây 60 =1. 11. Số nốt cây 50 =2. 12. Số nốt cây T(cây 10)=6. 13. Kết thúc. Vậy kết quả hàm trả về là bằng 6. 3.4. Xoá 1 nốt của cây BST. end begin T!=Null T->info=x T->left=null T->right=null Tree *p=T Free(p) T=null Tree *p=T->left Tree *q=T q=p p=p->right p->right!=Null T->info=p->info T=p x=p->info T->info<x T=T->left T=T->right T->left!=null Tree *p=T T=T->right Free(p) Sơ đồ khối: Đ S S Đ Đ S Đ S Đ S Đ Thuật toán: (giá trị xóa được xác định dựa vào mã số sinh viên) B1: Nếu cây rỗng báo không xoá được. B2: Ngược lại (tìm được giá trị cần xoá): B2.1: Nếu cây là lá thì xoá cây. B2.2: Nếu cây chỉ có con trái thì gán cây =con trái. B2.3: Nếu cây chỉ có con phải thì gán cây =con phải. B2.4: Trường hợp cây có 2 con thực hiện 1 trong 2 cách: - Tìm giá trị lớn nhất bên con trái thay vào cây sau đó xoá giá trị lớn nhất bên con trái cây vừa thay. - Hoặc tìm giá trị nhỏ nhất bên con phải thay vào cây sau đó xoá giá trị nhỏ nhất bên con phải cây vừa thay. B3: Ngược lại nếu giá trị xoá > hơn giá trị của cây thì chuyển sang xoá bên phải của cây. B4: Ngược lại nếu giá trị xoá < hơn giá trị của cây thì chuyển sang xoá bên trái của cây. Ví dụ: Xoá nốt 10 trên cây nhị phân sau : Hình 40: Xoá nốt cây BST. 10 >5, chuyển sang xoá bên phải cây. Hình 41: Xoá nốt cây BST. - Tìm được nốt 10 trong cây. - 10 có 2 cây con. - Tìm giá trị nhỏ nhất bên con trái của cây 10. - 9 là giá trị lớn nhất bên con trái. - Gán nốt 10= 9. Hình 42: Xoá nốt cây BST. - Tìm xoá nốt 9. - Kết quả sau khi xoá như hình trên. 3.5.Kiểm tra cây có phải cây BST không: Dùng mảng một chiều lưu các giá trị của cây khi duyệt trung tự , nếu mảng được được lưu theo thứ tự tăng dần thì cây vừa được xử lý là BST. -Hàm sao chép các giá trị của cây sang mảng mộ chiều:: Đầu vào: Cây nhị phân T lưu số nguyên, mảng một chiều a, một biến n lưu kích thước mảng (ban đầu bằng 0). Đầu ra: Mảng a (lưu các giá trị của cây ) có kích thước n (bằng số nốt trên cây). B1: Trong khi cây khác rỗng: B1.1: gọi hàm đệ quy cho cây con trái. B1.2: Tăng kích thước mảng lên 1. B1.3: Gán giá trị của cây vào mảng. B1.4: gọi hàm đệ quy cho cây con phải. Ví dụ: Cây nhị phân T. Hình 32: Sao chép sang mảng. Kết quả lưu trên mảng: Hình 33: Cây mảng cây T. + Hàm kiểm tra cây BST: Đầu vào: Cây nhị phân T. Đầu ra: Trả về 1 (nếu là cây BST) hoặc 0 (không phải cây BST). Thuật toán: B1: Khai báo mảng a kích thước ban đầu n=0. B2: Gọi hàm chuyển sang mảng cây T. B3: Lặp i từ 1 đến n. Nếu a[i] >a[i+1] trả về không. B4: Trả về 1 3.6.Kiểm tra nốt gốc có lớn hơn mọi nốt trong cây hay không: Đầu vào: Cây nhị phân lưu các số nguyên không có 2 nốt cùng giá trị. Đầu ra: Trả về 0(nếu cây rỗng hoặc nốt gốc không lớn nhất) hoặc 1 nếu nốt gốc là lớn nhất. Muốn kiểm tra xem nốt gốc của cây có lớn hơn mọi nốt trong cây hay không ta phải xây dựng hàm tìm giá trị lớn nhất trong cây và hàm so sánh giả trị này với nốt gốc của cây. Thuât toán: -Hàm tìm giá trị lớn nhất trong cây: B1: Nếu cây rỗng trả về 0. B2: Ngược lại nếu cây là không có cây con nào thì trả về giá trị của cây. B3: Ngược lại khai báo m = giá trị của cây. B3.1: Nếu con trái khác rỗng khai báo mleft = giá trị lớn nhất của con trái.Nếu mleft >m thì m=mleft. B3.1: Nếu con phải khác rỗng khai báo mright =giá trị lớn nhất của con phải. Nếu mleft >m thì m=mright. B4: Trả về m. Ví dụ minh hoạ: Tìm giá trị lớn nhất của cây T. Ghi chú: m là giá trị lớn nhất như trong thuật toán. Hình 31: Tìm giá trị lớn nhất. Kết quả cuối cùng trả về m=60. -Hàm kiểm tra nốt gốc có lớn nhất không: B1: Nếu cây rỗng trả về 0. B2: Ngược lại nếu nốt gốc lớn hơn hoặc bằng giá trị lớn nhất của cây thì trả về 1 B3: Còn lại trả về 0. 3.7.Tính tổng các giá trị của cây: Để tính tổng nốt của cây ta phải tính tổng nốt của các cây con ,khi đó tổng nốt của cây bằng giá trị của cây cộng với tổng nốt các cây con. Thuật toán: B1: Nếu cây rỗng trả về trả về 0. B2: Ngược lại thì trả về giá trị của cây cộng với tổng cây con phải cộng với tổng cây con trái. Ví dụ : Tính tổng cây T. Hình 29: Tính tổng các nốt. Kết quả: Tổng các nốt cây T bằng 210. 3.8.Tìm chiều cao của cây: Để tính chiều cao của cây ta phải tính chiều cao của các cây con, khi đó chiều cao của cây bằng chiều cao lớn nhất của các cây con cộng thêm 1. Thuật toán : B1: Nếu cây rỗng thì chiều cao bằng 0. B2: Ngược lại: B2.1: Khai báo h1=chiều cao cây con trái. B2.2: Khai báo h2=chiều cao cây con phải. B2.3: Nếu h1>h2 thì trả về h1+1. B2.4: Ngược lại trả về h2+1. Ví dụ :Tìm chiều cao của cây T. Hình 28: Tìm chiều cao cây. Kết quả : Chiều cao cây T bằng 3. CHƯƠNG II: XÂY DỰNG ỨNG DỤNG QUẢN LÝ SINH VIÊN BẰNG CÂY NHỊ PHÂN BST 2.1.Đặc tả bài toán Cây có ứng dụng trong rất nhiều giải thuật trong tin học.Ta có thể thấy tầm quan trọng của cấu trúc dạng cây trên rất nhiều mặt.Trong tự nhiên có thể lấy một ví dụ điển hình nhất đúng như tên gọi của nó chính là các cây xanh, chúng có được sức sống rất tốt là nhờ khả năng vận chuyển chất từ gốc tới tất cả các điểm là của cây ,ưu điểm mà con người vận dụng trong khoa học củ thể là khoa học máy tính. Có thể lấy một ví dụ khác hãy coi đại dương là nguồn,các nốt là các cửa sông và các giao điểm cúa các con sông ,sông và suối,một cách bao quát đại dương,sông, suối-dòng chảy duy trì sự sống trên trái đất cũng dùng cấu trúc đặc biệt này.Trong các ngành khoa học ,”Cây” cũng được ứng dụng rất sâu rộng như cây gia phả các dòng họ,biểu diễn các hợp chất hoá học,sắp xếp mục lục, hay bản đồ tư duy-một công trình khoa học nổi tiếng giúp tối ưu khả năng tư duy sánh tạo của con người cũng áp dụng cây biểu đồ.Còn trong lĩnh vực toán tin cây được định nghĩa là một đồ thị liên thông không có chu trình, giúp giải quyết rất nhiều thuật toán về tìm kiếm, sắp xếp ,tính các biểu thức...Và để tìm hiểu sâu hơn về giải thuật đệ quy trên khía cạnh tin học đề tài sẽ sử dụng cây nhị phân-một trường hợp đặc biệt của cây làm mục tiêu nghiên cứu. Cây nhị phân BST là một trong những cấu trúc dữ liệu cơ bản và rất quan trọng trong lập trình.Ở đây ta sẽ tạo một hệ thống quản lý sinh viên bằng cây nhị phân BST gồm những thao tác cơ bản trên cây nhị phân bằng thuật toán đệ quy như tạo,duyệt cây nhị phân và cây nhị phân tìm kiếm, một số thao tác đếm, tìm kiếm,chèn... 2.Yêu cầu bài toán Mục đích đề tài: Xây dựng và tạo được chương trình quản lý sinh viên bằng cây nhị phân BST. Nội dung đề tài: - Chương trình tạo ra có thể thực hiện đầy đủ các công việc của người quản lý sinh viên: Nhập, xóa, thêm, tìm kiếm,sắp xếp. - Mỗi sinh viên phải đảm bảo đầy đủ các thông tin: mã số sinh viên, tên sinh viên,ngày/tháng/năm sinh,giới tính, lớp, quê quán - Hệ thống phải đảm bảo mọi công việc phải được thao tác trên vùng dữ liệu chung. -Các thao tác phải rõ ràng, dễ sử dụng. Phân tích: Yêu cầu quan trọng nhất của đề tài đặt là nắm vững lý thuyết đệ quy, đặc biệt là giải thuật đệ quy trong tin học.Thứ hai là cấu trúc dữ liệu cây trong đó củng cố và tìm hiểu kỹ về cây nhị phân gồm định ngĩa, các khái niệm liên quan đến cây nhị phân. Cuối cùng là ứng dụng các thuật toán đệ quy để cài đặt một số bài toán trên cây nhị phân, chương trình được viết bằng ngôn ngữ C. Chương trình được thực hiện trên ngôn ngữ lập trình C++, chương trình sẽ bao gồm các thao tác thực hiện trên cây nhị phân. Với các thuật toán ứng dụng sẽ thể hiện rõ được các thuộc tính cũng như đặt trưng trên cây vào bài toán quản lý sinh viên. Chương trình được thiết kế ở dạng menu, trên menu bao gồm các chức năng của chương trình như: Đọc dữ liệu từ file, thêm sinh viên vào danh sách, tìm sinh viên, liệt kê các sinh viên , xóa sinh viên, lưu dữ liệu vào file. 3. KHAI BÁO CẤU TRÚC DỮ LIỆU QUẢN LÝ SINH VIÊN 3.1.Cây nhị phân là một kiểu dữ liệu tự định ngĩa: Đệ tạo ra môt cấu trúc cây nhị phân quản lý sinh viên gồm các trường: mã số,họ tên,giới tính,năm sinh,lớp,địa chỉ trên máy tính , với ngôn ngữ C ta định nghĩa cây nhị phân là một kiểu dữ liệu gồm trường chứa thông tin xử lý là kiểu số nguyên,kiểu ký tự, hai trường chứa địa chỉ tới con trái và con phải của cây. Có thể khai báo như sau: struct SinhVien { int maso; char name[30]; char ngaysinh[20]; char gioitinh[5]; char lop[10]; char diachi[50]; Tree *left, *right; }; Cây nhị phân là một kiểu cấu trúc trên lý thuyết không giới hạn số lương phần tử. 3.2. Khai báo toàn cục: Gồm hai cấu trúc kiểu cây được khai báo trong chương trình đệ quy xử lý trên cây nhị phân tìm kiếm. Cây nhị phân tìm kiếm BST: Khai báo:SinhVien *T; Sử dụng trong các thao tác tạo, duyệt, chèn và xoá của menu cây BST. int x;char H[30];char date[20];char G[5];char L[10];char D[50] là các mảng dùng để gán dữ liệu trong các thao tác thêm, chèn. 4. LẬP TRÌNH 4.1. Các bước lập trình. - Nội dung chương trình là cài đặt các thao tác trên cây nhị phân bằng giải thuật đệ quy nên bước đầu tiên thực hiện là nhóm các thao tác tương tự nhau thành các menu con (chương trình gồm 8 menu tác vụ đã nêu ở phần phân tích hệ thống) - Sau khi nhóm các tác vụ thành các menu con phần việc tiếp theo là xây dựng thuật toán bằng ngôn ngữ tự nhiên cho các tác vụ của từng menu. - Mỗi tác vụ con sẽ thực hiện tuần tự các bước từ ý thưởng thuật toán , lập mã giả , viết mã của chương trình và cuối cùng là kiểm thử. 4.2. Ghi chú: - Trong mã chương trình mỗi menu sẽ được thông báo ở trước các hàm của menu đó. 4.3. Mã chương trình (code): - Phần code của chương trình vì hầu hết được viết bằng giải thuật đệ quy nên rất ngắn gọn, giảng viên có thể xem thông các trình soạn thảo C++ (C Free, DevC...). 4.4.Đọc dữ liệu từ file: Sơ đồ khối: begin end f=fopen(file, “r”) F==Null !feof(f) fgets(data,100,f); chenDS(data,T); Đ S Đ S Thuật toán: B1:mở file để đọc dữ liệu. B2:kiểm tra file B.2.1.Nếu không có sinh viên nào thông báo ra màn hình file trống B.2.2.Ngược lại nếu file có dữ liệu thì toàn bộ dữ liệu sẽ được tải lên cây nhị phân. Code: void docfile(char *filename,SinhVien *&T){ FILE *f=fopen(filename,"r"); If(f==NULL) cout<< “khong co du lieu”; while(!feof(f)){ char maso[30];//fscanf(f,"%d",&x); fgets(maso,100,f); x=atoi(maso); fgets(H,100,f); fgets(date,100,f); fgets(G,100,f); fgets(L,100,f); fgets(D,100,f); chenDS(x,H,date,G,L,D,T); } fclose(f); } 4.5.Hệ thống menu chương trình: Menu Tìm sinh viên theo mã số In danh sách Thêm sinh viên Sửa thông tin sinh viên Xóa sinh viên Đếm số sinh viên Lưu chương trình Thoát chương trình Chương trình sẽ thực hiện các thao tác và mộ số bài toán cơ bản trên cây nhị phân có trường dữ liệu là các số nguyên và ký tự. Sơ đồ hệ thống chương trình (đươc minh hoạ ở hình 8 ) gồm menu chính hiển thị đường dẫn đến các menu tác vụ nhỏ hơn: -Menu nhập sinh viên: Tạo ra một cây nhị phân bằng cấu trúc liên kết lưu trữ các số nguyên và kí tự. nhập từ bàn phím để tạo ra một cây nhị phân. Nếu bỏ qua menu này thì chương trình sẽ thực hiện các tác vụ với cây đã được cài mặc định. Tạo cây BST: -Hàm chèn một đối tượng vào cây BST: Sơ đồ khối: end begin T=NULL T=new SinhVien T->data=dulieu T->left=T->right=null T->info>x T=T->left T->right<x T=T->right S Đ S Đ S Đ Thuật toán: B1: Nếu cây rỗng. B1.1: Tạo nốt mới. B1.2: Gán cây bằng nốt vừa tạo. B2: Ngược lại nếu mã số của sinh viên cần chèn nhỏ hơn mã số của sinh viên trong cây thì chèn vào bên trái của cây. B3: Ngược lại nếu mã số của sinh viên cần chèn lớn hơn mã số của sinh viên trong cây thì chèn vào bên phải của cây. B4: trùng giá trị đã có thì báo đã có trong cây. Code: void chenDS(int x,char H[30],char date[20],char G[5],char L[10],char D[50], SinhVien *&T) { if (T==N) { T=new SinhVien; T->maso=x; strcpy(T->name,H); strcpy(T->ngaysinh,date); strcpy(T->gioitinh,G); strcpy(T->lop,L); strcpy(T->diachi,D); T->left=T->right=N; } else if(T->maso>x) chenDS(x,H,date,G,L,D,T->left); else if(T->masoright); else cout<<"\nDa co ten"; } -Menu in danh sách sinh viên: Duyệt toàn bộ cây theo cách duyệt trung tự vào in thông tin ra màn hình. Sử dụng phép duyệt : Đầu vào: Cây nhị phân lưu các số nguyên. Kết quả: xuất ra màn hình 1 dãy các giá trị của cây cần duyệt. Sơ đồ khối: begin end T!=null T->left!=null T=T->left T->data T->right!=null T=T->right S Đ S Đ S Đ Thuật toán : Duyệt trung tự: B1: Trong khi cây khác rỗng: B1.1: gọi hàm đệ quy duyệt cây con trái. B1.2: xuất ra thông tin sinh viên. B1.3: gọi hàm đệ quy duyệt cây con phải. Code: void F(SinhVien *T){ if(T!=N){ F(T->left); coutmaso; coutname; coutngaysinh; coutgioitinh; coutlop; coutdiachi; F(T->right); } } -Menu tìm kiếm: Thuật toán thực hiện nhiệm vụ này sẽ duyệt qua tất cả các nốt duy nhất một lần , tuỳ vào từng trường hợp cụ thể mà mỗi hàm viết ra có nhiệm vụ khác nhau.Ở đây nhiệm vụ của hàm duyệt là vụ xuất ra màn hình sinh viên có mã số hoặc tên tương ứng lưu trên các nốt của cây.Có 2 cách tìm kiếm: + Tìm kiếm theo mã số : Xử lý và tìm kiếm các mã số sinh viên giống với từ khóa. begin end T=null T->data=x T->data T->left!=null T=T->left T=T->right Đ S Đ S S Đ Thuật toán: B1: Nếu cây rỗng báo không tồn tại B2: Nếu mã số sinh viên cần tìm trùng với mã số tồn tại trong cây hiển thị thông tin của sinh viên đó ra màn hình. B3: Nếu mã số của sinh viên cần tìm nhỏ hơn mã số sinh viên trong cây thì chuyển qua so sánh bên trái của cây. B4: Ngược lại nếu mã số của sinh viên cần tìm lớn hơn mã số sinh viên trong cây thì chuyển qua so sánh bên phải của cây. -Sửa danh sách sinh viên : đầu tiên tìm và hiện thông tin của sinh viên cần sửa , sau đó gán thông tin cần sửa vào trường cần sửa. Code: void SuaDS(SinhVien *&T,int r){ SinhVien *p; cout<<"\nThong tin SV can sua:"; p=Timmaso(T,r); cout<<"\nNhap lai thong tin:"; fflush(stdin); cout<<"\nTen SV: "; gets(H); strcat(H,"\n"); cout<<"\nNgay sinh: "; gets(date); strcat(date,"\n"); cout<<"\nGioi tinh: "; gets(G); strcat(G,"\n"); cout<<"\nLop: "; gets(L); strcat(L,"\n"); cout<<"\nDia chi: "; gets(D); strcat(D,"\n"); strcpy(p->name,H); strcpy(p->ngaysinh,date); strcpy(p->gioitinh,G); strcpy(p->lop,L); strcpy(p->diachi,D); } -Xóa sinh viên : tìm và kiểm tra sinh viên cần xóa có tồn tại hay không nếu tồn tại thì xóa node chứa thông tin về sinh viên đó và thiết lập lại các node phía sau nó. Sơ đồ khối: end begin T!=Null T->maso=x T->left=null T->right=null SinhVien *p=T Free(p) T=null SinhVien *p=T->left SinhVien *q=T q=p p=p->right p->right!=Null T->maso=p->maso T=p x=p->maso T->maso<x T=T->left T=T->right T->left!=null SinhVien *p=T T=T->right Free(p) S Đ S S Đ Đ S Đ Đ S S Đ Thuật toán: (giá trị xóa được xác định dựa vào mã số sinh viên) B1: Nếu cây rỗng báo không xoá được. B2: Ngược lại (tìm được mã số sinh viên cần xoá): B2.1: Nếu sinh viên nằm trong cây là lá thì xoá cây chứa sinh viên đó. B2.2: Nếu cây chỉ có con trái thì gán cây =con trái. B2.3: Nếu cây chỉ có con phải thì gán cây =con phải. B2.4: Trường hợp cây có 2 con thực hiện 1 trong 2 cách: - Tìm mã số sinh viên lớn nhất bên con trái thay vào cây sau đó xoá mã số sinh viên lớn nhất bên con trái cây vừa thay. - Hoặc tìm mã số sinh viên nhỏ nhất bên con phải thay vào cây sau đó xoá mã số sinh viên nhỏ nhất bên con phải cây vừa thay. B3: Ngược lại nếu mã số sinh viên cần xoá > hơn mã số sinh viên của cây thì chuyển sang xoá bên phải của cây. B4: Ngược lại nếu mã số sinh viên cần xoá < hơn mã số sinh viên của cây thì chuyển sang xoá bên trái của cây. Code: void XoaDS(SinhVien *&T,int s){ if(T!=N) if(T->maso==s) if(T->left==N && T->right==N){ SinhVien *p=T; free(p); T=N; } else if(T->left!=N){ SinhVien *p=T->left,*q=T; while(p->right!=N){ q=p; p=p->right; } T->maso=p->maso; XoaDS(p,p->maso); } else{ SinhVien *p=T; T=T->right; free(p); } else if(T->masoright,s); else XoaDS(T->left,s); } -Thống kê sô lượng sinh viên: Thao tác sẽ đếm xem có bao nhiêu sinh viên có trong danh sách. Để tính số sinh viên ta cần tính số sinh viên của cây con trái và phải.Khi đó tổng số sẽ bằng tổng sinh viên của các cây con cộng thêm 1. Sơ đồ khối: d++ begin end T!=null T->left!=null T=T->left T->right!=null T=T->right d=1 S Đ S Đ S Đ Thuật toán : B1: Nếu cây rỗng trả về 0. B2: Ngược lại trả về 1 cộng với hàm đếm số sinh viên cây con trái cộng tiếp với hàm đếm số sinh viên cây con phải. Code: int dem(SinhVien *T){ if(T==NULL)return 0; else { return 1+dem(T->left)+dem(T->right); } } -Lưu chương trình: chức năng này cho phép lưu lại các thao tác phía trên.Ghi các dữ liệu đã được sửa chữa vào trong file.Nếu chức năng không được khởi động thì các thao tác đã được thực hiện sẽ không đươc lưu vào chương trình. Code: void GhiFile(char *FileName,SinhVien *&T){ char c= (int)10; if(T!=NULL){ FILE *f = fopen(FileName,"a"); fprintf(f,"%d\n",T->maso); fprintf(f,"%s",T->name); fprintf(f,"%s",T->ngaysinh); fprintf(f,"%s",T->gioitinh); fprintf(f,"%s",T->lop); fprintf(f,"%s",T->diachi); //fprintf(f,"\n"); //xuong dong GhiFile(FileName,T->left); GhiFile(FileName,T->right); } } -Thoát khỏi chương trình. CHƯƠNG III DEMO CHƯƠNG TRÌNH Chương trình được viết bằng ngôn ngữ C++ với trình soạn thảo và biên dịch là C Free version 4. Các trình biên dịch C/C++ khác khi thực thi chương trình có thể gặp một số vấn đề về cú pháp như cách khai báo hàm main (trong Dev C là int main(),Turbo C là Void main(),C Free 4 cả hai cách trên đều được). Ngoài ra còn một số lệnh điều khiển như lệnh xóa màn hình chương trình dùng lệnh system(“cls”) thay cho lệnh clrscr() trong turbo C. Vì vậy chương trình sẽ chạy tốt nhất trên phần mềm C Free. Hướng dẫn thao tác: Các menu khi chọn đã được tô màu, để chọn menu và các tác vụ chi cần di chuyển các phím lên xuống. Khi thực thi xong một tác vụ của một menu con ,chương trình sẽ chuyển về menu chính khi nhấn phím bất kỳ. Ví dụ: Hình :Menu chính chương trình. Dùng phím di chuyển để chọn thao tác.Nhấn enter để chạy chương trình. Chọn dòng đầu tiên nhấn enter để thêm sinh viên vào trong cây nhị phân Chọn dòng 2 thì tất cả dữ liệu sinh viên có trong cây sẽ được in ra màn hình Chọn dòng 3 thì chương trình sẽ tìm kiếm sinh viên trong cây theo mã số nhập từ bàn phím. Chọn dòng 4 chương trình sẽ tìm sinh viên và dữ liệu sửa của sinh viên sẽ nhập lại từ bàn phím. Chọn dòng 5 chương trình sẽ tìm và xóa sinh viên có mã số tương ứng khỏi danh sách. Chọn dòng 6 chương trình sẽ đếm xem có bao nhiêu sinh viên có trong cây. Chọn dòng 7 chương trình sẽ lưu toàn bộ thao tác thêm, xóa ,sửa đã được thực hiện ở trên.Nếu không chọn thao tác này trước khi tắt chương trình thì toàn bộ thao tác thêm, sửa ,xóa sẽ không lưu lại cho lần sau. Chọn dòng 8 để thoát khỏi chương trình. KẾT LUẬN Ưu điểm : - Nắm rõ yêu cầu của bài toán gồm hai phần quan trọng là lý thuyết đệ quy và cây nhị phân. -Thực hiện đầy đủ các yêu cầu về nội dung và hình thức trình bày của đề tài. - Hiểu rõ các tất cả các thuật toán đệ quy trong chương trình. - Chương trình được bố cục rõ ràng : Phần cốt thực hiện theo sườn đề tài, menu thực thi được chia nhỏ và săp xếp tiện thao tác. Nhược điểm: - Chương trình chỉ dừng lại ở các thao các cở bản. - Chương trình không phân biệt tính đúng sai của dữ liệu cần nhập. Phát triển : - Điểm mạnh của cây nhị phân là tính ứng dụng cho việc tìm kiếm. Trường dữ liệu có thể được xây dựng phức tạp hơn (không chỉ là các số nguyên) phù hợp với nhiều bài toán.Vì vậy hướng phát triển của đề tại sẽ chú trọng sâu hơn vào phần cây nhị phân tìm kiếm, cụ thể nâng cao các thuật toán phức tạp hơn nhằm cải tiến công tác quản lý sinh viên. TÀI LIỆU THAM KHẢO Tieng viet [1] Giải thuật và lập trình. Lê Minh Hoàng. ĐH sư phạm Hà Nội. Năm 2002. [2 ]Cấu trúc dữ liệu và giải thuật (bài giảng chuyên đề). Lê Minh Hoàng. [3] Giáo trình cấu trúc dữ liệu và giải thuật. Đại học Duy Tân. [4] Trang web Wikipedia (Cấu trúc dữ liệu cây ): Web site 1. 2. www.congdongcviet.com 3. www.laptrinhc.daitudiem.com MỤC LỤC Tên đề tài 02 Nhận xét của GVHD 03 Lời mở đầu 04 Chương I:Cơ sở lý thuyết 05 1.Lý thuyết đệ quy 05 1.1.Khái niệm 05 1.2.Ưu nhược điểm của thuật toán 06 2.Cấu trúc dữ liệu cây 06 2.1.Cây tổng quát 06 2.2.Cây nhị phân 08 2.3.Cây nhị phân tìm kiếm(BST) 09 3.Thuật toán và sơ đồ khối 08 3.1.Tạo cây BST 10 3.2.Các phép duyệt 12 3.3.Các thao tác đếm 17 3.4.Xóa một nốt của cây BST 19 3.5.Kiểm tra có phải cây BST không 21 3.6.Kiểm tra nốt gốc có lớn hơn mọi nốt trong cây hay không 22 3.7.Tính tổng giá trị của cây 24 3.8.Tính chiều cao của cây 25 Chương II:Xây dựng ứng dụng quản lý sinh viên bằng cây nhị phân 27 1.Đặc tả bài toán 27 2.Yêu cầu bài toán 27 3.Khai báo cấu trúc dư liệu quản lý sinh viên 28 4.Lập trình 29 4.1.Các bước lập trình 29 4.2.Ghi chú 30 4.3.Mã chương trình 30 4.4.Đọc dữ liệu từ file 30 4.5.Hệ thống menu 32 Chương III:Triển khai chạy demo chương trinh 44 Kết luận 49 Tài liệu tham khảo 50