The project final report doubly linked list by c

Báo cáo cuối kỳ dự án: Danh sách liên kết đôi bằng C. Tìm hiểu cách triển khai và sử dụng danh sách liên kết đôi trong C. Code mẫu, giải thích chi tiết và ứng dụng thực tế.

• Tác giả: Nguyen Thi Phu
• Người hướng dẫn: Phd. Le Van Vinh
• Trường học: Trường Đại Học Sư Phạm Kĩ Thuật Tp. Hồ Chí Minh
• Chuyên ngành: Công Nghệ Thông Tin
• Đề tài: Doubly Linked List By C++
• Loại tài liệu: Project Final Report
• Năm xuất bản: 2022
• Địa điểm: Tp. Hồ Chí Minh

Tóm tắt

I. Hướng dẫn toàn diện đồ án danh sách liên kết đôi bằng C

Bài viết này cung cấp một phân tích chi tiết và hướng dẫn toàn diện về đồ án môn học liên quan đến chủ đề cài đặt danh sách liên kết đôi bằng ngôn ngữ lập trình C. Đây là một chủ đề cốt lõi trong môn cấu trúc dữ liệu và giải thuật, đóng vai trò nền tảng cho nhiều ứng dụng phức tạp sau này. Báo cáo tập trung vào việc hiện thực hóa các khái niệm lý thuyết thành một sản phẩm cụ thể, với đầy đủ source code C và các giải thích chi tiết. Mục tiêu chính là xây dựng một cấu trúc dữ liệu linh hoạt, cho phép thực hiện các thao tác thêm, xóa, sửa, và tìm kiếm dữ liệu một cách hiệu quả. Không giống như mảng tĩnh, danh sách liên kết đôi cung cấp khả năng cấp phát động, giúp quản lý bộ nhớ tối ưu hơn, đặc biệt khi số lượng phần tử không xác định trước. Trong khuôn khổ của một báo cáo cuối kỳ, việc trình bày rõ ràng từ cấu trúc của một node, cách sử dụng con trỏ trong C để liên kết các node, cho đến việc triển khai các hàm xử lý là vô cùng quan trọng. Tài liệu này sẽ đi sâu vào từng khía cạnh, từ việc định nghĩa struct trong C cho node và danh sách, đến việc quản lý con trỏ pHead và pTail. Mỗi hàm chức năng sẽ được phân tích về mặt logic, mã nguồn tham khảo và độ phức tạp thuật toán, giúp người đọc không chỉ sao chép mã mà còn hiểu sâu sắc bản chất vấn đề. Các ví dụ minh họa sẽ tập trung vào các bài toán quản lý quen thuộc như quản lý sinh viên hoặc quản lý thư viện sách, làm nổi bật tính ứng dụng thực tiễn của cấu trúc dữ liệu này.

1.1. Tổng quan về cấu trúc dữ liệu và giải thuật trong đồ án

Trong lĩnh vực khoa học máy tính, cấu trúc dữ liệu và giải thuật là hai khái niệm không thể tách rời. Một cấu trúc dữ liệu hiệu quả là tiền đề cho một giải thuật tối ưu. Đồ án môn học này tập trung vào danh sách liên kết đôi, một cấu trúc dữ liệu động tuyến tính. Mỗi phần tử, hay còn gọi là node, không chỉ lưu trữ dữ liệu mà còn chứa hai con trỏ: một con trỏ (pNext) trỏ đến phần tử kế tiếp và một con trỏ (pPrev) trỏ đến phần tử đứng trước nó. Sự tồn tại của con trỏ pPrev chính là điểm khác biệt cơ bản, tạo ra ưu thế vượt trội so với danh sách liên kết đơn. Cấu trúc này cho phép thao tác duyệt danh sách theo cả hai chiều (xuôi và ngược) một cách dễ dàng, đồng thời tối ưu hóa các thao tác xóa một node bất kỳ mà không cần duyệt từ đầu. Việc hiểu rõ bản chất này là bước đầu tiên và quan trọng nhất để hoàn thành tốt báo cáo cuối kỳ.

1.2. So sánh danh sách liên kết đôi và danh sách liên kết đơn

