báo cáo bài tập lớn môn cấu trúc dữ liệu và giải thuật chủ đề image viewer using linked list

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 (2.96 MB, 22 trang )

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

<b>TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI </b>

BÁO CÁO BÀI TẬP LỚN MÔN CẤU TRÚCDỮ LIỆU VÀ GIẢI THUẬT

Chủ đề: “Image Viewer using linked list”

Giáo viên hướng dẫn: cô Trần Thị Thanh HảiDanh sách sinh viên nhóm 17:

1. Vũ Đăng Tuấn 202141332. Trần Minh Đức 202138893. Trần Hưng Sách 202140704. Nguyễn Trọng Hiếu 20200685

Mục Lục

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

<small>I. Giới thiệu...4</small>

<small>1.2. Định nghĩa bài toán...4</small>

<small>1.3. Bảng phân công nhiệm vụ...4</small>

<small>II. Phương pháp lựa chọn...5</small>

<small>2.4. Tìm kiếm Node trong danh sách...9</small>

<small>III. Triển khai cài đặt...9</small>

<small>1. Ngôn ngữ lập trình và thư viện...9</small>

<small>1.1. Ngơn ngữ lập trình C++ và các thư viện cơ bản...9</small>

<small>1.2. Thư viện openCV...10</small>

<small>2. Tổ chức chương trình...11</small>

<small>IV. Kết quả thực nghiệm...13</small>

<small>2. Kết quả thực nghiệm...15</small>

<small>2.7. Test chức năng ghi file khi đóng chương trình...19</small>

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

<small>Hình 3. Linked List...6</small>

<small>Hình 4. Khai báo 1 Linked List...6</small>

<small>Hình 5. Code duyệt danh sách...7</small>

<small>Hình 8. Xóa node bất kỳ khơng phải ở đầu...9</small>

<small>Hình 19. Thêm thất bại do tên ảnh sai hoặc khơng có ảnh đó trong file “img”...16</small>

<small>Hình 20. Thêm thất bại do ảnh đã tồn tại trong danh sách...16</small>

<small>Hình 21. Thêm thành cơng ảnh "messi.jpg"...16</small>

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

I. Giới thiệu

1.1. Lý do và động lực

Ngày nay con người có nhu cầu chụp ảnh rất nhiều , có những người trong bộ sưu tập có đến hàng trăm , hàng nghìn bức ảnh dẫn đến việc quản lý hay xem lại một ảnh nào đó rất khó khăn.Vì vậy nhóm em quyết định tạo ra ứng dụng Image Viewer giúp người dùng xem,thao tác và quản lý hình ảnh một cách dễ dàng hơn.

Ngồi ra tạo 1 Image Viewer sử dụng Linked List giúp người học xây dựng một ứng dụng thực tế , học cách áp dụng cấu trúc dữ liệu vào các ứng dụng thực tế và nâng cao kỹ năng lập trình.

1.2. Định nghĩa bài tốn

Bài tốn “Image Viewer using Linked List” là việc xây dựng trình xem ảnh sử dụng cấu trúc dữ liệu Linked List để quản lý danh sách các ảnh. Ứng dụng sẽ có các chức năng:

Hiển thị danh sách ảnhThêm ảnh

Xóa ảnh

Tìm ảnh có nhiều lượt xem nhấtTìm ảnh chụp cùng 1 địa điểmPhân bố ảnh chụp theo năm1.3. Bảng phân công nhiệm vụ

Phân công công việc theo thời gian :

Tuần 1 : Tìm hiểu chủ đề và lên kế hoạch giải quyết bài toán. Tuần 2 : Nghiên cứu và bắt đầu viết chương trình.

Tuần 3 : Hồn thiện chương trình và chạy thử.Tuần 4 : Tổng hợp kết quả và làm báo cáo.

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

II. Phương pháp lựa chọn

1. Danh sách liên kết đơn1.1. Con trỏ và struct

a. Con trỏ

