Đề tài Quản lý hộ khẩu

ức của một công ty
GIẦY DÉP
QUẦN ÁO
TRUNG QUỐC
THÁI LAN
CAMPUCHIA
NỘI ĐỊA
QUỐC TẾ
KINH DOANH
TÀI VỤ
SẢN XUẤT
GIÁM ĐỐC
● Cuốn gia phả
● Cấu trúc cây thư mục trong DOS/WIN
● Cấu trúc thư viện,.
 Ä Nhận xét:
	- Trong một cây không tồn tại chu trình
- Tổ chức 1 cấu trúc cây cho phép truy cập nhanh đến các phần tử của cây.
 2.2 Cây nhị phân
 2.2.1 Định nghĩa
Cây nhị phân là cây mà mỗi nút có tối đa 2 nút con .gồm nút con bên trái và nút con bên phải. Cây nhị phân có thể được ứng dụng trong nhiều bài toán thông dung, ví dụ dưới đây cho ta hình ảnh của một biểu thức toán học .
 2.2.2 Biễu diễn cây nhị phân T:
Cây nhị phân là một cấu trúc bao gồm các phần tử (nút) được kết nối với nhau theo quan hệ “cha - con”, với mỗi cha có tối đa 2 con. Để biểu diễn cây nhị phân ta chọn phương pháp cấp phát liên kết. Ứng với một nút ta dùng một biến động lưu trữ các thông tin:
+ Thông tin lưu trữ tại nút
+ Địa chỉ nút gốc của cây con trái trong bộ nhớ 
+ Địa chỉ nút gốc của cây con phải trong bộ nhớ
 Khai báo 1 nút của cây tương ứng trong ngôn ngữ Pascal như sau: 
	Type tree =^node
	 Node = record 
	Info: integer;
	Left: tree;
	Right: tree;
	 End;
 Do tính chất mềm dẻo của cách biểu diễn bằng cấp phát liên kết, phương pháp này được dùng chủ yếu trong biểu diễn cây nhị phân.
 2.2.3 Duyệt cây nhị phân
Có nhiều kiểu duyệt cây khác nhau và chúng cũng có những ứng dụng khác nhau. Đối với cây nhị phân, do cấu trúc đệ quy của nó, việc duyệt cây tiếp cận theo kiểu đệ quy là hợp lý và đơn giản nhất. Có 3 cách duyệt thông dụng: duyệt theo thứ tự trước (NLR), duyệt theo thứ tự giữa (LNR), duyệt theo thứ tứ sau (LRN), với 3 công việc chính:
+ Thăm nút gốc
+ Duyệt cây con bên trái
+ Duyệt cây con bên phải
 2.2.4 Cây tìm kiếm nhị phân
 a. Định nghĩa:
Cây tìm kiếm nhị phân là cây thoả mãn: với mọi nút của cây thì giá trị khoá của các nút cây con bên trái nhỏ hơn giá trị của nút và giá trị khoá của các cây con bên phải lớn hơn giá trị khoá của nút đó.
Ví dụ sau minh hoạ một cây TKNP có khoá là số nguyên (với quan hệ thứ tự trong tập số nguyên). 
20
17
15
10
5
22
30
42
35
Nhận xét:
 + Trên cây TKNP không có hai nút cùng khoá
 + Cây con của một cây TKNP là cây TKNP
 + Khi duyệt trung tự (InOrder) cây TKNP ta được một dãy có thứ tự tăng
 b. Cài đặt cây tìm kiếm nhị phân
Cây TKNP, trước hết, là một cây nhị phân. Do đó ta có thể áp dụng các cách cài đặt như đã trình bày trong phần cây nhị phân. Sẽ không có sự khác biệt nào trong việc cài đặt cấu trúc dữ liệu cho cây TKNP so với cây nhị phân, nhưng tất nhiên sẽ có sự khác biệt trong các giải thuật thao tác trên cây TKNP như tìm kiếm, thêm hoặc xoá một nút trên cây TKNP để luôn đảm bảo tính chất của cây TKNP. Một cách cài đặt cây TKNP thường gặp là cài đặt bằng con trỏ. Mỗi nút của cây như là một mẩu tin (record) có ba trường: một trường chứa khoá, hai trường kia là hai con trỏ trỏ đến hai nút con (nếu nút con vắng mặt ta gán con trỏ bằng NIL). 
 *Tìm kiếm một nút có khóa cho trước trên cây TKNP: để tìm kiếm 1 nút có khoá x trên cây TKNP, ta tiến hành từ nút gốc bằng cách so sánh khoá của nút gốc với khoá x. 
