<span class="text_page_counter">Trang 1</span><div class="page_container" data-page="1">

TRƯỜNG ĐẠI HỌC MỞ HÀ NỘI

<b>KHOA CÔNG NGHỆ THÔNG TIN</b>

<b>---BÁO CÁO BÀI TẬP LỚN</b>

<b>MÔN CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬTĐề tài: Quản lý cho thuê xe Ô TÔ</b>

<b> Giảng viên hướng dẫn: ThS.Trịnh Thị Xuân</b>

<i><b> Sinh viên thực hiện: Bùi Hải Triều- 2010A04</b></i>

<i> Lê Tuấn Vũ – 2010A04 Đoàn Minh Tùng – 2010A04 Lê Quang Vinh – 2010A05</i>

<b>Hà Nội – Năm 2021</b>

</div><span class="text_page_counter">Trang 2</span><div class="page_container" data-page="2">

<b><small>PHÂN CÔNG VÀ KẾ HOẠCH THỰC HIỆN</small></b>

MỤC LỤC

<b><small>A. XÁC ĐỊNH BÀI TỐN...1</small></b>

<small>I.Phát biểu bài tốn...1</small>

<small>II. Xác định cấu trúc dữ liệu bài toán...1</small>

<small>III.Xác định các thuật toán và chức năng...1</small>

<b><small>B. XÁC ĐỊNH CẤU TRÚC DỮ LIỆU CỦA BÀI TỐN...2</small></b>

<small>I.Mơ tả cấu trúc dữ liệu tổ chức để lưu trữ cho bài tốn...2</small>

<i><small>1.Danh sách liên kết đơn...2</small></i>

<i><small>2.Danh sách liên kết đơi...4</small></i>

<i><small>3.Ngăn xếp(Tương tự 1 và 2 )...6</small></i>

<i><small>4.Hàng Đợi(Tương tự 1 và 2 )...6</small></i>

<small>II. Liệt kê input và output của từng chức năng...6</small>

<b><small>C. XÁC ĐỊNH CÁC THUẬT TOÁN...8</small></b>

<small>I.Danh sách liên kết đơn...8</small>

<small>II. Danh sách liên kết đôi...18</small>

<small>III.Ngăn xếp... 28</small>

<small>IV.Hàng đợi... 34</small>

<b><small>D. Cài Đặt – Kiểm Thử...42</small></b>

<small>1.Danh sách liên kết đơn...42</small>

<small>2.Danh sách liên kết đôi...49</small>

<small>3.Ngăn Xếp (Stack)...56</small>

<small> 4.Hang đợi (Queue)...63</small>

<b>A.XÁC ĐỊNH BÀI TỐN</b>

2

</div><span class="text_page_counter">Trang 3</span><div class="page_container" data-page="3">

I. Phát biểu bài tốn

Ngày nay với sự phát triển của ngành công nghệ thông tin đã đem lại hiệu quả to lớn trong nhiều lĩnh vực, đáp ứng nhu cầu ngày càng cao của cuộc sống con người trong đó có quản lý trong lĩnh vực thuê xe ô tô . Đây là một trong những lĩnh vực phổ biển ở việt nam và nhận được nhiều sự quan tâm và thảo luận rộng rãi . Vì vậy , việc quản lý hóa đơn cho th xe ơ tơ trên máy tính , chúng ta sẽ giảm bớt khối cơng việc rất lớn cho người quản lý , giảm bớt nhân sự cho khâu này , dễ dàng quản lý , nhập nhật và thay đổi linh hoạt của thơng tin hóa đơn một cách linh hoạt nhất.

Cửa hàng cho thuê xe ô tô cần lưu danh sách thông tin Xe ô tô cho thuê , Khách hàng và Hóa đơn cho thuê .

II. Xác định cấu trúc dữ liệu bài tốn

 Xe ơ tơ : <i>Mã xe , Tên xe, Hãng xe, giá cho thuê . </i>

<i> Khách hàng : Mã khách hàng, Họ tên ,SDT, CMND, Địa chỉ. Hóa đơn : Mã HĐ ,ngày thuê, số ngày thuê, số lượng xe thuê, thành </i>

<i>tiền,,thông tin ô tô thuê,thông tin khách hàng</i>

(Giá cho thê từ ô tô * số lượng xe muốn thuê)*số ngày thuê = thành tiền III. Xác định các thuật tốn và chức năng

<i><b> Đối với ơ tơ</b></i>

 Nhập danh sách ô tô  Hiện danh sách ô tô  Ghi danh sách ô tô vào file  Đọc file danh sách ô tô  Thêm ô tơ vào cuối danh sách  Xóa một ơ tơ vào đầu danh sách  Tìm kiếm ơ tơ theo mã xe

<i><b> Chức năng thực hiện với hóa đơn</b></i>

 Nhập danh sách hóa đơn 3

</div><span class="text_page_counter">Trang 4</span><div class="page_container" data-page="4">

 Hiện danh sách hóa đơn  Ghi danh sách hóa đơn vào file  Đọc danh sách hóa đơn từ file

 Thêm hóa đơn mới( Thêm đầu , thêm cuối ….. )  Xóa hóa đơn ( Xóa đầu , xóa cuối …….)  Tổng tiền tất cả hóa đơn

 Sắp xếp theo tổng tiền tăng dần trong hóa đơn  Săp xếp tăng dần theo số ngày thuê trong hóa đơn  Sắp xếp giảm dần theo số lượng xe thue trong mỗi hóa đơn

 Lọc ra những hóa đơn có tổng tiền từ > =150000000 & <=300000000  Tìm kiếm hóa đơn có tổng tiền cao nhất

 Tìm kiếm hóa đơn có tổng tiền thấp nhất

B.XÁC ĐỊNH CẤU TRÚC DỮ LIỆU CỦA BÀI TỐN I. Mơ tả cấu trúc dữ liệu tổ chức để lưu trữ cho bài toán

<i>1. Danh sách liên kết đơna. Đối tượng OTO</i>

4

</div><span class="text_page_counter">Trang 5</span><div class="page_container" data-page="5">

<i>b. Đối tượng Hóa Đơn</i>

<small> </small>

<small> </small>

5

</div><span class="text_page_counter">Trang 6</span><div class="page_container" data-page="6">

<i>2. Danh sách liên kết đôia. Đối tượng OTO</i>

6

</div><span class="text_page_counter">Trang 7</span><div class="page_container" data-page="7">

b. Đối tượng hóa đơn

7

</div><span class="text_page_counter">Trang 8</span><div class="page_container" data-page="8">

<i>3. Ngăn xếp(Tương tự 1 và 2 )a. Đối tượng OTOb. Đối tượng Hóa Đơn4. Hàng Đợi(Tương tự 1 và 2 )</i>

<i>a. Đối tượng OTOb. Đối tượng Hóa Đơn</i>

II. Liệt kê input và output của từng chức năng 1. Đối tượng OTO

1.1: Nhập danh sách ô tô

 Input: Thông tin giáo viên nhập từ bàn phím gồm: Mã ơ tơ, tên xe, Hãng xe, Giá cho thuê

 Output: Thông tin ô tô được lưu trữ trên máy tính. 1.2: Hiện danh sách ơ tơ

 Input: Thơng tin ơ tơ lưu trữ trên máy tính.  Output: Danh sách ô tô được in ra trên màn hình. 1.3: Ghi danh sách ơ tơ vào file

 Input: Danh sách ô tô

 Output: Danh sách ô tô được lưu trữ trên máy tính dưới dạng file. 1.4: Đọc danh sách ô tô từ file

 Input: Danh sách ơ tơ được lưu trữ trên máy tính dưới dạng file.  Output: Dữ liệu trong file được in ra trên màn hình.

1.5: Thêm giáo ơ tơ

 Intput: Thơng tin của ô tô mới, danh sách ô tô.  Output: Danh sách ô tô sau khi được thêm giáo viên mới.

8

</div><span class="text_page_counter">Trang 9</span><div class="page_container" data-page="9">

1.6: Xóa giáo viên

 Input: Danh sách ơ tơ, thực hiện xóa ơ tơ.

 Output: Danh sách ơ tơ sau khi xóa được hiển thị trên màn hình. 1.7: Tìm kiếm giáo viên theo mã ô tô X

 Input: Danh sách ô tô, mã ô tơ của từng ơ tơ, X nhập từ bàn phím.  Output: Thơng tin của ơ tơ đang được tìm kiếm hiển thị trên màn hình. 1.8: Sắp xếp danh sách ô tô theo chiều giảm dần của giá cho thuê

 Input: Danh sách ô tô, tên của từng ô tô.

 Output: Danh sách ô tô sau khi sắp xếp được hiển thị trên màn hình. 2. Đối tượng Hóa Đơn