Một con trỏ (pointer) là một biến dùng để lưu trữ <b>địa chỉ</b> của một biến khác. Biến khác ở đây có thể là một biến thông thường như biến số nguyên,biến số thực, hoặc có thể là một mảng, một hàm, và có khi cũng chính là một con trỏ khác. Vì con trỏ là một biến nên nó cũng cần phải được lưu trữ ở đâu đó trong bộ nhớ; có nghĩa là<small> bản thân biến con trỏ cũng có một địa bộ nhớ. Do đó, ta có thể dùng con trỏ đề lưu địa chỉ của một con trỏ </small>

Cú pháp khai báo con trỏ trong C, nói một cách đơn giản (nhưng khơng hồn tồn chính xác), gồm 3 phần: (i) kiểu của biến khác mà con trỏ lưu trữ địa chỉ, (2) dấu * và (3) tên của con trỏ. Con trỏ hàm thì khai báo hơi khác một chút, nhưng đây không phải vấn đề trọng tâm của bài viết. Ví dụ, khai báo một số con trỏ:

b. Struct

Struct cho phép chúng ta tập hợp một hoặc một vài kiểu dữ liêu khác nhau thành một kiểu dữ liệu mới. Các kiểu dữ liệu thành phần của một struct có thể là kiểu dữ liệu sẵn có như số nguyên, số thực, con trỏ, hoặc một kiểu struct đã định nghĩa trước đó.

Trong DSLK, struct được sử dụng để khai báo một “mắt xích” của danh sách. Ví dụ ta muốn khai báo một mắt xích của một danh sách liên kết các biến kiểu int thì ta có thể khai báo như sau:

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

<small> </small>1.3. Đặc điểm của danh sách liên kết đơn

Do danh sách liên kết đơn là một cấu trúc dữ liệu động, được tạo nên nhờ việc cấp phát động nên nó có một số đặc điểm sau đây:

Được cấp phát bộ nhớ khi chạy chương trìnhCó thể thay đổi kích thước qua việc thêm, xóa phần tửKích thước tối đa phụ thuộc vào bộ nhớ khả dụng của RAMCác phần tử được lưu trữ ngẫu nhiên (không liên tiếp) trong RAM

<small>Hinh 1. Linked List</small>

<small>Hinh 2. Khai báo 1 Linked List</small>

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

Và do tính liên kết của phần tử đầu và phần tử đứng sau nó trong danh sáchliên kết đơn, nó có các đặc điểm sau:

Chỉ cần nắm được phần tử đầu và cuối là có thể quản lý được danhsách

Truy cập tới phần tử ngẫu nhiên phải duyệt từ đầu đến vị trí đóChỉ có thể tìm kiếm tuyến tính một phần tử

2. Giải thuật2.1. Duyệt danh sách

Khởi tạo từ node “p” = head rồi theo con trỏ next đến khi bằng NULL thìdừng

<small>Hinh 3. Code duy t danh sáchệ</small>

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

2.2. Thêm 1 node vào đầu danh sách

Gán next của Node mới trỏ đến Node đầu (cũ): node->next = head;Cập nhập lại giá trị head: head = node;.

2.3. Xóa 1 node khỏi danh sách theo vị tría. Xóa ở đầu danh sách

<b>Bước 1:</b> Khai báo một con trỏ p để lưu lại địa chỉ của Node đầu tiên: Node* temp = head;

o Trường hợp ngoại lệ cần xử lý là nếu danh sách khơng có phần tử nào thì phải thốt trước khi thực hiện xóa.

<b>Bước 2:</b> cập nhập lại giá trị của head: head = head->next;

<b>Bước 3:</b> giải phóng vùng nhớ của Node cần xóa: delete temp;

<small>Hinh 5. Xóa Node đầầuở</small>

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

<small> </small>b. Xóa các node cịn lại

<b>Bước 1:</b> Khai báo một con trỏ p để lưu lại địa chỉ của Node đầu tiên: Node* temp = head;