+ Nếu nút gốc bằng NULL thì không có khoá x trên cây. 
+ Nếu x bằng khoá của nút gốc thì giải thuật dừng và ta đã tìm được nút chứa khoá x. 
+ Nếu x lớn hơn khoá của nút gốc thì ta tiến hành (một cách đệ qui) việc tìm khoá x trên cây con bên phải. 
+ Nếu x nhỏ hơn khoá của nút gốc thì ta tiến hành (một cách đệ qui) việc tìm khoá x trên cây con bên trái.
 *Thêm một nút có khóa cho trước vào cây TKNP 
Theo định nghĩa cây tìm kiếm nhị phân ta thấy trên cây tìm kiếm nhị phân không có hai nút có cùng một khoá. Do đó nếu ta muốn thêm một nút có khoá x vào cây TKNP thì trước hết ta phải tìm kiếm để xác định có nút nào chứa khoá x chưa. Nếu có thì giải thuật kết thúc (không làm gì cả!). Ngược lại, sẽ thêm một nút mới chứa khoá x này. Việc thêm một khoá vào cây TKNP là việc tìm kiếm và thêm một nút, tất nhiên, phải đảm bảo cấu trúc cây TKNP không bị phá vỡ. Giải thuật cụ thể như sau:
- Ta tiến hành từ nút gốc bằng cách so sánh khóa cuả nút gốc với khoá x
 + Nếu nút gốc bằng NULL thì khoá x chưa có trên cây, do đó ta thêm một nút mới chứa khoá x
 + Nếu x bằng khoá của nút gốc thì giải thuật dừng, trường hợp này ta không thêm nút
 + Nếu x lớn hơn khoá của nút gốc thì ta tiến hành (một cách đệ qui) giải thuật này trên cây con bên phải
 + Nếu x nhỏ hơn khoá của nút gốc thì ta tiến hành (một cách đệ qui) giải thuật này trên cây con bên trái.
 *Xóa một nút có khóa cho trước ra khỏi cây TKNP
Giả sử ta muốn xoá một nút có khoá x, trước hết ta phải tìm kiếm nút chứa khoá x trên cây. Việc xoá một nút như vậy, tất nhiên, ta phải bảo đảm cấu trúc cây TKNP không bị phá vỡ
- Nếu không tìm thấy nút chứa khoá x thì giải thuật kết thúc 
- Nếu tìm gặp nút N có chứa khoá x, ta có ba trường hợp sau: 
 + Nếu N là lá ta thay nó bởi NULL 
 + N chỉ có một nút con ta thay nó bởi nút con của nó 
 + N có hai nút con ta thay nó bởi nút lớn nhất trên cây con trái của nó (nút cực phải của cây con trái) hoặc là nút bé nhất trên cây con phải của nó (nút cực trái của cây con phải). Trong giải thuật sau, ta thay x bởi khoá của nút cực trái của cây con bên phải rồi ta xoá nút cực trái này. Việc xoá nút cực trái của cây con bên phải sẽ rơi vào một trong hai trường hợp trên.
 2.3 Giới thiệu ngôn ngữ lập trình
Pascal là ngôn ngữ lập trình cấp cao do Niklaus Wirth – người Thuỵ Sỹ thiết kế vào đầu năm 1970, với tên Pascal để kỷ niệm nhà toán học người Pháp Balaise Pascal.
Ngôn ngữ lập trình Pascal có ưu điểm là ngữ pháp, ngữ nghĩa đơn giản và có tính logic; câu trúc chương trình rõ ràng, dễ hiểu; dễ sữa chữa, cải tiến. Có thể nói tính cấu trúc của Pascal được thể hiện trên ba mặt:
 1. Dữ liệu: từ các dữ liệu đã có, có thể xây dựng thành các kiểu dữ liệu phức tạp.
 2. Lệnh: từ các lệnh đã có, có thể nhóm chúng lại với nhau và đặt giữa hai từ khóa Begin và End thành lệnh ghép.
 3. Chương trình: một chương trình có thể chia thành nhiều chương trình con.
 Từ những ưu điểm trên, nhóm chúng em sử dụng ngôn ngữ lập trình Pascal cho đề tài.
III. CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT
 3.1 Cấu trúc dữ liệu
Đề tài Quản lý hộ khẩu sử dụng kiểu bản ghi, và kiểu File – văn bản để cài đặt thuật toán
 3.1.1 Kiểu bản ghi
 Khai báo: type tên kiểu =record
	 Field 1: kiểu 1;
	 Field 2: kiểu 2;
	 .......	
	 Field n: kiểu n;
	 End;
 Var biến: tên kiểu;
 3.1.2 Kiểu File – văn bản
 a. Một số thủ tục và các hàm chung 
 *Một số thủ tục:
- Gán tên file
 ASSIGN(F, filename); 
Gán một file trên đĩa có tên là filename cho biến F,mọi truy xuất trên file cụ thể được thực hiện thông qua biến file này.
- Mở một file mới 
 REWRITE(F); mở file mới rỗng
Tạo file mới có tên đã gán cho biến file F. Nếu file đã có trên đĩa thì mọi dữ liệu trên đó sẽ bị xoá và con trỏ file ở vị trí đầu tiên của file.
- Mở file đã có trên đĩa
 RESET(F);
