Cấu trúc dữ liệu
I.
II.
III.
Các thao tác trên danh sách (tổ ch c bằng mảng và danh sách liên kết đơn):
Duyệt
1. Duyệt cơ bản
2. Duyệt có điều kiện
Thêm
1. Thêm cơ bản
2. Thêm có điều kiện
Xóa
1. Xóa cơ bản
2. Xóa có điều kiện
Các thao tác trên cây (cây nhị phân,cây tìm kiếm nhị phân,cây tổng quát):
Duyệt
1. Duyệt cơ bản
2. Duyệt có điều kiện
Thêm (chỉ có trên cây nhị phân)
1. Thêm cơ bản
2. Thêm có điều kiện
Xóa (ch yếu là xóa nút lá)
1. Xóa cơ bản
2. Xóa có điều kiện
Các thao tác trên đồ thị (đồ thị có hướng,vô hướng):
Duyệt
1. Duyệt cơ bản
2. Duyệt có điều kiện (tìm kiếm)
I.Danh sách:
1.Danh sách tổ chức bằng mảng:
Cách tổ ch c dữ liệu gồm có 2 thành phần như sau:
+một mảng mangpt lưu tất cả các phần tử c a danh sách,mỗi phần tử có kiểu là KieuPT.
+một ô nhớ để lưu số phần tử c a mảng và cũng là phần tử cuối cùng c a mảng
Chú ý:
+mangpt là tên mảng,ví dụ danh sách sinh viên thì ghi sv,danh sách thuê bao điện
thoại thì ghi tb(thuê bao)…
+KieuPT là kiểu phần tử ,ví dụ danh sách sinh viên thì ghi SinhVien(kiểu Sinh
Viên),danh sách thuê bao điện thoại thì ghi ThueBao(kiểu Thuê Bao)
Khai báo danh sách:
Pascal:
Type KieuPT=record
Thuộc tính 1:kiểu dữ liệu 1;
Thuộc tính 2:kiểu dữ liệu 2;
Thuộc tính 3:kiểu dữ liệu 3;
…
Thuộc tính n:kiểu dữ liệu n;
End;
Type DanhSach=record
mangpt:Array[1..Max] of KieuPT;
soPT:integer;
end;
Java:
class KieuPT
{
private kiểu dữ liệu 1 Thuộc tính 1;
private kiểu dữ liệu 2 Thuộc tính 2;
private kiểu dữ liệu 3 Thuộc tính 3;
…
private kiểu dữ liệu n Thuộc tính n;
…
}
class DanhSach
{
private KieuPT mangpt[];
private int soPT;
…
}
Chú ý:
+ Max số phần tử tối đa c a danh sách
+ DanhSach tên danh sách ,ví dụ danh sách sinh viên thì đặt tên là DSSV ,danh sách thuê bao
thì đặt tên là DanhBa (hoặc đặt tên là DSTB :danh sách thuê bao),danh sách giáo viên thì đặt
tên là DSGV…
+ mangpt tên cái mảng lưu danh sách, đây ta viết lại cái tên mảng mình đặt
phần I cách tổ ch c dữ liệu.
+ soPT :nếu kiểu danh sách sinh viên thì soPT mình đặt tên là soSV(số sinh viên),nếu danh
sách cần lưu có kiểu phần tử là kiểu thuê bao thì soPT mình đặt tên là soTB(số thuê bao).
Chú ý:
+KieuPT là tên kiểu dữ liệu mình tự định nghĩa ,đặt tên sao cho sát với tên c a đối
tượng cần lưu trữ c a danh sách mình đang làm việc,ví dụ danh sách sinh viên thì đối tượng
cần lưu trữ là Sinh Viên suy ra KieuPT là SinhVien
+các loại kiểu dữ liệu 1 , kiểu dữ liệu 2, kiểu dữ liệu 3 là các kiểu dữ liệu phù hợp cho
từng thuộc tính ,ví dụ :thuộc tính 1 là họ tên thì kiểu dữ liệu 1 là kiểu string (kiểu
chuỗi),thuộc tính 2 là mã số sinh viên thì kiểu dữ liệu 2 là kiểu string (kiểu chuỗi),thuộc tính
3 nếu dùng để lưu trữ số nguyên thì kiểu dữ liệu 3 là kiểu integer (kiểu số nguyên),nếu thuộc
tính 4 dùng để lưu trữ điểm trung bình thì kiểu dữ liệu 4 là kiểu real(kiểu số thực ,vì điểm
trung bình thư ng là số có phần lẻ thập phân ví dụ:7.5 ,8.6 …).Tổng quát là tùy vào giá trị
cần lưu trữ là chuỗi kí tự thì dùng kiểu string ,nếu lưu trữ số nguyên thì là kiểu integer,số
thực thì là kiểu real.
Ví dụ về khai báo tổ ch c dữ liệu bằng mảng
Bài 1:Cho danh sách sinh viên,mỗi sinh viên gồm:tên,mã sinh viên,điểm trung bình.Hãy khai
báo tổ ch c dữ liệu cho danh sách này.
o Giải đáp
Mỗi sinh viên gồm 3 thành phần:
+Phần tên thuộc kiểu xâu kí tự
+Phần mã sinh viên thuộc kiểu xâu kí tự
+Phần điểm trung bình thuộc kiểu số thực
Tổ ch c dữ liệu danh sách sinh viên bằng mảng gồm 2 thành phần:
+Phần mảng lưu tất cả các phần tử c a danh sách,mà mỗi phần tử thuộc kiểu sinh viên
+Một ô nhớ lưu số lượng sinh viên trong danh sách
Khai báo:
Pascal:
const Max_SV=…;{số lượng sinh viên tối đa trong danh sách}
TYPE
SinhVien=record
ten:string;
masv:string;
dtb:real;
DSSV=record
sv:array[1..Max_SV] of SinhVien;
soSV:0..Max_SV;
END;
var ds:DSSV;
Java:
class SinhVien
{
private string ten;
private string masv;
private double dtb;
…
}
class DSSV
{
private SinhVien sv[];
private int soSV;
…
}
Bài 2:Khai báo tổ ch c dữ liệu cho một danh sách các cuốn sách,mỗi cuốn sách gồm tên
sách,giá tiền,các tác giả(tối đa 5 tác giả).
o Giải đáp
Mỗi cuốn sách gồm 3 thành phần:
+Phần tên thuộc kiểu xâu kí tự
+Phần giá tiền thuộc kiểu số nguyên
+Phần tác giả là một mảng danh sách các tên tác giả,mỗi tên tác giả thuộc kiểu xâu kí tự
Tổ ch c dữ liệu cho danh sách bằng mảng gồm 2 thành phần:
+Phần mảng lưu tất cả các phần tử c a danh sách,mà mỗi phần tử là một cuốn sách
+Một ô nhớ lưu số lượng cuốn sách trong danh sách
Khai báo:
Pascal:
const Max_CS=…;{số lượng cuốn sách tối đa trong danh sách}
TYPE
CuonSach=record
ten:string;
giaTien:integer;
tacGia:array[1..5] of string;
soTacGia:0..5;
DSCS=record
cs:array[1..Max_CS] of CuonSach;
soCS:0..Max_CS;
END;
var ds:DSCS;
Java:
class CuonSach
{
private string ten;
private int giaTien;
private string tacGia[];
private int soTacGia;
…
}
class DSSV
{
private CuonSach cs[];
private int soCS;
…
}
Bài 3:Một khách sạn A có rất nhiều phòng cho thuê,mỗi phòng gồm:mã phòng,tên ngư i
thuê,th i gian thuê.Hãy khai báo tổ ch c dữ liệu để quản lý các phòng cho khách sạn này.
o Giải đáp
Mỗi phòng gồm 3 thành phần:
+Phần mã phòng thuộc kiểu xâu kí tự
+Phần tên ngư i thuê phòng,thuộc kiểu xâu kí tự
+Phần th i gian thuê thuộc kiểu số nguyên
Tổ ch c dữ liệu cho danh sách bằng mảng gồm 2 thành phần:
+Phần mảng lưu tất cả các phần tử c a danh sách,mà mỗi phần tử là một phòng
+Một ô nhớ lưu số lượng phòng trong danh sách
Khai báo:
Pascal:
const Max_Phong=…;{số lượng phòng tối đa trong danh sách}
TYPE
Phong=record
maPhong:string;
tenKH:string;
thoiGian:integer;
DSPhong=record
ph:array[1..Max_Phong] of Phong;
soPhong:0..Max_Phong;
END;
var ds:DSPhong;
Java:
class Phong
{
private string maPhong;
private string tenKH;
private int thoiGian;
…
}
class DSPhong
{
private Phong ph[];
private int soPhong;
…
}
Bài 4:Một cửa hàng tạp hóa có bảng hóa đơn,mỗi hàng hóa gồm:, tên mặt hàng,số lượng,đơn
giá,thành tiền.Bạn hãy khai báo tổ ch c dữ liệu cho mỗi hóa đơn,biết mỗi hóa đơn có tối đa
10 hàng hóa .Khai báo tổ ch c dữ liệu cho danh sách các hóa đơn
o Giải đáp
Mỗi hàng hóa gồm 4 thành phần:
+Phần tên thuộc kiểu xâu
+Phần số lượng thuộc kiểu số nguyên
+Phần đơn giá thuộc kiểu số nguyên
+Phần thành tiền thuộc kiểu số nguyên
Tổ ch c dữ liệu bằng mảng cho mỗi hóa đơn gồm 2 thành phần:
+Phần mảng lưu tất cả các phần tử c a danh sách,mà mỗi phần tử là một hàng hóa
+Một ô nhớ lưu số lượng hàng hóa trong danh sách
Tổ ch c dữ liệu bằng mảng cho danh sách các hóa đơn gồm 2 thành phần:
+Phần mảng lưu tất cả các phần tử c a danh sách,mà mỗi phần tử là một hóa đơn
+Một ô nhớ lưu số lượng hóa đơn trong danh sách
Khai báo:
Pascal:
const Max_HH=10;
const Max_HD=…;
type
HangHoa=record
tenHH:string;
soLuong:integer;
donGia:integer;
thanhTien:integer;
HoaDon=record
hh:array[1...Max_HH] of HangHoa;
soHH:0..Max_HH;
DSHD=record
hd:array[1..Max_HD] of HoaDon
soHD:0...Max_HD;
end;
var ds:DSHD;
Java:
class HangHoa
{
private string tenHH;
private int soLuong;
private int donGia;
private int thanhTien;
…
}
class HoaDon
{
private HangHoa hh[];
private int soHH;
…
}
class DSHD
{
private HoaDon hd[];
private int soHD;
…
}
Bài 5:Một ngư i có rất nhiều bạn,anh ta có thể liên lạc với những ngư i bạn c a mình bằng
số điện thoại,nhưng máy điện thoại c a anh ấy thì không thể lưu được nhiều hơn 10 số điện
thoại.Cho nên Anh ta quyết định viết một phần mềm trên máy tính để quản lý các số điện
thoại tất cả bạn bè.Nhưng anh ấy lại chưa biết làm sao để khai báo tổ ch c dữ liệu.Bạn hãy
giúp anh ấy khai tổ ch c dữ liệu cho phần mềm này nhé.
o Giải đáp
Mỗi thuê bao gồm 2 thành phần:
+Phần tên thuê bao thuộc kiểu xâu kí tự
+Phần số điện thoại,thuộc kiểu xâu kí tự
Tổ ch c dữ liệu cho danh sách thuê bao bằng mảng gồm 2 thành phần:
+Phần mảng lưu tất cả các phần tử c a danh bạ,mà mỗi phần tử là một thuê bao
+Một ô nhớ lưu số lượng thuê bao trong danh bạ
Khai báo:
Pascal:
const Max_ThueBao=…;{số lượng thuê bao tối đa trong danh sách}
TYPE
ThueBao=record
tenTB:string;
soDT:string;
DSTB=record
tb:array[1..Max_ThueBao] of ThueBao;
soTB:0..Max_ThueBao;
END;
var ds:DSTB;
Java:
class ThueBao
{
private string tenTB;
private string soDT;
…
}
class DSTB
{
private ThueBao tb[];
private int soTB;
…
}
Bài 6:Một sinh viên học ngành công nghệ thông tin đang có một bài tập liên quan đến môn
cấu trúc dữ liệu.Ông thầy c a môn này đưa ra câu hỏi như sau:
Ch c a nhà sách đang đau đầu về việc tính toán doanh thu và thống kê số sách bán được
mỗi tháng c a mình,nhưng ông không muốn thuê nhân viên kế toán vì phải trả thêm
lương.Cho nên ông quyết định nh một ngư i biết lập trình viết cho ông một phần mềm để
giải quyết vấn đề này.Bạn nào có cách giải quyết thì giúp ông ch này nhé.
Bài 7:Một anh chàng sinh viên đang đau đầu với môn tư tư ng hồ chí minh,khi đang trên
đư ng đi học về nhà anh này thì gặp một cô gái mà anh quen biết,cô gái này đang suy tư điều
gì đó,anh hỏi ra thì mới biết là cô ấy đang gặp khó khăn trong việc quản lý sản phẩm bán
online.Vì cô kinh doanh nhỏ nên không có website riêng nên cô gái đang bán hàng trên
facebook.Anh sinh viên quyết định giúp cô ấy nhưng chưa nghĩ ra cách tổ ch c dữ liệu ra
sao.Bạn đã học qua môn cấu trúc dữ liệu thì hãy giúp đỡ anh ấy nhé.
a.Duyệt cơ bản(duyệt không có điều kiện):
Giải thích về duyệt:
Để hiểu về duyệt ta xem qua một ví dụ sau:cho một danh sách tên các sinh viên trong lớp,vậy việc
bạn nhìn qua tất cả các tên sinh viên trong danh sách thì việc bạn nhìn chính là thao tác duyệt.Nói
chung về mặt cơ bản duyệt giống như việc bạn phải xem xét tất cả các tên sinh viên có trong danh
sách.Duyệt không có điều kiện t c là xem qua tất cả các phần tử nhưng không có bất c một thao
tác với thông tin của phần tử trong mảng.
Chú thích:
- Thao tác: so sánh,kiểm tra
- Thông tin của phần tử:ví dụ tên sinh viên,mã sinh viên,điểm…
Thuật toán:
- Duyệt lần lượt từng phần tử c a danh sách từ đầu đến cuối danh sách
+ Thao tác với phần tử đang xét(thăm)
Giải thích thuật toán:Lần lượt xem qua tất cả các phần tử c a danh sách,với mỗi phần tử đang xét ta
có thể dùng nó để làm điều kiện cho việc tính toán khác như đếm phần tử,liệt kê,tìm kiếm…
Cài đặt:
Pascal:
procedure duyet();
var n:integer;
begin
for i:=1 to n do
{ ds.mangpt[i] chính là phần tử đang xét }
end;
Java:
void duyet()
{
int i;
for(i=0;i<n;i++)
//mangpt[i] chính là phần tử đang xét
}
b.Duyệt có điều kiện:Duyệt qua lần lượt các phần tử trong danh sách với mỗi phần tử đang xét ta
sử dụng thông tin c a phần tử để giải quyết một số vấn đề như là đếm,liệt kê,thêm,tìm kiếm,…
Giải thích:Với mỗi một phần tử c a danh sách ta sẽ kiểm tra thông tin của phần tử,việc kiểm tra
thông tin c a phần tử chính là điều kiện duyệt,kết quả duyệt có điều kiện hoàn toàn phụ thuộc vào
điều kiện này.Sử dụng thông tin c a phần tử để làm điều kiện cho các thao tác đếm,thêm,tìm
kiếm,…
Chú thích:
- Thông tin của phần tử:ví dụ tên sinh viên,mã sinh viên,điểm…
- kiểm tra Thông tin của phần tử :ví dụ kiểm tra tên sinh viên có phải là “Nguyễn Văn A”
,kiểm tra sinh viên có mã sinh viên “1204520” ,hoặc kiểm tra sinh viên có điểm >=7.0 .
Lưu ý:Nếu vận dụng linh hoạt việc sử dụng thông tin của phần tử làm điều kiện duyệt thì tất cả các
bài toán ta đều giải quyết được.
Thuật toán:
- Duyệt lần lượt từng phần tử trong danh sách từ đầu đến cuối danh sách
+ Kiểm tra thông tin c a phần tử đang xét nếu thỏa mãn điều kiện thì thực hiện công việc như
đếm,liệt kê,tìm kiếm,…
Giải thích thuật toán:Với mỗi phần tử trong danh sách ta sẽ kiểm tra thông tin c a phần tử nếu thông
tin này thỏa mãn điều kiện yêu cầu từ đề bài thì thực hiện việc đếm,liệt kê,hoặc tìm kiếm,…
Cài đặt:
Pascal:
function duyetDK(dk:KieuDK):kiểu trả về;{KieuDK là kiểu dữ liệu c a điều kiện}
var i:integer;
begin
for i:=1 to n do
begin
if (kiểm tra ds.mangpt[i].thongtin với điều kiện dk ) đúng then
begin
{thực hiện đếm,liệt kê,hoặc tìm kiếm,…}
end;
end;
end;
Java:
Kiểu trả về duyetDK(KieuDK dk)//KieuDK là kiểu dữ liệu c a điều kiện
{
int i;
for(i=0;i<n;i++)
{
if( kiểm tra mangpt[i].thongtin với điều kiện dk) đúng
{
// thực hiện đếm,liệt kê,hoặc tìm kiếm,…
}
}
}
Chú ý:hầu hết thao tác duyệt đều là duyệt có điều kiện.
Các loại duyệt có điều kiện của danh sách tổ chức bằng mảng:
- Duyệt để liệt kê
- Duyệt để tìm kiếm
- Duyệt để đếm
Duyệt để liệt kê:liệt kê đây là hiển thị ra những thông tin theo yêu cầu c a đề bài
Ví dụ:
+Liệt kê sinh viên t c là hiển thị ra tất cả các thông tin về sinh viên như :tên,mã sinh viên,địa
chỉ,điểm,…
+Liệt kê tên c a tất cả các sinh viên thì thông tin cần hiển thị là tên sinh viên
+Liệt kê điểm c a tất cả các sinh viên thì thông tin cần hiển thị là điểm
Chú ý:các loại liệt kê trên là liệt kê không có điều kiện,ch yếu chúng ta cần quan tâm là liệt kê có
điều kiện,ví dụ:liệt kê các sinh viên tên “Nguyễn Văn A”,liệt kê các sinh viên có điểm số lớn hơn
a,liệt kê các sinh viên quê “Bình Định”.
Như vậy trong duyệt để liệt kê còn có thêm phần điều kiện,nhưng ta dễ thấy những điều kiện c a đề
bài sẽ dùng để kiểm tra thông tin c a phần tử trong danh sách,nếu thông tin c a phần tử phù hợp với
điều kiện yêu cầu từ đề bài thì ta sẽ hiển thị thông tin c a phần tử đúng với điều kiện đề bài.
Thuật toán:
- Duyệt lần lượt từng phần tử trong danh sách từ đầu đến cuối
+ Nếu thông tin c a phần tử đang xét phù hợp với yêu cầu đề bài thì hiển thị ra thông tin c a
phần tử này(theo yêu cầu c a đề bài).
Cài đặt:
Pascal:
procedure lietKe(dk:KieuDK);{KieuDK là kiểu dữ liệu c a điều kiện}
var i:integer;
begin
for i=1 to n do
begin
if( thông tin c a ds.mangpt[i] đúng với điều kiện dk )then
begin
{hiển thị ra thông tin c a phần tử ds.mangpt[i] theo yêu cầu đề bài}
end;
end;
end;
Java:
void lietKe(KieuDK dk)
{
int i;
for(i=0;i<n;i++)
{
if(thông tin c a a[i] phù hợp với điều kiện dk)
{
//hiển thị ra những thông tin mà đề bài yêu cầu c a phần tử a[i]
}
}
}
Ví dụ duyệt để liệt kê:
Bài 1:Cho danh sách sinh viên,mỗi sinh viên gồm:tên,mã sinh viên,điểm trung bình.Hãy khai báo tổ
ch c dữ liệu cho danh sách này.Sau đó trình bày thuật toán và cài đặt chương trình có ch c năng sau
a)Liệt kê nhưng sinh viên có họ là X
b)Liệt kê những sinh viên có mã số bắt đầu là y
c)Liệt kê những sinh viên có điểm trung bình >=z
o Giải đáp
Phần khai báo tổ ch c dữ liệu đã làm phần trước,nên phần này chỉ tập trung vào trình bày thuật
toán và cài đặt chương trình cho từng thuật toán.
a)Liệt kê những sinh viên có họ là X
Thuật toán:
- Duyệt lần lượt từng phần tử trong danh sách sinh viên từ đầu đến cuối danh sách
+ Nếu sinh viên đang xét có họ là X thì hiển thị thông tin c a sinh viên này
Cài đặt:
Pascal:
Procedure lietKe(X:string);
Var i:integer;
Begin
For i:=1 to ds.soSV
Begin
If(ds.sv[i].ho=X) then
Writeln(„ten :‟,ds.sv[i].ten,‟ masv:‟,ds.sv[i].masv,‟ dtb:‟,ds.sv[i].dtb);
End;
End;
Java:
Void lietKe(string X)
{
int i;
for(i=0;i<soSV;i++)
{
if(sv[i].ho.equals(X))
System.out.println(“ten :”+sv[i].ten+” masv:”+sv[i].masv+” dtb:”+sv[i].dtb);
}
}
b) Liệt kê những sinh viên có mã số bắt đầu là y
Thuật toán:
- Duyệt lần lượt từng phần tử trong danh sách sinh viên từ đầu đến cuối danh sách
+ Nếu sinh viên đang xét có mã số bắt đầu là y thì hiển thị thông tin c a sinh viên này
Cài đặt:
Pascal:
Procedure lietKe(y:string);
Var i:integer;
Begin
For i:=1 to ds.soSV
Begin
If(pos(ds.sv[i].masv,y)=1) then{nếu sinh viên đang xét có mã bắt đầu là y}
Writeln(„ten :‟,ds.sv[i].ten,‟ masv:‟,ds.sv[i].masv,‟ dtb:‟,ds.sv[i].dtb);
End;
End;
Java:
Void lietKe(string X)
{
int i;
for(i=0;i<soSV;i++)
{
if(sv[i].masv.substring(0,y.length()).equals(y))/*nếu sinh viên đang xét có masv bắt
đầu là y*/
System.out.println(“ten :”+sv[i].ten+” masv:”+sv[i].masv+” dtb:”+sv[i].dtb);
}
}
c)Liệt kê những sinh viên có điểm trung bình >=z
Thuật toán:
- Duyệt lần lượt từng phần tử trong danh sách sinh viên từ đầu đến cuối danh sách
+ Nếu sinh viên đang xét có điểm trung bình >=z thì hiển thị thông tin c a sinh viên này
Cài đặt:
Pascal:
Procedure lietKe(z:real);
Var i:integer;
Begin
For i:=1 to ds.soSV
Begin
If(ds.sv[i].dtb>=z) then{nếu sinh viên đang xét có điểm trung bình >=z}
Writeln(„ten :‟,ds.sv[i].ten,‟ masv:‟,ds.sv[i].masv,‟ dtb:‟,ds.sv[i].dtb);
End;
End;
Java:
Void lietKe(double z)
{
int i;
for(i=0;i<soSV;i++)
{
if(sv[i].dtb>=z)//nếu sinh viên đang xét có điểm trung bình >=z
System.out.println(“ten :”+sv[i].ten+” masv:”+sv[i].masv+” dtb:”+sv[i].dtb);
}
}
Bài 2:Khai báo tổ ch c dữ liệu cho một danh sách các cuốn sách,mỗi cuốn sách gồm tên
sách,giá tiền,các tác giả(tối đa 5 tên tác giả).Trình bày thuật toán và cài đặt cho các ch c
năng sau
a)Liệt kê các cuốn sách có giá tiền <=t
b)Liệt kê các cuốn sách có tên tác giả là tg
o Giải đáp
a)Liệt kê các cuốn sách có giá tiền <=t
Thuật toán:
- Duyệt lần lượt từng phần tử trong danh sách cuốn sách từ đầu đến cuối danh sách
+ Nếu cuốn sách đang xét có giá tiền <=t thì hiển thị thông tin c a cuốn sách này
Cài đặt:
Pascal:
Procedure lietKe(t:integer);
Var i,j:integer;
Begin
For i:=1 to ds.soCS
Begin
If(ds.cs[i].giatien<=t) then{nếu cuốn sách đang xét có giá tiền <=t thì}
Begin
Writeln(„ten :‟,ds.cs[i].ten,‟ gia tien:‟,ds.cs[i].giatien,‟ tac gia:‟);
For j:=1 to ds.cs[i].soTacGia
Write(„ „,ds.cs[i].tacgia[j]);
End;
End;
End;
Java:
Void lietKe(int t)
{
int i,j;
for(i=0;i<soSV;i++)
{
if(cs[i].giatien<=t)//nếu cuốn sách đang xét có giá tiền <=t
{
System.out.println(“ten :”+cs[i].ten+” gia tien:”+sv[i].giatien+” tac gia:”);
for(j=0;j<cs[i].laySoTacGia();j++)
System.out.print(“ “+cs[i].layTacGia[j]);
}
}
}
b)Liệt kê các cuốn sách có tên tác giả là tg
Thuật toán:
- Duyệt lần lượt từng phần tử trong danh sách cuốn sách từ đầu đến cuối danh sách
+ Nếu cuốn sách đang xét có tên tác giả là tg thì hiển thị thông tin c a cuốn sách này
Cài đặt:
Pascal:
Procedure lietKe(tg:string);
Var i,j:integer;
Begin
For i:=1 to ds.soCS
Begin
For j:=1 to ds.cs[i].soTacGia
begin
If(ds.cs[i].tacgia[j]=tg) then{nếu cuốn sách đang xét có tác giả là tg thì}
Begin
Writeln(„ten :‟,ds.cs[i].ten,‟ gia tien:‟,ds.cs[i].giatien,‟ tac gia:‟);
For j:=1 to ds.cs[i].soTacGia
Write(„ „,ds.cs[i].tacgia[j]);
Break;
End
End;
End;
End;
Java:
Void lietKe(string tg)
{
int i,j;
for(i=0;i<soSV;i++)
{
for(j=0;j<cs[i].laySoTacGia();j++)
if(cs[i].layTacGia()[j].equals(tg))//nếu cuốn sách đang xét có tác giả là tg
{
System.out.println(“ten :”+cs[i].ten+” gia tien:”+sv[i].giatien+” tac gia:”);
for(j=0;j<cs[i].laySoTacGia();j++)
System.out.print(“ “+cs[i].layTacGia()[j]);
break;
}
}
}
Duyệt để tìm kiếm:Duyệt qua tất cả các phần tử c a danh sách,khi xem xét từng phần tử c a
danh sách ta kiểm tra thông tin c a phần tử đó,nếu phù hợp với điều kiện yêu cầu từ đề bài ta
sẽ trả về kết quả là: tìm được,không tìm được,phần tử đang xét,rỗng,hoặc trả về vị trí c a
phần tử tìm được.
Ví dụ:
+ Tìm sinh viên có tên “Nguyễn Văn A” trong danh sách sinh viên,nếu có trả về true,không có trả về
false
- Điều kiện trong câu hỏi này là tên “Nguyễn Văn A” , yêu cầu đề bài là có hay không có =>ta
sẽ duyệt qua tất cả các sinh viên trong danh sách nếu có ngư i tên “Nguyễn Văn A” thì kết
quả trả về là true,ngược lại trả về false(khi ta duyệt qua tất cả các phần tử trong danh sách mà
không tìm thấy ngư i tên “Nguyễn Văn A” thì trả về kết quả là false).
*Thuật toán:
-- Duyệt lần lượt từng phần tử c a danh sách sinh viên từ đầu đến cuối danh sách
++ Nếu phần tử đang xét có tên là “Nguyễn Văn A” thì kết quả trả về là true,dừng lặp
-- Nếu không tìm thấy thì Trả về false
+ Tìm sinh viên có mã sinh viên là “10233011”,kết quả trả về phần tử ch a sinh viên
- Điều kiện đây là mã sinh viên ,yêu cầu đề bài trả về sinh viên tìm được =>ta sẽ xem trong
danh sách có mã sinh viên “10233011” hay không,nếu có trả về phần tử sinh viên,ngược lại
không tìm được thì trả về null. (khi ta duyệt qua tất cả các phần tử trong danh sách mà không
tìm thấy mã sinh viên “10233011” thì trả về kết quả là false).
-- Duyệt lần lượt từng phần tử c a danh sách sinh viên từ đầu đến cuối danh sách
++ Nếu phần tử đang xét có tên là “10233011” thì kết quả trả về là true,dừng lặp
--Nếu không tìm thấy thì Trả về false
+ Tìm địa chỉ c a sinh viên tên “Nguyễn Văn X”
- Điều kiện đây là tên “Nguyễn Văn X”,yêu cầu đề bài là tìm địa chỉ => ta sẽ duyệt qua tất cả
các phần tử c a danh sách,nếu gặp phần tử có tên “Nguyễn Văn X” thì ta lấy thông tin địa chỉ
(kiểu string)c a ngư i này.Nếu không tìm được ngư i nào có tên “Nguyễn Văn X” thì kết
quả trả về là chuỗi rỗng.
-- Duyệt lần lượt từng phần tử c a danh sách sinh viên từ đầu đến cuối danh sách
++ Nếu phần tử đang xét có tên là “Nguyễn Văn X” thì kết quả trả về là địa chỉ c a
ngư i này,dừng lặp
--Nếu không tìm thấy thì Trả về chuỗi rỗng
+ Tìm số điện thoại c a ngư i tên X
+ Tìm tên c a ch số điện thoại 01263652236
+ Tìm vị trí c a sinh viên tên X
o Giải đáp:Điều kiện tìm kiếm là tên c a sinh viên,kết quả trả về vị trí c a sinh viên này
- Duyệt lần lượt từng phần tử c a danh sách từ đầu đến cuối danh sách
+ Nếu phần tử đang xét có tên là X thì trả về vị trí c a phần tử đang xét,dừng lặp
- (Không tìm được )trả về -1
Thuật toán (duyệt để tìm kiếm):
- Duyệt lần lượt từng phần tử c a danh sách từ đầu đến cuối danh sách
+ Nếu phần tử đang xét có thông tin phù hợp với điều kiện c a để bài thì trả về kết quả theo
yêu cầu đề bài.
- (Không tìm được )trả về false,null, rỗng,hoặc -1(-1 dùng cho tìm kiếm vị trí)
Cài đặt:
Pascal:
function timkiem(dk:KieuDK):kiểu trả về;{điều kiện đề bài là dk}
var i:integer;
begin
timkiem:= false,null,-1,hoặc rỗng;{ban đầu đặt giá trị không tìm được}
for i:=1 to n do
begin
if (kiểm tra thông tin c a phần tử ds.mangpt[i] đúng với điều kiện đề bài dk) then
begin
timkiem:=thông tin của phần tử ds.mang[i] theo yêu cầu đề bài;
break;
end;
end;
{sau khi duyệt hết danh sách mà không tìm được t c là giá trị tìm kiếm đặt đâu chương trình vẫn
được giữ nguyên}
end;
chú ý: thông tin của phần tử ds.mang[i] theo yêu cầu đề bài có thể là true,vị trí phần tử cần
tìm,đối tượng phần tử cần tìm.
Java:
kiểu trả về timkiem(KieuDK dk)//dk là điều kiện c a đề bài
{
int i;
for(i=0;i<n;i++)
{
if (kiểm tra thông tin c a phần tử ds.mangpt[i] đúng với điều kiện đề bài dk)
{
return thông tin của phần tử ds.mangpt[i] theo yêu cầu đề bài;
}
}
return false,null,-1,hoặc rỗng;//không tìm thấy phần tử nào
}
chú ý: thông tin của phần tử ds.mang[i] theo yêu cầu đề bài có thể là true,vị trí phần tử cần
tìm,đối tượng phần tử cần tìm.
Ví dụ duyệt để tìm kiếm:
Bài 1:Cho danh sách sinh viên,mỗi sinh viên gồm:tên,mã sinh viên,điểm trung bình.Hãy khai báo tổ
ch c dữ liệu cho danh sách này.Sau đó trình bày thuật toán và cài đặt chương trình có ch c năng sau
a)Tìm vị trí đầu tiên c a sinh viên có tên x
b)Tìm vị trí sinh viên có điểm trung bình cao nhất
c)Kiểm tra trong danh sách có sinh viên mang mã số z
o Giải đáp
Phần khai báo tổ ch c dữ liệu đã làm phần trước,nên phần này chỉ tập trung vào trình bày thuật
toán và cài đặt chương trình cho từng thuật toán.
a)Tìm vị trí đầu tiên c a sinh viên có tên x
Thuật toán:
- Duyệt lần lượt từng phần tử trong danh sách sinh viên từ đầu đến cuối danh sách
+ Nếu sinh viên đang xét có tên là X thì trả về kết quả là vị trí c a sinh viên này
- Không tìm thấy thì trả về -1
Cài đặt:
Pascal:
function tim(X:string):integer;
Var i:integer;
Begin
tim:=-1;{không tìm thấy sinh viên tên X}
For i:=1 to ds.soSV
Begin
If(ds.sv[i].ten=X) then
tim:=i;{tìm thấy sinh viên tên X vị trí i}
End;
End;
Java:
int tim(string X)
{
int i;
for(i=0;i<soSV;i++)
{
if(sv[i].ten.equals(X))
return i;//tìm thấy sinh viên tên x
vị trí i
}
return -1;//không tìm thấy sinh viên tên x
}
b)Tìm vị trí sinh viên có điểm trung bình cao nhất
Thuật toán:
- Gán max là điểm trung bình c a sinh viên đầu tiên trong danh sách
- Gán vitri là 1
- Duyệt lần lượt từng phần tử trong danh sách sinh viên từ đầu đến cuối danh sách
+ Nếu sinh viên đang xét có điểm trung bình >max thì
*Gán max là điểm trung bình c a sinh viên này
*Gán vitri là vị trí c a sinh viên này
- Trả về kết quả là vitri
Cài đặt:
Pascal:
Function timvtMax():integer;
Var i,vitri:integer;
Var max:real;
Begin
max:=ds.sv[1].dtb;
vitri:=1;
For i:=1 to ds.soSV
Begin
If(ds.sv[i].dtb>max) then
Begin
max:= ds.sv[i].dtb;
vitri:=i;
End;
End;
timvtMax:=vitri;
End;
Java:
int timvtMax()
{
int i,vitri;
double max;
for(i=0;i<soSV;i++)
{
if(sv[i].dtb>max)
{
max:= sv[i].dtb;
vitri:=i;
}
}
return vitri;
}
c)Kiểm tra trong danh sách có sinh viên mang mã số z
Thuật toán:
- Duyệt lần lượt từng phần tử trong danh sách sinh viên từ đầu đến cuối danh sách
+ Nếu sinh viên đang xét có mã số là z thì kết quả trả về là true,dừng lặp
- Nếu không tìm thấy thì kết quả trả về là false
Cài đặt:
Pascal:
function tim(z:string):boolean;
Var i:integer;
Begin
tim:=false;
For i:=1 to ds.soSV
Begin
If(ds.sv[i].masv=z) then
Begin
tim:=true;
Break;
End;
End;
End;
Java:
boolean tim(string z)
{
int i;
for(i=0;i<soSV;i++)
{
if(sv[i].masv.equals(z))
return true;
}
return false;
}
Duyệt để đếm: Duyệt qua tất cả các phần tử c a danh sách,khi xem xét từng phần tử c a
danh sách ta kiểm tra thông tin c a phần tử đó,nếu phù hợp với điều kiện yêu cầu từ đề bài ta
sẽ đếm số phần tử cùng điều kiện c a đề bài.
Ví dụ:
+ Đếm số ngư i có điểm trung bình trên 5
+ Đếm số ngư i có cùng họ “Nguyễn”
+ Đếm số điện thoại có đầu số 098
+ Đếm số ngư i cùng địa chỉ “Quy Nhơn”
+ Đếm số lượng số nhỏ hơn 22 trong một mảng số nguyên
+ Đếm số lượng số lớn hơn 26 nhỏ hơn 45 trong một mảng số nguyên
+ Đếm số sinh viên có điểm trung bình lớn hơn 6.5 nhỏ hơn 8.0
+ Đếm số điện thoại có đầu số 0168 hoặc 0169
+ Đếm số điện thoại có số đuôi là 165
+ Đếm số ngư i cùng họ “Nguyễn” và có điểm trung bình lớn hơn 6.0
+ Đếm số sách lớp 10 và có mệnh giá lớn hơn 25 ngàn
+ Đếm số sách thể loại “truyện tranh” trong thư viện
Chú ý:Trên đây là một số ví dụ về đếm có điều kiện,điều kiện c a đề bài có thể là được kết hợp từ
nhiều thông tin c a phần tử trong danh sách.Với mỗi phần tử trong danh sách ta kiểm tra thông tin
c a phần tử với điều kiện c a đề bài.Kết quả c a việc đếm chính là số lượng phần tử có thông tin
phù hợp với điều kiện từ đề bài.
Thuật toán:
- Duyệt lần lượt từng phần tử c a danh sách từ đầu đến cuối danh sách
+ Nếu thông tin c a phần tử đang xét phù hợp với điều kiện c a đề bài thì tăng biến đếm
thêm 1.
- Trả về kết quả là biến đếm.
Giải thích thuật toán:Với mỗi phần tử phù hợp với điều kiện c a đề bài thì tăng biến đếm thêm 1,sau
khi duyệt qua hết tất cả các phần tử c a danh sách thì trả về kết quả là biến đếm.
Cài đặt:
Pascal:
function dem(dk:KieuDK):integer;
var i,d:integer;
begin
d:=0;
for i:=1 to n do
begin
if(kiểm tra thông tin ds.a[i] đúng với điều kiện từ đề bài dk) then
begin
d:=d+1;{tăng biến d(đếm) thêm 1}
end;
end;
dem:=d;{trả về kết quả là giá trị trong biến d}
end;
Java:
int dem(KieuDK dk)
{
int i,d=0;
for(i=0;i<n;i++)
{
if(kiểm tra thông tin ds.a[i] đúng với điều kiện từ đề bài dk)
{
d=d+1;//tăng biến d(đếm) thêm 1
}
}
return d;//trả về kết quả là giá trị c a biến d
}
Thao tác thêm(chèn):
+ Thêm t c là đưa thêm một phần tử mới vào danh sách,số phần tử c a danh sách tăng thêm 1, Khi
thêm một phần tử vào danh sách phải đảm bảo danh sách sau khi thêm ch a phần tử mới và tất cả
các phần tử c a danh sách cũ(danh sách trước khi thêm).Như vậy vị trí cần thêm ta phải di d i
phần tử cũ sang một vị trí khác thì ta mới có chỗ trống cho phần tử mới.Vậy phải di d i sao cho các
phần tử cũ c a danh sách không bị mất đi.
Ví dụ:
Đầu tiên ta ví dụ một danh sách số điện thoại c a sinh viên được ghi trên giấy:
Để thêm một số điện thoại vào danh sách thì ta có 2 cách thêm đó là:thêm vào các vị trí đã có số
điện thoại hoặc thêm vào cuối danh sách này.
Để thêm vào vị trí đã có số điện thoại ta cần có một t giấy trắng,tiến hành chép lại các số điện thoại
từ đầu đến vị trí trước vị trí cần thêm trong danh sách cũ vào t giấy trắng,sau đó viết tiếp số điện
thoại cần thêm vào t giấy này,cuối cùng chép các số điện thoại còn lại trong danh sách cũ vào t
giấy.Minh họa bằng hình ảnh như sau:
1.0123547898
2.0166852222
3.0165223133
4.0983564631
5.0962646413
6.0122665656
……………
n-1.0122564665
n:0188656565
1.0123547898
2.0166852222
3.0165223133
4.0983564631
5.0123445566
6.0962646413
7.0122665656
……………
n.0122564665
n+1.0188656565
Sao chép
0123445566
Sao chép
hình trên ,số điện thoại cần thêm là 0123445566,vị trí cần thêm là vị trí th 5(th tự bắt đầu từ
1).Đây gọi là thêm vào vị trí th k trong danh sách(k € [1,sopt],sopt là số phần tử).
Để thêm một phần tử vào cuối danh sách thì rất dễ dàng ta chỉ cần viết nó vào sau phần tử cuối cùng
c a danh sách cũ.t c là thêm vào vị trí th sopt+1.
Danh sách tổ ch c bằng mảng trên máy tính có điểm thuận lợi hơn danh sách trên giấy,vì có thể xóa
dữ liệu và ghi mới dữ liệu một cách dễ dàng.Nên việc thêm một phần tử vào danh sách thực hiện dễ
dàng hơn mà không cần tạo thêm một danh sách mới như làm việc trên giấy.
Thêm vào vị trí k (k€[1 đến sopt],với sopt là số phần tử c a danh sách hiện tại):
Công việc thêm sẽ làm như sau:di chuyển các phần tử c a danh sách từ vị trí k đến sopt ra sau một
vị trí,sau đó đưa phần tử cần thêm vào vị trí k.
Chi tiết hơn cho công việc này là:duyệt lần lượt các phần tử c a danh sách từ cuối(vị trí sopt) về vị
trí k,d i phần tử đang xét ra sau 1 vị trí.
1
2
3
4
5
6
n-1
n
5
6
n-1
n
vị trí th k
1
2
3
4
Phần tử mới
Việc thêm phần tử vào danh sách tổ ch c bằng mảng cũng giống như việc một ngư i chen vào hàng
ngư i đang mua vé tàu.Khi ngư i này chen vào thì những ngư i phía sau ngư i này buộc lòng phải
lùi ra sau thì mới có chỗ đ ng.Và trên máy tính việc làm này cũng giống vậy,giống như việc một
ngư i xin vào hàng và được những ngư i khác đồng ý và họ sẽ như ng vị trí này,để có chỗ trống
bắt buộc ngư i sau cùng phải lùi ra sau trước tiên,tiếp đến những ngư i khác từ sau tr về trước
phải lùi ra sau.Việc làm này tránh ngư i này dẫm lên chân ngư i kia,cũng giống như trong máy tính
làm vậy sẽ không bị mất bất c một phần tử nào trong danh sách.
Thuật toán thêm một phần tử vào vị trí k:
- Duyệt lần lượt từng phần tử trong danh sách từ cuối về vị trí k
+ chuyển phần tử đang xét ra sau 1 vị trí
- Đưa phần tử cần thêm vào vị trí k
Chi tiết hơn:
- Duyệt lần lượt từng phần tử trong danh sách từ vị trí sopt về vị trí k
+ đưa phần tử đang xét ra sau 1 vị trí
- Đưa phần tử cần thêm vào vị trí k
Cài đặt:
Pascal:
procedure them(pt:KieuPT;k:integer);{pt là phần tử cần thêm,k là vị trí cần thêm}
var i:integer;
begin
for i:=sopt downto k do
begin
ds.a[i+1]=ds.a[i];{chuyển phần tử đang xét ra sau 1 vị trí hay gán phần tử sau bằng
phần tử trước}
end;
ds.a[k]=pt;{đưa phần tử cần thêm vào vị trí k}
end;
Java:
void them(KieuPT pt,int k)
{
int i;
for(i=sopt-1;i>=k;i--)
{
a[i+1]=a[i];
}
a[k]=pt;
}
Chú ý:Thao tác thêm được mô tả trên đây chỉ còn một điều kiện đơn giản khi thêm điều kiện là vị trí
cần thêm trong mảng.Nhưng trong nhiều bài toán thao tác thêm có thể có các điều kiện khác như
thêm một phần tử sau phần tử có tên x,hoặc thêm một sinh viên vào sau sinh viên có mã sinh viên y.
Thêm có điều kiện ta cũng làm tương tự như thêm vào vị trí k,nhưng lúc này ta chưa biết vị trí cần
thêm do đó ta cần phải tìm ra vị trí cần thêm đúng theo yêu cầu đề bài,với vị trí tìm được ta dùng
thuật toán thêm phần tử vào vị trí k để giải quyết.Nếu không tìm được vị trí cần thêm thì không
thêm phần tử vào danh sách.
Ví dụ:
+ Thêm một sinh viên vào sau sinh viên tên x trong danh sách sinh viên
+ Thêm một số điện thoại vào sau số điện thoại y
+ Thêm một môn học vào danh sách môn học c a ngư i tên z
+ Nhập điểm môn cấu trúc dữ liệu cho sinh viên có mã số x
Trên đây là một số ví dụ cơ bản cho việc thêm có điều kiện,việc kết hợp nhiều thông tin c a phần tử
để tìm được vị trí cần thêm thì việc thêm tr thành thêm có điều kiện.
Thuật toán:
- Duyệt lần lượt từng phần tử c a danh sách từ đầu đến cuối danh sách
+ Nếu phần tử đang xét thỏa điều kiện đề bài,vị trí c a phần tử này gọi là vị trí k,dừng lặp
- Duyệt lần lượt từng phần tử c a danh sách từ cuối về vị trí k
+ Chuyển phần tử đang xét ra sau 1 vị trí
- Đưa phần tử cần thêm vào vị trí k
Cài đặt:
Pascal:
procedure them(pt:KieuPT;dk:KieuDK);{pt phần tử cần thêm,dk điều kiện thêm}
var i,k:integer;
begin
for i:=1 to sopt do
begin
if(thông tin c a phần tử ds.a[i] đúng với điều kiện đề bài dk) then
begin
i+1;nếu đề bài yêu cầu thêm vào sau phần tử có điều kiện dk
k=
i;nếu đề bài yêu cầu thêm vào vị trí c a phần tử có điều kiện dk
break;
end;
end;
for i:=sopt downto k do
begin
ds.a[i+1]:=ds.a[i];{chuyển phần tử đang xét ra sau 1 vị trí}
end;
ds.a[k]=pt;{đưa phần tử cần thêm vào vị trí k}
end;
Java:
void them(KieuPT pt,KieuDK dk)
{
int i,k;
for(i=0;i<sopt;i++)
{
if(thông tin c a phần tử a[i] đúng với yêu cầu đề bài dk)
{
i+1;nếu đề bài yêu cầu thêm vào sau phần tử có điều kiện dk
k=
i;nếu đề bài yêu cầu thêm vào vị trí c a phần tử có điều kiện dk
break;
}
}
for(i=sopt-1;i>=k;i--)
{
a[i+1]=a[i];
}
a[k]=pt;
}
Thao tác xóa:
Xóa phần tử trong danh sách là công việc loại bỏ phần tử ra khỏi danh sách,làm giảm bớt số phần tử
không cần thiết trong danh sách.Nếu trên giấy ta loại bỏ bằng cách gạch tên những ngư i trong danh
sách.
Thuật toán xóa phần tử vị trí th k:Chuyển các phần tử từ vị trí sau k đến cuối danh sách lên trước
một vị trí.T c là ta thay thế phần tử th k bằng phần tử th k+1,phần tử k+1 được thay bằng phần tử
k+2,lặp cho đến phần tử th sopt-1 được thay bằng phần tử th n.
- Duyệt lần lượt từng phần tử trong danh sách từ vị trí k đến sopt-1
+ Đặt phần tử đang xét là phần tử liền sau nó
- Giảm số phần tử đi 1
Cài đặt:
Pascal:
procedure xoa(k:integer);
var i:integer;
begin
for i:=k to sopt-1 do
begin
ds.a[i]=ds.a[i+1];{đặt phần tử đang xét là phần tử liền sau nó}
end;
sopt:=sopt-1;{giảm số phần tử đi 1}
end;
Java:
void xoa(int k)
{
int i;
for(i=k;i<sopt-1;i++)
{
a[i]=a[i+1];//đặt phần tử đang xét là phần tử liền sau nó
}
sopt--;//giảm số phần tử đi 1
}
Xóa có điều kiện:Tìm trong danh sách nếu thông tin c a phần tử nào trong danh sách phù hợp với
điều kiện xóa thì tiến hành xóa phần tử này.T c là duyệt lần lượt từng phần tử,nếu phần tử đang xét
có ch a thông tin phù hợp với điều kiện c a đề bài ta tiến hành xóa phần tử này.
- Có hai loại thao tác xóa:
+ Chỉ xóa một phần tử
+ Xóa nhiều phần tử hoặc tất cả phần tử có cùng điều kiện
Xóa một phần tử theo điều kiện bài toán:Tìm phần tử cần xóa theo điều kiện từ đề bài sau đó tiến
hành xóa
Xóa nhiều phần tử theo điều kiện bài toán:Ta có một cách giải quyết đơn giản đó là với mỗi phần tử
tìm được ta tiến hành xóa phần tử đó,lặp lại quá trình này cho đến khi không tìm thấy phần tử nào
thỏa điều kiện bài toán.
Một cách giải quyết tốt hơn đó là với mỗi phần từ cần xóa ta không ghi nó tr lại danh sách,ta chỉ
ghi những phần tử không phù hợp với điều kiện bài toán tr lại danh sách.Cách này giống như lập
một danh sách mới,do dữ liệu trên máy tính có thể xóa và ghi dễ dàng.
Một kỹ thuật để giải quyết việc xóa nhiều phần tử đó là ta dùng một biến giữ vị trí mà ta sẽ ghi phần
tử cần ghi vào vị trí đó,những phần tử nào cần xóa thì bỏ qua.Gọi p là biến lưu vị trí cần ghi,kh i tạo
p=0,với mỗi phần tử không thỏa điều kiện xóa thì ta tăng p thêm 1 và ta ghi phần tử này vào vị trí p,
nếu gặp phần tử cần xóa thì ta không làm gì cả,sau khi đã duyệt qua hết tất cả phần tử c a danh sách
thì p chính là số phần tử còn lại sau khi xóa.
Thuật toán:
- Gán p=0
- Duyệt lần lượt từng phần tử trong danh sách từ đầu đến cuối danh sách
+ Nếu phần tử đang xét có thông tin không thỏa mãn điều kiện đề bài thì
*Tăng p thêm 1
*Đưa phần tử đang xét vào vị trí p.
- Gán số phần tử là p
Ví dụ:Xóa tất cả những số điện thoại có đầu số 0123 trong danh bạ.
Điều kiện cần xóa là đầu số 0123,Thuật toán giải quyết như sau:Duyệt lần lượt từng phần tử từ đầu
đến cuối danh sách,ghi lại những số điện thoại có đầu số khác 0123.
- Gán p=0
- Duyệt lần lượt từng phần tử trong danh bạ từ đầu đến cuối danh bạ
+ Nếu phần tử đang xét có đầu số khác 0123 thì
*Tăng p thêm 1
*Đưa số điện thoại đang xét vào vị trí p
- Gán số phần tử là p
2.Danh sách liên kết đơn:
Tổ ch c dữ liệu danh sách liên kết đơn:
Mỗi phần tử trong danh sách liên kết đơn gồm hai thành phần:
+ Phần dữ liệu c a từng phần tử trong danh sách,thuộc kiểu KieuPT
+ Phần lienKet là địa chỉ c a phần tử mà nó liên kết đến
Một danh sách liên kết đơn gồm một thành phần:
+ Một ô nhớ lưu phần tử đầu c a danh sách.
Khai báo cho danh sách liên kết đơn:
Pascal:
TYPE
KieuPT=RECORD{khai báo phần dữ liệu}
Thuộc tính 1:kiểu dữ liệu 1;
Thuộc tính 2:kiểu dữ liệu 2;
Thuộc tính 3:kiểu dữ liệu 3;
…
Thuộc tính n:kiểu dữ liệu n;
DSLK=^PTLK;
PTLK=record
dulieu:KieuPT;
lienKet:DSLK;
END;
var dau:DSLK;
Chú ý:
+KieuPT là tên kiểu dữ liệu mình tự định nghĩa ,đặt tên sao cho sát với tên c a đối
tượng cần lưu trữ c a danh sách mình đang làm việc,ví dụ danh sách sinh viên thì đối tượng
cần lưu trữ là Sinh Viên suy ra KieuPT là SinhVien
+các loại kiểu dữ liệu 1 , kiểu dữ liệu 2, kiểu dữ liệu 3 là các kiểu dữ liệu phù hợp cho
từng thuộc tính ,ví dụ :thuộc tính 1 là họ tên thì kiểu dữ liệu 1 là kiểu string (kiểu
chuỗi),thuộc tính 2 là mã số sinh viên thì kiểu dữ liệu 2 là kiểu string (kiểu chuỗi),thuộc tính
3 nếu dùng để lưu trữ số nguyên thì kiểu dữ liệu 3 là kiểu integer (kiểu số nguyên),nếu thuộc
tính 4 dùng để lưu trữ điểm trung bình thì kiểu dữ liệu 4 là kiểu real(kiểu số thực ,vì điểm
trung bình thư ng là số có phần lẻ thập phân ví dụ:7.5 ,8.6 …).Tổng quát là tùy vào giá trị
cần lưu trữ là chuỗi kí tự thì dùng kiểu string ,nếu lưu trữ số nguyên thì là kiểu integer,số
thực thì là kiểu real.
Java:
class KieuPT
{
private kiểu dữ liệu 1 Thuộc tính 1;
private kiểu dữ liệu 2 Thuộc tính 2;
private kiểu dữ liệu 3 Thuộc tính 3;
…
private kiểu dữ liệu n Thuộc tính n;
…
}
class PTLK
{
private KieuPT duLieu;
private PTLK lienKet;
…
}
class DSLK
{
private PTLK dau;
…
}
Chú ý:
+ PTLK tên đặt cho kiểu phần tử liên kết.
+ KieuPT tên c a kiểu dữ liệu cho mỗi phần tử trong danh sách(giống cách đặt tên cho
KieuPT phần mảng).
+lienKet tên đặt cho thuộc tính liên kết.
chú ý:
+DSLK tên c a danh sách,ví dụ danh sách sinh viên thì đặt tên là DSSV(giống như cách đặt
tên trong danh sách tổ ch c bằng mảng).
+dau đây là tên c a biến lưu địa chỉ đầu c a danh sách liên kết đơn,ta cũng chọn tên là dau
luôn.
+PTLK tên c a kiểu phần tử liên kết đã khai báo trước đó.
Ví dụ khai báo danh sách liên kết đơn:
Bài 1:Cho danh sách sinh viên,mỗi sinh viên gồm:tên,mã sinh viên,điểm trung bình.Hãy khai báo tổ
ch c dữ liệu cho danh sách này.
Mỗi sinh viên gồm 3 thành phần:
+Phần tên thuộc kiểu xâu kí tự
+Phần mã sinh viên thuộc kiểu xâu kí tự
+Phần điểm trung bình thuộc kiểu số thực
Tổ ch c dữ liệu danh sách sinh viên bằng danh sách liên kết đơn gồm 2 thành phần:
+Phần dữ liệu c a mỗi phần tử trong danh sách,thuộc kiểu sinh viên
+Phần liên kết là phần tử mà nó liên kết đến
Khai báo:
Pascal:
TYPE
SinhVien=record
ten:string;
maSV:string;
dtb:real;
DSLK=^PTLK;
PTLK=record
sv:SinhVien;
lienket:DSLK;
END;
var dau:DSLK;
Java:
class SinhVien
{
private string ten;
private string masv;
private double dtb;
…
}
class PTLK
{
private SinhVien sv;
private PTLK lienKet;
…
}
class DSLK
{
private PTLK dau;
…
}
Bài 2:Khai báo tổ ch c dữ liệu cho một danh sách các cuốn sách,mỗi cuốn sách gồm tên
sách,giá tiền,các tác giả(tối đa 5 tác giả).
Mỗi cuốn sách gồm 3 thành phần:
+Phần tên sách thuộc kiểu xâu kí tự
+Phần giá tiền thuộc kiểu số nguyên
+Phần tác giả là một mảng tên các tác giả,mỗi tác giả thuộc kiểu xâu kí tự
Tổ ch c dữ liệu danh sách cuốn sách bằng danh sách liên kết đơn gồm 2 thành phần:
+Phần dữ liệu c a mỗi phần tử trong danh sách,thuộc kiểu cuốn sách
+Phần liên kết là phần tử mà nó liên kết đến
Khai báo:
Pascal:
TYPE
CuonSach=record
tensach:string;
giatien:integer;
tacgia:array[1..5] of string;
DSLK=^PTLK;
PTLK=record
cs:CuonSach;
lienket:DSLK;
END;
var dau:DSLK;
Java:
class CuonSach
{
private string ten;
private int giaTien;
private string tacGia[];
…
}
class PTLK
{
private CuonSach cs;
private PTLK lienKet;
…
}
class DSLK
{
private PTLK dau;
…
}
Bài 3:Một khách sạn A có rất nhiều phòng cho thuê,mỗi phòng gồm:mã phòng,tên ngư i
thuê,th i gian thuê.Hãy khai báo tổ ch c dữ liệu để quản lý các phòng cho khách sạn này.
Mỗi phòng gồm 3 thành phần:
+Phần mã phòng thuộc kiểu xâu kí tự
+Phần tên ngư i thuê thuộc kiểu xâu kí tự
+Phần th i gian thuê thuộc kiểu số nguyên
Tổ ch c dữ liệu danh sách phòng bằng danh sách liên kết đơn gồm 2 thành phần:
+Phần dữ liệu c a mỗi phần tử trong danh sách,thuộc kiểu phòng
+Phần liên kết là phần tử mà nó liên kết đến
TYPE
Phong=record
maphong:string;
tennguoithue:string;
thoigianthue:integer;
DSLK=^PTLK;
PTLK=record
ph:Phong;
lienket:DSLK;
END;
var dau:DSLK;
Java:
class Phong
{
private string maPhong;
private string tenKH;
private int thoiGian;
…
}
class PTLK
{
private Phong ph;
private PTLK lienKet;
…
}
class DSLK
{
private PTLK dau;
…
}
Bài 4:Một cửa hàng tạp hóa có bảng hóa đơn,mỗi hàng hóa gồm:, tên mặt hàng,số lượng,đơn
giá,thành tiền.Bạn hãy khai báo tổ ch c dữ liệu cho mỗi hóa đơn,biết mỗi hóa đơn có tối đa
10 hàng hóa .Khai báo tổ ch c dữ liệu cho danh sách các hóa đơn
o Giải đáp
Mỗi hàng hóa gồm 4 thành phần:
+Phần tên thuộc kiểu xâu
+Phần số lượng thuộc kiểu số nguyên
+Phần đơn giá thuộc kiểu số nguyên
+Phần thành tiền thuộc kiểu số nguyên
Tổ ch c dữ liệu bằng mảng cho mỗi hóa đơn gồm 2 thành phần:
+Phần mảng lưu tất cả các phần tử c a danh sách,mà mỗi phần tử là một hàng hóa
+Một ô nhớ lưu số lượng hàng hóa trong danh sách
Tổ ch c dữ liệu bằng danh sách liên kết đơn cho danh sách các hóa đơn gồm 2 thành phần:
+Phần dữ liệu c a mỗi phần tử trong danh sách,kiểu dữ liệu là hóa đơn
+Phần liên kết là phần tử mà nó liên kết đến
TYPE
HangHoa=record
tenHH:string;
soLuong:integer;
donGia:integer;
thanhTien:integer;
HoaDon=record
hh:array[1...Max_HH] of HangHoa;
soHH:1..Max_HH;
DSLK=^PTLK;
PTLK=record
hd:HoaDon;
lienket:DSLK;
end;
var dau:DSLK;
Java:
class HangHoa
{
private string tenHH;
private int soLuong;
private int donGia;
private int thanhTien;
…
}
class HoaDon
{
private HangHoa hh[];
private int soHH;
…
}
class PTLK
{
private HoaDon hd;
private PTLK lienKet;
…
}
class DSLK
{
private PTLK dau;
…
}
Duyệt cơ bản:
Tổng quan danh sách liên kết đơn:
+Danh sách liên kết đơn là danh sách mà mỗi phần tử đều có một thành phần lưu giữ vị trí c a phần
tử sau nó(vị trí này gọi là thành phần liên kết).
+Danh sách đơn có một ô nhớ lưu giữ phần tử đầu tiên c a danh sách.
+Phần tử cuối cùng c a danh sách liên kết đơn sẽ liên kết đến phần tử rỗng.
Thuật toán duyệt trong danh sách liên kết đơn:Gán p là phần tử đầu c a danh sách,Lặp trong khi p
khác rỗng,chuyển p sang phần tử ngay sau nó.
Thuật toán:
- Gán p là phần tử đầu
- Lặp trong khi p khác rỗng
+Thao tác với phần tử p(thao tác:hiển thị,đếm,kiểm tra,so sánh,…)
+Chuyển p sang phần tử ngay sau nó
Giải thích thuật toán:Vì trong mỗi phần tử đều ch a một địa chỉ là vị trí c a phần tử phía sau nó.Do
đó khi ta đang một phần tử nào đó ta hoàn toàn có thể chuyển sang phần tử sau nó,lặp lại với các
phần tử còn lại cho đến khi gặp phần tử rỗng thì ta đã tới thăm tất cả các phần tử c a danh sách.
Duyệt có điều kiện:Duyệt các phần tử c a danh sách nhưng chỉ quan tâm đến những phần tử có ch a
thông tin thỏa mãn yêu cầu bài toán.Có nghĩa ta phải đi qua tất cả các phần tử c a danh sách nhưng
chỉ quan quân đến các phần tử thỏa mãn yêu cầu bài toán.
Thuật toán duyệt có điều kiện:Gán p là phần tử đầu,Lặp trong khi p khác rỗng,thao tác với thông tin
c a phần tử p với điều kiện từ bài toán,chuyển p sang phần tử ngay sau nó.
Thuật toán:
- Gán p là phần tử đầu
-
Lặp trong khi p khác rỗng
+ Nếu thông tin c a phần tử p thỏa mãn yêu cầu bài toán thì thực hiện các thao tác với phần
tử này (ví dụ như:đếm,hiển thị,kiểm tra,so sánh,…).
+ Chuyển p sang phần tử ngay sau nó
Giải thích thuật toán:Với mỗi phần tử c a danh sách ta kiểm tra thông tin phần tử này ,nếu thỏa mãn
yêu cầu đề bài thì thực hiện thao tác trên phần tử này.
Ví dụ:hiển thị sinh viên có điểm số lớn hơn 5.0
Điều kiện hiển thị:điểm số lớn hơn 5.0
Thuật toán:
- Gán p là phần tử đầu c a danh sách sinh viên
- Lặp trong khi p khác rỗng
+ Nếu dữ liệu điểm c a phần tử p lớn hơn 5.0 thì
*Hiển thị dữ liệu c a p
+ Chuyển p sang phần tử ngay sau nó
Ví dụ c a duyệt có điều kiện:
+ Kiểm tra xem có sinh viên tên x trong danh sách hay không
+ Liệt kê các sinh viên có điểm trung bình lớn hơn 7.5 và nhỏ hơn 8.0
+ Đếm số lượng số điện thoại c a ngư i tên x
+ Đếm số sinh viên lớp k36 học môn cấu trúc dữ liệu
+ Đếm số lượng số điện thoại có số đuôi là 123
+ Liệt kê những cuốn sách thể loại toán học
Và rất nhiều những ví dụ liên quan đến duyệt,nhưng mọi chuyện thực sự đơn giản chỉ là việc kết
hợp các thông tin c a phần tử để tạo ra điều kiện ph c tạp hơn,còn thao tác thì ch yếu là:liệt
kê,đếm,tìm kiếm.
Ta nhận thấy thao tác duyệt trên danh sách liên kết đơn cũng tương tự như danh sách tổ ch c bằng
mảng.
-
Các loại duyệt có điều kiện với danh sách liên kết đơn:
Duyệt để liệt kê
Duyệt để tìm kiếm
Duyệt để đếm
Duyệt để liệt kê:liệt kê
đây là hiển thị ra những thông tin theo yêu cầu c a đề bài
Ví dụ:
+Liệt kê sinh viên t c là hiển thị ra tất cả các thông tin về sinh viên như :tên,mã sinh viên,địa
chỉ,điểm,…
+Liệt kê tên c a tất cả các sinh viên thì thông tin cần hiển thị là tên sinh viên
+Liệt kê điểm c a tất cả các sinh viên thì thông tin cần hiển thị là điểm
Chú ý:các loại liệt kê trên là liệt kê không có điều kiện,ch yếu chúng ta cần quan tâm là liệt kê có
điều kiện,ví dụ:liệt kê các sinh viên tên “Nguyễn Văn A”,liệt kê các sinh viên có điểm số lớn hơn
a,liệt kê các sinh viên quê “Bình Định”.
Như vậy trong duyệt để liệt kê còn có thêm phần điều kiện,nhưng ta dễ thấy những điều kiện c a đề
bài sẽ dùng để kiểm tra thông tin c a phần tử trong danh sách,nếu thông tin c a phần tử phù hợp với
điều kiện yêu cầu từ đề bài thì ta sẽ hiển thị thông tin c a phần tử đúng với điều kiện đề bài.
Thuật toán:
- Gán p là phần tử đầu c a danh sách
- Lặp trong khi p khác rỗng
+ Nếu thông tin c a phần tử p phù hợp với yêu cầu đề bài thì hiển thị ra thông tin c a phần tử
p(theo yêu cầu c a đề bài).
+ Chuyển p sang phần tử ngay sau nó
Cài đặt:
Pascal:
procedure lietKe(dk:KieuDK);
var p:PTLK;{p thuộc kiểu phần tử liên kết}
begin
p:=dau;{dau:phần tử đầu c a danh sách}
while (p<>nil) do
begin
if( thông tin c a p đúng với điều kiện dk )then
begin
{hiển thị ra thông tin c a phần tử p theo yêu cầu đề bài}
end;
p:=p.lienket;{chuyển p sang phần tử ngay sau nó}
end;
end;
Java:
void lietKe(KieuDK dk)
{
PTLK p=dau;//gán p là phần tử đầu c a danh sách
while(p!=null)
{
if(thông tin c a p phù hợp với điều kiện dk)
{
//hiển thị ra những thông tin mà đề bài yêu cầu c a phần tử p
}
p=p.layLienKet();//chuyển p sang phần tử ngay sau nó
}
}
Duyệt để tìm kiếm:Duyệt qua tất cả các phần tử c a danh sách,khi xem xét từng phần tử c a
danh sách ta kiểm tra thông tin c a phần tử đó,nếu phù hợp với điều kiện yêu cầu từ đề bài ta
sẽ trả về kết quả là: tìm được,không tìm được,phần tử đang xét,hoặc rỗng.
Ví dụ:
+ Tìm sinh viên có tên “Nguyễn Văn A” trong danh sách sinh viên,nếu có trả về true,không có trả về
false
- Điều kiện trong câu hỏi này là tên “Nguyễn Văn A” , yêu cầu đề bài là có hay không có =>ta
sẽ duyệt qua tất cả các sinh viên trong danh sách nếu có ngư i tên “Nguyễn Văn A” thì kết
quả trả về là true,ngược lại trả về false(khi ta duyệt qua tất cả các phần tử trong danh sách mà
không tìm thấy ngư i tên “Nguyễn Văn A” thì trả về kết quả là false).
*Thuật toán:
-- Gán p là phần tử đầu c a danh sách
-- Lặp trong khi p khác rỗng
++ Nếu phần tử p có ch a tên là “Nguyễn Văn A” thì kết quả trả về là true,dừng lặp
++ Chuyển p sang phần tử ngay sau nó
-- Nếu không có sinh viên nào tên “Nguyễn Văn A” thì Trả về false
+ Tìm sinh viên có mã sinh viên là “10233011”,kết quả trả về phần tử ch a sinh viên
- Điều kiện đây là mã sinh viên ,yêu cầu đề bài trả về sinh viên tìm được =>ta sẽ xem trong
danh sách có mã sinh viên “10233011” hay không,nếu có trả về phần tử sinh viên,ngược lại
không tìm được thì trả về null. (khi ta duyệt qua tất cả các phần tử trong danh sách mà không
tìm thấy ngư i tên “10233011” thì trả về kết quả là false).
-- Gán p là phần tử đầu c a danh sách sinh viên
-- Lặp trong khi p khác rỗng
++ Nếu phần tử p có ch a tên là “10233011” thì kết quả trả về là true,dừng lặp
++ Chuyển p sang phần tử ngay sau nó
--Nếu không có sinh viên “Nguyễn Văn A” thì Trả về false
+ Tìm địa chỉ c a sinh viên tên “Nguyễn Văn X”
- Điều kiện đây là tên “Nguyễn Văn X”,yêu cầu đề bài là tìm địa chỉ => ta sẽ duyệt qua tất cả
các phần tử c a danh sách,nếu gặp phần tử có tên “Nguyễn Văn X” thì ta lấy thông tin địa chỉ
(kiểu string)c a ngư i này.Nếu không tìm được ngư i nào có tên “Nguyễn Văn X” thì kết
quả trả về là chuỗi rỗng.
-- Gán p là phần tử đầu c a danh sách sinh viên
-- Duyệt lần lượt từng phần tử c a danh sách sinh viên từ đầu đến cuối danh sách
++ Nếu phần tử p có ch a tên là “Nguyễn Văn X” thì kết quả trả về là địa chỉ c a
ngư i này,dừng lặp
++ Chuyển p sang phần tử ngay sau nó
--Nếu không có sinh viên nào tên “Nguyễn Văn X” thì Trả về chuỗi rỗng
+ Tìm số điện thoại c a ngư i tên X
+ Tìm tên c a ch số điện thoại 01263652236
Thuật toán (duyệt để tìm kiếm):
- Gán p là phần tử đầu c a danh sách
- Lặp trong khi p khác rỗng
+ Nếu phần tử p có thông tin phù hợp với điều kiện c a để bài thì trả về kết quả theo yêu cầu
đề bài.
+ Chuyển p sang phần tử ngay sau nó
- (Không tìm được )trả về false,null,hoặc rỗng
Cài đặt:
Pascal:
function timkiem(dk:KieuDK):kiểu trả về;{điều kiện đề bài là dk}
var p:PTLK;{p thuộc kiểu phần tử liên kết}
begin
timkiem:= false,null,hoặc rỗng;
p:=dau;{gán p là phần tử đầu c a danh sách liên kết đơn}
while(p<>nil) do
begin
if (kiểm tra thông tin c a phần tử p đúng với điều kiện đề bài dk) then
begin
timkiem:=thông tin c a phần tử p theo yêu cầu đề bài;
break;
end;
p:=p.lienket;{Chuyển p sang phần tử ngay sau nó}
end;
end;
Java:
kiểu trả về timkiem(KieuDK dk)//dk là điều kiện c a đề bài
{
PTLK p=dau;//gán p là phần tử đầu c a danh sách
while(p!=null)
{
if (kiểm tra thông tin c a phần tử p đúng với điều kiện đề bài dk)
{
return thông tin c a phần tử p theo yêu cầu đề bài;
}
p=p.layLienKet();//chuyển p sang phần tử ngay sau nó
}
return false,null,hoặc rỗng;
}
Duyệt để đếm: Duyệt qua tất cả các phần tử c a danh sách,khi xem xét từng phần tử c a
danh sách ta kiểm tra thông tin c a phần tử đó,nếu phù hợp với điều kiện yêu cầu từ đề bài ta
sẽ đếm số phần tử cùng điều kiện c a đề bài.
Ví dụ:
+ Đếm số ngư i có điểm trung bình trên 5
+ Đếm số ngư i có cùng họ “Nguyễn”
+ Đếm số điện thoại có đầu số 098
+ Đếm số ngư i cùng địa chỉ “Quy Nhơn”
+ Đếm số lượng số nhỏ hơn 22 trong một mảng số nguyên
+ Đếm số lượng số lớn hơn 26 nhỏ hơn 45 trong một mảng số nguyên
+ Đếm số sinh viên có điểm trung bình lớn hơn 6.5 nhỏ hơn 8.0
+ Đếm số điện thoại có đầu số 0168 hoặc 0169
+ Đếm số điện thoại có số đuôi là 165
+ Đếm số ngư i cùng họ “Nguyễn” và có điểm trung bình lớn hơn 6.0
+ Đếm số sách lớp 10 và có mệnh giá lớn hơn 25 ngàn
+ Đếm số sách thể loại “truyện tranh” trong thư viện
Chú ý:Trên đây là một số ví dụ về đếm có điều kiện,điều kiện c a đề bài có thể là được kết hợp từ
nhiều thông tin c a phần tử trong danh sách.Với mỗi phần tử trong danh sách ta kiểm tra thông tin
c a phần tử với điều kiện c a đề bài.Kết quả c a việc đếm chính là số lượng phần tử có thông tin
phù hợp với điều kiện từ đề bài.
Thuật toán:
- Gán p là phần tử đầu c a danh sách liên kết đơn
- Lặp trong khi p khác rỗng
+ Nếu thông tin c a phần tử p phù hợp với điều kiện c a đề bài thì tăng biến đếm thêm 1.
+ Chuyển p sang phần tử ngay sau nó
- Trả về kết quả là biến đếm.
Giải thích thuật toán:Với mỗi phần tử phù hợp với điều kiện c a đề bài thì tăng biến đếm thêm 1,sau
khi duyệt qua hết tất cả các phần tử c a danh sách thì trả về kết quả là biến đếm.
Cài đặt:
Pascal:
function dem(dk:KieuDK):integer;{đếm với điều kiện dk}
var d:integer;
var p:PTLK;{p thuộc kiểu phần tử liên kết}
begin
d:=0;{kh i tạo biến đếm bằng 0}
p:=dau;{gán p là phần tử đầu c a danh sách liên kết đơn}
while(p<>nil) do
begin
if(kiểm tra thông tin p đúng với điều kiện từ đề bài dk) then
begin
d:=d+1;{tăng biến d(đếm) thêm 1}
end;
p:=p.lienket();{Chuyển p sang phần tử ngay sau nó}
end;
dem:=d;{trả về kết quả là giá trị trong biến d}
end;
Java:
int dem(dk)
{
int d=0;//kh i tạo biến đếm bằng 0
PTLK p=dau;//gán p là phần tử đầu c a danh sách liên kết đơn
while(p!=null)
{
if(kiểm tra thông tin p đúng với điều kiện từ đề bài dk)
{
d=d+1;//tăng biến d(đếm) thêm 1
}
p=p.layLienKet();//chuyển p sang phần tử ngay sau nó
}
return d;//trả về kết quả là giá trị c a biến d
}
Thao tác thêm(chèn):
+ Thêm t c là đưa thêm một phần tử mới vào danh sách,số phần tử c a danh sách tăng thêm 1, Khi
thêm một phần tử vào danh sách phải đảm bảo danh sách sau khi thêm ch a phần tử mới và tất cả
các phần tử c a danh sách cũ(danh sách trước khi thêm).Đối với danh sách liên kết đơn ta có 2 vị trí
cần thêm là thêm vào đầu và thêm vào sau một phần tử nào đó.
+ Thêm vào đầu danh sách liên kết đơn:Gọi q là phần tử cần thêm vào danh sách,dau là ch a địa chỉ
c a phần tử đầu tiên trong danh sách liên kết đơn.Để thêm đầu tiên ta đặt liên kết c a q là dau,sau đó
gán lại q cho dau.
Giải thích:Với mỗi phần tử trong danh sách liên kết đơn ta đều biết phần từ sau nó,do đó khi thêm q
vào đầu danh sách thì q phải liên kết với danh sách cũ (t c là đặt liên kết c a q là phần tử đầu c a
danh sách cũ),kết quả q tr thành phần tử đầu tiên trong danh sách mới nên ta phải đặt lại dau là
phần tử q.
Cài đặt:
Pascal:
procedure them(pt:KieuPT);{pt là phần tử cần thêm,yêu cầu thêm vào đầu danh sách}
var q:PTLK;
begin
new(q,pt);{đưa phần tử cần thêm vào dữ liệu c a phần tử liên kết}
q.lienket:=dau;{q liên kết đến đầu danh sách cũ}
dau:=q;{danh sách mới có phần tử đầu là q}
end;
Java:
void them(KieuPT pt)
{
PTLK q;
q=new PTLK(pt);// đưa phần tử cần thêm vào dữ liệu c a phần tử liên kết
q.ganLienKet(dau);//q liên kết đến phần tử đầu c a danh sách cũ
dau=q;//danh sách mới có phần tử đầu là q
}
+ Thêm vào vị trí sau phần tử p:Gọi q là phần tử cần thêm,để thêm q vào sau p ta đặt liên kết c a q
là liên kết c a p,sau đó đặt liên kết c a p là phần tử q.
Thuật toán thêm một phần tử vào vị trí sau p:
- Gán liên kết c a q là liên kết c a p
- Gán liên kết c a p là phần tử q
Giải thích:Khi thêm q vào sau p thì q phải giữ liên kết với phần danh sách sau p và p liên kết đến q.
Minh họa bằng hình ảnh:
p
NULL
q
Cài đặt:
Pascal:
procedure them(pt:KieuPT;p:PTLK);{pt là phần tử cần thêm,thêm vào sau p}
var p1,q:PTLK;
begin
new(q,pt);{đưa phần tử cần thêm vào dữ liệu c a phần tử liên kết}
q.lienket:=p.lienket;{đặt liên kết c a q là phần tử sau p}
p.lienket:=q;{đặt liên kết c a p là q}
end;
Java:
void them(KieuPT pt,PTLK p)
{
PTLK p1,q;
q=new PTLK(pt);{đưa dữ liệu pt vào q}
q.ganLienKet(p.layLienKet());//q liên kết đến phần tử sau p
p.ganLienKet(q);//p liên kết đến q
}
Chú ý:Thao tác thêm được mô tả trên đây chỉ còn một điều kiện đơn giản khi thêm là vị trí cần thêm
trong danh sách.Nhưng trong nhiều bài toán thao tác thêm có thể có các điều kiện khác như thêm
một phần tử sau phần tử có tên x,hoặc thêm một sinh viên vào sau sinh viên có mã sinh viên y.
Thêm có điều kiện ta cũng làm tương tự như thêm vào vị trí k trong mảng,nhưng lúc này ta chưa
biết vị trí cần thêm do đó ta cần phải tìm ra vị trí cần thêm đúng theo yêu cầu đề bài,với vị trí tìm
được ta dùng thuật toán thêm phần tử vào sau vị trí k để giải quyết.Nếu không tìm được vị trí cần
thêm thì không thêm phần tử vào danh sách.
Ví dụ:
+ Thêm một sinh viên vào sau sinh viên tên x trong danh sách sinh viên
+ Thêm một số điện thoại vào sau số điện thoại y
+ Thêm một môn học vào danh sách môn học c a ngư i tên z
+ Nhập điểm môn cấu trúc dữ liệu cho sinh viên có mã số x
Trên đây là một số ví dụ cơ bản cho việc thêm có điều kiện,việc kết hợp nhiều thông tin c a phần tử
để tìm được vị trí cần thêm thì việc thêm tr thành thêm có điều kiện.
Thuật toán:
- Tạo phần tử liên kết q ch a phần tử(dữ liệu) cần thêm vào danh sách
- Đặt p là phần tử đầu c a danh sách liên kết đơn
- Lặp trong khi p khác rỗng
+ Nếu phần tử p thỏa điều kiện đề bài,vị trí c a phần tử liên kết này gọi là vị trí k
*Thêm q vào sau vị trí p,dừng lặp
Thuật toán chi tiết hơn:
- Tạo phần tử liên kết q ch a phần tử(dữ liệu) cần thêm vào danh sách
- Đặt p là phần tử đầu c a danh sách liên kết đơn
- Lặp trong khi p khác rỗng
+ Nếu phần tử p thỏa điều kiện đề bài,vị trí c a phần tử liên kết này gọi là vị trí k
*Đặt liên kết c a phần tử q là liên kết c a p
*Đặt liên kết c a p là q,dừng lặp
Cài đặt:
Pascal:
procedure them(pt:KieuPT;dk:KieuDK);{pt phần tử cần thêm,dk điều kiện thêm}
var p,q:PTLK;
begin
new(q,pt);{ đưa phần tử cần thêm vào dữ liệu c a phần tử liên kết }
p:=dau;
while(p<>nil) do
begin
if(thông tin c a phần tử p đúng với điều kiện đề bài dk) then
begin
{p chính là phần tử k cần tìm}
q.lienket:=p.lienket;{cho q liên kết đến phần tử sau p}
p.lienket:=q;{cho p liên kết đến q}
break;
end;
p:=p.lienket;
end;
end;
Java:
void them(KieuPT pt,KieuDK dk)
{
PTLK p,q;
q=new PTLK(pt);{đưa dữ liệu pt vào q}
while(p!=null)
{
if(thông tin c a phần tử p đúng với yêu cầu đề bài dk)
{
//p là vị trí k cần tìm
q.ganLienKet(p.layLienKet());//q liên kết đến phần tử sau p
p.ganLienKet(q);//p liên kết đến q
break;
}
p=p.layLienKet();
}
}
Thao tác xóa:
Xóa phần tử trong danh sách là công việc loại bỏ phần tử ra khỏi danh sách,làm giảm bớt số phần tử
không cần thiết trong danh sách.Nếu trên giấy ta loại bỏ bằng cách gạch tên những ngư i trong danh
sách.
Xóa một phần tử có 2 trư ng hợp:
TH1:Xóa phần từ đầu trong danh sách:chuyển phần tử đầu c a danh sách sang phần tử sau phần tử
đầu.
Giải thích:trong danh sách liên kết đơn khi có phần tử đầu ta có thể đi thăm các phần tử c a danh
sách,mỗi phần tử đều giữ địa chỉ có phần tử sau nó,nên khi ta chuyển phần tử đầu c a danh sách
sang phần tử sau phần tử đầu thì danh sách sẽ bắt đầu bằng phần tử sau phần tử đầu,do đó ta sẽ
không thể biết được phần tử đầu c a danh sách cũ.
Thuật toán:
- Gán phần tử đầu là phần tử ngay sau nó
TH2:Xóa phần tử khác phần tử đầu:
Thuật toán xóa phần tử vị trí k:Để xóa phần tử vị trí k ta phải biết phần tử trước k và phần tử sau
vị trí k,sau đó ta cho phần tử trước k liên kết đến phần tử sau k,như vậy là ta đã xóa được k.
Giải thích:Mỗi phần tử đều ch a một giá trị là vị trí c a phần tử đằng sau nó,do đó chỉ phần trước k
mới biết địa chỉ c a phần tử k,cho nên khi ta chuyển liên kết c a phần tử trước k sang phần tử sau
k,thì phần tử trước k không còn biết địa chỉ c a phần tử k,như vậy coi như k đã bị xóa ra khỏi danh
sách.
Thuật toán:
- p là phần tử trước k
- cho p liên kết đến phần tử sau k
Xóa có điều kiện:Tìm trong danh sách nếu thông tin c a phần tử nào trong danh sách phù hợp với
điều kiện xóa thì tiến hành xóa phần tử này.T c là duyệt qua từng phần tử c a danh sách liên kết
đơn,nếu phần tử đang xét có ch a thông tin phù hợp với điều kiện c a đề bài ta tiến hành xóa phần
tử này.
- Có hai loại thao tác xóa:
+ Chỉ xóa một phần tử
+ Xóa nhiều phần tử hoặc tất cả phần tử có cùng điều kiện
Chỉ xóa một phần tử:Tiến hành tìm phần tử cần xóa theo điều kiện c a bài toán,sau đó dùng
thuật toán xóa một phần tử.
Thuật toán:
- Nếu danh sách liên kết không rỗng thì
+ Nếu thông tin c a phần tử dau thỏa mãn yêu cầu bài toán thì tiến hành xóa phần tử đầu
(TH1 c a xóa một phần tử)
+ Ngược lại:
*Gán p là phần tử đầu c a danh sách liên kết đơn
*Lặp trong khi p khác rỗng
-- Nếu thông tin c a phần tử p thỏa mãn yêu cầu bài toán thì (p chính là phần tử cần
xóa)
-+ Xóa phần tử p(TH2 c a xóa một phần tử)
-+ Dừng lặp
-- Chuyển p sang phần tử ngay sau nó
Thuật toán chi tiết:
- Nếu danh sách liên kết không rỗng thì
+ Nếu thông tin c a phần tử dau thỏa mãn yêu cầu bài toán thì
*Gán phần tử đầu là phần tử sau phần tử đầu
+ Ngược lại:
*Gán p là phần tử đầu c a danh sách liên kết đơn
*Gán q là p
*Lặp trong khi p khác rỗng
-- Nếu thông tin c a phần tử p thỏa mãn yêu cầu bài toán thì (p chính là phần tử cần
xóa)
-+cho q liên kết đến phần tử sau p
-+ Dừng lặp
-- Gán q là p
-- Chuyển p sang phần tử ngay sau nó
Cài đặt:
Pascal:
procedure xoa(dk:KieuDK);
var p,q:PTLK;
begin
if(dau<>nil)
begin
if(thông tin c a phần tử đầu thỏa mãn điều kiện xóa dk) then
begin
dau:=dau.lienket;{chuyển đầu ra phần tử ngay sau nó}
end
else
begin
p:=dau;
q:=p;
while(p<>nil) do
begin
if(thông tin c a phần tử p thỏa mãn điều kiện xóa dk) then
begin
q.lienket:=p.lienket;
break;{dừng lặp khi đã tìm được 1 phần tử cần xóa}
end;
q:=p;
p:=p.lienket;{chuyển p sang phần tử ngay sau nó}
end;
end;
end;
end;
Java:
void xoa(KieuDK dk)
{
PTLK p,q;
if(dau!=null)
{
if(thông tin c a phần tử dau thỏa mãn điều kiện dk)
{
dau.ganLienKet(dau.layLienKet());
}
else
{
p=dau;
q=p;
while(p!=null)
{
if( thông tin c a phần tử p thỏa mãn điều kiện dk)
{
q.ganLienKet(p.layLienKet());
return;
}
q=p;
p=p.layLienKet();
}
}
}
}
Xóa nhiều phần tử trong danh sách liên kết đơn:Ta sẽ lặp quá trình xóa một phần tử thì ta
được cách xóa nhiều phần tử.
Xóa nhiều phần tử cũng gặp 2 trư ng hợp:Phần tử cần xóa là phần tử đầu trong danh sách và phần
tử cần xóa là phần tử khác phần tử đầu.
TH1: Lặp trong khi phần tử đầu khác rỗng và phần tử đầu thỏa mãn điều kiện xóa,tiến hành xóa
phần tử đầu.
Thuật toán:
- Lặp trong khi phần tử đầu khác rỗng và thông tin c a phần tử đầu thỏa mãn điều kiện xóa
+ Xóa phần tử đầu
Thuật toán chi tiêt hơn:
- Lặp trong khi phần tử đầu danh sách khác rỗng và thông tin c a phần tử đầu danh sách thỏa
mãn điều kiện xóa
+Chuyển phần từ đầu sang phần tử ngay sau nó
TH2:Tiến hành tìm phần tử cần xóa ,sau đó xóa phần tử này,lặp lại việc tìm và xóa cho đến khi
duyệt hết danh sách.
Thuật toán:
- Gán p là phần tử đầu c a danh sách liên kết đơn
- Lặp trong khi p khác rỗng
+ Nếu thông tin c a phần tử p thỏa mãn điều kiện xóa thì
*Xóa phần tử p
+ Chuyển p sang phần tử ngay sau nó
Thuật toán chi tiết hơn:
-
Gán p là phần tử đầu c a danh sách liên kết đơn
Gán q là p
Lặp trong khi p khác rỗng
+ Nếu thông tin c a phần tử p thỏa mãn điều kiện xóa thì
*Chuyển liên kết c a q sang phần tử sau phần tử p
*Gán p là q{việc duyệt bắt đầu lại từ phần tử q}
+ Gán q là p
+ Chuyển p sang phần tử ngay sau nó
Khi kết hợp hai trư ng hợp xóa trên ta được cách xóa tất cả các phần tử thỏa mãn điều kiện xóa c a
bài toán.
Cài đặt xóa tất cả các phần tử thỏa mãn điều kiện xóa:
Pascal:
procedure xoa(dk:KieuDK);
var p,q:PTLK;
begin
while(dau<>nil) do
begin
if(thông tin c a phần tử đầu thỏa mãn điều kiện xóa dk) then
dau:=dau.lienket{chuyển đầu ra phần tử ngay sau nó}
else
break;
end;
p:=dau;
q:=p;
while(p<>nil) do
begin
if(thông tin c a phần tử p thỏa mãn điều kiện xóa dk) then
begin
q.lienket:=p.lienket;
p:=q;
end;
q:=p;
p:=p.lienket;{chuyển p sang phần tử ngay sau nó}
end;
end;
Java:
void xoa(KieuDK dk)
{
PTLK p,q;
while(dau!=null)
{
if(thông tin c a phần tử dau thỏa mãn điều kiện dk)
dau.ganLienKet(dau.layLienKet());
else
break;
}
p=dau;
q=p;
while(p!=null)
{
if( thông tin c a phần tử p thỏa mãn điều kiện dk)
{
q.ganLienKet(p.layLienKet());
p=q;
}
q=p;
p=p.layLienKet();
}
}
Ví dụ xóa có điều kiện:
+ Xóa tất cả sinh viên có tên x trong danh sách sinh viên
+ Xóa tất cả số điện thoại c a ngư i tên y trong danh bạ
+ Xóa điểm môn cấu trúc dữ liệu c a sinh viên tên z
+ Xóa tên những nhân viên trên 50 tuổi trong danh sách nhân viên
Các ví dụ trên đều tổ ch c dữ liệu bằng danh sách liên kết đơn
II.Cây:
1.Cây nhị phân:
Tổ ch c dữ liệu
Mỗi nút trên cây nhị phân gồm có ba thành phần:
+ Phần duLieu là dữ liệu c a từng nút trên cây
+ Phần trai là địa chỉ c a nút con bên trái mà nút này liên kết đến
+ Phần phai là địa chỉ c a nút con bên phải mà nút này liên kết đến
Một cây nhị phân gồm một thành phần:
+ Một ô nhớ lưu nút gốc c a cây.
Khai báo:
Pascal:
TYPE Nut=^PTLK;
PTLK=RECORD
dulieu:KieuDL;{KieuDL là kiểu dữ liệu c a phần tử tại mỗi nút}
trai,phai:Nut;
END;
TYPE Cay=RECORD
goc:Nut;
END;
Java:
class Nut
{
private KieuDL dulieu;
private Nut trai,phai;
…
}
class Cay
{
private Nut goc;
…
}
Chú ý:
+ Nut tên đặt cho kiểu phần tử nút
+ KieuDL tên c a kiểu dữ liệu cho mỗi phần tử trên cây nhị phân.
+trai,phai là tên đặt cho thuộc tính liên kết trái và phải.
+ goc là ô nhớ lưu phần tử gốc c a cây.
Cây nhị phân là cây mà mỗi nút có tối đa hai nút con.
A.Duyệt:Duyệt trong cây nhị phân cũng là đi thăm qua tất cả các phần tử c a cây,mỗi phần tử gọi là
nút,chỉ có di chuyển từ phần tử này sang phần tử này khác là khác nhau,do mỗi phần tử có tối đa 2
hướng để đi nên quá trình di chuyển sẽ ph c tạp hơn.Hoạt động duyệt trên cây nhị phân cũng giống
như hoạt động duyệt trên danh sách.
Tư tư ng thuật toán duyệt:vì mỗi nút có 2 hướng để đi nên có thể đi sang trái hoặc đi sang phải.Nên
sau khi thăm nút hiện tại thì ta đi thăm nút bên trái và đi thăm nút bên phải.Hai nút bên trái,bên phải
gọi là hai nút con c a nút hiện tại.
Thuật toán duyệt cơ bản:Duyệt cây nhị phân xuất phát từ nút p
- Nếu nút p khác rỗng thì
+Thao tác với nút p(thao tác gồm:hiện thị,so sánh,kiểm tra thông tin nút này)
+Duyệt cây nhị phân xuất phát từ nút con trái c a nút p
+Duyệt cây nhị phân xuất phát từ nút con phải c a nút p
Giải thích:Cách duyệt trên đây là duyệt đệ quy,quá trình duyệt được thực hiện nh l i gọi đệ
quy.Cho nên khá ph c tạp để hiểu được,cơ bản có thể hiểu như sau:đầu tiên ta thăm nút hiện tại
trước,sau đó từ nút hiện tại ta di chuyển sang nút con bên trái,rồi từ nút hiện tại ta di chuyển sang
nút con bên phải,như vậy mỗi nút ta đều đi sang được 2 nút con c a nó do đó ta có thể đi thăm
toàn bộ nút c a cây.Cách này giống như việc khi di chuyển sang trái ta phải ghi nhớ nút hiện tại,để
sau khi đi sang trái thì ta tr lại và đi sang phải.
Quá trình duyệt đệ quy thì tại mỗi nút đều thực hiện th tục duyệt,ví dụ có 10 nút trên cây thì th tục
duyệt được gọi 10 lần tại mỗi nút trên cây.
Cài đặt:
Pascal:
procedure duyet(p:Nut);{duyệt cây xuất phát từ nút p}
begin
if(p<>nil) then
begin
+ Thao tác với nút p;{hiển thị,tìm kiếm,kiểm tra,so sánh}
duyet(p.trai);
duyet(p.phai);
end;
end;
Java:
void duyet(Nut p)
{
if(p!=null)
{
+ Thao tác với nút p;//hiện thị,tìm kiếm,kiểm tra,so sánh
duyet(p.layTrai());
duyet(p.layPhai());
}
}
Chú ý:hầu hết hoạt động duyệt đều là duyệt có điều kiện.
Duyệt cây có điều kiện: Duyệt qua tất cả các nút trong cây với mỗi nút ta sử dụng thông tin c a nút
để giải quyết một số vấn đề như là đếm,liệt kê,thêm,tìm kiếm,…
Giải thích:Với mỗi một nút c a cây ta sẽ kiểm tra thông tin của nút,việc kiểm tra thông tin c a nút
chính là điều kiện duyệt,kết quả duyệt có điều kiện hoàn toàn phụ thuộc vào điều kiện này.Sử dụng
thông tin c a nút để làm điều kiện cho các thao tác đếm,thêm,tìm kiếm,…
- Thông tin của nút như là tên,tuổi,…c a mỗi nút.
- kiểm tra Thông tin của nút :ví dụ kiểm tra tên ngư i nút có phải là “Nguyễn Văn A” ,kiểm
tra tuổi ngư i nút có lớn hơn 50,hoặc kiểm tra ngư i nút có con cháu hay không.
Thuật toán duyệt có điều kiện:Duyệt cây nhị phân xuất phát từ nút p với điều kiện dk
- Nếu nút p khác rỗng thì
+Nếu thông tin nút p thỏa mãn điều kiện đề bài dk thì hiện các thao tác như liệt kê,đếm,tìm
kiếm.
+Duyệt cây nhị phân xuất phát từ nút con trái c a nút p với điều kiện dk
+Duyệt cây nhị phân xuất phát từ nút con phải c a nút p với điều kiện dk
Giải thích:Duyệt cây nhị phân có điều kiện có cũng như duyệt không điều kiện,khi ta đến mỗi nút
trên cây thì kiểm tra thông tin nút đó với điều kiện từ đề bài,nếu thỏa mãn điều kiện đề bài thì ta
thực hiện các thao tác như đếm,liệt kê,tìm kiếm.
Cài đặt:
Pascal:
procedure duyet(p:Nut;dk:KieuDK);{duyệt cây xuất phát từ nút p}
begin
if(p<>nil) then
begin
if(thông tin c a nút p thỏa mãn điều kiện dk) then
begin
{thực hiện đếm,liệt kê,hoặc tìm kiếm,…}
end;
duyet(p.trai,dk);
duyet(p.phai,dk);
end;
end;
Java:
void duyet(Nut p,KieuDK dk)//duyệt xuất phát từ nút p với điều kiện dk
{
if(p!=null)
{
if(thông tin c a nút p thỏa mãn điều kiện dk)
{
//thực hiện đếm,liệt kê,hoặc tìm kiếm,…
}
duyet(p.layTrai(),dk);
duyet(p.layPhai(),dk);
}
}
Bổ sung độ cao cho mỗi nút trên cây nhị phân:
Thuật toán:dùng một biến h lưu độ cao c a nút p so với nút gốc.Như vậy thì nút con trái và nút con
phải c a nút p có độ cao lớn hơn nút p một đơn vị.
Thuật toán:Duyệt cây xuất phát từ nút p với độ cao h
- Nếu nút p khác rỗng (t c là nút p có độ cao h)
+Thao tác với nút p(thao tác:hiển thị,kiểm tra,tìm kiếm,có thể kết hợp thông tin độ cao h)
+ Duyệt cây xuất phát từ nút con trái c a nút p với độ cao h+1
+ Duyệt cây xuất phát từ nút con phải c a nút p với độ cao h+1
Cài đặt:cài đặt dưới đây là phần cài đặt tổng quát xuất phát từ nút p,khi gọi thủ tục này thì thay p là
nút gốc và h=0
Pascal:
procedure duyet(p:Nut;dk:KieuDK,h:integer);{duyệt cây xuất phát từ nút p với điều kiện dk,độ cao
h}
begin
if(p<>nil) then
begin
if(thông tin c a nút p thỏa mãn điều kiện dk, kết hợp thông tin độ cao h) then
begin
{thực hiện đếm,liệt kê,hoặc tìm kiếm,…}
end;
duyet(p.trai,dk,h+1);{Duyệt cây xuất phát từ nút em c a nút p với điều kiện dk}
duyet(p.phai,dk,h+1);{Duyệt cây xuất phát từ nút con c a nút p với điều kiện dk}
end;
end;
Java:
void duyet(Nut p,KieuDK dk,int h)//duyệt cây xuất phát từ nút p với điều kiện dk,với độ cao h
{
if(p!=null)
{
if(thông tin c a nút p thỏa mãn điều kiện dk,kết hợp với độ cao h)
{
//thực hiện đếm,liệt kê,hoặc tìm kiếm,…
}
duyet(p.layTrai(),dk,h+1);// Duyệt cây xuất phát từ nút con trái c a nút p với điều kiện
dk,với độ cao h.
duyet(p.layPhai(),dk,h+1);// Duyệt cây xuất phát từ nút con phải c a nút p với điều kiện
dk,với độ cao h+1
}
}
Các loại duyệt có điều kiện trên cây nhị phân:
- Duyệt để liệt kê
- Duyệt để tìm kiếm
- Duyệt để đếm
Duyệt để liệt kê:liệt kê đây là hiển thị ra những thông tin theo yêu cầu c a đề bài
Ví dụ:Một dòng họ đã thực hiện kế hoạch hóa gia đình rất tốt cho nên trong mỗi gia đình chỉ có tối
đa 2 ngư i con.Tổ ch c dữ liệu cho những ngư i có quan hệ họ hàng với nhau trong dòng họ này và
viết thuật toán cho các thao tác dưới đây.
+Liệt kê tên tất cả mọi ngư i trong dòng họ
+Liệt kê tên c a những ngư i con trai trong dòng họ
+Liệt kê những ngư i có độ tuổi từ 20 đến 35 tuổi
Các giải quyết:Vì mỗi gia đình trong dòng họ chỉ có 2 ngư i con,tuy gia đình có vợ và chồng nhưng
ta chỉ quan tâm đến tên những ngư i có dòng máu dòng họ.Như vậy ta sẽ tổ ch c dữ liệu cho bài
toán này là cây nhị phân mà mỗi nút là một ngư i trong dòng họ.Ông tổ c a dòng họ là nút gốc.
Chú ý:Ch yếu liệt kê là có điều kiện,ví dụ:liệt kê những ngư i có tên bắt đầu bằng chữ “H”.hoặc
liệt kê những ngư i trên 60 tuổi.Như vậy trong duyệt để liệt kê còn có thêm phần điều kiện,nhưng ta
dễ thấy những điều kiện c a đề bài sẽ dùng để kiểm tra thông tin c a nút trong cây,nếu thông tin c a
nút phù hợp với điều kiện yêu cầu từ đề bài thì ta sẽ hiển thị thông tin c a nút đúng với điều kiện đề
bài.
Duyệt cây để liệt kê có điều kiện: Duyệt qua tất cả các nút trong cây với mỗi nút ta kiểm tra thông
tin c a nút có thỏa mãn với điều kiện bài toán,nếu thỏa mãn ta hiển thị thông tin nút này.
Giải thích:Với mỗi một nút c a cây ta sẽ kiểm tra thông tin của nút,việc kiểm tra thông tin c a nút
chính là điều kiện duyệt,kết quả duyệt có điều kiện hoàn toàn phụ thuộc vào điều kiện này.Nếu
thông tin c a nút nào thỏa mãn yêu cầu từ đề bài thì ta hiển thị thông tin nút đó.
Thuật toán duyệt để liệt kê có điều kiện:Duyệt cây nhị phân xuất phát từ nút p với điều kiện dk
- Nếu nút p khác rỗng thì
+Nếu thông tin nút p thỏa mãn điều kiện đề bài dk thì liệt kê thông tin nút p
+Duyệt cây nhị phân xuất phát từ nút con trái c a nút p với điều kiện dk
+Duyệt cây nhị phân xuất phát từ nút con phải c a nút p với điều kiện dk
Giải thích:Duyệt cây nhị phân có điều kiện cũng như duyệt không có điều kiện,khi ta đến mỗi nút
trên cây thì kiểm tra thông tin nút đó với điều kiện từ đề bài,nếu thỏa mãn điều kiện đề bài thì ta
thực hiện các thao tác như đếm,liệt kê,tìm kiếm.
Cài đặt:
Pascal:
procedure duyet(p:Nut;dk:KieuDK);{duyệt cây xuất phát từ nút p}
begin
if(p<>nil) then
begin
if(thông tin c a nút p thỏa mãn điều kiện dk) then
begin
{hiển thị thông tin nút p}
end;
duyet(p.trai,dk);
duyet(p.phai,dk);
end;
end;
Java:
void duyet(Nut p,KieuDK dk)//duyệt xuất phát từ nút p với điều kiện dk
{
if(p!=null)
{
if(thông tin c a nút p thỏa mãn điều kiện dk)
{
//hiển thị thông tin nút p
}
duyet(p.layTrai(),dk);
duyet(p.layPhai(),dk);
}
}
Duyệt để tìm kiếm:Duyệt qua tất cả các nút c a cây,khi xem xét từng nút c a cây ta kiểm tra
thông tin c a nút đó,nếu thỏa mãn điều kiện từ đề bài ta sẽ trả về kết quả là: tìm được,không
tìm được,phần tử đang xét,hoặc rỗng.
Thuật toán:Tìm phần tử xuất phát từ nút p với điều kiện dk
- Nếu nút p rỗng thì trả về kết quả là không tìm thấy(kết quả không tìm thấy có thể là một số
thay thế cho không tìm thấy(ví dụ số 0)hoặc null(cho đối tượng)).
- Nếu thông tin nút p thỏa mãn điều kiện dk thì trả về kết quả tìm thấy(kết quả tìm thấy có thể
là một số thay thế hoặc chính nút p(đối tượng).
- Gán q là kết quả Tìm phần tử xuất phát từ nút con trái c a nút p với điều kiện dk
- Nếu q có giá trị không tìm được thì
+ Trả về kết quả Tìm phần tử xuất phát từ nút con phải c a nút p với điều kiện dk
- Ngược lại:Trả về giá trị c a q
Giải thích:Tìm kiếm trên cây nhị phân với điều kiện theo từng bài toán cũng giống như duyệt,khi ta
đến mỗi nút trên cây thì kiểm tra thông tin nút đó với điều kiện từ đề bài,nếu gặp nút có thông tin
thỏa mãn điều kiện dk thì trả về kết quả tìm thấy,nếu sau khi duyệt hết tất cả các nút trên cây mà
không tìm thấy thì trả về kết quả không tìm thấy.
Cài đặt:
Pascal:
procedure tim(p:Nut;dk:KieuDK);{tìm phần tử trên cây xuất phát từ nút p với điều kiện dk}
var q:KieuTV;{}
begin
if(p=nil) then
tim:=0{hoặc tim:=nil nếu không tìm thấy}
else
begin
if(thông tin c a nút p thỏa mãn điều kiện dk) then
begin
tim:=1;{hoặc tim:=p nếu kết quả cần trả về là nút}
end;
q:=tim(p.trai,dk);
if(q là giá trị không tìm được) then
tim:=tim(p.phai,dk)
else
tim:=q;
end;
end;
Java:
void tim(Nut p,KieuDK dk)//tìm phần tử trên cây xuất phát từ nút p với điều kiện dk
{
if(p==null) return 0;{return null; đây là kết quả không tìm thấy}
if(thông tin c a nút p thỏa mãn điều kiện dk) then
{
return 1;//return p;trả về kết quả tìm thấy
}
q=duyet(p.layTrai(),dk);
if(q là giá trị không tìm được)
duyet(p.layPhai(),dk);
else
return q;
}
Duyệt để đếm: Duyệt qua tất cả các nút trên cây,khi xem xét từng nút c a cây ta kiểm tra
thông tin c a nút đó,nếu phù hợp với điều kiện yêu cầu từ đề bài ta sẽ đếm số nút cùng điều
kiện c a đề bài.
Thuật toán:Đếm phần tử xuất phát từ nút p với điều kiện dk
- Nếu nút p rỗng thì trả về kết quả là 0
- Gán count là số phần tử đếm được từ cây con trái nút p cộng với số phần tử đếm được từ cây
con phải nút p.
- Nếu thông tin c a nút p thỏa mãn điều kiện dk thì
+ Trả về kết quả là count+1;
- Ngược lại Trả về kết quả là count
Giải thích:Đếm trên cây nhị phân với điều kiện theo từng bài toán cũng giống như duyệt,khi ta đến
mỗi nút trên cây thì kiểm tra thông tin nút đó với điều kiện từ đề bài,nếu gặp nút có thông tin thỏa
mãn điều kiện dk thì cộng thêm 1 vào tổng số phần từ đếm được từ cây con trái nút p và số phần tử
đếm được cây con phải nút p.
Cài đặt:
Pascal:
function dem(p:Nut;dk:KieuDK):integer;{đếm số phần tử trên cây xuất phát từ nút p với điều kiện
dk}
var count:integer;
begin
if(p=nil) then
dem:=0;
else
begin
count:=dem(p.trai,dk)+dem(p.phai,dk);
if(thông tin c a nút p thỏa mãn điều kiện dk) then
dem:=count+1
else
dem:=count;
end;
end;
Java:
int dem(Nut p,KieuDK dk)//đếm số phần tử trên cây xuất phát từ nút p với điều kiện dk
{
int count;
if(p==null) return 0;
count=dem(p.layTrai(),dk)+dem(p.layPhai(),dk);
if(thông tin c a nút p thỏa mãn điều kiện dk)
return count+1;
return count;
}
Chú ý:Trong trư ng hợp đếm tất cả các nút thì t c là đếm không có điều kiện
Tìm chiều cao cây cũng là duyệt để đếm chỉ có nguyên tắc khi đếm khác nhau.
Thuật toán tìm chiều cao c a cây:Tìm độ cao xuất phát từ nút p,Tìm độ cao c a cây con bên trái và
độ cao c a cây con bên phải,so sánh hai độ cao này và chọn độ cao nào lớn hơn và trả về độ cao đó
cộng thêm 1(cộng thêm 1 vì p là nút cha c a cây con trái và cây con phải,do đó độ cao c a p phải
cao hơn cây con trái và cây con phải 1 đơn vị).
Thuật toán:Tìm chiều cao cây xuất phát từ nút p
- Nếu nút p rỗng thì trả về 0
- Ngược lại:
+Gán h1 là Tìm chiều cao cây xuất phát từ nút con trái c a nút p
+Gán h2 là Tìm chiều cao cây xuất phát từ nút con phải c a nút p
+Nếu h1 lớn hơn h2 thì
*Kết quả Trả về h1+1
+Ngược lại Trả về kết quả là h2+1
Cài đặt:
Pascal:
function chieucao(p:Nut):integer;{tìm chiều cao cây xuất phát từ nút p}
var h1,h2:integer;
begin
if(p=nil) then
chieucao:=0;
else
begin
h1:=chieucao(p.trai);{tính chiều cao cây xuất phát từ nút con bên trái nút p}
h2:=chieucao(p.phai);{tính chiều cao cây xuất phát từ nút con bên phải nút p}
if(h1>h2) then
chieucao:=h1+1
else
chieucao:=h2+1;
end;
end;
Java:
int chieucao(Nut p)//tìm chiều cao cây xuất phát từ nút p
{
int h1,h2;
if(p==null) return 0;
h1=chieucao(p.layTrai());//tính chiều cao cây xuất phát từ nút con bên phải c a p
h2=chieucao(p.layPhai());//tính chiều cao cây xuất phát từ nút con bên trái c a p
if(h1>h2)//nếu cây bên trái cao hơn cây bên phải thì
return h1+1;//độ cao cây là độ cao cây bên trái +1
return h2+1; ;//ngược lại độ cao cây là độ cao cây bên phải +1
}
Các ví dụ cho đếm có điều kiện:
+ Đếm số con cháu c a ngư i tên x trên cây nhị phân gia phả
Đây là bài toán đếm có điều kiện,với điều kiện là tên ngư i x,để giải quyết bài này đơn giản là ta
dùng thuật toán tìm trên cây ngư i tên x,sau đó dùng thuật toán đếm số lượng con cháu c a ngư i x
vừa tìm được.
+ Đếm số ngư i trên 25 tuổi trong dòng họ trên cây nhị phân gia phả
Đây là bài toán đếm có điều kiện,với điều kiện là ngư i có tuổi trên 25 tuổi,để giải quyết bài này
đơn giản là ta dùng thuật toán đếm số ngư i với điều kiện là có tuổi lớn hơn 25
+ Đếm số lượng số lớn hơn 100 c a cây nhị phân số.
Đây là bài toán đếm có điều kiện ,với điều kiện là số lớn hơn 100,để giải quyết bài toán này ta dùng
thuật toán đếm những số lớn hơn 100.
Cây tìm kiếm nhị phân:
Các thao tác duyệt trên cây tìm kiếm nhị phân hoàn toàn giống các thao tác duyệt trên cây nhị phân
chỉ có thao tác tìm kiếm là có sự khác biệt,do dữ liệu trên cây tìm kiếm nhị phân được sắp xếp theo
một trật tự nhất định nhằm giảm th i gian tìm kiếm.Trong quá trình tìm kiếm ta chỉ đi sang nút con
trái nếu giá trị cần tìm nhỏ hơn nút cha,hoặc đi sang phải nếu giá trị cần tìm lớn hơn nút cha.Như
vậy ta chỉ có thể đi theo một hướng,hay nói cách khác ta chỉ có 1 đư ng đi duy nhất khi ta đến mỗi
nút.
Thuật toán không đệ quy:tìm kiếm giá trị x trong cây tìm kiếm nhị phân
- Gán p là nút gốc
- Lặp trong khi p khác rỗng
+ Nếu thông tin c a nút p có giá trị bằng x thì
*Trả về true(tìm được),dừng lặp
+ Ngược lại:
*Nếu thông tin c a nút có giá trị lớn hơn x thì
+Chuyển p sang nút con trái c a nó
*Ngược lại chuyển p sang nút con phải c a nó
- Nếu không tìm thấy thì trả về false
Giải thích thuật toán:Do dữ liệu được sắp xếp theo một trật tự nhất định nên khi tìm kiếm ta chỉ đi
theo 1 hướng hoặc sang trái,hoặc sang phải nên chỉ có một con đư ng để đi.Khi đi đến một nút bất
kì ta sẽ kiểm tra xem nên đi sang trái hay đi sang phải,do dữ liệu đã được sắp xếp sao cho nút con
bên trái luôn nhỏ hơn nút cha c a nó và nút con bên phải luôn lớn hơn nút cha c a nó.Cho nên ta sẽ
so sánh giá trị cần tìm với nút cha,nếu giá trị tại nút cha có giá trị bằng giá trị cần tìm thì kết quả là
true( ng với tìm được),nếu giá trị tại nút cha lớn hơn giá trị cần tìm có nghĩa giá trị cần tìm phải
nằm bên trái nút cha,nếu giá trị tại nút cha nhỏ hơn giá trị cần tìm có nghĩa là giá trị cần tìm phải
nằm bên phải nút cha.Sau khi đi hết đư ng đi mà không tìm được thì trả về false( ng với không tìm
được).
Cài đặt:
Pascal:
function timkiem(gt:KieuPT):boolean;{KieuPT là kiểu phần tử c a giá trị cần tìm kiếm}
var p:Nut;
begin
timkiem:=false;{gán tìm kiếm bằng false thì nếu không tìm thấy phần tử nào thì giá trị tìm
kiếm sẽ là false}
p:=goc;{goc là nút gốc c a cây}
while(p<>nil) do
begin
if(p.giatri=gt) then {nếu giá trị nút p bằng gt }
begin
timkiem:=true;{tìm thấy}
break;
end
else
if(p.giatri>gt) then{nếu giá trị tại nút p lớn hơn gt}
p:=p.trai{chuyển p sang nút con trái c a nó}
else
p:=p.phai;{chuyển p sang nút con phải c a nó}
end;
end;
Java:
boolean timkiem(KieuPT gt)//KieuPT là kiểu phần tử c a giá trị cần tìm kiếm
{
Nut p=goc;//gán nút p là nút gốc
while(p!=null)
{
if(p.layDuLieu()==gt)
return true;//tìm thấy
else if(p.layDuLieu()>gt)
p=p.layTrai();
else
p=p.layPhai();
}
return false;//không tìm thấy thì kết quả là false
}
Cây tổng quát
Tổ ch c dữ liệu
Mỗi nút trên cây tổng quát gồm có ba thành phần:
+ Phần duLieu là dữ liệu c a từng nút trên cây
+ Phần em là địa chỉ c a nút con bên trái mà nút này liên kết đến
+ Phần con là địa chỉ c a nút con bên phải mà nút này liên kết đến
Một cây tổng quát gồm một thành phần:
+ Một ô nhớ lưu nút gốc c a cây.
Khai báo:
Pascal:
TYPE Nut=^PTLK;
PTLK=RECORD
dulieu:KieuDL;{KieuDL là kiểu dữ liệu c a phần tử tại mỗi nút}
em,con:Nut;
END;
TYPE Cay=RECORD
goc:Nut;
END;
Java:
class Nut
{
private KieuDL dulieu;
private Nut em,con;
…
}
class Cay
{
private Nut goc;
…
}
Chú ý:
+ Nut tên đặt cho kiểu phần tử nút
+ KieuDL tên c a kiểu dữ liệu cho mỗi phần tử trên cây nhị phân.
+em,con là tên đặt cho thuộc tính liên kết em và con.
+ goc là ô nhớ lưu phần tử gốc c a cây.
Cây tổng quát là cây mà mỗi nút có thể nhiều hơn 2 nút con.
Để có tính chất giống cây nhị phân thì ta tổ ch c dữ liệu như sau:
Mỗi nút trong cây tổng quát gồm 3 thành phần:
+ Phần dữ liệu c a mỗi nút trên cây
+ Phần liên kết đến nút con c a nó
+ Phần liên kết đến nút em c a nó
Với cách tổ ch c này thì mỗi nút chỉ quản lý 2 nút là nút con và nút em c a nó,vì mỗi nút đều có
liên kết đến nút em c a nó nên ta có thể đi đến các nút em tiếp theo giống như danh sách liên kết
đơn,mà mỗi nút lại liên kết đến nút con c a chính nó nên ta lại có thể đi đến các nút con c a nó.do
đó cách quản lý này tương tự như cây nhị phân.
Duyệt trên cây tổng quát cũng giống như duyệt trên cây nhị phân:
Duyệt theo th tự trước:đầu tiên là thăm nút hiện tại,rồi từ nút hiện tại ta đi thăm nút em c a nó,sau
đó từ nút hiện tại đi thăm nút con c a nó.
Thuật toán:Duyệt cây xuất phát từ nút p
- Thao tác(thăm) với nút p(thao tác:so sánh,kiểm tra,liệt kê trên thông tin c a nút p)
- Duyệt cây xuất phát từ nút em c a nút p
- Duyệt cây xuất phát từ nút con c a nút p
Cài đặt thuật toán duyệt:
Pascal:
procedure duyet(p:Nut);{duyệt cây xuất phát từ nút p}
begin
if(p<>nil) then
begin
+ Thao tác với nút p;{hiển thị,tìm kiếm,kiểm tra,so sánh}
duyet(p.em);{ Duyệt cây xuất phát từ nút em c a nút p}
duyet(p.con);{ Duyệt cây xuất phát từ nút con c a nút p}
end;
end;
Java:
void duyet(Nut p)
{
if(p!=null)
{
+ Thao tác với nút p;//hiện thị,tìm kiếm,kiểm tra,so sánh
duyet(p.layEm());//Duyệt cây xuất phát từ nút em c a nút p
duyet(p.layCon());//Duyệt cây xuất phát từ nút con c a nút p
}
}
Thuật toán cũng giống như thuật toán duyệt cây nhị phân chỉ có khác tên phần liên kết, cây nhị
phân là nút trái thì cây tổng quát là nút con, cây nhị phân là nút phải thì cây tổng quát là nút
con.Quá trình duyệt trên cây tổng quát giống như di chuyển qua các con đư ng trong giao
thông,mỗi điểm giao nhau giữa các con đư ng thì gọi là nút,khi ta gặp một nút giao thông thì ta sẽ
có nhiều lựa chọn đư ng đi.Những điểm giao nhau giữa con đư ng lớn và đư ng nhỏ giống như các
nút anh em,con đư ng nhỏ sẽ đi đến nút con c a nó.
Ví dụ c a cây tổng quát:
Cây giả phả trong dòng họ vì sự phân th bậc trong một gia đình là cha thì cao hơn con,anh thì sinh
ra trước em.
Cây thư mục trên máy tính vì trong mỗi thư mục ch a các thư mục con,và trong mỗi thư mục con lại
có các thư mục con.Do đó thư mục có tính phân cấp.
Chú ý:hầu hết hoạt động duyệt đều là duyệt có điều kiện.
Duyệt cây có điều kiện: Duyệt qua tất cả các nút trong cây với mỗi nút ta sử dụng thông tin c a nút
để giải quyết một số vấn đề như là đếm,liệt kê,thêm,tìm kiếm,…
Giải thích:Với mỗi một nút c a cây ta sẽ kiểm tra thông tin của nút,việc kiểm tra thông tin c a nút
chính là điều kiện duyệt,kết quả duyệt có điều kiện hoàn toàn phụ thuộc vào điều kiện này.Sử dụng
thông tin c a nút để làm điều kiện cho các thao tác đếm,thêm,tìm kiếm,…
- Thông tin của nút như là tên,tuổi,…c a mỗi nút.
- kiểm tra Thông tin của nút :ví dụ kiểm tra tên ngư i nút có phải là “Nguyễn Văn A” ,kiểm
tra tuổi ngư i nút có lớn hơn 50,hoặc kiểm tra ngư i nút có con cháu hay không.
Thuật toán duyệt có điều kiện:Duyệt cây xuất phát từ nút p với điều kiện dk
- Nếu nút p khác rỗng thì
+Nếu thông tin nút p thỏa mãn điều kiện đề bài dk thì hiện các thao tác như liệt kê,đếm,tìm
kiếm.
+Duyệt cây xuất phát từ nút em c a nút p với điều kiện dk
+Duyệt cây xuất phát từ nút con c a nút p với điều kiện dk
Giải thích:Duyệt cây tổng quát có điều kiện cũng như duyệt không có điều kiện,khi ta đến mỗi nút
trên cây thì kiểm tra thông tin nút đó với điều kiện từ đề bài,nếu thỏa mãn điều kiện đề bài thì ta
thực hiện các thao tác như đếm,liệt kê,tìm kiếm.
Cài đặt:
Pascal:
procedure duyet(p:Nut;dk:KieuDK);{duyệt cây xuất phát từ nút p}
begin
if(p<>nil) then
begin
if(thông tin c a nút p thỏa mãn điều kiện dk) then
begin
{thực hiện đếm,liệt kê,hoặc tìm kiếm,…}
end;
duyet(p.em,dk);{Duyệt cây xuất phát từ nút em c a nút p với điều kiện dk}
duyet(p.con,dk);{Duyệt cây xuất phát từ nút con c a nút p với điều kiện dk}
end;
end;
Java:
void duyet(Nut p,KieuDK dk)//duyệt cây xuất phát từ nút p với điều kiện dk
{
if(p!=null)
{
if(thông tin c a nút p thỏa mãn điều kiện dk)
{
//thực hiện đếm,liệt kê,hoặc tìm kiếm,…
}
duyet(p.layEm(),dk);// Duyệt cây xuất phát từ nút em c a nút p với điều kiện dk
duyet(p.layCon(),dk);// Duyệt cây xuất phát từ nút em c a nút p với điều kiện dk
}
}
Bổ sung thế hệ cho mỗi nút trên cây tổng quát:
Thuật toán:dùng một biến h lưu độ cao c a nút p so với nút gốc(độ cao này chính là thế hệ c a nút
p).Như vậy thì nút em c a nút p có cùng độ cao với nút p và nút con c a nút p có độ cao lớn hơn nút
p một đơn vị(vì nút con là thế hệ sau c a nút p).
Thuật toán:Duyệt cây xuất phát từ nút p với độ cao h
- Nếu nút p khác rỗng (t c là nút p có độ cao h)
+Thao tác với nút p(thao tác:hiển thị,kiểm tra,tìm kiếm,có thể kết hợp thông tin độ cao h)
+ Duyệt cây xuất phát từ nút em c a nút p với độ cao h
+ Duyệt cây xuất phát từ nút con c a nút p với độ cao h+1
Cài đặt:cài đặt dưới đây là phần cài đặt tổng quát xuất phát từ nút p,khi gọi thủ tục này thì thay p là
nút gốc và h=0
Pascal:
procedure duyet(p:Nut;dk:KieuDK,h:integer);{duyệt cây xuất phát từ nút p với điều kiện dk,độ cao
h}
begin
if(p<>nil) then
begin
if(thông tin c a nút p thỏa mãn điều kiện dk, kết hợp thông tin độ cao h) then
begin
{thực hiện đếm,liệt kê,hoặc tìm kiếm,…}
end;
duyet(p.em,dk,h);{Duyệt cây xuất phát từ nút em c a nút p với điều kiện dk}
duyet(p.con,dk,h+1);{Duyệt cây xuất phát từ nút con c a nút p với điều kiện dk}
end;
end;
Java:
void duyet(Nut p,KieuDK dk,int h)//duyệt cây xuất phát từ nút p với điều kiện dk,với độ cao h
{
if(p!=null)
{
if(thông tin c a nút p thỏa mãn điều kiện dk,kết hợp với độ cao h)
{
//thực hiện đếm,liệt kê,hoặc tìm kiếm,…
}
duyet(p.layEm(),dk,h);// Duyệt cây xuất phát từ nút em c a nút p với điều kiện dk,với độ
cao h.
duyet(p.layCon(),dk,h+1);// Duyệt cây xuất phát từ nút em c a nút p với điều kiện dk,với
độ cao h+1
}
}
Duyệt cây tổng quát theo th tự các phần tử có cùng độ cao hay cùng cấp
Giải thích:trong một số trư ng hợp như cây gia phả c a dòng họ thì ngư i ta muốn xem thông tin
những ngư i cùng thế hệ.
Phương pháp duyệt:Dùng một hàng đợi để xếp những ngư i thế hệ trước vào trước,những ngư i thế
hệ sau được đưa vào sau.Đầu tiên ta đưa nút gốc vào hàng đợi,sau đó c mỗi lần lấy một nút từ hàng
đợi ta đưa tất cả các nút con c a nó vào hàng đợi.
Thuật toán duyệt:
- Tạo một hàng đợi rỗng
- Đưa nút gốc vào hàng đợi
- Lặp trong khi hàng đợi chưa rỗng
+Gán p là nút lấy ra từ hàng đợi
+Thao tác trên thông tin nút p(thao tác:kiểm tra,đếm,tìm kiếm,…)
+Chuyển p sang nút con c a nó
+Lặp trong khi nút p khác rỗng
*Đưa nút p vào hàng đợi
*Chuyển p sang nút em c a nó
Cài đặt:
Pascal:
procedure duyet(dk:KieuDK);
var p:Nut;
var q:QueueOfNut;
begin
Init(q);
AddQueue(q,goc);{đưa nút gốc vào hàng đợi q}
while(not empty(q)) do
begin
RemoveQueue(q,p);
if(thông tin c a nút p thỏa mãn điều kiện dk) then
begin
{thao tác với nút p}
end;
p:=p.con;
while(p<>nil) do
begin
AddQueue(q,p);{đưa p vào hàng đợi q}
p:=p.em;{chuyển p sang nút em c a nó}
end;
end;
end;
Java:
void duyet(KieuDK dk)
{
Queue q=new LinkedList();
Nut p;
q.add(goc);
while(!q.isEmty)
{
p=(Nut)q.remove();
if(thông tin c a nút p thỏa mãn điều kiện dk)
{
//thao tác với thông tin nút p,đếm,tìm kiếm,liệt kê
}
p=p.layCon();//lấy nút con c a nút p
while(p!=null)
{
q.add(p);//đưa nút p vào hàng đợi
p=p.layEm();//lấy nút em c a nút p
}
}
}
Các loại duyệt có điều kiện trên cây tổng quát:
- Duyệt để liệt kê
- Duyệt để tìm kiếm
- Duyệt để đếm
Duyệt để liệt kê:liệt kê đây là hiển thị ra những thông tin theo yêu cầu c a đề bài
Ví dụ:Cho một cây gia phả c a một dòng họ A.Tổ ch c dữ liệu cho những ngư i có quan hệ họ
hàng với nhau trong dòng họ này và viết thuật toán cho các thao tác dưới đây.
+Liệt kê tên tất cả mọi ngư i trong dòng họ
+Liệt kê tên c a những ngư i con trai trong dòng họ
+Liệt kê những ngư i có độ tuổi từ 20 đến 35 tuổi
+Liệt kê những ngư i con c a ngư i tên x trong dòng họ
+Liệt kê những ngư i thế hệ th 3 trong dòng họ(ông tổ là thế hệ th 0)=>Xem phần bổ sung thế hệ
cho mỗi nút trên cây để giải quyết vấn đề này
Chú ý:Ch yếu liệt kê là có điều kiện,ví dụ:liệt kê những ngư i có tên bắt đầu bằng chữ “H”.hoặc
liệt kê những ngư i trên 60 tuổi.Như vậy trong duyệt để liệt kê còn có thêm phần điều kiện,nhưng ta
dễ thấy những điều kiện c a đề bài sẽ dùng để kiểm tra thông tin c a nút trong cây,nếu thông tin c a
nút phù hợp với điều kiện yêu cầu từ đề bài thì ta sẽ hiển thị thông tin c a nút đúng với điều kiện đề
bài.
Duyệt cây để liệt kê có điều kiện: Duyệt qua tất cả các nút trong cây với mỗi nút ta kiểm tra thông
tin c a nút có thỏa mãn với điều kiện bài toán,nếu thỏa mãn ta hiển thị thông tin nút này.
Giải thích:Với mỗi một nút c a cây ta sẽ kiểm tra thông tin của nút,việc kiểm tra thông tin c a nút
chính là điều kiện duyệt,kết quả duyệt có điều kiện hoàn toàn phụ thuộc vào điều kiện này.Nếu
thông tin c a nút nào thỏa mãn yêu cầu từ đề bài thì ta hiển thị thông tin nút đó.
Thuật toán duyệt để liệt kê có điều kiện:Duyệt cây tổng quát xuất phát từ nút p với điều kiện dk
- Nếu nút p khác rỗng thì
+Nếu thông tin nút p thỏa mãn điều kiện đề bài dk thì liệt kê thông tin nút p
+Duyệt cây tổng quát xuất phát từ nút em c a nút p với điều kiện dk
+Duyệt cây tổng quát xuất phát từ nút con c a nút p với điều kiện dk
Giải thích:Duyệt cây tổng quát có điều kiện cũng như duyệt không có điều kiện,khi ta đến mỗi nút
trên cây thì kiểm tra thông tin nút đó với điều kiện từ đề bài,nếu thỏa mãn điều kiện đề bài thì ta
thực hiện các thao tác như đếm,liệt kê,tìm kiếm.
Cài đặt:
Pascal:
procedure duyet(p:Nut;dk:KieuDK);{duyệt cây xuất phát từ nút p}
begin
if(p<>nil) then
begin
if(thông tin c a nút p thỏa mãn điều kiện dk) then
begin
{hiển thị thông tin nút p}
end;
duyet(p.em,dk);{duyệt cây xuất phát từ nút em c a nút p với điều kiện dk}
duyet(p.con,dk);{duyệt cây xuất phát từ nút con c a nút p với điều kiện dk}
end;
end;
Java:
void duyet(Nut p,KieuDK dk)//duyệt cây xuất phát từ nút p với điều kiện dk
{
if(p!=null)
{
if(thông tin c a nút p thỏa mãn điều kiện dk)
{
//hiển thị thông tin nút p
}
duyet(p.layEm(),dk); //duyệt cây xuất phát từ nút em c a nút p với điều kiện dk
duyet(p.layCon(),dk); //duyệt cây xuất phát từ nút con c a nút p với điều kiện dk
}
}
Duyệt để tìm kiếm:Duyệt qua tất cả các nút c a cây,khi xem xét từng nút c a cây ta kiểm tra
thông tin c a nút đó,nếu thỏa mãn điều kiện từ đề bài ta sẽ trả về kết quả là: tìm được,không
tìm được,phần tử đang xét,hoặc rỗng.
Thuật toán:Tìm phần tử trên cây xuất phát từ nút p với điều kiện dk
- Nếu nút p rỗng thì trả về kết quả là không tìm thấy(kết quả không tìm thấy có thể là một số
thay thế cho không tìm thấy(ví dụ số 0)hoặc null(cho đối tượng)).
- Nếu thông tin nút p thỏa mãn điều kiện dk thì trả về kết quả tìm thấy(kết quả tìm thấy có thể
là một số thay thế hoặc chính nút p(đối tượng).
- Gán q là kết quả Tìm phần tử trên cây xuất phát từ nút em c a nút p với điều kiện dk
- Nếu q có giá trị là không tìm được thì
+ Trả về kết quả Tìm phần tử trên cây xuất phát từ nút con c a nút p với điều kiện dk
- Ngược lại:Trả về giá trị c a q
Giải thích:Tìm kiếm trên cây tổng quát với điều kiện theo từng bài toán cũng giống như duyệt,khi ta
đến mỗi nút trên cây thì kiểm tra thông tin nút đó với điều kiện từ đề bài,nếu gặp nút có thông tin
thỏa mãn điều kiện dk thì trả về kết quả tìm thấy,nếu sau khi duyệt hết tất cả các nút trên cây mà
không tìm thấy thì trả về kết quả không tìm thấy.
Cài đặt:
Pascal:
procedure tim(p:Nut;dk:KieuDK);{tìm phần tử trên cây xuất phát từ nút p với điều kiện dk}
var q:KieuTV;{}
begin
if(p=nil) then
tim:=0{hoặc tim:=nil nếu không tìm thấy}
else
begin
if(thông tin c a nút p thỏa mãn điều kiện dk) then
begin
tim:=1;{hoặc tim:=p nếu kết quả cần trả về là nút}
end;
q:=tim(p.em,dk);
if(q là giá trị không tìm được) then
tim:=tim(p.con,dk)
else
tim:=q;
end;
end;
Java:
void tim(Nut p,KieuDK dk)//tìm phần tử trên cây xuất phát từ nút p với điều kiện dk
{
if(p==null) return 0;{return null; đây là kết quả không tìm thấy}
if(thông tin c a nút p thỏa mãn điều kiện dk) then
{
return 1;//return p;trả về kết quả tìm thấy
}
q=duyet(p.layEm(),dk);
if(q là giá trị không tìm được)
duyet(p.layCon(),dk);
else
return q;
}
Duyệt để đếm: Duyệt qua tất cả các nút trên cây,khi xem xét từng nút c a cây ta kiểm tra
thông tin c a nút đó,nếu phù hợp với điều kiện yêu cầu từ đề bài ta sẽ đếm số nút cùng điều
kiện c a đề bài.
Thuật toán:Đếm phần tử trên cây xuất phát từ nút p với điều kiện dk
- Nếu nút p rỗng thì trả về kết quả là 0
- Gán count là số phần tử đếm được từ cây em c a nút p cộng với số phần tử đếm được từ cây
con c a nút p.
- Nếu thông tin c a nút p thỏa mãn điều kiện dk thì
+ Trả về kết quả là count+1;
- Ngược lại Trả về kết quả là count
Giải thích:Đếm trên cây tổng quát với điều kiện theo từng bài toán cũng giống như duyệt,khi ta đến
mỗi nút trên cây thì kiểm tra thông tin nút đó với điều kiện từ đề bài,nếu gặp nút có thông tin thỏa
mãn điều kiện dk thì cộng thêm 1 vào tổng số phần từ đếm được từ cây em c a nút p và số phần tử
đếm được cây con c a nút p.
Cài đặt:
Pascal:
function dem(p:Nut;dk:KieuDK):integer;{đếm số phần tử trên cây xuất phát từ nút p với điều kiện
dk}
var count:integer;
begin
if(p=nil) then
dem:=0;
else
begin
count:=dem(p.em,dk)+dem(p.con,dk);
if(thông tin c a nút p thỏa mãn điều kiện dk) then
dem:=count+1
else
dem:=count;
end;
end;
Java:
int dem(Nut p,KieuDK dk)//đếm số phần tử trên cây xuất phát từ nút p với điều kiện dk
{
int count;
if(p==null) return 0;
count=dem(p.layEm(),dk)+dem(p.layCon(),dk);
if(thông tin c a nút p thỏa mãn điều kiện dk)
return count+1;
return count;
}
Chú ý:Trong trư ng hợp đếm tất cả các nút thì t c là đếm không có điều kiện
Các ví dụ cho đếm có điều kiện:
+ Đếm số thư mục con cháu c a thư mục x trên cây thư mục
Đây là bài toán đếm có điều kiện,với điều kiện là thư mục tên x,để giải quyết bài này đơn giản là ta
dùng thuật toán tìm trên cây thư mục tên x,sau đó dùng thuật toán đếm số lượng con cháu c a thư
mục x vừa tìm được.
+ Đếm số tập tin trong thư mục y có phần m rộng(phần đuôi c a file) là “.txt”
Đây là bài toán đếm có điều kiện,với điều kiện là tập tin có phần m rộng là “.txt”,để giải quyết bài
này đơn giản là ta dùng thuật toán đếm số tập tin với điều kiện là có phần m rộng là “.txt”
+ Đếm số ngư i thế hệ th 5 trong dòng họ A
Đây là bài toán đếm có điều kiện ,với điều kiện là thế hệ th 5,để giải quyết bài toán này gắn vào
mỗi ngư i trong dòng họ một giá trị thế hệ chính là độ cao tính từ ông tổ,từ đó ta kiểm tra xem
ngư i nào có độ cao là 5 thì ta đếm những ngư i này.
Giải ví dụ này:Xem thêm phần bổ sung thế hệ cho mỗi nút trên cây
Thuật toán:Đếm trên cây xuất phát từ nút p với độ cao h và điều kiện độ cao dk
- Nếu nút p rỗng thì kết quả đếm là 0
- Nếu nút p khác rỗng (t c là nút p có độ cao h)
+ Gán count là tổng c a Đếm trên cây xuất phát từ nút em c a nút p với độ cao h
và Đếm trên cây xuất phát từ nút con c a nút p với độ cao h+1
+Nếu độ cao h=dk thì trả về kết quả là count+1
+Ngược lại kết quả trả về là count
Cài đặt:cài đặt dưới đây là phần cài đặt tổng quát xuất phát từ nút p,khi gọi thủ tục này thì thay p là
nút gốc và h=0,điều kiện dk=5
Pascal:
function dem(p:Nut;dk:integer,h:integer):integer;{duyệt cây xuất phát từ nút p với điều kiện dk,độ
cao h}
var count:integer;
begin
if(p=nil) then
dem:=0
else
begin
count:=dem(p.em,dk,h)+ dem(p.con,dk,h+1);
if(h=dk) then
dem:=count+1
else
dem:=count;
end;
end;
Java:
void dem(Nut p,int dk,int h)//duyệt cây xuất phát từ nút p với điều kiện dk,với độ cao h
{
int count;
if(p==null) return 0;
count=dem(p.layEm(),dk,h)+dem(p.layCon(),dk,h+1);
if(h==dk)
return count+1;
return count;
}
}
III.Đồ thị
1.Biểu diễn đồ thị bằng ma trận kề
Giả sử G là một đồ thị gồm n đỉnh,giả sử các đỉnh này được đánh số là 1,2,3,…,n.Để biểu diễn đồ
thị ta dùng một mảng hai chiều ch a giá trị là một số thực.
Gọi mtk(ma trận kề) là một mảng hai chiều biểu diễn đồ thị không có trọng số thì các phần tử c a
mảng được xác định như sau:
1 nếu cạnh(cung) (i,j) thuộc đồ thị
mtk[i][j]=
0 nếu cạnh (i,j) không thuộc đồ thị
Đối với đồ thị có trọng số thì phần tử c a mảng được xác định như sau:
C[i][j] nếu cạnh(cung) (i,j) thuộc đồ thị
mtk[i][j]=
0 nếu cạnh (i,j) không thuộc đồ thị
Với C[i][j] là trọng số c a cạnh (i,j)
Khai báo:
Pascal:
Const MaxVerti=…;{số đỉnh tối đa c a đồ thị}
TYPE
KieuPT=…;{kiểu phần tử c a ma trận kề có thể là integer hoặc double}
DoThi=RECORD
soDinh:1..MaxVerti;
mtk:array[1.. MaxVerti,1.. MaxVerti] of KieuPT;
END;
var G:DoThi;
Java:
class DoThi
{
private int soDinh;
private KieuPT mtk[][];
…
}
Chú ý:
+KieuPT thư ng là kiểu int hoặc kiểu double
Duyệt đồ thị theo chiều sâu trên đồ thị biểu diễn bằng ma trận kề
Bổ sung vào trong khai báo DoThi một mảng daTham[] kiểu boolean.đây là mảng đánh dấu các
đỉnh đã thăm,trước khi thực hiện duyệt thì đặt daTham[i]=false (với i=1 đến soDinh)
Thuật toán:Duyệt đồ thị theo chiều sâu xuất phát từ đỉnh v với điều kiện dk
-
Gán daTham[v] là true(t c là đã thăm nút v)
Với mỗi đỉnh w kề với đỉnh v
+Nếu chưa thăm w thì
*Thao tác với thông tin cặp cạnh (v,w) (thao tác:kiểm tra,đếm,liệt kê)
*Duyệt đồ thị theo chiều sâu xuất phát từ đỉnh w với điều kiện dk
Giải thích thuật toán:khi đến thăm nút v thì đặt daTham[v]=true,duyệt lần lượt các đỉnh c a đồ thị
,Nếu đỉnh đang xét là chưa thăm và kề với v thì thực hiện duyệt đồ thị theo chiều sâu xuất phát từ
đỉnh đang xét.
Cài đặt:
Pascal:
procedure duyet(v:integer;KieuDK dk);
var w:integer;
begin
daTham[v]:=true;
for w=1 to G.soDinh do
begin
if(daTham[w]=false and G.mtk[v][w]<>0) then
begin
if(thông tin cặp cạnh (v,w) thỏa mãn điều kiện dk) then
begin
{thao tác:đếm ,liệt kê,…}
end;
duyet(w,dk);
end;
end;
end;
Java:
void duyet(int v,KieuDK dk)
{
int w;
daTham[v]=true;
for(w=0;w<soDinh;w++)
{
if(!daTham[w] && mtk[v][w]!=0)//nếu chưa thăm w và có cạnh (v,w) trong đồ thị
{
if(thông tin cặp cạnh (v,w) thỏa điều kiện dk)
{
//Thao tác với cạnh (v,w);
}
duyet(w,dk);
}
}
}
ng dụng duyệt đồ thị theo chiều sâu trong bài toán tìm đư ng đi từ đỉnh x tới đỉnh y
Tư tư ng thuật toán:ta cũng có một mảng daTham[] đánh dấu đỉnh đã thăm hoặc chưa thăm và một
mảng truoc[] lưu đư ng đi.Thực hiện duyệt đồ thị theo xuất sâu xuất phát từ x ,thăm đỉnh w thì đặt
daTham[w] là true,dùng truoc[w] để lưu đỉnh kề trước c a w.
Thuật toán:duyệt đồ thị theo chiều sâu xuất phát từ đỉnh v
- Gán daTham[v] là true(t c đã thăm v)
- Với mỗi đỉnh w kề với v
+Nếu đỉnh w chưa được thăm thì
*Gán truoc[w] là v (trước khi đến w phải qua v)
*duyệt đồ thị theo chiều sâu xuất phát từ đỉnh w
Thuật toán tìm đư ng đi từ x tới y:
Kh i tạo giá trị cho tất cả các phần tử c a mảng daTham[] là false
Duyệt đồ thị theo chiều sâu xuất phát từ đỉnh x
Nếu daTham[y] là true thì
+ hiển thị đư ng đi lưu trong mảng truoc[]
Ngược lại thì không có đư ng đi từ x tới y
Cài đặt:
Pascal:
procedure duyet(v:integer);
var w:integer;
begin
daTham[v]:=false;
for w:=1 to G.soDinh do
begin
if(daTham[w]=false and mtk[v][w]<>0) then{nếu chưa thăm w và cạnh (v,w) có trong
đồ thị}
begin
truoc[w]:=v;{trước w là v hay v là đỉnh kề trước c a w}
duyet(w);{duyệt sâu từ đỉnh w}
end;
end;
end;
void duongdi(x:integer;y:integer);
var i:integer;
begin
for i:=1 to G.soDinh do
daTham[i]:=false;
duyet(x);
if(daTham[y]=true)
begin
i:=y;
while(i<>x) do
begin
write(i,‟ <-„);
i:=truoc[i];{lấy đỉnh trước đỉnh i}
end;
write(i,‟ <-„);{hiển thị đỉnh x}
end
else
writeln(„khong co duong di tu ‟,x,‟ toi „,y);
end;
Java:
void duyet(int v)
{
int w;
daTham[v]=true;
for(w=0;w<soDinh;w++)
{
if(!daTham[w] && mtk[v][w]!=0)//nếu chưa thăm w và cạnh(v,w) có trong đồ thị
{
truoc[w]=v;//trước w là v hay v là đỉnh kề trước c a w
duyet(w);//duyệt sâu xuất phát từ w
}
}
}
void duongdi(int x,int y)
{
int i;
for(i=0;i<soDinh;i++)
daTham[i]=false;
duyet(x);//duyệt sâu xuất phát từ đỉnh x
if(daTham[w])
{
i=y;
while(i!=x)
{
System.out.print(“%d <-”,i);
i=truoc[i];//lấy đỉnh trước đỉnh i
}
}
else
System.out.println(“khong co duong di tu %d toi %d”,x,y);
}
Ví dụ:Các bài toán có thể giải quyết bằng duyệt đồ thị theo chiều sâu
+ Tìm đư ng đi từ đỉnh x tới đỉnh y sao cho trọng số mỗi cạnh trên đư ng đi phải lớn hơn W
Giải quyết bài này như sau:duyệt đồ thị theo chiều sâu xuất phát từ x,điều kiện duyệt là W,chỉ đi qua
những cạnh nào giá trị lớn hơn W.
+ Liệt kê những đỉnh không kề với x
Giải quyết bài này như sau:Với mỗi đỉnh y c a đồ thị mà y khác x,kiểm tra cạnh (x,y) có thuộc đồ
thị hay không,nếu không thuộc đồ thị thì tăng biến đếm thêm 1.
+ Liệt kê những đỉnh đi đến được đỉnh x
Giải quyết bài này như sau:Với mỗi đỉnh y c a đồ thị mà y khác x,tìm đư ng đi từ y tới x,nếu tìm
được đư ng đi từ y tới x thì tăng biến đếm thêm 1 (t c là có thêm một đỉnh có đư ng đi tới đỉnh x).
+ Kiểm tra đồ thị có liên thông hay không
Giải quyết bài này như sau:Duyệt đồ thị theo chiều sâu xuất phát từ một đỉnh bất kì,nếu sau khi
duyệt mà có một đỉnh nào đó chưa được thăm thì đồ thị đã cho không liên thông,ngược lại thì liên
thông.
+ Liệt kê các thành phần liên thông
Với mỗi đỉnh v c a đồ thị mà v chưa được thăm,thực hiện duyệt theo chiều sâu xuất phát từ đỉnh
v,trong khi duyệt kết hợp hiển thị các đỉnh đã thăm.
Như vậy mỗi lần duyệt theo chiều sâu xuất phát từ đỉnh v ta sẽ liệt kê được những đỉnh đã
thăm,những đỉnh nào chưa thăm lần duyệt này t c không thuộc thành phần liên thông với đỉnh v.
Thuật toán kiểm tra một dãy các đỉnh là đư ng đi:Đơn giản ta kiểm tra 2 đỉnh liên tiếp có phải là
cạnh c a đồ thị.
Thuật toán:
Duyệt lần lượt từng đỉnh trong dãy đỉnh từ đầu tới kề cuối
+Nếu đỉnh đang xét và đỉnh liền sau nó trong dãy không tạo thành một cạnh trong đồ thị thì
*Kết quả trả về là false(dãy đã cho không phải là đư ng đi),dừng lặp
Nếu duyệt hết dãy thì kết quả trả về là true(dãy đã cho là đư ng đi)
Giải thích:với mỗi cặp đỉnh liên tiếp trong dãy ta kiểm tra nó có trong đồ thị hay không,nếu không
có thì kết luận dãy đỉnh đã cho không phải đư ng đi,Nếu duyệt hết các cặp đỉnh liên tiếp mà cặp
đỉnh nào cũng là cạnh c a đồ thị thì kết luận dãy đã cho là đư ng đi.
Cài đặt:
Pascal:
function ktDuongDi(day:array[] of integer;n:integer):boolean;
var i:integer;
begin
ktDuongDi:=true;{đặt giá trị lúc đầu bằng true để khi duyệt nếu không thay đổi thì giá trị c a
nó vẫn là true}
for i:=1 to n-1 do
begin
if(mtk[day[i]][day[i+1]]=0) then
begin
ktDuongDi:=false;{hai đỉnh liên tiếp không phải là cạnh c a đồ thị}
break;
end;
end;
end;
Java:
boolean ktDuongDi(int day[])
{
int i;
for(i=0;i<day.length-1;i++)
if(mtk[day[i]][day[i+1]]==0)
return false;//có 1 cạnh không thuộc đồ thị
return true;//duyệt hết mà tất cả các cạnh đều thuộc đồ thị
}
Duyệt đồ thị theo chiều rộng
Để duyệt đồ thị theo chiều rộng ta cần sử dụng hàng đợi.
Thuật toán duyệt theo chiều rộng xuất phát từ đỉnh v:
- Kh i tạo hàng đợi q rỗng
- Đưa đỉnh v vào hàng đợi
- Đánh dấu đã thăm đỉnh v
- Lặp trong khi hàng đợi chưa rỗng
+Gán w là đỉnh lấy ra từ hàng đợi q
+Thao tác với đỉnh w(liệt kê,đếm,tìm kiếm)
+Với mỗi đỉnh x kề với w
*Nếu x chưa được thăm thì
**đánh dấu đã thăm x
**đưa x vào hàng đợi q
Cài đặt:
Pascal:
procedure duyetrong(v:integer);
var q:Queue;
var x,w:integer;
begin
Init(q);
AddQueue(q,v);
daTham[v]:=true;
while(not emty(q)) do
begin
RemoveQueue(q,w);
{Thao tác với đỉnh w (liệt kê,đếm,tìm kiếm)}
for x:=1 to G.soDinh do
begin
if(daTham[x]=false and mtk[w][x]<>0) then
begin
daTham[x]:=true;
AddQueue(q,x);
end;
end;
end;
end;
Java:
void duyetRong(int v)
{
int x,w;
Queue q=new LinkedList();
daTham[v]=true;
q.add(v);
while(!q.isEmty())
{
w=q.remove();
//thao tác với đỉnh w (liệt kê,đếm,tìm kiếm)
for(x=0;x<soDinh;x++)
{
if(!daTham[x] && mtk[w][x]<>0)
{
daTham[x]=true;
q.add(x);
}
}
}
}
2.Biểu diễn đồ thị bằng danh sách kề
Với mỗi đỉnh ta lưu một danh sách các đỉnh kề với nó
Khai báo:
Pascal:
const MaxVerti=…;{số đỉnh tối đa c a đồ thị}
TYPE
DSKe=^PTLK;
PTLK=RECORD
dinh:integer;
trongSo:double;
lienKet:DSKe;
DoThi=RECORD
soDinh:0.. MaxVerti;
dsk:array[1..MaxVerti] of DSKe;
END;
var G:DoThi;
Java:
Class DSKe
{
private int/double trongSo;// thư ng là kiểu int hoặc double
private int dinh;//đỉnh kề
private DSKe lienKet;
…
}
class DoThi
{
private int soDinh;
private DSKe dsk[];
…
}
Duyệt đồ thị theo chiều sâu trên đồ thị biểu diễn bằng danh sách cạnh
Bổ sung vào trong khai báo DoThi một mảng daTham[] kiểu boolean.đây là mảng đánh dấu các
đỉnh đã thăm,trước khi thực hiện duyệt thì đặt daTham[i]=false (với i=1 đến soDinh)
Thuật toán:Duyệt đồ thị theo chiều sâu xuất phát từ đỉnh v với điều kiện dk
- Gán daTham[v] là true(t c là đã thăm nút v)
- Với mỗi đỉnh w kề với đỉnh v
+Nếu chưa thăm w thì
*Thao tác với thông tin cặp cạnh (v,w) (thao tác:kiểm tra,đếm,liệt kê)
*Duyệt đồ thị theo chiều sâu xuất phát từ đỉnh w với điều kiện dk
Thuật toán chi tiết cho đồ thị biểu diễn bằng danh sách cạnh:
Duyệt đồ thị theo chiều sâu xuất phát từ đỉnh v với điều kiện dk
- Gán daTham[v] là true(t c là đã thăm nút v)
- Gán p là danh sách kề c a v
- Lặp trong khi p khác rỗng
+Nếu chưa thăm đỉnh c a phần tử p thì
*Thao tác với thông tin cặp cạnh (v,đỉnh c a p) (thao tác:kiểm tra,đếm,liệt kê)
*Duyệt đồ thị theo chiều sâu xuất phát từ đỉnh c a phần tử p với điều kiện dk
+Chuyển p sang phần tử ngay sau nó
Giải thích thuật toán:khi đến thăm nút v thì đặt daTham[v]=true,duyệt lần lượt các đỉnh c a đồ thị
,Nếu đỉnh đang xét là chưa thăm và kề với v thì thực hiện duyệt đồ thị theo chiều sâu xuất phát từ
đỉnh đang xét.
Cài đặt:
Pascal:
procedure duyetsau(v:integer;KieuDK dk);
var p:DSKe;
begin
daTham[v]:=true;
p:=G.dsk[v];
while(p<>nil)
begin
if(daTham[p.dinh]=false ) then
begin
if(thông tin cạnh (v, p.dinh) thỏa mãn điều kiện dk) then
begin {thao tác với đỉnh p.dinh}
duyetsau(p.dinh,dk);
end;
end;
p:=p.lienKet;
end;
end;
Java:
void duyetSau(int v,KieuDK dk)
{
DSKe p;
daTham[v]=true;
p=dsk[v];
while(p!=null)
{
If(!daTham[p.layDinh()] )
{
If(thông tin cạnh (v, p.layDinh()) thỏa điều kiện dk)
{
//thao tác với đỉnh p.layDinh()
duyetSau(p.layDinh(),dk);
}
}
p=p.layLienKet();
}
}
ng dụng duyệt đồ thị theo chiều sâu trong bài toán tìm đư ng đi từ đỉnh x tới đỉnh y
Tư tư ng thuật toán:ta cũng có một mảng daTham[] đánh dấu đỉnh đã thăm hoặc chưa thăm và một
mảng truoc[] lưu đư ng đi.Thực hiện duyệt đồ thị theo xuất sâu xuất phát từ x ,thăm đỉnh w thì đặt
daTham[w] là true,dùng truoc[w] để lưu đỉnh kề trước c a w.
Thuật toán:duyệt đồ thị theo chiều sâu xuất phát từ đỉnh v
- Gán daTham[v] là true(t c đã thăm v)
- Với mỗi đỉnh w kề với v
+Nếu đỉnh w chưa được thăm thì
*Gán truoc[w] là v (trước khi đến w phải qua v)
*duyệt đồ thị theo chiều sâu xuất phát từ đỉnh w
Thuật toán tìm đư ng đi từ x tới y:
Kh i tạo giá trị cho tất cả các phần tử c a mảng daTham[] là false
Duyệt đồ thị theo chiều sâu xuất phát từ đỉnh x
Nếu daTham[y] là true thì
+ hiển thị đư ng đi lưu trong mảng truoc[]
Ngược lại thì không có đư ng đi từ x tới y
Cài đặt:
Pascal:
procedure duyetsau(v:integer);
var p:DSKe;
begin
daTham[v]:=true;
p:=G.dsk[v];
while(p<>nil)
begin
if(daTham[p.dinh]=false ) then
begin
truoc[p.dinh]:=v;
duyetsau(p.dinh);
end;
p:=p.lienKet;
end;
end;
void duongdi(x:integer;y:integer);
var i:integer;
begin
for i:=1 to G.soDinh do
daTham[i]:=false;
duyet(x);
if(daTham[y]=true)
begin
i:=y;
while(i<>x) do
begin
write(i,‟ <-„);
i:=truoc[i];{lấy đỉnh trước đỉnh i}
end;
write(i,‟ <-„);{hiển thị đỉnh x}
end
else
writeln(„khong co duong di tu ‟,x,‟ toi „,y);
end;
Java:
void duyetSau(int v,KieuDK dk)
{
DSKe p;
daTham[v]=true;
p=dsk[v];
while(p!=null)
{
if(!daTham[p.layDinh()] )
{
truoc[p.layDinh()]=v;
duyetSau(p.layDinh());
}
p=p.layLienKet();
}
void duongDi(int x,int y)//in đư ng đi theo chiều thuận
{
if(y!=x)
duongDi(x,truoc[y]);
System.out.print(“%d ->”,y);
}
void duongdi(int x,int y)//in đư ng đi theo chiều ngược lại
{
int i;
for(i=0;i<soDinh;i++)
daTham[i]=false;
duyet(x);//duyệt sâu xuất phát từ đỉnh x
if(daTham[w])
{
i=y;
while(i!=x)
{
System.out.print(“%d <-”,i);
i=truoc[i];//lấy đỉnh trước đỉnh i
}
}
else
System.out.println(“khong co duong di tu %d toi %d”,x,y);
}
Ví dụ:Các bài toán có thể giải quyết bằng duyệt đồ thị theo chiều sâu
+ Tìm đư ng đi từ đỉnh x tới đỉnh y sao cho trọng số mỗi cạnh trên đư ng đi phải lớn hơn W
Giải quyết bài này như sau:duyệt đồ thị theo chiều sâu xuất phát từ x,điều kiện duyệt là W,chỉ đi qua
những cạnh nào giá trị lớn hơn W.
+ Liệt kê những đỉnh không kề với x
Giải quyết bài này như sau:Với mỗi đỉnh y c a đồ thị mà y khác x,kiểm tra cạnh (x,y) có thuộc đồ
thị hay không,nếu không thuộc đồ thị thì tăng biến đếm thêm 1.
+ Liệt kê những đỉnh đi đến được đỉnh x
Giải quyết bài này như sau:Với mỗi đỉnh y c a đồ thị mà y khác x,tìm đư ng đi từ y tới x,nếu tìm
được đư ng đi từ y tới x thì tăng biến đếm thêm 1 (t c là có thêm một đỉnh có đư ng đi tới đỉnh x).
+ Kiểm tra đồ thị có liên thông hay không
Giải quyết bài này như sau:Duyệt đồ thị theo chiều sâu xuất phát từ một đỉnh bất kì,nếu sau khi
duyệt mà có một đỉnh nào đó chưa được thăm thì đồ thị đã cho không liên thông,ngược lại thì liên
thông.
+ Liệt kê các thành phần liên thông
Với mỗi đỉnh v c a đồ thị mà v chưa được thăm,thực hiện duyệt theo chiều sâu xuất phát từ đỉnh
v,trong khi duyệt kết hợp hiển thị các đỉnh đã thăm.
Như vậy mỗi lần duyệt theo chiều sâu xuất phát từ đỉnh v ta sẽ liệt kê được những đỉnh đã
thăm,những đỉnh nào chưa thăm lần duyệt này t c không thuộc thành phần liên thông với đỉnh v.
Duyệt đồ thị biểu diễn bằng danh sách kề theo chiều rộng
Để duyệt đồ thị theo chiều rộng ta cần sử dụng hàng đợi.
Thuật toán duyệt theo chiều rộng xuất phát từ đỉnh v:
- Kh i tạo hàng đợi q rỗng
- Đưa đỉnh v vào hàng đợi
- Đánh dấu đã thăm đỉnh v
- Lặp trong khi hàng đợi chưa rỗng
+Gán w là đỉnh lấy ra từ hàng đợi q
+Thao tác với đỉnh w(liệt kê,đếm,tìm kiếm)
+Với mỗi đỉnh x kề với w
*Nếu x chưa được thăm thì
**đánh dấu đã thăm x
**đưa x vào hàng đợi q
Cài đặt:
Pascal:
procedure duyetRong(v:integer);
var q:Queue;
var w:integer;
var p:DSKe;
begin
Init(q);
AddQueue(q,v);
daTham[v]:=true;
while(not empty(q)) do
begin
RemoveQueue(q,w);
{Thao tác với đỉnh w (liệt kê,đếm,tìm kiếm)}
p:=G.dsk[w];
while(p<>nil) do
begin
if(daTham[p.dinh]=false) then
begin
daTham[p.dinh]:=true;
AddQueue(q,p.dinh);
end;
p:=p.lienKet;
end;
end;
end;
Java:
void duyetRong(int v)
{
int w;
DSKe p;
Queue q=new LinkedList();
daTham[v]=true;
q.add(v);
while(!q.isEmty())
{
w=q.remove();
//thao tác với đỉnh w (liệt kê,đếm,tìm kiếm)
p=dsk[w];
while(p!=null)
{
if(!daTham[p.layDinh()])
{
daTham[p.layDinh()]=true;
q.add(p.layDinh());
}
p=p.layLienKet();
}
}
}
3.Biểu diễn đồ thị bằng danh sách cạnh
Dùng một mảng lưu tất cả các cạnh c a đồ thị
Khai báo:
Pascal:
const Max_Edge=…;{số cạnh tối đa bằng bình phương c a số đỉnh}
TYPE
Canh=RECORD
dinhDau:integer;
dinhCuoi:integer;
trongSo:double;
DoThi=RECORD
soCanh:integer;
dsc:array[Max_Edge] of Canh;{dsc là mảng danh sách cạnh}
END;
var G:DoThi;
Java:
class Canh
{
private int dinhDau,dinhCuoi;
private int/double trongSo;//kiểu trọng số có thể là int hoặc double
…
}
class DoThi
{
private int soCanh;
private Canh dsc[];
…
}