Sự khác biệt chính giữa danh sách liên kết đôi và danh sách liên kết đơn nằm ở cấu trúc của mỗi node. Trong danh sách liên kết đơn, mỗi node chỉ có một con trỏ next để trỏ tới node sau nó. Điều này làm cho việc duyệt danh sách chỉ có thể diễn ra theo một chiều. Ngược lại, danh sách liên kết đôi trang bị thêm con trỏ prev, cho phép duyệt ngược từ cuối về đầu. Ưu điểm này đặc biệt hữu ích trong các thuật toán yêu cầu truy cập phần tử lân cận phía trước, ví dụ như thao tác xóa một node. Với danh sách liên kết đơn, để xóa node p, cần phải tìm được node đứng ngay trước nó, một thao tác có độ phức tạp thuật toán là O(n). Trong khi đó, với danh sách liên kết đôi, thao tác này chỉ mất O(1) nếu đã có con trỏ đến node p. Tuy nhiên, nhược điểm của danh sách liên kết đôi là tốn thêm bộ nhớ cho con trỏ prev và các thao tác chèn, xóa cần phải cập nhật nhiều con trỏ hơn.

II. Bí quyết làm chủ con trỏ và cấp phát bộ nhớ động trong C

Một trong những thách thức lớn nhất khi làm việc với danh sách liên kết trong C chính là quản lý bộ nhớ và con trỏ trong C. Không giống các ngôn ngữ bậc cao có cơ chế thu gom rác tự động, C đòi hỏi lập trình viên phải tự quản lý việc cấp phát và giải phóng bộ nhớ. Đây là kỹ năng then chốt để xây dựng một chương trình ổn định và tránh các lỗi rò rỉ bộ nhớ (memory leak). Trọng tâm của phần này là việc sử dụng các hàm cấp phát động như malloc và free trong C. Khi một node mới cần được thêm vào danh sách, hàm malloc sẽ được gọi để yêu cầu một vùng nhớ mới từ heap. Vùng nhớ này sau đó được ép kiểu thành một con trỏ tới struct trong C đã định nghĩa cho node. Ngược lại, khi một node bị xóa, hàm free phải được gọi để trả lại vùng nhớ đó cho hệ thống. Việc quên gọi free sẽ dẫn đến rò rỉ bộ nhớ, làm chương trình tiêu tốn tài nguyên một cách không cần thiết. Tài liệu gốc "The project final report" minh họa việc tạo node mới bằng hàm createNode, trong đó sử dụng new (của C++), nhưng trong C, chúng ta sẽ thay thế bằng malloc. Việc hiểu rõ vòng đời của một đối tượng được cấp phát động, từ lúc được tạo ra cho đến lúc bị hủy, là nền tảng để triển khai thành công đồ án môn học về danh sách liên kết đôi.

2.1. Khai báo cấu trúc Node và danh sách bằng struct trong C

Để bắt đầu cài đặt danh sách liên kết đôi, bước đầu tiên là định nghĩa cấu trúc dữ liệu cho một node và cho chính danh sách đó. Ngôn ngữ C cung cấp từ khóa struct để thực hiện việc này. Một node tiêu biểu sẽ được định nghĩa bao gồm ba thành phần chính: một trường để lưu dữ liệu (ví dụ: COFFEE data), một con trỏ pNext để trỏ tới node kế tiếp, và một con trỏ pPrev để trỏ tới node phía trước. Cấu trúc của danh sách (DoublyLinkedList) sẽ chứa hai con trỏ quan trọng là pHead (trỏ tới node đầu tiên) và pTail (trỏ tới node cuối cùng). Việc sử dụng pHead, pTail, pNext, pPrev giúp quản lý và thực hiện các thao tác trên danh sách một cách logic và hiệu quả. Ví dụ, pHead cho phép truy cập danh sách từ đầu, trong khi pTail giúp thao tác thêm vào cuối danh sách nhanh chóng với độ phức tạp O(1).

2.2. Quản lý bộ nhớ với malloc và free trong C cho các node

Quản lý bộ nhớ là một khía cạnh quan trọng trong lập trình C, đặc biệt với các cấu trúc dữ liệu động. Hàm malloc và free trong C là cặp công cụ chính để thực hiện cấp phát động. Khi cần tạo một node mới, hàm malloc(sizeof(NODE)) được sử dụng để xin cấp phát một vùng nhớ có kích thước bằng một NODE. Hàm này trả về một con trỏ kiểu void*, cần được ép kiểu tường minh về NODE*. Sau khi cấp phát thành công, dữ liệu và các con trỏ pNext, pPrev của node mới sẽ được khởi tạo. Ngược lại, khi một node không còn được sử dụng (ví dụ sau khi thực hiện thao tác xóa), việc gọi hàm free() với tham số là con trỏ tới node đó là bắt buộc. Thao tác này giải phóng vùng nhớ mà node đang chiếm giữ, trả lại cho hệ thống để tái sử dụng, từ đó ngăn chặn hiện tượng rò rỉ bộ nhớ (memory leak).

III. Phương pháp cài đặt các hàm thêm và xóa node hiệu quả

Trái tim của một đồ án danh sách liên kết đôi nằm ở việc cài đặt chính xác và hiệu quả các hàm thao tác cơ bản, đặc biệt là thêm node vào danh sách và xóa node khỏi danh sách. Các thao tác này đòi hỏi sự cẩn thận trong việc cập nhật các con trỏ trong C. Một sai sót nhỏ trong việc gán lại con trỏ pNext hoặc pPrev có thể phá vỡ toàn bộ cấu trúc liên kết của danh sách, dẫn đến mất dữ liệu hoặc lỗi chương trình. Báo cáo này sẽ trình bày chi tiết các trường hợp cần xử lý khi thêm một node: thêm vào đầu danh sách, thêm vào cuối danh sách và thêm vào một vị trí bất kỳ. Tương tự, thao tác xóa cũng được chia thành các trường hợp: xóa node đầu, xóa node cuối và xóa node ở vị trí k. Đối với mỗi thao tác, việc kiểm tra các trường hợp đặc biệt như danh sách rỗng, danh sách chỉ có một phần tử là cực kỳ quan trọng. Dựa trên tài liệu gốc, các hàm như addFirst, addLast, removeFirst, removeLast được mô tả rõ ràng. Ví dụ, khi thêm một node vào đầu danh sách rỗng, cả pHead và pTail đều phải trỏ tới node mới này. Khi xóa node cuối cùng, pHead và pTail phải được cập nhật về NULL. Việc phân tích kỹ lưỡng các trường hợp này đảm bảo mã nguồn hoạt động đúng đắn trong mọi tình huống.

3.1. Chi tiết các bước thêm node vào danh sách liên kết đôi

Thao tác thêm node vào danh sách liên kết đôi cần xử lý cẩn thận các liên kết. Có ba kịch bản chính: thêm vào đầu, thêm vào cuối và thêm vào vị trí k. Khi thêm vào đầu (addFirst), node mới tmp sẽ có pNext trỏ tới pHead cũ. Con trỏ pPrev của pHead cũ phải được cập nhật để trỏ tới tmp. Cuối cùng, pHead của danh sách được cập nhật thành tmp. Khi thêm vào cuối (addLast), pTail cũ sẽ có pNext trỏ tới tmp, và pPrev của tmp sẽ trỏ tới pTail cũ. Sau đó, pTail của danh sách được cập nhật thành tmp. Trường hợp danh sách rỗng là một ngoại lệ cần xử lý riêng, khi đó cả pHead và pTail đều sẽ trỏ tới node mới. Việc cập nhật chính xác các con trỏ pNext, pPrev là yếu tố quyết định sự thành công của thao tác.

3.2. Kỹ thuật xóa node khỏi danh sách và giải phóng bộ nhớ

Việc xóa node khỏi danh sách là một quy trình đòi hỏi độ chính xác cao để duy trì tính toàn vẹn của cấu trúc. Để xóa một node p, cần phải nối lại node đứng trước nó (p->pPrev) với node đứng sau nó (p->pNext). Cụ thể, p->pPrev->pNext sẽ được gán bằng p->pNext, và p->pNext->pPrev sẽ được gán bằng p->pPrev. Sau khi các liên kết đã được cập nhật để "bỏ qua" node p, bước cuối cùng và quan trọng nhất là giải phóng vùng nhớ mà node p đang chiếm giữ bằng hàm free(p). Cần đặc biệt chú ý đến các trường hợp biên như xóa node đầu tiên (p == pHead), xóa node cuối cùng (p == pTail), hoặc khi danh sách chỉ còn một node duy nhất. Bỏ qua việc giải phóng bộ nhớ sẽ gây ra rò rỉ, một lỗi nghiêm trọng trong các ứng dụng chạy dài hạn.

IV. Cách duyệt tìm kiếm và sắp xếp danh sách liên kết đôi