<b>Bước 2: </b>Duyệt danh sách để tìm vị trí node cần xóa và node trước nó(prev)

<b>Bước 3:</b> cập nhập lại giá trị next của Node prev: prev->next = >next;

<b>temp-Bước 4:</b> giải phóng vùng nhớ của Node cần xóa: delete temp;

2.4. Tìm kiếm Node trong danh sáchTạo con trỏ temp trỏ đến node đầu.

Duyệt danh sách từ node đầu đến node cuối.nếu temp = node cần tìm thì dừng vịng lặp và trả về temp.

III. Triển khai cài đặt

1. Ngơn ngữ lập trình và thư viện

1.1. Ngơn ngữ lập trình C++ và các thư viện cơ bản

C++ là một ngơn ngũ lập trình đa năng , có cấp độ cao được phát triển bởi Bjarne Stroustrup vào năm 1983. Nó là một phần mở rộng của ngơn ngữ lập trình C và hỗ trợ các mơ hình lập trình hương đối tượng. C++ được sử dụng rộng rãi trong việc phất triển hệ điều hành, phần mềm hệ thống, trình

<small>Hinh 6. Xóa node bầất kỳ không ph i đầầuả ở</small>

<small>Hinh 7. Tim kiêấm Node</small>

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

điều khiển thiết bị , trò chơi video và các uwngs dụng đòi hỏi hiệu suất cao khác.

Các thư viện cần dùng trong bài :iostream: nhập xuất dữ liệu.string: xử lý chuỗi.

vector: lưu trữ thông tin 1 ảnh.

map: phân bố ảnh theo năm với “key=năm” và “value=mảng chứa các ảnh cùng năm đó”.

fstream : lấy dữ liệu ảnh.opencv2: hiển thị ảnh.1.2. Thư viện openCV

OpenCV là một thư viện mã nguồn mở để phất triển các ứng dụng thịgiác máy tính và xử lý ảnh. Thư viện này cung cấp nhiều hàm xử lý ảnhvà video , hỗ trỡ cho nhiều ngơn ngữ lập trình như C++,Python,Java vàC#.

OpenCV2 là phiên bản cũ của thư viện OpenCV, được phát hành năm2009.Các tính năng chính của openCV2 :

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

Img: chứa ảnh

<small>Hinh 8. Code hi n th nh bằầng opencvểị ả</small>

<small>Hinh 9. Th m c dataưụ</small>

<small>Hinh 10. Th m c imgưụ</small>

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

Header file: chứa các file header

struct Imagestring name - tên

string resolution - độ phân giảistring location - địa điểmstring date - thời gianint views - sô lượt xemImage() – hàm tạo rỗngImage(…) – hàm tạo có tham sốvoid showImage() – hàm hiển thị ảnhbool addImage() – hàm thêm ảnh

Struct nodeImage data – thông tin ảnh

node *next – con trỏ next

<small>Hinh 11. T o các th vi n cầần thiêấtạưệ</small>

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

node(Image img) – Hàm khởi tạo 1 node

class ImageViewer – tạo 1 linked list với các chức năng node *head – node đầu

int count – số lượng node

ImageViewer() – hàm khởi tạo rỗngvoid add(Image img) – thêm 1 node vào đầuvoid remove(int index) – xóa 1 node theo vị trí

vector<Image*> mostViews() – tìm ảnh nhiều views nhấtvector<Image*> find(string location) – tìm ảnh theo địa điểmmap<string,vector<Image*> > filter() – phân bố ảnh theo nămvector<Image*> listImg() – lấy tất cả ảnh bỏ vào mảng

Class MENU – xử lý các chức năngImageViewer iv – khai báo 1 Linked List

vector<Image*> readfile(string fileName) – lấy ảnh từ file txtMENU() – hàm tạo để thêm ảnh từ file “ListImg.txt” vào dsach~MENU() – hàm hủy để lưu thay đổi vào file “ListImg.txt” khi đóng chương trình.

