bài tập lớn đề tài quản lý các số nguyên dùng dslk đôi

Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (4.59 MB, 14 trang )

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

<b>BỘ GIÁO DỤC VÀ ĐÀO TẠOTRƯỜNG ĐẠI HỌC CÔNG NGHỆ ĐÔNG Á</b>

<b>BÀI TẬP LỚN</b>

<b>HỌC PHẦN: CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬTĐỀ TÀI: QUẢN LÝ CÁC SỐ NGUN DÙNG DSLK ĐƠI</b>

<b><small>Sinh viên thực hiệnKhóaLớpMã sinh viên</small></b>

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

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

<b>MỤC LỤC:</b>

- Cấu trúc của một Node...4

- Cấu trúc danh sách liên kết đôi...6

<b>III. Các thao tác trong danh sách liên kết đôi...6</b>

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

<b>DANH MỤC BẢNG BIỂU, HÌNH VẼ:</b>

Hình 1.1 Ví dụ về danh sách liên kết đơi...5

Hình 2.1 Cấu trúc của một node...5

Hình 2.2 Xây dựng danh sách liên kết kép...6

Hình 2.3 Cấu trúc danh sách liên kết đơi...6

Hình 3.1 Chèn vào đầu List...7

Hình 3.2 Chèn vào cuối List...8

Hình 3.3 Xuất thơng tin ra màn hình...8

Hình 4.1 Sơ đồ nhập vào chuỗi a...9

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

- Danh sách liên kết đôi (<b>Doubly linked list</b>) là danh sách liên kết mà mỗi phần tử có hai liên kết đến phần tử liền trước và liền sau nó.

- Khi duyệt các nút sẽ thực hiện theo hai chiều về trước và về sau thay vì thực hiền duyệt một chiều như danh sách liên kết đơn.

Hình 1.1 Ví dụ về danh sách liên kết đôi

- Cấu trúc của một Node:

Mô Ut node trong danh sách liên kết kép đươꄣc cấu thành tư뀀 ba thành phần là dư뀃 liê Uu và phần kết nối tới node kế tiếp và node trước nó.

Hình 2.1 Cấu trúc của một node Trong đó:

o Data: Là giá trị của Node o Prev: Là con trỏ tới node trước o Next: Là con trỏ tới node kế tiếp

Xây dựng danh sách liên kết kép bởi liên kết các node với nhau.

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

Hình 2.2 Xây dựng danh sách liên kết kép - Cấu trúc danh sách liên kết đơi:

Hình 2.3 Cấu trúc danh sách liên kết đôi

<b>III. Các thao tác trong danh sách liên kết đôi</b>

Trong danh sách liên kết đôi cũng có các thao tác tương tự như danh sách liên kết đơn, các thao tác này đươꄣc sử dụng rất nhiều khi làm việc với DSLK.

Tạo Node mới trong DSLK đơi Chèn Node trong DSLK đơi Xóa Node trong DSLK đơi Duyệt DSLK đơi

Tìm kiếm và sắp xếp trong DSLK đôi

Chèn Node trong danh sách liên kết đôi có hai trường hơꄣp là: chèn vào đầu, chèn vào cuối.

Xóa Node trong danh sách liên kết đơi cũng có hai trường hơꄣp là: xóa ở đầu và xóa ở cuối.

Việc chèn dư뀃 liệu vào đầu trong danh sách liên kết kép:

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

Hình 3.1 Chèn vào đầu List • Nếu head = NULL, ta sẽ cho cả head và tail = newNode.

• Nếu head != NULL, ta sẽ cập nhật lại head mới là newNode. Ta cần tạo liên kết giư뀃a head hiện tại với newNode trước khi cho newNode làm head mới. Việc chèn dư뀃 liệu vào cuối trong danh sách liên kết kép:

Hình 3.2 Chèn vào cuối List • Nếu head = NULL, newNode sẽ là head và tail ln

• Nếu head != NULL, cập nhật lại tail mới là newNode. Ta cần tạo liên kết thằng tail hiện tại với newNode trước khi để newNode làm tail mới.

Duyệt danh sách liên kết:

Hình 3.3 Xuất thơng tin ra màn hình

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

• Ta sẽ duyệt bắt đầu tư뀀 Node head cho tới trước khi gặp Node NULL bằng cách dùng con trỏ next.

<b>IV. Bài toán </b>

Cho một danh sách lưu trư뀃 các số nguyên. Viết chương trình tạo menu thực hiện các chức năng 1,2,3.

1. Khởi tạo danh sách, quá trình nhập sẽ dư뀀ng lại khi nhấn # 2. Nhập vào một số k, đếm các số = k, thông báo số lươꄣng số đếm đươꄣc là

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

Hình 4.3 Khởi tạo Kết quả:

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

Hình 4.4 Kết quả câu 1 - Yêu cầu 2:

Sơ đồ:

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

Hình 4.5 Sơ đồ câu 2 Code:

Hình 4.6 Nhập vào số đếm k, số đó là chẵn hay lẻ Kết quả:

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

Hình 4.9 Tính trung bình cộng các số lẻ dương Kết quả:

Hình 4.10 Kết quả câu 3 - Tạo Menu:

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

Hình 4.11 Tạo Menu

Hình 4.12 Tạo Menu

</div>