2.1: Nhập danh sách Hóa Đơn

 Input: Thơng tin Hóa đơn nhập từ bàn phím gồm: Mã hóa đơn, ngày thuê, sô ngày thuê , số lượng xe thuê, thành tiền , thông tin xe ds ô tô thuê, thơng tin khách hàng th

 Output: Thơng tin Hóa đơn được lưu trữ trên máy tính. 2.2: Hiện danh sách hóa đơn

 Input: Thơng tin hóa đơn lưu trữ trên máy tính.  Output: Danh sách hóa đơn được in ra trên màn hình. 2.3: Ghi danh sách bảng lương vào file

 Input: Danh sách Hóa đơn.

 Output: Danh sách hóa đơn được lưu trữ trên máy tính dưới dạng file. 2.4: Đọc danh sách hóa đơn từ file

 Input: Danh sách hóa đơn được lưu trữ trên máy tính dưới dạng file.  Output: Dữ liệu trong file được in ra trên màn hình.

2.5: Thêm hóa đơn mới

 Intput: Thơng tin của hóa đơn mới, danh sách hóa đơn, vị trí cần thêm.  Output: Danh sách hóa đơn sau khi được thêm bảng lương mới. 2.6: Xóa hóa đơn

 Input: Danh sách hóa đơn, thực hiện xóa bảng lương.

 Output: Danh sách hóa đơn sau khi xóa được hiển thị trên màn hình. 2.7: Tổng tiền tất cả hóa đơn

 Input: Thành tiền danh sách hóa đơn

 Output: Tổng tất cả thành tiền của tất cả hóa đơn hiển thị trên màn hình. 2.8: Loc ra Hoa Don co tong tien >=5.000.000 & <= 10.000.000

 Input: Danh sách hóa đơn, tổng tiền của từng hóa đơn.

 Output: Danh sách hóa đơn sau khi lọc được hiển thị trên màn hình. 2.9: Sắp xếp danh sách hóa đơn theo tổng tiền tăng dần

9

</div><span class="text_page_counter">Trang 10</span><div class="page_container" data-page="10">

 Input: Danh sách hóa đơn

 Output: Danh sách hóa đơn sau khi sắp xếp được hiển thị trên màn hình. 2.10: Sắp xếp hóa đơn theo chiều giảm dần số lượng xe th

 Input: Danh sách hóa đơn.

 Output: Thơng tin hóa đơn của giáo viên có lương nhỏ nhất 2.11: Thơng tin hóa đơn có tổng tiền là lớn nhất

 Input: Danh sách hóa đơn, tổng tiền của từng hóa đơn.  Output: Thơng tin hóa đơn có tổng tiền lớn nhất 2.12: Thơng tin hóa đơn có tổng tiền là ít nhất

 Input: : Danh sách hóa đơn, tổng tiền của từng hóa đơn.  Output: Thơng tin hóa đơn có tổng tiền ít nhất 2.13: Thơng tin hóa đơn theo mã hóa đơn X

 Input: Danh sách hóa đơn, mã x nhập từ bàn phím.  Output: Thơng tin hóa đơn tìm kiếm.

2.14: Thơng tin hóa đơn theo tên khách hàng

 Input: Danh sách hóa đơn , tên khách hàng nhập tự bàn phím  Output: Hiện thị thơng tin hóa đơn tìm kiếm.

C.XÁC ĐỊNH CÁC THUẬT TỐN I. Danh sách liên kết đơn

1. Nhập danh sách( bao gồm hóa đơn và ơ tơ)  Áp dụng cho danh sách ơ tơ & Hóa đơn

10

</div><span class="text_page_counter">Trang 11</span><div class="page_container" data-page="11">

2. Hiện danh sách

 Áp dụng với danh sách ô tô và Hóa đơn

11

</div><span class="text_page_counter">Trang 13</span><div class="page_container" data-page="13">

3.1 Thêm vào cuối danh sách

 Áp dụng với danh sách ô tô & Hóa đơn

13

</div><span class="text_page_counter">Trang 14</span><div class="page_container" data-page="14">

3.2 Thêm phần tử bất kỳ vào trong danh sách  Áp dụng với danh sách ơ tơ & Hóa đơn

14

</div><span class="text_page_counter">Trang 15</span><div class="page_container" data-page="15">

4. Xóa phần tử cuối danh sách

 Áp dụng cho danh sách ơ tơ và Hóa đơn 15

</div><span class="text_page_counter">Trang 16</span><div class="page_container" data-page="16">

