Phân Tích và Cài Đặt Thuật Toán Danh Sách Liên Kết Kép | Môn Cấu trúc dữ liệu và thuật toán - Trường Đại học Khoa học, Đại học Huế

lOMoAR cPSD| 58702377 MỤC LỤC
CHƯƠNG 1: TỔNG QUAN VỀ ĐỀ TÀI......................................................................5
1.1 GIỚI THIỆU ĐỀ TÀI..............................................................................................5
1.1.1 Mục tiêu đề tài.................................................................................................5
1.1.2 Khái niệm DS LK Kép.....................................................................................6
1.1.3 Đặc điểm, vai trò và cài đặt DS......................................................................8
1.1.4 Phân tích đề tài................................................................................................9
1.2 PHÂN CÔNG CÔNG VIỆC.......................................................................................13
CHƯƠNG 2: THUẬT TOÁN......................................................................................14
2.1 LƯU ĐỒ THUẬT TOÁN...........................................................................................14
2.2 BỘ DỮ LIỆU MÃU..................................................................................................17
CHƯƠNG 3: CÀI ĐẶT................................................................................................27
MODULE 1: KHAI BÁO CÁC THÀNH PHẦN CẦN CÓ TRONG CHƯƠNG TRÌNH............27
MODULE 2: THÊM ĐA THỨC VÀ THÀNH PHẦN ĐA THỨC VÀO CUỐI........................28
MODULE 3: THUẬT TOÁN SẮP XẾP..........................................................................28
MODULE 4: TỐI ƯU CHƯƠNG TRÌNH........................................................................29
KẾT LUẬN...............................................................................................................31
KẾT QUẢ ĐẠT ĐƯỢC...........................................................................................32
HƯỚNG PHÁT TRIỂN...........................................................................................33
DANH MỤC BẢNG BIỂU VÀ SƠ ĐỒ Số hiệu Loại Tên Số trang 1.2.1 Bảng
Bảng phân công nhiệm vụ 13, 14 lOMoAR cPSD| 58702377 2.1.1 Hình
Lưu đồ thuật toán sắp xếp đa 15
thức theo chiều tăng dần của hệ số 2.1.2 Hình
Lưu đồ thuật toán sắp xếp đa 16
thức theo chiều tăng dần của số mũ 2.2.1 Bảng Input bộ 1 17 2.2.2 Bảng Input bộ 2 18 2.2.3 Bảng Input bộ 3 19 2.2.4 Bảng Input bộ 4 20 2.2.5 Bảng Input bộ 5 21 2.2.6 Bảng Input bộ 6 22 2.2.7 Bảng Input bộ 7 23 2.2.8 Bảng Input bộ 8 24 2.2.9 Bảng Input bộ 9 25 2.2.10 Bảng Input bộ 10 26 lOMoAR cPSD| 58702377
CHƯƠNG 1: TỔNG QUAN VỀ ĐỀ TÀI
1.1 Giới thiệu đề tài
1.1.1 Mục tiêu đề tài
Viết chương trình cho phép nhập vào 1 đa thức, mỗi phần tử của đa thức bao gồm. (DS LK Kép) -hệ số của biến 1 - số mũ của biến 1 -hệ số của biến 2 - số mũ của biến 2
- tên biến 1 - tên biến 2. Hãy:
19.1 Nhập 1 đa thức cho đến khi nhập dấu “$”.
19.2. Sắp xếp đa thức theo chiều tăng dần của hệ số biến 1.
19.3. Sắp xếp đa thức theo chiều tăng dần của hệ số biến 2.
19.4 Sắp xếp đa thức theo chiều tăng dần của số mũ biến 1.
19.5 Sắp xếp đa thức theo chiều tăng dần của số mũ biến 2.
19.6. Sắp xếp đa thức theo chiều giảm dần của hệ số biến 1 và tăng dần của hệ số biến 2.
1.1.2 Khái niệm DS LK Kép
Về việc sử dụng danh sách liên kết kép sẽ khắc phục điểm yếu của danh sách liên
kết đơn là chỉ có liên kết tới node kế tiếp mà không có liên kết tới node đứng trước.
Do vây ta luôn pḥ ải duyêt tọ àn bô danh ṣ ách từ node gốc để tìm kiếm dữ liêu tại
mộ t vị trí ḅ ất kì. Môt node trong danh ṣ
ách liên kết kép được cấu thành từ ba thành phần là dữ
liêụ và phần kết nối tới node kế tiếp và node trước nó. lOMoAR cPSD| 58702377
Prev: Là con trỏ tới node trước.
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.
Viêc chèn dữ liệ u trong danh ṣ ách liên kết kép
Giả sử trước khi chèn dữ liêu ta có mộ t node riêng biệ t ṿ à môt danh ṣ ách liên kết kép.
Trường hợp ta muốn chèn vào vị trí giữa danh sách liên kết ở trên sẽ được mô tả như sau: lOMoAR cPSD| 58702377
So sánh với danh sách liên kết đơn:
- Về ưu điểm: Ta có thể duyêt danh ṣ ách theo cả hai chiều bởi vì danh sách liên
kết kép có con trỏ prev để truy câp node trước ṿ
à con trỏ next để truy câp
node ̣ sau. Nên khi muốn tìm kiếm dữ liêu trong danh ṣ ách ta không nhất thiết phải duyêt từ đ ̣
ầu danh sách như với danh sách liên kết đơn.
- Về nhược điểm: Vì con trỏ prev được thêm vào mỗi node, như vây ṣ ẽ tốn thêm
không gian bô nhớ và c ̣ ách thức hoạt đông c ̣
ủa danh sách liên kết kép cũng
vì vâỵ mà phức tạp hơn.
1.1.3 Đặc điểm, vai trò và cài đặt DS
Các thành phần của danh sách liên kết kép bao gồm:
+ Các node: Mỗi node bao gồm phần dữ liêu, mộ t con trỏ prev đ ̣ ể trỏ đến
node ngay trước nó và môt con trỏ next đ ̣
ể trỏ tới node ngay tiếp sau nó.
+ Con trỏ head để trỏ tới vị trí đầu tiên của danh sách liên kết. lOMoAR cPSD| 58702377
Các thao tác chính với danh sách liên kết kép:
+ Tạo môt node mới ṿ à trả về con trỏ tới node đó
+ Chèn môt node ṿào cuối danh sách
+ Hiển thị tất cả các node trong danh sách. lOMoAR cPSD| 58702377
1.1.4 Phân tích đề tài
Tổng quan về cấu trúc dữ liệu và giải thuật thì đây là môn học nền tảng để xây
dựng tư duy cho các môn lập trình đồng thời xác định và định hướng cho học viên.
Nói về đề tài, đề tài của nhóm 19 chúng em có tên gọi chung là : Sắp xếp đa thức
theo chiều tăng dần. Đây là một đề tài khó với nhóm em, nó yêu cầu tư duy về
những con số nhiều hơn là làm việc bằng câu chữ như đa số các đề tài khác của
các bạn trong lớp. Trước hết ta phải phân tích đề bài để tìm ra hướng đi và đưa ra
cách giải quyết vấn đề. - Phân tích đề bài:
Sau khi đọc xong nửa đầu của đề bài thì câu hỏi lớn nhất hiện ra trong đầu phải là
câu hỏi: “ ĐA THỨC LÀ GÌ ? ” Đa thức là chuỗi các kí tự toán học bao gồm các
phần tử của đa thức và các phần tử đó được nối với nhau bởi dấu cộng. Mà phần
tử của đa thức lại bao gồm hệ số, tên của biến và số mũ.
Vậy sau khi tìm được câu trả lời cho câu hỏi của nửa đầu thì công thức hay khuôn
mẫu để tạo thành 1 đa thức sẽ được gói gọn lại theo dạng:
(Hệ số) Tên biến số mũ + …+(Hệ số’) Tên biến số mũ’
Đã xong câu hỏi cho nửa đầu thì ta đi đến yêu cầu, phần yêu cầu đầu tiên cho đề
tài là: Nhập vào một đa thức cho đến khi nhập dấu “$” . Vậy thì quá trình nhập
xuất đa thức sẽ kết thúc khi ta nhập hệ số = $ hoặc số mũ = $. Qua đó ta có thể thấy
rõ hai trường hợp có thể xảy ra: TH1: Hệ số = $
Quá trình nhập xuất kết thúc lOMoAR cPSD| 58702377
Trong trường hợp này thì không có gì đáng chú ý vì khi muốn kết thúc quá trình
nhập xuất ngay sau khi hoàn thành xong thành phần đa thức cuối cùng trước đó.
TH2: Hệ số là một số bất kì và số mũ = $
Vậy thì phần tử đa thức sẽ có dạng: (hệ số) X $ VD: Hệ số = 5 Số mũ = $
In ra màn hình: 5 , việc không nhập số mũ hoặc kết thúc nhập hàm tại vị trí nhập
số mũ sẽ biến phần tử của đa thức đó thành hệ số tự do tức là sẽ không phụ thuộc
vào x cũng như việc nhập một hệ số bất kì và nhập số mũ = 0.
Yêu cầu tiếp theo trong đề tài và cũng chính là yêu cầu quan trong nhất đó là: sắp
xếp đa thức theo chiều tăng dần của hệ số và số mũ. Dừng lại ở đây và đặt ra một
câu hỏi mới vậy thì hai yêu cầu trên khác nhau ở điểm nào? Có thể thấy rõ nhất là
một yêu cầu làm việc với hệ số và một yêu cầu còn lại làm việc với số mũ. Phân
tích qua một chút về hai thành phần này, như đã trình bày ở trên, đa thức thì phải
có tên biến, hệ số và số mũ nhưng nó phải được sắp xếp theo trình tự. Lấy tên biến
x làm trung tâm để dễ dàng hình dung vấn đề, những thành phần nào đứng trước x
sẽ được gọi là hệ số, nhưng sẽ có vài trường hợp ngoại lệ có thể kể đến như việc ta
nhập từ bàn phím với hệ số = 0 và ta biết rằng số 0 nhân với số nào cũng bằng 0 vì
vậy trong trường hợp này thành phần của đa thức sẽ là hệ số tự do và đồng thời rơi
vào trường hợp đặc biệt đó là = 0.
Trường hợp tiếp theo về hệ số cũng đặc biệt không kém đó là khi ta nhập từ bàn
phím với hệ số bằng 1, trong trường hợp này việc in ra màn hình với dạng 1x thì
sẽ không được tối ưu cho lắm vì trên thực tế chẳng ai viết như thế cả và trong việc
viết phần mềm rồi in ra màn hình về lâu dài cũng khiến cho nó bị tốn nhiều hơn lOMoAR cPSD| 58702377
dung lượng dự tính, vì vậy trong trường hợp này ta sẽ tối ưu hóa đoạn chương trình
bằng cách: nếu ta nhập từ bàn phím với hệ số = 0 thì ta sẽ không in thành phần này ra màn hình.
Và cũng gần tương tự với trường hợp hệ số = 1 ta sẽ chỉ in ra tên biến và số mũ
của nó thay vì viết cả phần hệ số là = 1 ra màn hình. Về các trường hợp còn lại là
hệ số != 0 và 1 thì in ra màn hình như bình thường vì nó đã tối ưu rồi.
Đến đây chúng em nhận ra một vấn đề nữa ảnh hưởng gián tiếp tới hệ số đó là số
mũ, nếu trong trường hợp số mũ bằng nhau giữa không chỉ 1 mà rất nhiều những
phần tử trong đa thức thì sao? Lấy ví dụ khi ta nhập vào đa thức có hai phần tử có
số mũ bằng nhau như sau: 3x5 + 4x5 thì xét về mặt toán học ta có thể rút gọn đa
thức này bằng cách cộng hai phần hệ số với nhau và giữ nguyên phần số mũ = 7x5.
Vậy thì một lần nữa ta phải tối ưu lại câu lệnh, nếu như số mũ của phần tử cũ bằng
với số mũ của phần tử mới thì ta cho phép hai phần tử này rút gọn bằng cách tính
tổng hai thành phần hệ số của chúng đồng thời giữ nguyên thành phần số mũ của chúng.
Tiếp theo khi làm việc với số mũ thì cũng có những trường hợp đặc biệt xảy ra
tương tự với hệ số, nếu ta nhập từ bàn phím số mũ = 0 thì xét về mặt toán học bất
kì số nào mũ 0 đều bằng 1 cho nên lúc này thành phần đa thức sẽ bị rút gọn chỉ còn
phần hệ số do tên biến đã bị triệt tiêu bởi việc số mũ = 0. Nếu nhập từ bàn phím số
mũ bằng 1 thì lại xảy ra trường hợp dư thừa dữ liệu do nếu xét về mặt toán học thì
x1 = x. Vì vậy nếu trong trường hợp số mũ nhập vào từ bàn phím bằng 1 thì ta có
thể tối ưu câu lệnh bằng cách không in ra số mũ của phần tử đó mà chỉ in ra hệ số
và tên của biến đó mà thôi.
Phần cuối cùng đó là sắp xếp, thì về bản chất việc sắp xếp hệ số và số mũ là như
nhau. Để sắp xếp đa thức theo chiều tăng dần của hệ số ta đi từ phần tử đầu tiên
của đa thức và kết thúc khi đi đến phần tử cuối cùng của đa thức đó. Nếu hệ số của lOMoAR cPSD| 58702377
phần tử đã duyệt lớn hơn so với hệ số của phần tử muốn duyệt tiếp theo thì ta đổi
chỗ hai phần tử đó với nhau. Khi đi hết quá trình đó ta sẽ được dãy sắp xếp đa thức
theo chiều tăng dần của hệ số cũng như là số mũ.
1.2 Phân công công việc ST Công việc Tên đầu việc Đánh giá T chia đến nhỏ nhất Thành viên Thiết kế chương trình và thuật Quá trình Phân tích đề bài. toán bằng ngôn phân tích ổn Tìm ra giải pháp cho Thái Bảo Tuấn ngữ C++ để triển khai yêu cầu của đề bài. nhiều vấn đề. 1 Bộ dữ liệu tạo ra đa
Thiết kế bộ dữ liệu Nguyễn Văn Tuấn dạng với mẫu. nhiều trường hợp đặc biệt. Khai báo các phần tử Tích cực tham gia vào chương tham gia làm 2 Cài đặt Code trình. Nguyễn Văn Tuấn bài. Thiết kế hàm thêm đa Hàm dễ hiểu, thức. dễ vận dụng. lOMoAR cPSD| 58702377 Thiết kế hàm main. Thiết kế hàm thêm vào cuối dãy. Tích cực tham gia làm Trần Mạnh điều bài. Hàm dễ hiểu, dễ vận dụng. Tích cực
Vẽ lưu đồ thuật toán. tham gia làm
Thiết kế hàm sắp xếp. bài. 2 Cài đặt Code Thái Bảo Tuấn Hàm dễ hiểu, Bổ sung và tối ưu dễ vận dụng. thuật toán . Tích cực Tất cả thành viên tham gia làm 3 Word và PowerPoint trong nhóm bài và đóng góp ý kiến.
Bảng 1.2.1 - Bảng phân công nhiệm vụ
CHƯƠNG 2: THUẬT TOÁN
2.1 Lưu đồ thuật toán
Quy trình thực hiện quá trình thiết kế lưu đồ như sau
B1: Quyết định xem bạn cần vẽ lưu đồ cho quy trình nào lOMoAR cPSD| 58702377
Tất nhiên, việc xây dựng lưu đồ trước tên cần phải có ý tưởng. Ý tưởng đó là để
quy trình hoá theo lưu đồ với mục đích gì. Mục đích ở đây là sắp xếp các thành
phần của phần tử trong đa thức cụ thể là hệ số và số mũ B2: Thu thập thông tin
Trừ khi nghĩ đến việc gì thì thông tin cũng là điều quan trọng nhất mà bạn cần phải
tìm hiểu. Thông tin bạn cần cho lưu đồ lại càng cần phải chính xác và có liên quan
tới phần lưu đồ bạn chuẩn bị thực hiện.
Ngay cả khi quy trình có vẻ đơn giản hoặc thời gian diễn ra ngắn thì thông tin thu
thập đều quan trọng cả và phải đều chính xác. Sau bước này thì sẽ có hai khả năng
đó là quy trình vẫn được giữ nguyên như cũ hoặc quay trở lại bước trước đó và lặp
lại quy trình hoặc rẽ sang quy trình hoàn toàn khác.
B3: Bắt tay vào thực hiện vẽ lưu đồ
Khi bạn đã có trong tay đủ các thông tin thì hoạt động vẽ được tiến hành ngay. Các
bạn có thể dùng cách đơn giản nhất là dùng bút và giấy, hoặc cao cấp hơn đó là các
phần mềm, công cụ để hỗ trợ bạn lên lưu đồ rất đơn giản. Hoặc ở mức độ thấp thì
bạn có thể dùng Microsoft PowerPoint, Paint hoặc các phần mềm soạn thảo khác
để thực hiện thao tác cuối cùng này. lOMoAR cPSD| 58702377
Hình 2.1.1 – Lưu đồ thuật toán sắp xếp đa thức theo chiều tăng dần của hệ số lOMoAR cPSD| 58702377
Hình 2.1.2 – Lưu đồ thuật toán sắp xếp đa thức theo chiều tăng dần của số mũ
2.2 Bộ dữ liệu mãu Bộ 1: Phần tử 0 1 2 3 4 Hệ số 3 9 1 3 9 lOMoAR cPSD| 58702377 Số mũ 4 7 2 1 0 Bảng 2.2.1 – Input bộ 1 Kết quả: Bộ 2: Phần tử 0 1 2 3 4 Hệ số 7 5 1 5 5 Số mũ 3 5 9 11 5 lOMoAR cPSD| 58702377 Bảng 2.2.2 – Input bộ 2 Kết quả: Bộ 3: Phần tử 0 1 2 3 4 Hệ số 12 3 50 4 49 Số mũ 6 19 70 1 11 Bảng 2.2.3 – Input bộ 3 Kết quả: lOMoAR cPSD| 58702377 Bộ 4: Phần tử 0 1 2 3 4 Hệ số 5 17 12 9 40 Số mũ 3 7 12 7 1 Bảng 2.2.4 – Input bộ 4 Kết quả: lOMoAR cPSD| 58702377 Bộ 5: Phần tử 0 1 2 3 4 Hệ số 9 19 17 9 3 Số mũ 7 17 3 2 0 Bảng 2.2.5 – Input bộ 5 Kết quả: lOMoAR cPSD| 58702377 Bộ 6: Phần tử 0 1 2 3 4 Hệ số 17 9 0 3 17 Số mũ 12 11 1 0 5 Bảng 2.2.6 – Input bộ 6 Kết quả: lOMoAR cPSD| 58702377 Bộ 7: Phần tử 0 1 2 3 4 Hệ số 12 7 37 99 100 Số mũ 11 9 2 7 0 Bảng 2.2.7 – Input bộ 7 Kết quả: