Hướng dẫn thực hành mơn: Nhập mơn lập trình Lớp 07DB_A/B Người soạn: Nguyễn Hải Minh Email: nhminh@fit.hcmuns.edu.vn CHỦ ĐỀ: CÀI ĐẶT THAM SỐ DÒNG LỆNH TRÊN VISUAL C++ 6.0 -oOo - Giới thiệu: Tham số dòng lệnh (command line arguments) hay đầy đủ tham số truyền từ dòng lệnh tập tham số đầu vào cho chương trình Chương trình dựa vào tham số để thực theo hướng định Tham số dịng lệnh ứng dụng cho chương trình viết dạng Console (chạy DOS) Từ dấu nhắc DOS, ta gọi chương trình chạy theo cách mà ta mong muốn # Ví dụ: lệnh CD DOS cho ta di chuyển tới thư mục CD WINDOWS chuyển tới thư mục C:\WINDOWS Trong đó, WINDOWS tham số mà ta truyền vào cho câu lệnh CD Trang Hướng dẫn thực hành mơn: Nhập mơn lập trình Lớp 07DB_A/B CD chuyển tới thư mục cha thư mục hành Trong đó, tham số truyền vào cho lệnh CD Tất nhiên, chương trình có khơng nhận vào tham số dịng lệnh để thực thi chức chương trình Tuy nhiên, việc cài đặt tham số dòng lệnh phát huy tính linh động tiện dụng chương trình Ví dụ minh họa # Cài đặt chương trình TinhTong tính tổng hai số nguyên a, b, xuất kết hình Cách 1: cài thơng thường, khơng dùng tham số dòng lệnh Cách 2: cài đặt với tham số dịng lệnh Khi chạy chương trình, người dùng phải nhập vào số Nhập tự động a,b thông qua tham số dịng lệnh sau: a, b chương trình thực TinhTong 10 12 Trang Hướng dẫn thực hành mơn: Nhập mơn lập trình Lớp 07DB_A/B Hướng dẫn cài đặt 3.1 Khai báo hàm main ¾ Hàm main có dạng void main(int argc, char* argv[]) ¾ Trong đó: • argc: số lượng tham số nhận vào từ dịng lệnh • argv: mảng trỏ kiểu char lưu tham số dạng chuỗi ký tự 3.2 Lấy tham số nhập từ dòng lệnh Mặc định tham số lưu lại mảng argv theo thứ tự từ trái sang phải Ví dụ với cài đặt phần 2, ta có: • argc = //số tham số dịng lệnh nhận vào • argv[0] = “TinhTong2” //tham số thứ 1: tên chương trình • argv[1] = “10” //tham số thứ • argv[2] = “12” //tham số thứ ª Lưu ý: Vì mảng argv mảng trỏ kiểu char nên để tính tốn tham số này, cần dùng hàm atoi để chuyển chuỗi sang số nguyên (xem ví dụ minh họa trên) 3.3 Chạy tham số dòng lệnh VC++ 6.0 Để nhập tham số dòng lệnh chạy chương trình VC++ 6.0, mở Project Ỉ Settings… vào tab Debug, ghi tham số vào khung Program arguments Trang Hướng dẫn thực hành môn: Nhập môn lập trình Lớp 07DB_A/B ª Lưu ý: Khơng ghi tên chương trình vào Program arguments (mặc định argv[0] tên chương trình), tham số nhập vào khung Program arguments lưu vào argv[1], argv[2], … Sau nhập tham số vào, click OK Biên dịch chương trình (F7) chạy bình thường (Ctrl+F5 F5) 3.4 Chạy tham số dòng lệnh từ DOS Commander 1) Vào Start Ỉ Run, gõ vào cmd Ỉ OK Trang Hướng dẫn thực hành mơn: Nhập mơn lập trình Lớp 07DB_A/B 2) Chuyển tới thư mục chứa file TinhTong2.exe (dùng lệnh CD Duong_dan) 3) Gõ vào TinhTong2 55 100 Hoặc gõ đường dẫn trực tiếp đến file TinhTong2.exe sau: Trang 3.3 Chạy tham số dòng lệnh Visual Studio 2008 Vào Project\ Properties\Configuration Properties\Debugging\Command Argument Đánh tham số vào text box bên cạnh Command Argument (các tham số khơng gồm tên chương trình) Sau nhấn OK Như chương trình chạy debug với tham số dòng lệnh VS 2008 Thuật toán Balan ngược (Reverse Polish Notation) -oOo Input (đầu vào): - Chuỗi P1 chuỗi biểu thức dạng In-fix VD P1 = “(3+4*5)/(6-8/2)” Output (kết quả): - Chuỗi P2 chuỗi biểu thức dạng Post-fix VD P2 = “345*+682/-/” Thuật toán : Khởi tạo stack S rỗng Push(S, ‘$’) // $ «tốn tử giả» có độ ưu tiên thấp $ < + - < * / // qui ước: độ ưu tiên ( < $ P2 = ‘’ // chuỗi ban đầu rỗng Lặp cho phần tử P1[i]: P1[i] tốn hạng ghi P1[i] vào bên phải P2 P1[i] == ‘(‘ đưa P1[i] vào stack S: Push(S, P1[i]) P1[i] toán tử (+ - * /) thì: Lặp a Pop(S, x) // x = giá trị đỉnh stack b Nếu độ ưu tiên x >= độ ưu tiên P1[i] ghi x vào bên phải P2 Ngược lại { Push(S, x) Push(S, P1[i]) break; } Hết lặp P1[i] == ‘)’ thì: Lặp a Pop(S, x) // x = giá trị đỉnh stack b Nếu x tốn tử (+ - * /) ghi x vào bên phải P2 Nếu x == ‘(‘ break; Hết lặp Hết lặp P1[i] Lấy tất phần tử stack S ra, ghi vào bên phải P2 Thuật tốn Tính giá trị biểu thức Post-fix -oOo Input (đầu vào): - Chuỗi P chuỗi biểu thức dạng Post-fix VD P = “345*+682/-/” - Mỗi số hạng có chữ số Output (kết quả): - Giá trị biểu thức P Thuật toán : Khai báo stack S // S: INT_STACK hay FLOAT_STACK tuỳ theo toán tử / // chia nguyên hay chia số thực Khởi tạo stack S rỗng Lặp cho phần tử P[i]: Nếu P[i] tốn hạng thì: Biến đổi P[i] thành số nguyên: value = P[i] – 48; Push(S, value); Nếu P[i] tốn tử thì: Pop(S, b); // b: toán hạng thứ biểu thức, VD a + b Pop(S, a); // a: toán hạng thứ biểu thức Kq = a b; // tính biểu thức con, P[i] tốn tử + - * / Push(S, Kq); Hết lặp P[i] Giá trị biểu thức phần tử cuối nằm stack PREPRINT In Proc Workshop on Algorithms and Data Structures, pages 60-71 Springer Verlag, 1993  ✂✁☎✄✆✁☎✝✟✞✡✠☞☛✍✌✎✠☞✁✑✏✒✞✔✓✖✕✗✏✒✠☞✠☞✘✚✙ ✁✑☛✛✠✜✌✣✢✆✤✦✥✛✄✧✠ ✪★ ✩✬✫✮✭✑★✪✫✰✯✱✭✆✩✳✲✴✲✶✵✷✫✮✸ ✹✻✺✴✼✾✽✆✿❁❀❃❂✑✺✴❄❅❀❇❆❉❈❋❊●❆❉❂✑✼■❍✷❀❃✺✬✿❑❏▼▲✳◆❖✺✳❄✷▲✳✺◗€■❘❙❍■❄■❚❱❯❑❄■◆❖❲❳✺✴✿❃❨❁◆❩❀❭❬❪€▼❫❴❆✧❵✎❛◗❛✳❜▼€✱❏❅❝❭❞◗❞❪❛❢❡❉❡❣❘❙❍✷❄✾❚✰€■❏❪❤❇✺✐❚▼✺✳❄ ❃❀❀❁❥❧✿❃◆✇❆❉✺✳❦♥❄■✺✳♠✳❨✳❨✰♦✴⑦❴❆❉♣✆⑧❭❈■q■❄⑨❚✷r◗◆❖♦◗❀❃▲✴s✉✺✴❀❃✿❃◆❖t❆◗❂✑❄■❨❙❨✑✽✆✽✒✿❃❆❉◆❖▲✳✺✳❈✡❆◗❨✳❄❪▲✴€✐❆❅❀❁❤●✿❃❚✷✺❴◆❖✺⑩✈■✼▼❍▼❨❁✿❃❀❃◆❖✺✳◆✇❂✑❨❁❆❉✺✳❄✻✼■❄❪④❖❀❃❀②◆❖❆✒▲✳❄✷◆❩❀❃❀❭✺✴①■❬❪❤✟€❋✺♥❂☎✿❃❆◗✺✳❍▼✽✆▲✳✿❱◆❖✺✳❄❅❄❪✽❉❀❃❀②④❖✺✴⑤◗❚✷❄✾❆✆✺✳✽❉✿❃✈■❄✷◆❖❀❃✽✆▲✳①✷❀❃✺③❂✑✺③✽❉❆◗④❖❨☎⑤❉❄☞❆❉▲✳❨❁✿❃❆◗◆❖◆❩❂✑❂✑❀❃①■✼■✼■❂✑✽✆④❖✺③❨✰✿❃✺❶◆❖❈⑥❂✑❆❉❈⑥✿❢✼■✽✧✈✾❲◗④❖✺✳❆◗✽❉❂✑❍✷④✇✽✆✿✶✺✳❄■✽✆❄❪▲✳✈■❀✶✺✐④❩✽✧❬❚ ❝ ❤❷◆❖❀❃①❧❀❃①■❆❉❨❁✺✻❈⑥❆❉✿❸❚✷✺✬❀❃✺✴✿❃❂✑◆❖❄■◆❖❨❹❀❃◆❖▲✡✽❉❄■❚❶✼✷✿❃❆❉✈✾✽❉✈✷◆❖④✇◆❖❨❹❀❃◆❖▲☞❨❁❺❅◆✇✼❱④❖◆✇❨❹❀❃❨✳⑦ ❻ ❼✷❽❑❾✱❿✮➀✡➁✪➂✪➃②❾✮➄✶➀✔❽ ➅❹➆❇➇ ✲❋➈❑✭❉➉➊➉■➋✾✫✮✵❪➈✡✫ ➆✬➌✰➍❅➆❋➆✴➌ ✭✆✩✴✭ ➇ ✲ ➍☞➌■➎✰➏ ✭ ➏■➍❅➐✑➑ ✭ ➆ ➈❸✭✆✭❉✫ ➆✬➌ ✭❉✵▼✩✴➒ ➍ ✫✰✯ ➐ ✩ ➍▼➓✧➆✬➇⑥➓ ✭ ➇ ✫ ➓ ✵▼➔ ➐✮➎✱➆ ✭✆✩ ➐ ✩✴✵ ➏ ✩ ➍ ➔❶➔ ➇ ✫ ➏✰→✷➣↔➌✮➇ ➉➊✭ ➓ ✵✷➔ ➐❙➍ ✫ ➇ ✭❉✲ ➐ ✩✬✵✱✯ ➎❙➓✧➇ ✫ ➏❱➓ ✵▼➔ ➐✮➎✱➆ ✭✆✩✳✲✔✵✷✩ ➓❉➍ ✩✳✲ ➍ ✩✴✭ ➍ ✫✱↕ ➇ ✵ ➎ ✲ ➆ ✵ ➎ ✲✬✭ ➆✬➌ ✭ ➑ ✭◗✲ ➆✒➆ ✭ ➓✳➌ ✫✰✵▼➉➙✵ ➏ ➒ ➍❳➛❪➍▼➇ ➉ ➍❅➑ ➉➙✭❑➜ ➍❪➆ ➉➙✭ ➍ ✲ ➆✒➆✬➌ ✭✆➒ ➆ ✩✬➒ ➆ ✵ ➓ ✵✷✫ ➛■➇ ✫ ➓ ✭ ➆✴➌ ✭ ➇ ✩ ➓✆➎ ✲ ➆ ✵▼➔➝✭✆✩✳✲ ➆✬➌❙➍❪➆ ➆✬➌ ✭✆➒❧✯✱✵✑✲✬✵☞➜ ➆✴➌ ✭ ➐✮➌✮➇ ➉➊✵■✲✶✵ ➐✮➌ ➒ ➇ ✲❇✵▼➞ ➆ ✭✆✫➝✯ ➇➊➟ ✭❉✩✬✭❉✫ ➆❇➇ ✫➝✲✶✵▼➞ ➆ ➈ ➍ ✩✬✭❑✭✆✫ ➏✷➇ ✫✮✭❉✭✆✩ ➇ ✫ ➏✰➠❳➇✇➆✒➇ ✲❇✭✆✫✮✵ ➎✮➏▼➌ ➆ ✵ ➐ ✩✬✵✱✯ ➎✰➓ ✭ ➐ ✩✬✵ ➏ ✩ ➍ ➔⑩✲ ➆✬➌✰➍❅➆❣➡ ➈❑✵✷✩✬➋ → ➢✪➤❷➥⑩➓✆➇ ✭❉✫ ➆✔➍ ➉ ➏ ✵▼✩ ➇➊➆✬➌ ➔⑩✲❴➞➦✵▼✩❷✲✬✵▼✩ ➆✬➇ ✫ ➏❣➍ ✫✰✯❶✲✶✭ ➍ ✩ ➓✳➌✮➇ ✫ ➏✰➧ ➈ ➌✮➇⑥➓✳➌➨➍ ✩✬✭ ➆✴➍❅➎✰➏▼➌■➆➩➇ ✫ ➇ ✫ ➆ ✩✴✵✾✯ ➎✰➓✐➆ ✵▼✩✴➒ ➓ ✵ ➎ ✩✳✲✬✭❉✲ ➧❙➍ ✩✴✭❧✵▼➞ ➆ ✭❉✫➫✩✴✭ ➐ ➉ ➍▼➓ ✭❉✯ ➑ ➒ ➐ ✵■✵✷✩➩➔➝✭ ➆✬➌ ✵✱✯✮✲ ➧ ✲ ➎✰➓✳➌✣➍ ✲ ➑✮➎✰➑✮➑ ➉➙✭✉✲✬✵▼✩ ➆✬➇ ✫ ➏❱➍ ✫✰✯⑩➉ ➇ ✫✰➋▼✭❉✯✎➉ ➇ ✲ ➆ ✲ →■➅ ➞❴➒▼✵ ➎ ✩ ➐ ✩✴✵ ➏ ✩ ➍ ➔ ➆✴➎ ✩✬✫❙✲❑✵ ➎✱➆✔➆ ✵❱✩✴✭❉➭ ➎✮➇ ✩✴✭ ➆ ✵✾✵ ➔ ➎❙➓✳➌✎➆✴➇ ➔➝✭❣✵▼✩✡✲ ➐✰➍▼➓ ✭➩➒✷✵ ➎✣➍ ✯ ➛✾➇➙➓ ✭❣➒▼✵ ➎ ✩ ➓✆➎ ✲ ➆ ✵▼➔➝✭✆✩ ➆ ✵ ➑✰➎ ➒ ➍ ✫✮✭✆➈ ➧✱➌ ✭ ➍❳➛✾➇ ✭❉✩ ➍ ✫✰✯✎➞ ➍ ✲ ➆ ✭✆✩ ➧ ➓ ✵✷➔ ➐✮➎✱➆ ✭❉✩ → ➯✻➌✮➇ ✲❣✲ ➇➊➆✬➎✰➍❅➆✬➇ ✵▼✫➲✲ ➆ ✩✬✵✷✫ ➏ ➉➙➒✛➔➝✵ ➆✬➇➙➛❪➍❪➆ ✭❉✲ ➍ ✫➨✭✧↕ ➆ ✭❉✫✰✲ ➇➙➛ ✭➝✲✬✭ ➍ ✩ ➓✳➌ ➞➦✵✷✩✉✲ ➇ ➔ ➐ ➉➙✭ ➍ ✫✰✯➨✲ ➌ ✵▼✩ ➆✶➳ ➓ ✵✱✯✱✭◗✯❱✲✬✵▼➉ ➎✱➆✴➇ ✵✷✫✰✲ ➆ ✵ ➓ ✵✷➔➝➔❶✵✷✫ ➓ ✵▼➔ ➐✮➎✱➆✳➍❪➆✴➇ ✵✷✫ ➍ ➉ ➆✴➍ ✲✶➋✱✲ ➧ ➞➦✵▼✩ ➇ ✫✰✲ ➆✳➍ ✫ ➓ ✭✻➈❑✵✷✩✴✲ ➆✶➳❁➓✆➍ ✲✶✭❑✭ ➥➵➓✧➇ ✭✆✫ ➆ ➔ ➍❅➇ ✫ ➆ ✭✆✫ ➍ ✫ ➓ ✭❱✵▼➞❸✯ ➇⑥➓✐➆✴➇ ✵✷✫ ➍ ✩ ➇ ✭◗✲ →♥➸➩➎ ✭ ➆ ✵ ➇➊➆ ✲✉➞ ➎ ✫✰✯ ➍ ➔➝✭✆✫ ➆✴➍ ➉ ➓✳➌✰➍ ✩ ➍▼➓✧➆ ✭✆✩ ➧❙➆✬➌✮➇ ✲ ➐ ✩✴✵ ➑ ➉➙✭✆➔ ➇ ✲ ✵▼✫✰✭➺✵▼➞ ➆✬➌ ✭➺➔➝✵■✲ ➆ ➈❸✭✆➉➙➉ ➳ ✲ ➆✴➎ ✯ ➇ ✭❉✯ ➇ ✫ ➍ ➉ ➏ ✵✷✩ ➇➊➆✬➌ ➔➻✯✮✭❉✲ ➇➊➏ ✫ →✒➼ ✫ ➆✬➇ ➉✡✩✬✭ ➓ ✭❉✫ ➆ ➉➊➒ ➧❷➍ ➉➙➉✡✲✶✵✷➉ ➎✱➆✴➇ ✵✷✫✰✲ ➌✰➍❳➛ ✭ ➑ ✭✆✭✆✫ ➑✰➍ ✲✬✭❉✯➽✵▼✫ ➑❙➍ ➉ ➍ ✫ ➓ ✭❉✯➾✲✬✭ ➍ ✩ ➓✳➌↔➆ ✩✬✭❉✭❉✲ ➧ ✲ ➎✰➓✳➌➚➍ ✲➺★❋➪✉➶ ➳❭➆ ✩✴✭✆✭❉✲➩➹✇➘✆➴ ➧ ✲✬➒✾➔❶➔➝✭ ➆ ✩ ➇➙➓ ➑✮➇ ✫ ➍ ✩✴➒➬➷ ➳❭➆ ✩✴✭✆✭◗✲✪➹ ➮❳➴⑩➱ ➍ ➉⑥✲✬✵✃✯✱✭✆✫✰✵ ➆ ✭◗✯↔✩✴✭❉✯ ➳❹➑ ➉ ➍▼➓ ➋ ➆ ✩✬✭❉✭❉✲➩➹ ❐❅➴❮❒ ➧✻❰ ➷✻➷❣➱ÐÏ✰❒ ➳❭➆ ✩✴✭✆✭❉✲➩➹ Ñ❅➴ ➧ ➈❑✭ ➇➊➏✷➌■➆✶➳ ➑✰✫✮✵✷➍ ➉✫✮➍ ✭❑✫ ✵▼➓ ➞✭◗✯ ➆ ✭✆✩✴➔ ✭✆✭◗✲➩➹➊➘▼✲ ➘✐➴ ➧✾✭ ➌✰✵✷➍ ➔❶➉➊➞ ➳❹✭ ➑✰➍ ➉ ➍✭✻✫ ✲ ➓ ✭❉✩ ✯ ➆ ✩✬✭❉✩✴✭❉✭❑✲✉✵▼➹✇➞➘❳Ò◗➴ ➧✱✵ ➍ ✫✰✭ ✯✎Ï ➔❶➳ ✫✮✵✷✭ ✫ ➇➙➏▼➌✾➑ ✩✬✵✵ ➎ ✩✩ ➆ ➔➝✩✴✭✆➔➝✭◗✲➩✭✆✩✳➹ Ĩ❳✲ ➴ →✾✲ Ơ ✵❪➈❑✭✆➒ ✭ ➛ ✭❉✩✬✩ ✭ ➧ ➆✴➌ ➌❙➍ ➑ ➓ ➆✬➌ ➆ ➎✰➓✧➆✬➎ ➓✳➌ ➇➙➓ ➍ ➏✪➐ ➏ ➍ ➍ ➆✴➌ ➍ ➍ ➉➙➉ ➓✆➎ ➔ ➑ ✭✆✩✳✲✬✵▼➔➝✭ ➆ ✵ ➇ ➔ ➐ ➉➙✭✆➔➝✭✆✫ ➆❉→●➯ ✵ ➓✧➇➊➆ ✭✎Õ ➎ ✫✮✩✬✵ ➧❴Ö✒➍▼➐✰➍ ✯ ➍ ➋ ➇ ✲ ➧♥➍ ✫✰✯ ❰ ✭◗✯ ➏ ✭❉➈ ➇➙➓ ➋✟➹➊➘❉×❳➴ ➧ ➆✬➌ ✭ ➆ ✩ ➍ ✯ ➇➊➆✬➇ ✵▼✫ ➍ ➉③✲✶✵ ➎ ✩ ➓ ✭ ➓ ✵✱✯✱✭✉➞➦✵▼✩ ➍❶➑✰➍ ➉ ➍ ✫ ➓ ✭◗✯✎✲✬✭ ➍ ✩ ➓✳➌➵➆ ✩✬✭❉✭ ➡✬➓ ✵✷✫ ➆✴➍❅➇ ✫✰✲❸✫ ➎ ➔➝✭✆✩✴✵ ➎ ✲ ➓❉➍ ✲✬✭❉✲ ➇ ✫ ➛ ✵▼➉ ➛✾➇ ✫ ➏ ✲ ➇ ✫ ➏ ➉➊✭ ➍ ✫✰✯➺✯✱✵ ➎✮➑ ➉➊✭❣✩✴✵ ➆✴➍❅➆✬➇ ✵▼✫✰✲ ➆ ✵ ➆✬➌ ✭✑➉➙✭✧➞ ➆✪➍ ✫✰✯ ➆✬➌ ✭✑✩ ➇➊➏✷➌■➆✴➢✮→ ➅ ✫ ➆✬➌ ✭❣✩✴✭ ➓ ✭❉✫ ➆ ➒✷✭ ➍ ✩✴✲ ➧▼➆✴➌ ✭☎✲✬✭ ➍ ✩ ➓✳➌ ➞➦✵✷✩☞✲ ➇ ➔ ➐ ➉➊✭❉✩✡✯ ➇➙➓✧➆✬➇ ✵▼✫ ➍ ✩✬➒ ➍ ➉ ➏ ✵▼✩ ➇✇➆✴➌ ➔⑩✲ ➌✰➍ ✲ ➆✴➍ ➋▼✭❉✫ ➍ ✫✮✭❉➈ ➧◗➍ ✫✰✯☎➭ ➎✮➇➊➆ ✭❑✲ ➎✰➓❉➓ ✭❉✲✴✲✶➞ ➎ ➉ ➧ ✯ ➇ ✩✬✭ ➓✐➆✴➇ ✵✷✫ ➑ ➒ ➆✴➌ ✭ ➇ ✫ ➆ ✩✴✵✾✯ ➎✰➓✐➆✴➇ ✵✷✫☎✵❅➞✰✲✬✵▼➔➝✭ ➡ ✫✮✵▼✫ ➳❭➆ ✩✴✭✆✭ ➢ ✲ ➆ ✩ ➎❙➓✐➳ ➆✬✩ ➎ ✫✰✩✬✭◗✯✱✲ ✵✷→▼➔ ỉ ĩí ị òõịĩé ✩✴✫ ✲ ➆ ✩✴✵✱✯ ✲✶➎✰✭✪➓ ✭❉✭ ✯ ➑ ➒ ✭✆✫Ö❷➎✰➏▼➌ ✩ ➹➊➘✆✫Ñ❪➴ ➇ ✲ ➍ ✲ ➇ ➔ ➐ ➉➙✭ ➍ ✫✰✯❶✭❉➉➊✭ ➏✷➍ ✫ ➆ ➍ ➇➊á ➍❅➆✴➍ ➆ ➎❙➓✐➆✬➎ óọồịổịĩịốỗĩíị ò ịĩ ✲✻✩✬✭ ➓ ✭❉✫ ➆ ➉➊➒ ➇ ✫ ➆ ✩✴✵✱✯ ➎✰➓ ✭❉✯ ➑ ➒✣Õ ➎ ✫✮✩✴✵ ➧✮Ö✒➍▼➐✰➍ ✯ ➍ ➋ ➇ ✲ ➧✱➍ ✫✰✯ ❰ ✭❉✯ ➏ ✭✆➈ ➇⑥➓ ➋✟➹✇➘◗×❳➴ → ➯✻➌ ✭ ➇ ➔ ➐ ✵▼✩ ➆✴➍ ✫ ➆ ➞➦✭ ➍❪➆✬➎ ✩✬✭❣✵❅➞ ➆✬➌ ✭✑✯✱✭ ➆ ✭❉✩✬➔ ➇ ✫ ➇ ✲ ➆✬➇⑥➓ ✲✶➋ ➇➙➐ ➉ ➇ ✲ ➆✡➇ ✲ ➇➊➆ ✲ ỗộóĩịồòịốỗịờ ế ➎ ✫✮✩✴✵➺✭ ➆✑➍ ➉ →➊➧②➆✬➌ ✭➝✲✬✵ ➎ ✩ ➓ ✭ ➓ ✵✱✯✱✭❱➞➦✵▼✩ ➇ ✫✰✲✬✭✆✩ ➆✬➇ ✵▼✫ ➇ ✫ ➆ ✵ ➍ ✯✱✭ ➆ ✭❉✩✬➔ ➇ ✫ ➇ ✲ ➆✬➇⑥➓ ✲✬➋ ➇➙➐ ➉ ➇ ✲ ➆❸➇ ✲✻✲ ➇ ➔ ➐ ➉➙✭✆✩❣➱➦✵✷✩ ➍❅➆ ➉➙✭ ➍ ✲ ➆ ✲ ➌ ✵✷✩ ➆ ✭✆✩✐❒ ➆✬➌❙➍ ✫ ➍ ✫■➒ ➐ ✩✴✭ ➛✾➇ ✵ ➎ ✲✬➉➙➒ ➐ ✩✴✭❉✲✬✭✆✫ ➆ ✭❉✯ ➓ ✵✾✯✮✭✪➞➦✵✷✩ ➍ ë t ✿❃❄■✺❉⑦ t ❄✾❚▼✺✴✿❃❨❁❨❁❆◗❄✾ì✻❚✷❄✾✽❅⑦ ④❖❀❃①✰⑦ ❨❁✺ CuuDuongThanCong.com https://fb.com/tailieudientucntt ➑✰➍ ➉ ➍ ✫ ➓ ✭◗✯⑩✲✶✭ ➍ ✩ ➓✳➌❶➆ ✩✴✭✆✭ →✷➅ ✫ ➍ ✯✰✯ ➇✇➆✴➇ ✵✷✫ ➧✷➆✬➌ ✭ ➍❅➎✱➆✴➌ ✵▼✩✳✲ ➓ ➉ ➍▼➇ ➔➝✭❉✯ ➆✴➌✰➍❪➆❑➆✬➌ ✭ ➓ ✵✱✯✱✭✪➞➦✵▼✩❑✯✮✭✆➉➙✭ ➆✬➇ ✵▼✫ ➈❸✵ ➎ ➉⑥✯ ➑ ✭☎✲ ➇ ➔ ➐ ➉➙✭ ➧❙➍ ➉ ➆✬➌ ✵ ➎✮➏▼➌➺➇✇➆ ➈ ➍ ✲❸✫✮✵ ➆☞➐ ✩✴✭❉✲✬✭✆✫ ➆ ✭◗✯ → ➅ ✫ ➆✴➌✮➇ ✲ ➍ ✩ ➆✴➇➙➓ ➉➊✭❑➈❑✭✔✯✮✭✆➔➝✵▼✫✰✲ ➆ ✩ ➍❪➆ ✭ ớịổợọờùéọ ñ❳➴ ➧ ➔ ➍ ➒ ➑ ✭❱➔ ➍❅➇ ✫ ➆✳➍❅➇ ✫✮✭❉✯ ➑ ➒ ➛ ✭✆✩✴➒➺✲ ➇ ➔ ➐ ➉➊✭ ➍ ➉ ➏ ✵▼✩ ➇➊➆✬➌ ➔⑩✲ →②➯✻➌ ✭❶✲ ➇ ➔ ➐ ➉ ➇➙➓✆➇✇➆ ➒ ➇ ✲ ➍✷➓✳➌✮➇ ✭ ➛ ✭◗✯➺➞➦✩✬✵✷➔ ➆✴➌ ✩✬✭❉✭❣✵ ➑ ✲✬✭✆✩ ➛❪➍❪➆✬➇ ✵▼✫❙✲✆ị ó ➑➯✻✭✉➌ ✭❧✩✬✭ ➉ ➐ ➍ ➉ ✩ ➍✷➏ ➓ ✭☎✭◗✯ ✫ ➎ ➑ ➔ ➒ ➑ ➆ ➈❸✭❉✩➩✵❱✵▼✲ ➞ ➇ ➔ ➓✆➍ ➐ ✲✬➉➊✭❉✭✉✲✪✵ ✵ ➐ ➓✆✭✆➓✧✩ ➎ ➍❪✩✬➆✴✩ ➇ ✵✷➇ ✫ ✫✰➏➵✲ ➧✾➇ ✫➓✆➍ ➆ ➉➊➉➙✩ ✭❉➍ ✯✛✯ ➇➊ô ➆✬➇Ý✷✵▼Û✧✫ õ➫➍ ➉➍ ✫✰➑❙✯✛➍ ụ òị ế ✫ ➌ ➏❱✵✱✯✮➍ ✲➩ô ➔ Ý✷Û✧➍ õ ➒ ➞➦✵✷➉➊➉➙✵❪➈❸✭❉✯ ➑ ụ òị ✩ ➍❳➛ ✭✆✩✳✲✶✭◗✯ ➐✰➍❅➆✬➌⑩➇ ✲❷✭❉✫✮✵ ➎✮➏✷➌➝➆ ✵☎➔ ➍▼➇ ✫ ➆✴➍▼➇ ✫ ➑❙➍ ➉ ➍ ✫ ➓ ✭❣✯ ➎ ✩ ➇ ✫ ➏➝➎✮➐ ✯ ➍❪➆ ✭❉✲ → ó ➯✻✲ ➇➙➏➌ ✫ ✭➫➇ Ø ✩✴➓✆✭ ➍➐ ✫ ✩✴✭❉➆❣✲✬➍✭✆✫➔❶➆✴✵ ➍❅➎➆✬➇ ✫ ✵▼➆ ✫➬✵▼✵❅➞ ➞ ➑ ➑❙✵✾➍✵▼➉➋ ➍ ➳ ✫ ➋✷➓ ✭✆✭ ✭ ➐✮➇ ➇ ✫✮✫ ➞➦➏✰✵▼→❋✩✴➔ ö ➍❅✫✮➆✬✭➝➇ ✵▼✲ ✫ ➌ ✵✷➍ ✩ ✲➵➆❣➇✵▼✫ ✫✰➆ ✭ ✭ ➏ ➑✮✭✆➇➊✩⑩➆➺➱è➐ ÷✱✭✆➱è➉➊✩➺✵ ➏ ✫✮➉➙✵✱✵ ✯✱➏❷✭ ø ➓❒ ✩✬➑✮✭ ➍❪➇➊➆ ➆ ✲✳✭◗❒ ✲ ➇ ✫ ➍ ✭ ➍▼➓✳➌ ✫✮✵✱✯✱✭❣➔ ➍ ➋▼✭◗✲ ➆✬➌ ✭ ➍ ➉ ➏ ✵▼✩ ➇✇➆✴➌ ➔⑩✲✻✲ ➇ ➔ ➐ ➉➊✭❉✩ → ó ➓✆➯✻➎ ➌ ➔ ✭❧➑ ✯✱✭✆✭✆✩✳➉➙✲✬✭ ✵▼➆✴➔➝➇ ✵✷✭✫✟➧ ✵❅✭ ➞ ➛ ✭✆➍ ✫➵✫ ➈ ➇ ✫ ➇➊➆➆✬✭✆➌ ✩✴✵ ✫ ➎✱➍ ➆✻➉❋➑✰✫✮➍ ✵✱➉ ✯✱➍ ✭❣✫ ➓✆➞➦➇✩✬✫ ✵✷➏✰➔ →■➣ ➍➝✭❣➑✰➇ ✲ ✫ ➌ ➍ ✵❪✩✬➈ ➒✣➌ ✲✶✭ ✵❪➍ ➈ ✩ ➓✳➆ ➌✎✵❶➆ ✲ ✩✬➇ ✭❉➔ ✭ ➐ ➌✰➉ ➇ ➍ ➞➦➒✲ ➍ ➆✴➌➉➙➈ ✭✉➍ ✯✮➒✱✭✆✲ ➉➙✭ ➑ ➆✬✭❉➇ ✵▼✭✆✫✫ ➍ ➉ ➏ ✵▼✩ ➇✇➆✴➌ ➔ ➑ ➒ ➆✴➌ ✭ ➎ ✲✬✭✉✵▼➞ ➆ ➈❸✵ ➏ ➉➙✵ ➑✰➍ ➉ ➐ ✵ ➇ ✫ ➆ ✭❉✩✴✲ → ★✪✲ ➍ ➔ ➍❪➆✶➆ ✭✆✩❱✵❅➞✻➞ ➍▼➓✧➆❉➧③➆✴➌ ✭ ➓ ✵✾✯ ➇ ✫ ➏ ✵▼➞✡✵ ➎ ✩ ➍ ➉ ➏ ✵▼✩ ➇✇➆✴➌ ➔⑩✲ ➇ ✲❧✭ ➛ ✭✆✫ù✲ ➌ ✵▼✩ ➆ ✭✆✩ ➆✴➌✰➍ ✫ ➆✴➌ ✭ ➓ ✵✾✯✮✭☞➞➦✵▼✩✻✲✬➋ ➇➙➐ ➉ ➇ ✲ ➆ ✲ ➧■➑ ✵ ➆✬➌✎➐ ✩✬✵ ➑✰➍❅➑✮➇ ➉ ➇ ✲ ➆✬➇⑥➓☞➍ ✫❙✯➵✯✱✭ ➆ ✭✆✩✴➔ ➇ ✫ ➇ ✲ ➆✬➇⑥➓❅➧✱➍ ✩✴✭ →✷➅ ✫✎✵ ➎ ✩✔✵ ➐✰➇ ✫ ➇ ✵▼✫ ➧✷➇➊➆❸➇ ✲ ➍ ➉➙✲✬✵✣✲ ➇ ➔ ➐ ➉➙✭✆✩ ➍ ✫✰✯ ➓ ➉➊✭ ➍ ✩✴✭✆✩ →②Ô ✭✆✫ ➓ ✭ ➧②➆✬➌ ✭ ➑✰➇ ✫ ➍ ✩✬➒⑨✲✬✭ ➍ ✩ ➓✳➌⑨➆ ✩✴✭✆✭❶➔ ➍ ➒ ➓ ✵▼➔ ➐ ✭ ➆ ✭ ➛ ✭✆✩✴➒➺➈❸✭✆➉➙➉ ➈ ➇➊➆✬➌ ✲✬➋ ➇➙➐ ➉ ➇ ✲ ➆ ✲ ➇ ✫ ➆ ✭✆✩✴➔⑩✲✻✵❅➞✒✲ ➇ ➔ ➐ ➉ ➇⑥➓✧➇➊➆ ➒ → ➅ ✫ ❰ ✭ ➓✐➆✬➇ ✵▼✫➺Ò❶➈❑✭ ➐ ✩✴✭❉✲✬✭✆✫ ➆✡➆✴➌ ✭☎✫✮✭❉➈➚➔ ➍▼➇ ✫ ➆ ✭❉✫ ➍ ✫ ➓ ✭ ➍ ➉ ➏ ✵✷✩ ➇➊➆✬➌ ➔➝✲❸➞➦✵✷✩ ➑✮➇ ✫ ➍ ✩✴➒✣➷ ➳❭➆ ✩✴✭✆✭◗✲ ➧ ➍ ✲✶✫✰✵✷✯ ✫ ➇ ✫ ✭ ❰ ➈❸✭ ➓✐✭✆➆✬✭❉➇ ✫ ✵▼✫✣ú❱✫ ➈❸✩✬✭☎➒⑨✯ ➷ ➇ ✲ ➓✆➎ ✩✴✭✆✲✴✭◗✲ ✲ ➆✬➌ ✭✫✰➇ ✯➲✩ ➇ ✯✱➔ ✭ ➐ ✭✆➉➙✩✴✭✆➔ ➔➝✭✆✫ ✫ ➆✳✲ ➍❪➆✬➇ ✵▼✲✬✫ ➋ →❙❰ ✭ ➉ ➓✧✲➆✬➇ ✵▼✲ ✫➵Ñ ✭ ➓ ✵▼✫ ➉➙➆✴✲✬➍▼✵➺➇ ✫✰➔ ✲ ➍❶➋▼✭ ➓ ✵▼➔ ➐✰✩ ➍ ✭✆✩ ➳➞ ➇ ➑ ➆ ➑✰➇ ➍ ➳❭➆ ➍ ➆ ➇ ➇ ➆✬➇⑥➓ ➇➊➐ ➇ ➆ →③➣ ➍ ➍ ➍➺➑ ➇ ➓ ✵▼➔ ➐✰➍ ✩ ➇ ✲✶✵✷✫⑩➈ ➇✇➆✴➌➵➆✬➌ ✭ ➐ ✩✬✵ ➑✰➍❅➑✮➇ ➉ ➇ ✲ ➆✬➇⑥➓ ✲✬➋ ➇➊➐ ➉ ➇ ✲ ➆◗→✱û❴➇ ✫ ➍ ➉➊➉➙➒ ➧ ➈❸✭✉✲ ➎ ➔➝➔ ➍ ✩ ➇➊á ✭✪✵ ➎ ✩❑✩✴✭❉✲ ➎ ➉ ➆ ✲ ➇ ✫ ❰ ✭ ➓✐➆✴➇ ✵✷✫✣ñ ỹ ýỵ ỵ ➍ ✩✴➒ ➷ ➳Ð➆ ✩✬✭❉✭ ➧ ➷✻➷ ➳Ð➆ ✩✬✭❉✭ ➧ ➈ ➍ ✲ ➇ ✫ ➆ ✩✴✵✾✯ ➎✰➓ ✭◗✯ ➑ ➒✃➷ ➍ ➒▼✭❉✩ ➇ ✫â➘◗Ĩ ✾➘☎➹ đ◗➴ ➍ ✲ ➍➨➑✮➇ ✫ ➍ ✩✴➒ ✩✴✭ ➐ ✩✴✭❉✲✬✭✆✫ ➆✳➍❪➆✬➇ ✵▼✫➺✵❅➞✔Ò ➳ ú ➆ ✩✬✭❉✭❉✲✪➹ Ò◗➴ →❙➼ ✲ ➇ ✫ ➏⑩➆✴➌ ✭ ➆ ✭❉✩✬➔ ➇ ✫✮✵▼➉➙✵ ➏ ➒ ➇ ✫➫➹ Ñ❅➴ ➧ ➈❸✭☎✲ ➍ ➒ ➆✬➌✰➍❅➆➩➍ ✫✮✵✱✯✱✭ ➇ ✫ ➍ Ò ➳ ú ➆ ✩✴✭✆✭ ➇ ✲❇✩✴✭ ➐ ✩✴✭❉✲✬✭✆✫ ➆ ✭◗✯ ➑ ➒ ➍✪ß②Ü✧Û ✰ã▼é❅ð❁ỉ②é◗ã▼Û✔➓ ✵▼✫ ➆✳➍❅➇ ✫ ➇ ✫ ➏ ✵✷✫✮✭✻✵▼✩ ➆ ➈❸✵ ➑✮➇ ✫ ➍ ✩✴➒☎✫✮✵✱✯✱✭❉✲ → ➤ ✯ ➏ ✭◗✲ ➇ ✫✰✲ ➇ ✯✮✭ ➐ ✲✶✭ ➎ ✯✱✵ ➳ ✫✮✵✱✯✱✭◗✲ ộọị ộổợ ọịốỗợử ✫✮➉➙➒➬✩ ➇➙➏▼➌■➆✬➳ ✭◗✯ ➏ ✭◗✲ ➍ ✩✴✭ ➍ ➉➙➉➙✵❪➈❑✭◗✯ ➆ ✵ ➑ ✭ ➌ ✵▼✩ ➇➊á ✵▼✫ ➆✴➍ ➉ →❷➅ ✫â✵▼✩✳✯✱✭✆✩ ➆ ✵✃➔ ➍▼➇ ✫ ➆✴➍▼➇ ✫ ➑✰➍ ➉ ➍ ✫ ✭✆➓ ➉➙✭➩➉ ✫ ✯ ➎ ✩ ➈ ➇ ✫ ➏❱✭ ➎✮➐ ✭✆✯ ✩ ➍❪➆ ✭❉✭ ✲ ➧ ✫ ➈❸✭ ✵▼➔➌✰➍❳➛✫ ✭ ➆ ✭◗✵➝✯ ✲ ➆ ✭➝✵▼✩✴➱➦✵✷✭ ✩ ➑✰➍ ➉ ➍✭❣✫ ✵ ➓ ✭ ➇ ✫✱✵ ➞➦✵✷✫ ✩✬➔ ✩ ➍❅➆✬➇ ✵▼✫ ✭❉➇ ✯ ✫ ➆✬✭◗➌ ❒ ✭➩✲ ✫✮✵✱✵✷✯✱✩ ✭◗✲ →✮✵✷ö ✫ ✫✮✭ ➉ ➑✮➇➊➆❉➧✾➆ ➇ ➏ ➌ ➆✴➌ ➆✴➌ ➇ ➓ ➇ ➏ ➏ ➆✴➌ ➎✱➆✴➏ ➇ ➏ ➇➙➏▼➌■➆✶➳ ➏ ➇ ➌ ➇➙á ➆✳➍ ✵✷✩☞✫✮✵ ➆◗➧ ➈❸✵ ➎ ➉⑥✯ ➑ ✭❧✭✆✫✮✵ ➎✮➏▼➌③→❙Ô ✵❪➈❸✭ ➛ ✭❉✩ ➧✱➇ ✫✛✵ ➎ ✩ ➇ ➔ ➐ ➉➙✭✆➔➝✭❉✫ ➆✳➍❪➆✴➇ ✵✷✫✛➈❑✭ ➓✳➌ ✵✷✲✬✭ ➆ ✵➵✲ ➆ ✵▼✩✴✭ ➍ ✫ ➇ ✫ ➆ ✭ ➏ ✭✆✩ à➊Û Û✆à❉➇ ✫❧✭ ➍▼➓✳➌ ✫✮✵✱✯✱✭ ➧❳➓ ✵▼✩✴✩✬✭◗✲ ➐ ✵▼✫❙✯ ➇ ✫ ➏✻➆ ✵ ➆✬➌ ✭ ➛ ✭✆✩ ➆✬➇⑥➓✆➍ ➉ ➌ ✭ ➇➙➏▼➌■➆ ✵▼➞ ➆✬➌ ✭❸✫✮✵✱✯✱✭ → ✵✾✯✮✭❉✲ ➍❅➆❸➆✴➌ ✭ ➑ ✵ ➆✶➆ ✵▼➔ ✵❅➞ ➆✬➌ ✭ ➆ ✩✬✭❉✭ ➍ ✩✬✭❣✵✷✫✣➉➙✭ ➛ ✭✆➉❋➘ → ➷❸✩ ➇ ✭ ❙➒ ➧✻➍ ➉➙➉✉✩✴✭ ➐ ✩✬✭◗✲✶✭❉✫ ➆✳➍❪➆✴➇ ✵✷✫✰✲⑩✵❅➞❶➷ ➳❭➆ ✩✴✭✆✭◗✲ ➧❑➇ ✫ ➓ ➉ ➎ ✯ ➇ ✫ ➏✗➑✰➇ ✫ ➍ ✩✬➒↔➷ ➳❭➆ ✩✴✭✆✭❉✲ ➧ ✩✴✭❉✯ ➑ ➉ ➍▼➓ ➋ ➆ ✩✬✭❉✭❉✲ ➧✆➍ ✫✰✯✑✯✮✭ ➆ ✭❉✩✬➔ ➇ ✫ ➇ ✲ ➆✴➇➙➓ ✲✶➋ ➇➙➐ ➉ ➇ ✲ ➆ ✲ ➧◗➍ ✩✴✭✒➔ ➍❅➇ ✫ ➆✳➍❅➇ ✫✮✭❉✯ ➑ ➒ ➆ ➈❑✵ ➑❙➍ ✲ ➇➙➓ ✵ ➐ ✭❉✩ ➍❅➆✬➇ ✵▼✫✰✲❉ò ❃✵ ➇ ✫ ➇ ✫ ➏ ➍ ✫✰✯✟✲ ➐ ➉ ➇➊➆✶➆✬➇ ✫ ➏ ✵▼➞✒➷ ➳❭➆ ✩✴✭✆✭❣✫✮✵✱✯✱✭◗✲ →✮➅ ✫ ➍❶➑✮➇ ✫ ➍ ✩✬➒ ➆ ✩✴✭✆✭✑✩✴✭ ➐ ✩✴✭❉✲✬✭✆✫ ➆✴➍❅➆✬➇ ✵▼✫ ➧✾➆✴➌✮➇ ✲ ➇ ✲ ➐ ✭❉✩✶➞➦✵✷✩✬➔➝✭❉✯ ➑ ➒➝✩✬✵ ➆✴➍❅➆✬➇ ✵▼✫✰✲ ➍ ✫✰✯ ➓✳➌✰➍ ✫ ➏ ✭✪✵▼➞ ➑✰➍ ➉ ➍ ✫ ➓ ✭ ➇ ✫✱➞➦✵✷✩✬➔ ➍❪➆✴➇ ✵✷✫ →✾➯✻➌ ✭➩✩✴✭ ➍ ✲✶✵✷✫⑩➈ ➌ ➒ ➆✬➌ ✭ ➍ ➉ ➏ ✵✷✩ ➇➊➆✬➌ ➔⑩✲ ➑ ✭ ➓ ✵▼➔➝✭ ➓ ✵▼➔ ➐ ➉ ➇➙➓❉➍❪➆ ✭❉✯ ➇ ✲ ➆✬➌✰➍❅➆⑨➍✃➐ ✲✬✭ ➎ ✯✱✵ ➳ ✫✮✵✱✯✱✭➲➔ ➍ ➒ ➆✳➍ ➋▼✭➲➔ ➍ ✫✾➒➾✯ ➇➊➟ ✭❉✩✬✭❉✫ ➆ ✲ ➌✰➍❅➐ ✭❉✲ ➧ ➓❉➍❅➎ ✲ ➇ ✫ ➏ ➔ ➍ ✫■➒ ✲ ➐ ✭ ➓✆➇➙➍ ➉ ➓✆➍ ✲✶✭◗✲ →❷û ✵▼✩⑩✭✆↕ ➍ ➔ ➐ ➉➊✭ ➧✔➍ ✯✰✯ ➇ ✫ ➏ ➍ ✫✮✭✆➈ ➌ ✵▼✩ ➇➙á ✵▼✫ ➆✳➍ ➉✻✭❉✯ ➏ ✭ ➆ ✵ ➍ ➐ ✲✬✭ ➎ ✯✱✵ ➳ ✫✮✵✱✯✱✭❶✵❅➞❑✲ ➌✰➍❅➐ ✭ ✵✷✩ ➔ ➍ ➒✛✩✴✭❉✲ ➎ ➉ ➆❣➇ ✫➫Ø ➛ ✭❶✯ ➇✇➟ ✭✆✩✴✭✆✫ ➆ ✲ ➌❙➍❅➐ ✭❉✲ ➧ ✫ ➍ ➔➝✭✆➉➙➒ ✁✄✂✆☎✝✁✄✞ ✠✟ ☛✡ ✌☞ ✎✍ ✑✏ ✒ ✔✓ ✒ ✖✕ ✘✗ CuuDuongThanCong.com https://fb.com/tailieudientucntt CẤU TRÚC DỮ LIỆU & GIẢI THUẬT HOMEWORK 5.1 – Danh sách liên kết -oOo Khai báo DSLK đơn sau: struct NODE { int Key; NODE* pNode; }; Trong đó, NODE* pNode có nghĩa là: a Con trỏ tới vùng liệu phần tử b Con trỏ tới phần tử DSLK c Con trỏ tới địa vùng nhớ phần tử trước DSLK d Con trỏ tới địa vùng nhớ DSLK Đặc điểm sau danh sách liên kết a Sử dụng trỏ (pointer) b Các node lưu trữ liên tiếp nhớ c Có thể mở rộng tuỳ ý (chỉ giới hạn dung lượng nhớ) d Thao tác Thêm/Xóa khơng cần phải dịch chuyển phần tử Cho danh sách liên kết đơn sau: a b c d p1 = pHead->pNext; p3 = p1->pNext->pNext; p3->data = p1->data; pCurr = p1; while (pCurr != NULL) { pCurr->data *= 5; pCurr = pCurr->pNext; } Hãy thực lệnh từ [a] đến [d], vẽ lại DSLK sau lệnh để thể rõ thay đổi DSLK Cho DSLK đơn hình vẽ Cho trước trỏ P, Q vị trí tương ứng Hãy viết lệnh cần thiết để chuyển DSLK thành dạng biểu diễn hình © Nguyen Tri Tuan – Khoa CNTT, trường ĐH.KHTN Tp.HCM 1/2 Cho DSLK với phần tử đầu pHead hàm fn sau Hãy cho biết kết gọi hàm fn(pHead) int fn(NODE *p) { if (p!=NULL) return (1 + fn(p->Next)); else return 0; } Cho DSLK đơn có phần tử đầu pHead, phần tử DSLK có field: Key: khóa, kiểu int pNext: trỏ đến phần tử DSLK a Hãy viết hàm không đệ qui đếm số phần tử DSLK b Hãy viết hàm đệ qui đếm số phần tử DSLK Hãy viết hàm “Xóa phần tử danh sách liên kết đơn” Hàm có dạng sau: NODE * Delete_1st_item_in_list(NODE *pHead); với pHead trỏ đầu danh sách Yêu cầu xử lý cho trường hợp: - Danh sách rỗng - Danh sách có phần tử - Danh sách có nhiều phần tử - Nếu danh sách rỗng danh sách có phần tử sau xóa, hàm trả giá trị NULL - Nếu danh sách có nhiều phần tử sau xóa, hàm trả trỏ phần tử kế sau pHead Cho danh sách liên kết đơn đó, phần tử chứa số nguyên Hãy viết hàm xóa phần tử có giá trị lớn danh sách Lưu ý: - Chỉ phép duyệt danh sách lần - Nếu có nhiều phần tử lớn giống xóa phần tử Giả sử ta cần lưu trữ danh sách gồm N sinh viên (N chưa biết trước) Mỗi sinh viên có thuộc tính liệu sau: - Mã SV: chuỗi ký tự - Họ tên: chuỗi 50 ký tự - Ngày sinh: dd/mm/yyyy - Điểm trung bình: số thực - Phái: Nam/Nữ Yêu cầu: a Hãy trình bày cấu trúc liệu khác để lưu trữ danh sách nêu Với cấu trúc liệu, hãy: i Khai báo cấu trúc C/C++ ii Cho biết cần byte để lưu trữ N phần tử? b Lập bảng so sánh (ngắn gọn, tối đa tiêu) hai cấu trúc liệu theo mẫu sau: Chỉ tiêu so sánh Cấu trúc liệu © Nguyen Tri Tuan – Khoa CNTT, trường ĐH.KHTN Tp.HCM Cấu trúc liệu 2/2 CẤU TRÚC DỮ LIỆU & GIẢI THUẬT HOMEWORK 5.2 – Ngăn xếp, Hàng đợi -oOo Giả sử có class Stack khai báo trang 27, chương a Hãy viết lệnh để thực yêu cầu sau: - Khai báo stack S có N phần tử kiểu int Khởi tạo S rỗng - Đưa giá trị sau vào S: 15, 8, 6, 21 - Lấy 21 khỏi S - Lấy khỏi S - Gán giá trị  99 vào S - Lần lượt lấy phần tử S in lên hình b Cho mảng a chứa N số nguyên (giá trị từ đến N) Hãy viết lệnh để đảo ngược phần tử mảng a Cho ngăn xếp s đoạn chương trình sau: struct STACK s; InitStack(s, 10); // khởi tạo stack s rỗng, maxsize=10 int x, y = 5; Push(s, 8); // push vào s Push(s, y); Push(s, 9); Pop(s, x); // lấy phần tử đỉnh stack lưu vào x Push(s, 18); Pop(s, x); Push(s, 22); while (IsEmpty(s) == 0) { Pop(s, x); printf(“%d “, x); } Hãy cho biết kết thi hành đoạn code ? Ta có lựa chọn: Stack; Queue; List; Cả CTDL khơng thích hợp Trong tình sau, cho biết áp dụng lựa chọn thích hợp nhất: a Các khách hàng quầy bán vé xe lửa lấy số thứ tự để mua vé b Một danh sách tên theo thứ tự ABC c Các số nguyên cần phải thứ tự d Danh sách hàng bán ngày quầy thâu ngân siêu thị e Chương trình có sử dụng kỹ thuật Back-tracking f Các máy bay chờ đáp xuống phi trường Thuật toán Balan ngược Cho biểu thức số học dạng hậu tố (postfix) Hãy áp dụng thuật tốn Ba Lan ngược để tính tốn giá trị biểu thức Ghi rõ trạng thái stack qua bước tính tốn © Nguyen Tri Tuan – Khoa CNTT, trường ĐH.KHTN Tp.HCM 1/3 a 10 + * * - / + b + * + / + * Hãy áp dụng thuật toán Balan ngược để biến đổi biểu thức sau thành dạng postfix: (2+6/(8–5))*9 Trình bày trạng thái stack sau lần có thay đổi Tính giá trị biểu thức postfix, ghi rõ trạng thái stack qua bước tính tốn Hãy áp dụng thuật tốn Balan ngược để viết chương trình chuyển đổi biểu thức dạng trung tố (infix) sang dạng hậu tố (postfix) tính giá trị biểu thức Chương trình cần báo lỗi biểu thức có lỗi dấu ngoặc đơn: thiếu hay thừa dấu “(“ hay dấu “)”.Chỉ báo lỗi xuất Yêu cầu: - Input: biểu thức trung tố đọc từ file input.txt - Output: kết xuất file output.txt - File input.txt output.txt mặc định lưu thư mục với chương trình - Khơng phép sử dụng class stack có sẵn C++ - Biểu thức infix gồm số nguyên dương có chữ số dấu + - * / ( ) Ví dụ: input.txt output.txt 5+((1+2)*4)+3 512+4*+3+ 20 5+((1+2)*4+3 Lỗi thiếu dấu ) 5+(1+2)*4)+3 Lỗi thừa dấu ) Cho hàng đợi ban đầu sau: (hàng đợi có tối đa phần tử) Vẽ tình trạng hàng đợi, cho biết giá trị f, r tương ứng với lần thực thao tác sau: Thao tác f r Queue Bổ sung E vào hàng đợi Loại phần tử khỏi hàng đợi Bổ sung I, J, K vào hàng đợi Loại phần tử khỏi hàng đợi Bổ sung O vào hàng đợi Loại phần tử khỏi hàng đợi Stack Queue Giả sử cấu trúc liệu dùng để lưu trữ phần tử ngăn xếp hàng đợi danh sách liên kết đơn (có thơng tin phần tử đầu pHead phần tử cuối pTail) Hãy cho biết © Nguyen Tri Tuan – Khoa CNTT, trường ĐH.KHTN Tp.HCM 2/3 cài đặt thao tác THÊM VÀO LẤY RA ngăn xếp hàng đợi sử dụng thao tác danh sách liên kết đơn (AddHead, AddTail, RemoveHead, RemoveTail) cho hiệu nhất? Điền câu trả lời vào chỗ trống bảng sau: Ngăn Xếp Thuật ngữ Thao tác cài đặt Hàng Đợi Thuật ngữ Thao tác cài đặt Thêm vào Lấy Ra - Hết - © Nguyen Tri Tuan – Khoa CNTT, trường ĐH.KHTN Tp.HCM 3/3 CẤU TRÚC DỮ LIỆU & GIẢI THUẬT HOMEWORK 5.3 – Cây nhị phân tìm kiếm, Priority Queue -oOo Cây nhị phân là: a Cây có tối đa node b Cây mà node gốc có tối đa c Cây mà node phải có khác rỗng d Cây mà node có Cho cấu trúc cây: a Bậc (degree) node gốc Đúng Sai b Các node gốc gọi node (internal node) Đúng Sai Cho nhị phân hình vẽ bên Giả sử kết phép duyệt là: 12 20 18 15 Hãy cho biết tên phép duyệt cây? 10 Vẽ nhị phân tìm kiếm sau chèn khóa sau vào theo thứ tự từ trái qua phải Cây ban đầu rỗng Key = {17, 9, 26, 12, 11, 7, 30, 20, 21, 10} Sử dụng kết trên, vẽ lại BST xóa khóa 17 Trong hình bên cạnh: a Cây complete? b Cây full? Chứng minh nhị phân với chiều cao h có tối đa 2h-1 node © Nguyen Tri Tuan – Khoa CNTT, trường ĐH.KHTN Tp.HCM 1/5 Viết giải thuật (mã giả) duyệt theo mức Hãy điền thuật ngữ tiếng Anh vào chỗ trống: a Cây nhị phân: …………………………… b Cây nhị phân đầy đủ: …………………………… c Cây nhị phân hoàn chỉnh: …………………… ……… d Cây con: ………………………… e Node lá: ………………………… f Node gốc: ……………………… g Node cha: ………………………… h Node anh em: …………………………… i Node nội (node trong): …………………………… Cây nhị phân có chiều cao h=6 có tối đa ……… node 10 Đây có phải BST khơng? 11 Hãy vẽ hình BST thực thêm khóa theo thứ tự: leopard, cobra, shark, horse, alligator, bat, tiger, cow, cat, dog, chicken, bear 12 Hãy viết hàm tạo DSLK đơn từ BST cho trước, cho giá trị phần tử DSLK có thử tự giảm dần Trình bày ý tưởng viết thành hàm C/C++ 13 Cho BST, node số nguyên Nếu áp dụng cách duyệt NLR ta có kết sau: © Nguyen Tri Tuan – Khoa CNTT, trường ĐH.KHTN Tp.HCM 2/5 Nếu áp dụng cách duyệt LNR ta có kết sau: Hãy vẽ 14 Cho nhị phân hình Cho biết trước node P Hãy viết lệnh cần thiết để chuyển sang dạng 15 Cho nhị phân có chứa node sau (mỗi khóa xuất lần): Áp dụng cách duyệt NLR để tính tổng node lá, ta có kết tổng = 22 Áp dụng cách duyệt LNR để tính tổng node khơng phải node lá, ta có kết tổng = 18 Hãy node 16 Hãy viết hàm “Tìm phần tử lớn BST”: a Dùng đệ qui b Không dùng đệ qui 17 Vẽ BST thêm key sau theo thứ tự vào ban đầu rỗng E A S Y Q U E S T I O N 18 Cây BST ln ln có chi phí tìm kiếm O(log2N) Đúng Sai 19 Cho biết kết duyệt slide #77, chương theo cách: preorder, inorder, postorder? 20 Căn vào class BINARY_TREE slide #78, chương 5, cài đặt chi tiết hàm sau: a countNode: đếm số node b height: tính chiều cao 21 Căn vào class BINARY_SEARCH_TREE slide #94, chương 5, bổ sung cài đặt chi tiết hàm sau: a BSTNode *maxNode(): trả node có khóa lớn nhất, dùng đệ qui b BSTNode *minNode(): trả node có khóa nhỏ nhất, khơng dùng đệ qui © Nguyen Tri Tuan – Khoa CNTT, trường ĐH.KHTN Tp.HCM 3/5 22 Hình 1: tìm phần tử ptt cho node “5” Hình 2: tìm phần tử ptt cho node “15”? 23 Cho BST hình Hãy vẽ sau thực xóa node Áp dụng cách tìm phần tử thay Hình Sau xóa 8, dùng ptt cách Sau xóa 8, dùng ptt cách 24 Cho priority queue hình Hãy cho biết kết thao tác sau (mỗi thao tác độc lập nhau, thực hình 1) a insert(0) b deleteMin() Hình Sau insert(0) Sau deleteMin() © Nguyen Tri Tuan – Khoa CNTT, trường ĐH.KHTN Tp.HCM 4/5 25 Minh họa hình vẽ thực thao tác insert khóa vào Priority Queue: 15, 13, 9, 5, 12, 8, 7, 4, 0, 6, 2, 26 Minh họa hình vẽ thực thao tác deleteMin ba lần liên tiếp Priority Queue tập 25 - Hết - © Nguyen Tri Tuan – Khoa CNTT, trường ĐH.KHTN Tp.HCM 5/5 CẤU TRÚC DỮ LIỆU & GIẢI THUẬT HOMEWORK 5.4 – Cây AVL, Cây Đỏ-Đen, Cây AA -oOo Cây AVL Cho dãy key: 70, 12, 15, 10, 30, 40, 50, 90, 20, 60, 80, 100 a Hãy tạo AVL cách thêm key vào Vẽ bước có xảy thao tác cân Ghi hệ số cân node b Lần lượt xóa key=50 key=60 Vẽ lại sau xóa key Ghi hệ số cân node Cây Red-Black Cho dãy key: 70, 12, 15, 10, 30, 40, 50, 90, 20, 60, 80, 100 a Hãy tạo Red-Black cách thêm key vào Vẽ bước có xảy thao tác cân Ghi màu node b Lần lượt xóa key=50 key=60 Vẽ lại sau xóa key Ghi màu node Cây AA Cho dãy key: 70, 12, 15, 10, 30, 40, 50, 90, 20, 60, 80, 100 a Hãy tạo AA cách thêm key vào Vẽ bước có xảy thao tác cân Ghi mức (level) node b Lần lượt xóa key=50 key=60 Vẽ lại sau xóa key Ghi mức (level) node Cây AVL Cho nhị phân tìm kiếm với gốc Root (NODE *Root) Hãy viết hàm isAVL để kiểm tra xem có phải cân AVL hay không Prototype hàm là: // kết trả về: // + true: AVL // + false: AVL bool isAVL(NODE *p); Cây Red-Black Tính chất sau Red-Black: a Mọi đường dẫn từ gốc đến node phải có số lượng node đen b h = 191 c >= 192 Thuật toán Huffman tĩnh cần duyệt file (input) lần ? Chọn câu sai: a Static Huffman thuật tốn phải có tồn liệu (input) xử lý b Static Huffman thuật toán nén bảo tồn thơng tin c Trong số trường hợp đặc biệt, Huffman nhiều 511 node Thuật toán nén RLE Cho liệu sau: AAAAAAABCDFEEEEEEEGHJJJ[0xFE][0xFF][0xFF][0xFF][0x70] Hãy cho biết liệu dạng nén tương ứng với giải thuật nén: a RLE PCX (cải biên 1) © Nguyen Tri Tuan – Khoa CNTT, trường ĐH.KHTN Tp.HCM 1/2 b RLE BMP (cải biên 2) Ghi chú: liệu dấu [] số hexa tương đương byte Thuật toán nén Huffman tĩnh Áp dụng thuật toán nén Huffman tĩnh để nén chuỗi liệu sau: “KHOA CNTT DHKHTN” Vẽ (sau cùng), lập bảng mã bit cho loại ký tự, xác định chuỗi liệu sau nén (thể số hexa) 10 Thuật toán nén Huffman tĩnh Áp dụng thuật toán nén Huffman tĩnh để nén chuỗi liệu sau: “TTTH DHKHTN” Vẽ (sau cùng), lập bảng mã bit cho loại ký tự, xác định chuỗi liệu sau nén (thể số hexa) 11 Thuật toán nén Huffman động (*) Nén chuỗi liệu sau: “KHOA CNTT DHKHTN” thuật toán nén Huffman động Vẽ (trình bày trình), xác định chuỗi liệu sau nén (thể bit) 12 Giải nén Huffman động (*) Hãy áp dụng thuật toán giải nén, vẽ Huffman xác định kết giải nén cho chuỗi liệu mã hoá sau: ‘D’ ‘A’ 00 ‘T’ 11100 ‘S’ 1111100 ‘R’ 0100 ‘U’ 0000 ‘C’ 10111100111100 ‘E’ Biết rằng, ký tự 0/1 tương ứng với bit Các ký tự khác dấu nháy đơn tương ứng với byte (mã ASCII bit) Chỉ yêu cầu vẽ sau 13 Thuật toán nén RLE Viết chương trình cài đặt thuật tốn nén giải nén RLE dạng BMP (chương 6, slide số 23) - Chương trình sử dụng tham số dịng lệnh, theo cú pháp sau: Cú pháp Ý nghĩa RLE_BMP.EXE -e file1.txt file2.bin Nén (encode) file1.txt lưu kết nén vào file2.bin RLE_BMP.EXE -d file1.bin file2.txt Giải nén (decode) file1.bin lưu kết giải nén vào file2.txt - File TXT: file chứa liệu chưa nén, dạng file text VD File1.txt AAAAAAAAAAAAAAAAAAAAABBBBBBCDEFGHIJKKKKKKKKKKKKKKKKK KKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKLLLLLL LLLLLLLLLLLMMMMMMMNOPQRSTUVWWWWWWWWWWWWWWWWWW XYZ - File BIN: file chứa liệu nén, dạng file nhị phân - Hết - © Nguyen Tri Tuan – Khoa CNTT, trường ĐH.KHTN Tp.HCM 2/2 ... bước tiền xử lý thuật tốn Rabin-Karp là: (a) M (b) 2*M (c) O(N) Thuật toán MP/KMP Biết rằng: o T: chuỗi text, T = 0 1100 1 0100 1101 0101 0 1101 0100 001 o P: chuỗi mẫu cần tìm, P = 0101 10 0101 1 Hãy tính... cấu trúc liệu, hãy: i Khai báo cấu trúc C/C++ ii Cho biết cần byte để lưu trữ N phần tử? b Lập bảng so sánh (ngắn gọn, tối đa tiêu) hai cấu trúc liệu theo mẫu sau: Chỉ tiêu so sánh Cấu trúc liệu. .. 12 Giải nén Huffman động (*) Hãy áp dụng thuật toán giải nén, vẽ Huffman xác định kết giải nén cho chuỗi liệu mã hoá sau: ‘D’ ‘A’ 00 ‘T’ 1 1100 ‘S’ 111 1100 ‘R’ 0100 ‘U’ 0000 ‘C’ 101 1 1100 11 1100