Sau khi đã xây dựng được các thao tác cơ bản, báo cáo cuối kỳ cần đề cập đến các chức năng nâng cao hơn như duyệt danh sách liên kết, tìm kiếm trong danh sách liên kết và sắp xếp. Duyệt danh sách là thao tác cơ bản nhất, thường được thực hiện bằng một vòng lặp for hoặc while, bắt đầu từ pHead và di chuyển qua từng node bằng con trỏ pNext cho đến khi gặp NULL. Nhờ có con trỏ pPrev, việc duyệt ngược từ pTail cũng có thể được thực hiện một cách tương tự. Tìm kiếm một phần tử trong danh sách thường là tìm kiếm tuần tự: duyệt qua từng node và so sánh dữ liệu của node đó với giá trị cần tìm. Thao tác này có độ phức tạp thuật toán là O(n) trong trường hợp xấu nhất. Phần thú vị và thách thức hơn là sắp xếp. Tài liệu gốc đề cập đến hai thuật toán là Selection Sort và Quick Sort. Việc áp dụng các thuật toán này trên danh sách liên kết có sự khác biệt so với trên mảng, vì không thể truy cập phần tử bằng chỉ số một cách trực tiếp. Ví dụ, Quick Sort trên danh sách liên kết đòi hỏi kỹ thuật phân hoạch (partition) thông minh mà không cần truy cập ngẫu nhiên. Phân tích và cài đặt các thuật toán này sẽ là một điểm cộng lớn cho đồ án môn học.

4.1. Tối ưu thuật toán duyệt và tìm kiếm trong danh sách

Thao tác duyệt danh sách liên kết là nền tảng cho nhiều chức năng khác. Một vòng lặp đơn giản bắt đầu từ pHead, di chuyển con trỏ tạm p theo liên kết p->pNext cho đến khi p bằng NULL là cách tiếp cận phổ biến nhất. Đối với tìm kiếm trong danh sách liên kết, phương pháp tìm kiếm tuần tự (linear search) được áp dụng. Giải thuật sẽ duyệt qua danh sách từ đầu, tại mỗi node, nó so sánh dữ liệu với khóa tìm kiếm. Nếu tìm thấy, hàm sẽ trả về con trỏ tới node đó; nếu không, sau khi duyệt hết danh sách, nó sẽ trả về NULL. Mặc dù đơn giản, hiệu năng của tìm kiếm tuần tự không cao, với Big O Notation là O(n). Trong một số trường hợp, nếu danh sách được duy trì ở trạng thái đã sắp xếp, có thể áp dụng các kỹ thuật tìm kiếm hiệu quả hơn, nhưng điều này làm tăng độ phức tạp cho các thao tác chèn và xóa.

4.2. Phân tích thuật toán sắp xếp Selection Sort và Quick Sort

Sắp xếp một danh sách liên kết là một bài toán kinh điển. Selection Sort hoạt động bằng cách lặp đi lặp lại việc tìm phần tử nhỏ nhất (hoặc lớn nhất) từ phần chưa được sắp xếp và chuyển nó vào danh sách đã sắp xếp. Quick Sort lại hoạt động dựa trên nguyên tắc chia để trị. Một phần tử được chọn làm "pivot", danh sách sau đó được phân hoạch thành hai danh sách con: một chứa các phần tử nhỏ hơn pivot và một chứa các phần tử lớn hơn. Quá trình này được lặp lại đệ quy trên hai danh sách con. Việc cài đặt Quick Sort cho danh sách liên kết đôi phức tạp hơn so với mảng vì không thể hoán vị các phần tử một cách trực tiếp. Thay vào đó, cần phải thao tác trên các con trỏ để thay đổi vị trí của các node. Phân tích độ phức tạp thuật toán của hai giải thuật này là một phần quan trọng trong báo cáo cuối kỳ.

V. Top ứng dụng thực tiễn của danh sách liên kết đôi trong C

Lý thuyết về danh sách liên kết đôi sẽ trở nên ý nghĩa hơn khi được áp dụng vào các bài toán thực tế. Cấu trúc này được sử dụng rộng rãi trong nhiều lĩnh vực của công nghệ phần mềm. Một trong những ứng dụng phổ biến nhất là việc triển khai các cấu trúc dữ liệu khác như Stack, Queue, hoặc Deque. Ví dụ, một Deque (hàng đợi hai đầu) có thể được cài đặt rất hiệu quả bằng danh sách liên kết đôi, cho phép thêm và xóa phần tử ở cả hai đầu với độ phức tạp O(1). Trong các trình duyệt web, lịch sử duyệt web (nút back và forward) là một ví dụ điển hình của việc sử dụng danh sách liên kết đôi. Mỗi trang web đã truy cập là một node, cho phép người dùng di chuyển tới lui một cách dễ dàng. Một ứng dụng khác là trong các trình soạn thảo văn bản, chức năng undo/redo có thể được xây dựng dựa trên danh sách liên kết đôi để lưu trữ các trạng thái thay đổi của tài liệu. Trong khuôn khổ đồ án môn học, một bài toán quen thuộc là xây dựng chương trình quản lý sinh viên bằng dslkđ hoặc quản lý thư viện bằng dslkđ. Các chương trình này cho phép thực hiện các thao tác CRUD (Create, Read, Update, Delete) trên một danh sách đối tượng, minh họa rõ ràng sức mạnh và tính linh hoạt của danh sách liên kết đôi.

