頁:
[1]
link list反轉(invert)
本帖最後由 st474ddr 於 2016-12-1 02:57 PM 編輯小弟剛開始學link list
看到一個習題是單純反轉link list
有個疑問 為什麼我不能輸入什麼就馬上輸出
這樣不是會更快嗎?
但是用online judge的系統卻沒辦法
是有什麼測資會爆炸嗎?
那我該如何從link list下手
如何讓1 2 3 4 5讀檔進去
link list 反轉後
變成5 4 3 2 1
求各位大大開導
...<div class='locked'><em>瀏覽完整內容,請先 <a href='member.php?mod=register'>註冊</a> 或 <a href='javascript:;' onclick="lsSubmit()">登入會員</a></em></div><div></div> 本帖最後由 CoNsTaRwU 於 2016-12-13 01:46 AM 編輯
reverse 在數學上的意義用 Agda 表達是:
data ℕ : Set where
zero : ℕ
suc : ℕ → ℕ
data Vect {l} (A : Set l) : ℕ → Set l where
[] : Vect A zero
_∷_ : ∀ {n} → A → Vect A n → Vect A (suc n)
insert : ∀ {l n} {A : Set l} → A → Vect A n → Vect A (suc n)
insert x [] = x ∷ []
insert x (y ∷ ys) = y ∷ (insert x ys)
reverse : ∀ {l n} {A : Set l} → Vect A n → Vect A n
reverse (x ∷ xs) = insert x (reverse xs)
reverse whatever = whatever
用 C++ 來實作的話,SGI 版本的 stl 的 std::list 對 reverse 的實作大約是像這樣(我大約寫的,不一定完全相同):
void
M_reverse_() noexcept
{
list_node_base_* tmp__ = this;
do
{
std::swap(tmp__->...<div class='locked'><em>瀏覽完整內容,請先 <a href='member.php?mod=register'>註冊</a> 或 <a href='javascript:;' onclick="lsSubmit()">登入會員</a></em></div> 本帖最後由 hf387 於 2017-1-16 12:56 AM 編輯
可以一開始就反著連
新的 Node 往前一個 Node 連
Head 指向新的 Node
簡單寫大概這樣吧(沒驗證)
Node* mHead = NULL;
Node* mNode = new Node;
mNode->next = mHead;
mHead = mNode;
hi, 你可以學學stl 裡面有很多好用的容器
自己做太累的 不然網路上也有很多範例 你可以用 doubly linked list 偷吃步,不過既然會考你 link list 反轉,應該是要考你如何將單向 linked list 反轉,你需要同時用三個變數紀錄前一個、後一個、和現在的節點,演算法如下:static wznode *
wz_invert_node(wznode * node) { /* node must not be NULL */
wznode * root;
wznode * c = node; /* c => child */
wznode * n = c->parent; /* n => node */
wznode * p; /* p => parent */
for (;;) {
if (n == NULL) {
root = c;
break;
}
p = n->...<div class='locked'><em>瀏覽完整內容,請先 <a href='member.php?mod=register'>註冊</a> 或 <a href='javascript:;' onclick="lsSubmit()">登入會員</a></em></div><br><br><br><br><br><div></div>
頁:
[1]