Mở file có tên đã gán cho biến file F. Nếu file chưa có trên đĩa thì chương trình sẽ dừng vì gặp lỗi xuất/ nhập
- Đọc dữ liệu 
 Read(F, các biến); 
 Readln(F, các biến);
- Ghi dữ liệu 
 Write(F, các biến); 
 Writeln(F, các biến);
 - Đóng file 
 Close(F);
 b. Các hàm chung
- Hàm kiểm tra cuối file
 Eof(F);trả về giá trị true hoặc false
- Hàm kiểm tra cuối dòng	
 Eoln(F);trả về giá trị true hoặc false
 3.2 Giải thuật
*Hàm liệt kê Output( ):
 Bước 1: gọi hàm Duyetdexuat( )
 Bước 2: nếu có thì xuất ngược lại thông báo “ không có gì để xuất cả”
 Bước 3: kết thúc.
*Hàm nhập mã hộ khẩu mới update( ):
 Bước 1: Nhập dữ liệu từ bàn phím
 Bước 2: Kiểm tra mã hộ khẩu muốn nhập, nếu mã hộ khẩu đã có trong danh sách thì hiện thông báo” mã hộ khẩu đã có rồi, bạn muốn thay thế không?”, nếu “không” chuyến bước 4, nếu “có” thì thay đổi thông tin chủ hộ, ngược lại chuyển bước 3
 Bước 3 : Gọi thủ tục CapNhap() để chèn một nút mới vào cây
 Bước 4: kết thúc
*Hàm sửa thông tin sửa( ):
 Bước 1: Nhập mã hộ khẩu cần chỉnh sửa
 Bước 2: Kiểm tra xem mã hộ khẩu cần sửa có trong danh sách vừa nhập hay không, nếu có thí sửa thông tin chủ hộ ngược lại hiện thông báo “không có mã hộ khẩu nào như vậy”. Nếu hộ khẩu rỗng thì hiện thông báo “không có gì để sửa”.
 Bước 3: Kết thúc
*Hàm tìm kiếm theo mã hộ khẩu search( )(Tìm theo khoá)
 Bước 1: Nhập mã hộ khẩu cần tìm kiếm
 Bước 2: Duyệt cây theo thủ tục duyệt trước không đệ quy, nếu tìm thấy thì in thông tin chủ hộ ( họ tên, giới tính, địa chỉ), nếu không tìm thấy thì hiện thông báo không có.
 Bước 3: kết thúc
*Hàm xoá dữ liệu: xoa( ), được gọi khi ta muốn xoá dữ liệu hộ khẩu đó
 Bước 1: Nhập mã hộ khẩu muốn xoá
 Bước 2: Kiểm tra xem mã hộ khẩu có đúng với mã hộ khẩu có trong danh sách hay ko. Nếu đúng thì xoá nút khỏi cây, ngược lại thì không có mã hộ khẩu cần xoá
 Bước 3: kết thúc
* Hàm ghi file():
 Bước 1 : Tạo file( HOKHAU.TXT)
 Bước 2: ghi dữ liệu vào file (HOKHAU.TXT)
 Bước 3: Đóng file 
KẾT LUẬN
 1. Đánh giá
	Chương trình được viết dựa vào cấu trúc tìm kiếm nhị phân là một cấu trúc dữ liệu hay và rất linh hoạt. Các thao tác trong chương trình được xây dựng giúp cho người quản lý làm chủ công việc một cách đơn giản, hiệu quả và không mất nhiều thời gian như việc quản lý thủ công.
Tuy nhiên, do kiến thức còn hạn chế và thiếu kinh nghiệm trong việc xây dựng một đề tài quản lý cho nên chương trình còn có nhiều thiếu sót, tính bảo mật chưa cao, các chức năng trong chương trình còn đơn giản, giao diện được cài đặt trên nền DOS nên chưa thực sự ấn tượng.
 2. Hướng phát triển
+ Cài đặt chương trình trên nền Windows.
	+ Hoàn thiện các chức năng nâng cao. 
	+ Mở rộng với các đối tượng quản lý khác.
TÀI LIỆU THAM KHẢO
	1.Giáo trình cấu trúc dữ liệu và giải thuật GV - Phan Đoàn Ngọc Phương
2. Giáo trình lập trình Pascal GV- Đoàn Duy Bình
3. Giáo trình Turbo Pascal 7.0 PGS.TS - Bùi Thế Tâm
 4. Giải thuật TH.S – Nguyễn Văn Linh
	5.Giáo trình cấu trúc dữ liệu và giải thuật PGS.TSKH Trần Quốc Chiến
. 6. Giáo trình cấu trúc dữ liệu và giải thuật Đỗ Xuân Lôi
 7. 
 Và các tài liệu có liên quan khác.