4.1 Xóa phần tử bất kỳ danh sách

 Áp dụng cho danh sách ô tô và Hóa đơn

16

</div><span class="text_page_counter">Trang 17</span><div class="page_container" data-page="17">

5. Tổng tiền tất cả hóa đơn

 Áp dụng cho tổng tiền tất cả hóa đơn

17

</div><span class="text_page_counter">Trang 18</span><div class="page_container" data-page="18">

6. Sắp xếp danh sách

 Sắp xếp tổng tiền tăng dần hóa đơn

18

</div><span class="text_page_counter">Trang 19</span><div class="page_container" data-page="19">

 Sắp xếp tăng dần thôi số ngày thuê xe ô tô

 Sắp xếp giảm dần theo số lượng xe th trong hóa đơn

7. Tìm kiếm danh sách

 Tìm kiếm hóa đơn có tổng tiền thấp nhất 19

</div><span class="text_page_counter">Trang 20</span><div class="page_container" data-page="20">

 Tìm kiếm hóa đơn có tổng tiền cao nhất  Tìm kiếm thơng tin hóa đơn theo số ngày th  Tìm kiếm thơng tin hóa đơn theo tên khách hàng

II. Danh sách liên kết đôi 1. Nhập danh sách

20

</div><span class="text_page_counter">Trang 21</span><div class="page_container" data-page="21">

 Nhập danh sách ô tô và Hóa đơn

2. Hiện danh sách

 Hiện danh sách ơ tơ và hóa đơn 21

</div><span class="text_page_counter">Trang 22</span><div class="page_container" data-page="22">

3. Thêm vào đầu danh sách

 Áp dụng với danh sách ơ tơ và Hóa đơn

22

</div><span class="text_page_counter">Trang 23</span><div class="page_container" data-page="23">

III.1 Thêm phần tử vào cuối danh sách  Áp dụng với dánh sách ơ tơ và Hóa đơn

23

</div><span class="text_page_counter">Trang 24</span><div class="page_container" data-page="24">

III.2 Thêm phần tử vào một ví trị bất kỳ sau q  Áp dụng với danh sách ô tơ và Hóa đơn

24

</div><span class="text_page_counter">Trang 25</span><div class="page_container" data-page="25">

4. Xóa phần tử ở đầu danh sách

 Áp dụng với danh sách ô tô và Hóa đơn

25

</div><span class="text_page_counter">Trang 26</span><div class="page_container" data-page="26">

4.1 Xóa cuối danh sách

 Áp dụng với danh sách ô tơ và Hóa đơn

4.2 Xóa phần tử bất kỳ trong danh sách  Áp dụng với danh sách ô tô và Hóa đơn

26

</div><span class="text_page_counter">Trang 27</span><div class="page_container" data-page="27">

5. Tổng tiền tất cả danh sách hóa đơn

 Tổng tiền tất cả hóa đơn trong danh sách hóa đơn

27

</div><span class="text_page_counter">Trang 28</span><div class="page_container" data-page="28">

6. Sắp xếp danh sách hóa đơn

 Sắp xếp tổng tiền tăng dần hóa đơn  Sắp xếp tăng dần thơi số ngày thuê xe ô tô

28

</div><span class="text_page_counter">Trang 29</span><div class="page_container" data-page="29">

 Sắp xếp giảm dần theo số lượng xe thuê trong hóa đơn

7. Tìm kiếm danh sách hóa đơn

 Tìm kiếm hóa đơn có tổng tiền thấp nhất  Tìm kiếm hóa đơn có tổng tiền cao nhất

29

</div><span class="text_page_counter">Trang 30</span><div class="page_container" data-page="30">

 Tìm kiếm thơng tin hóa đơn theo số ngày th  Tìm kiếm thơng tin hóa đơn theo tên khách hàng

III. Ngăn xếp 1. Nhập danh sách

 Nhập danh sách ô tô

30

</div><span class="text_page_counter">Trang 31</span><div class="page_container" data-page="31">

 Nhập danh sách hóa đơn

2. Hiện danh sách  Hiện danh sách ô tô  Hiện danh sách Hóa đơn

31

</div><span class="text_page_counter">Trang 32</span><div class="page_container" data-page="32">

3. Xóa phần tử ở Stack  Xóa ơ tơ  Xóa hóa đơn

32

</div><span class="text_page_counter">Trang 33</span><div class="page_container" data-page="33">

4. Tổng tiền tất cả hóa đơn

 Áp dụng với tất cả hóa đơn trong Stack

33