5.1. Xây dựng hệ thống quản lý sinh viên bằng dslkđ

Một ứng dụng thực tiễn phổ biến cho đồ án môn học là hệ thống quản lý sinh viên bằng dslkđ (danh sách liên kết đôi). Trong hệ thống này, mỗi sinh viên được biểu diễn bằng một node trong danh sách. Dữ liệu của node (sử dụng struct trong C) sẽ chứa các thông tin như mã số sinh viên, họ tên, ngày sinh, điểm trung bình. Việc sử dụng danh sách liên kết đôi cho phép thêm sinh viên mới, xóa sinh viên đã ra trường, cập nhật thông tin, hoặc tìm kiếm sinh viên theo mã số một cách linh hoạt mà không bị giới hạn về số lượng như khi dùng mảng. Các chức năng nâng cao như sắp xếp danh sách sinh viên theo tên hoặc điểm trung bình cũng có thể được cài đặt, minh họa rõ ràng khả năng của cấu trúc dữ liệu này.

5.2. Phân tích source code C mẫu cho báo cáo cuối kỳ

Để hoàn thành tốt báo cáo cuối kỳ, việc tham khảo và phân tích một source code C mẫu là rất hữu ích. Một mã nguồn tốt không chỉ chạy đúng mà còn phải được tổ chức rõ ràng, có chú thích đầy đủ và tuân thủ các quy tắc lập trình tốt. Phân tích mã nguồn mẫu giúp sinh viên hiểu cách các hàm như createNode, addFirst, removeNode được kết nối với nhau để tạo thành một hệ thống hoàn chỉnh. Chú ý đến cách quản lý con trỏ trong C, cách xử lý các trường hợp đặc biệt (danh sách rỗng, một phần tử), và cách giải phóng bộ nhớ bằng malloc và free trong C. Việc hiểu và có thể giải thích từng dòng lệnh trong source code C sẽ chứng tỏ sự nắm vững kiến thức và là yếu tố quan trọng để đạt điểm cao.

VI. Đánh giá độ phức tạp thuật toán và hướng phát triển

Phần cuối cùng của một báo cáo cuối kỳ chất lượng là đánh giá về hiệu năng và đề xuất các hướng phát triển trong tương lai. Hiệu năng của các thao tác trên danh sách liên kết đôi được đo lường bằng độ phức tạp thuật toán, thường được biểu diễn qua ký hiệu Big O Notation. Ví dụ, các thao tác truy cập phần tử đầu/cuối, thêm/xóa ở đầu/cuối danh sách có độ phức tạp là O(1), rất hiệu quả. Tuy nhiên, việc truy cập hoặc tìm kiếm một phần tử ở vị trí bất kỳ lại có độ phức tạp là O(n), vì đòi hỏi phải duyệt qua một phần hoặc toàn bộ danh sách. Các thuật toán sắp xếp như Selection Sort có độ phức tạp O(n^2), trong khi Quick Sort có độ phức tạp trung bình là O(n log n). Việc phân tích và trình bày các kết quả này cho thấy sự hiểu biết sâu sắc về cấu trúc dữ liệu và giải thuật. Về hướng phát triển, đồ án có thể được mở rộng bằng cách cài đặt các loại danh sách liên kết khác như danh sách liên kết vòng, hoặc áp dụng danh sách liên kết đôi để xây dựng các cấu trúc phức tạp hơn như cây nhị phân tìm kiếm hoặc bảng băm. Một hướng khác là tối ưu hóa việc quản lý bộ nhớ hoặc tích hợp giao diện người dùng đồ họa để chương trình trở nên thân thiện hơn.

6.1. Phân tích Big O Notation cho các thao tác cơ bản

Đánh giá hiệu suất của các thuật toán là một phần không thể thiếu. Big O Notation là công cụ tiêu chuẩn để mô tả độ phức tạp thuật toán trong trường hợp xấu nhất. Đối với danh sách liên kết đôi, các thao tác cơ bản có độ phức tạp như sau: Truy cập phần tử đầu/cuối (O(1)), thêm node vào danh sách ở đầu/cuối (O(1)), xóa node khỏi danh sách ở đầu/cuối (O(1)). Các thao tác này rất nhanh vì chúng chỉ yêu cầu cập nhật một vài con trỏ thông qua pHead và pTail. Ngược lại, việc truy cập, tìm kiếm, thêm hoặc xóa một node tại vị trí thứ k yêu cầu phải duyệt từ đầu danh sách, do đó có độ phức tạp là O(n). Hiểu rõ những đặc điểm này giúp lập trình viên lựa chọn đúng cấu trúc dữ liệu cho bài toán cụ thể.

