ĐẠI HỌC ĐÀ NẴNG
TRƯỜNG ĐẠI HỌC SƯ PHẠM
KHOA TOÁN

Đề tài:

Giáo viên hướng dẫn : Phan Đoàn Ngọc Phương
Sinh viên thực hiện : Lưu Thị The
Ngô Thị Nhung
Nguyễn Thị Hoàng Anh
Lớp : 07CTT2
Đà Nẵng, tháng 05/ 2010
LỜI NÓI ĐẦU
Cấu trúc dữ liệu và giải thuật là một trong những môn học quan trọng đối với
những sinh viên ngành cử nhân toán tin, với mục đích nhằm củng cố kiến thức cơ sở đã
học về cấu trúc dữ liệu và tăng thêm sự hiểu biết về cây và file.
Được sự đồng ý của cô Phan Đoàn Ngọc Phương nhóm em chọn đề tài “Quản lý
hộ khẩu” để thực hiện.
Tuy nhóm em đã cố gắng nhưng chắc hẳn sẽ không tránh khỏi những thiếu xót do
hạn chế về kinh nghiệm và kiến thức. Chúng em rất mong nhận được ý kiến đóng góp, bổ
sung của cô giáo và các bạn.
Chúng em xin chân thành cảm ơn !
Đà Nẵng, tháng 05 năm 2010

I. MỞ ĐẦU
1. Lý do chọn đề tài
Trong thực tế, việc quản lý hộ khẩu của một số địa phương còn tồn tại cách quản
lý thủ công, lưu trữ dưới các loại văn bản giấy tờ. Công tác quản lý trên đã lỗi thời và gây
nhiều bất cập cho việc lưu trữ, bảo vệ cũng như cập nhật dữ liệu, nó còn làm mất thời
gian cho công tác truy cập dữ liệu, nguy cơ không đồng bộ dữ liệu là rất lớn. Do đó, việc
xây dựng các chương trình quản lý trên máy tính là rất cần thiết.

i
(i =
n,1
) cũng là một cây. Mỗi nút ở cấp I sẽ quản lý một số nút ở
cấp I+1. Quan hệ này gọi là quan hệ cha – con.
2.1.2 Một số khái niệm cơ bản
- Bậc của một nút: là số lượng nút con của nút đó.
- Bậc của một cây: là bậc lớn nhất của nút trong cây. Cây có bậc n thì gọi là cây n-
phân.
- Nút góc là nút không có nút cha.
- Nút lá là nút có bậc bằng 0
- Nút nhánh: là nút có bậc khác 0 và không phải là nút gốc.
- Mức của một nút:
+ Mức (gốc(T)) = 1
+ Gọi T
1,
T
2
,…,T
n
là các nút con của T
0
+ Mức (T
1
)= Mức (T
2
) =…= Mức (T
0
)


+ Đị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).
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

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

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

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.