st474ddr 該用戶已被刪除 | 本帖最後由 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
求各位大大開導
... |
|
|
| |
| |
CoNsTaRwU 該用戶已被刪除 | 若瀏覽伊莉的時侯發生問題或不正常情況,請使用Internet Explorer(I.E)。 本帖最後由 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__->M_next_, tmp__->M_prev_);
- tmp__ = tmp__->M_prev_;
- }
- while (tmp__ != this);
- }
- void
- reverse() noexcept
- { this->M_impl_.M_node_.M_reverse_(); }
複製代碼 ... |
|
如果瀏覽伊莉時速度太慢或無法連接,可以使用其他分流瀏覽伊莉,www01.eyny.com(02,03)。 |
| |
| |
- 最後登錄
- 2024-5-19
- 在線時間
- 739 小時
- 註冊時間
- 2016-9-11
- 閱讀權限
- 20
- 精華
- 0
- UID
- 3943214
- 帖子
- 573
- 積分
- 352 點
- 潛水值
- 3390 米
| 如果你忘記伊莉的密碼,請在登入時按右邊出現的 '找回密碼'。輸入相關資料後送出,系統就會把密碼寄到你的E-Mail。 本帖最後由 hf387 於 2017-1-16 12:56 AM 編輯
可以一開始就反著連
新的 Node 往前一個 Node 連
Head 指向新的 Node
簡單寫大概這樣吧(沒驗證)- Node* mHead = NULL;
- Node* mNode = new Node;
- mNode->next = mHead;
- mHead = mNode;
複製代碼 |
|
|
| |
| |
- 最後登錄
- 2024-5-18
- 在線時間
- 358 小時
- 註冊時間
- 2009-12-6
- 閱讀權限
- 20
- 精華
- 0
- UID
- 7321273
- 帖子
- 111
- 積分
- 0 點
- 潛水值
- 24810 米
| 如果發覺自己無法使用一些功能或出現問題,請按重新整理一次,並待所有網頁內容完全載入後5秒才進行操作。 hi, 你可以學學stl 裡面有很多好用的容器
自己做太累的 不然網路上也有很多範例 |
|
回覆中加入附件並不會使你增加積分,請使用主題方式發佈附件。 |
| |
| |
o_g349 該用戶已被刪除 | 若新密碼無法使用,可能是數據未更新。請使用舊密碼看看。 你可以用 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->parent;
- n->parent = c;
- if (p == NULL) {
- root = n;
- break;
- }
- c = n;
- n = p;
- }
- node->parent = NULL;
- return root;
- }
複製代碼 以這個例子說明,每個 node 都有自己的父節點,利用各自的父節點將節點們連接成一個單向 linked list,最頂端的父節點的父節點是 NULL,相當於單向 linked list 的尾巴,最底端的子節點相當於單向 linked list 的頭,這個函數將最底端的子節點作為輸入,然後將整條單向 linked list 反轉後回傳原本最頂端的父節點,也就是新的單向 linked list 的頭...
|
|
若有安裝色情守門員,可用無界、自由門等軟件瀏覽伊莉。或使用以下網址瀏覽伊莉: http://www.eyny.com:81/index.php |
| |
| |
Powered by Discuz!
© Comsenz Inc.
重要聲明:本討論區是以即時上載留言的方式運作,對所有留言的真實性、完整性及立場等,不負任何法律責任。而一切留言之言論只代表留言者個人意見,並非本網站之立場,用戶不應信賴內容,並應自行判斷內容之真實性。於有關情形下,用戶應尋求專業意見(如涉及醫療、法律或投資等問題)。 由於本討論區受到「即時上載留言」運作方式所規限,故不能完全監察所有留言,若讀者發現有留言出現問題,請聯絡我們。有權刪除任何留言及拒絕任何人士上載留言,同時亦有不刪除留言的權利。切勿上傳和撰寫 侵犯版權(未經授權)、粗言穢語、誹謗、渲染色情暴力或人身攻擊的言論,敬請自律。本網站保留一切法律權利。