創作內容

0 GP

ZeroJudge - a870: 10. List Maker 解題心得

作者:Not In My Back Yard│2019-08-23 22:30:40│贊助:0│人氣:18
題目連結:


題目大意:
對於一份清單,有三種指令可以對其操作:
ADD X ,代表將 X 加到清單的最尾端。
INSERT X N ,代表將 X 插到 N 的前面。
REMOVE X ,代表從清單移除 X 。
其中 X 、 N 皆為只由大寫字母組成的字串。

清單一開始是空的。給定若干數量的以上三種指令,輸入以「SHOW」結尾。求最後此清單的內容為何?將清單內的每個元素(字串)以一個空格分隔後輸出於一列。

注:原題沒有提及操作的合法性,但是經過測試,不會有刪除不存在的元素或是插入在不存在的元素之前的狀況發生。



範例輸入:
ADD NEVER
ADD COLLAR
INSERT CAT COLLAR
ADD DOG
ADD SCARES
INSERT ANYTHING CAT
REMOVE CAT
INSERT THAT SCARES
REMOVE COLLAR
INSERT WEAR ANYTHING
REMOVE DOG
ADD CAT
INSERT YOUR CAT
SHOW


範例輸出:
NEVER WEAR ANYTHING THAT SCARES YOUR CAT


解題思維:
此可作為鏈結串列(Linked List)的練習題。

定義鏈結串列中每個節點要儲存以下東西(下面是雙向的鏈結串列之範例):
一字串 S ,用以儲存題目給定的字串。
兩個指標 last 、 next ,分別用以指向前一個以及後一個節點的記憶體位置。兩者初始值皆為空指標。

然後宣告一個該種節點的指標 root,作為指向清單的開頭之用。

因此題目的三種指令:
ADD:
如果清單為空(root 為空指標),則創建一個新節點(內容為字串 X )並將 root 指向它;若非空,則從頭跑道尾端,然後將尾端節點的指標 next 指向新節點,並將新節點的 last 指向原本的尾端節點。尾端節點即指標 next 為空指標(代表沒有下一個節點)的那個節點。當然,也可以直接宣告並維護指向尾端的指標。

INSERT:
如果剛好開頭的節點恰為字串 N ,則開頭節點的 last 要指向新節點,新節點的 next 再指向開頭節點,最後將 root 指向新節點;不然,跑過一次清單的內容直到遇見內容 S 符合字串 N 的節點 B 。此時的情況較為複雜 ——
B 的前節點 P 之 next 要先指向新節點,並將新節點的 last 指向 P 。
接著將新節點的 next 指向 B ,最後將 N 的 last 指向新節點。

REMOVE:
如果開頭節點的內容正好為要刪除的字串 X  ,則分兩種情況:
一是清單只有開頭那個節點,則直接將清單清空(root 變為空指標);
二是開頭的 next 有指向下一個元素,則將該元素作為新開頭,並將新開頭的 last 清成空指標。
如果不是開頭的話,跟 INSERT 指令類似,跑過一次清單。找到欲刪除的節點 B 時,又分為兩種狀況:
B 為尾端的節點,因此直接將 B 的前一個節點(B 的 last 指向的那個)的 next 清為空指標,並刪除節點 B (清除該記憶體空間);
若 B 不是尾端,則 B 的前一個節點的 next 要指向 B 的下一個節點(B 的 next 所指之節點)且 B 的下一個節點的 last 要指向 B 的前一個節點。最後才刪除節點 B 。

指令結束後碰到「SHOW」,就跑過一次清單,並將沿途上的節點之內容輸出(記得要空一個空格)。


如果這題不用雙向(只有 next 指標)的話會比較麻煩,不能剛好跑到要插入或刪除的節點,否則沒辦法回去上一個節點讓其指向此節點的下一個,導致鏈結串列出錯。

此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。
引用網址:https://home.gamer.com.tw/TrackBack.php?sn=4505502
All rights reserved. 版權所有,保留一切權利

相關創作

同標籤作品搜尋:程式題目解題心得|鏈結串列(Linked List)

留言共 0 篇留言

我要留言提醒:您尚未登入,請先登入再留言

喜歡★inversion 可決定是否刪除您的留言,請勿發表違反站規文字。

前一篇:ZeroJudge - ... 後一篇:ZeroJudge - ...

追蹤私訊

作品資料夾

flys8028大家
食譜更新~清蒸石斑魚喵^~^歡迎來小屋逛逛呦~看更多我要大聲說4小時前


face基於日前微軟官方表示 Internet Explorer 不再支援新的網路標準,可能無法使用新的應用程式來呈現網站內容,在瀏覽器支援度及網站安全性的雙重考量下,為了讓巴友們有更好的使用體驗,巴哈姆特即將於 2019年9月2日 停止支援 Internet Explorer 瀏覽器的頁面呈現和功能。
屆時建議您使用下述瀏覽器來瀏覽巴哈姆特:
。Google Chrome(推薦)
。Mozilla Firefox
。Microsoft Edge(Windows10以上的作業系統版本才可使用)

face我們了解您不想看到廣告的心情⋯ 若您願意支持巴哈姆特永續經營,請將 gamer.com.tw 加入廣告阻擋工具的白名單中,謝謝 !【教學】