void menu() – hàm menu

void print(vector<Image*> img) – in danh sách ảnh theo yêu cầuCác hàm thực hiện chức năng từ 1 đến 6

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

Source file: chứa file main.cpp đề chạy chương trình

IV. Kết quả thực nghiệm

1. Dữ liệu

Nhóm em đã sưu tầm được khoảng 50 bức ảnh của các cầu thủ bóng đá trên thếgiới.

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

18 garnacho.jpg 365dpi Argentina 12/01/2023

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

40 mitoma.jpeg 300dpi Nhat Ban 15/01/2018

45 bruno fernandes.jfif 300dpi Bo Dao Nha 15/04/2023

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

2. Kết quả thực nghiệm

2.1. Test Menu 1: Hiển thị danh sách ảnh

2.2. <small>Test Menu 2: Thêm nh ả</small>

<small>Hinh 12. Các nh có sằẵn trong th m c nhảư ụ ả</small>

<small>Hinh 13. File “Image.txt”</small>

<small>Hinh 14. File "ListImg.txt"</small>

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

2.3. Test Menu 3: Xóa ảnh

2.4. Test Menu 4: Tìm ảnh có lượt xem cao nhất

<small>Hinh 17. Thêm thầất b i do nh đã tôần t iạảạtrong danh sách</small>

<small>Hinh 20. Ch c nằng 3ứHinh 18. Thêm thầất b i do tên nh sai ho c khơng có nh đó trong fleạảặả</small>

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

Như đã xem ở trên thì ảnh “gavi” và “messi” được xem nhiều nhất với views là 1.

2.5. Test Menu 5: Tìm ảnh theo địa điểm

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

2.6. Test Menu 6: Phân bố ảnh theo năm

2.7. Test chức năng ghi file khi đóng chương trình

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

Xem ảnh và thơng tin ảnhThêm ,xóa ảnh

Tìm kiếm ảnhPhân bố ảnh theo năm2. Bài học rút ra

Bài toán "Image Viewer using Linked List" giúp chúng ta hiểu thêm về cách sử dụng cấu trúc dữ liệu Linked List để lưu trữ và quản lý dữ liệu. Bài toán này cũng giúp chúng ta học được cách triển khai các thao tác cơ bản trên danh sách như thêm, xóa, duyệt, tìm kiếm.

Ngồi ra, bài tốn cũng giúp chúng ta nhận thức được rằng việc lưu trữ và quản lý dữ liệu là một phần rất quan trọng trong lập trình. Nếu khơngcó cấu trúc dữ liệu phù hợp, việc thao tác trên dữ liệu sẽ trở nên khó khăn và tốn thời gian.

Cuối cùng, bài toán cũng giúp chúng ta rèn luyện kỹ năng lập trình và tưduy thuật tốn, từ đó giúp chúng ta trở nên thành thạo hơn trong lập trình và giải quyết các bài tốn khó hơn.

3. Những khó khắn khi học mơn học này

Mơn học Cấu trúc dữ liệu và Giải thuật có thể đòi hỏi nhiều nỗ lực và thời gian để học và làm quen với các khái niệm và phương pháp. Một số khó khăn cụ thể khi học mơn này có thể bao gồm:

Khái niệm phức tạp: Cấu trúc dữ liệu và giải thuật có nhiều khái niệm phức tạp và trừu tượng, nhưng lại là cơ sở cho nhiều ứng dụng và thuật toán phức tạp. Việc hiểu rõ các khái niệm này và ứng dụng chúng vào thực tế có thể địi hỏi nhiều thời gian và nỗ lực.

Nhiều thuật tốn và phương pháp: Có nhiều thuật toán và phương pháp khác nhau để giải quyết các bài toán sử dụng cấu trúc dữ liệu vàgiải thuật, việc hiểu và áp dụng chúng có thể khó khăn

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