Cấu trúc dữ liệu

- Cấu trúc dữ liệu I.
- 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 có điều kiện  Thêm 1.
- Thêm có điều kiện  Xóa 1.
- Xóa có điều kiện II.
- Duyệt có điều kiện  Thêm (chỉ có trên cây nhị phân) 1.
- Thêm có điều kiện  Xóa (chủ yếu là xóa nút lá) 1.
- Xóa có điều kiện III.
- 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.
- Type DanhSach=record mangpt:Array[1..Max] of KieuPT.
- 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.
- private int soPT.
- 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ụ 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.
- DSSV=record sv:array[1..Max_SV] of SinhVien.
- soSV:0..Max_SV.
- Java: class SinhVien { private string ten.
- private string masv.
- 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.
- tacGia:array[1..5] of string.
- DSCS=record cs:array[1..Max_CS] of CuonSach.
- soCS:0..Max_CS.
- Java: class CuonSach { private string ten.
- private int giaTien.
- private string tacGia.
- private int soTacGia.
- 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.
- DSPhong=record ph:array[1..Max_Phong] of Phong.
- soPhong:0..Max_Phong.
- Java: class Phong { private string maPhong.
- private string tenKH.
- private int thoiGian.
- 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.
- 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.
- Java: class HangHoa { private string tenHH.
- private int soLuong.
- private int donGia.
- private int thanhTien.
- private int soHH.
- 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.
- DSTB=record tb:array[1..Max_ThueBao] of ThueBao.
- soTB:0..Max_ThueBao.
- Java: class ThueBao { private string tenTB.
- private string soDT.
- 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.
- 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.
- begin for i:=1 to n do { ds.mangpt[i] chính là phần tử đang xét } end.
- 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.
- 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.
- 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=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).
- for(i=0;i=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