EECS Data Structures, HW3 Bus Route Editing Operations

Bus Route Editor
NTHU ITRI
Mackay
HCHS TSMC
KFSH
EECS Data Structures, HW3
Bus Route Editing Operations
• INSERT (src, dst, new, method)
• src: the name of the source bus stop
• dst: the name of the destination bus stop, which is next
to the src stop
• new: the name of the newly added bus stop
• method:
• 1: insert the new stop in between srcdst
• 2: In addition to srcdst, also insert the same stop in between
dstsrc if appropriate
• DELETE (name)
• Delete the named bus stop
NTHU
NTHU Mackay TSMC
TSMC
Insert (NTHU, TSMC, Mackay, 2)
Insert (TSMC, NTHU, Mackay, 2)
or
src, dst, new, method
NTHU TSMC
NTHU
Mackay
TSMC
Insert (NTHU, TSMC, Mackay, 1)
src, dst, new, method
NTHU TSMC
NTHU TSMC
Mackay
Insert (TSMC, NTHU, Mackay, 1)
src, dst, new, method
NTHU TSMC
Mackay
NTHU TSMC
Mackay KFSH
Insert (TSMC, Mackay, KFSH, 1)
Insert (TSMC, Mackay, KFSH, 2)
or
src, dst, new, method
Delete (Mackay)
NTHU ITRI
Mackay
HCHS MTK
KFSH
NTHU ITRI
Mackay
HCHS MTK
KFSH
NTHU ITRI
Mackay
HCHS MTK
KFSH
Delete (ITRI)
NTHU
Mackay
HCHS MTK
KFSH
Delete (HCHS)
NTHU
Mackay
ITRI MTK
KFSH
NTHU ITRI
Mackay
HCHS MTK
KFSH
Delete (MTK)
NTHU
Mackay
ITRI HCHS
KFSH
NTHU ITRI
Mackay
HCHS MTK
KFSH
Delete (TSMC)
NTHU ITRI
Mackay
HCHS
TSMC
KFSH MTK
NTHU ITRI
Mackay
HCHS
KFSH MTK
Other Notes
• The bus route contains NTHU and TSMC in the
beginning
• NTHU is never deleted
• You have to use linked lists implemented yourself
to solve the problem
Input
10
INSERT NTHU TSMC APPLE 2
INSERT APPLE NTHU Mackay 1
INSERT APPLE Mackay KFSH 1
INSERT Mackay NTHU ITRI 2
DELETE ITRI
INSERT TSMC APPLE ITRI 2
DELETE APPLE
INSERT ITRI TSMC HCHS 1
INSERT TSMC ITRI MTK 2
DELETE TSMC
Number of operations bellow Each line is an operation
Output
• Traverse the final bus route from NTHU and back to
NTHU
NTHU->ITRI->HCHS->MTK->ITRI->KFSH->Mackay->NTHU
NTHU ITRI
Mackay
HCHS
KFSH MTK