6.2. Triển vọng và cải tiến cho đồ án môn học tương lai

Một đồ án môn học về danh sách liên kết đôi có thể được mở rộng và cải tiến theo nhiều hướng. Một hướng đi tự nhiên là chuyển đổi danh sách liên kết đôi thành danh sách liên kết vòng đôi, nơi con trỏ pNext của pTail trỏ về pHead và pPrev của pHead trỏ về pTail. Cấu trúc này hữu ích trong các ứng dụng cần duyệt vòng lặp liên tục. Một cải tiến khác là tạo ra một phiên bản generic của danh sách liên kết, có thể lưu trữ bất kỳ kiểu dữ liệu nào bằng cách sử dụng con trỏ void* và các hàm callback. Về mặt ứng dụng, đồ án có thể được phát triển thành một thư viện cấu trúc dữ liệu và giải thuật hoàn chỉnh, hoặc tích hợp vào một dự án lớn hơn, ví dụ như một trò chơi đơn giản hoặc một hệ thống quản lý phức tạp hơn.

Trích đoạn nội dung tài liệu

BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC SƯ PHẠM KĨ THUẬT TP. HỒ CHÍ MINH KHOA CÔNG NGHỆ THÔNG TIN  ********* ********* THE PROJECT FINAL REPORT INSTRUCTOR : PhD. LE VAN VINH SUBJECT CODE : DASA230179_22_1_10 STUDENT : NGUYEN THI PHU STUDENT ID : 21110600 TP. HỒ CHÍ MINH - THÁNG 12 NĂM 2022 Name ID Task Completion rate 1.

Install Doubly Linked List, Queue Structure, Hash Tableand their fucntions. Nguyen Thi Phu 21110600 2. Install Grapical User 100% Interface (Winform). Edit and check the program.

Le Van Vinh I.1 : DOUBLY LINKED LIST BY C++ : − A Linked List is a list which includes one or many NODE, we define a NODE has at least two elements : <data_type> data and NODE next. We use the element data to store the users’ data, and the element next to link to the others. We use NODE head and NODE tail to manage our linked list easily. − A Doubly Linked List contains an extra pointer : NODE previous, typically called the previous pointer, together with the next pointer and data which are there in the Singly Linked List.