</div><span class="text_page_counter">Trang 34</span><div class="page_container" data-page="34">

5. Sắp xếp danh sách

<i>1. Áp dụng cho danh sách hóa đơn</i>

34

</div><span class="text_page_counter">Trang 42</span><div class="page_container" data-page="42">

 Sắp xếp tăng dần thôi số ngày thuê xe ô tô

 Sắp xếp giảm dần theo số lượng xe th trong hóa đơn

7. Tìm kiếm hóa đơn

1. Áp dụng với danh sách hóa đơn  Tìm kiếm hóa đơn có tổng tiền thấp nhất

42

</div><span class="text_page_counter">Trang 43</span><div class="page_container" data-page="43">

 Tìm kiếm hóa đơn có tổng tiền cao nhất  Tìm kiếm thơng tin hóa đơn theo số ngày th  Tìm kiếm thơng tin hóa đơn theo tên khách hàng

D. Cài Đặt – Kiểm Thử

43

</div><span class="text_page_counter">Trang 44</span><div class="page_container" data-page="44">

1. Danh sách liên kết đơn  Chương trình tổng

 Danh sách ơ tơ

- Nhập và xuất danh sách ô tô (Bao gồm đọc file, lưu file)

- Thêm vào cuối danh sách ô tô

44

</div><span class="text_page_counter">Trang 45</span><div class="page_container" data-page="45">

- Xóa đầu danh sách ơ tơ

- Tìm mã ơ tơ

- Sắp xếp

45

</div><span class="text_page_counter">Trang 46</span><div class="page_container" data-page="46">

 Danh sách hóa đơn - Menu

- Nhập xuất (Bao gồm lưu file , đọc file)

46

</div><span class="text_page_counter">Trang 47</span><div class="page_container" data-page="47">

- Them hóa đơn vào cuối

47

</div><span class="text_page_counter">Trang 48</span><div class="page_container" data-page="48">

- Xóa đầu danh sách

- Tổng tiền tất cả hóa đơn

- Lọc hóa đơn

48

</div><span class="text_page_counter">Trang 49</span><div class="page_container" data-page="49">

- Sắp xếp theo số lượng xe giảm dần

49

</div><span class="text_page_counter">Trang 59</span><div class="page_container" data-page="59">

- Xóa đầu danh sách ơ tơ

- Tìm mã ô tô

- Sắp xếp

59

</div><span class="text_page_counter">Trang 60</span><div class="page_container" data-page="60">

 Danh sách hóa đơn - Menu

- Nhập xuất (Bao gồm lưu file , đọc file)

60

</div><span class="text_page_counter">Trang 61</span><div class="page_container" data-page="61">

- Them hóa đơn vào cuối

61

</div><span class="text_page_counter">Trang 62</span><div class="page_container" data-page="62">

- Xóa đầu danh sách

- Tổng tiền tất cả hóa đơn

- Lọc hóa đơn

62

</div><span class="text_page_counter">Trang 63</span><div class="page_container" data-page="63">

- Sắp xếp theo số lượng xe giảm dần

63

</div><span class="text_page_counter">Trang 64</span><div class="page_container" data-page="64">

- Tìm kiếm

64

</div><span class="text_page_counter">Trang 65</span><div class="page_container" data-page="65">

4. Hang đợi (Queue)  Chương trình tổng

 Danh sách ô tô

- Nhập và xuất danh sách ô tô (Bao gồm đọc file, lưu file)

- Thêm vào cuối danh sách ơ tơ

65

</div><span class="text_page_counter">Trang 66</span><div class="page_container" data-page="66">

- Xóa đầu danh sách ơ tơ

- Tìm mã ơ tơ

- Sắp xếp

66

</div><span class="text_page_counter">Trang 67</span><div class="page_container" data-page="67">

 Danh sách hóa đơn - Menu

- Nhập xuất (Bao gồm lưu file , đọc file)

67

</div><span class="text_page_counter">Trang 68</span><div class="page_container" data-page="68">

- Them hóa đơn vào cuối

68

</div><span class="text_page_counter">Trang 69</span><div class="page_container" data-page="69">

- Xóa đầu danh sách

- Tổng tiền tất cả hóa đơn

- Lọc hóa đơn

69

</div><span class="text_page_counter">Trang 70</span><div class="page_container" data-page="70">

- Sắp xếp theo số lượng xe giảm dần

70

</div><span class="text_page_counter">Trang 71</span><div class="page_container" data-page="71">

- Tìm kiếm

71

</div>