Cấu trúc dữ liệu

Điệp Đinh Ngọc

Se analiza como a traves de la aritmetica en diferentes sistemas de numeracion posicional, se fomenta, desarrolla y promueve el pensamiento numerico. Observando que cuando uno se ve enfrentando a situaciones de trato numerico, suele convertir la resolucion de un problema en la solucion de algoritmos; no se analiza, en cambio si se opera. Se busca que mediante bases numericas diferentes al decimal, se analicen y comprendan los principios posicionales implicitos al operar. La investigacion se centra en tres pilares que contribuyen a desarrollar el pensamiento numerico, tomados del Ministerio de Educacion Nacional y del investigador Luis Rico Romero y su grupo de investigacion, los cuales son: - Comprension de los numeros y de la numeracion. - Comprension del concepto de las operaciones. - Calculos con numeros y aplicaciones de numeros y operaciones.

The use of a simple Windows authentication password is not always enough to ensure protection and confidentiality of the data stored on user’s workstations. In this paper we propose and implement an encrypted file system. The proposed solution is based on creating and using encrypted volumes embedded (stored) on a physical partition. The encrypted volumes act as virtual drives which offer the user the impression that he’s working with a normal physical partition. Security of the password and the encrypted volumes’ portability are ensured by the developed application.

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[]; … }

RELATED PAPERS

RELATED TOPICS

Log In

Cấu trúc dữ liệu

Cấu trúc dữ liệu

Related Papers

RELATED PAPERS

RELATED TOPICS