− Installing by C++ language programming “struct” data type for the COFFEE products : struct COFFEE { string name; double cafein; int count; long sourcecost; long salecost; }; struct NODE { COFFEE data; NODE* prev; NODE* next; }; struct DoublyLinkedList { NODE* Head; NODE* Tail; }; − Then we will install The Doubly Linked List’s functions : 1. Initializing the Doubly Linked List : − By assigning NODE Head and NODE Tail equals NULL, we have finished the initialization. void initList(DoublyLinkedList& myList) { myList.Head = NULL; myList. Creating new NODE : NODE* createNode(COFFEE X) { NODE* tmp = new NODE(); tmp->data = X; tmp->prev = NULL; tmp->next = NULL; return tmp; } 3.

Checking the list whether it is full or empty : bool isEmpty(DoublyLinkedList myList) { return myList.Head == NULL; } bool isFull(DoublyLinkedList myList) { NODE* tmp = new NODE(); return tmp == NULL; } 4. Showing the data of the list : − By traversing the linked list, we have the value of it. We traverse from the first NODE (NODE Head) to the last NODE (NODE Tail) and get the data we want to show. void showList(DoublyLinkedList myList) { int i = 0; for (NODE* p = myList.Head; p != NULL; p = p->next) { cout << "THE COFFEE [" << i << "]" << endl; i++; showANode(p); cout << endl; } } − If we want to show a list, firstly we must have a function which shows the value or the data of a NODE.

By doing that, our code is obvious and logical. void showANode(NODE* X) { cout << "The coffee name : " << X->data.name << endl; cout << "The concentration : " << X->data.cafein << " %" << endl; cout << "The amount : " << X->data.count << endl; cout << "The orginal : " << X->data.sourcecost << " VND" << endl; cout << "The agio : " << X->data.salecost << " VND" << endl; } 5. Insertion in Doubly Linked List : ❑ At the front of the Doubly Linked List : void addFirst(DoublyLinkedList& myList, COFFEE X) { NODE* tmp = createNode(X); if (isEmpty(myList)) myList.Tail = tmp; else { tmp->next = myList.Head->prev = tmp; myList.Head = tmp; } } ❑ At the end of the Doubly Linked List : void addLast(DoublyLinkedList& myList, COFFEE X) { NODE* tmp = createNode(X); if (isEmpty(myList)) myList.Tail = tmp; else { myList.Tail->next = tmp; tmp->prev = myList.Tail = tmp; } } ❑ At the position of the Doubly Linked List : void addPosition(DoublyLinkedList& myList, int k, COFFEE X) { NODE* tmp = createNode(X); if (isEmpty(myList)) myList.Tail = tmp; else { if (myList.Tail) addLast(myList, X); else { NODE* p = myList.Head; for (int i = 1; i < k; i++) p = p->next; p->next->prev = tmp; tmp->next = p->next; p->next = tmp; p = tmp->prev; } } } 6. Removing an element out of the list : ❑ At the front of the Doubly Linked List : void removeFisrt(DoublyLinkedList& myList) { if (isEmpty(myList)) return; else { NODE* tmp = myList.Head; if (myList.Tail = NULL; else { myList.Head->next; myList.Head->next->prev = NULL; } delete tmp; } } ❑ At the end of the Doubly Linked List : void removeLast(DoublyLinkedList& myList) { if (isEmpty(myList)) return; else { if (myList.Tail = NULL; else { NODE* tmp = myList.Tail->prev; myList.Tail->next = NULL; delete tmp; } } } ❑ At the position of the Doubly Linked List : void removePosition(DoublyLinkedList& myList, int k) { if (isEmpty(myList)) return; else { NODE* p = myList.Head; for (int i = 0; i < k; i++) p = p->next; NODE* tmp = p; p->prev->next = p->next; p->next->prev = p->prev; delete tmp; } } ❑ The NODE chosen : − We make full use of the remove at the front of the list and remove at the end of the list to install this function.

If the NODE chosen is the first NODE of the Doubly Linked List we utilise removeFirst function, in case of it is the last NODE of the Doubly Linked List we can use removeLast function. When the NODE isn’t drop in 2 cases mentioned we will install as the diagram : void removeNode(DoublyLinkedList& myList, NODE* p) { if (p == myList.Head) removeFirst(myList); else { if (p == myList.Tail) removeLast(myList); else { NODE tmp = myList.Head; while(tmp->next!=NULL&&tmp.data!=p->data) tmp=tmp->next; tmp->prev->next = tmp->next; tmp->next->prev = tmp->prev; tmp = NULL; delete tmp; } } } 7. Working with File handling : − We have a file “COFFEE.txt”, and then we transfer the data from it to the Doubly Linked List through some procedures : + Step 1 : Read file. + Step 2 : Define the structure of the file.

An element is defined by 5 atributtes : name, cafein, count, original cost and salecost. + Step 3 : Use the addLast(DoublyLinkedList& myList) function to insert an element respectively.9 20 32000 62000 void readFile(DoublyLinkedList& myList) { ifstream input; input.txt"); if (input) { while (!input.eof()) { COFFEE X; input >> X.salecost; addLast(myList, X); } input. Searching by name of the Coffee product : − By traversing the Doubly Linked List from the first NODE to the last NODE, if the program find the name of the Coffee we want to search, it return its data, In case of not being found, it returns the NULL value. NODE* searchByName(DoublyLinkedList myList, string s) { for (NODE* p = myList.Head; p != NULL; p = p->next) if (s == p->data.name) return p; return NULL; } 9.

Seaching the List of low cost : − We use the addLast() method to add an new item with satisfied requirement. In this case, if the cost's Coffee products less than k, return the List of them. DoublyLinkedList searchByLowCost(DoublyLinkedList myList, int k) { DoublyLinkedList result; initList(result); for (NODE* p = myList.Head; p != NULL; p = p->next) if (p->data.salecost < k) addLast(result, p->data); return result; } 10. Sorting for data of the Doubly Linked List : − In this report, we will install the Selection Sort and Quick Sort Algorithm for this problem.

Two atributtes we choose to sort are : name’s and salecost’s products. ❑ SELECTION SORT : − Step 1 : Create and initialize new list named as newList. − Step 2 : Use while-loop until my list is empty.1 : Assign NODE Head to NODE q.2 : Traverse from the second NODE to the last NODE in the list. If the value (name or salecost) of NODE q is less than the element traversed, we will do the next step 2.

Else we continue traversing to the last NODE.3 : Use the add last fucntion (addLast(DoublyLinkedList& myList, COFFEE X)) to insert this element − Step 2.4 : Use the remove node function ( void selectionSort(DoublyLinkedList myList) { DoublyLinkedList newList; initList(newList); while (!isEmpty(myList)) { NODE* q = myList.Head; for (NODE* p = myList.Head->next; p != NULL; p = p->next) { if (p->data.name) q = p; } addLast(newList, q->data); removeNode(myList, q); } showList(newList); } ❑ QUICK SORT : − Step 1 : Seperate the Doubly Linked List into two smaller List. − Step 2 : Check whether myList is empty or not. If it is empty return the program and do not anything. − Step 3 : Choose the pivot item (It can be a NODE Head) and remove it from List.

− Step 4 : Traverse the Doubly Linked List, and add the item into two List initialized. Remember to remove it − Step 5 : Use the Recursion Function for two List initialized. − Step 6 : Concatenate new List 1 - pivot - new List 2. void quickSort(DoublyLinkedList& myList) { DoublyLinkedList mynewList1, mynewList2; initList(mynewList1); initList(mynewList2); if (myList.Tail) return; NODE* pivot = createNode(myList.Head->data); NODE* p = myList.Head->next; myList.Head = NULL; while (p != NULL) { if(p->data.compare(pivot->data.name) <= 0) addLast(mynewList1,p->data); else addLast(mynewList2,p->data); NODE* temp = p->next; p = NULL; p = temp; } quickSort(mynewList1); quickSort(mynewList2); if (!isEmpty(mynewList1)) { mynewList1.Tail->next = pivot; pivot->prev = mynewList1.Tail = pivot; myList.Tail; } else { myList.Head = pivot; myList.Tail = pivot; } myList.Tail->next = mynewList2.Head; if (!isEmpty(mynewList2)) { mynewList2.Head->prev = myList.

Other functions : ❑ Merging two Doubly Linked List : void mergeList(DoublyLinkedList& X, DoublyLinkedList Y) { X.Tail; } ❑ Filtering the low count coffee products : void removeLowCount(DoublyLinkedList& myList) { for (NODE* p = myList.Head; p != NULL; p = p->next) if (p->data.count < 10) { p->prev->next = p->next; p->next->prev = p->prev; } } ❑ Request by cost : − Do you wonder if the customer want to find the cheap products ? To solve this problem we have a fucntion filtering these products to a list, and it structure is the same as the Doubly Linked List. We use the add last function (addLast(DoublyLinkedList& myList, COFFEE X)) to insert the elements meet the require. In this case it is less than k (the cost we choose to compare). DoublyLinkedList requestByCost(DoublyLinkedList myList, long k) { DoublyLinkedList result; initList(result); for (NODE* p = myList.Head; p != NULL; p = p->next) if (p->data.salecost <= k) addLast(result, p->data); return result; } II.2 : DOUBLY LINKED LIST BY C Sharp : − Instead of using "Struct" as C++, in C# - an oriented programming language, we create classes like each of struct.

❖ Build Class COFFEE : public class COFFEE { public string name; public double cafein; public int count; public int original_cost; public int sale_cost; } ❖ Build Class NODE : public class NODE { public COFFEE data; public NODE prev; public NODE next; } ❖ Build Class Doubly Linked List : − We just transfer the code in C++ into C# language by fixing grammar error. public class DoublyLinkedList { public NODE Head; public NODE Tail; } public void initList() { this.Head = null; this.Tail = null; } ❑ Create new Node : public NODE createNode(COFFEE X) { NODE tmp = new NODE(); tmp.prev = null; tmp.next = null; return tmp; } ❑ Check List is empty or full : public bool isEmpty() { return this.Head == null; } public bool isFull() { NODE tmp = new NODE(); return tmp == null; } ❑ Add a new item : public void addFirst(COFFEE X) { NODE tmp = createNode(X); if (isEmpty()) this.Tail = tmp; else { tmp.prev = tmp; this.Head = tmp; } } public void addLast(COFFEE X) { NODE tmp = createNode(X); if (isEmpty()) this.Tail = tmp; else { this.next = tmp; tmp.Tail = tmp; } } public void addPosition(int k, COFFEE X) { NODE tmp = createNode(X); if (isEmpty()) this.Tail = tmp; else if (this.Tail) addLast(X); else { NODE p = this.prev = tmp; tmp.next = tmp; p = tmp.prev; } } ❑ Remove an old item : public void removeFisrt() { if (isEmpty()) return; else { NODE tmp = this.Head; if (this.Tail = null; else this.next; tmp = null; GC.Collect(); } } public void removeLast() { if (isEmpty()) return; else { if (this.Tail = null; else { NODE tmp = this.